Математическая логика и теория алгоритмов

Специалитет 2019/2020

Статус: Курс обязательный (Компьютерная безопасность)

Кто читает: Департамент прикладной математики

Где читается: Московский институт электроники и математики им. А.Н. Тихонова

Когда читается: 2-й курс, 3, 4 модуль

Формат изучения: без онлайн-курса

Преподаватели: Анашкин Александр Владимирович, Бусяцкая Ирина Константиновна, Кочетков Юрий Юрьевич, Попов Владимир Леонидович

Специальность: 10.05.01. Компьютерная безопасность

Язык: русский

Кредиты: 4

Контактные часы: 62

Полная версия программы учебной дисциплины

Аннотация

Целями освоения дисциплины «Математическая логика и теория алгоритмов» являются: • получение представления об основных понятиях, методах и результатах теории вычислимости; • получение представления об основных понятиях и методах булевой алгебры; • получение представления об основных понятиях формальных исчислений.

Цель освоения дисциплины

Получение представления об основных понятиях, методах и результатах теории вычислимости
Получение представления об основных понятиях и методах булевой алгебры
Получение представления об основных понятиях формальных исчислений

Планируемые результаты обучения

Решает задачи о равномощности множеств.
Решает задачи о программировании на МНР: о системе команд, их нумерации и о нумерации программ.
Решает задачи о вычислимых функциях, включая явное построение вычисляющих их программ
Решает задачи о вычислимых, перечислимых и диофантовых множествах.
Решает задачи о булевых функциях, их совершенной, сокращенной и тупиковой дизъюнктивной нормальной форме, их полиномах Жегалкина
Решает задаче о замкнутости и полноте систем булевых функций
Решает задачи о контактных схемах.
Решает задачи о формальных исчислениях, в том числе об исчислении высказываний

Содержание учебной дисциплины

Элементы теории множеств
1.1. Взаимно однозначное соответствие между множествами. Равномощность множеств. Счетные множества, простейшие теоремы о счетных множествах. 1.2. Теорема о конечности или счетности объединения конечного или счетного множества конечных или счетных множеств. Ее применения. 1.3. Теорема о равномощности бесконечного множества и его объединения с конечным или счетным множеством. 1.4. Определение неравенства между мощностями множеств. Теорема Кантора—Бернштейна. 1.5. Теорема Кантора. Несчетность множества всех бесконечных последовательностей из 0 и 1. 1.6. Парадоксы теории множеств.
Вычислимость
2.1. Машина с неограниченными регистрами (МНР). Система команд. Программа. Схема работы МНР по заданной программе. 2.2. МНР-вычислимые функции. Разрешимые предикаты. 2.3. Теорема о вычислимости суперпозиции вычислимых функций. 2.4. Неформальные алгоритмы. Тезис Черча. 2.5. Теорема о существовании МНР-невычислимых функций. 2.6. Система нумерации МНР-команд и МНР-программ. Примеры явного описания программ по заданному номеру. 2.7. Построение МНР-невычислимой программы, использующее явную нумерацию программ. 2.8. Универсальная функция для заданного множества МНР-вычислимых функций. Теорема о существовании универсальной функции для множества всех МНР-вычислимых функций одного переменного. 2.9. Тотальные МНР-вычислимые функции. Теорема о несуществовании универсальной функции для множества всех тотальных МНР-вычислимых функций одного переменного. 2.10. Теорема о несуществовании алгоритма, определяющего тотальность/нетотальность элементов множества всех МНР-вычислимых функций. 2.11. Разрешимые и перечислимые множества. Теорема о разрешимости любого перечислимого множества. Теорема о существовании перечислимых неразрешимых множеств. 2.12. Теорема о том, что всякое перечислимое множество натуральных чисел есть проекция на первую координату некоторого разрешимого подмножества в множестве всех пар натуральных чисел. 2.13. Алгебраические подмножества. Диофантовы подмножества. Теорема Матиясевича (без доказательства). 10-я проблема Гильберта и ее отрицательное решение с помощью теоремы Матиясевича. 2.14. Теорема о том, что всякое перечислимое множество есть множество значений некоторой тотальной МНР-вычислимой функции. 2.15. Теорема о том, что множество перечислимо тогда и только тогда, когда оно является множеством неотрицательных значений некоторого многочлена от нескольких переменных с целыми коэффициентами. Приложение: существование «формулы простых чисел».
Булевы функции
3.1. Основные определения: булева функция, конъюнкция, дизъюнкция, отрицание, импликация, эквивалентность, таблица истинности. 3.2. n-мерный единичный куб, его грани в вершины. Нумерация вершин с помощь двоичного разложения целых чисел. 3.3. Определение формулы. Задание булевых функций с помощью формул, вопрос о его единственности. Равносильность формул. Список важнейших равносильностей алгебры логики. 3.4. Носитель булевой функции. Теорема о носителе конъюнкции (дизъюнкции) булевых функций. 3.5. Элементарная конъюнкция. Правильная элементарная конъюнкция и теорема о ее носителе. 3.6. Дизъюнктивная нормальная форма (ДНФ) булевой функции и совершенная ДНФ (СДНФ). Теорема о существовании единственной СДНФ и любой ненулевой булевой функции. Практический способ нахождения СДНФ. 3.7. Полином Жегалкина булевой функции. Теорема о его существовании и единственности. 3.8. Сокращенная ДНФ. Правила обобщенного склеивания и поглощения. 3.9. Алгоритм Блейка нахождения СДНФ. 3.10. Тупикования ДНФ и способ ее нахождения. 3.11. Двойственная и самодвойственная булева функция. Теорема о суперпозиции двойственных булевых функций. 3.12. Монотонные булевы функции Теорема о суперпозиции монотонных булевых функций. 3.13. Функциональное замыкание совокупности булевых функций. Функционально замкнутые совокупности. Полные совокупности. Классы S, L, M, T0, T1, их функциональная замкнутость и полнота. 3.14. Теорема Поста о полноте. 3.15. Контактные схемы и булевы функции, ими реализуемые. Проблема минимизации контактных схем. Функция Шеннона. Теоремы Шеннона и Лупанова.
Формальные исчисления
4.1. Компоненты, из которых состоит любое формальное исчисление: язык, аксиомы, правило вывода. 4.2. Язык, аксиомы и правило вывода исчисления высказываний. 4.3. Алгоритм, распознающий является ли конечная последовательность формул выводом в исчислении высказываний или нет. 4.4. Теорема об отсутствии в исчислении высказываний лишних правил вывода. 4.5. Формулы в исчислении высказываний, являющиеся тавтологией. Критерий выводимости формулы в исчислении высказываний (с доказательством того, что из выводимости следует тавтологичность). 4.6. Алгоритм эффективного нахождения вывода по данной выводимой формуле в исчислении высказываний.

