[[Категория:Лекционные курсы кафедры МК]]
Страница курса по дискретной математике для студентов 1 курса 1 потока (общую информацию см. на странице [[Дискретная математика (1-й курс)]]).

Основной курс '''для студентов 1-го курса''', читается во '''2-м''' семестре. Лекции - '''3 ч''' в неделю, семинары - '''2 ч''' в неделю, отчетность - экзамен.

Лектор - [[Селезнева Светлана Николаевна]]

==Объявления==

Записи лекций Селезневой С.Н., прочитанных в 2021 г., можно найти по прямой ссылке [https://m.cs.msu.ru/s/6JnNMf5AXwYT7JF '''Записи лекций С.Н. Селезневой''']

Вопросы по содержанию курса (и другие вопросы, относящиеся к курсу) можно задавать лектору Селезневой Светлане Николаевне по эл. почте selezn@cs.msu.ru

==Экзамен==

'''Информация об экзамене в 2026 году'''

Экзамен устный. В билете три вопроса: вопросы 1 и 2 по теории, вопрос 3 - задача по одной из четырех тем: "Алгебра логики", "Графы", "Коды", "Конечные автоматы". Ответы на вопросы 1 и 2 почти без подготовки (подготовка в течение 5 мин). Если вопрос отмечен звездочкой *, то при ответе на него можно посмотреть (в течение 5 минут) бумажные источники (конспекты лекций, распечатки слайдов, учебники, др.). Важно: все определения и теоремы вопроса следует написать без источников (до того, как материалы будут открыты). При ответах на другие вопросы и при решении задачи из вопроса 3 не разрешается пользоваться никакими источниками.

После ответа на вопросы из билета - общий опрос по всему курсу, возможны задачи по всему курсу (вне зависимости от освобождения от задач). При этом общем вопросе не разрешается пользоваться никакими источниками.

Как учитываются итоги проверочных работ. Проверочные работы проводилась по темам "Алгебра логики" и "Графы". По каждой из тем можно было получить одну из трех оценок: или 0, или 0,5 или 1. Если у студента по теме оценка 1 и задача по этой теме в вопросе 3 в билете студента, то при ответе на билет студент освобождается от решения задачи из вопроса 3. Если у студента оценки 0 по обеим темам или студент не писал проверочные работы, то после общего опроса студент решает дополнительную задачу по одной из тем "Алгебра логики", "Графы" (на выбор экзаменатора).

'''Вопросы к экзамену'''

<ol>
<li> Функции алгебры логики. Существенность переменных. Суперпозиция. Тождества.
<li> Функции алгебры логики. Разложение функции алгебры логики по переменным.
<li> Дизъюнктивная нормальная форма (ДНФ). Выразимость функции алгебры логики совершенной ДНФ.
<li> Конъюнктивная нормальная форма (КНФ). Выразимость функции алгебры логики совершенной КНФ.
<li> Полином Жегалкина. Теорема Жегалкина о выразимости функции алгебры логики полиномом Жегалкина.
<li> *Полиномы Жегалкина. Вычисление коэффициентов полинома Жегалкина функции алгебры логики. Быстрый алгоритм построения полинома Жегалкина.
<li> Функции алгебры логики. Полные системы. Примеры полных систем (с доказательством полноты).
<li> Функции алгебры логики. Замыкание. Свойства замыкания. Замкнутый класс. Замкнутые классы функций, сохраняющих константу, и линейных функций.
<li> Функции алгебры логики. Двойственность. Самодвойственные функции. Замкнутый класс самодвойственных функций.
<li> Функции алгебры логики. Монотонные функции. Замкнутый класс монотонных функций.
<li> Функции алгебры логики. Самодвойственные функции. Лемма о несамодвойственной функции.
<li> Функции алгебры логики. Монотонные функции. Лемма о немонотонной функции.
<li> Функции алгебры логики. Линейные функции. Лемма о нелинейной функции.
<li> Функции алгебры логики. Полнота. Теорема Поста о полноте в алгебре логики.
<li> Функции алгебры логики. Базис. Теорема о числе функций в базисе алгебры логики.
<li> *Функции алгебры логики. Предполные классы. Замкнутость предполного класса. Теорема о предполных классах.
<li> Графы (псевдографы, мультиграфы, простые графы). Изоморфизм графов. Степень вершины, формула Эйлера для степеней вершин.
<li> Графы. Пути, цепи, простые цепи. Замкнутые пути, циклы, простые циклы. Свойства путей и циклов в графе.
<li> Графы. Связность. Два свойства связных графов. Компоненты связности графа. Теорема о соотношении между числом вершин, ребер и компонент связности в графе.
<li> Деревья. Теорема о равносильных определениях дерева.
<li> Деревья. Обход дерева в глубину из заданной вершины. Верхняя оценка числа неизоморфных деревьев с заданным числом ребер.
<li> Остовные деревья. Существование остовного дерева в связном графе: три алгоритма построения остовного дерева (с обоснованием).
<li> *Кратчайшие остовные деревья. Алгоритм построения кратчайшего остовного дерева в связном графе (с обоснованием).
<li> Геометрическое представление графов в n-мерном пространстве. Теорема о геометрическом представлении графов в трехмерном пространстве.
<li> Планарные графы. Укладка планарного графа на плоскости. Грань планарного графа при его укладке на плоскости. Формула Эйлера для планарных графов.
<li> Планарные графы. Свойства планарных графов (верхняя оценка числа ребер, существование вершины ограниченной степени).
<li> Планарные графы. Графы K5 и K3,3. Непланарность графов K5 и K3,3.
<li> Планарные графы. Гомеоморфизм графов. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
<li> Раскраски вершин графов. Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
<li> Раскраски вершин графов. Теорема о раскраске вершин планарных графов в 5 цветов.
<li> Кодирование, однозначность (разделимость) кодирования. Алфавитное кодирование, алфавитные коды. Однозначность (разделимость) алфавитного кода. Некоторые однозначные алфавитные коды (равномерные, префиксные, суффиксные).
<li> *Алфавитные коды. Граф однозначности алфавитного кода. Алгоритм Маркова распознавания однозначности алфавитного кода (с обоснованием).
<li> *Алфавитные коды. Теорема Маркова об алфавитных кодах.
<li> *Алфавитные коды. Неравенство Макмиллана.
<li> Алфавитные коды. Префиксные коды. Существование префиксного кода с заданными длинами кодовых слов.
<li> Коды с минимальной избыточностью (оптимальные коды). Три леммы о свойствах кодов с минимальной избыточностью.
<li> *Коды с минимальной избыточностью (оптимальные коды). Теорема редукции.
<li> Коды с минимальной избыточностью (оптимальные коды). Алгоритм Хаффмана построения кода с минимальной избыточностью.
<li> Равномерные двоичные коды. Ошибки замещения. Коды, обнаруживающие и исправляющие ошибки. Критерии кодов, обнаруживающих и исправляющих t ошибок.
<li> *Коды, исправляющие t ошибок. Оценки максимальной мощности кода, исправляющего t ошибок.
<li> Коды, исправляющие одну ошибку. Коды Хэмминга. Оценки мощности кода, исправляющего одну ошибку.
<li> Код Хэмминга. Алгоритмы кодирования, исправления ошибки и декодирования в коде Хэмминга.
<li> Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
<li> Конечные автоматы. Функционирование конечного автомата. Конечно-автоматные функции. Канонические уравнения и диаграмма Мура конечного автомата. Единичная задержка, ее конечно-автоматность.
<li> *Конечные автоматы. Отличимость состояний конечного автомата. Теорема Мура. Достижимость оценки теоремы Мура.
<li> Дискретные преобразователи без памяти. Схемы из функциональных элементов (СФЭ). Выразимость функции алгебры логики схемой из функциональных элементов в базисе из конъюнкции, дизъюнкции и отрицания.
<li> *Дискретные преобразователи с конечной памятью. Схемы из функциональных элементов и элементов задержки (СФЭЗ). Автоматность осуществляемых ими отображений.
<li> *Дискретные преобразователи с конечной памятью. Выразимость автоматной функции схемой из функциональных элементов и элементов задержки (при подходящем кодировании).
<li> Сумматор порядка n. Верхняя оценка сложности СФЭ n-разрядного сумматора.
<li> Вычитатель порядка n. Верхняя оценка сложности СФЭ n-разрядного вычитателя.
<li> Умножитель порядка n. Порядок сложности СФЭ n-разрядного умножителя по алгоритму «в столбик». Оценки сложности СФЭ умножения n-разрядного числа на степень двойки и на разряд и умножения (n+1)-разрядных чисел.
<li> *Метод Карацубы построения умножителя. Оценка сложности СФЭ умножения 2n-разрядных чисел. Верхняя оценка сложности СФЭ n-разрядного умножителя по методу Карацубы.
</ol>

'''Литература'''
<ol>
<li> Собственный конспект лекций.
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
<li> Алексеев В.Б. Дискретная математика. М.: Инфра-М, 2021.
<li> [[Media:Lectdm.doc|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс.
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2006.
</ol>

'''Задачи к экзамену'''

*Найти существенные и фиктивные переменные заданной функции алгебры логики.
*Найти совершенную ДНФ, совершенную КНФ или полином Жегалкина заданной функции алгебры логики.
*Подсчитать число функций алгебры логики, зависящих от n переменных, в заданном множестве.
*Исследовать на полноту заданной системы функций алгебры логики (конечной или бесконечной).
*Выяснить, является ли данная система функций алгебры логики базисом, или выделить из заданной системы функций алгебры логики все базисы.

*Найти число неизоморфных графов с заданными свойствами и изобразить эти графы.
*Найти код упорядоченного корневого дерева или восстановить упорядоченное корневое дерево по коду.
*Найти в заданном графе подграф, гомеоморфный графу K_5 или графу K_3,3.
*Выяснить, является ли заданный граф планарным.
*Выяснить, найдется ли планарный граф с заданными свойствами.
*Найти хроматическое число или хроматический индекс заданного графа.
*Исследовать разделимость заданного алфавитного кода (по алгоритму Маркова).
*Исследовать разделимость заданного алфавитного кода по неравенству Макмиллана или построить префиксный код с заданными длинами кодовых слов.
*Найти оптимальный алфавитный двоичный код по заданному набору частот.
*Установить, сколько ошибок замещения обнаруживает или исправляет заданный равномерный код.
*Кодировать или исправить ошибку и декодировать сообщение в коде Хэмминга.
*Найти кодовое расстояние заданного линейного кода.
*Найти диаграмму Мура автоматной функции, заданной описанием.
*Найти диаграмму Мура, каноническую таблицу, канонические уравнения или СФЭ с задержками автоматной функции, заданной одним из перечисленных способов.
*Построить диаграмму Мура, не содержащую недостижимых и неотличимых состояний, для заданной автоматной функции.

==Программа курса==

'''1. Алгебра логики'''. Функции алгебры логики, таблицы истинности. Существенность переменных. Суперпозиции, тождества, эквивалентные преобразования. Дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ). Полиномы Жегалкина. Полнота в алгебре логики. Замкнутые классы. Предполные классы.

'''2. Графы'''. Графы, простейшие свойства. Связность. Деревья, остовные деревья. Планарность графов. Раскраски графов.

'''3. Коды'''. Кодирование. Алфавитные коды, их свойства. Однозначность (разделимость) алфавитных кодов. Минимальная избыточность алфавитных кодов. Коды, обнаруживающие и исправляющие ошибки. Коды Хэмминга. Линейные коды.

'''4. Конечные автоматы'''. Конечные автоматы-преобразователи и конечно-автоматные функции. Представления конечных автоматов и конечно-автоматных функций. Упрощение конечных автоматов.

'''5. СФЭ'''. Схемы из функциональных элементов (СФЭ), представление функций алгебры логики ими. Сумматор, оценка его сложности в СФЭ. Вычитатель, оценка его сложности в СФЭ. Умножитель, оценка его сложности в СФЭ.


'''Литература'''
<ol>
<li> Конспекты лекций.
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
<li> Алексеев В.Б. Дискретная математика. М.: Инфра-М, 2021.
<li> [[Media:Lectdm.pdf|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс.
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2006.
</ol>

==Лекции==



1. '''Алгебра логики'''

Лекция 1. Функции алгебры логики. Таблицы истинности. Существенные и несущественные переменные. Суперпозиции. Тождества.

Лекция 2. Разложение функций по переменным. Дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ). Совершенная ДНФ и совершенная КНФ.

Лекция 3. Полиномы Жегалкина. Теорема Жегалкина. Построение полиномов Жегалкина.

Лекция 4. Полные системы, полнота некоторых систем. Замыкание множества. Замкнутые классы. Замкнутость классов T_0, T_1, L, S, M.

Лекция 5. Леммы о несамодвойственной, немонотонной и нелинейной функциях. Полнота. Теорема Поста о полноте.

Лекция 6. Базисы в P_2. Теорема о числе функций в базисе P_2. Предполные классы. Теорема о предполных классах в P_2.

2. '''Графы'''

Лекция 7. Графы. Простейшие свойства графов. Пути и цепи. Циклы и связность. Удаление и добавление ребер в связных графах. Соотношение между числом вершин, числом ребер и числом компонент связности в графе. Орграфы.

Лекция 8. Деревья. Теорема о равносильных определениях дерева. Корневые деревья. Упорядоченные корневые деревья. Оценка числа деревьев с q ребрами.

Лекция 9. Остовные деревья. Минимальные (кратчайшие) остовные деревья. Алгоритм построения минимального остовного дерева.

Лекция 10. Геометрическое представление графов. Планарные графы. Формула Эйлера для планарных графов. Критерий планарности Понтрягина-Куратовского.

Лекция 11. Раскраски графов. Раскраски графов в два цвета. Раскраски планарных графов.

3. '''Коды'''

Лекция 12. Кодирование. Алфавитные коды. Теорема об однозначности равномерного кода. Теорема об однозначности префиксного кода. Алгоритм Маркова для распознавания однозначности алфавитного кода. Теорема Маркова.

Лекция 13. Алфавитные коды. Неравенство Макмиллана. Теорема о существовании префиксного кода с заданными длинами кодовых слов. Дерево префиксного кода.

Лекция 14. Алфавитные коды. Коды с минимальной избыточностью (оптимальные коды). Свойства кодов с минимальной избыточностью. Теорема редукции. Алгоритм Хаффмена построения кода с минимальной избыточностью.

Лекция 15. Коды, обнаруживающие и исправляющие ошибки, их свойства. Мощность кода, исправляющего ошибки. Линейные коды и их свойства.

Лекция 16. Коды, исправляющие одну ошибку. Коды Хэмминга и их свойства. Алгоритмы кодирования, исправления ошибки и декодирования в коде Хэмминга. Мощность кода, исправляющего одну ошибку.

4. '''Автоматы'''

Лекция 17. Конечные автоматы. Способы их представления. Схемы из функциональных элементов с задержками (СФЭЗ) и представление конечных автоматов ими.

Лекция 18. Конечные автоматы. Отличимость состояний конечного автомата. Оценка длины слова, отличающего два отличимых состояния конечного автомата. Упрощение автоматов.

5. '''СФЭ'''

Лекция 19. Схемы из функциональных элементов (СФЭ). Представление функций алгебры логики СФЭ. Схемы для сложения и вычитания, их сложность.

Лекция 20. Схема для умножения. Сложность схемы для умножения по методу Карацубы.


==Семинары==

[[Media: dm1-seminars.pdf | План семинарских занятий]]

[[Media: dm1-seminars-d.pdf | Дополнительные задачи к семинарским занятиям]]

==Записи лекций==

Записи лекций Селезневой С.Н., прочитанных в 2021 г., можно найти по прямой ссылке [https://m.cs.msu.ru/s/6JnNMf5AXwYT7JF '''Записи лекций С.Н. Селезневой''']

Файл:Mvk-26-06-05.pdf

2026-05-31T11:04:39Z

SeleznevaSN: SeleznevaSN загружена новая версия «Файл:Mvk-26-06-05.pdf»

2026-04-21T12:02:33Z

SeleznevaSN: SeleznevaSN загружена новая версия «Файл:Mvk-26-04-24.pdf»

Файл:Mvk-26-04-24.pdf

2026-04-21T10:42:12Z

SeleznevaSN:

Математические вопросы кибернетики

2026-04-21T10:41:45Z

SeleznevaSN: /* 2025-2026 учебный год */

[[Mathematical Problems of Cybernetics]]

Научно-исследовательский семинар кафедр [http://new.math.msu.su/department/dm/ '''дискретной математики'''] и [http://intsys.msu.ru/ '''математической теории интеллектуальных систем'''] механико-математического факультета и [https://mk.cs.msu.ru/index.php/Заглавная_страница '''математической кибернетики'''] факультета вычислительной математики и кибернетики МГУ имени М.В. Ломоносова.

'''Цель семинара''': обсуждение современных задач математической кибернетики и широкого круга смежных вопросов и представление наиболее значимых результатов в этой области.

'''Традиции семинара''': семинар продолжает научно-исследовательский семинар по математическим вопросам кибернетики, который более 30 лет проводился в Московском университете под руководством [https://mk.cs.msu.ru/index.php/Яблонский_Сергей_Всеволодович '''Сергея Всеволодовича Яблонского'''] и [http://new.math.msu.su/obl '''Олега Борисовича Лупанова'''].

==2025-2026 учебный год==

В '''2025-2026 учебном году''' семинар проводится удаленно '''по пятницам''' в '''19-00''' (по московскому времени) по объявлениям.

Заседания проводятся на платформе zoom, идентификатор конференции: 830 6246 3909, код доступа: 947173.

По вопросам, связанным с работой семинара, можно писать по эл. почте '''mvk@cs.msu.ru''' Селезневой Светлане Николаевне.

'''Расписание докладов'''

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 24 апреля 2026 г.
| '''Сложность задачи о существовании сюръективного гомоморфизма на цикл.''' [[Media: mvk-26-04-24.pdf | Аннотация доклада]]
|'''Корчагин Никита Павлович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 20 февраля 2026 г.
| '''О сложности укладок схем из функциональных элементов на графах.''' [[Media: mvk-26-02-20.pdf | Аннотация доклада]]
|'''Калачев Глеб Вячеславович, Ефимов Алексей Андреевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 26 декабря 2025 г.
| '''Семинар, посвященный 90-летию со дня рождения Н.А. Карповой.'''
|'''Кочергин Вадим Васильевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 19 сентября 2025 г.
| '''О свойствах конечно порождающих систем булевых функций для классов рациональных вероятностей'''. [[Media: mvk-25-09-19.pdf | Аннотация доклада]]
|'''Трифонова Екатерина Евгеньевна''' (Москва, ИМП им. М.В. Келдыша)
|-
|}

==2024-2025 учебный год==

'''Расписание докладов'''

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 23 мая 2025 г.
| '''Метод граничных функционалов и нижние оценки числа антицепей в некоторых ранжированных ЧУМ'''. [[Media: mvk-25-05-23.pdf | Аннотация доклада]]
|'''Андреева Татьяна Владимировна''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 25 апреля 2025 г.
| '''Асимптотически точные оценки сложности некоторых функций и систем функций в модели клеточных схем'''. [[Media: mvk-25-04-25.pdf | Аннотация доклада]]
|'''Зизов Вадим Сергеевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 14 марта 2025 г.
| '''О некоторых свойствах конечных квазигрупп'''. [[Media: mvk-25-03-14.pdf | Аннотация доклада]]
|'''Галатенко Алексей Владимирович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 28 февраля 2025 г.
| '''Семинар памяти Л.А. Шоломова'''.
|'''Чашкин Александр Викторович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 25 октября 2024 г.
| '''Нижние оценки сложности линейных операторов над GF(2)'''. [[Media: mvk-24-10-25.pdf | Аннотация доклада]]
|'''Сергеев Игорь Сергеевич''' (Москва, Научно-исследовательский институт «Квант»)
|-
|}

==2023-2024 учебный год==

'''Расписание докладов'''

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 17 мая 2024 г.
| '''Оценки длин минимальных тестов для аргументов функций при подстановке констант, алгебраических операциях и сдвигах'''. [[Media: mvk-24-05-17.pdf | Аннотация доклада]]
|'''Антюфеев Григорий Валерьевич''' (Москва, «НИИМА «ПРОГРЕСС»»)
|-
| 5 апреля 2024 г.
| '''Семинар, посвященный 85-летию проф. А.А. Сапоженко'''. [[Media: mvk-24-04-05.pdf | Аннотация доклада]]
|
|-
| 22 марта 2024 г.
| '''Многомерные матрицы в алгебраической теории гиперграфов'''. [[Media: mvk-24-03-22.pdf | Аннотация доклада]]
| '''Тараненко Анна Александровна''' (Новосибирск, Институт математики имени С.Л. Cоболева СО РАН)
|-
| 15 марта 2024 г.
| '''Симметричные функции k-значной логики и универсальные алгоритмы для задачи удовлетворения ограничений'''. [[Media: mvk-24-03-15.pdf | Аннотация доклада]]
| '''Жук Дмитрий Николаевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 15 декабря 2023 г.
| '''Коммутаторная длина степеней в свободных произведениях групп'''. [[Media: mvk-23-12-15.pdf | Аннотация доклада]]
| '''Березнюк Вадим Юрьевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 8 декабря 2023 г.
| '''Реализация вероятностных автоматов на однородных вычислительных системах при использовании арифметики полей Галуа'''. [[Media: mvk-23-12-08.pdf | Аннотация доклада]]
| '''Шалагин Сергей Викторович''' (Казань, Казанский национальный исследовательский технический университет им. А.Н.Туполева – КАИ)
|-
| 1 декабря 2023 г.
| '''О сложности и структуре некоторых типов контактных схем для ряда симметрических булевых функций'''. [[Media: mvk-23-12-01.pdf | Аннотация доклада]]
| '''Попов Евгений Александрович''' (Москва, фирма Примариус)
|-
| 17 ноября 2023 г.
| '''Правильные семейства дискретных функций: эквивалентные определения и свойства'''. [[Media: mvk-23-11-17.pdf | Аннотация доклада]]
| '''Царегородцев Кирилл Денисович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 6 октября 2023 г.
| '''Компьютерное моделирование логических процессов'''. [[Media: mvk-23-10-06.pdf | Аннотация доклада]]
| '''Подколзин Александр Сергеевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
|}

==2022-2023 учебный год==

'''Расписание докладов'''

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 19 мая 2023 г.
| '''Конструкции и свойства корреляционно-иммунных и платовидных булевых функций'''. [[Media: mvk-23-05-19.pdf | Аннотация доклада]]
| '''Таранников Юрий Валерьевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 12 мая 2023 г.
| '''О соотношениях между активностью схем из функциональных элементов и положительной чувствительностью функций алгебры логики'''. [[Media: mvk-23-05-12.pdf | Аннотация доклада]]
| '''Местецкий Михаил Александрович''', '''Шуплецов Михаил Сергеевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 28 апреля 2023 г.
| '''Семинар, посвященный 70-летию со дня рождения О. М. Касим-Заде'''. [[Media: mvk-23-04-28.pdf | Аннотация]]
|
|-
| 21 апреля 2023 г.
| '''Дихотомия сложности кванторной задачи удовлетворения ограничениям'''. [[Media: mvk-23-04-21.pdf | Аннотация доклада]]
| '''Жук Дмитрий Николаевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 31 марта 2023 г.
| '''О числе субпериодичностей в двоичных формальных словах'''. [[Media: mvk-23-03-31.pdf | Аннотация доклада]]
| '''Колпаков Роман Максимович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 17 марта 2023 г.
| '''Некоторые свойства сложностных классов AC^0 и TC^0'''. [[Media: mvk-23-03-17.pdf | Аннотация доклада]]
| '''Савицкий Игорь Владимирович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 3 марта 2023 г.
| '''Оценки энергопотребления объемных схем'''. [[Media: mvk-23-03-03.pdf | Аннотация доклада]]
| '''Ефимов Алексей Андреевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 17 февраля 2023 г.
| '''Об асимптотике роста мощности слоев в декартовых степенях некоторых взвешенных множеств'''. [[Media: mvk-23-02-17.pdf | Аннотация доклада]]
| '''Андреева Татьяна Владимировна''' (Москва, МГТУ имени Н.Э. Баумана; МГУ имени М.В. Ломоносова), '''Семенов Юрий Станиславович'''
|-
| 16 декабря 2022 г.
| '''Памяти Валерия Борисовича Кудряцева'''. [[Media: mvk-22-12-16.pdf | Аннотация доклада]]
| '''Гасанов Э.Э., Алешин С.В., Часовских А.А., Сыркин Г.И.'''
|-
| 9 декабря 2022 г.
| '''Тензорные сети для эффективной симуляции квантовых вычислений'''. [[Media: mvk-22-12-09.pdf | Аннотация доклада]]
| '''Пантелеев Павел Анатольевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 11 ноября 2022 г.
| '''Цифровая подпись на основе кодов, определяющих изображения с точностью до аффинных преобразований'''. [[Media: mvk-22-11-11.pdf | Аннотация доклада]]
| '''Козлов Вадим Никитович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 28 октября 2022 г.
| '''О математических моделях и структурных графах в теории механизмов'''. [[Media: mvk-22-10-28.pdf | Аннотация доклада]]
| '''Ковалев Михаил Дмитриевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 21 октября 2022 г.
| '''О перманентах (0, 1)- и (-1,1)-матриц'''. [[Media: mvk-22-10-21.pdf | Аннотация доклада]]
| '''Таранин Константин Александрович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 14 октября 2022 г.
| '''Параметро-эффективная расшифровка булевых функций'''. [[Media: mvk-22-10-14.pdf | Аннотация доклада]]
| '''Быстрыгова Анастасия Викторовна''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 7 октября 2022 г.
| '''Задачи Беллмана, Кнута, Лупанова, Пиппенджера и их вариации как обобщения задачи об аддитивных цепочках'''. [[Media: mvk-22-10-07.pdf | Аннотация доклада]]
| '''Кочергин Вадим Васильевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 30 сентября 2022 г.
| '''Асимптотически точные оценки сложности некоторых функций в модели клеточных схем'''. [[Media: mvk-22-09-30.pdf | Аннотация доклада]]
| '''Ложкин Сергей Андреевич, Зизов Вадим Сергеевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
|}

==2021-2022 учебный год==

'''Расписание докладов'''

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 29 апреля 2022 г.
| '''Размерность Вейсфейлера-Лемана алгебраических и комбинаторных структур'''. [[Media: mvk-22-04-29.pdf | Аннотация доклада]]
| '''Пономаренко Илья Николаевич''' (Санкт-Петербург, Санкт-Петербургское отделение Математического института им. В.А.Стеклова Российской академии наук)
|-
| 22 апреля 2022 г.
| '''О некоторых приложениях теории сложности алгоритмов к прикладным задачам криптографии'''. [[Media: mvk-22-04-22.pdf | Аннотация доклада]]
| '''Смышляев Станислав Витальевич''' (Москва, ООО «КРИПТО-ПРО», Технический комитет по стандартизации «Криптографическая защита информации» (ТК 26))
|-
| 15 апреля 2022 г.
| '''Мультиоперации на конечных множествах'''. [[Media: mvk-22-04-15.pdf | Аннотация доклада]]
| '''Перязев Николай Алексеевич''' (Санкт-Петербург, СПбГЭТУ «ЛЭТИ»)
|-
| 8 апреля 2022 г.
| '''Темпы роста произвольных конечных структур'''. [[Media: mvk-22-04-08.pdf | Аннотация доклада]]
| '''Комков Степан Алексеевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 1 апреля 2022 г.
| '''Квантовое хеширование: основные свойства, эффективные конструкции, реализация'''. [[Media: mvk-22-04-01.pdf | Аннотация доклада]]
| '''Аблаев Фарид Мансурович, Аблаев Марат Фаридович''' (Казань, Казанский (Приволжский) федеральный университет)
|-
| 25 марта 2022 г.
| '''Асимптотически хорошие семейства классических и квантовых LDPC кодов'''. [[Media: mvk-22-03-25.pdf | Аннотация доклада]]
| '''Пантелеев Павел Анатольевич, Калачев Глеб Вячеславович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 18 марта 2022 г.
| '''Предикаты k-значной логики и задача удовлетворения ограничениям'''. [[Media: mvk-22-03-18.pdf | Аннотация доклада]]
| '''Жук Дмитрий Николаевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 11 марта 2022 г.
| '''Аддитивные представления и замкнутые классы функций многозначной логики'''. [[Media: mvk-22-03-11.pdf | Аннотация доклада]]
| '''Мещанинов Дмитрий Германович''' (Москва, НИУ «МЭИ»)
|-
| 25 февраля 2022 г.
| '''Удивительный жадный алгоритм'''. [[Media: mvk-22-02-25.pdf | Аннотация доклада]]
| '''Куликов Александр Сергеевич''' (Санкт-Петербург, Санкт-Петербургский государственный университет)
|-
| 18 февраля 2022 г.
| '''Линейное хеширование'''. [[Media: mvk-22-02-18.pdf | Аннотация доклада]]
| '''Чашкин Александр Викторович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 17 декабря 2021 г.
| '''Семинар памяти О.М. Касим-Заде (29.04.1953-22.12.2020)'''. [[Media: mvk-21-12-17.pdf | Аннотация доклада]]
| '''Кочергин Вадим Васильевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 10 декабря 2021 г.
| '''Семинар, посвященный 70-летию со дня рождения проф. А.Б. Угольникова'''. [[Media: mvk-21-12-10.pdf | Аннотация доклада]]
| '''Колпаков Роман Максимович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 3 декабря 2021 г.
| '''Синтез и сложность бинарных программ с некоторыми структурными ограничениями'''. [[Media: mvk-21-12-03.pdf | Аннотация доклада]]
| '''Жуков Владимир Владимирович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 26 ноября 2021 г.
| '''Об исследовании вопросов полноты в классе линейных автоматов над подкольцами рациональных чисел'''. [[Media: mvk-21-11-26.pdf | Аннотация доклада]]
| '''Ронжин Дмитрий Владимирович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 19 ноября 2021 г.
| '''Булевы биюнктивные функции и порождаемые ими системы булевых уравнений'''. [[Media: mvk-21-11-19.pdf | Аннотация доклада]]
| '''Тарасов Алексей Вячеславович''' (Москва, Федеральное учебно-методическое объединение ВУЗов в области информационной безопасности (ФУМО ВО ИБ))
|-
| 12 ноября 2021 г.
| '''Математические модели передачи информации через зашумленные скрытые каналы'''. [[Media: mvk-21-11-12.pdf | Аннотация доклада]]
| '''Казаков Илья Борисович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 29 октября 2021 г.
| '''Асимптотика логарифма числа наборов, k-свободных от решений, в абелевых группах'''. [[Media: mvk-21-10-29.pdf | Аннотация доклада]]
| '''Саргсян Ваге Гнелович''' (Ереван, Институт проблем информатики и автоматизации Национальной Академии Наук Республики Армения)
|-
| 22 октября 2021 г.
| '''Задачи дискретной оптимизации в спорте'''. [[Media: mvk-21-10-22.pdf | Аннотация доклада]]
| '''Дагаев Дмитрий Александрович''' (Москва, НИУ ВШЭ)
|-
| 8 октября 2021 г.
| '''О сложности реализации систем одночленов схемами композиции'''. [[Media: mvk-21-10-08.pdf | Аннотация доклада]]
| '''Корнеев Сергей Александрович''' (Москва, МГУ имени М.В. Ломоносова, ИПМ им. М.В. Келдыша РАН)
|-
|}

==2020-2021 учебный год==

'''Расписание докладов'''

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 28 мая 2021 г.
| '''Пороговые функции и пороговые схемы'''. [[Media: mvk-21-05-28.pdf | Аннотация доклада]]
| '''Подольский Владимир Владимирович''' (Москва, МИАН им. В.А.Стеклова)
|-
| 21 мая 2021 г.
| '''Регистровые машины со счетчиками'''. [[Media: mvk-21-05-21.pdf | Аннотация доклада]]
| '''Савицкий Игорь Владимирович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 14 мая 2021 г.
| '''Арифметика фибоначчиевых кодов. Асимптотически быстрая сортировка. Метод Храпченко для k-местных базисов'''. [[Media: mvk-21-05-14.pdf | Аннотация доклада]]
| '''Сергеев Игорь Сергеевич''' (Москва, ФГУП «НИИ "Квант"»)
|-
| 30 апреля 2021 г.
| '''Полнота и выразимость в классах линейных автоматов'''. [[Media: mvk-21-04-30.pdf | Аннотация доклада]]
| '''Часовских Анатолий Александрович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 16 апреля 2021 г.
| '''Преобразования конечных случайных величин системами функций k-значной логики и вопросы аппроксимируемости'''. [[Media: mvk-21-04-16.pdf | Аннотация доклада]]
| '''Яшунский Алексей Дмитриевич''' (Москва, Институт прикладной математики им. М.В. Келдыша РАН)
|-
|}

Файл:Mvk-26-02-20.pdf

2026-02-17T17:38:03Z

SeleznevaSN:

Математические вопросы кибернетики

2026-02-17T17:27:11Z

SeleznevaSN: /* 2025-2026 учебный год */

[[Mathematical Problems of Cybernetics]]

Научно-исследовательский семинар кафедр [http://new.math.msu.su/department/dm/ '''дискретной математики'''] и [http://intsys.msu.ru/ '''математической теории интеллектуальных систем'''] механико-математического факультета и [https://mk.cs.msu.ru/index.php/Заглавная_страница '''математической кибернетики'''] факультета вычислительной математики и кибернетики МГУ имени М.В. Ломоносова.

'''Цель семинара''': обсуждение современных задач математической кибернетики и широкого круга смежных вопросов и представление наиболее значимых результатов в этой области.

'''Традиции семинара''': семинар продолжает научно-исследовательский семинар по математическим вопросам кибернетики, который более 30 лет проводился в Московском университете под руководством [https://mk.cs.msu.ru/index.php/Яблонский_Сергей_Всеволодович '''Сергея Всеволодовича Яблонского'''] и [http://new.math.msu.su/obl '''Олега Борисовича Лупанова'''].

==2025-2026 учебный год==

В '''2025-2026 учебном году''' семинар проводится удаленно '''по пятницам''' в '''19-00''' (по московскому времени) по объявлениям.

Заседания проводятся на платформе zoom, идентификатор конференции: 830 6246 3909, код доступа: 947173.

По вопросам, связанным с работой семинара, можно писать по эл. почте '''mvk@cs.msu.ru''' Селезневой Светлане Николаевне.

'''Расписание докладов'''

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 20 февраля 2026 г.
| '''О сложности укладок схем из функциональных элементов на графах.''' [[Media: mvk-26-02-20.pdf | Аннотация доклада]]
|'''Калачев Глеб Вячеславович, Ефимов Алексей Андреевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 26 декабря 2025 г.
| '''Семинар, посвященный 90-летию со дня рождения Н.А. Карповой.'''
|'''Кочергин Вадим Васильевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 19 сентября 2025 г.
| '''О свойствах конечно порождающих систем булевых функций для классов рациональных вероятностей'''. [[Media: mvk-25-09-19.pdf | Аннотация доклада]]
|'''Трифонова Екатерина Евгеньевна''' (Москва, ИМП им. М.В. Келдыша)
|-
|}

==2024-2025 учебный год==

'''Расписание докладов'''

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 23 мая 2025 г.
| '''Метод граничных функционалов и нижние оценки числа антицепей в некоторых ранжированных ЧУМ'''. [[Media: mvk-25-05-23.pdf | Аннотация доклада]]
|'''Андреева Татьяна Владимировна''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 25 апреля 2025 г.
| '''Асимптотически точные оценки сложности некоторых функций и систем функций в модели клеточных схем'''. [[Media: mvk-25-04-25.pdf | Аннотация доклада]]
|'''Зизов Вадим Сергеевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 14 марта 2025 г.
| '''О некоторых свойствах конечных квазигрупп'''. [[Media: mvk-25-03-14.pdf | Аннотация доклада]]
|'''Галатенко Алексей Владимирович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 28 февраля 2025 г.
| '''Семинар памяти Л.А. Шоломова'''.
|'''Чашкин Александр Викторович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 25 октября 2024 г.
| '''Нижние оценки сложности линейных операторов над GF(2)'''. [[Media: mvk-24-10-25.pdf | Аннотация доклада]]
|'''Сергеев Игорь Сергеевич''' (Москва, Научно-исследовательский институт «Квант»)
|-
|}

==2023-2024 учебный год==

'''Расписание докладов'''

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 17 мая 2024 г.
| '''Оценки длин минимальных тестов для аргументов функций при подстановке констант, алгебраических операциях и сдвигах'''. [[Media: mvk-24-05-17.pdf | Аннотация доклада]]
|'''Антюфеев Григорий Валерьевич''' (Москва, «НИИМА «ПРОГРЕСС»»)
|-
| 5 апреля 2024 г.
| '''Семинар, посвященный 85-летию проф. А.А. Сапоженко'''. [[Media: mvk-24-04-05.pdf | Аннотация доклада]]
|
|-
| 22 марта 2024 г.
| '''Многомерные матрицы в алгебраической теории гиперграфов'''. [[Media: mvk-24-03-22.pdf | Аннотация доклада]]
| '''Тараненко Анна Александровна''' (Новосибирск, Институт математики имени С.Л. Cоболева СО РАН)
|-
| 15 марта 2024 г.
| '''Симметричные функции k-значной логики и универсальные алгоритмы для задачи удовлетворения ограничений'''. [[Media: mvk-24-03-15.pdf | Аннотация доклада]]
| '''Жук Дмитрий Николаевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 15 декабря 2023 г.
| '''Коммутаторная длина степеней в свободных произведениях групп'''. [[Media: mvk-23-12-15.pdf | Аннотация доклада]]
| '''Березнюк Вадим Юрьевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 8 декабря 2023 г.
| '''Реализация вероятностных автоматов на однородных вычислительных системах при использовании арифметики полей Галуа'''. [[Media: mvk-23-12-08.pdf | Аннотация доклада]]
| '''Шалагин Сергей Викторович''' (Казань, Казанский национальный исследовательский технический университет им. А.Н.Туполева – КАИ)
|-
| 1 декабря 2023 г.
| '''О сложности и структуре некоторых типов контактных схем для ряда симметрических булевых функций'''. [[Media: mvk-23-12-01.pdf | Аннотация доклада]]
| '''Попов Евгений Александрович''' (Москва, фирма Примариус)
|-
| 17 ноября 2023 г.
| '''Правильные семейства дискретных функций: эквивалентные определения и свойства'''. [[Media: mvk-23-11-17.pdf | Аннотация доклада]]
| '''Царегородцев Кирилл Денисович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 6 октября 2023 г.
| '''Компьютерное моделирование логических процессов'''. [[Media: mvk-23-10-06.pdf | Аннотация доклада]]
| '''Подколзин Александр Сергеевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
|}

==2022-2023 учебный год==

'''Расписание докладов'''

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 19 мая 2023 г.
| '''Конструкции и свойства корреляционно-иммунных и платовидных булевых функций'''. [[Media: mvk-23-05-19.pdf | Аннотация доклада]]
| '''Таранников Юрий Валерьевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 12 мая 2023 г.
| '''О соотношениях между активностью схем из функциональных элементов и положительной чувствительностью функций алгебры логики'''. [[Media: mvk-23-05-12.pdf | Аннотация доклада]]
| '''Местецкий Михаил Александрович''', '''Шуплецов Михаил Сергеевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 28 апреля 2023 г.
| '''Семинар, посвященный 70-летию со дня рождения О. М. Касим-Заде'''. [[Media: mvk-23-04-28.pdf | Аннотация]]
|
|-
| 21 апреля 2023 г.
| '''Дихотомия сложности кванторной задачи удовлетворения ограничениям'''. [[Media: mvk-23-04-21.pdf | Аннотация доклада]]
| '''Жук Дмитрий Николаевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 31 марта 2023 г.
| '''О числе субпериодичностей в двоичных формальных словах'''. [[Media: mvk-23-03-31.pdf | Аннотация доклада]]
| '''Колпаков Роман Максимович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 17 марта 2023 г.
| '''Некоторые свойства сложностных классов AC^0 и TC^0'''. [[Media: mvk-23-03-17.pdf | Аннотация доклада]]
| '''Савицкий Игорь Владимирович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 3 марта 2023 г.
| '''Оценки энергопотребления объемных схем'''. [[Media: mvk-23-03-03.pdf | Аннотация доклада]]
| '''Ефимов Алексей Андреевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 17 февраля 2023 г.
| '''Об асимптотике роста мощности слоев в декартовых степенях некоторых взвешенных множеств'''. [[Media: mvk-23-02-17.pdf | Аннотация доклада]]
| '''Андреева Татьяна Владимировна''' (Москва, МГТУ имени Н.Э. Баумана; МГУ имени М.В. Ломоносова), '''Семенов Юрий Станиславович'''
|-
| 16 декабря 2022 г.
| '''Памяти Валерия Борисовича Кудряцева'''. [[Media: mvk-22-12-16.pdf | Аннотация доклада]]
| '''Гасанов Э.Э., Алешин С.В., Часовских А.А., Сыркин Г.И.'''
|-
| 9 декабря 2022 г.
| '''Тензорные сети для эффективной симуляции квантовых вычислений'''. [[Media: mvk-22-12-09.pdf | Аннотация доклада]]
| '''Пантелеев Павел Анатольевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 11 ноября 2022 г.
| '''Цифровая подпись на основе кодов, определяющих изображения с точностью до аффинных преобразований'''. [[Media: mvk-22-11-11.pdf | Аннотация доклада]]
| '''Козлов Вадим Никитович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 28 октября 2022 г.
| '''О математических моделях и структурных графах в теории механизмов'''. [[Media: mvk-22-10-28.pdf | Аннотация доклада]]
| '''Ковалев Михаил Дмитриевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 21 октября 2022 г.
| '''О перманентах (0, 1)- и (-1,1)-матриц'''. [[Media: mvk-22-10-21.pdf | Аннотация доклада]]
| '''Таранин Константин Александрович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 14 октября 2022 г.
| '''Параметро-эффективная расшифровка булевых функций'''. [[Media: mvk-22-10-14.pdf | Аннотация доклада]]
| '''Быстрыгова Анастасия Викторовна''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 7 октября 2022 г.
| '''Задачи Беллмана, Кнута, Лупанова, Пиппенджера и их вариации как обобщения задачи об аддитивных цепочках'''. [[Media: mvk-22-10-07.pdf | Аннотация доклада]]
| '''Кочергин Вадим Васильевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 30 сентября 2022 г.
| '''Асимптотически точные оценки сложности некоторых функций в модели клеточных схем'''. [[Media: mvk-22-09-30.pdf | Аннотация доклада]]
| '''Ложкин Сергей Андреевич, Зизов Вадим Сергеевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
|}

==2021-2022 учебный год==

'''Расписание докладов'''

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 29 апреля 2022 г.
| '''Размерность Вейсфейлера-Лемана алгебраических и комбинаторных структур'''. [[Media: mvk-22-04-29.pdf | Аннотация доклада]]
| '''Пономаренко Илья Николаевич''' (Санкт-Петербург, Санкт-Петербургское отделение Математического института им. В.А.Стеклова Российской академии наук)
|-
| 22 апреля 2022 г.
| '''О некоторых приложениях теории сложности алгоритмов к прикладным задачам криптографии'''. [[Media: mvk-22-04-22.pdf | Аннотация доклада]]
| '''Смышляев Станислав Витальевич''' (Москва, ООО «КРИПТО-ПРО», Технический комитет по стандартизации «Криптографическая защита информации» (ТК 26))
|-
| 15 апреля 2022 г.
| '''Мультиоперации на конечных множествах'''. [[Media: mvk-22-04-15.pdf | Аннотация доклада]]
| '''Перязев Николай Алексеевич''' (Санкт-Петербург, СПбГЭТУ «ЛЭТИ»)
|-
| 8 апреля 2022 г.
| '''Темпы роста произвольных конечных структур'''. [[Media: mvk-22-04-08.pdf | Аннотация доклада]]
| '''Комков Степан Алексеевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 1 апреля 2022 г.
| '''Квантовое хеширование: основные свойства, эффективные конструкции, реализация'''. [[Media: mvk-22-04-01.pdf | Аннотация доклада]]
| '''Аблаев Фарид Мансурович, Аблаев Марат Фаридович''' (Казань, Казанский (Приволжский) федеральный университет)
|-
| 25 марта 2022 г.
| '''Асимптотически хорошие семейства классических и квантовых LDPC кодов'''. [[Media: mvk-22-03-25.pdf | Аннотация доклада]]
| '''Пантелеев Павел Анатольевич, Калачев Глеб Вячеславович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 18 марта 2022 г.
| '''Предикаты k-значной логики и задача удовлетворения ограничениям'''. [[Media: mvk-22-03-18.pdf | Аннотация доклада]]
| '''Жук Дмитрий Николаевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 11 марта 2022 г.
| '''Аддитивные представления и замкнутые классы функций многозначной логики'''. [[Media: mvk-22-03-11.pdf | Аннотация доклада]]
| '''Мещанинов Дмитрий Германович''' (Москва, НИУ «МЭИ»)
|-
| 25 февраля 2022 г.
| '''Удивительный жадный алгоритм'''. [[Media: mvk-22-02-25.pdf | Аннотация доклада]]
| '''Куликов Александр Сергеевич''' (Санкт-Петербург, Санкт-Петербургский государственный университет)
|-
| 18 февраля 2022 г.
| '''Линейное хеширование'''. [[Media: mvk-22-02-18.pdf | Аннотация доклада]]
| '''Чашкин Александр Викторович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 17 декабря 2021 г.
| '''Семинар памяти О.М. Касим-Заде (29.04.1953-22.12.2020)'''. [[Media: mvk-21-12-17.pdf | Аннотация доклада]]
| '''Кочергин Вадим Васильевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 10 декабря 2021 г.
| '''Семинар, посвященный 70-летию со дня рождения проф. А.Б. Угольникова'''. [[Media: mvk-21-12-10.pdf | Аннотация доклада]]
| '''Колпаков Роман Максимович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 3 декабря 2021 г.
| '''Синтез и сложность бинарных программ с некоторыми структурными ограничениями'''. [[Media: mvk-21-12-03.pdf | Аннотация доклада]]
| '''Жуков Владимир Владимирович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 26 ноября 2021 г.
| '''Об исследовании вопросов полноты в классе линейных автоматов над подкольцами рациональных чисел'''. [[Media: mvk-21-11-26.pdf | Аннотация доклада]]
| '''Ронжин Дмитрий Владимирович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 19 ноября 2021 г.
| '''Булевы биюнктивные функции и порождаемые ими системы булевых уравнений'''. [[Media: mvk-21-11-19.pdf | Аннотация доклада]]
| '''Тарасов Алексей Вячеславович''' (Москва, Федеральное учебно-методическое объединение ВУЗов в области информационной безопасности (ФУМО ВО ИБ))
|-
| 12 ноября 2021 г.
| '''Математические модели передачи информации через зашумленные скрытые каналы'''. [[Media: mvk-21-11-12.pdf | Аннотация доклада]]
| '''Казаков Илья Борисович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 29 октября 2021 г.
| '''Асимптотика логарифма числа наборов, k-свободных от решений, в абелевых группах'''. [[Media: mvk-21-10-29.pdf | Аннотация доклада]]
| '''Саргсян Ваге Гнелович''' (Ереван, Институт проблем информатики и автоматизации Национальной Академии Наук Республики Армения)
|-
| 22 октября 2021 г.
| '''Задачи дискретной оптимизации в спорте'''. [[Media: mvk-21-10-22.pdf | Аннотация доклада]]
| '''Дагаев Дмитрий Александрович''' (Москва, НИУ ВШЭ)
|-
| 8 октября 2021 г.
| '''О сложности реализации систем одночленов схемами композиции'''. [[Media: mvk-21-10-08.pdf | Аннотация доклада]]
| '''Корнеев Сергей Александрович''' (Москва, МГУ имени М.В. Ломоносова, ИПМ им. М.В. Келдыша РАН)
|-
|}

==2020-2021 учебный год==

'''Расписание докладов'''

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 28 мая 2021 г.
| '''Пороговые функции и пороговые схемы'''. [[Media: mvk-21-05-28.pdf | Аннотация доклада]]
| '''Подольский Владимир Владимирович''' (Москва, МИАН им. В.А.Стеклова)
|-
| 21 мая 2021 г.
| '''Регистровые машины со счетчиками'''. [[Media: mvk-21-05-21.pdf | Аннотация доклада]]
| '''Савицкий Игорь Владимирович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 14 мая 2021 г.
| '''Арифметика фибоначчиевых кодов. Асимптотически быстрая сортировка. Метод Храпченко для k-местных базисов'''. [[Media: mvk-21-05-14.pdf | Аннотация доклада]]
| '''Сергеев Игорь Сергеевич''' (Москва, ФГУП «НИИ "Квант"»)
|-
| 30 апреля 2021 г.
| '''Полнота и выразимость в классах линейных автоматов'''. [[Media: mvk-21-04-30.pdf | Аннотация доклада]]
| '''Часовских Анатолий Александрович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 16 апреля 2021 г.
| '''Преобразования конечных случайных величин системами функций k-значной логики и вопросы аппроксимируемости'''. [[Media: mvk-21-04-16.pdf | Аннотация доклада]]
| '''Яшунский Алексей Дмитриевич''' (Москва, Институт прикладной математики им. М.В. Келдыша РАН)
|-
|}

2026-02-06T12:46:38Z

SeleznevaSN: SeleznevaSN загружена новая версия «Файл:Dm1-seminars.pdf»

Дискретная математика (1-й поток)

2026-02-06T12:45:36Z

SeleznevaSN: /* Лекции */

[[Категория:Лекционные курсы кафедры МК]]
'''Дополнительная''' страница по курсу [[Дискретная математика (1-й курс)]].

Основной курс '''для студентов 1-го курса''', читается во '''2-м''' семестре. Лекции - '''3 ч''' в неделю, семинары - '''2 ч''' в неделю, отчетность - экзамен.

Лектор - [[Селезнева Светлана Николаевна]]

==Объявления==

Вопросы по содержанию курса (и другие вопросы, относящиеся к курсу) можно задавать лектору Селезневой Светлане Николаевне по эл. почте selezn@cs.msu.ru

==Программа курса==

'''1. Алгебра логики'''. Функции алгебры логики, таблицы истинности. Существенность переменных. Суперпозиции, тождества, эквивалентные преобразования. Дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ). Полиномы Жегалкина. Полнота в алгебре логики. Замкнутые классы. Предполные классы.

'''2. Графы'''. Графы, простейшие свойства. Связность. Деревья, остовные деревья. Планарность графов. Раскраски графов.

'''3. Коды'''. Кодирование. Алфавитные коды, их свойства. Однозначность (разделимость) алфавитных кодов. Минимальная избыточность алфавитных кодов. Коды, обнаруживающие и исправляющие ошибки. Коды Хэмминга. Линейные коды.

'''4. Конечные автоматы'''. Конечные автоматы-преобразователи и конечно-автоматные функции. Представления конечных автоматов и конечно-автоматных функций. Упрощение конечных автоматов.

'''5. СФЭ'''. Схемы из функциональных элементов (СФЭ), представление функций алгебры логики ими. Сумматор, оценка его сложности в СФЭ. Вычитатель, оценка его сложности в СФЭ. Умножитель, оценка его сложности в СФЭ.


'''Литература'''
<ol>
<li> Конспекты лекций.
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
<li> Алексеев В.Б. Дискретная математика. М.: Инфра-М, 2023.
<li> [[Media:Lectdm.pdf|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс.
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2006.
</ol>

==Лекции==



1. '''Алгебра логики'''

Лекция 1. Функции алгебры логики. Таблицы истинности. Существенные и несущественные переменные. Суперпозиции. Тождества.

Лекция 2. Разложение функций по переменным. Дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ). Совершенная ДНФ и совершенная КНФ.

Лекция 3. Полиномы Жегалкина. Теорема Жегалкина. Построение полиномов Жегалкина.

Лекция 4. Полные системы, полнота некоторых систем. Замыкание множества. Замкнутые классы. Замкнутость классов T_0, T_1, L, S, M.

Лекция 5. Леммы о несамодвойственной, немонотонной и нелинейной функциях. Полнота. Теорема Поста о полноте.

Лекция 6. Базисы в P_2. Теорема о числе функций в базисе P_2. Предполные классы. Теорема о предполных классах в P_2.

2. '''Графы'''

Лекция 7. Графы. Простейшие свойства графов. Пути и цепи. Циклы и связность. Удаление и добавление ребер в связных графах. Соотношение между числом вершин, числом ребер и числом компонент связности в графе. Орграфы.

Лекция 8. Деревья. Теорема о равносильных определениях дерева. Корневые деревья. Упорядоченные корневые деревья. Оценка числа деревьев с q ребрами.

Лекция 9. Остовные деревья. Минимальные (кратчайшие) остовные деревья. Алгоритм построения минимального остовного дерева.

Лекция 10. Геометрическое представление графов. Планарные графы. Формула Эйлера для планарных графов. Критерий планарности Понтрягина-Куратовского.

Лекция 11. Раскраски графов. Раскраски графов в два цвета. Раскраски планарных графов.

3. '''Коды'''

Лекция 12. Кодирование. Алфавитные коды. Теорема об однозначности равномерного кода. Теорема об однозначности префиксного кода. Алгоритм Маркова для распознавания однозначности алфавитного кода. Теорема Маркова.

Лекция 13. Алфавитные коды. Неравенство Макмиллана. Теорема о существовании префиксного кода с заданными длинами кодовых слов. Дерево префиксного кода.

Лекция 14. Алфавитные коды. Коды с минимальной избыточностью (оптимальные коды). Свойства кодов с минимальной избыточностью. Теорема редукции. Алгоритм Хаффмена построения кода с минимальной избыточностью.

Лекция 15. Коды, обнаруживающие и исправляющие ошибки, их свойства. Мощность кода, исправляющего ошибки. Линейные коды и их свойства.

Лекция 16. Коды, исправляющие одну ошибку. Коды Хэмминга и их свойства. Алгоритмы кодирования, исправления ошибки и декодирования в коде Хэмминга. Мощность кода, исправляющего одну ошибку.

4. '''Автоматы'''

Лекция 17. Конечные автоматы. Способы их представления. Схемы из функциональных элементов с задержками (СФЭЗ) и представление конечных автоматов ими.

Лекция 18. Конечные автоматы. Отличимость состояний конечного автомата. Оценка длины слова, отличающего два отличимых состояния конечного автомата. Упрощение автоматов.

5. '''СФЭ'''

Лекция 19. Схемы из функциональных элементов (СФЭ). Представление функций алгебры логики СФЭ. Схемы для сложения и вычитания, их сложность.

Лекция 20. Схема для умножения. Сложность схемы для умножения по методу Карацубы.


==Семинары==

[[Media: dm1-seminars.pdf | План семинарских занятий]]

[[Media: dm1-seminars-d.pdf | Дополнительные задачи к семинарским занятиям]]

==Записи лекций==

Записи лекций Селезневой С.Н., прочитанных в 2021 г., можно найти по прямой ссылке [https://m.cs.msu.ru/s/6JnNMf5AXwYT7JF '''Записи лекций С.Н. Селезневой''']

==Экзамен==

Экзамен устный. В билете два теоретических вопроса и задача. Первый вопрос билета - из части А, второй вопрос билета - из части Б.

'''Вопросы к экзамену'''

'''Часть А'''.
Ответ без подготовки, но с возможностью смотреть любые бумажные источники (конспекты лекций, учебники, др.). Пользоваться любыми электронными средствами (телефонами, планшетами, ноутбуками, пр.) не разрешается. Проверяется понимание материала и умение пояснить переходы в доказательствах утверждений. Важно: все определения и теоремы вопроса следует сформулировать без источников (до того, как материалы будут открыты).

<ol>
<li> Функции алгебры логики. Полиномы Жегалкина. Быстрый алгоритм построения полинома Жегалкина функции алгебры логики (с обоснованием).
<li> Функции алгебры логики. Двойственность. Самодвойственные функции. Замкнутость класса самодвойственных функций.
<li> Функции алгебры логики. Монотонные функции. Замкнутость класса монотонных функций.
<li> Функции алгебры логики. Линейные функции. Лемма о нелинейной функции.
<li> Функции алгебры логики. Полнота. Теорема Поста о полноте системы функций алгебры логики.
<li> Функции алгебры логики. Предполные классы. Теорема о предполных классах.
<li> Деревья. Теорема о равносильных определениях дерева.
<li> Остовные деревья. Алгоритм построения кратчайшего остовного дерева в связном графе (с обоснованием).
<li> Раскраски вершин графов. Теорема о раскраске вершин планарных графов в 5 цветов.
<li> Алфавитные коды. Однозначность (разделимость) алфавитного кода. Алгоритм Маркова распознавания однозначности алфавитного кода (с обоснованием).
<li> Алфавитные коды. Теорема Маркова об алфавитных кодах.
<li> Алфавитные коды. Неравенство Макмиллана.
<li> Алфавитные коды. Префиксные коды. Существование префиксного кода с заданными длинами кодовых слов.
<li> Коды с минимальной избыточностью (оптимальные коды). Теорема редукции.
<li> Коды, обнаруживающие и исправляющие ошибки. Критерии кодов, обнаруживающих и исправляющих t ошибок замещения. Функция Mt(n), ее оценки.
<li> Коды, исправляющие одну ошибку. Коды Хэмминга. Оценка функции M1(n).
<li> Схемы из функциональных элементов и элементов задержки (СФЭЗ). Автоматность осуществляемых ими отображений.
<li> Схемы из функциональных элементов и элементов задержки (СФЭЗ). Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
<li> Конечные автоматы. Отличимость состояний конечного автомата. Теорема Мура. Достижимость оценки теоремы Мура.
<li> Схемы из функциональных элементов. Сумматор, верхняя оценка его сложности.
<li> Схемы из функциональных элементов. Вычитатель, верхняя оценка его сложности.
<li> Схемы из функциональных элементов (СФЭ). Умножитель. Метод Карацубы построения умножителя, верхняя оценка его сложности.
</ol>

'''Часть Б'''.
Ответ почти без подготовки и без возможности пользоваться источниками.

<ol start="23">
<li> Функции алгебры логики. Существенность переменных. Формулы. Тождества.
<li> Функции алгебры логики. Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме (ДНФ). Теорема о совершенной конъюнктивной нормальной форме (КНФ).
<li> Функции алгебры логики. Полные системы. Примеры полных систем (с доказательством полноты).
<li> Функции алгебры логики. Теорема Жегалкина о выразимости функции алгебры логики полиномом Жегалкина.
<li> Функции алгебры логики. Замыкание, замкнутый класс. Функции, сохраняющие константу, и линейные функции. Замкнутость классов функций, сохраняющих константу, и линейных функций.
<li> Функции алгебры логики. Самодвойственные функции. Лемма о несамодвойственной функции.
<li> Функции алгебры логики. Монотонные функции. Лемма о немонотонной функции.
<li> Функции алгебры логики. Базис. Теорема о числе функций в базисе в алгебре логики.
<li> Графы. Изоморфизм графов. Связность. Формула Эйлера для степеней вершин. Теорема о соотношении между числом вершин, ребер и компонент связности в графе.
<li> Деревья. Корневые деревья, упорядоченные корневые деревья. Верхняя оценка числа деревьев с заданным числом ребер.
<li> Геометрическое представление графов. Теорема о геометрическом представлении графов в трехмерном пространстве.
<li> Планарные графы. Формула Эйлера для планарных графов. Верхняя оценка числа ребер в планарном графе.
<li> Графы K5 и K3,3. Непланарность графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
<li> Раскраски вершин графов. Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
<li> Коды с минимальной избыточностью (оптимальные коды). Три леммы о свойствах кодов с минимальной избыточностью.
<li> Коды с минимальной избыточностью (оптимальные коды). Алгоритм Хаффмена построения кода с минимальной избыточностью.
<li> Коды, исправляющие одну ошибку. Алгоритмы кодирования, исправления ошибки и декодирования в коде Хэмминга.
<li> Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
<li> Конечные автоматы. Функционирование конечного автомата. Автоматные функции. Канонические уравнения и диаграмма Мура конечного автомата. Единичная задержка, ее автоматность.
<li> Схемы из функциональных элементов. Выразимость функции алгебры логики схемой из функциональных элементов в базисе из конъюнкции, дизъюнкции и отрицания.
</ol>

'''Литература'''
<ol>
<li> Собственный конспект лекций.
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
<li> [[Media:Lectdm.doc|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс.
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2006.
</ol>

'''Задачи к экзамену'''

*Найти существенные и фиктивные переменные заданной функции алгебры логики.
*Найти совершенную ДНФ, совершенную КНФ или полином Жегалкина заданной функции алгебры логики.
*Подсчитать число функций алгебры логики, зависящих от n переменных, в заданном множестве.
*Проверить полноту заданной системы функций алгебры логики (конечной или бесконечной).
*Проверить, является ли данная система функций алгебры логики базисом, или выделить из заданной системы функций алгебры логики все базисы.

*Найти число неизоморфных графов с заданными свойствами и изобразить эти графы.
*Найти код упорядоченного корневого дерева или восстановить упорядоченное корневое дерево по коду.
*Найти в заданном графе подграф, гомеоморфный графу K_5 или графу K_3,3.
*Проверить, является ли заданный граф планарным.
*Проверить, найдется ли планарный граф с заданными свойствами.
*Найти хроматическое число или хроматический индекс заданного графа.
*Проверить разделимость заданного алфавитного кода (по алгоритму).
*Проверить разделимость заданного алфавитного кода по неравенству Макмиллана или построить префиксный код с заданными длинами кодовых слов.
*Найти оптимальный алфавитный двоичный код по заданному набору частот.
*Определить, сколько ошибок замещения обнаруживает или исправляет заданный равномерный код.
*Закодировать или исправить ошибку и декодировать сообщение в коде Хэмминга.
*Найти кодовое расстояние заданного линейного кода.
*Найти диаграмму Мура автоматной функции, заданной описанием.
*Найти диаграмму Мура, каноническую таблицу, канонические уравнения или СФЭ с задержками автоматной функции, заданной одним из перечисленных способов.
*Построить диаграмму Мура, не содержащую недостижимых и неотличимых состояний, для заданной автоматной функции.

Дискретная математика (1-й поток)

2026-02-06T12:43:31Z

SeleznevaSN: /* Программа курса */

[[Категория:Лекционные курсы кафедры МК]]
'''Дополнительная''' страница по курсу [[Дискретная математика (1-й курс)]].

Основной курс '''для студентов 1-го курса''', читается во '''2-м''' семестре. Лекции - '''3 ч''' в неделю, семинары - '''2 ч''' в неделю, отчетность - экзамен.

Лектор - [[Селезнева Светлана Николаевна]]

==Объявления==

Вопросы по содержанию курса (и другие вопросы, относящиеся к курсу) можно задавать лектору Селезневой Светлане Николаевне по эл. почте selezn@cs.msu.ru

==Программа курса==

'''1. Алгебра логики'''. Функции алгебры логики, таблицы истинности. Существенность переменных. Суперпозиции, тождества, эквивалентные преобразования. Дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ). Полиномы Жегалкина. Полнота в алгебре логики. Замкнутые классы. Предполные классы.

'''2. Графы'''. Графы, простейшие свойства. Связность. Деревья, остовные деревья. Планарность графов. Раскраски графов.

'''3. Коды'''. Кодирование. Алфавитные коды, их свойства. Однозначность (разделимость) алфавитных кодов. Минимальная избыточность алфавитных кодов. Коды, обнаруживающие и исправляющие ошибки. Коды Хэмминга. Линейные коды.

'''4. Конечные автоматы'''. Конечные автоматы-преобразователи и конечно-автоматные функции. Представления конечных автоматов и конечно-автоматных функций. Упрощение конечных автоматов.

'''5. СФЭ'''. Схемы из функциональных элементов (СФЭ), представление функций алгебры логики ими. Сумматор, оценка его сложности в СФЭ. Вычитатель, оценка его сложности в СФЭ. Умножитель, оценка его сложности в СФЭ.


'''Литература'''
<ol>
<li> Конспекты лекций.
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
<li> Алексеев В.Б. Дискретная математика. М.: Инфра-М, 2023.
<li> [[Media:Lectdm.pdf|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс.
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2006.
</ol>

==Лекции==



1. '''Алгебра логики'''

Лекция 1. Функции алгебры логики. Таблицы истинности. Существенные и несущественные переменные. Формулы. Тождества.

Лекция 2. Разложение функций по переменным. Дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ). Совершенная ДНФ и совершенная КНФ.

Лекция 3. Полиномы Жегалкина. Теорема Жегалкина. Построение полиномов Жегалкина.

Лекция 4. Полные системы, полнота некоторых систем. Замыкание множества. Замкнутые классы. Замкнутость классов T_0, T_1, L, S, M.

Лекция 5. Леммы о несамодвойственной, немонотонной и нелинейной функциях. Полнота. Теорема Поста о полноте.

Лекция 6. Базисы в P_2. Теорема о числе функций в базисе P_2. Предполные классы. Теорема о предполных классах в P_2.

2. '''Графы'''

Лекция 7. Графы. Простейшие свойства графов. Пути и цепи. Циклы и связность. Удаление и добавление ребер в связных графах. Соотношение между числом вершин, числом ребер и числом компонент связности в графе. Орграфы.

Лекция 8. Деревья. Теорема о равносильных определениях дерева. Корневые деревья. Упорядоченные корневые деревья. Оценка числа деревьев с q ребрами.

Лекция 9. Остовные деревья. Кратчайшие остовные деревья. Алгоритм построения кратчайшего остовного дерева.

Лекция 10. Геометрическое представление графов. Планарные графы. Формула Эйлера для планарных графов. Критерий планарности Понтрягина-Куратовского.

Лекция 11. Раскраски графов. Раскраски графов в два цвета. Раскраски планарных графов.

3. '''Коды'''

Лекция 12. Кодирование. Алфавитные коды. Теорема об однозначности равномерного кода. Теорема об однозначности префиксного кода. Алгоритм Маркова для распознавания однозначности алфавитного кода. Теорема Маркова.

Лекция 13. Алфавитные коды. Неравенство Макмиллана. Теорема о существовании префиксного кода с заданными длинами кодовых слов. Дерево префиксного кода.

Лекция 14. Алфавитные коды. Коды с минимальной избыточностью (оптимальные коды). Свойства кодов с минимальной избыточностью. Теорема редукции. Алгоритм Хаффмена построения кода с минимальной избыточностью.

Лекция 15. Коды, обнаруживающие и исправляющие ошибки, их свойства. Мощность кода, исправляющего ошибки. Линейные коды и их свойства.

Лекция 16. Коды, исправляющие одну ошибку. Коды Хэмминга и их свойства. Алгоритмы кодирования, исправления ошибки и декодирования в коде Хэмминга. Мощность кода, исправляющего одну ошибку.

4. '''Автоматы'''

Лекция 17. Конечные автоматы. Способы их представления. Схемы из функциональных элементов с задержками (СФЭЗ) и представление конечных автоматов ими.

Лекция 18. Конечные автоматы. Отличимость состояний конечного автомата. Оценка длины слова, отличающего два отличимых состояния конечного автомата. Упрощение автоматов.

5. '''СФЭ'''

Лекция 19. Схемы из функциональных элементов (СФЭ). Представление функций алгебры логики СФЭ. Схемы для сложения и вычитания, их сложность.

Лекция 20. Схема для умножения. Сложность схемы для умножения по методу Карацубы.


==Семинары==

[[Media: dm1-seminars.pdf | План семинарских занятий]]

[[Media: dm1-seminars-d.pdf | Дополнительные задачи к семинарским занятиям]]

==Записи лекций==

Записи лекций Селезневой С.Н., прочитанных в 2021 г., можно найти по прямой ссылке [https://m.cs.msu.ru/s/6JnNMf5AXwYT7JF '''Записи лекций С.Н. Селезневой''']

==Экзамен==

Экзамен устный. В билете два теоретических вопроса и задача. Первый вопрос билета - из части А, второй вопрос билета - из части Б.

'''Вопросы к экзамену'''

'''Часть А'''.
Ответ без подготовки, но с возможностью смотреть любые бумажные источники (конспекты лекций, учебники, др.). Пользоваться любыми электронными средствами (телефонами, планшетами, ноутбуками, пр.) не разрешается. Проверяется понимание материала и умение пояснить переходы в доказательствах утверждений. Важно: все определения и теоремы вопроса следует сформулировать без источников (до того, как материалы будут открыты).

<ol>
<li> Функции алгебры логики. Полиномы Жегалкина. Быстрый алгоритм построения полинома Жегалкина функции алгебры логики (с обоснованием).
<li> Функции алгебры логики. Двойственность. Самодвойственные функции. Замкнутость класса самодвойственных функций.
<li> Функции алгебры логики. Монотонные функции. Замкнутость класса монотонных функций.
<li> Функции алгебры логики. Линейные функции. Лемма о нелинейной функции.
<li> Функции алгебры логики. Полнота. Теорема Поста о полноте системы функций алгебры логики.
<li> Функции алгебры логики. Предполные классы. Теорема о предполных классах.
<li> Деревья. Теорема о равносильных определениях дерева.
<li> Остовные деревья. Алгоритм построения кратчайшего остовного дерева в связном графе (с обоснованием).
<li> Раскраски вершин графов. Теорема о раскраске вершин планарных графов в 5 цветов.
<li> Алфавитные коды. Однозначность (разделимость) алфавитного кода. Алгоритм Маркова распознавания однозначности алфавитного кода (с обоснованием).
<li> Алфавитные коды. Теорема Маркова об алфавитных кодах.
<li> Алфавитные коды. Неравенство Макмиллана.
<li> Алфавитные коды. Префиксные коды. Существование префиксного кода с заданными длинами кодовых слов.
<li> Коды с минимальной избыточностью (оптимальные коды). Теорема редукции.
<li> Коды, обнаруживающие и исправляющие ошибки. Критерии кодов, обнаруживающих и исправляющих t ошибок замещения. Функция Mt(n), ее оценки.
<li> Коды, исправляющие одну ошибку. Коды Хэмминга. Оценка функции M1(n).
<li> Схемы из функциональных элементов и элементов задержки (СФЭЗ). Автоматность осуществляемых ими отображений.
<li> Схемы из функциональных элементов и элементов задержки (СФЭЗ). Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
<li> Конечные автоматы. Отличимость состояний конечного автомата. Теорема Мура. Достижимость оценки теоремы Мура.
<li> Схемы из функциональных элементов. Сумматор, верхняя оценка его сложности.
<li> Схемы из функциональных элементов. Вычитатель, верхняя оценка его сложности.
<li> Схемы из функциональных элементов (СФЭ). Умножитель. Метод Карацубы построения умножителя, верхняя оценка его сложности.
</ol>

'''Часть Б'''.
Ответ почти без подготовки и без возможности пользоваться источниками.

<ol start="23">
<li> Функции алгебры логики. Существенность переменных. Формулы. Тождества.
<li> Функции алгебры логики. Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме (ДНФ). Теорема о совершенной конъюнктивной нормальной форме (КНФ).
<li> Функции алгебры логики. Полные системы. Примеры полных систем (с доказательством полноты).
<li> Функции алгебры логики. Теорема Жегалкина о выразимости функции алгебры логики полиномом Жегалкина.
<li> Функции алгебры логики. Замыкание, замкнутый класс. Функции, сохраняющие константу, и линейные функции. Замкнутость классов функций, сохраняющих константу, и линейных функций.
<li> Функции алгебры логики. Самодвойственные функции. Лемма о несамодвойственной функции.
<li> Функции алгебры логики. Монотонные функции. Лемма о немонотонной функции.
<li> Функции алгебры логики. Базис. Теорема о числе функций в базисе в алгебре логики.
<li> Графы. Изоморфизм графов. Связность. Формула Эйлера для степеней вершин. Теорема о соотношении между числом вершин, ребер и компонент связности в графе.
<li> Деревья. Корневые деревья, упорядоченные корневые деревья. Верхняя оценка числа деревьев с заданным числом ребер.
<li> Геометрическое представление графов. Теорема о геометрическом представлении графов в трехмерном пространстве.
<li> Планарные графы. Формула Эйлера для планарных графов. Верхняя оценка числа ребер в планарном графе.
<li> Графы K5 и K3,3. Непланарность графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
<li> Раскраски вершин графов. Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
<li> Коды с минимальной избыточностью (оптимальные коды). Три леммы о свойствах кодов с минимальной избыточностью.
<li> Коды с минимальной избыточностью (оптимальные коды). Алгоритм Хаффмена построения кода с минимальной избыточностью.
<li> Коды, исправляющие одну ошибку. Алгоритмы кодирования, исправления ошибки и декодирования в коде Хэмминга.
<li> Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
<li> Конечные автоматы. Функционирование конечного автомата. Автоматные функции. Канонические уравнения и диаграмма Мура конечного автомата. Единичная задержка, ее автоматность.
<li> Схемы из функциональных элементов. Выразимость функции алгебры логики схемой из функциональных элементов в базисе из конъюнкции, дизъюнкции и отрицания.
</ol>

'''Литература'''
<ol>
<li> Собственный конспект лекций.
<li> Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
<li> [[Media:Lectdm.doc|Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004.]] Электронный ресурс.
<li> Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.
<li> Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
<li> Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2006.
</ol>

'''Задачи к экзамену'''

*Найти существенные и фиктивные переменные заданной функции алгебры логики.
*Найти совершенную ДНФ, совершенную КНФ или полином Жегалкина заданной функции алгебры логики.
*Подсчитать число функций алгебры логики, зависящих от n переменных, в заданном множестве.
*Проверить полноту заданной системы функций алгебры логики (конечной или бесконечной).
*Проверить, является ли данная система функций алгебры логики базисом, или выделить из заданной системы функций алгебры логики все базисы.

*Найти число неизоморфных графов с заданными свойствами и изобразить эти графы.
*Найти код упорядоченного корневого дерева или восстановить упорядоченное корневое дерево по коду.
*Найти в заданном графе подграф, гомеоморфный графу K_5 или графу K_3,3.
*Проверить, является ли заданный граф планарным.
*Проверить, найдется ли планарный граф с заданными свойствами.
*Найти хроматическое число или хроматический индекс заданного графа.
*Проверить разделимость заданного алфавитного кода (по алгоритму).
*Проверить разделимость заданного алфавитного кода по неравенству Макмиллана или построить префиксный код с заданными длинами кодовых слов.
*Найти оптимальный алфавитный двоичный код по заданному набору частот.
*Определить, сколько ошибок замещения обнаруживает или исправляет заданный равномерный код.
*Закодировать или исправить ошибку и декодировать сообщение в коде Хэмминга.
*Найти кодовое расстояние заданного линейного кода.
*Найти диаграмму Мура автоматной функции, заданной описанием.
*Найти диаграмму Мура, каноническую таблицу, канонические уравнения или СФЭ с задержками автоматной функции, заданной одним из перечисленных способов.
*Построить диаграмму Мура, не содержащую недостижимых и неотличимых состояний, для заданной автоматной функции.

Графы и их приложения

2026-01-06T16:18:06Z

SeleznevaSN: /* Объявления */

[[Категория:Лекционные курсы кафедры МК]]
[[Категория:Спецкурсы кафедры МК]]
Спецкурс для аспирантов.

Лектор - [[Селезнева Светлана Николаевна]]

'''Аннотация'''. В курсе рассматриваются основные структурные свойства графов и показывается их применение при решении подходящих задач. Разбираются простейшие свойства графов, связность и k-связность, деревья и остовные деревья, вершинные и реберные раскраски графов, наследственные свойства графов и экстремальные графы, числа Рамсея, статистические свойства графов и потоки в сетях. Кроме того, уделяется внимание алгоритмическим вопросам, связанным с графами, в частности, труднорешаемым графовым задачам. Приводятся как классические, так и достаточно новые результаты, относящиеся к свойствам графов.

==Объявления==

Пересдача экзамена состоится 10 января 2026 г. (в субботу) в ауд. 503. Начало экзамена в 11 ч 00 мин.

Продолжительность написания работы - 1 ч 30 мин (до 12 ч 30 мин).

Вопросы по содержанию курса можно присылать Селезневой Светлане Николаевне по эл. почте selezn@cs.msu.ru

==Экзамен==

Экзамен письменный. Продолжительность экзамена – 1 час 30 минут (90 минут). В проверочной работе десять заданий разной сложности по содержанию курса. Первые четыре задания – стандартные задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания – формулировки определений или теорем с дополнительным вопросом. Вопрос проясняет понимание аспирантом формулировки. Они оцениваются также в три балла каждое. Оставшиеся два задания – вопросы или задачи повышенной сложности. Они показывают, может ли аспирант извлекать новые сведения из полученных знаний в курсе. Всего за работу можно получить не более 32 баллов. Критерии оценок: не менее 27 баллов – «отлично», 21-26 баллов – «хорошо», 15-20 баллов – «удовлетворительно», менее 14 баллов – «неудовлетворительно».

'''Вопросы для подготовки к экзамену (2025-2026 уч. год)'''

1. Граф. Степень вершины в графе, формула Эйлера. Пути, цепи и циклы в графе, их свойства. Связность, компоненты связности графа. Соотношение между числом вершин, числом ребер и числом компонент связности в графе.

2. Деревья, основные свойства деревьев.

3. Разделяющие вершины и ребра (мосты) в графе. Критерии разделяющей вершины и моста в графе.

4. Вершинно двусвязные графы. Критерий двусвязности графа. Реберно двусвязные графы. Критерий реберно двусвязного графа.

5. Компоненты двусвязности связного графа. Дерево компонент двусвязности и разделяющих вершин связного графа.

6. Остовные деревья. Число остовных деревьев в полном помеченном графе (теорема Кэли).

7. Остовные деревья. Достижимость промежуточного числа висячих вершин в остовном дереве графа.

8. Остовные деревья. Оценка числа висячих вершин в остовном дереве графа.

9. Хроматическое число графа. Критерий раскрашиваемости вершин графа в два цвета (теорема Кенига).

10. Хроматическое число графа. Верхние оценки хроматического числа графа (теорема Брукса).

11. Хроматическое число графа. Существование графов без треугольников с произвольно большим хроматическим числом (теорема Зыкова).

12. Хроматический индекс графа. Хроматический индекс двудольного графа (теорема Кенига).

13. Хроматический индекс графа. Верхняя оценка хроматического индекса графа (теорема Визинга).

14. Наследственные свойства графов. Рекуррентное соотношение о наибольшем числе ребер в графе с наследственным свойством.

15. Наследственные свойства графов. Планарные графы. Наибольшее число ребер в планарном графе.

16. Наследственные свойства графов. Наибольшее число ребер в графе без треугольников.

17. Наследственные свойства графов. Наибольшее число ребер в графе без полного подграфа с n вершинами (теорема Турана).

18. Числа Рамсея. Рекуррентное соотношение для чисел Рамсея. Верхние оценки числа Рамсея.

19. Числа Рамсея. Нижняя оценка числа Рамсея (теорема Эрдеша).

==Лекции==

'''Литература'''

'''Основная''':

1. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2009.

2. Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008.

'''Дополнительная''':

3. Diestel R. Graph Theory. Springer, 2010.

4. Карпов Д.В. Теория графов

5. Харари Ф. Теория графов. М.: Мир, 1973.

6. Оре О. Теория графов. М.: Наука, 1980.

7. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

8. Липский В. Комбинаторика для программистов. М.: Мир, 1988.

9. Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. М.: МЦНМО, 2014.

10. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.

11. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.

Графы и их приложения

2026-01-06T16:17:51Z

SeleznevaSN: /* Объявления */

[[Категория:Лекционные курсы кафедры МК]]
[[Категория:Спецкурсы кафедры МК]]
Спецкурс для аспирантов.

Лектор - [[Селезнева Светлана Николаевна]]

'''Аннотация'''. В курсе рассматриваются основные структурные свойства графов и показывается их применение при решении подходящих задач. Разбираются простейшие свойства графов, связность и k-связность, деревья и остовные деревья, вершинные и реберные раскраски графов, наследственные свойства графов и экстремальные графы, числа Рамсея, статистические свойства графов и потоки в сетях. Кроме того, уделяется внимание алгоритмическим вопросам, связанным с графами, в частности, труднорешаемым графовым задачам. Приводятся как классические, так и достаточно новые результаты, относящиеся к свойствам графов.

==Объявления==

Пересдача экзамена состоится 10 декабря 2026 г. (в субботу) в ауд. 503. Начало экзамена в 11 ч 00 мин.

Продолжительность написания работы - 1 ч 30 мин (до 12 ч 30 мин).

Вопросы по содержанию курса можно присылать Селезневой Светлане Николаевне по эл. почте selezn@cs.msu.ru

==Экзамен==

Экзамен письменный. Продолжительность экзамена – 1 час 30 минут (90 минут). В проверочной работе десять заданий разной сложности по содержанию курса. Первые четыре задания – стандартные задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания – формулировки определений или теорем с дополнительным вопросом. Вопрос проясняет понимание аспирантом формулировки. Они оцениваются также в три балла каждое. Оставшиеся два задания – вопросы или задачи повышенной сложности. Они показывают, может ли аспирант извлекать новые сведения из полученных знаний в курсе. Всего за работу можно получить не более 32 баллов. Критерии оценок: не менее 27 баллов – «отлично», 21-26 баллов – «хорошо», 15-20 баллов – «удовлетворительно», менее 14 баллов – «неудовлетворительно».

'''Вопросы для подготовки к экзамену (2025-2026 уч. год)'''

1. Граф. Степень вершины в графе, формула Эйлера. Пути, цепи и циклы в графе, их свойства. Связность, компоненты связности графа. Соотношение между числом вершин, числом ребер и числом компонент связности в графе.

2. Деревья, основные свойства деревьев.

3. Разделяющие вершины и ребра (мосты) в графе. Критерии разделяющей вершины и моста в графе.

4. Вершинно двусвязные графы. Критерий двусвязности графа. Реберно двусвязные графы. Критерий реберно двусвязного графа.

5. Компоненты двусвязности связного графа. Дерево компонент двусвязности и разделяющих вершин связного графа.

6. Остовные деревья. Число остовных деревьев в полном помеченном графе (теорема Кэли).

7. Остовные деревья. Достижимость промежуточного числа висячих вершин в остовном дереве графа.

8. Остовные деревья. Оценка числа висячих вершин в остовном дереве графа.

9. Хроматическое число графа. Критерий раскрашиваемости вершин графа в два цвета (теорема Кенига).

10. Хроматическое число графа. Верхние оценки хроматического числа графа (теорема Брукса).

11. Хроматическое число графа. Существование графов без треугольников с произвольно большим хроматическим числом (теорема Зыкова).

12. Хроматический индекс графа. Хроматический индекс двудольного графа (теорема Кенига).

13. Хроматический индекс графа. Верхняя оценка хроматического индекса графа (теорема Визинга).

14. Наследственные свойства графов. Рекуррентное соотношение о наибольшем числе ребер в графе с наследственным свойством.

15. Наследственные свойства графов. Планарные графы. Наибольшее число ребер в планарном графе.

16. Наследственные свойства графов. Наибольшее число ребер в графе без треугольников.

17. Наследственные свойства графов. Наибольшее число ребер в графе без полного подграфа с n вершинами (теорема Турана).

18. Числа Рамсея. Рекуррентное соотношение для чисел Рамсея. Верхние оценки числа Рамсея.

19. Числа Рамсея. Нижняя оценка числа Рамсея (теорема Эрдеша).

==Лекции==

'''Литература'''

'''Основная''':

1. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2009.

2. Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008.

'''Дополнительная''':

3. Diestel R. Graph Theory. Springer, 2010.

4. Карпов Д.В. Теория графов

5. Харари Ф. Теория графов. М.: Мир, 1973.

6. Оре О. Теория графов. М.: Наука, 1980.

7. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

8. Липский В. Комбинаторика для программистов. М.: Мир, 1988.

9. Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. М.: МЦНМО, 2014.

10. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.

11. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.

Графы и их приложения

2026-01-06T16:16:25Z

SeleznevaSN: /* Объявления */

[[Категория:Лекционные курсы кафедры МК]]
[[Категория:Спецкурсы кафедры МК]]
Спецкурс для аспирантов.

Лектор - [[Селезнева Светлана Николаевна]]

'''Аннотация'''. В курсе рассматриваются основные структурные свойства графов и показывается их применение при решении подходящих задач. Разбираются простейшие свойства графов, связность и k-связность, деревья и остовные деревья, вершинные и реберные раскраски графов, наследственные свойства графов и экстремальные графы, числа Рамсея, статистические свойства графов и потоки в сетях. Кроме того, уделяется внимание алгоритмическим вопросам, связанным с графами, в частности, труднорешаемым графовым задачам. Приводятся как классические, так и достаточно новые результаты, относящиеся к свойствам графов.

==Объявления==

Пересдача экзамена состоится 10 декабря 2025 г. (в субботу) в ауд. 503. Начало экзамена в 11 ч 00 мин.

Продолжительность написания работы - 1 ч 30 мин (до 12 ч 30 мин).

Вопросы по содержанию курса можно присылать Селезневой Светлане Николаевне по эл. почте selezn@cs.msu.ru

==Экзамен==

Экзамен письменный. Продолжительность экзамена – 1 час 30 минут (90 минут). В проверочной работе десять заданий разной сложности по содержанию курса. Первые четыре задания – стандартные задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания – формулировки определений или теорем с дополнительным вопросом. Вопрос проясняет понимание аспирантом формулировки. Они оцениваются также в три балла каждое. Оставшиеся два задания – вопросы или задачи повышенной сложности. Они показывают, может ли аспирант извлекать новые сведения из полученных знаний в курсе. Всего за работу можно получить не более 32 баллов. Критерии оценок: не менее 27 баллов – «отлично», 21-26 баллов – «хорошо», 15-20 баллов – «удовлетворительно», менее 14 баллов – «неудовлетворительно».

'''Вопросы для подготовки к экзамену (2025-2026 уч. год)'''

1. Граф. Степень вершины в графе, формула Эйлера. Пути, цепи и циклы в графе, их свойства. Связность, компоненты связности графа. Соотношение между числом вершин, числом ребер и числом компонент связности в графе.

2. Деревья, основные свойства деревьев.

3. Разделяющие вершины и ребра (мосты) в графе. Критерии разделяющей вершины и моста в графе.

4. Вершинно двусвязные графы. Критерий двусвязности графа. Реберно двусвязные графы. Критерий реберно двусвязного графа.

5. Компоненты двусвязности связного графа. Дерево компонент двусвязности и разделяющих вершин связного графа.

6. Остовные деревья. Число остовных деревьев в полном помеченном графе (теорема Кэли).

7. Остовные деревья. Достижимость промежуточного числа висячих вершин в остовном дереве графа.

8. Остовные деревья. Оценка числа висячих вершин в остовном дереве графа.

9. Хроматическое число графа. Критерий раскрашиваемости вершин графа в два цвета (теорема Кенига).

10. Хроматическое число графа. Верхние оценки хроматического числа графа (теорема Брукса).

11. Хроматическое число графа. Существование графов без треугольников с произвольно большим хроматическим числом (теорема Зыкова).

12. Хроматический индекс графа. Хроматический индекс двудольного графа (теорема Кенига).

13. Хроматический индекс графа. Верхняя оценка хроматического индекса графа (теорема Визинга).

14. Наследственные свойства графов. Рекуррентное соотношение о наибольшем числе ребер в графе с наследственным свойством.

15. Наследственные свойства графов. Планарные графы. Наибольшее число ребер в планарном графе.

16. Наследственные свойства графов. Наибольшее число ребер в графе без треугольников.

17. Наследственные свойства графов. Наибольшее число ребер в графе без полного подграфа с n вершинами (теорема Турана).

18. Числа Рамсея. Рекуррентное соотношение для чисел Рамсея. Верхние оценки числа Рамсея.

19. Числа Рамсея. Нижняя оценка числа Рамсея (теорема Эрдеша).

==Лекции==

'''Литература'''

'''Основная''':

1. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2009.

2. Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008.

'''Дополнительная''':

3. Diestel R. Graph Theory. Springer, 2010.

4. Карпов Д.В. Теория графов

5. Харари Ф. Теория графов. М.: Мир, 1973.

6. Оре О. Теория графов. М.: Наука, 1980.

7. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

8. Липский В. Комбинаторика для программистов. М.: Мир, 1988.

9. Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. М.: МЦНМО, 2014.

10. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.

11. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.

Математические вопросы кибернетики

2025-12-22T17:06:57Z

SeleznevaSN: /* 2025-2026 учебный год */

[[Mathematical Problems of Cybernetics]]

Научно-исследовательский семинар кафедр [http://new.math.msu.su/department/dm/ '''дискретной математики'''] и [http://intsys.msu.ru/ '''математической теории интеллектуальных систем'''] механико-математического факультета и [https://mk.cs.msu.ru/index.php/Заглавная_страница '''математической кибернетики'''] факультета вычислительной математики и кибернетики МГУ имени М.В. Ломоносова.

'''Цель семинара''': обсуждение современных задач математической кибернетики и широкого круга смежных вопросов и представление наиболее значимых результатов в этой области.

'''Традиции семинара''': семинар продолжает научно-исследовательский семинар по математическим вопросам кибернетики, который более 30 лет проводился в Московском университете под руководством [https://mk.cs.msu.ru/index.php/Яблонский_Сергей_Всеволодович '''Сергея Всеволодовича Яблонского'''] и [http://new.math.msu.su/obl '''Олега Борисовича Лупанова'''].

==2025-2026 учебный год==

В '''2025-2026 учебном году''' семинар проводится удаленно '''по пятницам''' в '''19-00''' (по московскому времени) по объявлениям.

Заседания проводятся на платформе zoom, идентификатор конференции: 830 6246 3909, код доступа: 947173.

По вопросам, связанным с работой семинара, можно писать по эл. почте '''mvk@cs.msu.ru''' Селезневой Светлане Николаевне.

'''Расписание докладов'''

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 26 декабря 2025 г.
| '''Семинар, посвященный 90-летию со дня рождения Н.А. Карповой.'''
|'''Кочергин Вадим Васильевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 19 сентября 2025 г.
| '''О свойствах конечно порождающих систем булевых функций для классов рациональных вероятностей'''. [[Media: mvk-25-09-19.pdf | Аннотация доклада]]
|'''Трифонова Екатерина Евгеньевна''' (Москва, ИМП им. М.В. Келдыша)
|-
|}

==2024-2025 учебный год==

'''Расписание докладов'''

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 23 мая 2025 г.
| '''Метод граничных функционалов и нижние оценки числа антицепей в некоторых ранжированных ЧУМ'''. [[Media: mvk-25-05-23.pdf | Аннотация доклада]]
|'''Андреева Татьяна Владимировна''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 25 апреля 2025 г.
| '''Асимптотически точные оценки сложности некоторых функций и систем функций в модели клеточных схем'''. [[Media: mvk-25-04-25.pdf | Аннотация доклада]]
|'''Зизов Вадим Сергеевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 14 марта 2025 г.
| '''О некоторых свойствах конечных квазигрупп'''. [[Media: mvk-25-03-14.pdf | Аннотация доклада]]
|'''Галатенко Алексей Владимирович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 28 февраля 2025 г.
| '''Семинар памяти Л.А. Шоломова'''.
|'''Чашкин Александр Викторович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 25 октября 2024 г.
| '''Нижние оценки сложности линейных операторов над GF(2)'''. [[Media: mvk-24-10-25.pdf | Аннотация доклада]]
|'''Сергеев Игорь Сергеевич''' (Москва, Научно-исследовательский институт «Квант»)
|-
|}

==2023-2024 учебный год==

'''Расписание докладов'''

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 17 мая 2024 г.
| '''Оценки длин минимальных тестов для аргументов функций при подстановке констант, алгебраических операциях и сдвигах'''. [[Media: mvk-24-05-17.pdf | Аннотация доклада]]
|'''Антюфеев Григорий Валерьевич''' (Москва, «НИИМА «ПРОГРЕСС»»)
|-
| 5 апреля 2024 г.
| '''Семинар, посвященный 85-летию проф. А.А. Сапоженко'''. [[Media: mvk-24-04-05.pdf | Аннотация доклада]]
|
|-
| 22 марта 2024 г.
| '''Многомерные матрицы в алгебраической теории гиперграфов'''. [[Media: mvk-24-03-22.pdf | Аннотация доклада]]
| '''Тараненко Анна Александровна''' (Новосибирск, Институт математики имени С.Л. Cоболева СО РАН)
|-
| 15 марта 2024 г.
| '''Симметричные функции k-значной логики и универсальные алгоритмы для задачи удовлетворения ограничений'''. [[Media: mvk-24-03-15.pdf | Аннотация доклада]]
| '''Жук Дмитрий Николаевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 15 декабря 2023 г.
| '''Коммутаторная длина степеней в свободных произведениях групп'''. [[Media: mvk-23-12-15.pdf | Аннотация доклада]]
| '''Березнюк Вадим Юрьевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 8 декабря 2023 г.
| '''Реализация вероятностных автоматов на однородных вычислительных системах при использовании арифметики полей Галуа'''. [[Media: mvk-23-12-08.pdf | Аннотация доклада]]
| '''Шалагин Сергей Викторович''' (Казань, Казанский национальный исследовательский технический университет им. А.Н.Туполева – КАИ)
|-
| 1 декабря 2023 г.
| '''О сложности и структуре некоторых типов контактных схем для ряда симметрических булевых функций'''. [[Media: mvk-23-12-01.pdf | Аннотация доклада]]
| '''Попов Евгений Александрович''' (Москва, фирма Примариус)
|-
| 17 ноября 2023 г.
| '''Правильные семейства дискретных функций: эквивалентные определения и свойства'''. [[Media: mvk-23-11-17.pdf | Аннотация доклада]]
| '''Царегородцев Кирилл Денисович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 6 октября 2023 г.
| '''Компьютерное моделирование логических процессов'''. [[Media: mvk-23-10-06.pdf | Аннотация доклада]]
| '''Подколзин Александр Сергеевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
|}

==2022-2023 учебный год==

'''Расписание докладов'''

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 19 мая 2023 г.
| '''Конструкции и свойства корреляционно-иммунных и платовидных булевых функций'''. [[Media: mvk-23-05-19.pdf | Аннотация доклада]]
| '''Таранников Юрий Валерьевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 12 мая 2023 г.
| '''О соотношениях между активностью схем из функциональных элементов и положительной чувствительностью функций алгебры логики'''. [[Media: mvk-23-05-12.pdf | Аннотация доклада]]
| '''Местецкий Михаил Александрович''', '''Шуплецов Михаил Сергеевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 28 апреля 2023 г.
| '''Семинар, посвященный 70-летию со дня рождения О. М. Касим-Заде'''. [[Media: mvk-23-04-28.pdf | Аннотация]]
|
|-
| 21 апреля 2023 г.
| '''Дихотомия сложности кванторной задачи удовлетворения ограничениям'''. [[Media: mvk-23-04-21.pdf | Аннотация доклада]]
| '''Жук Дмитрий Николаевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 31 марта 2023 г.
| '''О числе субпериодичностей в двоичных формальных словах'''. [[Media: mvk-23-03-31.pdf | Аннотация доклада]]
| '''Колпаков Роман Максимович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 17 марта 2023 г.
| '''Некоторые свойства сложностных классов AC^0 и TC^0'''. [[Media: mvk-23-03-17.pdf | Аннотация доклада]]
| '''Савицкий Игорь Владимирович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 3 марта 2023 г.
| '''Оценки энергопотребления объемных схем'''. [[Media: mvk-23-03-03.pdf | Аннотация доклада]]
| '''Ефимов Алексей Андреевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 17 февраля 2023 г.
| '''Об асимптотике роста мощности слоев в декартовых степенях некоторых взвешенных множеств'''. [[Media: mvk-23-02-17.pdf | Аннотация доклада]]
| '''Андреева Татьяна Владимировна''' (Москва, МГТУ имени Н.Э. Баумана; МГУ имени М.В. Ломоносова), '''Семенов Юрий Станиславович'''
|-
| 16 декабря 2022 г.
| '''Памяти Валерия Борисовича Кудряцева'''. [[Media: mvk-22-12-16.pdf | Аннотация доклада]]
| '''Гасанов Э.Э., Алешин С.В., Часовских А.А., Сыркин Г.И.'''
|-
| 9 декабря 2022 г.
| '''Тензорные сети для эффективной симуляции квантовых вычислений'''. [[Media: mvk-22-12-09.pdf | Аннотация доклада]]
| '''Пантелеев Павел Анатольевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 11 ноября 2022 г.
| '''Цифровая подпись на основе кодов, определяющих изображения с точностью до аффинных преобразований'''. [[Media: mvk-22-11-11.pdf | Аннотация доклада]]
| '''Козлов Вадим Никитович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 28 октября 2022 г.
| '''О математических моделях и структурных графах в теории механизмов'''. [[Media: mvk-22-10-28.pdf | Аннотация доклада]]
| '''Ковалев Михаил Дмитриевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 21 октября 2022 г.
| '''О перманентах (0, 1)- и (-1,1)-матриц'''. [[Media: mvk-22-10-21.pdf | Аннотация доклада]]
| '''Таранин Константин Александрович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 14 октября 2022 г.
| '''Параметро-эффективная расшифровка булевых функций'''. [[Media: mvk-22-10-14.pdf | Аннотация доклада]]
| '''Быстрыгова Анастасия Викторовна''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 7 октября 2022 г.
| '''Задачи Беллмана, Кнута, Лупанова, Пиппенджера и их вариации как обобщения задачи об аддитивных цепочках'''. [[Media: mvk-22-10-07.pdf | Аннотация доклада]]
| '''Кочергин Вадим Васильевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 30 сентября 2022 г.
| '''Асимптотически точные оценки сложности некоторых функций в модели клеточных схем'''. [[Media: mvk-22-09-30.pdf | Аннотация доклада]]
| '''Ложкин Сергей Андреевич, Зизов Вадим Сергеевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
|}

==2021-2022 учебный год==

'''Расписание докладов'''

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 29 апреля 2022 г.
| '''Размерность Вейсфейлера-Лемана алгебраических и комбинаторных структур'''. [[Media: mvk-22-04-29.pdf | Аннотация доклада]]
| '''Пономаренко Илья Николаевич''' (Санкт-Петербург, Санкт-Петербургское отделение Математического института им. В.А.Стеклова Российской академии наук)
|-
| 22 апреля 2022 г.
| '''О некоторых приложениях теории сложности алгоритмов к прикладным задачам криптографии'''. [[Media: mvk-22-04-22.pdf | Аннотация доклада]]
| '''Смышляев Станислав Витальевич''' (Москва, ООО «КРИПТО-ПРО», Технический комитет по стандартизации «Криптографическая защита информации» (ТК 26))
|-
| 15 апреля 2022 г.
| '''Мультиоперации на конечных множествах'''. [[Media: mvk-22-04-15.pdf | Аннотация доклада]]
| '''Перязев Николай Алексеевич''' (Санкт-Петербург, СПбГЭТУ «ЛЭТИ»)
|-
| 8 апреля 2022 г.
| '''Темпы роста произвольных конечных структур'''. [[Media: mvk-22-04-08.pdf | Аннотация доклада]]
| '''Комков Степан Алексеевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 1 апреля 2022 г.
| '''Квантовое хеширование: основные свойства, эффективные конструкции, реализация'''. [[Media: mvk-22-04-01.pdf | Аннотация доклада]]
| '''Аблаев Фарид Мансурович, Аблаев Марат Фаридович''' (Казань, Казанский (Приволжский) федеральный университет)
|-
| 25 марта 2022 г.
| '''Асимптотически хорошие семейства классических и квантовых LDPC кодов'''. [[Media: mvk-22-03-25.pdf | Аннотация доклада]]
| '''Пантелеев Павел Анатольевич, Калачев Глеб Вячеславович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 18 марта 2022 г.
| '''Предикаты k-значной логики и задача удовлетворения ограничениям'''. [[Media: mvk-22-03-18.pdf | Аннотация доклада]]
| '''Жук Дмитрий Николаевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 11 марта 2022 г.
| '''Аддитивные представления и замкнутые классы функций многозначной логики'''. [[Media: mvk-22-03-11.pdf | Аннотация доклада]]
| '''Мещанинов Дмитрий Германович''' (Москва, НИУ «МЭИ»)
|-
| 25 февраля 2022 г.
| '''Удивительный жадный алгоритм'''. [[Media: mvk-22-02-25.pdf | Аннотация доклада]]
| '''Куликов Александр Сергеевич''' (Санкт-Петербург, Санкт-Петербургский государственный университет)
|-
| 18 февраля 2022 г.
| '''Линейное хеширование'''. [[Media: mvk-22-02-18.pdf | Аннотация доклада]]
| '''Чашкин Александр Викторович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 17 декабря 2021 г.
| '''Семинар памяти О.М. Касим-Заде (29.04.1953-22.12.2020)'''. [[Media: mvk-21-12-17.pdf | Аннотация доклада]]
| '''Кочергин Вадим Васильевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 10 декабря 2021 г.
| '''Семинар, посвященный 70-летию со дня рождения проф. А.Б. Угольникова'''. [[Media: mvk-21-12-10.pdf | Аннотация доклада]]
| '''Колпаков Роман Максимович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 3 декабря 2021 г.
| '''Синтез и сложность бинарных программ с некоторыми структурными ограничениями'''. [[Media: mvk-21-12-03.pdf | Аннотация доклада]]
| '''Жуков Владимир Владимирович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 26 ноября 2021 г.
| '''Об исследовании вопросов полноты в классе линейных автоматов над подкольцами рациональных чисел'''. [[Media: mvk-21-11-26.pdf | Аннотация доклада]]
| '''Ронжин Дмитрий Владимирович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 19 ноября 2021 г.
| '''Булевы биюнктивные функции и порождаемые ими системы булевых уравнений'''. [[Media: mvk-21-11-19.pdf | Аннотация доклада]]
| '''Тарасов Алексей Вячеславович''' (Москва, Федеральное учебно-методическое объединение ВУЗов в области информационной безопасности (ФУМО ВО ИБ))
|-
| 12 ноября 2021 г.
| '''Математические модели передачи информации через зашумленные скрытые каналы'''. [[Media: mvk-21-11-12.pdf | Аннотация доклада]]
| '''Казаков Илья Борисович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 29 октября 2021 г.
| '''Асимптотика логарифма числа наборов, k-свободных от решений, в абелевых группах'''. [[Media: mvk-21-10-29.pdf | Аннотация доклада]]
| '''Саргсян Ваге Гнелович''' (Ереван, Институт проблем информатики и автоматизации Национальной Академии Наук Республики Армения)
|-
| 22 октября 2021 г.
| '''Задачи дискретной оптимизации в спорте'''. [[Media: mvk-21-10-22.pdf | Аннотация доклада]]
| '''Дагаев Дмитрий Александрович''' (Москва, НИУ ВШЭ)
|-
| 8 октября 2021 г.
| '''О сложности реализации систем одночленов схемами композиции'''. [[Media: mvk-21-10-08.pdf | Аннотация доклада]]
| '''Корнеев Сергей Александрович''' (Москва, МГУ имени М.В. Ломоносова, ИПМ им. М.В. Келдыша РАН)
|-
|}

