Читайте также:
|
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 с.
Дата добавления: 2015-04-11; просмотров: 32 | Поможем написать вашу работу | Нарушение авторских прав |