5. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины и учебно-методическое обеспечение самостоятельной работы студентов

№ темы

п/п

Тема, контрольные вопросы

3 семестр

1.

Тема: Основные понятия математической логики

1.1. Задачи, цель и предмет курса. 1.2. Понятие высказывания. 1.3. Основные логические операции. 1.4. Определение пропорциональной формулы. 1.5. Истинные значения пропорциональных формул в классической двузначной логике. 1.6. Отношение семантического следования и семантической равносильности формул. 1.7. Выполнимые формулы. 1.8. Классификация формул. 1.9. Основные законы булевой алгебры. 1.10. Проблема разрешения в логике высказываний. 1.11. Нормальные формы, СДНФ, СКНФ, хорновские дизъюнкты. 1.12. Минимизация формул. 1.13. Анализ и синтез цифровых электронных схем с базовыми логическими элементами.

2.

Тема: Исчисление высказываний

2.1. Понятие логического исчисления. 2.2. Выводимость в логическом исчислении. 2.3. Элементарные свойства выводимости. 2.4. Язык, аксиомы и правила вывода исчисления высказываний. 2.5. Теорема дедукции. 2.6. Непротиворечивые множества формул. 2.7. Семантическая и синтаксическая полнота. 2.8. Независимость аксиом и правил вывода. 2.9. Многозначные логики.

3.

Тема: Логика предикатов

3.1. Понятие предиката на наборе множеств. 3.2. Логические операции над предикатами. 3.3. Кванторы. 3.4. Область истинности предиката. 3.5. Теоретико-множественный смысл операций над предикатами. 3.6. Термы и формулы логики предикатов. 3.7. Семантика термов и формул. 3.8. Функция истинности формулы. 3.9. Выполнимые и общезначимые формулы. 3.10. Семантическое исследование и равносильность формул. 3.11 Основные равносильности. 3.12. Проблема общезначимости и разрешения в логике предикатов.

4.

Тема: Исчисление предикатов, формальные аксиоматические теории

4.1. Алфавит и аксиомы исчисления предикатов. 4.2. Правила вывода в исчислении предикатов. 4.3. Теоремы о семантической пригодности и полноте. 4.4. Теории 1-го порядка: логические и собственные аксиомы. 4.5. Примеры теорий 1-го порядка. 4.6. Противоречивость и непротиворечивость теорий 1-го порядка, непротиворечивость выполнимых теорий. 4.7. Теорема Геделя о полноте. 4.8. Основные понятия лямбда-исчисления.

5.

Тема: Основы теории алгоритмов. Нормальные алгоритмы Маркова

5.1. Определения алгоритма. 5.2. Конструктивные объекты и их типы. 5.3. Нумерация конструктивных объектов. 5.4. Алгоритмический процесс. 5.5. Вычислимые функции. 5.6. Сигнализирующее множество алгоритма. 5.7. Словарные функции и множества. 5.8. Формулы подстановки в нормальных алгоритмах Маркова. 5.9. Применение алгоритмов Маркова для преобразований над строками. 5.10. Возможности нормальных алгоритмов, тезис Маркова.

6.

Тема: Элементы теории множеств. Машина Тьюринга

6.1. Разделимые множества, их свойства. 6.2. Полуразделимые множества. 6.3. Теорема Поста-Чёрча. 6.4. Перечислимые множества, их связь с полуразделимыми. 6.5. Вычислимость и перечислимость. 6.6. Модель машины Тьюринга. 6.7. Функции, вычислимые по Тьюрингу. 6.8. Модели, эквивалентные машине Тьюринга. 6.9. Синтез машин Тьюринга. 6.10. Тезис Черча-Тьюринга. 6.11. Многоленточные машины Тьюринга. 6.12. Квантовый аналог машины Тьюринга.

7.

Тема: Рекурсивные функции

7.1. Арифметические функции. 7.2.Операции над арифметическими функциями. 7.3. Примитивно-рекурсивные функции. 7.4. Ограниченная сумма и произведение примитивно-рекурсивных функций. 7.5. Частично-рекурсивные функции. 7.6. Связь частично-рекурсивных функций с машиной Тьюринга

8.

Тема: Неразрешимые алгоритмические проблемы

8.1. Примеры невычислимых функций. 8.2. Проблемы самоприменимости и остановки машин Тьюринга, их алгоритмическая неразрешимость. 8.3. Теорема Райса. 8.4. Полугруппы слов. 8.5. Задание полугрупп образующими и соотношениями. 8.6. Проблема равенства слов и теорема Маркова-Поста. 8.7. Десятая проблема Гильберта. 8.8. Теорема Матиясевича. 8.9. Понятие сложности вычислений, временная сложность. 8.10. Полиномиальные алгоритмы и задачи, класс P. 8.11. Класс NP, NP-полные и NP-трудные задачи. 8.12 Класс сложности E. 8.13 Емкостная сложность алгоритма