Элементы контроля

опрос на семинарах
контрольная работа №1
На экзамене студент, не написавший вовремя контрольную работу по уважительной причине, может получить в качестве компенсации задание, которое оценивается в 6 баллов.
контрольная работа №2
На экзамене студент, не написавший вовремя контрольную работу по уважительной причине, может получить в качестве компенсации задание, которое оценивается в 6 баллов.
экзамен
Форма экзамена---письменный, а для части студентов---и устный (см. ниже). На экзамене студент, не написавший вовремя контрольную работу по уважительной причине, может получить в качестве компенсации задание, которое оценивается в 6 баллов. Устный Устный экзамен проводится после письменного в следующих двух случаях: (a) либо суммарный балл по накопленной оценке и письменному экзамену ниже 4, (b) либо этот балл выше 3, но студент считает, что заслуживает более высокой оценки. В остальных случаях указанный суммарный балл считается итоговым и выставляется в экзаменационную ведомость. В случае (б) указанный суммарный балл неснижаемым не является: если ответ на устном экзамене показывает существенные пробелы в освоении материалов курса, этот балл может быть снижен. Устный экзамен проводится в виде опроса по материалам курса на платформе Microsoft Teams https://drive.google.com/file/d/1bDksog2P30Q6ac3QKh5NCQwsxNIdWpFs/view Студенты подключаются классу, созданному на базе этой платформы тем преподавателем, который вел у них занятия и проводил письменный экзамен. К экзамену необходимо подключиться согласно расписанию (т. е. 11 мая 2020 г. в 10:30). Компьютер студента должен удовлетворять требованиям: наличие рабочей камеры и микрофона, поддержка Microsoft Teams. Для участия в экзамене студент обязан: поставить на аватар свою фотографию, явиться на экзамен согласно точному расписанию, при ответе включить камеру и микрофон. Во время экзамена студентам запрещено: выключать камеру, пользоваться конспектами и подсказками. Кратковременным нарушением связи во время экзамена считается нарушение связи менее минуты. Долговременным нарушением связи во время экзамена считается нарушение минута и более. При долговременном нарушении связи студент не может продолжить участие в экзамене. Пересдача назначается учебной частью.

Промежуточная аттестация

Промежуточная аттестация (4 модуль)
0.2 * контрольная работа №1 + 0.2 * контрольная работа №2 + 0.2 * опрос на семинарах + 0.4 * экзамен

Программа дисциплины