==2020-2021 учебный год==

'''Расписание докладов'''

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 28 мая 2021 г.
| '''Пороговые функции и пороговые схемы'''. [[Media: mvk-21-05-28.pdf | Аннотация доклада]]
| '''Подольский Владимир Владимирович''' (Москва, МИАН им. В.А.Стеклова)
|-
| 21 мая 2021 г.
| '''Регистровые машины со счетчиками'''. [[Media: mvk-21-05-21.pdf | Аннотация доклада]]
| '''Савицкий Игорь Владимирович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 14 мая 2021 г.
| '''Арифметика фибоначчиевых кодов. Асимптотически быстрая сортировка. Метод Храпченко для k-местных базисов'''. [[Media: mvk-21-05-14.pdf | Аннотация доклада]]
| '''Сергеев Игорь Сергеевич''' (Москва, ФГУП «НИИ "Квант"»)
|-
| 30 апреля 2021 г.
| '''Полнота и выразимость в классах линейных автоматов'''. [[Media: mvk-21-04-30.pdf | Аннотация доклада]]
| '''Часовских Анатолий Александрович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 16 апреля 2021 г.
| '''Преобразования конечных случайных величин системами функций k-значной логики и вопросы аппроксимируемости'''. [[Media: mvk-21-04-16.pdf | Аннотация доклада]]
| '''Яшунский Алексей Дмитриевич''' (Москва, Институт прикладной математики им. М.В. Келдыша РАН)
|-
|}

