2 курс 1,2 семестр

Общая трудоемкость дисциплины составляет 8 зачетных единиц, 288 часов из них 4 зачетные единицы (144 часа) в 3 семестре и 4 зачетные единицы (144 часа) в 4 семестре. Основными видами учебных занятий являются лекции и семинарские занятия. Аудиторные занятия составляют 54 часа в 3 семестре и 72 часа во 2 семестре.

№п/п	Наименование раздела дисциплины	Содержание раздела (дидактические единицы)
1	Основные понятия формальных теорий	Алфавит, слова, языки. Формулы. Структура формальных теорий. Понятие интерпретации формальной теории. Способы задания формальных теорий (семантический и синтаксический). Теоремы теории (тождественно истинные формулы в данной интерпретации). Понятие полноты и непротиворечивости формальной теории.
2	Семантика исчисления высказываний	Язык исчисления высказываний. Формулы исчисления высказываний. Семантика исчисления высказываний. Выполнимые и общезначимые формулы. Булева алгебра. Основные равносильности булевой алгебры. Булевы функции. Фиктивные и существенные переменные булевой функции. Основные булевы функции. Расширение понятия формулы исчисления высказываний (формулы в произвольном базисе). Представление булевых функций формулами исчисления высказываний. Понятие схемы из функциональных элементов. Типовые логические элементы ЭВМ. Принцип двойственности. Представление булевых функций совершенными дизъюнктивными и конъюнктивными нормальными формами. Полиномы Жегалкина. Представление булевых функций полиномами Жегалкина. Замыкание системы булевых функций. Основные свойства замыкания. Замкнутые и полные классы в . Примеры замкнутых классов. Полнота системы . Достаточное условие полноты в . Классы самодвойственных, монотонных и линейных булевых функций, их замкнутость. Леммы о несамодвойственной, немонотонной и нелинейной булевой функции. Критерий полноты в . Понятие о результатах Поста.
3	Синтаксис исчисления высказываний	Синтаксическое задание исчисления высказываний. Аксиомы и правила вывода в исчислении высказываний. Понятия доказательства и вывода из совокупности формул в исчислении высказываний. Теорема дедукции, правило силлогизма, закон контрапозиции, приведение к абсурду. Полнота исчисления высказываний. Непротиворечивость исчисления высказываний.
4	Семантика исчисления предикатов	Язык исчисления предикатов. Понятие сигнатуры языка. Понятие предиката. Алгебра предикатов. Основные равносильности алгебры предикатов. Термы и формулы исчисления предикатов. Понятие алгебраической системы. Примеры алгебраических систем. Изоморфизм алгебраических систем. Интерпретация термов и формул исчисления предикатов. Выполнимые и общезначимые формулы исчисления предикатов. Понятие замкнутой формулы исчисления предикатов. Понятие модели совокупности замкнутых формул исчисления предикатов
5	Синтаксис исчисления предикатов	Синтаксическое задание исчисления предикатов. Аксиомы и правила вывода в исчислении предикатов. Понятия доказательства и вывода в исчислении предикатов. Теорема дедукции в исчислении предикатов. Теоремы исчисления предикатов. Непротиворечивость исчисления предикатов
6	Элементарные теории	Понят Понятие элементарной теории. Примеры элементарных теорий Понятие непротиворечивости и полноты элементарной теории. Теорема Линденбаума. Существование модели у любой непротиворечивой элементарной теории. Полнота исчисления предикатов. Теорема Сколема - Левенгейма. Формальная арифметика. Парадокс Ришара. Арифметизация выводов. Понятие о результатах Геделя.
7	Метод резолюций	Метод резолюций для логики высказываний. Подстановка и унификация. Алгоритм унификации. Метод резолюций для логики предикатов. Полнота метода резолюций. Примеры использования метода резолюций.
8	Начальные понятия теории алгоритмов	Общее понятие алгоритма. Основные свойства алгоритма. Понятие модели вычисления (исполнителя алгоритма). Частичные функции. Вычислимые числовые функции, примеры. Разрешимые и неразрешимые предикаты. Примеры разрешимых предикатов. Понятие нумерации. Сведение любого алгоритма к вычислению числовой функции.
9	Основные модели вычислений	Машина с неограниченными регистрами (МНР). Понятие программы, конфигурации и вычисления. Программирование на МНР. Функции вычислимые на МНР, примеры. Основные операции над МНР. Операции суперпозиции, примитивной рекурсии и минимизации. Рекурсивные функции. Понятие о машинах Тьюринга. Формализм Мак-Карти. Диофантовы множества. Тезис Черча, доводы в его справедливость.
10	Нумерации вычислимых функций	Эффективная нумерация пар и троек натуральных чисел. Эффективная нумерация конечных последовательностей натуральных чисел. Эффективная нумерация программ для МНР. Существование универсальной программы. Эффективная нумерация функций вычислимых на МНР.
11	Алгоритмическая теория множеств	Разрешимые множества, их свойства. Перечислимые множества, их свойства. Теорема Поста. Теорема о представлении произвольного перечислимого множества как области определения некоторой вычислимой функции. Теорема о представлении произвольного перечислимого множества как области значений некоторой вычислимой функции. Пример неразрешимого перечислимого множества. Пример множества, не являющегося перечислимым. Теорема о графике вычислимой функции.
12	Неразрешимые алгоритмические проблемы	Диагональный метод. Доказательство существования функции не вычислимой на МНП. Массовые и индивидуальные проблемы. Алгоритмически разрешимые и алгоритмически неразрешимые проблемы. Проблема самоприменимости и проблема останова, их алгоритмическая неразрешимость. Теорема о параметризации. Алгоритмическая сводимость проблем. Теорема Успенского-Райса. Примеры алгоритмически неразрешимых проблем в информатике.
13	Введение в теорию сложности алгоритмов	Сложность алгоритма как функция числового аргумента. Сложность в худшем случае. Необходимость оценки сложности алгоритма с точностью до мультипликативной константы. Асимптотические обозначения. Понятие сложности в среднем. Сортировка и конечные вероятностные пространства. Применение формулы полного математического ожидания. Понятие нижней границы сложности. Оптимальные алгоритмы. Рекуррентные соотношения как средство анализа сложности алгоритмов. Реально выполнимые и реально невыполнимые алгоритмы. Понятие полиномиального алгоритма. Полиномиальный алгоритм как формализация понятия реально выполнимого алгоритма. Теорема об ускорении. Понятие класса сложности. Теорема об иерархии. Задачи распознавания. Классы P, NP и EXPTIME. Примеры задач, принадлежащих классам P и NP. Полиномиальная сводимость. NP-полные задачи. Задача о выполнимости. Теорема Кука. Задача о покрытии и задача о клике, их NP-полнота. Понятие комбинаторной задачи оптимизации, примеры. Связь между задачами распознавания и комбинаторными задачами оптимизации. Важность теории NP-полноты для практического программирования.
14	Приближенные алгоритмы	Понятие приближенного алгоритма для комбинаторных задач оптимизации, его точность. Жадные алгоритмы. Точность жадного алгоритма в задачи о покрытии.

