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

Паспорт

• Где и когда. I–II семестры программы 01.03.02 «Прикладная математика и информатика», профиль «Математика», набор 2025.
• Объём. 225 часов, 5 з.е.: 90 часов и 2 з.е. в I семестре, 135 часов и 3 з.е. во II. Всего 120 аудиторных часов (60 лекций, 60 семинаров), 75 часов самостоятельной работы и 30 часов на подготовку к экзамену.
• Кафедра. Кафедра дискретной математики.
• Преподаватель. В доступной программе 2022 лектор — доцент Е. В. Дашков. Это исторические данные документа, а не подтверждение распределения лекторов для набора 2025.
• Итоговый контроль. Аттестация предусмотрена в обоих семестрах; её форму для конкретной группы нужно смотреть в актуальном плане.

Содержание опубликованной программы

Ниже — полный список из доступной программы «Математическая логика» 2022 года, лектор Е. В. Дашков. Он включает 24 темы и опубликован как исторический вариант, а не как неизменная программа набора 2025.

1. Интуитивное понятие множества, элементы, включение, равенство, способы образования множеств, пустое множество и парадокс Рассела.
2. Объединение, пересечение, дополнение и их тождества; пары Куратовского, декартово произведение, упорядоченные \(n\)-ки и степени множества.
3. Бинарные отношения, обращение и композиция, отношения на множестве, образы и прообразы.
4. Функциональность, инъективность, сюръективность и тотальность отношений; частичные функции и функции многих аргументов.
5. Инъекции, сюръекции, биекции, равномощность, сравнение мощностей, теоремы Кантора и Кантора—Бернштейна—Шрёдера, аксиома выбора и индексированные семейства.
6. Рефлексивность, симметричность и транзитивность; частичные и линейные порядки, грани, супремум, инфимум, решётки, цепи и антицепи.
7. Эквивалентности, классы эквивалентности, фактор-множества и разбиения.
8. Конечные множества, индукция, принцип Дирихле, мощность и теорема о рекурсии.
9. Мощностные свойства конечных и счётных множеств, правила суммы и произведения, счётные объединения.
10. Слова и формальные языки, конкатенация, префиксы и суффиксы, индуктивные определения и индукция по построению.
11. Фундированные и вполне упорядоченные множества, принцип индукции, предельные элементы.
12. Строение вполне упорядоченных множеств, сложение и умножение на них.
13. Начальные отрезки, изоморфизм и сравнение вполне упорядоченных множеств.
14. Сравнение вполне упорядоченного множества с подмножеством, вычитание и деление с остатком.
15. Цепи в частично упорядоченном множестве, лемма Цорна, теорема Цермело и их связь с аксиомой выбора.
16. Алгоритмы, вычислимые функции, разрешимые и перечислимые множества, теорема Поста.
17. \(T\)-предикат алгоритма, теорема о графике вычислимой функции, образы и прообразы, полухарактеристическая функция.
18. Универсальная вычислимая функция, проблемы самоприменимости и остановки, примеры перечислимых и неразрешимых множеств.
19. Главная универсальная функция, кодирование пар, теорема Клини о неподвижной точке, теорема о рекурсии и совместная рекурсия.
20. Индексные множества, теоремы Райса—Успенского и Райса—Шапиро, \(m\)-сводимость.
21. Машины Тьюринга и реализация свойств алгоритмов в моделях машин Тьюринга и частично рекурсивных функций.
22. Бестиповое \(\lambda\)-исчисление: термы, комбинаторы, \(\beta\)- и \(\eta\)-редукции, нормальная форма и теорема Чёрча—Россера.
23. Представимость частичных функций в \(\lambda\)-исчислении, кодирование логики и натуральных чисел, композиция и примитивная рекурсия.
24. Комбинаторы неподвижной точки, рекурсия и минимизация, эквивалентность моделей частично рекурсивных функций и \(\lambda\)-исчисления, неразрешимость \(\lambda\)-исчисления и теорема Скотта.

Оценивание

Открытая актуальная БРС с числовыми порогами не найдена.

Источники и актуальность

Программа 2022, архив материалов кафедры, план 01.03.02, набор 2025.