ГЛАВА 2. ТЕОРИЯ АЛГОРИТМОВ (8 часов).

2.1. Понятие алгоритма и неформальной вычислимости: определения и основные особенности алгоритма.

2.2. Подход Геделя-Клини к формализации понятия алгоритма: Частично-рекурсивные функции (ЧРФ): операторы суперпозиции, примитивной рекурсии, минимизации для построения ЧРФ.

2.3. Примеры рекурсивности (примитивно-рекурсивных и общерекурсивных функций)

2.4. Подход А. Черча: Ламбда-исчисление. Его особенности. выражения и их вычисления.

2.5. Определение термов и выражений. редекс и редекс. Процесс редукции. Примеры редукций.

2.6. Нормальные формы выражений и порядок редукций: аппликативный (АПР- стратегия энергичных вычислений) и нормальный (НПР- стратегия ленивых вычислений) порядок редукций. Следствие из теоремы Черча-Россера.

2.7. Рекурсивные функции. Комбинатор неподвижной точки.

2.8. Чистое исчисление.

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

2.10. Другие подходы к определению понятия алгоритма. Тезис Черча.

2.11. Алгоритмически неразрешимые проблемы.

2.12. Сложность алгоритмов: в наихудшем случае и поведения в среднем. Сложность задачи.

2.13. Классификация задач по сложности: класс Р и класс Е.

2.14. Класс NP. NP-трудные и NP-полные задачи. Теорема Кука.

 

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

Мендельсон Э. Введение в математическую логику. – М.: Наука, 1984.

Шелупанов А.А., Зюзьков В.М. Математическая логика и теория алгоритмов. – Томск: STT, 2001. – 176 с.

Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001. – 304 с.: ил.

Гетманова А.Д. Учебник по логике. 2-ое изд. – М.: Владос, 1995. – 303 с.

Никифоров А. Книга о логике. – М.: Гнозис, 1996.

Манин Ю.И. Доказуемое и недоказуемое. – М.: Советское радио, 1979.

Манин Ю.И. Вычислимое и невычислимое. – М.: Советское радио, 1980. -128 с.

Кац М., Улам С. Математика и логика. Ретроспектива и перспективы: Пер. с англ. – М.: Мир, 1971. – 254 с.

Судоплатов С.В. и др. Математическая логика и теория алгоритмов. –М.: изд. Дом «ИНФРА», 2004.-224 с.

Судоплатов Дискретная математика

Справочная книга по математической логике: В 4-х частях/Под ред. Дж. Барвайса. Ч.III. Теория рекурсии: Пер. с англ. – М.: Наука, 1982. – 360 с.

Успенский В.А. Теорема Геделя о неполноте. – М.: Наука, 1982. – 112 с.

Филд А., Харрисон П. Функциональное программирование. – М.: Мир, 1993. – 637 с.

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

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

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

Барендрегт Х. Ламбда-исчисление. Его синтаксис и семантика. – М.: Мир, 1985. – 606 с.

Шевелев Ю.П. Высшая математика 6. Дискретная математика. Ч.2: Теория конечных автоматов. Комбинаторика. Теория графов (для автоматизированной технологии обучения): Учебное пособие. – Томск: Томск. гос. ун-т систем управления и радиоэлектроники, 1999. – 120 с.

Яблонский С.В. Введение в дискретную математику: Учеб. пособие для вузов./Под ред. В.А. Садовничего. – 3-е изд., стер. – М.: Высшая школа; 2001. – 384 с.

Дискретная математика и математические вопросы кибернетики. Т 1./Под общей редакцией С.В. Яблонского и О.Б. Лупанова, М.: Наука, 1974. – 311 с.

Кнут Д. Искусство программирования для ЭВМ, т.т. 1,2. – М.: Мир, 1977.

Глушков В.М. Синтез цифровых автоматов. – М.: Физматгиз, 1962. – 476 с.

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

1. Носов В.А. Специальные главы дискретной математики: Учебное пособие. М.: Наука, 1990.

2. Айзерман М.А. и др. Логика. Автоматы. Алгоритмы. – М.: Физматгиз, 1963. – 556 с.

3. Флорин Ж. Синтез логических устройств и его автоматизация. – М.: Мир, 1966. – 375 с.