Математическая логика и теория алгоритмов (стр. 3 )

Перечень заданий / вопросов

1. Практическое занятие 1 по теме «Упражнения по теории множеств» [6 часов] Занятие 1 (2 часа): Практическое занятие по теме «Теория множеств» Упражнение 1.1. [1] Упражнение 1.2. [1] Упражнение 1.3. [1] Упражнение 1.4. [1] Упражнения к главе 1. [2] Литература: 1. , Математическая логика и теория алгоритмов. – Томск: STT, 2001. – 176 с. 2. Дискретная математика для программистов. – СПб.: Питер, 2001.–304 с.: ил. Занятие 2 (5 часов): Практическое занятие по теме «Булева алгебра» Примеры 3.1 и 3.2 из главы 3 [1] Упражнения к главе 3. [2] Литература: 1. , Математическая логика и теория алгоритмов. – Томск: STT, 2001. – 176 с. 2. Дискретная математика для программистов. – СПб.: Питер, 2001.–304 с.: ил. Занятие 3 (5 часов): Практическое занятие по теме «Логика высказываний» Упражнения к главе 4. [2] Упражнения 2. [1] Задачи и упражнения к главе 1 [3] Литература: 1. , Математическая логика и теория алгоритмов. – Томск: STT, 2001. – 176 с. 2. Дискретная математика для программистов. – СПб.: Питер, 2001.–304 с.: ил. 3. , Математическая логика и теория алгоритмов: Учебник. - М.: ИНФРА-М; Новосибирск: Изд-во НГТУ, 2004.-224 с. - (Высшее образование). Занятие 4 (6 часов): Практическое занятие по теме «Логика предикатов» Упражнения к главе 4. [2] Упражнения 4. [1] Задачи и упражнения к главе 2 [3] Литература: 1. , Математическая логика и теория алгоритмов. – Томск: STT, 2001. – 176 с. 2. Дискретная математика для программистов. – СПб.: Питер, 2001.–304 с.: ил. 3. , Математическая логика и теория алгоритмов: Учебник. - М.: ИНФРА-М; Новосибирск: Изд-во НГТУ, 2004.-224 с. - (Высшее образование). Занятие 5 (6 часов): Практическое занятие по теме «Теория алгоритмов» Задачи из главы 6 и 7. [1] Задачи и упражнения к главе 4 [2] Список литературы: 1. , Математическая логика и теория алгоритмов. – Томск: STT, 2001. – 176 с. 2. , Математическая логика и теория алгоритмов: Учебник. - М.: ИНФРА-М; Новосибирск: Изд-во НГТУ, 2004.-224 с. - (Высшее образование).

ЗАДАНИЯ К ЭКЗАМЕНУ

Перечень заданий /вопросов

