Курс лекций для студентов специальности I-31 03 04 «Информатика»
всех форм обучения. Минск: БГУИР, 2006, -103с.
Содержание
Основы теории алгоритмов
Неформальное определение алгоритма и необходимость его уточнения
Арифметические и интуитивно вычислимые функции
Машины Тьюринга
Вычислимость по Тьюрингу
Машины Шёнфилда
Частично вычислимые функции
Кодирование алгоритмов
Алгоритмически неразрешимые задачи
Универсальные функции
Некоторые теоремы теории алгоритмов
Оценка сложности алгоритмов
Сложность алгоритмов
Классы сложности P И EXP
Класс сложности NP
Сводимость. NP – полные задачи
Анализ сложности рекурсивных алгоритмов
Точная оценка сложности алгоритмов в наилучшем, наихудшем и среднем случае
Алгоритмы сортировки и их анализ
Алгоритмы вычислительной математики
Логика высказываний
Понятие высказывания. операции с высказываниями
Формулы логики высказываний. интерпретация
Равносильные ФЛВ
Логическое следствие
Метод резолюций для логики высказываний
Применение логики высказываний при решении задач
Логика предикатов
Предикат: определение и примеры
Операции над предикатами. кванторы
Формулы логики предикатов
Общезначимость и выполнимость ФЛП
Эрбрановские модели
Равносильность ФЛП
Нормальные формы
Метод резолюций в логике предикатов
Использование логики предикатов при решении задач
Логическое программирование
Формальные аксиоматические теории
Аксиоматические теории
Формальные теории
Определение и примеры формальных аксиоматических теорий
Интерпретация, полнота и непротиворечивость ФАТ
Исчисление высказываний
Теорема дедукции исчисления высказываний
Основные свойства исчисления высказываний
Исчисление предикатов
Теории первого порядка. формальная арифметика
Литература
Основы теории алгоритмов
Неформальное определение алгоритма и необходимость его уточнения
Арифметические и интуитивно вычислимые функции
Машины Тьюринга
Вычислимость по Тьюрингу
Машины Шёнфилда
Частично вычислимые функции
Кодирование алгоритмов
Алгоритмически неразрешимые задачи
Универсальные функции
Некоторые теоремы теории алгоритмов
Оценка сложности алгоритмов
Сложность алгоритмов
Классы сложности P И EXP
Класс сложности NP
Сводимость. NP – полные задачи
Анализ сложности рекурсивных алгоритмов
Точная оценка сложности алгоритмов в наилучшем, наихудшем и среднем случае
Алгоритмы сортировки и их анализ
Алгоритмы вычислительной математики
Логика высказываний
Понятие высказывания. операции с высказываниями
Формулы логики высказываний. интерпретация
Равносильные ФЛВ
Логическое следствие
Метод резолюций для логики высказываний
Применение логики высказываний при решении задач
Логика предикатов
Предикат: определение и примеры
Операции над предикатами. кванторы
Формулы логики предикатов
Общезначимость и выполнимость ФЛП
Эрбрановские модели
Равносильность ФЛП
Нормальные формы
Метод резолюций в логике предикатов
Использование логики предикатов при решении задач
Логическое программирование
Формальные аксиоматические теории
Аксиоматические теории
Формальные теории
Определение и примеры формальных аксиоматических теорий
Интерпретация, полнота и непротиворечивость ФАТ
Исчисление высказываний
Теорема дедукции исчисления высказываний
Основные свойства исчисления высказываний
Исчисление предикатов
Теории первого порядка. формальная арифметика
Литература