Курс “Комбинаторика слов и ее приложения”

Каждый университет сталкивается с тем, что на некоторые темы в городе невозможно найти преподавателя, который бы являлся в этой теме специалистом. Один из вариантов решить эту проблему состоит в том, чтобы поручить подготовить курс на эту тему какому-нибудь из имеющихся преподавателей, который не является специалистом в этой области. Мы в Акадеическом университете стараемся пойти другим путем — пригласить специалиста для чтения курса. В прошлом году мы поучаствовали в конкурсе ^[1] фонда Династия “приглашенный профессор”. Мы подали две заявки и обе выиграли, а также два наших преподавателя были приглашены в Уральский и Казанский федеральные университеты. В сентябре 2014 года Александр Охотин ^[2] из университета Турку прочитал курс Формальные грамматики ^[3]. А 18 марта начнет читать курс ^[4] “Комбинаторика слов и ее приложения” профессор Уральского федерального университета Арсений Михайлович Шур ^[5]. Мы приняли решение сделать этот курс полностью открытым для всех и провести его в рамках Computer Science клуба, нашего постоянного партнера.

Арсений Михайлович — активный исследователь в области комбинаторики слов, поэтому курс обещает быть очень интересным. Первое занятие состоится в среду 18 марта в 18-30 в Мраморном зале ПОМИ РАН (Санкт-Петербург, наб. реки Фонтанки д. 27), вход свободный, регистрация не требуется.

Подробное описание курса и расписание: тут ^[4].

Краткое описание курса

Символьные последовательности (слова), являющиеся основным объектом исследования комбинаторики слов, окружают нас повсюду. Это лексемы, фразы и тексты на естественных языках, исходники программ и библиотеки, логи серверов и протоколы обмена данными, математические и химические формулы, молекулы ДНК и белков, символические траектории точек в фазовом пространстве, записи чисел в позиционной системе счисления, и многое другое. Для эффективной работы с таким изобилием и разнообразием слов необходим соответствующий математический аппарат, который и предоставляет комбинаторика слов. Зарождение комбинаторики слов связывают с выдающимися работами норвежского математика А. Туэ (1863-1922) о бесповторных словах. Оформление комбинаторики слов как самостоятельной дисциплины произошло в начале 1980-х, когда группа французских математиков под руководством М. Шютценберже написала книгу “Combinatorics on words” в рамках проекта “Энциклопедия математики и ее приложений”. В настоящее время комбинаторика слов — динамично развивающаяся дисциплина на стыке дискретной математики и компьютерных наук. В рамках учебного курса невозможно изложить научную дисциплину целиком, поэтому наша основная цель – дать слушателям представление об основных особенностях слов и о том, как и зачем нужно изучать слова (в том числе бесконечные, циклические и частичные). Большое внимание в курсе уделено связям “внутренних” объектов и результатов с “внешними” постановками задач из различных разделов математики и компьютерных наук. Материал курса сгруппирован вокруг следующих свойств и понятий:

• некоммутативность умножения слов и ее следствия;
• лексикографический порядок на словах, его свойства и использование;
• повторы в словах: периоды и свойства периодических слов, квадраты, палиндромы;
• бесповторность и другие варианты избегаемости;
• функции подсчета слов;
• коды и кодирование (если успеем).

Автор: dmitrits

Источник ^[6]