Анализ алгоритмов

Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

«Иркутский государственный педагогический университет»

Факультет математики, физики и информатики

Утверждено

на заседании совета факультета

математики, физики и информатики

протокол №­­­­­­_____от __________200 г.

Председатель совета________________

()

УЧЕБНАЯ ПРОГРАММА ДИСЦИПЛИНЫ

ОПД. Р.05. Анализ алгоритмов

Направление: 050200 Физико-математическое образование

Квалификация: бакалавр физико-математического образования

Курс: 2

Триместр: 4

Форма обучения: очная

Количество часов на дисциплину: 90 час.

Количество аудиторных часов: 45 час.; из них:

Лекций: 30 час.

Практических занятий: 15 час.

Самостоятельная работа: 45 час.

Итоговый контроль: зачет

I. ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЙ РАЗДЕЛ

Место дисциплины

Дисциплина «Анализ алгоритмов» является основной дисциплиной, формирующей базовое профессиональное физико-математическое образование в программе подготовки бакалавра.

Цель дисциплины

Цель дисциплины – дать научное обоснование понятию «алгоритм» и основы теории сложности алгоритмов, поднять алгоритмическую культуру студентов.

Задачи дисциплины

Задачи курса – познакомить студентов с математическими моделями алгоритмов, основными результатами в теории алгоритмов, методами построения и анализа алгоритмов.

Принципы отбора содержания и организации учебного материала

Учебный материал представлен двумя разделами: общая теория алгоритмов и методы построения и анализа алгоритмов. В основу отбора материала положен принцип обзора различных математических моделей алгоритмов и методов их построения и углубленное изучение некоторых таких моделей и методов.

Требования к освоению содержания дисциплины

Студент должен знать:

- основные модели алгоритмов,

- методы построения алгоритмов,

- вычисления сложности работы алгоритмов.

Студент должен уметь:

- разрабатывать алгоритмы для конкретных задач,

- находить сложность работы алгоритмов.

Студент должен владеть:

- методами доказательства корректности алгоритмов для типичных массовых проблем,

- методами доказательства неразрешимости массовых задач.

Виды контроля

Текущий – проводится по каждой учебной единице в форме проверки домашнего задания.

Рубежный – проводится по каждому из двух модулей в форме контрольных работ с рейтинговой оценкой.

Итоговый – проводится в форме зачета.

Планирование содержания дисциплины

№	Название модуля	Часы аудиторных занятий	Часы самостоятельной работы студента	Всего часов
Лекции	Практ. занятия
М.1	Математические модели алгоритмов.	12	8	15	35
М.2	Основные результаты теории алгоритмов	8	0	15	23
М.3	Построение и анализ алгоритмов.	10	7	15	32
	Итого	30	15	45	90

II. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ

Модуль №1 Математические модели алгоритмов.

1). Интуитивное понятие алгоритма и математические модели алгоритмов.

Примеры алгоритмов. Основные свойства интуитивного понятия алгоритма. Числовые функции: частичные, тотальные. Понятие интуитивно вычислимой функции и разрешимого множества. Необходимость математических моделей алгоритмов. Основные типы моделей алгоритмов.

2). Машины Тьюринга.

Машины Тьюринга как математическая модель алгоритма. Тезис Тьюринга. Вычисление функций на машинах Тьюринга. Построение машин Тьюринга.

3). Частично-рекурсивные функции.

Базисные функции: нулевая, следования, проекции. Операторы суперпозиции и примитивной рекурсии. Примитивно-рекурсивные функции. Оператор минимизации. Частично-рекурсивные функции. Тотально-рекурсивные функции. Примеры примитивно (частично, тотально)-рекурсивных функций. Тезис Черча.

4). Нормальные алгорифмы Маркова.

Нормальные алгорифмы Маркова как математическая модель алгоритма. Принцип нормализации Маркова. Вычисление функций нормальными алгорифмами.

5). Связь различных моделей алгоритмов.

Доказательство равнообъемности математических моделей алгоритмов: машин Тьюринга, частично-рекурсивных функций, нормальных алгорифмов Маркова.
Модуль №2 Основные результаты теории алгоритмов.

1). Рекурсивные и перечислимые множества.

Характеристическая функция множества. Определение рекурсивных и перечислимых множеств. Перечислимость рекурсивных множеств. Критерий рекурсивности.

2). Универсальные машины и универсальные функции.

