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

   Список участников семинара (в закрытом доступе)

С чего начинался проект: Бруно Бухбергер в ЛЭТИ (февраль 2015 года)

(интервью Бухбергера Роману Евгеньевичу Спиридонову - кафедра АПУ ЛЭТИ - во время этого визита)


Бруно Бухбергер в ЛЭТИ февраль 2015-2.png   Бруно Бухбергер в ЛЭТИ февраль 2015.png


Во время визита Бруно Бухбергер рассказал, что читает для первокурсников необычный курс по математике. По нашей просьбе он прислал конспект этой книги: "Б.Бухбергер, Ф. Лихтенбергер. Математика для компьютерных специалистов. Часть I, 13 сентября 2015 года".
К сожалению, конспект оказался на немецком. Тогда из студентов, изучающих немецкий язык, была создана группа переводчиков, в неё вошли:
Елизавета Карпова, Елизавета Козлова, Элина Гумерова, Дмитрий Братковский, Артём Щербаков, Efimenko, Влад Грабнюк, Глеб Масюк, Михаил Любарец, Хатбуллина Лейла, Почанин  Роман, Васильев Анатолий, Сергей Стафеев. Студенты справились с переводом, хотя не все, и не весь перевод можно считать качественным. Однако конспект был собран в ТеХе и его pdf-версию вы можете прочитать (файлы прилагаются к странице).

Спецкурс Васильева-2.png

          Следующее событие: лекции Н.Н.Васильева

“Три сюжета по компьютерной математике” 

(март - май 2015 года)


Участникам семинара полезно прослушать цикл из 4 лекций Н.Н.Васильева

по трём сюжетам компьютерной алгебры (весна 2015 год):

Лекция 1: Быстрое вычисление полиномов.

Лекция 2: Аддитивные цепочки

Лекция 3: Факторизация полиномов (разложение на множители)

Лекция 4: Полиномиальные уравнения


                       Сайт с конспектами первых трёх лекций
               
       

      


 Теку
щее мероприятие: семинар по алгоритмической математики (руководитель  Н.Н.Васильев)


Первое (организационное) заседание в осеннем семестре 2018 года (21 сентября 2018, ауд. 5427, 17.20)

Выступил руководитель семинара Н.Н.Васильев, который представил направления работы семинара и примерную тематику докладов. В том числе, были анонсированы следующие выступления: доклад известного ученого в области теории сложности вычислений Димы Григорьева, доклад Александра Тискина по теории параллельных вычислений (теория “водорослей”) и доклад Семёна Григорьева по теории формальных грамматик.


Второе заседание в осеннем семестре 2018 года (5 октября 2018, ауд. 5427, 17.20) (презентация) (видео)

Докладчик: Семён Вячеславович Григорьев, к.ф.-м.наук, преподаватель математико-механического факультета СПбГУ, сотрудник фирмы JetBrains

Название. "Формальные языки: практическое применение и теоретические вопросы"

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

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


Третье заседание в осеннем семестре 2018 года (19 октября 2018, ауд. 5427, 17.20) (видео)

Докладчик: Николай Николаевич Васильев, с.н.с. ПОМИ, научный руководитель семинара
Тема: Дроби Фарея, дерево Штерна-Броко и отображения отрезка в себя.
Аннотация: Будет рассказано о некоторой специальной системе счисления, в которой все рациональные числа имеют конечное представление, а иррациональные представляются бесконечными последовательностями. Эта система связана  с интересным математическим объектом -- деревом Штерна-Броко. В этом дереве бесконечные пути находятся во взаимно однозначном соответствии с иррациональными числами.Эта конструкция связана также с разложением чисел в непрерывные дроби и дробями Фарея. Будет определено некоторое специальное отображение отрезка в себя, непрерывное в иррациональных точках, и рассказано о свойствах динамической системы, задающейся итерациями этого отображения.

Четвёртое заседание в осеннем семестре 2018 года (2 ноября 2018, ауд. 5427, 17.20) (презентация) (видео)
ДокладчикАртём Кузьмин
НазваниеОбратное RSK преобразование. Исследование классов эквивалентности перестановок.
АннотацияВ докладе будет рассказано о таких комбинаторных объектах, как диаграммы и таблицы Юнга, градуированные графы, мера Планшереля, а также о таких преобразованиях, как соответствие Робинсона-Шенстеда-Кнута (RSK) , обратное RSK  и преобразование Шютценберже. Обратное RSK преобразование ставит в соответствие паре таблиц Юнга одинаковой формы некоторую перестановку целых чисел, а преобразование Шютценберже преобразует одну таблицу Юнга в другую таблицу меньшего размера.