Математические вопросы кибернетики

2025-12-22T17:06:25Z

SeleznevaSN: /* 2025-2026 учебный год */

[[Mathematical Problems of Cybernetics]]

Научно-исследовательский семинар кафедр [http://new.math.msu.su/department/dm/ '''дискретной математики'''] и [http://intsys.msu.ru/ '''математической теории интеллектуальных систем'''] механико-математического факультета и [https://mk.cs.msu.ru/index.php/Заглавная_страница '''математической кибернетики'''] факультета вычислительной математики и кибернетики МГУ имени М.В. Ломоносова.

'''Цель семинара''': обсуждение современных задач математической кибернетики и широкого круга смежных вопросов и представление наиболее значимых результатов в этой области.

'''Традиции семинара''': семинар продолжает научно-исследовательский семинар по математическим вопросам кибернетики, который более 30 лет проводился в Московском университете под руководством [https://mk.cs.msu.ru/index.php/Яблонский_Сергей_Всеволодович '''Сергея Всеволодовича Яблонского'''] и [http://new.math.msu.su/obl '''Олега Борисовича Лупанова'''].

==2025-2026 учебный год==

В '''2025-2026 учебном году''' семинар проводится удаленно '''по пятницам''' в '''19-00''' (по московскому времени) по объявлениям.

Заседания проводятся на платформе zoom, идентификатор конференции: 830 6246 3909, код доступа: 947173.

По вопросам, связанным с работой семинара, можно писать по эл. почте '''mvk@cs.msu.ru''' Селезневой Светлане Николаевне.

'''Расписание докладов'''

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 26 декабря 2025 г.
| '''Семинар к 90-летию со дня рождения Н.А. Карповой.'''
|'''Кочергин Вадим Васильевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 19 сентября 2025 г.
| '''О свойствах конечно порождающих систем булевых функций для классов рациональных вероятностей'''. [[Media: mvk-25-09-19.pdf | Аннотация доклада]]
|'''Трифонова Екатерина Евгеньевна''' (Москва, ИМП им. М.В. Келдыша)
|-
|}

==2024-2025 учебный год==

'''Расписание докладов'''

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 23 мая 2025 г.
| '''Метод граничных функционалов и нижние оценки числа антицепей в некоторых ранжированных ЧУМ'''. [[Media: mvk-25-05-23.pdf | Аннотация доклада]]
|'''Андреева Татьяна Владимировна''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 25 апреля 2025 г.
| '''Асимптотически точные оценки сложности некоторых функций и систем функций в модели клеточных схем'''. [[Media: mvk-25-04-25.pdf | Аннотация доклада]]
|'''Зизов Вадим Сергеевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 14 марта 2025 г.
| '''О некоторых свойствах конечных квазигрупп'''. [[Media: mvk-25-03-14.pdf | Аннотация доклада]]
|'''Галатенко Алексей Владимирович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 28 февраля 2025 г.
| '''Семинар памяти Л.А. Шоломова'''.
|'''Чашкин Александр Викторович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 25 октября 2024 г.
| '''Нижние оценки сложности линейных операторов над GF(2)'''. [[Media: mvk-24-10-25.pdf | Аннотация доклада]]
|'''Сергеев Игорь Сергеевич''' (Москва, Научно-исследовательский институт «Квант»)
|-
|}

==2023-2024 учебный год==

'''Расписание докладов'''

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 17 мая 2024 г.
| '''Оценки длин минимальных тестов для аргументов функций при подстановке констант, алгебраических операциях и сдвигах'''. [[Media: mvk-24-05-17.pdf | Аннотация доклада]]
|'''Антюфеев Григорий Валерьевич''' (Москва, «НИИМА «ПРОГРЕСС»»)
|-
| 5 апреля 2024 г.
| '''Семинар, посвященный 85-летию проф. А.А. Сапоженко'''. [[Media: mvk-24-04-05.pdf | Аннотация доклада]]
|
|-
| 22 марта 2024 г.
| '''Многомерные матрицы в алгебраической теории гиперграфов'''. [[Media: mvk-24-03-22.pdf | Аннотация доклада]]
| '''Тараненко Анна Александровна''' (Новосибирск, Институт математики имени С.Л. Cоболева СО РАН)
|-
| 15 марта 2024 г.
| '''Симметричные функции k-значной логики и универсальные алгоритмы для задачи удовлетворения ограничений'''. [[Media: mvk-24-03-15.pdf | Аннотация доклада]]
| '''Жук Дмитрий Николаевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 15 декабря 2023 г.
| '''Коммутаторная длина степеней в свободных произведениях групп'''. [[Media: mvk-23-12-15.pdf | Аннотация доклада]]
| '''Березнюк Вадим Юрьевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 8 декабря 2023 г.
| '''Реализация вероятностных автоматов на однородных вычислительных системах при использовании арифметики полей Галуа'''. [[Media: mvk-23-12-08.pdf | Аннотация доклада]]
| '''Шалагин Сергей Викторович''' (Казань, Казанский национальный исследовательский технический университет им. А.Н.Туполева – КАИ)
|-
| 1 декабря 2023 г.
| '''О сложности и структуре некоторых типов контактных схем для ряда симметрических булевых функций'''. [[Media: mvk-23-12-01.pdf | Аннотация доклада]]
| '''Попов Евгений Александрович''' (Москва, фирма Примариус)
|-
| 17 ноября 2023 г.
| '''Правильные семейства дискретных функций: эквивалентные определения и свойства'''. [[Media: mvk-23-11-17.pdf | Аннотация доклада]]
| '''Царегородцев Кирилл Денисович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 6 октября 2023 г.
| '''Компьютерное моделирование логических процессов'''. [[Media: mvk-23-10-06.pdf | Аннотация доклада]]
| '''Подколзин Александр Сергеевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
|}

==2022-2023 учебный год==

'''Расписание докладов'''

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 19 мая 2023 г.
| '''Конструкции и свойства корреляционно-иммунных и платовидных булевых функций'''. [[Media: mvk-23-05-19.pdf | Аннотация доклада]]
| '''Таранников Юрий Валерьевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 12 мая 2023 г.
| '''О соотношениях между активностью схем из функциональных элементов и положительной чувствительностью функций алгебры логики'''. [[Media: mvk-23-05-12.pdf | Аннотация доклада]]
| '''Местецкий Михаил Александрович''', '''Шуплецов Михаил Сергеевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 28 апреля 2023 г.
| '''Семинар, посвященный 70-летию со дня рождения О. М. Касим-Заде'''. [[Media: mvk-23-04-28.pdf | Аннотация]]
|
|-
| 21 апреля 2023 г.
| '''Дихотомия сложности кванторной задачи удовлетворения ограничениям'''. [[Media: mvk-23-04-21.pdf | Аннотация доклада]]
| '''Жук Дмитрий Николаевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 31 марта 2023 г.
| '''О числе субпериодичностей в двоичных формальных словах'''. [[Media: mvk-23-03-31.pdf | Аннотация доклада]]
| '''Колпаков Роман Максимович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 17 марта 2023 г.
| '''Некоторые свойства сложностных классов AC^0 и TC^0'''. [[Media: mvk-23-03-17.pdf | Аннотация доклада]]
| '''Савицкий Игорь Владимирович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 3 марта 2023 г.
| '''Оценки энергопотребления объемных схем'''. [[Media: mvk-23-03-03.pdf | Аннотация доклада]]
| '''Ефимов Алексей Андреевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 17 февраля 2023 г.
| '''Об асимптотике роста мощности слоев в декартовых степенях некоторых взвешенных множеств'''. [[Media: mvk-23-02-17.pdf | Аннотация доклада]]
| '''Андреева Татьяна Владимировна''' (Москва, МГТУ имени Н.Э. Баумана; МГУ имени М.В. Ломоносова), '''Семенов Юрий Станиславович'''
|-
| 16 декабря 2022 г.
| '''Памяти Валерия Борисовича Кудряцева'''. [[Media: mvk-22-12-16.pdf | Аннотация доклада]]
| '''Гасанов Э.Э., Алешин С.В., Часовских А.А., Сыркин Г.И.'''
|-
| 9 декабря 2022 г.
| '''Тензорные сети для эффективной симуляции квантовых вычислений'''. [[Media: mvk-22-12-09.pdf | Аннотация доклада]]
| '''Пантелеев Павел Анатольевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 11 ноября 2022 г.
| '''Цифровая подпись на основе кодов, определяющих изображения с точностью до аффинных преобразований'''. [[Media: mvk-22-11-11.pdf | Аннотация доклада]]
| '''Козлов Вадим Никитович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 28 октября 2022 г.
| '''О математических моделях и структурных графах в теории механизмов'''. [[Media: mvk-22-10-28.pdf | Аннотация доклада]]
| '''Ковалев Михаил Дмитриевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 21 октября 2022 г.
| '''О перманентах (0, 1)- и (-1,1)-матриц'''. [[Media: mvk-22-10-21.pdf | Аннотация доклада]]
| '''Таранин Константин Александрович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 14 октября 2022 г.
| '''Параметро-эффективная расшифровка булевых функций'''. [[Media: mvk-22-10-14.pdf | Аннотация доклада]]
| '''Быстрыгова Анастасия Викторовна''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 7 октября 2022 г.
| '''Задачи Беллмана, Кнута, Лупанова, Пиппенджера и их вариации как обобщения задачи об аддитивных цепочках'''. [[Media: mvk-22-10-07.pdf | Аннотация доклада]]
| '''Кочергин Вадим Васильевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 30 сентября 2022 г.
| '''Асимптотически точные оценки сложности некоторых функций в модели клеточных схем'''. [[Media: mvk-22-09-30.pdf | Аннотация доклада]]
| '''Ложкин Сергей Андреевич, Зизов Вадим Сергеевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
|}

==2021-2022 учебный год==

'''Расписание докладов'''

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 29 апреля 2022 г.
| '''Размерность Вейсфейлера-Лемана алгебраических и комбинаторных структур'''. [[Media: mvk-22-04-29.pdf | Аннотация доклада]]
| '''Пономаренко Илья Николаевич''' (Санкт-Петербург, Санкт-Петербургское отделение Математического института им. В.А.Стеклова Российской академии наук)
|-
| 22 апреля 2022 г.
| '''О некоторых приложениях теории сложности алгоритмов к прикладным задачам криптографии'''. [[Media: mvk-22-04-22.pdf | Аннотация доклада]]
| '''Смышляев Станислав Витальевич''' (Москва, ООО «КРИПТО-ПРО», Технический комитет по стандартизации «Криптографическая защита информации» (ТК 26))
|-
| 15 апреля 2022 г.
| '''Мультиоперации на конечных множествах'''. [[Media: mvk-22-04-15.pdf | Аннотация доклада]]
| '''Перязев Николай Алексеевич''' (Санкт-Петербург, СПбГЭТУ «ЛЭТИ»)
|-
| 8 апреля 2022 г.
| '''Темпы роста произвольных конечных структур'''. [[Media: mvk-22-04-08.pdf | Аннотация доклада]]
| '''Комков Степан Алексеевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 1 апреля 2022 г.
| '''Квантовое хеширование: основные свойства, эффективные конструкции, реализация'''. [[Media: mvk-22-04-01.pdf | Аннотация доклада]]
| '''Аблаев Фарид Мансурович, Аблаев Марат Фаридович''' (Казань, Казанский (Приволжский) федеральный университет)
|-
| 25 марта 2022 г.
| '''Асимптотически хорошие семейства классических и квантовых LDPC кодов'''. [[Media: mvk-22-03-25.pdf | Аннотация доклада]]
| '''Пантелеев Павел Анатольевич, Калачев Глеб Вячеславович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 18 марта 2022 г.
| '''Предикаты k-значной логики и задача удовлетворения ограничениям'''. [[Media: mvk-22-03-18.pdf | Аннотация доклада]]
| '''Жук Дмитрий Николаевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 11 марта 2022 г.
| '''Аддитивные представления и замкнутые классы функций многозначной логики'''. [[Media: mvk-22-03-11.pdf | Аннотация доклада]]
| '''Мещанинов Дмитрий Германович''' (Москва, НИУ «МЭИ»)
|-
| 25 февраля 2022 г.
| '''Удивительный жадный алгоритм'''. [[Media: mvk-22-02-25.pdf | Аннотация доклада]]
| '''Куликов Александр Сергеевич''' (Санкт-Петербург, Санкт-Петербургский государственный университет)
|-
| 18 февраля 2022 г.
| '''Линейное хеширование'''. [[Media: mvk-22-02-18.pdf | Аннотация доклада]]
| '''Чашкин Александр Викторович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 17 декабря 2021 г.
| '''Семинар памяти О.М. Касим-Заде (29.04.1953-22.12.2020)'''. [[Media: mvk-21-12-17.pdf | Аннотация доклада]]
| '''Кочергин Вадим Васильевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 10 декабря 2021 г.
| '''Семинар, посвященный 70-летию со дня рождения проф. А.Б. Угольникова'''. [[Media: mvk-21-12-10.pdf | Аннотация доклада]]
| '''Колпаков Роман Максимович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 3 декабря 2021 г.
| '''Синтез и сложность бинарных программ с некоторыми структурными ограничениями'''. [[Media: mvk-21-12-03.pdf | Аннотация доклада]]
| '''Жуков Владимир Владимирович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 26 ноября 2021 г.
| '''Об исследовании вопросов полноты в классе линейных автоматов над подкольцами рациональных чисел'''. [[Media: mvk-21-11-26.pdf | Аннотация доклада]]
| '''Ронжин Дмитрий Владимирович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 19 ноября 2021 г.
| '''Булевы биюнктивные функции и порождаемые ими системы булевых уравнений'''. [[Media: mvk-21-11-19.pdf | Аннотация доклада]]
| '''Тарасов Алексей Вячеславович''' (Москва, Федеральное учебно-методическое объединение ВУЗов в области информационной безопасности (ФУМО ВО ИБ))
|-
| 12 ноября 2021 г.
| '''Математические модели передачи информации через зашумленные скрытые каналы'''. [[Media: mvk-21-11-12.pdf | Аннотация доклада]]
| '''Казаков Илья Борисович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 29 октября 2021 г.
| '''Асимптотика логарифма числа наборов, k-свободных от решений, в абелевых группах'''. [[Media: mvk-21-10-29.pdf | Аннотация доклада]]
| '''Саргсян Ваге Гнелович''' (Ереван, Институт проблем информатики и автоматизации Национальной Академии Наук Республики Армения)
|-
| 22 октября 2021 г.
| '''Задачи дискретной оптимизации в спорте'''. [[Media: mvk-21-10-22.pdf | Аннотация доклада]]
| '''Дагаев Дмитрий Александрович''' (Москва, НИУ ВШЭ)
|-
| 8 октября 2021 г.
| '''О сложности реализации систем одночленов схемами композиции'''. [[Media: mvk-21-10-08.pdf | Аннотация доклада]]
| '''Корнеев Сергей Александрович''' (Москва, МГУ имени М.В. Ломоносова, ИПМ им. М.В. Келдыша РАН)
|-
|}

==2020-2021 учебный год==

'''Расписание докладов'''

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 28 мая 2021 г.
| '''Пороговые функции и пороговые схемы'''. [[Media: mvk-21-05-28.pdf | Аннотация доклада]]
| '''Подольский Владимир Владимирович''' (Москва, МИАН им. В.А.Стеклова)
|-
| 21 мая 2021 г.
| '''Регистровые машины со счетчиками'''. [[Media: mvk-21-05-21.pdf | Аннотация доклада]]
| '''Савицкий Игорь Владимирович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 14 мая 2021 г.
| '''Арифметика фибоначчиевых кодов. Асимптотически быстрая сортировка. Метод Храпченко для k-местных базисов'''. [[Media: mvk-21-05-14.pdf | Аннотация доклада]]
| '''Сергеев Игорь Сергеевич''' (Москва, ФГУП «НИИ "Квант"»)
|-
| 30 апреля 2021 г.
| '''Полнота и выразимость в классах линейных автоматов'''. [[Media: mvk-21-04-30.pdf | Аннотация доклада]]
| '''Часовских Анатолий Александрович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 16 апреля 2021 г.
| '''Преобразования конечных случайных величин системами функций k-значной логики и вопросы аппроксимируемости'''. [[Media: mvk-21-04-16.pdf | Аннотация доклада]]
| '''Яшунский Алексей Дмитриевич''' (Москва, Институт прикладной математики им. М.В. Келдыша РАН)
|-
|}

Математические вопросы кибернетики

2025-12-22T17:05:44Z

SeleznevaSN: /* 2025-2026 учебный год */

[[Mathematical Problems of Cybernetics]]

Научно-исследовательский семинар кафедр [http://new.math.msu.su/department/dm/ '''дискретной математики'''] и [http://intsys.msu.ru/ '''математической теории интеллектуальных систем'''] механико-математического факультета и [https://mk.cs.msu.ru/index.php/Заглавная_страница '''математической кибернетики'''] факультета вычислительной математики и кибернетики МГУ имени М.В. Ломоносова.

'''Цель семинара''': обсуждение современных задач математической кибернетики и широкого круга смежных вопросов и представление наиболее значимых результатов в этой области.

'''Традиции семинара''': семинар продолжает научно-исследовательский семинар по математическим вопросам кибернетики, который более 30 лет проводился в Московском университете под руководством [https://mk.cs.msu.ru/index.php/Яблонский_Сергей_Всеволодович '''Сергея Всеволодовича Яблонского'''] и [http://new.math.msu.su/obl '''Олега Борисовича Лупанова'''].

==2025-2026 учебный год==

В '''2025-2026 учебном году''' семинар проводится удаленно '''по пятницам''' в '''19-00''' (по московскому времени) по объявлениям.

Заседания проводятся на платформе zoom, идентификатор конференции: 830 6246 3909, код доступа: 947173.

По вопросам, связанным с работой семинара, можно писать по эл. почте '''mvk@cs.msu.ru''' Селезневой Светлане Николаевне.

'''Расписание докладов'''

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 26 декабря 2025 г.
| '''Семинар к 90-летию со дня рождения Н.А. Карповой.'''.
|'''Кочергин Вадим Васильевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 19 сентября 2025 г.
| '''О свойствах конечно порождающих систем булевых функций для классов рациональных вероятностей'''. [[Media: mvk-25-09-19.pdf | Аннотация доклада]]
|'''Трифонова Екатерина Евгеньевна''' (Москва, ИМП им. М.В. Келдыша)
|-
|}