Кодирование машин Тьюринга. Универсальная машина Тьюринга. Перечислимость множества частично-рекурсивных функций. Универсальная частично-рекурсивная функция. Существование универсальной функции для множества n-местных частично-рекурсивных функций.

3). Некоторые теоремы о вычислимых функциях.

Частичные и тотальные вычислимые функции. Доказательство не перечислимости множества тотально вычислимых функций. Существование не вычислимой функции. Неразрешимость проблемы определения тотальных функций в множестве частичных вычислимых функций. Пример частичной вычислимой функции, которую нельзя доопределить до тотальной вычислимой функции. Теорема Райса.

4). Алгоритмические проблемы.

Массовые алгоритмические проблемы. Неразрешимость проблемы остановки машин Тьюринга. Алгоритмическая сводимость. Обзор алгоритмически неразрешимых проблем.

Модуль №3 Построение и анализ алгоритмов.

1). Понятие сложности алгоритмов.

Различные понятия меры сложности алгоритмов. Скорость роста сложности алгоритмов. Асимптотическая сложность алгоритмов.

2). Алгоритмы сортировки.

Сортировка и определение сложности алгоритмов сортировки. Сортировка вставками. Пузырьковая сортировка. Сортировка выбором. Быстрая сортировка. Сортировка слиянием. Пирамидальная сортировка. Сортировка перечислением. Сортировка всплытием. Сортировка бинарным поиском. Алгоритмы сортировки использующие структуру элементов: цифровая сортировка, корневая сортировка.

3). Численные алгоритмы.

Вычисление значений булевых термов. Умножение матриц. Алгоритм Штрассена. Решение систем линейных уравнений.

4) Общая теория сложности алгоритмов.

Множества языков P и NP. Теорема о полиномиальной сводимости. NP-трудные и NP-полные задачи. Применение теории NP-полноты для анализа сложности алгоритмических проблем.

Основные понятия.

Математическая модель алгоритма; машина Тьюринга; нормальный алгорифм; частично-рекурсивная функция; массовая алгоритмическая проблема; рекурсивные и перечислимые множества; универсальные алгоритмы и универсальные функции; сложности алгоритмов; алгоритмы сортировки. Множества языков P и NP; NP-полные задачи.

III. ОРГАНИЗАЦИЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

I. Элементы программирования для машин Тьюринга.

Последовательное, параллельное и условное соединение машин Тьюринга. Итерация машин Тьюринга.

Задания для самостоятельной работы.

1.  Изучить теоретический материал по литературе из основного списка [2, 8] и из дополнительного списка [1-3].

2.  Выполнить задания:

a) По заданным машинам Тьюринга осуществить последовательное соединение.

b) По заданным машинам Тьюринга осуществить параллельное соединение.

c) По заданным машинам Тьюринга осуществить условное соединение.

d) Осуществить программирования цикла на машинах Тьюринга.

Каждый студент получает индивидуальное задание по задачам вышеперечисленных типов.

Контроль. Решенные задачи сдаются на проверку преподавателю, теоретические вопросы выносятся на зачет.

2. Алгоритмы решения задачи коммивояжера.

Формулировка и подходы к решению задачи коммивояжера. Алгоритмы решения и их оценка.

Задания для самостоятельной работы.

3.  Изучить теоретический материал по литературе из основного списка [5-7, 10] и из дополнительного списка [5, 7].

4.  Выполнить задания:

a) Решить задачу коммивояжера точным алгоритмом.

b) Решить задачу коммивояжера двумя разными приближенными алгоритмами и сравнить результат.

Каждый студент получает индивидуальное задание по задачам вышеперечисленных типов.

Контроль. Решенные задачи сдаются на проверку преподавателю, теоретические вопросы выносятся на зачет.

IV. КОНТРОЛЬ КАЧЕСТВА ОСВОЕНИЯ ДИСЦИПЛИНЫ

1. Текущий контроль.

Проводится по каждой учебной единице в форме проверки домашнего задания.

2. Рубежный контроль.

Проводится по 1 и 2 модулям в форме контрольных работ с рейтинговой оценкой от 0 до 50 баллов. Тема первой контрольной работы «Построение математических моделей алгоритмов для вычисления функций». Тема второй контрольной работы «Алгоритмы сортировки и их сложность».

3. Итоговый контроль.

Проводится в форме зачета.

Вопросы и задания к зачету.

