Название работы	Кол-во страниц	Размер
Жизнь и деятельность василий III иванович василий III как человек	1	151.38kb.
Диплом II ст. «Капель» диплом III ст. «Анастасия диплом III ст.	1	21.88kb.
Программа курса Макроэкономика (4 семестр)	1	34.92kb.
Самостоятельная работа: 120 час. Итоговый контроль: 8 семестр зачет...	1	110.66kb.
Iii ефремовские чтения в школе №41 Н. С. Левшина, газета храма муч.	1	52.03kb.
Курс "Основы построения трансляторов"	2	731.23kb.
Ленин В. И. III, Коммунистический Интернационал	1	16.79kb.
Учебник для 7 класса основной школы Раздаточный материал (документы...	1	81.45kb.
Четверть 27 уроков, III четверть 30 уроков, IV четверть 25 уроков...	1	71.65kb.
Семинар "экобионика" осенний семестр 20 12	1	17kb.
Вопросы к экзамену по математическому анализу (2й семестр)	1	22.55kb.
Программа по курсу: сравнительный анализ языков программирования...	1	122.74kb.
Викторина для любознательных: «Занимательная биология»	1	9.92kb.

Вопросы по математической логике

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

(АВТФ, III семестр)

1. Формальные исчисления. Вывод в исчислении. Теорема исчисления. Разрешимые и непротиворечивые исчисления.

2. Исчисление высказываний (ИВ): формулы, аксиомы и правила вывода. Понятие доказательства, дерево доказательства.

3. Основные эквивалентности ИВ. Теорема о замене. Дизъюнктивная и конъюнктивная нормальные формы.

4. Семантика исчисления высказываний. Непротиворечивость ИВ. Таблицы истинности. Общезначимые и выполнимые формулы. Теорема о полноте. Разрешимость ИВ.

5. Семантическое дерево. Алгоритм Квайна и алгоритм редукции проверки общезначимости формул.

6. Метод резолюций в ИВ. Метод согласия. Метод резолюций для хорновских дизъюнктов.
7. Формулы сигнатуры S. Подформулы. Свободные и связанные переменные. Предложения. Истинность формулы на элементах алгебраической системы.

8. Общезначимые и выполнимые формулы. Теорема об общезначимости формул сигнатуры S, соответствующих общезначимым формулам ИВ. Выполнимое множество формул. Теорема компактности.

9. Исчисление предикатов сигнатуры S (): аксиомы и правила вывода, доказуемые формулы. Тождественно истинные формулы. Теорема о непротиворечивости .

10. Основные эквивалентности . Теорема о замене. Пренексные и клазуальные нормальные формы.

11. Теорема о существовании модели. Теорема Гёделя о полноте. Теорема Мальцева о компактности.

12. Скулемизация алгебраических систем.

13. Подстановка сигнатуры S. Композиция подстановок. Унификатор и наиболее общий унификатор. Алгоритм унификации. Теорема об алгоритме унификации.

14. Бинарная резольвента и резольвента дизъюнктов сигнатуры S. Резолютивный вывод. Полнота метода резолюций.

15. Проверка непротиворечивости множества предложений методом резолюций и построение моделей. Формализация свойств и их доказательство с помощью метода резолюций.

16. Принцип логического программирования. Логические программы.

17. Элементарные теории. Система аксиом теории. Полные теории.

18. Типы. Основные классы моделей.

18. k-Категоричные теории. Теорема о полноте k-категоричной теории. w-Категоричность теории плотного линейного порядка. Спектры моделей полных теорий.

19. Система аксиом арифметики Пеано. Нестандартные модели арифметики. Теорема Дедекинда-Пеано.

20. Понятие алгоритма, основные признаки алгоритма. Вычислимые функции и тезис Чёрча.

21. Определение машины Тьюринга.

22. Основные машины Тьюринга. Операции над машинами Тьюринга.

23. Вычисление функций на машинах Тьюринга.

24. Понятие примитивно рекурсивной функции, основные примеры.

25. Примитивно рекурсивные отношения, основные преобразования над ними, примеры примитивно рекурсивных отношений.

26. Нумерации n-ок натуральных чисел примитивно рекурсивными функциями.

27. Частично рекурсивные и рекурсивные функции. Теорема об элиминации примитивной рекурсии.

28. Вычислимость частично рекурсивных функций на машинах Тьюринга.

29. Частичная рекурсивность функций, вычислимых на машинах Тьюринга.

30. Универсальные ЧРФ. Теорема об универсальности. Теорема о существовании ЧРФ, не доопределимой до рекурсивной функции. Теорема Райса.

31. Гёделевская нумерация формул, аксиом и правил вывода исчисления предикатов. Рекурсивно перечислимые множества. Разрешимые и неразрешимые теории. Теорема Гёделя о неполноте арифметики. Теорема Чёрча о неразрешимости исчисления предикатов.

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

33. Класс эффективно вычислимых функций. Метод сводимости.

34. Понятие переборной задачи. Универсальные переборные задачи, примеры.

35. Основные алгоритмы сортировки и их сложность.

36. Детерминированные и недетерминированные конечные автоматы, связь между ними.
37. Пропозициональные неклассические логики.

38. Предикатные неклассические логики.

39. Предикатные временне логики и их приложение к программированию.

40. Алгоритмические логики.

Литература: Судоплатов С.В., Овчинникова Е.В. Математическая логика и теория алгоритмов: Учебник. – М.: ИНФРА-М, Новосибирск, Изд-во НГТУ, 2004. – 224 с.