==2024-2025 учебный год==

'''Расписание докладов'''

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 23 мая 2025 г.
| '''Метод граничных функционалов и нижние оценки числа антицепей в некоторых ранжированных ЧУМ'''. [[Media: mvk-25-05-23.pdf | Аннотация доклада]]
|'''Андреева Татьяна Владимировна''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 25 апреля 2025 г.
| '''Асимптотически точные оценки сложности некоторых функций и систем функций в модели клеточных схем'''. [[Media: mvk-25-04-25.pdf | Аннотация доклада]]
|'''Зизов Вадим Сергеевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 14 марта 2025 г.
| '''О некоторых свойствах конечных квазигрупп'''. [[Media: mvk-25-03-14.pdf | Аннотация доклада]]
|'''Галатенко Алексей Владимирович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 28 февраля 2025 г.
| '''Семинар памяти Л.А. Шоломова'''.
|'''Чашкин Александр Викторович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 25 октября 2024 г.
| '''Нижние оценки сложности линейных операторов над GF(2)'''. [[Media: mvk-24-10-25.pdf | Аннотация доклада]]
|'''Сергеев Игорь Сергеевич''' (Москва, Научно-исследовательский институт «Квант»)
|-
|}

==2023-2024 учебный год==

'''Расписание докладов'''

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 17 мая 2024 г.
| '''Оценки длин минимальных тестов для аргументов функций при подстановке констант, алгебраических операциях и сдвигах'''. [[Media: mvk-24-05-17.pdf | Аннотация доклада]]
|'''Антюфеев Григорий Валерьевич''' (Москва, «НИИМА «ПРОГРЕСС»»)
|-
| 5 апреля 2024 г.
| '''Семинар, посвященный 85-летию проф. А.А. Сапоженко'''. [[Media: mvk-24-04-05.pdf | Аннотация доклада]]
|
|-
| 22 марта 2024 г.
| '''Многомерные матрицы в алгебраической теории гиперграфов'''. [[Media: mvk-24-03-22.pdf | Аннотация доклада]]
| '''Тараненко Анна Александровна''' (Новосибирск, Институт математики имени С.Л. Cоболева СО РАН)
|-
| 15 марта 2024 г.
| '''Симметричные функции k-значной логики и универсальные алгоритмы для задачи удовлетворения ограничений'''. [[Media: mvk-24-03-15.pdf | Аннотация доклада]]
| '''Жук Дмитрий Николаевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 15 декабря 2023 г.
| '''Коммутаторная длина степеней в свободных произведениях групп'''. [[Media: mvk-23-12-15.pdf | Аннотация доклада]]
| '''Березнюк Вадим Юрьевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 8 декабря 2023 г.
| '''Реализация вероятностных автоматов на однородных вычислительных системах при использовании арифметики полей Галуа'''. [[Media: mvk-23-12-08.pdf | Аннотация доклада]]
| '''Шалагин Сергей Викторович''' (Казань, Казанский национальный исследовательский технический университет им. А.Н.Туполева – КАИ)
|-
| 1 декабря 2023 г.
| '''О сложности и структуре некоторых типов контактных схем для ряда симметрических булевых функций'''. [[Media: mvk-23-12-01.pdf | Аннотация доклада]]
| '''Попов Евгений Александрович''' (Москва, фирма Примариус)
|-
| 17 ноября 2023 г.
| '''Правильные семейства дискретных функций: эквивалентные определения и свойства'''. [[Media: mvk-23-11-17.pdf | Аннотация доклада]]
| '''Царегородцев Кирилл Денисович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 6 октября 2023 г.
| '''Компьютерное моделирование логических процессов'''. [[Media: mvk-23-10-06.pdf | Аннотация доклада]]
| '''Подколзин Александр Сергеевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
|}

