[ МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
Ярославский государственный университет им. П.Г. Демидова
Математический факультет
УТВЕРЖДАЮ
Проректор по развитию образования
_Е.В.Сапир
"_"2012 г.
Рабочая программа дисциплины послевузовского профессионального образования (аспирантура) Теория алгоритмов и сложность вычислений по специальности научных работников 01.01.06 Математическая логика, алгебра и теория чисел Ярославль 2012 1.Цели освоения дисциплины Целями освоения дисциплины «Теория алгоритмов и сложность вычислений» в соответствии с общими целями основной профессиональной образовательной программы послевузовского профессионального образования (аспирантура) (далее - образовательная программа послевузовского профессионального образования) являются:
- усвоение аспирантами знаний об основных подходах к математическому уточнению интуитивного понятия алгоритм, их эквивалентности, о методах доказательства алгоритмической неразрешимости проблем, о способах оценки сложности выполнения алгоритмов;
- изучение вопросов применения понятий и методов теории алгоритмов в математике и ее приложениях, в частности, в исследованиях криптосистем;
- формирование у аспирантов общей математической культуры.
2.Место дисциплины в структуре ООП послевузовского профессионального образования (аспирантура) Дисциплина «Теория алгоритмов и сложность вычислений» относится к разделу «Обязательные дисциплины» (подраздел «Дисциплины по выбору аспиранта») образовательной составляющей образовательной программы послевузовского профессионального образования по специальности научных работников 01.01. Математическая логика, алгебра и теория чисел.
Дисциплина «Теория алгоритмов и сложность вычислений» играет важную роль в подготовке специалистов в области информатики и компьютерной безопасности.
Для изучения данной дисциплины необходимы знания и умения, полученные в процессе обучения по программам специалитета или бакалавриата – магистратуры (дисциплины «Алгебра» и «Математическая логика и теория алгоритмов»). Дисциплина «Теория алгоритмов и сложность вычислений» развивает и дополняет соответствующий раздел обязательной дисциплины «Специальность».
3. Требования к результатам освоения содержания дисциплины В результате освоения дисциплины «Теория алгоритмов и сложность вычислений»
обучающийся должен:
Знать: основные определения, понятия и проблемы теории алгоритмов.
Уметь: применять математический аппарат теории алгоритмов для решения профессиональных задач, в том числе с использованием вычислительной техники.
Владеть: аппаратом теории алгоритмов и основными подходами к оценке сложности выполнения алгоритмов.
4. Структура и содержание дисциплины «Теория алгоритмов и сложность вычислений»
Общая трудоемкость дисциплины составляет 3 зачетные единицы, 108 часов.
Курс № Раздел Виды учебной работы, Формы текущего Неделя п/п Дисциплины включая самостоятельную контроля успеваемости работу обучающихся, и (по неделям) трудоемкость (в часах) Форма промежуточной Форма обуч.: очная/заочная аттестации Лекций задачи курса. Обзор основных результатов.
интуитивном алгоритма сивные функции.
теории машин Тьюринга.
алгоритмов.
8.Недетерминирореферат 10. Неразрешимые Содержание разделов дисциплины.
Тема 1. Введение. Принципы построения и изучения курса. Краткое содержание.
Роль и место курса в формировании специалистов. Рекомендации по изучению курса, самостоятельной работе и литературе. О формах контроля и отчетности при изучении курса.
Тема 2. Алгоритмы в интуитивном смысле. Примеры алгоритмов из различных разделов математики: алгебры, теории чисел, математической логики, математического анализа, теории обыкновенных дифференциальных уравнений и т. д.
Основные свойства алгоритмов. Дискретность, детерминированность, элементарность шагов и массовость алгоритмов.
Тема 3. Уточнение понятия алгоритма. Необходимость математического уточнения интуитивного понятия алгоритма, примеры математических проблем, сформулированных в конце XIX -- начале XX в., приведших к уточнению понятия алгоритма.
Неразрешимые алгоритмические проблемы в теории алгоритмов, алгебре, математической логике, теории чисел, математическом анализе, топологии.
Тема 4. Машины Тьюринга. Внешний и внутренний алфавиты, команды и программа машины Тьюринга. Различные варианты машин Тьюринга: многоленточные и одноленточные, с одномерной и многомерной лентой, с потенциально бесконечной в обе стороны лентой, с непродолжаемой влево лентой и т. д.
Словарные алгоритмы, реализуемые машинами Тьюринга. Вычислимые по Тьюрингу функции. Правильная вычислимость по Тьюрингу. Вычислимость по Тьюрингу элементарных теоретико-числовых функций. Разрешимые и перечислимые множества слов.
Операции над машинами Тьюринга. Композиция машин Тьюринга. Разветвление.
Зацикливание. Диаграммы машин Тьюринга. Циклический сдвиг, копирование.
Тезис Тьюринга. Замкнутость класса правильно вычислимых по Тьюрингу функций относительно операций суперпозиции, примитивной рекурсии и минимизации. Тезис А.Тьюринга.
Тема 5. Частично рекурсивные функции. Простейшие (исходные) функции.
Операции суперпозиции, примитивной рекурсии и минимизации.
Примитивно рекурсивные функции. Примеры примитивно рекурсивных теоретикочисловых функций. Частично рекурсивные и рекурсивные функции, примеры.
Операции над примитивными, рекурсивными и частично рекурсивными функциями.
Тезис А. Черча. Нумерация пар и $n$-ок натуральных чисел. Нумерационные функции.
Рекурсивные и рекурсивно перечислимые множества и предикаты. Теорема Э.
Поста. Теорема о графике функции. Правильная вычислимость по Тьюрингу любой частично рекурсивной функции.
Тема 6. Арифметизация теории машин Тьюринга. Геделева нумерация слов в конечных и счетных алфавитах.
Нумерация команд и программ машин Тьюринга. Нумерация конфигураций.
Построение примитивно рекурсивных функций, описывающих работу машин Тьюринга. Частичная рекурсивность любой вычислимой по Тьюрингу функции.
Универсальные частично рекурсивные функции. Неразрешимость проблем останова, самоприменимости и бессмертия для машин Тьюринга.
Нормальная форма С. Клини. Универсальные машины Тьюринга.
Неразрешимые алгоритмические проблемы. Неразрешимость проблемы выводимости для полусистем Туэ. Неразрешимость проблемы равенства для полугрупп и групп. Теоремы А.А. Маркова и С.И. Адяна об алгоритмической неразрешимости проблем распознавания полугрупповых и групповых свойств. Неразрешимые проблемы в математической логике.
Тема 7. Сложность алгоритмов. Многоленточные машины Тьюринга: внешний и внутренний алфавиты, программы.
Сложностные характеристики работы машины Тьюринга: временная (число шагов) и емкостная (объем памяти), связь между ними.
Сложностные характеристики работы машины Тьюринга в худшем случае:
временная и емкостная сигнализирующие функции (сложности, характеристики алгоритма), связь между ними.
Сложностные классы. Другие сложностные характеристики.
Тема 8. Недетерминированные машины Тьюринга. Недетерминированные многоленточные машины Тьюринга: внешний и внутренний алфавиты, программы.
Классы P и NP. NP-трудные и NP-полные задачи.
Теорема Кука об NP-полноте проблемы выполнимости для логики высказываний.
Примеры NP-полных проблем из различных разделов математики: дискретной математики, теории булевых функций, математической логики, теории графов, алгебры, теории чисел, теории автоматов и языков и т. д.
Тема 9. Трудно разрешимые задачи. Нижние оценки. Задачи, требующие экспоненциального времени и памяти (из теории автоматов и языков, из теории разрешимых элементарных теорий, например, теорема Рабина - Фишера о сложности разрешения арифметики Пресбургера и поля действительных чисел).
Неэлементарные задачи. Определение класса элементарных функций. Задачи, требующие неэлементарного времени для решения: из теории регулярных выражений, из математической логики (неэлементарность элементарной сингулярной (слабой) теории функции следования, неэлементарность элементарной теории свободной группы и т. д.).
Тема 10. Неразрешимые алгоритмические проблемы в топологии, математическом анализе, теории дифференциальных уравнений.
Значение существования алгоритмически неразрешимых проблем и трудно разрешимых проблем для математики и ее приложений.
5. Образовательные технологии В преподавании используются методические пособия, программные комплексы.
В преподавании курса используются активные и интерактивные технологии проведения занятий в сочетании с внеаудиторной работой.
Часть практических занятий проводится в дисплейном классе с целью разработки, тестирования и модифицирования приложений, реализующих алгоритмы на графах.
6. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины и учебно-методическое обеспечение самостоятельной работы обучающихся В качестве средств текущего контроля используется 2 контрольных работы, а также написание в течение семестра 1 реферата на выбранную тему. Итоговая форма контроля (зачет) дает возможность выявить уровень профессиональной подготовки аспиранта по данной дисциплине.
1. Доказать примитивную рекурсивность функции [x sqrt (2)].
2. Доказать, что функция c(x,y) = ((x+y)^2 + 3x + y)/2 задает объективное отображение множества пар натуральных чисел на множество натуральных чисел.
3. Доказать примитивную рекурсивность функции S(x) – число делителей числа x.
4. Доказать примитивную рекурсивность функции Pi(x) – число простых чисел, не превосходящих числа x.
5. Доказать примитивную рекурсивность функции k(x, y) – наименьшее общее 6. Доказать примитивную рекурсивность функции d(x, y) – наибольший общий делитель чисел x и y..
1. Построить машину Тьюринга, правильно вычисляющую примитивно рекурсивную функцию S(x) – число делителей числа x.
2. Построить машину Тьюринга, правильно вычисляющую примитивно рекурсивную функцию Pi(x) – число простых чисел, не превосходящих числа x.
3. Построить машину Тьюринга, правильно вычисляющую примитивно рекурсивную функцию k(x, y) – наименьшее общее кратное чисел x и y.
4. Построить машину Тьюринга, правильно вычисляющую примитивно рекурсивную функцию d(x, y) – наибольший общий делитель чисел x и y..
1.Математические проблем, приведшие к уточнению понятия алгоритма.
2. Неразрешимые алгоритмические проблемы.
3. Машины Тьюринга и Поста 4.Разрешимые и перечислимые множества слов.
5.Диаграммы машин Тьюринга.
6. Примитивно рекурсивные, частично рекурсивные и рекурсивные функции.
7. Рекурсивные и рекурсивно перечислимые множества и предикаты.
8. Арифметизация теории машин Тьюринга.
9. Универсальные частично рекурсивные функции.
10. Неразрешимость проблем останова, самоприменимости и бессмертия для машин Тьюринга.
11. Универсальные машины Тьюринга.
12. Неразрешимые алгоритмические проблемы.
13. Сложность алгоритмов. Сложностные классы.
14. Недетерминированные многоленточные машины Тьюринга.
15. Классы P и NP. NP-трудные и NP-полные задачи.
16. Теорема Кука об NP-полноте проблемы выполнимости для логики высказываний.
17. Трудно разрешимые задачи.
18. Теорема Рабина -- Фишера о сложности разрешения арифметики Пресбургера и поля действительных чисел).
19. Неэлементарные задачи.
20. Нормальные алгорифмы А.А. Маркова.
21. Сложность описания алгоритма как средство доказательства существования алгоритмически неразрешимых проблем.
22. Диофантовы множества и функции. 10-ая проблема Д.Гильберта.
23. Неразрешимые алгоритмические проблемы в топологии, математическом анализе, теории дифференциальных уравнений.
1. Алгоритмы в интуитивном смысле. Примеры алгоритмов из различных разделов математики: алгебры, теории чисел, математической логики, математического анализа, теории обыкновенных дифференциальных уравнений и т. д.
2. Основные свойства алгоритмов. Дискретность, детерминированность, элементарность шагов и массовость алгоритмов.
3. Необходимость математического уточнения интуитивного понятия алгоритма, примеры математических проблем, сформулированных в конце XIX -- начале XX в., приведших к уточнению понятия алгоритма.
4. Неразрешимые алгоритмические проблемы в теории алгоритмов, алгебре, математической логике, теории чисел, математическом анализе, топологии.
5. Машины Тьюринга. Внешний и внутренний алфавиты, команды и программа машины Тьюринга. Различные варианты машин Тьюринга: многоленточные и одноленточные, с одномерной и многомерной лентой, с потенциально бесконечной в обе стороны лентой, с непродолжаемой влево лентой и т. д.
6. Словарные алгоритмы, реализуемые машинами Тьюринга. Вычислимые по Тьюрингу функции. Правильная вычислимость по Тьюрингу. Вычислимость по Тьюрингу элементарных теоретико-числовых функций.
7. Разрешимые и перечислимые множества слов.
8. Операции над машинами Тьюринга. Композиция машин Тьюринга. Разветвление.
Зацикливание. Диаграммы машин Тьюринга. Циклический сдвиг, копирование.
9. Тезис Тьюринга. Замкнутость класса правильно вычислимых по Тьюрингу функций относительно операций суперпозиции, примитивной рекурсии и минимизации.
Тезис А.Тьюринга.
10. Примитивно рекурсивные, частично рекурсивные и рекурсивные функции.
Простейшие (исходные) функции. Операции суперпозиции, примитивной рекурсии и минимизации.
Примитивно рекурсивные функции. Примеры примитивно рекурсивных теоретикочисловых функций.
Частично рекурсивные и рекурсивные функции, примеры.
11. Операции над примитивными, рекурсивными и частично рекурсивными функциями. Тезис А. Черча.
12. Нумерация пар и $n$-ок натуральных чисел. Нумерационные функции.
13. Рекурсивные и рекурсивно перечислимые множества и предикаты. Теорема Э.
Поста.
Теорема о графике функции.
14. Правильная вычислимость по Тьюрингу любой частично рекурсивной функции.
15. Арифметизация теории машин Тьюринга. Геделева нумерация слов в конечных и счетных алфавитах.
Нумерация команд и программ машин Тьюринга. Нумерация конфигураций.
Построение примитивно рекурсивных функций, описывающих работу машин Тьюринга.
Частичная рекурсивность любой вычислимой по Тьюрингу функции.
16. Универсальные частично рекурсивные функции.
17. Неразрешимость проблем останова, самоприменимости и бессмертия для машин Тьюринга.
Нормальная форма С. Клини.
18. Универсальные машины Тьюринга.
19. Неразрешимые алгоритмические проблемы. Неразрешимость проблемы выводимости для полусистем Туэ.
Неразрешимость проблемы равенства для полугрупп и групп.
Теоремы А.А. Маркова и С.И. Адяна об алгоритмической неразрешимости проблем распознавания полугрупповых и групповых свойств.
Неразрешимые проблемы в математической логике.
20. Сложность алгоритмов. Многоленточные машины Тьюринга: внешний и внутренний алфавиты, программы.
Сложностные характеристики работы машины Тьюринга: временная (число шагов) и емкостная (объем памяти), связь между ними.
Сложностные характеристики работы машины Тьюринга в худшем случае:
временная и емкостная сигнализирующие функции (сложности, характеристики алгоритма), связь между ними.
Сложностные классы.
Другие сложностные характеристики.
21. Недетерминированные машины Тьюринга. Недетерминированные многоленточные машины Тьюринга: внешний и внутренний алфавиты, программы.
NP-трудные и NP-полные задачи.
Теорема Кука об NP-полноте проблемы выполнимости для логики высказываний.
Примеры NP-полных проблем из различных разделов математики: дискретной математики, теории булевых функций, математической логики, теории графов, алгебры, теории чисел, теории автоматов и языков и т. д.
22. Трудно разрешимые задачи. Нижние оценки. Задачи, требующие экспоненциального времени и памяти (из теории автоматов и языков, из теории разрешимых элементарных теорий, например, теорема Рабина - Фишера о сложности разрешения арифметики Пресбургера и поля действительных чисел).
23. Неэлементарные задачи. Определение класса элементарных функций. Задачи, требующие неэлементарного времени для решения: из теории регулярных выражений, из математической логики (неэлементарность элементарной сингулярной (слабой) теории функции следования, неэлементарность элементарной теории свободной группы и т. д.).
24. Диофантовы множества и функции. 10-ая проблема Д.Гильберта.
Теорема М.Девиса - Х.Путнам - Дж.Робинсон - Ю.В.Матиясевича.
Неразрешимые алгоритмические проблемы для систем линейных диофантовых уравнений.
Неразрешимые алгоритмические проблемы для систем уравнений в свободных группах и полугруппах.
25. Неразрешимые алгоритмические проблемы в топологии, математическом анализе, теории дифференциальных уравнений.
Значение существования алгоритмически неразрешимых проблем и трудно разрешимых проблем для математики и ее приложений.
7. Учебно-методическое и информационное обеспечение дисциплины а) основная литература:
1. Дурнев, В. Г., Материалы по дисциплине "Теория алгоритмов и сложность вычислений" : метод. указания / В. Г. Дурнев ; Яросл. гос. ун-т, Ярославль, ЯрГУ, 2. Дурнев, В. Г., Элементы теории алгоритмов : учеб. пособие для вузов / В. Г.
Дурнев ; Яросл. гос. ун-т, Ярославль, ЯрГУ, 2008, 247c 3. Мальцев А.И. Алгоритмы и рекурсивные функции. М.: Наука, 1986.
4. Марков А.А., Нагорный Н.М. Теория алгорифмов. М.: Наука, 1984.
5. Мендельсон Э. Введение в математическую логику. М.: Наука, 1976.
б) дополнительная литература 6. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. М.: Мир, 7. Адян С.И. Алгоритмическая неразрешимость проблем распознавания некоторых свойств групп // Докл. АН СССР. 1955. Т. 103. С.533-535.
8. Адян С.И., Дурнев В.Г. Алгоритмические проблемы для групп и полугрупп //Успехи матем. наук. 2000. Том 55.С.3-94.
9. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1983.
10. Булос Дж., Джеффри Р. Вычислимость и логика. М.: Мир, 1994.
11. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.М.: Мир, 12. Дурнев В.Г. О позитивных формулах на свободных полугруппах //Сиб. матем.
журн. 1974. Т. 25. С.1131-1137.
13. Дурнев В.Г. Неразрешимость позитивной 3-теории свободной полугруппы //Сиб.
матем. журн. 1995. Т. 36. С.1067-1080.
14. Дурнев В.Г. Об уравнениях на свободных полугруппах и группах //Матем. заметки.
1974. Т. 16. С.717-724.
15. Колмогоров А.Н., Успенский В.А. К определению понятия алгоритма //Успехи мат.
наук. 1958. Т. 13. Вып. 4. С.3-28.
16. Кормен, Т., Алгоритмы : построение и анализ : учеб. пособие / Т. Кормен, Ч.
Лейзерсон, Р. Ривест, М., МЦНМО, 2001, 955c 17. Маканин Г.С. К проблеме тождества в конечно-определенных полугруппах //Докл.
АН СССР. 1966. Т. 171. С.285-287.
18. Маканин Г.С. Проблема разрешимости уравнений в свободной полугруппе //Мат.
сб. 1977. Т. 103(145). С.147-236.
19. Манин Ю.И. Вычислимое и невычислимое. М.: Советское радио, 1979.
20. Марков А.А. Невозможность некоторых алгоритмов в теории ассоциативных систем // ДАН СССР. 1947. Том55. С.587-590.
21. Марков А.А. Неразрешимость проблемы гомеоморфии //Докл. АН СССР. 1958. Т.
121. С.218-220.
22. Марков А.А. К проблеме представимости матриц //Z. Math. Log. und Grundl. Math.
1958. Т. 4. С.157-168.
23. Марченков С.С. Неразрешимость позитивной - теории свободной полугруппы //Сиб. мат. журн. 1982. Т. 32. С.196-198.
24. Матиясевич Ю.В. Простые примеры неразрешимых ассоциативных исчислений //Докл. АН СССР. 1967. Т. 173. С.1264-1266.
25. Матиясевич Ю.В. Диофантовость перечислимых множеств //Докл. АН СССР. 1970.
Т. 130. С.495-498.
26. Новиков П.С. Об алгоритмической неразрешимости проблемы тождества теории групп //Докл. АН СССР. 1952. Т. 85. С.709-712.
27. Семенов А.Л. Интерпретация свободных алгебр в свободных группах //ДАН СССР.
1980. Том252. С.1326-1332.
28. Трахтенброт Б.А. Алгоритмы и вычислительные автоматы. М.: Советское радио, 29. Цейтин Г.С. Относительно проблемы распознавания свойств ассоциативных исчислений //Докл. АН СССР. 1956. Т. 107. С.209-212.
30. Цейтин Г.С. Ассоциативное исчисление с неразрешимой проблемой эквивалентности //Труды матем. ин-та. АН СССР. 1958. Т. 52. С.172-189.
31. ЭббинхаузГ.Д., ЯкобсК., МанФ.К., ХермесГ. Машины Тьюринга и рекурсивные функции. М.: Мир, 1972.
32. Churh A. An unsolvable problem of elementary number theory //Amer. J. Math. 1936.
Vol.58. P.345-363.
33. Churh A. A note on the Entscheidungsproblem // J. SymbolicLogic. 1936. Vol.1. P.40Dehn M. Uber unendliche diskontinuerliche Gruppen //Math.Ann. 1911. Bd. 71. S.116Post, E. Intoduction to a general theory of elementary propositions //Amer. J. Math. 1921.
Vol.43.P.163-185.
36. Post E.L. Finite combinatory processes - formulation 1 //Journal of Symbolic Logic.
1936. Vol.1. P.103-105.
37. Post E.L. A variant of a recursively unsolvable problem //Bull. Amer. Math. Soc. 1946.
Vol.52. P.264-268.
38. Post E.L. Recursive unsolvability of a problem of Thue //J. Symbol Log. 1947. Vol.12.
P.1-11.
39. Rado T. On non-computable functions //Bell System Technical Journal. 1962. P.877-884.
40. Quine W. Concatenation as a basis for arithmetic //J. Symbol Log. 1946. Vol.11. P.105Hall M.Jr. The word problem for semi-groups with two generators //J. Symbolic Logic, 1949. V. 14. P.115-118.
42.Thue. Problem uder Veranderungen von Zeichenreihen nach gegebehen Regeln //Vid.
Skr. Math.-natur. KI. 1914.
43 ietze H. \"Uber topologischen Invarianten mehrdimensionaler Mannigfaltigkeiten //Monatsh. Math. Phys. 1908. Vol.19. P.1-118.
44 Turing A.M. On computable numbers, with an application to the Entscheidugsproblem //Proceedings of London Mathematical Society. Ser. 2. 1936. Vol.42. P.230-265.
45 Scott D. A short recursively unsolvable problem (abstract) //J. Symbol. Log. 1956. Vol.
21. P.11-112.
б) программное обеспечение и Интернет-ресурсы:
1. Электронная библиотека ЯрГУ: http://www.lib.uniyar.ac.ru 2. http://mech.math.msu.su/department/ 8. Материально-техническое обеспечение дисциплины Аудитории для лекций и практических занятий (с необходимым материальным оснащением). Наличие рекомендованной литературы. Наличие электронных версий методических материалов.
Программа составлена в соответствии с федеральными государственными требованиями к структуре основной профессиональной образовательной программы послевузовского профессионального образования (аспирантура) (приказ Минобрнауки от 16.03.2011 г. № 1365) с учетом рекомендаций, изложенных в письме Минобрнауки от 22.06.2011 г. № ИБ – 733/12.
Программа одобрена на заседании кафедры компьютерной безопасности и математических методов обработки информации 02.10.2012 (протокол № 2).
профессор профессор
«