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

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

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

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

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


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

    Похожие публикации

    Комментарии 9

      0
      а что будет уметь ученик окончивший курс. можно какие-нибудь примеры практической пользы для программиста?
        +2
        Этот курс лекций не ставит цели обучить навыкам программирования, он посвящен математическому аппарату, который используется в комбинаторике слов. А комбинаторика слов в свою очередь имеет множество практических приложений, например для сжатия данных. Основная польза от этого курса — получение глубокого понимания того, как устроены методы работы со строками, какие существуют проблемы, как их решают, и почему именно так.
          +1
          я и не думал, что меня программированию будут учить. мне интересно то, что вы назвали 'множеством практических приложений', хочу понять какие практические задачи сейчас решаются с использованием аппарата комбмнаторики слов, чтобы решить интересно ли мне это
        • НЛО прилетело и опубликовало эту надпись здесь
            0
            Простите мне мою неграмотность, что такое обол?
            • НЛО прилетело и опубликовало эту надпись здесь
          0
          Простите, что поздно, но всё-таки…

          > а что будет уметь ученик окончивший курс. можно какие-нибудь примеры практической пользы для программиста?

          Поддерживаю вопрос. У вас в тексте написано:

          > Символьные последовательности (слова), являющиеся основным объектом исследования комбинаторики слов, окружают нас повсюду… Для эффективной работы с таким изобилием и разнообразием слов необходим соответствующий математический аппарат

          Не могли бы вы уточнить, что такое эффективная работа с такием изобилием? в одном ответе выше вы привели пример со сжатием данных. Но мне не очень понятно. Обычно такие алгоритмы работают просто с данными абстрактно, поэтому сжатие как-то не очень вяжется комбинаторикой слов.

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

          Не могли бы вы привести пример от задумки до формализации входных данных и результата на выходе? И если есть какой-то отчёт о лекции не положите ссылку?
            0
            Мне трудно полностью ответить на Ваш вопрос, так как я сам хожу на эти лекции, а не читаю их. Описание курса было составлено лектором. Данные сжимаются за счет того, что в них встречаются повторы, а комбинаторика слов изучает повторы и преобразования, которые эти повторы выявляет. Кроме сжатия данных уже были рассказаны примеры связанные с поиском образца в строке на лету, когда строка поступает в реальном времени, эффективное построение индекса для больших данным (такой индекс занимает места столько же, сколько сами данные и поиск в этой структуре выполняется очень быстро).

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

            Материалы лекций появляются тут: compsciclub.ru/course/wordscombinatorics
            Видеозаписи через некоторое время появятся тут: www.lektorium.tv

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

        Самое читаемое