Экспандеры: конструкции и приложения, заметки по материалам лекций 2009 и 2014 года.
Исправленная версия (март 2019 г.); версия января 2015 г.

Заметки о теории кодирования (2 изд.)
по семинарам на мехмате МГУ в 2004/2005 учебном году (совместно с А.Румянцевым и А.Шенем)

Курс Ведение в теорию информации, ФИВТ МФТИ

Программа курса 2014 года
Краткий конспект курса 2014 года (upd: 23.01.2016)

Упражнения к первой части курса
Упражнения ко второй части курса

Программа курса 2013 года

Конспект лекций по курсу Коммуникационная сложность
мех-мат МГУ, весенний семестр 2012 года, совместно с В.В.Подольским)

Курс Математическая логика и теория алгоритмов, МФТИ весенний семестр 2014 года (совместно с Д.В.Мусатовым)

ПМФ: программа второго семестра курса для специальности; основные темы первого семестра курса семестра курса.
ПМИ: программа второго семестра курса для специальности; основные темы первого семестра курса семестра курса.

Краткий конспект первой темы семестра (теория множеств и трансфинитная индукция): для студентов специальностей специальности ПМФ и ПМИ

Упражнения к курсу по теме трансфинитная индукция (ПМИ + ПМФ):

• Первый листок.
• Второй листок.
• Третий листок.
• Четвёртый листок.
• Пятый листок.
• Шестой листок.

Первая контрольная: задачи для работы над ошибками.

Краткий конспект второй темы семестра - вычислимость для ПМФ и ПМИ

Упражнения к курсу по теме вычислимость для студентов специальности ПМФ:

• Седьмой листок.
• Восьмой листок.
• Девятый листок.
• Десятый листок.

Упражнения к курсу по теме вычислимость для студентов специальности ПМИ:

• Седьмой листок.
• Восьмой листок.
• Девятый листок.
• Десятый листок.

Вторая контрольная: задачи для работы над ошибками для студентов специальности ПМИ и ПМФ.

Очень краткий конспект третьей темы семестра - лямбда-исчисление - для ПМФ и ПМИ

Упражнения к курсу по теме лямбда-исчисление:

• Одиннадцатый листок.

Рекомендуемая литература по лямбда-исчислению:

• Барендрегт X. Ламбда-исчисление. Его синтаксис и семантика. Пер. с англ. М.: Мир, 1985.
• Peter Selinger, Lecture notes on the lambda calculus.
• Achim Jung, A short introduction to the Lambda Calculus.
• Henk Barendregt, Erik Barendsen, Introduction to Lambda Calculus.
• Lawrence Paulson. Foundations of Functional Programming.

Краткий конспект четвертой темы семестра - арифметическая иерархия и теорема Гёделя о неполноте для специальностей ПМФ и ПМИ

Основная литература для подготовки к экзамену:

• Н.К.Верещагин, А.Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. М.: МЦНМО, 2008
• Лавров И.А., Максимова Л.Л., Задачи по теории множеств, математической логике и теории алгоритмов. 1995.

Материалы прошлых лет:

Программа второго семестра курса (весна 2013).

Краткий конспект первой части семестра (теория множеств, трансфинитная индукция)
Краткий конспект второй части семестра (алгоритмическая вычислимость)
Краткий конспект четвёртой части семестра (арифметическая иерархия и теорема Гёделя о неполноте)

Упражнения к курсу:

• Математическая индукция.
• Фундированные и вполне упорядоченные множества.
• Арифметические операции над ординалами.
• Применение трансфинитной индукции.


• Задачи для контроля первой темы курса (трансфинитная индукция).


• Вычислимые функции, разрешимые и перечислимые множества.
• Построение неразрешимых и неперечислимых множеств.
• Гёделевы нумерации вычислимых функций и теорема Клини о неподвижной точке.
• m-сводимость.


• Задачи для контроля второй темы курса (вычислимость).


• Лямбда-исчисление: приведение к нормальной форме.
• Лямбда-исчисление: теорема о неподвижной точке и рекурсивное программирование.
• Лямбда-исчисление: дополнительные задачи.


• Арифметическая иерархия и теорема Гёделя о неполноте.

• Программа курса (2009)
• Билеты и список задач к экзамену (2009)
• Билеты и список задач к экзамену (2010)
• Программа курса для специальности ПМИ (2012)
• Программа курса для спецаиальности ПМФ (2011/12)
• Задачи для подготовки к контрольной и экзамену: теория алгоритмов (2012)
• Задачи для подготовки к экзамену: арифметическая иерархия (2012)
• Задачи для подготовки к контрольной и экзамену: формальная арифметика (2012)
• Задачи для подготовки к контрольной и экзамену: лямбда-исчисление (2012)

Курс Алгоритмические методы в теории сложности, мех-мат МГУ, весенний семестр 2013 года:
программа курса, краткий конспект лекций, задачи к экзамену.

Краткий конспект лекций Алгоритмические задачи теории графов
мех-мат МГУ, весенний семестр 2011 года
задачи к курсу

Краткий конспект лекций Теория кодирования и сложность вычислений
мех-мат МГУ, весенний семестр 2010 года
задачи к курсу

Программа курса Сложность вычислений, МФТИ, весна 2009