==2022-2023 учебный год==

'''Расписание докладов'''

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 19 мая 2023 г.
| '''Конструкции и свойства корреляционно-иммунных и платовидных булевых функций'''. [[Media: mvk-23-05-19.pdf | Аннотация доклада]]
| '''Таранников Юрий Валерьевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 12 мая 2023 г.
| '''О соотношениях между активностью схем из функциональных элементов и положительной чувствительностью функций алгебры логики'''. [[Media: mvk-23-05-12.pdf | Аннотация доклада]]
| '''Местецкий Михаил Александрович''', '''Шуплецов Михаил Сергеевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 28 апреля 2023 г.
| '''Семинар, посвященный 70-летию со дня рождения О. М. Касим-Заде'''. [[Media: mvk-23-04-28.pdf | Аннотация]]
|
|-
| 21 апреля 2023 г.
| '''Дихотомия сложности кванторной задачи удовлетворения ограничениям'''. [[Media: mvk-23-04-21.pdf | Аннотация доклада]]
| '''Жук Дмитрий Николаевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 31 марта 2023 г.
| '''О числе субпериодичностей в двоичных формальных словах'''. [[Media: mvk-23-03-31.pdf | Аннотация доклада]]
| '''Колпаков Роман Максимович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 17 марта 2023 г.
| '''Некоторые свойства сложностных классов AC^0 и TC^0'''. [[Media: mvk-23-03-17.pdf | Аннотация доклада]]
| '''Савицкий Игорь Владимирович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 3 марта 2023 г.
| '''Оценки энергопотребления объемных схем'''. [[Media: mvk-23-03-03.pdf | Аннотация доклада]]
| '''Ефимов Алексей Андреевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 17 февраля 2023 г.
| '''Об асимптотике роста мощности слоев в декартовых степенях некоторых взвешенных множеств'''. [[Media: mvk-23-02-17.pdf | Аннотация доклада]]
| '''Андреева Татьяна Владимировна''' (Москва, МГТУ имени Н.Э. Баумана; МГУ имени М.В. Ломоносова), '''Семенов Юрий Станиславович'''
|-
| 16 декабря 2022 г.
| '''Памяти Валерия Борисовича Кудряцева'''. [[Media: mvk-22-12-16.pdf | Аннотация доклада]]
| '''Гасанов Э.Э., Алешин С.В., Часовских А.А., Сыркин Г.И.'''
|-
| 9 декабря 2022 г.
| '''Тензорные сети для эффективной симуляции квантовых вычислений'''. [[Media: mvk-22-12-09.pdf | Аннотация доклада]]
| '''Пантелеев Павел Анатольевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 11 ноября 2022 г.
| '''Цифровая подпись на основе кодов, определяющих изображения с точностью до аффинных преобразований'''. [[Media: mvk-22-11-11.pdf | Аннотация доклада]]
| '''Козлов Вадим Никитович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 28 октября 2022 г.
| '''О математических моделях и структурных графах в теории механизмов'''. [[Media: mvk-22-10-28.pdf | Аннотация доклада]]
| '''Ковалев Михаил Дмитриевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 21 октября 2022 г.
| '''О перманентах (0, 1)- и (-1,1)-матриц'''. [[Media: mvk-22-10-21.pdf | Аннотация доклада]]
| '''Таранин Константин Александрович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 14 октября 2022 г.
| '''Параметро-эффективная расшифровка булевых функций'''. [[Media: mvk-22-10-14.pdf | Аннотация доклада]]
| '''Быстрыгова Анастасия Викторовна''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 7 октября 2022 г.
| '''Задачи Беллмана, Кнута, Лупанова, Пиппенджера и их вариации как обобщения задачи об аддитивных цепочках'''. [[Media: mvk-22-10-07.pdf | Аннотация доклада]]
| '''Кочергин Вадим Васильевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 30 сентября 2022 г.
| '''Асимптотически точные оценки сложности некоторых функций в модели клеточных схем'''. [[Media: mvk-22-09-30.pdf | Аннотация доклада]]
| '''Ложкин Сергей Андреевич, Зизов Вадим Сергеевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
|}

==2021-2022 учебный год==

'''Расписание докладов'''

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 29 апреля 2022 г.
| '''Размерность Вейсфейлера-Лемана алгебраических и комбинаторных структур'''. [[Media: mvk-22-04-29.pdf | Аннотация доклада]]
| '''Пономаренко Илья Николаевич''' (Санкт-Петербург, Санкт-Петербургское отделение Математического института им. В.А.Стеклова Российской академии наук)
|-
| 22 апреля 2022 г.
| '''О некоторых приложениях теории сложности алгоритмов к прикладным задачам криптографии'''. [[Media: mvk-22-04-22.pdf | Аннотация доклада]]
| '''Смышляев Станислав Витальевич''' (Москва, ООО «КРИПТО-ПРО», Технический комитет по стандартизации «Криптографическая защита информации» (ТК 26))
|-
| 15 апреля 2022 г.
| '''Мультиоперации на конечных множествах'''. [[Media: mvk-22-04-15.pdf | Аннотация доклада]]
| '''Перязев Николай Алексеевич''' (Санкт-Петербург, СПбГЭТУ «ЛЭТИ»)
|-
| 8 апреля 2022 г.
| '''Темпы роста произвольных конечных структур'''. [[Media: mvk-22-04-08.pdf | Аннотация доклада]]
| '''Комков Степан Алексеевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 1 апреля 2022 г.
| '''Квантовое хеширование: основные свойства, эффективные конструкции, реализация'''. [[Media: mvk-22-04-01.pdf | Аннотация доклада]]
| '''Аблаев Фарид Мансурович, Аблаев Марат Фаридович''' (Казань, Казанский (Приволжский) федеральный университет)
|-
| 25 марта 2022 г.
| '''Асимптотически хорошие семейства классических и квантовых LDPC кодов'''. [[Media: mvk-22-03-25.pdf | Аннотация доклада]]
| '''Пантелеев Павел Анатольевич, Калачев Глеб Вячеславович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 18 марта 2022 г.
| '''Предикаты k-значной логики и задача удовлетворения ограничениям'''. [[Media: mvk-22-03-18.pdf | Аннотация доклада]]
| '''Жук Дмитрий Николаевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 11 марта 2022 г.
| '''Аддитивные представления и замкнутые классы функций многозначной логики'''. [[Media: mvk-22-03-11.pdf | Аннотация доклада]]
| '''Мещанинов Дмитрий Германович''' (Москва, НИУ «МЭИ»)
|-
| 25 февраля 2022 г.
| '''Удивительный жадный алгоритм'''. [[Media: mvk-22-02-25.pdf | Аннотация доклада]]
| '''Куликов Александр Сергеевич''' (Санкт-Петербург, Санкт-Петербургский государственный университет)
|-
| 18 февраля 2022 г.
| '''Линейное хеширование'''. [[Media: mvk-22-02-18.pdf | Аннотация доклада]]
| '''Чашкин Александр Викторович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 17 декабря 2021 г.
| '''Семинар памяти О.М. Касим-Заде (29.04.1953-22.12.2020)'''. [[Media: mvk-21-12-17.pdf | Аннотация доклада]]
| '''Кочергин Вадим Васильевич''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 10 декабря 2021 г.
| '''Семинар, посвященный 70-летию со дня рождения проф. А.Б. Угольникова'''. [[Media: mvk-21-12-10.pdf | Аннотация доклада]]
| '''Колпаков Роман Максимович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 3 декабря 2021 г.
| '''Синтез и сложность бинарных программ с некоторыми структурными ограничениями'''. [[Media: mvk-21-12-03.pdf | Аннотация доклада]]
| '''Жуков Владимир Владимирович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 26 ноября 2021 г.
| '''Об исследовании вопросов полноты в классе линейных автоматов над подкольцами рациональных чисел'''. [[Media: mvk-21-11-26.pdf | Аннотация доклада]]
| '''Ронжин Дмитрий Владимирович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 19 ноября 2021 г.
| '''Булевы биюнктивные функции и порождаемые ими системы булевых уравнений'''. [[Media: mvk-21-11-19.pdf | Аннотация доклада]]
| '''Тарасов Алексей Вячеславович''' (Москва, Федеральное учебно-методическое объединение ВУЗов в области информационной безопасности (ФУМО ВО ИБ))
|-
| 12 ноября 2021 г.
| '''Математические модели передачи информации через зашумленные скрытые каналы'''. [[Media: mvk-21-11-12.pdf | Аннотация доклада]]
| '''Казаков Илья Борисович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 29 октября 2021 г.
| '''Асимптотика логарифма числа наборов, k-свободных от решений, в абелевых группах'''. [[Media: mvk-21-10-29.pdf | Аннотация доклада]]
| '''Саргсян Ваге Гнелович''' (Ереван, Институт проблем информатики и автоматизации Национальной Академии Наук Республики Армения)
|-
| 22 октября 2021 г.
| '''Задачи дискретной оптимизации в спорте'''. [[Media: mvk-21-10-22.pdf | Аннотация доклада]]
| '''Дагаев Дмитрий Александрович''' (Москва, НИУ ВШЭ)
|-
| 8 октября 2021 г.
| '''О сложности реализации систем одночленов схемами композиции'''. [[Media: mvk-21-10-08.pdf | Аннотация доклада]]
| '''Корнеев Сергей Александрович''' (Москва, МГУ имени М.В. Ломоносова, ИПМ им. М.В. Келдыша РАН)
|-
|}