1. Интуитивное понятие алгоритма. Примеры алгоритмов. Основные свойства интуитивного понятия алгоритма.

2. Числовые функции: частичные, тотальные. Понятие интуитивно вычислимой функции.

3. Необходимость математических моделей алгоритмов. Основные типы моделей алгоритмов.

4. Машины Тьюринга. Машины Тьюринга как математическая модель алгоритма. Тезис Тьюринга.

5. Вычисление функций на машинах Тьюринга. Построение машин Тьюринга.

6. Частично-рекурсивные функции. Базисные функции: нулевая, следования, проекции. Операторы суперпозиции и примитивной рекурсии. Примитивно-рекурсивные функции. Оператор минимизации.

7. Тотально-рекурсивные функции. Примеры примитивно (частично, тотально)-рекурсивных функций. Тезис Черча.

8. Нормальные алгорифмы Маркова. Нормальные алгорифмы Маркова как математическая модель алгоритма.

9. Универсальные машины Тьюринга. Кодирование машин Тьюринга. Определение универсальной машины Тьюринга.

10. Перечислимость множества частично-рекурсивных функций.

11. Формулировка теоремы о неперечислимости множества тотально вычислимых функций. Формулировка теоремы о существовании невычислимой функции.

12. Формулировка теоремы о неразрешимости проблемы определения тотальных функций среди частичных вычислимых функций. Формулировка теоремы о частичной вычислимой функции, которую нельзя доопределить до тотальной вычислимой функции.

13. Алгоритмические проблемы. Массовые алгоритмические проблемы. Неразрешимость проблем самоприменимости и остановки машин Тьюринга.

14. Сортировка вставками.

15. Пузырьковая сортировка.

16. Сортировка выбором.

17. Быстрая сортировка.

18. Сортировка слиянием.

19. Пирамидальная сортировка.

20. Сортировка перечислением.

21. Сортировка всплытием.

22. Сортировка бинарным поиском.

23. Алгоритмы сортировки использующие структуру элементов: цифровая сортировка, корневая сортировка.

V. УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ

Рекомендуемая литература

Основная литература.

1.  Алексеев в теорию сложности алгоритмов. М.: Издательство ВМиК МГУ, 2002.

2.  Мальцев и рекурсивные функции. М.: Наука, 1986.

3.  , Нагорный алгорифмов. М.: ФАЗИС, 1996.

4.  Вычислимость. Введение в теорию рекурсивных функций. М.: Мир, 1983.

5.  Макконелл Дж. Анализ алгоритмов. Вводный курс. М.: Техносфера, 2002.

6.  , Максимова по теории множеств, математической логике и теории алгоритмов. М.: Физматлит, 1995.

7.  , Сапоженко и упражнения по дискретной математике. М.: Физматлит, 2004.

Дополнительная литература.

1.  Шоломов теории дискретных логических и вычислительных устройств. М.: Наука, 1980.

2.  Кузнецов математика для инженера. – СПб: Издательство «Лань», 2004.

3.  Зубков преобразователи информации. Учебное пособие. – Иркутск. Издательство ИГПУ, 2005.

4.  , Вычислимые функции. М.: МЦНМО, 1999.

5.  Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980.

6.  Сапоженко вопросы сложности алгоритмов. М.: Изд-во ВаиК МГУ, 2001.

7.  Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

8.  Макконелл Дж. Основы современных алгоритмов. М.: Техносфера, 2004.

9.  Алгоритмы: построение и анализ. М.: МЦНМО, 2001.

10.  Алгоритмы: введение в разработку и анализ. М.: Вильямс, 2006.

Электронно-программные средства.

1.  Компьютерные демонстрационные программы по математическим моделям алгоритмов (http://matinf/ – из внутривузовской сети, http://isttu. *****:82/ –из Интернета).

Компьютерные демонстрационные программы содержат справочник основных терминов, типичные примеры составления алгоритмов, возможность просмотра выполнения самостоятельно составленных алгоритмов.

2. Библиотека книг по теории алгоритмов на электронном носителе

(имеется на кафедре математической информатики).

Составитель: заведующий кафедрой математической информатики, профессор, доктор физ.-мат. наук .

Утверждено

на заседании кафедры

математической информатики

(протокол № ___ от __________ 200_ г.)

Зав. кафедрой ______________________

Утверждено

на заседании УМС факультета

математики, физики и информатики

(протокол № ___ от ___________ 200_ г.)

Председатель УМС___________________