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

Просеминар по математической логике и информатике

для студентов 1–3 курсов
руководители семинара: проф. Л. Д. Беклемишев, к. ф.-м. н. С. Л. Кузнецов, асп. А. А. Оноприенко, проф. А. Л. Семёнов

Просеминар проходит очно по четвергам 16:45-18:20, начиная с 14 марта. Собираемся на кафедре (аудитория 1605 Главного здания МГУ). По вопросам пропусков пишите Анастасии Александровне Оноприенко.

Анонс: 23 мая 2024 года Нестандартные модели арифметики и теорема Париха (Л.Д.Беклемишев).

Аннотация. Мы поговорим о нестандартных моделях арифметики Пеано и докажем теорему Р. Париха о том, что с помощью аксиом арифметики с индукцией для формул с ограниченными кванторами нельзя доказать тотальность экспоненты (как и любой вычислимой функции сверхполиномиального роста).


Просеминар для младшекурсников является традицией кафедры математической логики и теории алгоритмов. На этом семинаре начинали свою работу многие студенты, ставшие потом известными математиками. Участие в семинаре не требует дополнительной подготовки, там сразу будут предложены задачи разных уровней сложности, а также исследовательские нерешённые проблемы, вводящие участника в тематику, существенную для разных областей математики, computer science и их приложений.

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

Формат просеминара — короткие серии из 2–3 занятий на разные темы, проводимые профессорами, преподавателями, аспирантами и студентами кафедры, с параллельным решением и разбором задач. Приглашаются студенты 1–3 курсов, школьники старших классов, студенты других специальностей и вообще все интересующиеся. Начинать посещение семинара можно с любого занятия.

По всем вопросам можно обращаться к Анастасии Александровне Оноприенко по электронной почте: ansidiana@yandex.ru.

 


Материалы 2024 года (весна)
14 марта и 4 апреля 2024 года. Омега-языки и автоматы над бесконечными словами (Тихон Пшеницын).
21 и 28 марта 2024 года. Деревья решений и вопросная сложность (Н.К.Верещагин).
18 апреля 2024 года. Лямбда-исчисление (С.Л.Кузнецов).
25 апреля и 2 мая 2024 года. Интуиционистская логика (А.А.Оноприенко, М.Е.Вишникин).
16 мая 2024 года. Цепи Анселя (С.А.Корнеев).

Материалы 2023 года (осень)
5 и 19 октября 2023 года Исчисление секвенций (А.А. Оноприенко)
26 октября и 2 ноября 2023 Исчисление секвенций для логики предикатов: классической и интуиционистской (А.А. Оноприенко)
9 ноября 2023 года Лямбда анализ, комбинаторная логика и функциональные языки программирования (Руслан Голов)
16 и 23 ноября 2023 года Соответствие Карри — Говарда и Coq (С.Л. Кузнецов)
30 ноября и 7 декабря 2023 года. Введение в эпистемическую логику. (В.В.Долгоруков). Презентации: Эпистемическая логика, Доксатическая логика, Динамическая эпистемическая логика. Задачи.

Материалы 2023 года (весна)
2 и 9 марта 2023 года Модальные логики (А.А. Оноприенко)
16 марта 2023 года Исчисление секвенций: первое знакомство (Д.С.Шамканов)
23 и 30 марта 2023 года лямбда-исчисление (С.Л.Кузнецов)
6 и 13 апреля Релевантная логика (Константин Шишов)

Материалы 2022 года (осень)
6 октября 2022 года Теория множеств, эффективные алгоритмы на графах и математическая биология (В.А.Любецкий)
13 октября 2022 года Взвешивания и вопросы (А.А.Оноприенко)
20 и 27 октября 2022 года Деревья решений и вопросная сложность (Н.К.Верещагин)
3 ноября 2022 года. Формальные языки и где они обитают. (Максим Вишникин)
10 и 17 ноября 2022 года. Интуиционистская логика (А.А.Оноприенко)
24 ноября 2022 года. Формальные языки и где они обитают. Часть 2. (Максим Вишникин) Материалы
1 декабря 2022 года. Графы и монадическая логика первого порядка. (Тихон Пшеницын)
8 декабря 2022 года. Определимость. (А.Л.Семенов, С.Ф.Сопрунов) Задачи. Презентация.
15 декабря 2022 года. Графы и монадическая логика второго порядка. (Тихон Пшеницын)

Материалы 2021 года (осень)

1 и 8 октября 2021 года Модальные логики (А.А. Оноприенко)
15 октября 2021 года Булевы алгебры и теорема Стоуна (А. Запрягаев)
22 октября 2021 года Метазадачи (А. Шень)
29 октября 2021 года Многозначные логики (Ярослав Петрухин)
12 и 19 ноября 2021 года Конечные автоматы (Максим Вишникин)
26 ноября и 3 декабря 2021 года Контекстно-свободные грамматики (Тихон Пшеницын)
10 и 17 декабря Интуиционистская логика (В.Е. Плиско). Презентация от 10 декабря. Презентация от 17 декабря. Материалы.