==2020-2021 учебный год==

'''Расписание докладов'''

{| class="wide" width="100%"
! Дата
! Доклад
! Докладчик
|-
| 28 мая 2021 г.
| '''Пороговые функции и пороговые схемы'''. [[Media: mvk-21-05-28.pdf | Аннотация доклада]]
| '''Подольский Владимир Владимирович''' (Москва, МИАН им. В.А.Стеклова)
|-
| 21 мая 2021 г.
| '''Регистровые машины со счетчиками'''. [[Media: mvk-21-05-21.pdf | Аннотация доклада]]
| '''Савицкий Игорь Владимирович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 14 мая 2021 г.
| '''Арифметика фибоначчиевых кодов. Асимптотически быстрая сортировка. Метод Храпченко для k-местных базисов'''. [[Media: mvk-21-05-14.pdf | Аннотация доклада]]
| '''Сергеев Игорь Сергеевич''' (Москва, ФГУП «НИИ "Квант"»)
|-
| 30 апреля 2021 г.
| '''Полнота и выразимость в классах линейных автоматов'''. [[Media: mvk-21-04-30.pdf | Аннотация доклада]]
| '''Часовских Анатолий Александрович''' (Москва, МГУ имени М.В. Ломоносова)
|-
| 16 апреля 2021 г.
| '''Преобразования конечных случайных величин системами функций k-значной логики и вопросы аппроксимируемости'''. [[Media: mvk-21-04-16.pdf | Аннотация доклада]]
| '''Яшунский Алексей Дмитриевич''' (Москва, Институт прикладной математики им. М.В. Келдыша РАН)
|-
|}