Пятое заседание в осеннем семестре 2018 года (16 ноября 2018, ауд. 5427, 17.20)
ДокладчикН.Н.Васильев (руководитель семинара)
Тема:: "Китайская теорема об остатках для полиномов и полиномиальная интерполяция"
Аннотация: Будет рассказано о разных версиях китайской теоремы об остатках (КТО), классической, полиномиальной и  наиболее общей для взаимно-простых идеалов в коммутативных кольцах. Будет также показано, что многие классические интерполяционные формулы такие как интерполяционные формулы Лагранжа и Эрмита являются  следствиями полиномиальной версии КТО. 

Архивы семинара за прошлые годы

Первое заседание в весеннем семестре 2018 года (15 февраля 2018, ауд. 5427, 17.20).
Организационное заседание. Обсуждение тематики семинара и регламента работы.

Второе заседание в весеннем семестре 2018 года (1 марта 2018, ауд. 5427, 17.20) (видео) (презентация)
Докладчик: Стрельников Вячеслав (2-й курс ФКТИ СПбГЭТУ)
Тема доклада: "Паросочетания в произвольном графе. Алгоритм отыскания полного паросочетания."
Аннотация доклада: Паросочетание или независимое множество рёбер в графе - одно из важных базовых понятий теории графов. В докладе будут описаны основные свойства паросочетаний. Будет рассказано об алгоритме построения полного паросочетания и представлена его компьютерная реализация. 

Третье заседание в весеннем семестре 2018 года (15 марта 2018, ауд. 5427, 17.20) (видео) (презентация) (полный текст доклада)
Докладчик: Кинзябаева Гульназ  (2-й курс ФКТИ СПбГЭТУ)
Тема доклада: Классы сложности, теорема Кука-Левина и задача SAT Аннотация доклада: P равно или не равно NP и почему это так важно? Вопрос о равенстве этих двух классов считается одной из самых сложных открытых проблем в области теоретической информатики. Математический институт Клэя включил эту проблему в список проблем тысячелетия, предложив награду размером в один миллион долларов США за её решение. На семинаре с помощью теоремы Кука-Левина докажем NP-полноту задачи 3SAT. Будут рассмотрены сведение к SAT и 3SATтаких задач, как «Японский кроссворд», «Задача о трех раскрасках», «Независимое множество». Рассмотрим несколько простых правил для доказательства NP-полноты новых задач.

Четвёртое заседание в весеннем семестре 2018 года (29 марта 2018, ауд. 5419, 17.20) (видео) (презентация) (заметки)
Докладчики: Тарасова Анна (теория), Побежимов Александр (программная реализация).
Тема доклада: Решение систем тропических линейных уравнений
Аннотация доклада: Что такое тропическая математика? Она появилась сравнительно недавно, но её развитие идёт быстрыми темпами.  Одной из важных задач тропической математики является решение сисем линейных тропических уравнений. В докладе будет представлено введение в тропическую математику, разобран и показан на примерах алгоритм Григорьева для решения систем тропических линейных уравнений, приведена оценка его сложности. 

Пятое заседание в весеннем семестре 2018 года (12 апреля 2018, ауд. 5427, 17.20) (видео) (презентация) (анимация)
Докладчик: Дужин Василий Сергеевич
Название доклада: Преобразование Шютценберже на градуированных графах. Реализация и численные эксперименты.
Аннотация: Преобразование Шютценберже, также известное как Jeu de taquin, позволяет решать различные задачи из перечислительной комбинаторики и теории представлений симметрических групп. В докладе будут введены понятия диаграмм и таблиц Юнга, марковского процесса Планшереля, RSK соответствия, преобразования Шютценберже. Будут рассмотрены детали программной реализации преобразования Шютценберже как в двумерном, так и в трехмерном случае. Также будут представлены результаты численных экспериментов.


Шестое заседание в весеннем семестре 2018 года (26 апреля 2018, ауд. 5427, 17.20) (видео)

Докладчик: Пётр Соковых

Тема доклада: Топология алгебры, комбинаторика операции возведения в квадрат. Графы монад и численные эксперименты.
Аннотация: Монада -- объект, состоящий из множества и его отображения в себя. Существует взаимно однозначное соответствие между монадами и конечными ориентированный графами (такими, что из каждой их вершины выходит ровно одно ребро). В докладе будет рассказано об известных закономерностях в структурах таких графов, соответствующих им диаграммах Юнга; будут продемонстрированы эксперименты, наглядно демонстрирующие описанные закономерности.

