Мат. логика и теория алгоритмов. 2002/03 уч.г., экз.

1. Предмет мат. логики: исчисление высказываний и предикатов, лямбда-
исчисление.  Функции: детерминированные или правильно определенные; 
полные и частичные. Формальные и фактические параметры, применение 
функции. Композиция функций и примитивы. Функциональность (прозрач-
ность по ссылкам) и побочные эффекты.  
2. Базовые элементы языка Лисп. S-выражения: атомы, точечные пары.  
Списки, функции.  
3.  Атомы, их свойства и значение. Функции CAR, CDR, CONS, APPEND.
4.  Предикаты и функция COND.  
5. Рекурсивные функции. Примеры: m ^n, подсчет количества атомов в 
списке.  
6. Функции удаления элемента из списка, определения вхождения в спи-
сок, обращения списка (Revlist, Reverse).  
7.  Определение лямбда-функции. Примеры одно-  и двухаргументных и 
вложенных лямбда-функций.  
8. Замена всех вхождений элементов списка Y в списке U на соответ- 
ствующие элементы списка Х (subst, substll).  
9. Ассоциативные списки (ф. pair  и  assoc). Замена всех вхождений 
Y в U на Х с применением ассоциативного списка.  
10. Применение ассоциативного списка при вычислении чисел Фибоначчи.  
11. Генерация перестановок 1 (ф. permlist).  
12. Генерация перестановок 2 (две последовательные перестановки от- 
личаются транспозицией только двух соседних элементов).  
13. Функции в качестве аргументов (на примере генерации перестано- 
вок 2).  
14. Функции  mapcar  и  mapcan. Упрощение генератора перестановок 1 
путем использования встроенных функций.  
15. Графы - определения и способы представления. Алгоритм нахожде- 
ния соседей для графа в виде списка ребер.  
16. Алгоритмы нахождения соседей для графа в виде матрицы смежно- 
стей и в виде ассоциативного списка.  
17. Поиск на графах. Алгоритм поиска в глубину.  
18. Поиск на графах. Алгоритм поиска в ширину.  
19. Построение компонент связности графа.  
20. Построение остовного дерева графа.  
21. Решение задач из области искусственного интеллекта на основе
модели пространства состояний для конкретной предметной области.
22. Алгоритм поиска решения в ширину со списковым представлением
множества кандидатов.
23. Необходимость уточнения понятия алгоритма.
24. Машина Тьюринга(МТ): алфавиты, структура, работа, применимость.
25. МТ для перехода от N к N+1 в десятичной системе и перевода
десятичной записи в унарную.
26. МТ для сложения и умножения.
27. МТ для вычисления НОД двух натуральных чисел.
28. Библиотека тьюринговых программ и последовательная композиция
МТ.
29. Теоремы о параллельной композиции и разветвлении алгоритмов.
30. Теорема о повторном применении алгоритма. Универсальная МТ.
31. Основная гипотеза теории алгоритмов. Алгоритмичеcки неразре-
шимые проблемы. Теорема Черча. Распознавание применимости и само-
применимости.
32. Метод сводимости, распознавание переводимости.
33. Проблема распознавания эквивалентности слов.
34. Рекурсивные функции и функции, вычислимые по Тьюрингу. Опера-
торы введения фиктивных переменных, суперпозиции, итерации.
35. Рекурсивные функции и функции, вычислимые по Тьюрингу. Прими-
тивная рекурсия.