Теория алгоритмов

Понятие вычислимой функции. Разрешимые и перечислимые множества. График вычислимой функции. Формальная теория вычислимости (частично рекурсивные функции, регистровые машины, машины Тьюринга). Тезис Чёрча. Конечные и бесконечные машины. Понятие программы. Эффективная нумерация программ. Теорема о параметризации. Существование универсальной программы. Компьютер фон Неймана. Диагональный метод. Пример невычислимой функции. Проблема останова. Примеры неразрешимых и неперечислимых множеств. Алгоритмическая сводимость проблем. Примеры алгоритмически неразрешимых проблем в математике и информатике. Эффективные операции над вычислимыми функциями. Теорема о неподвижной точке. Общее понятие исчисления. Грамматики. Языки, иерархия языков по Хомскому. Языки и машины. Основные меры сложности вычисления. Основы теории NР-полноты. Применение теории NР-полноты для анализа сложности проблем. Приложения теории алгоритмов в информатике.

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

1. Ахо А., Хопкрофт Дж., Ульман Д. Структуры данных и алгоритмы – М.: Издательский дом «Вильямс», 2001.

2. Верещагин Н. К., Шень А. Вычислимые функции – М.: МЦНМО, 2002.

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

4. Зюзьков В. М., Шелупанов А. А. Математическая логика и теория алгоритмов: учеб. пособие для вузов – М.: Горячая линия - Телеком, 2007.

5. Игошин В. И. Задачи и упражнения по математической логике и теории алгоритмов – М.: Издательский центр «Академия», 2006.

6. Игошин В. И. Математическая логика и теория алгоритмов – М.: Издательский центр «Академия», 2004.

7. Информатика: учеб. пособие для студ. пед. вузов / под ред. Е.К.Хеннера. – М.: Издательский центр «Академия», 1999.

8. Кнут Д. Искусство программирования. В 3 т. 3-е изд.– М.: Издательский дом «Вильямс», 2000.

9. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. 2-е изд.– М.: Издательский дом «Вильямс», 2005.

10. Лавров И. А., Максимова Л. А. Задачи по теории множеств, математической логике и теории алгоритмов – М.: ФИЗМАТЛИТ, 2004.

11. Стариченко Б. Е. Теоретические основы информатики: учеб. пособие для вузов. 2-е изд., перераб. и доп.– М.: Горячая линия – Телеком, 2003.

12. Сэвидж Джон Э. Сложность вычислений – М.: Факториал, 1998.

13. Фалевич Б.Я. Теория алгоритмов: учеб. пособие – М.: Машиностроение, 2004.

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

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

2. Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике – М.: Мир, 1977.

3. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи – М.: Мир, 1982.

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

5. Матросов В. Л. Теория алгоритмов – М.: Прометей, 1989.

6. Успенский В. А. Машина Поста – М.: Наука, 1988.

7. Успенский В. А., Семенов А. Л. Теория алгоритмов: основные открытия и приложения – М.: Наука,1987.

Примерные вопросы

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

2. Уточнение понятия вычислимой функции в рамках теории рекурсивных функций. Примитивно рекурсивные функции. Частично рекурсивные функции. Тезис Черча. Рекурсивные множества и предикаты. Рекурсивно перечислимые множества.