Кафедра математической логики и теории алгоритмов

Материалы для группы 141

Контакты преподавателей:

Обзор курса: презентация.
Программа экзамена: скачать.

Материалы к лекции 1. Наивная теория множеств (обновлено 14/2/24)

Задачи без решений (PDF) | Задачи с решениями (PDF) | Презентация

Материалы к лекции 2. Вполне упорядоченные множества (обновлено 08/2/24)

Задачи без решений (PDF) | Задачи с решениями (PDF)

Материалы к лекции 3. Логические языки (обновлено 08/2/24)

Задачи без решений (PDF) | Задачи с решениями (PDF)

Материалы к лекции 4. Элиминация кванторов в поле действительных чисел (обновлено 08/2/24)

Задачи без решений (PDF) | Задачи с решениями (PDF)

Материалы к лекции 5. Построение модели теории в логике отношений (обновлено 08/2/24)

Задачи без решений (PDF) | Задачи с решениями (PDF)

Материалы к лекции 6. Теория моделей. Определения и примеры (обновлено 08/2/24)

Задачи без решений (PDF) | Задачи с решениями (PDF) | Презентация

Материалы к лекции 7. Структуры и теории. Элементарные расширения (обновлено 08/2/24)

Задачи без решений (PDF) | Задачи с решениями (PDF)

Материалы к лекции 8. Полные теории (обновлено 08/2/24)

Задачи без решений (PDF) | Задачи с решениями (PDF) | Презентация

Материалы к лекции 9. Решётка определимости. Автоморфизмы (обновлено 08/2/24)

Задачи без решений (PDF) | Задачи с решениями (PDF)

Материалы к лекции 10. Математическое изучение математики (обновлено 08/2/24)

Задачи без решений (PDF) | Задачи с решениями (PDF)

Ещё материалы к лекции 10. Неполнота математики. Теорема Гёделя (обновлено 08/2/24)

Задачи без решений (PDF) | Задачи с решениями (PDF)

Материалы к лекции 11. Исчисления и породимые множества (обновлено 08/2/24)

Задачи без решений (PDF) | Задачи с решениями (PDF)

Материалы к лекции 12. Сложность вычислений и объектов (обновлено 08/2/24)

Задачи без решений (PDF) | Задачи с решениями (PDF) | Презентация

Материалы к лекции 13. Алгоритмы и вычислимые функции (обновлено 08/2/24)

Задачи без решений (PDF) | Задачи с решениями (PDF)

Материалы к лекции 14. Вычислимость в теории множеств (обновлено 08/2/24)

Задачи без решений (PDF) | Задачи с решениями (PDF)

Вопросы к коллоквиуму 1 (07.03.2024)

Вопросы к коллоквиуму 2 (18.04.2024)

Задачи для семинаров: ссылка.

Файл будет обновляться по мере прохождения курса, ссылка останется той же самой.
Для лучшего понимания материала лекций и семинаров предлагается изучить следующие главы из рекомендованной литературы.

  • Семинар 1 (наивная теория множеств). ВШ-1: 1.1, 1.3-1.8, 2.1.
  • Семинар 2 (вполне упорядоченные множества). ВШ-1: 2.2-2.8.
  • Семинар 3 (логические языки). ВШ-2: 3.1, 3.2, 4.7.
  • Семинар 4 (элиминация кванторов в поле действительных чисел). ВШ-2: 3.6, 3.8.
  • Семинар 5 (построение модели теории в логике отношений). ВШ-2: 2.2, 4.5.
  • Семинар 6 (теория моделей). ВШ-2: 5.1, 5.2.
  • Семинар 7 (структуры и теории, элементарные расширения). ВШ-2: 3.9, 5.2.
  • Семинар 8 (полные теории). ВШ-2: 5.3, 5.4.
  • Семинар 9 (решётка определимости, автоморфизмы). ВШ-2: 3.3, 3.4, 3.5.
  • Семинар 10 (теория формальных грамматик). ПП: главы 1-3. Дополнительные материалы: раз, два.
  • Семинар 11 (алгоритмы). ВШ-3: 1.1-1.5, 2.1-2.3.
  • Семинар 12 (колмогоровская сложность). ВУШ: достаточно прочитать раздел «О чём эта книга?».
  • Семинар 13 (разное).

    1. Исчисление отношений. ВШ-2: 4.1-4.4.

    2. Аксиомы теории множеств. К: глава II, §1-2.

    3. Вокруг теорем Гёделя. Усп (советуем прочитать всю статью).

    4. Переборные задачи. ГД: 1.1-2.6.

Ссылка на «Таблицу успеваемости»: Ссылка

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

  1. [ВШ-1] Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств
  2. [ВШ-2] Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления
  3. [ВШ-3] Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции
  4. [CZ] Chagrov A., Zakharyaschev M. Modal logic.
  5. [Шап] Шапировский И.Б. Конспект курса «Введение в модальную логику».
  6. [ВУШ] Верещагин Н. К., Успенский В.А., Шень А. Колмогоровская сложность и алгоритмическая случайность
  7. [К] Пол Дж. Коэн. Теория множеств и континуум-гипотеза.
  8. [ПП] А.Е. Пентус, М.Р.Пентус. Теория формальных языков.
  9. [Усп] В.А.Успенский. Теорема Гёделя о неполноте и четыре дороги, ведущие к ней.
  10. [ГД] М.Гэри, Д.Джонсон. Вычислительные машины и труднорешаемые задачи.