Седьмое заседание в весеннем семестре 2018 года (8 мая 2018 (ВТОРНИК), ауд. 5427, 17.20) (видео) (презентация)
Докладчики: Левицкий Даниил, Носова Ольга
Тема доклада: Исследование предельных форм двумерных и трехмерных диаграмм Юнга
Аннотация: Предельная форма диаграмм Юнга является важной характеристикой вероятностной меры на графе Юнга.
Известны выражения для предельных форм планшерелевской меры на двумерном графе Юнга, а также равномерной меры на двумерном и трехмерном графах Юнга.
Также существует асимптотически центральный псевдопланшерелевский процесс на трехмерном графе Юнга, точная предельная форма которого неизвестна, но предположительно равна предельной форме неизвестного центрального процесса.
В докладе будет рассказано о результатах компьютерных экспериментов, позволяющих построить другие меры на графах, для которых предельные формы диаграмм близки к известным предельным формам. В дальнейшем предполагается изучить вероятноcтные распределения построенных марковских процессов.

Восьмое (заключительное) заседание в весеннем семестре 2018 года (24 мая 2018, ауд. 5427, 17.20) (видео) (презентация)
Докладчик: Павел Владимирович Плотников (СПбГУ)
Название: Решение минимаксных задач размещения на плоскости и в трехмерном пространстве на основе методов идемпотентной алгебры.
Аннотация: В докладе будут предложены аналитические решения в явном виде задач тропической оптимизации с одной, двумя и тремя переменными. На основе полученных результатов будут найдены прямые решения задач размещения точечного объекта на плоскости и в пространстве с прямоугольной метрикой при различных ограничениях на допустимую область размещения. 


Первое заседание семинара в осеннем семестре 2017 года 
 5 октября (четверг) 2017, 17.15, ауд. 3308 (переведена в ауд. 5427)

1. Васильев Н.Н. О тематике и планах работы семинара на ближайший семестр (видео).
2. Дужин В.С. О  конференции "Applications of Computer Algebra ACA 2017", состоявшейся в июле в Иерусалиме (презентация, видео)

Объявление Н.Н.Васильева на семинаре:
Понедельник, 9 октября, ПОМИ, ауд. 402. Начало в 18:00.
Докладчик: Дмитрий Юрьевич Григорьев (National Center for Scientific Research (CNRS), Institut des Mathématiques de Lille).
Тема: Тропическая комбинаторная теорема о нулях и тестирование малочленов.
Abstract
В начале предполагается привести базовые сведения о тропической алгебре, ее истоках и приложениях.
Далее, обсудим следующие три направления результатов, недавно полученных совместно с В. Подольским.
Первое, комбинаторную теорему о нулях Н. Алона и ее тропический аналог.
Второе, лемму Шварца-Зиппеля о нулях на решетке, ее тропический аналог и приложения к вероятностному тестированию многочленов.
Наконец, построение универсального множества для тестирования тропических разреженных многочленов. В этой задаче ситуация отличается от аналогичной задачи про классические многочлены и приводит к трудным вопросам комбинаторной выпуклой геометрии.

Второе заседание семинара 
в осеннем семестре 2017 года  19 октября (четверг) 2017, 17.15, ауд. 5427
Д.Левицкий, О.Носова. "Код открытого доступа" (видео).
В докладе будет обсуждаться следующая задача. Имеется секретный код, состоящий из N чисел   и столько же участников. Каждому известно одно число из кода. Требуется «секретно» передать этот код всем участникам. Для этого каждому участнику сообщается таблица M x N чисел. Участник знает свою строку в таблице. Участники по очереди говорят знает он код или не знает, и в результате все узнают код. В докладе будет продемонстрирована программная реализация процедуры отгадывания и рассказан алгоритм  формирования таблицы, позволяющий решить задачу.

Третье заседание семинара в осеннем семестре 2017 года  2 ноября (четверг) 2017, 17.15, ауд. 5427
Лисицына Мария Александровна "Совершенные 2-раскраски транзитивных кубических графов" (видео)(презентация)
Работа выполнена в Институте математики им. С. Л. Соболева СО РАН
АннотацияРаскраску вершин графа называют совершенной, если все его одинаково окрашенные вершины имеют одинаковый цветовой состав окружения.
Доклад посвящен исследованию совершенных раскрасок в два цвета некоторых бесконечных серий транзитивных кубических графов. Будут рассмотрены графы призмы, лестницы Мебиуса, скрещенные призмы, хордальные циклы, обобщенные графы Петерсена, усеченные графы. Для элементов таких серий  полностью описаны допустимые параметры совершенных 2-раскрасок.
Так сложилось исторически, что в данной теме исследователи уделяли внимание классам регулярных графов достаточно большой степени. Случай степени 3 был незаслуженно пропущен, возможно, из-за своей кажущейся простоты. Вместе с тем транзитивных кубических графов очень много, что видно уже на примере списка диаграмм таких графов с числом вершин, не превосходящим 18 (рис. 1). Трудности перечисления совершенных раскрасок таких графов растут с ростом их обхвата.