1. 
   Конечная порожденность замкнутых классов в .
   
2. 
   Описание замкнутых классов в .
   
3. 
   Функции многозначной логики. Основные отличия от при k > 2.
   
4. 
   Логики Лукасевича и простые числа.
   
5. 
   Независимость аксиом исчисления высказываний.
   
6. 
   Конечная базируемость классов тождеств над конечными системами булевых функций.
   
7. 
   Критерии полноты по неявной выразимости в трехзначной логике.
   
8. 
   Классы функций k-значной логики, замкнутые относительно операции суперпозиции.
   
9. 
   Конечная порожденность предполных классов монотонных функций многозначной логики.
   
10. 
    Полиномиальные представления булевых функций.
    
11. 
    Вероятностные значения случайных булевых выражений.
    
12. 
    Теорема Геделя о выполнимости.
    
13. 
    Примеры разрешимых элементарных теорий.
    
14. 
    Неразрешимость логики предикатов.
    
15. 
    Эффективный способ проверки тождественной истинности формул, содержащих только одноместные предикаты.
    
16. 
    Формальные модели компьютеров и вычислений.
    

1. 
   Структура формальных теорий. Понятие интерпретации формальной теории. Способы задания формальных теорий.
   
2. 
   Язык исчисления высказываний. Формулы исчисления высказываний. Семантика исчисления высказываний. Выполнимые и общезначимые формулы.
   
3. 
   Алгебра высказываний. Основные равносильности алгебры высказываний.
   
4. 
   Булевы функции. Основные булевы функции. Расширение понятия формулы исчисления высказываний (формулы в произвольном базисе). Представление булевых функций формулами.
   
5. 
   Принцип двойственности. Представление булевых функций совершенными дизъюнктивными нормальными формами.
   
6. 
   Полиномы Жегалкина. Представление булевой функции полиномом Жегалкина.
   
7. 
   Замкнутые и полные классы в . Примеры замкнутых классов.
   
8. 
   Полнота системы . Достаточное условие полноты в .
   
9. 
   Классы самодвойственных, монотонных и линейных булевых функций, их замкнутость.
   
10. 
    Леммы о несамодвойственной, немонотонной и нелинейной булевых функциях
    
11. 
    Критерий полноты в . Понятие о результатах Поста.
    
12. 
    Синтаксическое задание исчисления высказываний. Аксиомы и правила вывода в исчислении высказываний. Понятия доказательства и вывода из совокупности формул в исчислении высказываний. Теорема дедукции.
    
