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

Специалитет 2021/2022

Лучший по критерию «Новизна полученных знаний»

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

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

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

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

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

Охват аудитории: для всех кампусов НИУ ВШЭ

Преподаватели: Анашкин Александр Владимирович, Попов Владимир Леонидович

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

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

Кредиты: 4

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

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

Аннотация

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

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

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

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

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

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

Элементы теории множеств
Вычислимость
Булевы функции
Формальные исчисления

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

опрос на семинарах
контрольная работа №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. Для участия в экзамене студент обязан: поставить на аватар свою фотографию, явиться на экзамен согласно точному расписанию, при ответе включить камеру и микрофон. Во время экзамена студентам запрещено: выключать камеру, пользоваться конспектами и подсказками. Кратковременным нарушением связи во время экзамена считается нарушение связи менее минуты. Долговременным нарушением связи во время экзамена считается нарушение минута и более. При долговременном нарушении связи студент не может продолжить участие в экзамене. Пересдача назначается учебной частью.

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

2021/2022 учебный год 4 модуль
0.1 * опрос на семинарах + 0.3 * контрольная работа №1 + 0.3 * экзамен + 0.3 * контрольная работа №2

Список литературы

Авторы

Попов Владимир Леонидович

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