Желтов Валериан Павлович рабочая программа
| Вид материала | Программа |
- Желтов Валериан Павлович рабочая программа, 429.63kb.
- Желтов Валериан Павлович рабочая программа, 191.04kb.
- Желтов Валериан Павлович рабочая программа, 122.37kb.
- Желтов Валериан Павлович рабочая программа, 128.93kb.
- Желтов Валериан Павлович рабочая программа, 163.82kb.
- Желтов Валериан Павлович рабочая программа, 137.22kb.
- Желтов Валериан Павлович рабочая программа, 203.95kb.
- Желтов Валериан Павлович рабочая программа, 238.36kb.
- Желтов Валериан Павлович рабочая программа, 202.16kb.
- Желтов Валериан Павлович рабочая программа, 306.84kb.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное образовательное учреждение
высшего профессионального образования
«Чувашский государственный университет имени И.Н.Ульянова»
Факультет дизайна и компьютерных технологий
«УТВЕРЖДАЮ»
Проректор по учебной работе
______________ А.Ю. Александров
«______»______________ 20__ г.
РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ
«Введение в алгоритмы»
Направление подготовки
231000 Программная инженерия
Профиль подготовки
Управление разработкой программных проектов
Квалификация (степень) выпускника
Бакалавр
Форма обучения
очная
Чебоксары
2011
Рабочая программа основана на требованиях Федерального государственного стандарта высшего профессионального образования по направлению подготовки 231000 Введение в алгоритмы, утвержденного Приказом Минобрнауки 9.11.2009 № 542.
Составитель: доцент Кузнецова Н.А. ____________
Рабочая программа рассмотрена и одобрена на заседании обеспечивающей кафедры – компьютерных технологий (протокол № _____ от ___________2010 г.).
Зав. кафедрой: профессор Желтов Валериан Павлович
Рабочая программа согласована с Методической комиссией выпускающего факультета Дизайна и компьютерных технологий.
Председатель комиссии, декан: профессор Желтов Валериан Павлович____________
СОГЛАСОВАНО:
Зам. начальника УМУ: доцент М.Ю. Харитонов ____________
1. Цели освоения дисциплины
Дисциплина предназначена для студентов второго курса, обучающихся по направлению 231000 «Программная инженерия».
Целью освоения дисциплины является ознакомление студентов с теоретическими и алгоритмическими основами базовых разделов теории алгоритмов.
В результате изучения дисциплины студенты должны:
- получить знания об основах теории алгоритмов;
- знать и уметь использовать теоретические основы и прикладные средства теории алгоритмов;
- иметь представление о тенденциях и перспективах развития инструментальных средств теории алгоритмов;
- уметь строить и анализировать алгоритмы для решения дискретных задач.
2. Место дисциплины в структуре ООП бакалавриата
Дисциплина относится к вариативной части профессионального цикла дисциплин ООП бакалавра по направлению 231000 «Программная инженерия», предназначена для студентов второго курса.
Для изучения данной дисциплины необходимы знания школьного курса математики, дисциплины 2 семестра «Математическая логика и теория алгоритмов».
3. Компетенции обучающегося, формируемые в результате освоения дисциплины
Процесс изучения дисциплины направлен на формирование следующих профессиональных компетенций:
научно-исследовательская деятельность:
готовность к использованию методов и инструментальных средств исследования объектов профессиональной деятельности (ПК-3);
умение готовить презентации, оформлять научно-технические отчеты по результатам выполненной работы, публиковать результаты исследований в виде статей и докладов на научно-технических конференциях (ПК-5);
проектная деятельность
- способность оценивать временную и емкостную сложность программного обеспечения (ПК-13);
В результате освоения дисциплины студент должен:
- Знать: основные понятия теории алгоритмов: интуитивная концепция алгоритма, уточнения понятия алгоритма (машины Тьюринга и нормальные алгоритмы Маркова), понятия вычислимости, разрешимости; основные неразрешимые массовые проблемы; временные и емкостные оценки алгоритмов.
- Уметь: составлять программы машин Тьюринга и схемы нормальных алгоритмов для решения простых вычислительных задач; проводить анализ алгоритмов.
4. Структура и содержание дисциплины
4.1. Структура дисциплины
Общая трудоемкость дисциплины составляет 3 зачетных единиц, 108 часов.
| № п/п | Раздел дисциплины | Семестр | Неделя семестра | Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах) | Формы текущего контроля успеваемости (по неделям семестра) Форма промежуточной аттестации (по семестрам) | ||||||
| Лекции | Практ. зан. | Лабор. зан. | КСР * | СРС ** | Всего | Из ауд. зан. в интер. форме | |||||
| 1 | Введение. Алгоритмы и вычислимость | 3 | 1-8 | 10 | | 6 | | 29 | 45 | | |
| 2 | Анализ алгоритмов | 3 | 9-16 | 22 | | 10 | | 29 | 61 | | |
| | Итого | 3 | | 32 | | 16 | 2 | 58 | 108 | 32 | зачет |
* Контроль самостоятельной работы: аудиторные занятия для проверки самостоятельной работы студентов, приема зачета, проведения текущих консультаций.
** Самостоятельная работа студента, включая курсовой проект, курсовую работу, расчетно-графические работы.
4.2. Содержание лекционных занятий
Введение. – 1 час.
Организация учебного процесса. Рекомендуемая литература. Цели и задачи курса, связь с другими дисциплинами.
1. Алгоритмы и вычислимость – 10 часов.
1.1. Задачи и алгоритмы – 2 часа.
Массовая проблема и индивидуальная задача. Неформальное определение алгоритма. Свойства алгоритма. Различные подходы к формализации понятия алгоритма.
1.2. Машина Тьюринга – 2 часа.
Неформальное описание машины Тьюринга. Внешний алфавит, алфавит состояний, функциональная схема, принцип работы. Вычислимые по Тьюрингу функции, основная гипотеза теории алгоритмов.
1.3. Рекурсивные функции – 2 часа.
Описание класса рекурсивных функций: базисные функции (нуль-функция, функция следования и функция-проектор), операторы суперпозиции, примитивной рекурсии и минимизации. Примитивно-рекурсивные и частично-рекурсивные функции. Тезис Черча.
1.4. Нормальные алгоритмы Маркова – 2 часа.
Алфавит, слова, простые и заключительные формулы. Подстановки и нормальные алгоритмы Маркова. Нормально вычислимые функции, принцип нормализации Маркова. Совпадение классов частично рекурсивных, нормально вычислимых и вычислимых по Тьюрингу функций.
1.5. Алгоритмически неразрешимые проблемы – 2 часа.
Алгоритмически неразрешимые проблемы. Нумерация алгоритмов, машин Тьюринга. Проблемы распознавания самоприменимости и применимости. Проблема остановки. 10-я проблема Гильберта. Проблема определения общерекурсивности алгоритма. Проблема эквивалентности алгоритмов.
2. Анализ алгоритмов -22 часа.
2.1. Сравнительные оценки алгоритмов – 4 часа.
Временная и емкостная сложность. Трудоемкость алгоритма, функции оценки трудоемкости алгоритма: лучший, худший и средний случай.
2.2. Классификация алгоритмов по виду функции трудоёмкости – 2 часа.
Классификация алгоритмов по виду функции трудоемкости: количественно-зависимые по трудоемкости алгоритмы, параметрически-зависимые, количественно-параметрические, порядково-зависимые.
2.3. Трудоемкость основных алгоритмических конструкций – 2 часа.
Элементарные операции. Трудоемкость основных алгоритмических конструкций: следования, ветвления и цикла.
2.4. Переход к временным оценкам – 4 часа.
Методики перехода к временным оценкам: пооперационный анализ, метод Гиббсона, метод прямого определения среднего времени.
2.5. Сложностные классы задач – 4 часа.
Теоретический предел трудоемкости задачи. Сложностные классы задач: класс P (задачи с полиномиальной сложностью), класс NP (полиномиально проверяемые задачи), класс NPC (NP – полные задачи).
2.6. Построение эффективных алгоритмов. Метод декомпозиции – 6 часов.
Метод декомпозиции.
4.3. Содержание лабораторных занятий
Алгоритмы и вычислимость. – 6 часов.
Применение машин Тьюринга к словам. Конструирование машин Тьюринга. – 2 часа.
Рекурсивные функции. – 2 часа.
Применение нормальных алгоритмов к словам. Нормально вычислимые функции. – 2 часа.
Анализ алгоритмов. -10 часов.
Оценка сложности алгоритмов. – 10 часов.
5. Образовательные технологии
В процессе изучения дисциплины используются:
• раздаточный материал для изучения лекционного материала;
• учебный материал в электронном виде;
• контрольные программы по курсу для подготовки к сдаче семестровой аттеста-
ции и экзамена;
• программное обеспечение в соответствии с содержанием дисциплины;
6. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины.
6.1. Перечень заданий для самостоятельной работы и проведения текущего контроля:
- Временная и емкостная сложность.
- Массовая проблема и индивидуальная задача.
- Неформальное определение алгоритма.
- Неформальное описание машины Тьюринга.
- Внешний алфавит, алфавит состояний, функциональная схема, принцип работы.
- Примитивно-рекурсивные и частично-рекурсивные функции. Тезис Черча.
- Алфавит, слова, простые и заключительные формулы.
- Подстановки и нормальные алгоритмы Маркова.
- Нумерация алгоритмов, машин Тьюринга.
- Проблема остановки. 10-я проблема Гильберта.
- Проблема определения общерекурсивности алгоритма.
- Проблема эквивалентности алгоритмов
- Элементарные операции.
- Теоретический предел трудоемкости задачи.
6.2. Перечень вопросов к промежуточной аттестации.
Вопросы к зачету по всему курсу:
- Задачи и алгоритмы. Свойства алгоритма.
- Машина Тьюринга
- Рекурсивные функции
- Нормальные алгоритмы Маркова
- Алгоритмически неразрешимые проблемы
-
Сравнительные оценки алгоритмов
Классификация алгоритмов по виду функции трудоёмкости
Трудоемкость основных алгоритмических конструкций
- Переход к временным оценкам
- Сложностные классы задач
- Построение эффективных алгоритмов. Метод декомпозиции
7. Учебно-методическое и информационное обеспечение дисциплины
а) основная литература:
- Игошин В.И. Математическая логика и теория алгоритмов: учеб. пособие для студ. высш. учеб. заведений / В.И. Игошин. – 2-е изд., стер. - М.: Академия, 2008. – 448 с.
- Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов: Учеб. Пособие для вузов / В.И. Игошин. – М.: Академия, 2005. – 304с.
- Анкудинов Г.И., Анкудинов И.Г., Петухов О.А. Математическая логика и теория алгоритмов: Учеб. пособие.– 2-е изд. − СПб.: СЗТУ, 2003. - 104 c.
- Гамова Н. Математическая логика и теория алгоритмов. Саратов; Изд-во СГУ, 1999.-76с.
- Гуц А.К. Математическая логика и теория алгоритмов: Учебное пособие. – Омск: Издательство Наследие. Диалог-Сибирь, 2003. – 108с.
- Ершов Ю.Л., Палютин Е.А. Математическая логика. Учебное пособие. - СПб.: Лань, 2004. -336 с.
- Ковальский Р. Логика в решении проблем. - М.: Наука, 1990. - 280 с.
- Колмогоров А.Н., Драгалин А.Г. Математическая логика. Изд. 3-е, стереотипное. – М.: КомКнига, 2006. 240 с.
- Ульянов М.В., Шептунов М.В. Математическая логика и теория алгоритмов, часть 1: Математическая логика. – М.: МГАПИ, 2003. – 47 с.
- Ульянов М.В., Шептунов М.В. Математическая логика и теория алгоритмов, часть 2: Теория алгоритмов. – М.: МГАПИ, 2003. – 80 с.
б) дополнительная литература:
- Мощенский С.С. Лекции по математической логике. М.: Наука, 1970
- Судоплатов С.В., Овчинникова Е.В. Математическая логика и теория алгоритмов. Учебник. М.: Инфра-М, 2004. -224 с.
- Эдельман С.Л. Математическая логика: Учебное пособие для институтов / С.Л. Эдельман. – М.: Высшая школа, 1975. – 176с.
- Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир, 1982. – 416с.
- Лорьер Ж.-Л. Системы искусственного интеллекта. - М.: Мир, 1991. - 568 с.
- Матросов В.Л. Теория алгоритмов. - М.: Прометей, 1989.
- Тей А. и др. Логический подход к искусственному интеллекту: от классической логики к логическому программированию. - М.: Мир, 1990. - 432 с.
- Успенский В.А. Машина Поста. - М.: Наука, 1988.
- Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. - М.: Наука, 1987.
- Марков А.А., Нагорный Н.М. Теория алгоритмов. М.: Наука, 1984.
- Мендельсон Э. Введение в математическую логику. М.: Наука, 1984. 320с
в) программное обеспечение и Интернет-ресурсы
1.t.ru/department/algorithms/introalgo
2.u.ru/TFI/site_tfi/TFI/PVS/material/shaturn/theoralg
8. Материально-техническое обеспечение дисциплины
Для изучения дисциплины специально оборудованных кабинетов не требуется.