Дополнительные главы дискретной математики и кибернетики (2-й поток, 4 курс)
Курс для студентов бакалавриата, читается в осеннем семестре:
- 4-й курс 2-й поток — 2 часа лекций, 1 час консультаций и 1 час семинаров в неделю, отчётность — экзамен.
Лекторы: Ложкин Сергей Андреевич (3-я часть курса), Савицкий Игорь Владимирович (1-я и 2-я части курса).
Аннотация
Первая и вторая части курса посвящены классическим результатам теории автоматов и теории алгоритмов.
В первой части курса изучаются модели конечных автоматов-распознавателей, демонстрируются различные описания классов задаваемых ими множеств, в том числе регулярные выражения. Кроме того, излагаются основные сведения об автоматах-преобразователях и на языке функциональных операций описывается класс автоматных функций.
Во второй части рассматриваются машины Тьюринга и рекурсивные функции: демонстрируются основные приёмы построения машин Тьюринга, строится универсальная машина Тьюринга и устанавливается связь между вычислимыми и частично рекурсивными функциями. Помимо этого, даются основные сведения о сложностных классах P и NP: доказывается теорема Кука, приводятся примеры полиномиальных и NP-полных задач.
Третья часть курса посвящена синтезу схем для реализации функций алгебры логики и дополняет сведения, полученные из курса Основы кибернетики (2-й поток, 3 курс). Излагаются методы получение асимптотических оценок сложности для классов функций с помощью принципа локального кодирования и синтеза не всюду определённых функций, а также способы получения нижних оценок сложности для «индивидуальных» функций с помощью теоремы Храпченко и метода забивающих констант.
Материалы по курсу
Программа и основные материалы
Информационные материалы по курсу 2025-2026 уч. года
Презентации к лекциям 1–12 (первая и вторая части курса; в файле присутствует электронное оглавление)
Литература
- Савицкий И.В. Презентации к лекциям по 1 и 2 частям курса. 2023. (в файле присутствует электронное оглавление)
- Марченков С.С. Избранные главы дискретной математики. М.: МАКС Пресс, 2015. 136 с.
- Ложкин С.А. Дополнительные главы кибернетики. МГУ, 2019.
- Ложкин С. А. Дополнительные главы кибернетики и теории управляющих систем. МГУ, 2008.
- Сапоженко А.А. Некоторые вопросы сложности алгоритмов. М.: Изд-во МГУ, 2001.
Дополнительная литература
- Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2008. 384 с.
- Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Издательский отдел факультета ВМК МГУ, 2002.
- Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. Физматлит, 2005. 416 с.
- Алексеев В.Б., Вороненко А.А., Ложкин С.А., Романов Д.С., Сапоженко А.А., Селезнева С.Н. Задачи по курсу «Основы кибернетики», 2-е изд. М.: МАКС Пресс, 2011.