Графы
Четвёртое заседание семинара в осеннем семестре 2017 года  16 ноября (четверг) 2017, 17.15, ауд. 5427
Васильев Н.Н. О скорости роста функций, удовлетворяющих рекуррентным уравнениям и верхних оценках сложности рекурсивных алгоритмов (видео). 
Аннотация.
В докладе будет рассказано о том как разделение задач на подзадачи приводит к рекуррентным уравнениям для верхних оценок временной сложности программ. Скорость роста решений таких уравнений зависит от коэффициентов таких рекуррентных уравнений. На нескольких классических рекурсивных алгоритмах будет показано каким образом получаются либо экспоненциальные, либо полиномиальные асимптотические временные оценки.
Пятое заседание семинара в осеннем семестре 2017 года   состоится в четверг 7 декабря в ауд. 5427 в 17.15 (видео, начинается с краткого сообщения  Коточигова, потом основной доклад Ф.А. Новикова и С.С. Лебедева)
Основной доклад
Лебедев С.С., Новиков Ф.А. Необходимое и достаточное условие применимости алгоритма Дейкстры.
Короткое сообщение
Коточигов А.М. Комментарий к решениям задач Конкурса первокурсника.
Комментарий:
У участников семинара имеется уникальная возможность встретиться с автором известного учебника "Дискретная математика для программистов" Фёдором Александровичем Новиковым.


Второе заседание семинара 
в весеннем семестре 2017 года 30 марта 2017: Сучков Андрей (4-й курс ФКТИ) "Фильтрационный алгоритм поиска минимальных аддитивных цепочек" (видеопрезентация) (комментирует Н.Н.Васильев)

ДополненияПоскольку много говорили о книге Дональда Кнута, то будет интересно прочитать интервью с ним в переводе на русский (хотя и сделанное 8 лет назад). А вот недавнее интервью, в котором очень интересно рассказано про алгоритм Кнута-Морриса-Пратта (алгоритм КМП) поиска слов в тексте.


Третье заседание семинара в весеннем семестре 2017 года 13 апреля 2017. Неожиданно заболел докладчик. Участникам была выдана брошюра "Как компьютер помогает упрощать алгебраические уравнения или немного о базисах Грёбнера". Прошла вводная беседа по решению полиномиальных уравнений и были обсуждены темы работ для альтернативного экзамена:

Предварительная беседа о решении полиномиальных уравнений

Совет: почитать книгу И.В.Аржанцева “Базисы Грёбнера и системы алгебраических уравнений”

Четвертое заседание семинара в весеннем семестре 2017 года  27 апреля 2017  (видео).

Докладчик: Пестерев Дмитрий (3-й курс ФКТИ) "Редукция систем полиномиальных уравнений от нескольких переменных"

Аннотация доклада: Введение в полиномиальную редукцию, отношения порядка на мономах, лемма Диксона, полиномиальный идеал, базисы Гребнера.

Ведёт заседание Н.Н.Васильев.

Пятое заседание семинара в весеннем семестре 2017 года 11 мая (четверг) 2017

Докладчик: В.Дужин (ЛЭТИ). "Комбинаторика диаграмм Юнга, алгоритм RSK  и формула Планшереля" (презентациявидео доклада с комментарием Васильева).

Аннотация доклада.  Диаграммы Юнга появляются в самых различных математических контекстах. В докладе рассказано о комбинаторике диаграмм Юнга и связанных с ними объектов, таких как разбиения натуральных чисел на положительные слагаемые, таблицы Юнга и граф Юнга. Также рассказано о соответствии Робинсона-Шенстеда-Кнута или алгоритме строчной вставки и некоторых его важных следствиях.


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


Сообщение Н.Н.Васильева о планах семинара по алгоритмической математике на 2017-2018 учебный год


Ċ
Sergey Pozdnyakov,
29 мая 2018 г., 9:53
Ċ
Sergey Pozdnyakov,
14 мая 2017 г., 21:41
Ċ
Sergey Pozdnyakov,
9 окт. 2017 г., 4:35
Ċ
Sergey Pozdnyakov,
12 нояб. 2018 г., 10:52
Ċ
Sergey Pozdnyakov,
7 окт. 2018 г., 2:51
Ċ
Sergey Pozdnyakov,
21 мар. 2017 г., 15:07
Ċ
Sergey Pozdnyakov,
21 мар. 2017 г., 15:07
Ċ
Sergey Pozdnyakov,
18 мар. 2018 г., 13:52
Ċ
Sergey Pozdnyakov,
22 апр. 2018 г., 22:29
Ċ
Sergey Pozdnyakov,
22 апр. 2018 г., 22:30
Ċ
Sergey Pozdnyakov,
29 мая 2018 г., 9:54
Ċ
Sergey Pozdnyakov,
4 мар. 2018 г., 7:44
Ċ
Sergey Pozdnyakov,
22 апр. 2018 г., 22:29
ć
Sergey Pozdnyakov,
22 апр. 2018 г., 22:29
Comments