13. 
    .Полнота исчисления высказываний. Непротиворечивость исчисления высказываний.
    
14. 
    Понятие предиката. Алгебра предикатов. Основные равносильности алгебры предикатов.
    
15. 
    Язык исчисления предикатов. Термы и формулы исчисления предикатов. Интерпретация термов и формул исчисления предикатов. Выполнимые и общезначимые формулы исчисления предикатов. Понятие замкнутой формулы исчисления предикатов. Понятие модели совокупности замкнутых формул исчисления предикатов.
    
16. 
    Аксиомы и правила вывода в исчислении предикатов. Теоремы исчисления предикатов. Непротиворечивость исчисления предикатов.
    
17. 
    Метод резолюций для логики высказываний. Алгоритм унификации.
    
18. 
    Метод резолюций для логики предикатов. Полнота метода резолюций.
    

1. 
   Общее понятие алгоритма. Основные свойства алгоритма. Вычислимые числовые функции.
   
2. 
   Полиномиальная сводимость.
   
3. 
   .Машина с неограниченными регистрами. Понятие программы, конфигурации и вычисления.
   
4. 
   NP-полные задачи. Теорема Кука.
   
5. 
   Функции, вычислимые на МНР. Тезис Черча.
   
6. 
   NP-полнота задачи о клике.
   
7. 
   Понятие нумерации. Эффективная нумерация пар и троек натуральных чисел.
   
8. 
   Комбинаторные задачи оптимизации, примеры
   
9. 
   Разрешимые и неразрешимые предикаты. Примеры разрешимых предикатов.
   
10. 
    Понятие сложности алгоритма.
    
11. 
    Эффективная нумерация конечных последовательностей натуральных чисел.
    
12. 
    Реально выполнимые и реально невыполнимые алгоритмы.
    
13. 
    Эффективная нумерация программ для МНР.
    
14. 
    Примеры числовых невычислимых функций.
    
15. 
    Универсальная программа. Теорема о параметризации.
    
16. 
    Связь комбинаторных задач оптимизации с задачами распознавания.
    
17. 
    Разрешимые и неразрешимые проблемы. Проблема самоприменимости, ее неразрешимость.
    
18. 
    Понятие класса сложности.
    
19. 
    Разрешимые и неразрешимые проблемы. Проблема останова, ее неразрешимость.
    
20. 
    Понятие о верхних и нижних оценках сложности задачи
    
21. 
    Эквивалентные программы. Инвариантные и нетривиальные свойства программ. Теорема Успенского-Райса.
    
22. 
    Разрешимые множества и их свойства.
    
23. 
    Классы P и EXPTIME. Примеры задач из класса P.
    
24. 
    Перечислимые множества и их свойства.
    
25. 
    Класс NP. Примеры задач из класса NP.
    
26. 
    Теорема Поста.
    
27. 
    Теорема о графике вычислимой функции
    
28. 
    Важность теории NP-полноты для практического программирования.
    

• 
  Конспект лекций О.Б.Лупанова по курсу «Введение в математическую логику», М.: МГУ, 2007. (http://mech.math.msu.su/department/dm/dmmc/index.htm)
  
• 
  Н.К Верещагин, А.Шень Языки и исчисления, М.:МЦНМО, 2000.
  
• 
  И.А. Лавров Математическая логика, М.: Академия, 2006.
  
• 
  Н. Катленд Вычислимость. Введение в теорию рекурсивных функций, М.: Мир, 1983.
  
• 
  В.Н. Крупский, В.Е. Плиско Теория алгоритмов, М.: Академия, 2006.
  
• 
  В.Л. Матросов Теория алгоритмов, М.: Прометей, МГПИ, 1989.
  
• 
  Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов, 3-е изд. - М.: Наука, 1995.
  

б) дополнительная литература:

• 
  Э. Мендельсон «Введение в математическую логику», М.: Наука, 1976.
  
• 
  Ю.Л. Ершов, Е.А. Палютин Математическая логика, М.: Наука, 1979.
  
• 
  А.В. Гладкий Математическая логика, М.: РГГУ, 1998.
  
• 
  Н.Н. Непейвода Прикладная логика, Новосибирск, НГУ, 2000.
  
• 
  А.И. Мальцев Алгоритмы и рекурсивный функции, Наука, 1965.
  
• 
  В.Н. Крупский Введение в сложность вычислений, М.: ФАКТОРИАЛ ПРЕСС, 2006.
  
• 
  С.А. Абрамов Лекции о сложности алгоритмов, М.:МЦНМО, 2009.
  
• 
  М. Гэри, Д. Джонсон Вычислительные машины и труднорешаемые задачи, М.: Мир, 1982.
  
• 
  В. Босс Перебор и эффективные алгоритмы, Лекции по математике т.10, М.: ЛКИ, 2008.