Рабочая программа по дисциплине «теория алгоритмов и сложности» для специальности 351400 Прикладная информатика (по областям) Форма обучения: очная
| Вид материала | Рабочая программа |
- Рабочая программа по дисциплине «логика» для специальности 351400 Прикладная информатика, 292.77kb.
- Учебно-методический комплекс для студентов заочного обучения специальности Прикладная, 81.9kb.
- Паспорт (государственный стандарт) Специальности «прикладная информатика (по областям)», 504.1kb.
- Рабочая программа дисциплины: интеллектуальные информационные системы для специальностей:, 369.71kb.
- Программа по курсу "Математика. Алгебра и геометрия" для специальности 080801 (351400), 143.45kb.
- Рабочая программа по курсу Проектирование информационных систем для специальностей, 202.08kb.
- Рабочая программа дисциплины для магистрантов направления «Прикладная математика, 128.62kb.
- Рабочая программа учебной дисциплины «теория систем и системный анализ» Направление, 223.11kb.
- Рабочая программа по курсу «Мировые информационные ресурсы» 351400 «Прикладная информатика, 315.91kb.
- Учебно-методический комплекс для студентов заочного обучения специальности Прикладная, 88.44kb.
Лекция 10. Элементарные по Кальмару функции
Определение, свойства и примеры функций, множеств и отношений, элементарных по Кальиару.
Контрольный вопрос:
Элементарна ли по Кальмару характеристическая функция
множества совершенных чисел?
Лекция 11. Классы, основанные на ограниченной рекурсии. Классы функций и предикатов ограниченной вычислительной сложности
Определение, свойства и примеры классов функций, множеств и отношений, основанных на ограниченной рекурсии.
Контрольный вопрос:
Определить с помощью ограниченной рекурсии функцию
f(x,y,z) = [x/y**z]
Классы функций и предикатов ограниченной вычислительной сложности
Если Compl - мера сложности какой-то модели вычислений, а Bounds
- класс верхних границ сложности для этой меры сложности, то
сложностным классом BoundCompl называется класс множеств, для
которых существуют разрешающие алгоритмы на данной модели
вычислений удовлетворяющие некоторым границам из Bound для меры
сложности Compl.
Примеры Compl:
- Space - требуемый объем памяти (например в битах),
- Time - требуемое время вычисления (например, в тактах
процессора),
Функции класса Bound, как правило - функции длины записи
аргумента вычисляемой (характеристической) функции.
Примеры Bound:
- Log - логарифмические функции (натуральнозначные приближения,
объем памяти, занимаемой аргументом не считается, требуется
произвольный (прямой) доступ к элементам аргумента),
- Lin - линейные функуции,
- Poly - многочлены,
- Exp - показательные функции.
Примеры сложностных классов:
- P=PolyTime
- PSPACE=PolySpace
Известные соотношения между некоторыми сложностными классами
(теоремы):
- LogSpace - подмножество P (строгость включения неизвестна),
- LogSpace - строгое подмножество LinSpace (иерархия),
- P не равно LinSpace (детали не известны),
- P - строгое подмножество ExpSpace (иерархия),
- LinSpace - подмножество ExpTime (строгость включения
неизвестна),
- LinSpace - строгое подмножество PSPACE (иерархия),
- ExpTime - подмножество ExpSpace (строгость включения
неизвестна),
- ExpTime не равно PSPACE (детали неизвестны),
- PSPACE - строгое подмножество ExpSpace (иерархия).
Лекция 12. Методы оценки сложности вычислений и алгоритмов.
Доказуемо трудные задачи. Полные переборные задачи
В качестве доказуемо трудных задач рассматриваются задачи
установления принадлежности произвольного элемента заданному
множеству, то есть задачи вычисления характеристических функций
этих множеств. Доказуемая трудность такой задачи есть доказуемая
трудность соответствующего множества.
Множество называется доказуемо трудным относительно сложностного
класса C, если можно доказать что это множество не принадлежит
классу C.
Примеры доказуемо трудных задач относительно класса P:
- ограниченная арифметика Беннета (арифметика в сигнатуре:
- переменные x[i],
- 0, 1,
- +, *, =, меньше, &, или,
- для всех ..., меньших ..., выполнено ...
- для некоторых ..., меньших ..., выполнено ...)
- ограниченная теория слов в конечном алфавите (теория Смульяна:
то же, что и в предыдущем случае, но константы - алфавит, а
единственная операция - сцепление слов, вместо "меньше" -
"короче"),
- теория логических функций (переменные и константы для
логических значений и n-местных логических функций, применения
функций к формулам, кванторы по логическим значениям и
функциям).
Полные переборные задачи
Классом переборных задач называется класс NP?, определенный
ниже.
Множество M принадлежит NP, если найдется такое множество M' из
класса P и такой многочлен p, что принадлежносто произвольного
элемента x длины n множеству M эквивалентна существованию такого
y длины p(n), что xy принадлежит M'.
Пусть A - некоторое множество слов. Вычислительной машиной с
оракулом A называется вычислительная машина РАМ с дополнительной
командой TEST(A) a, которая проверяет за 1 шаг, принадлежит ли
содержимое ячейки a множеству A, помещая результат в виде
значения соответствующей характеристической функции в сумматор.
Аналог класса P, определенный с помощью такой машины
обозначается через P[A]. Если A принадлежит NP и NP=P[A], то A
называется NP-полным или полной переборной задачей. Пример
полной переборной задачи - множество выполнимых
пропозициональных формул. Полные переборные задачи также
образуют класс трудных задач.
Контрольный вопрос:
Какова временная сложность (простая и взвешенная)
и зонная (лог. взвеш., макс. сумма длин ячеек)
вычисления суммы входных чисел.
Лекция 13. On-line - вычисления, вычисления в реальное время
Определение, основные свойства и примеры on-line-вычислений и вычислений в реальное время.
Лекция 14. Автоматные вычисления. Регулярные множества
Определение и основные свойства конечных автоматов-распознавателей и конечных преобразователей. Автоматы Мили и Мура. Автоматные множества. Определение класса регулярных множеств.
Контрольный вопрос:
Написать on-line RAM для нахождения НОК чисел
Сложность (простое время)
Лекция 15. Регулярность автоматных и автоматность регулярных множеств
Теоремы об автоматности регулярных множеств и регулярности автоматных множеств
Дополнительный вопрос: Классы функций и предикатов, рудиментарные по Р.Смульяну
Лекция 16. Связь логики и вычислимости
Традиционные конструктивные логические теории
Пример: формальная конструктивная (интуиционистская) арифметика.
Вычислительная интерпретация логических формул.
Вычислительная интерпретация доказательств.
Лекция 17. Доказательства как программ
Извлечение программ из конструктивных доказательств. Интерпретация конструктивных доказательств как выполнимых программ.
Лекция 18. Нетрадиционные конструктивные теории
Конструктивные теории, предназначенные для построения программ ограниченной вычислительной сложности. Конструктивные теории, предназначенные для построения программ, работающих с расходуемыми и ограниченными ресурсами. Линейные логики.
- Программа лабораторных занятий
Занятие 1. Математическая логика и теория алгоритмов.
Построение алгоритмов следующих видов.
Машины Тьюринга: многоленточные, многоголовочные машины,
многомерные ленты, квазибесконечномерность лент*),
ленты с неевклидовой топологией, древовидные ленты,
эластичные ленты - К-алгоритмы.
Занятие 2. Виды алгоритмов
Построение алгоритмов следующих видов.
Алгоритмы Колмогорова-Успенского.
К-алгоритм - частный случай КУ-алгоритма.
Многомагазинный автомат.
Занятие 3. Магазинные автоматы. Нормальные алгоритмы. Регистровые машины
Построение магазинных автоматов, НА, РМ.
Занятие 4. Равнодоступные адресные машины (РАМ)
Построение РАМ.
РАМ с хранимой программой.
Занятие 5. Примитивно рекурсивные, частично рекурсивные и общерекурсивные функции
Построение ПРФ, ЧРФ и ОРФ.
Занятие 6. Примитивно рекурсивные предикаты, множества и отношения. Замкнутость этих классов относительно логических операций и навешивания ограниченных кванторов
Построение ПРП, ПРМ и ПРО. Операции над ними.
Занятие 7. Универсальный Нормальный Алгоритм Маркова на Упрощенном Рефале. Машины Джонса. Универсальная машина Джонса.
Построение моделей универсальных алгоритмов.
Занятие 8. Программа машины Джонса как структура данных
Построение структур программ машин Джонса.
Занятие 9. Разрешимые и неразрешимые множества.
Перечислимые и неперечислимые множества
Выделение примеров разрешимых, неразрешимых, перечислимых и неперечислимых иножеств.
Занятие 10. Элементарные по Кальмару функции
Построение примеров функций, множеств и отношений, элементарных по Кальиару.
Занятие 11. Классы, основанные на ограниченной рекурсии. Классы функций и предикатов ограниченной вычислительной сложности
Построение примеров функций, множеств и отношений, в классах, основанных на ограниченной рекурсии.
Построение примеров функций, множеств и отношений в классах ограниченной вычислительной сложности
Занятие 12. Методы оценки сложности вычислений и алгоритмов.
Доказуемо трудные задачи. Полные переборные задачи
Построение и выделение примеров доказуемо трудных и полных переборных задач.
Занятие 13. On-line - вычисления, вычисления в реальное время
Построение примеров on-line-алгоритмов и алгоритмов, работающих в реальное время.
Занятие 14. Автоматные вычисления. Регулярные множества
Построение примеров конечных автоматов-распознавателей и конечных преобразователей. Построение примеров регулярных множеств.
Занятие 15. Регулярность автоматных и автоматность регулярных множеств
Осуществление переходов между регулярными и автоматными определениями в конкретных случаях.
Занятие 16. Связь логики и вычислимости
Построение конструктивных логических выводов.
Занятие 17. Доказательства как программы
Осуществление извлечения программ из конструктивных доказательств в конкретных случаях.
- Программа самостоятельной работы студента
Самостоятельная работа выполняется в виде заданий к соответствующим лабораторным работам. Задания сдаются раз в 2 недели по следующим неделям:
Неделя 2. Математическая логика и теория алгоритмов. Виды алгоритмов
Неделя 4. Магазинные автоматы. Нормальные алгоритмы. Регистровые машины. Равнодоступные адресные машины (РАМ)
Неделя 6. Примитивно рекурсивные, частично рекурсивные и общерекурсивные функции. Примитивно рекурсивные предикаты, множества и отношения. Замкнутость этих классов относительно логических операций и навешивания ограниченных кванторов
Неделя 8 Универсальный Нормальный Алгоритм Маркова на Упрощенном Рефале. Машины Джонса. Универсальная машина Джонса. Программа машины Джонса как структура данных
Неделя 10. Разрешимые и неразрешимые множества. Перечислимые и неперечислимые множества. Элементарные по Кальмару функции
Неделя 12. Классы, основанные на ограниченной рекурсии. Классы функций и предикатов ограниченной вычислительной сложности. Методы оценки сложности вычислений и алгоритмов. Доказуемо трудные задачи. Полные переборные задачи
Неделя 14. On-line - вычисления, вычисления в реальное время. Автоматные вычисления. Регулярные множества
Неделя 16. Регулярность автоматных и автоматность регулярных множеств. Связь логики и вычислимости
Неделя 18. Нетрадиционные конструктивные теории
- Контролирующие материалы
Задания для лабораторных работ
1. Машина Тьюринга с одной одномерной двусторонней лентой и
одной головкой.
2. Машина Тьюринга с одной одномерной односторонней лентой и
одной головкой.
3. Машина Тьюринга с двумя двусторонними одномерными лентами по
одной головке на каждой ленте.
4. Машина Тьюринга с одной двумерной лентой.
5. Двухмагазинный автомат.
6. Нормальный алгоритм Маркова.
7. К-алгоритм.
8. Равнодоступная адресная машина.
9. Равнодоступная адресная машина с сохраняемой программой.
10. Машина Джонса.
11. Частично-рекурсивные функции.
12. Словарные рекурсивные функции.
13. Рекурсивные функции на бинарных деревьях.
14. Рекурсивные функции на термах.
15. Алгоритм Колмогорова-Успенского на бинарных
деревьях.
16. Алгоритм Колмогорова-Успенского на термах.
17. Регистровая (счетчиковая) машина.
18. Машина Тьюринга с лентой в виде бинарного дерева.
19. Двухголовочная машина Тьюринга с лентой в виде бинарного
дерева.
20. Машина Минского (счетчиковая машина).
Пример набора задач к экзамену
1. РАМ для нахождения максимума 100 входных чисел.
2. РАМ для нахождения минимума 400 входных чисел.
3. РАМ для нахождения максимума входных чисел, не превосходящих 200,
(всего дано 500 входных чисел) или выдать 300, если таких чисел нет.
4. РАМ для нахождения минимума входных чисел, не меньших 50,
(всего дано 150 входных чисел) или 0, если таких чисел нет.
5. РАМ для вычисления максимума попарных сумм из 120 входных чисел
(x[1],...,x[120]) x[i]+x[j], меньших 10 при i,j=1,...,120.
6. РАМ для вычисления миниимума попарных сумм из 80 входных чисел
(x[1],...,x[80]) x[i]+x[j], больших 20 при i,j=1,...,80.
7. РАМ для вычисления максимума попарных разностей 40 входных чисел.
8. РАМ для вычисления минимума попарных положительных разностей 60
входных чисел.
9. Машина Тьюринга, распознающая слова длины 3 в алфавите {0,1}
(101 -> 1, 10 -> 0, 1111 - > 0)
10. Машина Тьюринга, распознаюшие слова в алфавите {0,1}, имеющие
более 2-x единиц в своем составе (010 -> 0, 11 -> 0, 1011 -> 1).
11. РАМ для нахождения наименьшего из номеров наибольших чисел в заданной
последовательности из 10 чисел (2 2 3 4 5 7 6 7 4 3 -> 6).
12. РАМ для нахождения наибольшего из номеров наибольших чисел в заданной
последовательности из 10 чисел (2 2 3 4 5 7 6 7 4 3 -> 8).
13. РАМ для нахождения наименьшего из номеров наименьших чисел в заданной
последовательности из 10 чисел (3 2 2 3 4 5 7 6 7 4 -> 2).
4. РАМ для нахождения наибольшего из номеров наименьших чисел в заданной
последовательности из 10 чисел (2 2 3 4 5 7 6 7 4 3 -> 2).
15. Машина Тьюринга для уменьшения числа на 3 в монадической
("палочковой") системе счисления.
16. Машина Тьюринга для увеличения числа на 4 в монадической
("палочковой") системе счисления.
17. Машина Тьюринга для распознавания слова в алфавите {0,1},
состоящего из одних единиц.
18. Машина Тьюринга для распознавания словав алфавите {0,1},
состоящего из одних нулей.
19. РАМ для определения наименьшего положительного натурального
i, при котором x[i]=x[1] по входным числам x[1],...,x[80].
20. РАМ для определения наибольшего натурального i от 0 до 80,
при котором x[i]=x[1] по входным числам x[1],...,x[80].
21. РАМ для нахождения такого наименьшего i, что
x[i]=max{x[1],...,x[70],70} или i=71 по x[1],...,x[70].
22. РАМ для нахождения такого наибольшего i, что
x[i]=min{76,x[1],...,x[75]} или i=0 по x[1],...,x[75].
23. РАМ для вычисления такого наименьшего i (от 1 до 101), что
x[i]=0 или i=101 по входным числам x[1],...,x[100].
24. РАМ для вычисления такого наибольшего i (от 0 до 100), что
x[i]=0 или i=0 по входным числам x[1],...,x[100].
- Экзаменационные вопросы
1. Конструктивные логические теории.
2. Вычислительная интерпретация логических формул.
3. Вычислительная интерпретация доказательств.
4. Машины Тьюринга и другие модели вычислений.
5. Машины Джонса.
6. Равнодоступные адресные машины.
7. РАМ с хранимой программой.
8. Примитивно рекурсивные функции.
9. Частично-рекурсивные и общерекурсивные функции.
10. Тезисы Черча, Тьюринга, Маркова.
11. Эквивалентность разных моделей вычислимости.
12. Универсальные алгоритмы.
13. Рекурсивно разрешимые множества, неразрешимые множества.
14. Примитивно рекурсивные множества, отношения, предикаты.
15. Перечислимые множества и неперечислимые множества.
16. Элементарные функции, множества, отношения, предикаты.
17. Классы функция, основанных на ограниченной рекурсии.
18. Классы Гжегорчика и их аналоги.
19. Классы словарных функций.
20. Определение словарных функций с помощью словарной
ограниченной рекурсии.
21. Конечная сложность вычислений (сложность вычислений на
конечных равнодоступных адресных машинах).
22. Алгоритмическая (описательная, дескриптивная) сложность.
23. Алгоритмическое определение случайности.
- Список литературы (основная, дополнительная)
Основная литература
1. А.А.Марков Теория алгорифмов М.Л. Изд-во АН СССР, 1954,
374с., 1984, 432 с.
2. А.Ахо, Дж.Хопкрофт, Дж.Ульман. Построение и анализ
вычислительных алгоритмов. М. Мир, 1979. 536 с.
3. Проблемы математической логики (сб.). Под ред. Козмидиади и
др. М. Мир 1970, 432 с.
4. Э.Мендельсон. Введение в математическую логику. (Гл. 5.) M.
1971, 1976, 1984. 320 с.
5. С.К.Клини. Математическая логика. (Гл. V). М. Мир, 1973.
480с.
6. Ю.Л.Ершов, Е.А.Палютин. Математическая логика. (Гл. 7). М.
"Наука" 1971. 320 с.
7. Р.Смальян. Теория формальных систем. (Гл. I, II.) М. Наука,
1981, 207 с.
8. Дж.Шенфилд. Математическая логика. (Гл. 6-7.) М. Наука, 1975.
527 с.
9. С.К.Клини. Введение в метаматематику. М "Иностраниздат",
1957, 526 с.
10. Н.Верещагин, А.Шень. Лекции по математической логике и
теории алгоритмов. Ч 3. Вычислимые функции. M. МЦНМО 1999.
126с.
11. К.А.Гоуд. Доказательства как описания вычислений. В кн.
"Математическая логика в программировании". Под ред.
М.В.Захарьящева и Ю.И.Янова. М. 1991. С. 311-330. (407 с.)
12. А.И.Мальцев Алгоритмы и рекурсивные функции. М Наука 1986.
357с.
13. В.Г.Карпов, В.А.Мощенский Математическая логика и дискретная
математика, Минск "Высшая школа", 1977. 254 с.
14. А.Н.Колмогоров, Драгалин Математическая логика,
дополнительные главы, М МГУ, 1984. 120 с.
15. А.Н.Колмогоров, Драгалин Введение в математическую логику,
М. МГУ. 1982.
16. Н.К.Косовский Основы теории элементарных алгоритмов, Л. ЛГУ,
1987. 132 с.
17. С.Л.Эдельман Математическая логика, М. Высшая школа. 1975.
176с.
18. Дж.Булос,Р.Джефри. Вычислимость и логика, М. Мир. 1994.
396с.
Дополнительная литература
1. Математическая логика. Под ред. А.А.Столяра. Гл. А.4, Б.3. М.
1971.
2. Б.А.Трахтенброт. Алгоритмы и вычислительные автоматы. М.1974.
3. В.А.Успенский, А.Л.Семенов Теория Алгоритмов: основные
открытия и приложения. М., "Н", 1987.
4. Г.Д.Эббинхауз, К.Якобс, Ф.-К.Ман, Г.Хермес Машины Тьюринга и
рекурсивные функции. М.1972
5. Х.Роджерс Теория рекурсивных функций и эффективная
вычислимость, М.1972
6. В.К.Иложарский Математическая логика и алгоритмы, 1970
Приложение 1
Основное оборудование по дисциплине
Перечень основного оборудования в соответствии с ГОС
по дисциплине «Теория алгоритмов и сложности»
специальности «Прикладная информатика (по областям)»
Формы обучения «дневная»
2009/2010 год
-
№ п/п
Наименование оборудования
Кол-во
Примечание (сведения о наличии, необходимости обновления, приобретения)
1
Компьютерный проектор
1
Наличествует 1