- •1Язык логики высказываний. Простые высказывания, сложные высказывания, логические связки. Роль связок в естественном языке.
- •2Синтаксис языка логики высказываний: алфавит и правила построения формул. Семантика языка логики высказываний, интерпретация формул.
- •3Свойства формул: общезначимость, выполнимость, противоречивость, опровержимость.
- •4Основные схемы логически правильных рассуждений.
- •5Основные тавтологии, выражающие свойства логических операций.
- •12Алгебра логики. Функции алгебры логики. K-значные логики.
- •18Булева алгебра логических операций. Основные эквивалентные соотношения (законы) в булевой алгебре.
- •19Разложение функций по переменным. Совершенная дизъюнктивная нормальная форма.
- •27Понятие логического следования, принцип дедукции. Правило резолюций, метод резолюций. Стратегии метода резолюций.
- •26Теорема дедукции. Связь выводимости и истинности формул в логике высказываний. Выполнимые и общезначимые формулы.
- •29Алгоритм построения резолюций для множества фраз Хорна.
- •30Свойства формализованного счисления высказываний.
- •32Синтаксис языка логики предикатов: алфавит, термы, атомы, правила построения формул.
- •33Кванторные операции. Свободные и связанные вхождения переменных. Логический квадрат.
- •34Численные кванторы. Ограниченные кванторы.
- •35Множество истинности предикатов. Равносильность и следование предикатов.
- •49Принцип полной дизъюнкции в предикатной форме
- •50Метод (полной) математической индукции
- •54. Основные свойства формальных систем: непротиворечивость, полнота, разрешимость. Полнота и непротиворечивость исчисления высказываний. Полнота и непротиворечивость исчисления предикатов.
- •Предпосылки возникновения теории алгоритмов. Основные требования к алгоритмам. Подходы к уточнению понятия «алгоритм». Три основных типа универсальных алгоритмических моделей.
- •Машина Тьюринга. Конфигурация машины Тьюринга. Функция, правильно вычислимая по Тьюрингу. Эквивалентные машины Тьюринга. Композиция машин Тьюринга.
- •70Машина Поста.
- •Операторы подстановки и примитивной рекурсии определяются следующим образом:
- •72Нормальные алгорифмы Маркова. Нормально вычислимые функции и принцип нормализации Маркова.
- •76Сложность алгоритмов. Меры сложности алгоритмов. Сложность задачи. Массовые и индивидуальные задачи.
- •77Асимптотическая сложность, порядок сложности. Сложность в среднем и в худшем случае.
- •3) Метод прямого определения среднего времени
- •80Сложность и кодирование. Сложность и архитектура машины.
- •81Полиномиальный алгоритм. Легко- и трудноразрешимые задачи, классы задач p и np.
- •82Полиномиальная сводимость и np-полнота. Np-полные задачи. Примеры np-полных задач. Теорема Кука. Примеры практически значимых np-полных задач.
82Полиномиальная сводимость и np-полнота. Np-полные задачи. Примеры np-полных задач. Теорема Кука. Примеры практически значимых np-полных задач.
Алгоритмическая задача P1 полиномиально сводится к задаче Р2, если существует полиномиальный алгоритм для решения задача Р1, возможно, вызывающий в ходе своей работы процедуру для решения задачи Р2.
Задача разрешения называется NP-полной, если она принадлежит к классу NP и произвольная задача из NP сводится к ней полиномиально.
Если мы имеем задачу 1 и решающий эту задачу алгоритм, выдающий правильный ответ для всех конкретных проблем, составляющих задачу, а для задачи 2 алгоритм решения неизвестен, то если мы можем переформулировать (свести) задачу 2 в терминах задачи 1, то мы решаем задачу 2.
Таким образом, если задача 1 задана множеством конкретных проблем DA1, а задача 2 – множеством DA2, и существует функция fs (алгоритм), сводящая конкретную постановку задачи 2 (dА2) к конкретной постановке задачи 1 (dА1): fs(d(2)ÎDA2) = d(1)ÎDA1, то задача 2 сводима к задаче 1.
Если при этом FA (fs) = O(nk), т.е. алгоритм сведения принадлежит классу P, то говорят, что задача 1 полиномиально сводится к задаче 2.
Теорема Кука утверждает, что задача о выполнимости булевой формулы в КНФ является NP-полной.
Примеры NP-полных задач:
3-выполнимость — выполнимость для КНФ, к которой каждая дизъюнкция содержит ровно 3 литерала (литерал — это либо переменная, либо переменная с отрицанием).
Вершинное покрытие — имеется ли в графе G(V, E) вершинное покрытие не более чем из k элементов, т. е. такое V¢ Í V, что |V¢| < k и хотя бы один конец любого ребра принадлежит V¢?
Гамильтонов цикл.
k-раскрашиваемостъ — можно ли раскрасить граф G(V, E) в k цветов, где k <|V|?
Изоморфизм подграфу — изоморфен ли граф G1 какому-нибудь подграфу графа G2?