Рабочая программа дисциплины "Теория алгоритмов" для подготовки специалиста по специальности 030100 "Информатика" с дополнительной cпециальностью 032100 "Математика"

ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ

РАБОЧАЯ ПРОГРАММА

дисциплины "Теория алгоритмов"

для подготовки специалиста по специальности 030100 "Информатика"

с дополнительной cпециальностью 032100 "Математика"

Всего: 90 час

52 час - ауд

Из них: 26 – лекции

26 – семинары

38 СРС

Форма отчетности – экзамен, 8 сем.

по уч. плану 2000-2001 уч. г.

Составитель: доц.

Программа утверждена на заседании

кафедры информатики и МПМ 10 мая

2001 г. протокол № 9

Заведующий кафедрой, профессор

______________________

Воронеж – 2001

1. ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

Дисциплина "Теория алгоритмов" рассматривает основополагающие вопросы теоретической информатики.

Подробно рассматриваются понятие алгоритма, свойства и классификация алгоритмов, способы их формального описания и исполнения. Основные черты алгоритмических процессов. Определение конечных автоматов. Их графическое изображение. Языки, распознаваемые конечными автоматами. Эквивалентность конечных автоматов и недетерминированных конечных автоматов. Определение и примеры формальных грамматик. Контекстно–свободные и регулярные грамматики. Определение машин Шенфилда и функций, вычислимых на ней. Макросы. Тезис Черча. Теорема о параметризации (s-m-n-теорема). Машины Тьюринга. Определение. Простейшие машины Тьюринга. Операции на машинах Тьюринга и их свойства.

2. ТЕМАТИЧЕСКИЙ ПЛАН

№	Наименование разделов и тем	Всего часов	Всего	Лекций	Лабор.	СРС
1.	Множества, их основные свойства и операции над ними. Понятие вычислимой функции. Разрешимые и перечислимые множества. График вычислимой функции. Формальная теория вычислимости.	34	24	12	12	10
2.	Общее понятие исчисления	16	8	4	4	8
3.	Формальные грамматики. Контекстно–свободные и регулярные грамматики.	16	8	4	4	8
4.	Основы теории NР - полноты	24	12	6	6	12

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

1.  Множества, их основные свойства и операции над ними. Некоторые основные понятия в теории множеств.

2.  Алфавиты и языки, длина слова, конкатенация слов, степени с натуральным показателем, звездочка Клини.

3.  Конечные автоматы и их основные свойства. Основные черты алгоритмических процессов. Определение конечных автоматов. Их графическое изображение.

4.  Языки, распознаваемые конечными автоматами. Эквивалентность конечных автоматов и недетерминированных конечных автоматов. Замкнутость языков, распознаваемых конечными автоматами, относительно объединения, пересечения, дополнения, конкатенации и звездочки Клини.

5.  Определение и примеры формальных грамматик. Контекстно–свободные и регулярные грамматики.

6.  Совпадение класса регулярных языков и языков, распознаваемых конечными автоматами. Алгоритмическая разрешимость множества слов контекстно–свободных языков.

7.  Замкнутость регулярных языков относительно объединения, пересечения, дополнения, конкатенации и звездочки Клини.

8.  Определение машин Шенфилда и функций, вычислимых на ней. Макросы.

9.  Теорема об элиминации макросов. Определение частично рекурсивных функций. Простейшие функции. Операторы суперпозиции, примитивной рекурсии, минимизации. Общерекурсивные функции. Примеры вычислимых функций. Вычислимые (рекурсивные предикаты).

10.  Кодирование последовательностей. Теорема о совпадении классов функций, вычислимых на машинах Шенфилда и класса частично рекурсивных функций. Тезис Черча. Теорема о параметризации (s-m-n-теорема). Теорема Клини о нормальной форме. Универсальные вычислимые функции.

11.  Машины Тьюринга. Определение. Простейшие машины Тьюринга. Операции на машинах Тьюринга и их свойства. Нормальные алгоритмы Маркова. Определение. Примеры.

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

13.  Понятие абстрактной сложности. Общее свойство функций сложности вычислений. Теорема Блюм об ускорении.

4. РЕКОМЕНДАЦИИ ПО ОРГАНИЗАЦИИ РАБОТЫ СТУДЕНТОВ.

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

5. ЛИТЕРАТУРА

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

  1.  М. Брой. Информатика. В 4 частях. М. Диалог МИМИ. 1998

  2.  Ф. Бауэр, Г. Гооз. Информатика. М. Мир, 1976.

  3.  Н. Катленд. Вычислимость.

  4.  . Алгоритмы и рекурсивные функции.

  5.  Х. Роджерс. Теория рекурсивных функций и эффективная вычислимость.

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

  1.  Р. Соар. Вычислимо перечислимые множества и степени.

  2.  , Палютин логика. М.: Наука, 1987.

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

6. РЕКОМЕНДАЦИИ ДЛЯ СРС

На самостоятельную работу выносятся следующие вопросы:

1. Теоретико-множественные упражнения (1).
2. Конечные автоматы (1).
3. Формальные грамматики (1)
4. Построение простейших алгоритмов для машин Шенфилда (1).
5. Частично рекурсивные функции (1).
6. Машины Тьюринга (2).
7. Нормальные алгоритмы Маркова (1).
8. Дальнейшие вопросы теории вычислимости (1).

7. ВОПРОСЫ К ЭКЗАМЕНУ

1. Понятие рекурсивной (вычислимой) функции. Машина с неограниченными регистрами, формализация Клини.

2. Канторовская нумерационная функция, ее значение. Нумерация пар, n-ок и конечных последовательностей натуральных чисел. Нумерация машин с неограниченными регистрами.

3. Нумерация машин с неограниченными регистрами. Универсальная машина и универсальная функция.

4. s-m-n-теорема и ее следствия.

5. Неразрешимость проблемы остановки. Другие неразрешимые проблемы.

6. Рекурсивные и рекурсивно перечислимые множества, их простейшие свойства. Теорема Поста о рекурсивно перечислимых множествах.

7. Основная теорема о рекурсивно перечислимых множествах.

8. Теорема о проекции. Теорема о графике рекурсивной функции.

9. Рекурсивно перечислимые и рекурсивные индексы множеств. Кано - нические индексы конечных множеств. Переходы от одних типов индексов к другим.

10. Теорема о неподвижной точке и ее следствия. Теорема об отсутствии алгоритма, оптимизирующего любую машину.

11. 1- и m-сводимости и степени, их простейшие свойства. 1- и m-полные множества. Устройство рекурсивных 1- и m- степеней.

12. Машины с оракулом. Принцип релятивизации.

13. Сводимость по Тьюрингу и Тьюринговы степени, их простейшие свойства. Операция скачка.

14. Арифметическая иерархия. Представление арифметических отношений в виде предикатной формы от рекурсивных.

15. Арифметическая иерархия. Теорема о нормальной форме.

16. Теорема Поста об арифметической иерархии.