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