1. Интуитивное понятие алгоритма и его основные характеристики
| Вид материала | Документы |
- Урок Тема: Понятие алгоритма. Исполнитель алгоритма, 204.38kb.
- Д. С. Осипенко Понятие алгоритма. Примеры алгоритмов. Свойства алгоритмов. Способы, 96.46kb.
- Реферат по теме Понятие алгоритма, его свойства. Описание алгоритмов с помощью блок, 102.16kb.
- Термины и терминологические сочетания: основные характеристики, 619.93kb.
- Экзаменационные вопросы на гак для магистрантов по программе «Экономика труда», 43.28kb.
- Контрольные вопросы по курсу лекций : Мировой океан основные характеристики Переходные, 43.87kb.
- Теоретические вопросы, 25.48kb.
- Краткий курс лекций лекция Сущность налога и его основные характеристики, 1192.46kb.
- Понятие алгоритма и вычислимой функции. Частично рекурсивные функции. Тезис Черча., 17.86kb.
- Задача обучения алгоритмизации заключается в том, чтобы научить составлять записи алгоритмов,, 78.61kb.
Вопросов к экзамену по математической логике для студентов групп ВИ-1-02, ВИ-2-02 (7 семестр)
1.Интуитивное понятие алгоритма и его основные характеристики.
2.Определение рекурсивных и частично рекурсивных функций. Соотношение между классами примитивно рекурсивных, общерекурсивных и частично рекурсивных функций.
3.Примеры алгоритмически неразрешимых массовых задач. Примеры алгоритмически разрешимых и неразрешимых задач из алгебры и др. разделов математики.
4.Понятие нормального алгоритма Маркова. Примеры. Композиция нормальных алгоритмов. Нормальные алгоритмы для реализации элементарных рекурсивных функций.
5.Определение машины Тьюринга. Понятие универсальной машины . Определение машины Поста. Представление машиной Тьюринга машины Поста, представление машиной Поста машины Тьюринга. Принцип Тьюринга-Поста.
6. Вычисление на машине Тьюринга элементарных рекурсивных функций.
7. Алгебра высказываний и алгебра предикатов.
8. Основные логические операции и их свойства. Понятие булевой алгебры.
9.Алгебра высказываний и алгебра подмножеств как примеры булевых алгебр.
10. Предикаты на множестве и их связь с отношениями. Логические операции над предикатами. Определение формулы алгебры предикатов. Выполнимые, тождественно истинные и тождественно ложные формулы.
11.Равносильность формул, основные соотношения равносильности и их использование для упрощения формул.
12. Существование для каждой формулы алгебры высказываний приведенной формы, дизъюнктивной и конъюнктивной нормальных форм.
13.Понятие булевых функций и функций многозначной логики. Их представление формулами над заданной системой функций. Представление булевых функций формулами алгебры высказываний и многочленами Жигалкина.
14. Замкнутые классы функций. Критерии полноты для булевых функций и функций многозначной логики. Псевдобулевы функции и их задание. Минимизация булевых функций.
15.Общее понятие о логическом исчислении. Язык, аксиомы и правила вывода исчислений высказываний. Теорема дедукции. Непротиворечивость и полнота исчисления высказываний.
16. Язык, аксиомы и правила вывода исчисления предикатов. Выводимость и доказуемость формул в исчислении предикатов. Вспомогательные правила вывода: правило силлогизма, правила умножения и разделения формул, правило умножения и разделения посылок, правило умножения заключений, правило перестановки посылок, правило контрапозиции, правила де Моргана, правила противоречия, закон исключения третьего.
17. Теорема дедукции для замкнутой формулы.. Эквивалентность формул. Приведение формул к нормальным формам. Понятие об интерпретации исчисления предикатов..
18. Непротиворечивость исчисления предикатов. Непротиворечивые, полные и выполнимые системы формул. Теорема Черча о неразрешимости исчислений предикатов.
19. Подходы к оценкам сложности алгоритмов и вычислений. Модели вычислений. Сложность вычислений на машине Тьюринга. Свойства функций сложности. Нижние оценки.
20. Сложность распознавания симметрии слов. Сложность распознавания функциональной полноты системы булевых функций.
(базовый учебник: Капитонова и…. Лекции по дискретной математике. М.2003)