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

2026/2027

Учебный год

RUS

Обучение ведется на русском языке

3

Кредиты

Кто читает:

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

Статус:

Курс обязательный

Когда читается:

2-й курс, 3, 4 модуль

Преподаватели

Анашкин Александр Владимирович

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

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

Аннотация

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

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

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

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

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

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

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

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

• Контрольная работа №1
• Контрольная работа №2
• Activity
• Oral interview

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

• 2026/2027 4th module
  0.1 * Activity + 0.2 * Контрольная работа №1 + 0.2 * Контрольная работа №2 + 0.4 * Oral interview

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

Рекомендуемая основная литература

• Задачи по теории множеств, математической логике и теории алгоритмов, Лавров, И. А., 2004
• Лекции по математической логике и теории алгоритмов. Ч.1: Начала теории множеств, Верещагин, Н. К., 2012
• Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств - Верещагин Н.К., Шень А. - Московский центр непрерывного математического образования - 978-5-94057-321-0 - 2008 - русский - https://e.lanbook.com/book/9306 - ЛАНЬ - 9306
• Справочная книга по математической логике. Ч.2: Теория множеств, , 1982
• Теория множеств, Куратовский, К., 1970

Рекомендуемая дополнительная литература

• Задачи по теории множеств, математической логике и теории алгоритмов, Лавров, И. А., 2002

Авторы

• Сорокин Александр Владимирович
• Лось Алексей Борисович
• Попов Владимир Леонидович
• Анашкин Александр Владимирович