Часть 1. Математическая логика 1.1. Что изучает логика и математическая логика? Компоненты формальных теорий. Что такое высказывание? Логические операции (связки: отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция). 1.2. Формулы логики высказываний (подформулы). Интерпретация формул. Таблицы истинности для формул. 1.3. Выполнимые и опровержимые формулы. Тождественно-истинные и тождественно-ложные формулы (тавтологии и противоречия). Теоремы 1 и 2 «о тавтологиях». Наиболее важные тавтологии. Примеры тавтологий и противоречий. 1.4. Логическая эквивалентность – равносильность формул. Основные равносильности (правила равносильных преобразований). Правило подстановки. Теоремы 1,2,3 «о равносильностях». 1.5. Формальные теории (ФТ). Состав формальной теории Г. Выводимость формул: определения «выводимой формулы», «вывода», «теоремы», свойства «сохранения выводимости при добавлении лишних гипотез», интерпретации и «модели множества формул», «модели ФТ». 1.6. Общезначимость, непротиворечивость, полнота, независимость и разрешимость теории Г: определения общезначимой (тавтологии) и противоречивой формул, формулы «логического следствия» множества формул Г, определения «семантически и формально непротиворечивых» теории Г. Формулировки «метатеорем» о «семантически и формально непротиворечивых» теориях Г (без доказательства). Определения «полной» теории Г, «аксиоматизируемого» множества формул F, «независимой» системы аксиом, «разрешимой и полуразрешимой» теории Г. 1.7. Исчисление высказываний – формальная теория L: определение ИВ (ее состав). Определения: «формула В - частный случай формулы А», унификатор, «формула С - совместный частный случай формул А и В», унифицируемые формулы и наиболее общий унификатор, частный случай набора формул и совместный частный случай набора формул. 1.8. Различные аксиоматизации ИВ: Аксиомы Клини. Доказательство Теоремы 1: . Доказательство Теоремы 2: и ее смысл (производное правило – правило «введения импликации»). 1.9. Доказательство Теоремы «дедукции»:  . 1.10. Применимость правила дедукции для более широкого класса ФТ. Следствие 1: если  , то и обратно (доказательство). Следствие 2:  правило «транзитивности» . Следствие 3: правило «сечения»  . Доказательство следствий. 1.11. Некоторые важные теоремы ИВ: ТЕОРЕМЫ (с доказательством): а) - теорема «удаления двойного отрицания», б) - теорема «введения двойного отрицания», в) , г) - 1-ая теорема контрапозиции, д) - 2-ая теорема контрапозиции, е) , ж) . 1.12. Множество теорем ИВ: доказательство леммы  . 1.13. Множество теорем ИВ: доказательство теоремы и Следствия: Теория  L – формально непротиворечива. 1.14. Исчисление предикатов (ИП) – формальная теория К:  определение и состав ИП. Свободное и связанное вхождение переменных в формулы. Контрарные литералы. Определение «свободного терма» в формуле, «чистого и прикладного ИП (ЧИП и ПИП)» 1.15. Интерпретация ИП: определение, свойства интерпретации (11 свойств, в том числе определения истинной  и открытой формул, модели множества формул). 1.16. Общезначимость: определение и две теоремы: 1) Формула , где терм свободен для переменной в формуле , общезначима. 2) Формула , где терм свободен для переменной в формуле , общезначима. Метатеоремы 1, 2 о полноте ЧИП (без доказательства). 1.17. Определения «логического следования» и «логической эквивалентности». Некоторые следствия и эквивалентности. 1.18. Теория равенства: определение и 3 теоремы (с доказательством): 1) рефлексивность: для любого терма ; 2) симметричность: ; 3) транзитивность: . Вывод из теории равенства. 1.19. Формальная арифметика (аксиоматика). 1.20. Теория абелевых групп (АГ): определения АГ конечного порядка, полной АГ, периодической АГ. Формулировки 2-х Метатеорем Геделя о «неполноте» ПИП 1-го порядка. Вывод из теорем. 1.21. Автоматическое доказательство теорем (АДТ): постановка задачи, теорема «доказательство от противного» (как основа метода «резолюции»): если , где противоречие, то . 1.22. Сведение формул ИП к предложениям. Теорема «о невыполнимости множества предложений, полученных из противоречия». 1.23. Правило резолюции (ПР) для ИВ. Теорема (с доказательством):  «ПР логично, т. е. резольвента – логическое следствие резольвируемых предложений». 1.24. Правило резолюции для ИП. 1.25. Алгоритм АДТ: «опровержение методом резолюций» (3 возможных случая). Вывод в отношении ИП на основании 3-го случая. Пример доказательства (из семинарского занятия) теорем ИВ по алгоритму АДТ «опровержение методом резолюций». Часть 2. ТЕОРИЯ АЛГОРИТМОВ. 2.1. Понятие алгоритма и неформальной вычислимости: определения и основные особенности алгоритма. 2.2. Подход Геделя-Клини к формализации понятия алгоритма: Частично-рекурсивные функции (ЧРФ): операторы суперпозиции, примитивной рекурсии, минимизации для построения ЧРФ. 2.3. Примеры рекурсивности (примитивно-рекурсивных и общерекурсивных функций) 2.4. ерча: Ламбда-исчисление. Его особенности. выражения и их вычисления. 2.5. Определение термов и выражений. редекс и редекс. Процесс редукции. Примеры редукций. 2.6. Нормальные формы выражений и порядок редукций: аппликативный (АПР - стратегия энергичных вычислений) и нормальный (НПР - стратегия ленивых вычислений) порядок редукций. Следствие из теоремы Черча-Россера. 2.7. Рекурсивные функции. Комбинатор неподвижной точки. 2.8. Чистое исчисление. 2.8. Машины Тьюринга. 2.9. Другие подходы к определению понятия алгоритма. Тезис Черча. 2.10. Алгоритмически неразрешимые проблемы. 2.11. Сложность алгоритмов: в наихудшем случае и поведения в среднем. Сложность задачи. 2.12. Классификация задач по сложности: класс Р и класс Е. 2.13. Класс NP. NP-трудные и NP-полные задачи. Теорема Кука.

Методические материалы, определяющие процедуры оценивания знаний, умений, навыков и (или) опыта деятельности, характеризующих этапы формирования компетенций

В ходе изучения дисциплины, студенты, работая с фондом оценочных средств, набирают определенное количество баллов.

Формула перевода итоговой суммы баллов в традиционную оценку:

Отлично        85 - 100 баллов;

Хорошо:        70 - 84 балла;

Удовлетворительно:        50 - 69 баллов;

Не удовлетворительно:        0-49 баллов.