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

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

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

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


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


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

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

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

“Три сюжета по компьютерной математике” (март - май 2015 года)


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

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

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

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

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

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


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

      


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

Вводное заседание семинара по алгоритмической математике. Ведёт Н.Н.Васильев (16 марта 2017 года - видео)

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

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


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

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

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

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

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

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

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

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

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

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


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


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


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

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

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

Ċ
Sergey Pozdnyakov,
14 мая 2017 г., 21:41
Ċ
Sergey Pozdnyakov,
9 окт. 2017 г., 4:35
Ċ
Sergey Pozdnyakov,
21 мар. 2017 г., 15:07
Ċ
Sergey Pozdnyakov,
21 мар. 2017 г., 15:07
Comments