Компьютерная алгебра и теория формальных языков

На семинаре мы изучаем вопросы компьютерной алгебры и теории формальных языков.

Компьютерная алгебра

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

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

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

Литература:
  1. Дж. Дэвенпорт, И. Сирэ, Э. Турнье. Компьютерная алгебра. М.: Мир, 1991.
  2. Е.В. Панкратьев. Элементы компьютерной алгебры. М: БИHОМ, 2007.
  3. M. Bronstein. Symbolic integration I. Transcendental functions (Second edition). Springer-Verlag, 2005.
  4. J. von zur Gathen, J. Gerhard. Modern Computer Algebra (Second Edition). Cambrige University Press, 2003.

Теория формальных языков

Теория формальных языков занимается вопросами представления и автоматического преобразования синтаксических структур различной природы. Она изучает формальные грамматики, конечные и магазинные автоматы, альтернативные графовые формализмы.

На семинаре также рассматриваются интересные алгоритмы, актуальные технологии программирования.

План докладов на весну 2016/2017 учебного года

Дата Тема доклада Докладчик
3.03.2017 Разновидности машин Тьюринга и их имитация на компьютере Зуев Кирилл
Будут рассмотрены расширения базовой машины Тьюринга (многоленточные и недетерминированные), а также машины с некоторыми ограничениями. Кроме того, будет рассмотрена имитация машины Тьюринга на компьютере и сравнение времени работы МТ и компьютера.
10.03.2017 Канонический вид матрицы дифференциальных операторов Кошовец Олег
Будет рассмотрено понятие канонического вида матрицы и приведены примеры приведения матриц дифференциальных операторов к каноническому виду. Также все это будет рассмотрено в контексте исследования систем дифференциальных уравнений, записанных в операторной форме.
17.03.2017 Неразрешимые алгоритмические проблемы, связанные с машинами Тьюринга Лобосов Никита
Рассматривается ряд неразрешимых проблем для машины Тьюринга, с помощью которых доказывается неразрешимость Проблемы соответствия Поста.
24.03.2017 Рекомендации по разработке пользовательского интерфейса Минаева Елизавета
Любая современная программа, разрабатываемая для нужд большого количества пользователей, не обходится без графического интерфейса. В докладе будут рассмотрены некоторые рекомендации по разработке пользовательского интерфейса, основанные на особенностях человека мыслить, видеть, запоминать и призванные сделать интерфейс удобнее.
31.03.2017 Автоматизированная проверка структуры решений алгоритмических задач в учебной среде программирования Генералова Татьяна
7.04.2017 Распознавание цепочек по регулярным выражениям Хорошилов Георгий
В докладе определяются регулярные выражения и связанные с ними понятия, рассматриваются алгоритмы распознавания образов, задаваемых регулярными выражениями. Приводится пример работы механизма регулярных выражений в ОС Unix.
28.04.2017 Бесконтекстные L-графы и задача проверки равенства языков Хзмалян Размик
Определяются бесконтекстные L-графы и некоторые их подклассы. Рассматривается задача проверки равенства языков, заданных L-графами, и некоторые алгоритмы ее решения для подклассов бесконтекстных L-графов.
28.04.2017 Разработка и реализация эвристических методов для улучшения характеристик алгоритма Row-Reduction Тощев Андрей
Рассматривается алгоритм Row-Reduction, приводятся примеры работы алгоритма с его возможными неоднозначностями. В докладе уделяется внимание разработке и исследованию эвристических методов для улучшения характеристик алгоритма.
28.04.2017 Системы счисления с необычными основаниями Кондратьев Григорий
Рассматривается несколько необычных позиционных систем счисления. В основном такие системы представляют собой не более чем интересный курьез, не имеющий практического применения. Данное рассмотрение ограничивается целыми числами, однако его легко распространить и на цифры после точки, что обычно (хотя и не всегда) обозначает нецелые числа.

План докладов на весну 2015/2016 учебного года

Дата Тема доклада Докладчик
11.12.2015 Гармонические числа. Гармоническое суммирование Хзмалян Размик
01.03.2016 Числа Стирлинга. Числа Эйлера Сутупов Андрей
15.03.2016 Числа Бернулли Генералова Татьяна
Числа Бернулли - одна из важных последовательностей чисел, встречающихся, например, в коэффициентах разложения в ряд тригонометрических функций. В докладе, подготовленном по материалу соответствующей главы книги “Конкретная математика. Основание информатики”, представлены способы вычисления чисел Бернулли неявным рекуррентным соотношением и с помощью тангенциальных чисел, приводится доказательство формулы Бернуллли и ряда других утверждений. Рассмотрена взаимосвязь чисел Бернулли и чисел Стирлинга.
22.03.2016 Программные возможности в Maple Тощев Андрей
29.03.2016 Числа Фибоначчи Генералова Татьяна
Какие числа чаще всего встречаются в природе? Сколько (пра)*бабушек и (пра)*дедушек у пчелы трутня? Одна из любимых головоломок Льюиса Кэррола: разрезаем шахматную доску 8x8 и составляем из этих кусочков прямоугольник 13x5. В чем секрет? Как в уме быстро перевести мили в километры и обратно? Ответы на эти вопросы дают числа, введенные в 1202 году Леонардо Фибоначчи Пизанским.
05.04.2016 Формальные языковые средства набора математических формул Елонов Павел
В докладе даётся обзор некоторых средства набора математических формул (ТеХ, MathML и другие), а также рассматриваются варианты поддержки отображения формул на веб-страницах.

Доклады в 2012/2016 учебных годах

В 2012-2016 учебных годах доклады, кроме теории формальных языков и компьютерной алгебры, были посвящены темам из книг:

  1. Э.Дейкстра. Дисциплина программирования.
  2. Т.Кормен, Ч.Лейзерсон,Р.Ривест. Алгоритмы: построение и анализ
  3. Р.Грэхем, Д.Кнут, О.Паташник. Конкретная математика
    1. План докладов на 2011/2012 учебный год

      Дата Тема доклада Докладчик
      28.09.2011 Технология Map-Reduce. Модель вычислений, реализация, применение. Парамонов Сергей
      Рассматривается технология Map-Reduce, ее модель вычислений и примеры применения, элементы теории списочных гомоморфизмов, связанные с областью применимости метода. Также описываются некоторые существующие реализации.
      07.10.2011 Оптимальность схемы Горнера Гурьев Илья
      Схемой Горнера называется алгоритм вычисления значения произвольного полинома n-й степени требующий n сложений и n умножений: a_n*x^n + a_{n-1}*x^{n-1} + ... + a_1 * x + a_0 = (...(a_n * x + a{n-1})x + ... + a_1) * x + a_0. Доказав, что любой алгоритм вычисления значения произвольного полинома n-й степени, использующий только сложение и умножение, требует не менее n сложений и не менее n умножений получим, что схема Горнера является оптимальным в худшем случае алгоритмом вычисления выражения a_n*x^n + a_{n-1}*x^{n-1} + ... + a_1 * x + a_0 c помощью операций сложений и умноженияй.
      14.10.2011 Структура КС-языков. Леммы о разрастании Ростовский Артем
      Рассматриваются леммы о разрастании для регулярных и контекстно-свободных языков, описывающие способ построения всех цепочек заданного языка из некоторого конечного набора цепочек этого языка.
      21.10.2011 Представление КС-языков с помощью морфизмов и сетей Ростовский Артем
      Регулярные языки представимы как морфические образы 2-проверяемых языков. Приводится обобщение такого представления на КС-языки. Также рассматривается представление КС-языков с помощью конечного набора конечных сетей.
      28.10.2011 Наибольший общий делитель многочленов Зверев Илья
      Пусть f(x), g(x) E K[x]. Многочлен d(x) E K[x] называется наибольшим общим делителем (НОД) многочленов f(x) и g(x), если: 1. d(x) - общий делитель многочленов f(x) и g(x) (т. е. f(x)=d(x)q(x), g(x)=d(x)r(x) ); 2. для любого общего делителя d'(x) многочленов f(x) и g(x) многочлен d(x) делится на d'(x). В докладе рассмотрены различные алгоритмы его поиска с оценками сложности
      11.11.2011 Методы поиска наибольшего общего делителя (GCRD) и наименьшего общего кратного (LCLM) дифференциальных операторов Парамонов Сергей
      В докладе рассматриваются линейные дифференциальные операторы и операции над ними, нахождение GCRD и LCLM с помощью расширенного алгоритма Евклида, а также их связь с субрезультантами. Приводятся некоторые оценки для степеней коэффициентов получаемых операторов.
      18.11.2011 Представление рядов в компьютерной алгебре Гурьев Илья
      Рассматриваются основные способы представления рядов (ряды Тейлора, ряды Фурье) в системах компьютерной алгебры. Описаны случаи потери точности в операциях над рядами для каждого способа представления. Приводится пример использования рядов для решения нелинейных задач.
      25.11.2011 Алгоритмы геоинформатики Плотников Михаил
      Дан краткий экскурс в схему организации GPS-навигации. Показано, что в процессе вычисления координат навигатором возникает необходимость в решении сложных прямых и обратных задач с большим числом физических параматеров, рассмотрены примеры алгоритмов, вычисляющих поправки для GPS навигаторов в зависимости от погодных условий и состояния ионосферы.
      16.12.2011 Язык программирования Go. Зверев Илья
      Go -- компилируемый, многопоточный язык программирования, разработанный компанией Google. Официально язык был представлен в ноябре 2009 года. На данный момент его поддержка осуществляется для операционных систем FreeBSD, OpenBSD, Linux, Mac OS X и частично Windows.
      24.02.2012 Графовые представления формальных языков Ростовский Артем
      02.03.2012 Алгоритмы на графах Ростовский Артем
      09.03.2012 Нисходящий синтаксический анализ Зверев Илья
      16.03.2012 Восходящий синтаксический анализ (общий вид) Гурьев Илья
      23.03.2012 LR(k)-анализ Гурьев Илья
      30.03.2012 Базисные конечные автоматы Зверев Илья
      06.04.2012 Частичные оценки знаменателя для решений линейных уравнений с частными разностями Парамонов Сергей
      13.04.2012 Основы алгоритма поиска рациональных решений линейных дифференциальных уравнений с полиномиальными коэффициентами Плотников Михаил
      20.04.2012 Отчет о курсовых работах (4 курс)  
      27.04.2012 Отчет о курсовых работах (5 курс)  
      13.05.2012 Защита курсовых работ  

      План докладов на 2010/2011 учебный год

      Дата Тема доклада Докладчик
      18.11.2010 Введение в LaTeX Станислав Машевский
      25.11.2010 Арифметика на L-графах А.А. Вылиток
      02.12.2010 Быстрое деление с остатком Сергей Парамонов
      09.12.2010 Регулярные языки и звездная высота Артем Ростовский
      16.12.2010 Неразрешимость дифференциальных уравнений в подклассе решений Станислав Машевский
      09.02.2011 D-графы и магазинные автоматы Артем Ростовский
      13.04.2011 Программирование в системе Maple Сергей Парамонов
      20.04.2011 Определяющее уравнение. Его использование для оптимизации схемы поиска рациональных решений дифференциальных уравнений Станислав Машевский
      27.04.2011 L-графы и трансляция выражений А.А. Вылиток
      04.05.2011 Аналогии между ЛОДУ и алгебраическими уравнениями Сергей Парамонов
      11.05.2011 Обзор программных средств поддержки практикума на 1-м и 2-м курсах Петр Секретев

      Тематический план на 2009/2010 учебный год

      1. Графовые описания формальных языков.
      2. Примеры задания языков a^n b^n c^n, a^(n^2), a^(2^n) , n>=1 c помощью графов.
      3. Примеры сопряжений конечных автоматов.
      4. Генерация эквивалентных конечных автоматов типа "сеть" и "дерево".
      5. Генерация эквивалентных конечных автоматов с некратными циклами.
      6. Генерация эквивалентных конечных автоматов с различной циклической сложностью.
      7. Ядро конечных автоматов и теорема о развитии.
      8. Проблема эквивалентности детерминированных графовых описаний. Подходы к решению.
      9. Алгоритм построения D-графа по КС-грамматике путем замены нетерминалов парными скобочными переходами.
      10. Сопряжения графовых описаний. Примеры.
      11. Построение графа сопряжений для детерминированных конечных автоматов.
      12. Алгоритм построения элементов сопряжений графовых описаний.
      13. Проблема соовтетствий Поста. Примеры.
      14. Алгоритмически неразрешимые проблемы теории D-графов.
      15. Неразрешимость построения графа сопряжений для детерминированных D-графов.
      16. Подклассы D-графов с разрешимой проблемой построения графа сопряжений.
      17. Реализация конечных автоматов и D-графов в системе компьютерной алгебры Sage.

      (Участники секции Теория формальных языков: руководители А.А. Вылиток и П.Г. Сутырин; студенты В. Мерзляков, С. Харченков, Д. Юдочев)

      Тематический план на 2008/2009 учебный год

      1. Регулярные языки и выражения.
      2. Звездная высота регулярного языка.
      3. Конечные автоматы. Детерминированные и недетерминированные.
      4. Алгоритмы обработки КА ( минимизация, детерминирование, устранение нечитающих переходов).
      5. Алгоритмы преобразования КА в регулярное выражение и в регулярную грамматику.
      6. Магазинные автоматы и КС-грамматики. Ядро магазинного автомата.
      7. Преобразование магазинного автомата в D-граф.
      8. D-графы как характеризация КС-языков.
      9. Определение ядра. Теорема о развитии.
      10. D-графы без псевдоциклов. Трансформация ядра для удаления псевдоциклов.
      11. Детерминированные D-графы.
      12. Проблема регулярности для детерминрованных D-графов.
      13. Преобразование D-графа, допускающего регулярный язык, в конечный автомат.
      14. Свободное программное обеспечение.
      15. Язык программирования Питон. Введение.
      16. Язык программирования Питон. Основные конструкции, примеры.
      17. Система компьютерной алгебры Sage на базе языка программирования Питон.
      18. Грамматики LR(1) и LL(1).
      19. Нормальные формы КС-грамматик.
      20. Грамматики простого и операторного предшествования.
      21. Линейные КС-грамматики и языки.
      22. D-графы, характеризующие подклассы грамматик.
      23. Операции над конечными автоматами. Характеристики сложности.
      24. Визуализация конечных автоматов в системе Sage.

      Архив докладов на весну 2008 года

      Дата Тема доклада Докладчик
      20.02.2008 Система LaTex Мальская Екатерина
      05.03.2008 Введение в статистическую обработку текста и введение в теорию обучения машин Орлов Дмитрий
      12.03.2008 Интегральное представление и суммирование в замкнутом виде Евгений Викторович Зима
      19.03.2008 Инструменты для изготовления презентаций на основе TeX Юдочев Дмитрий
      26.03.2008 Итерационные алгоритмы: деление полиномов Сорокин Антон
      02.04.2008 Методы синтаксического анализа "сверху-вниз" Харченков Сергей, Строганов Александр
      16.04.2008 Алгоритм Каармаркара - Лекшмана сдвига коэффициентов многочленов Платонов Денис
      23.04.2008 Степенные ряды и линейные разностные уравнения С.А.Абрамов (ВЦ РАН)
      23.04.2008 Блочные символьные матричные алгоритмы М.С.Зуев (Тамбовский университет)
      30.04.2008 Отчетный семинар Студенты 3 и 4 курсов
      07.05.2008 Отчетный семинар Студенты 5 курса

      Архив докладов за осень 2007 года

      Дата Тема доклада Докладчик
      03.10.2007 Формальные системы в семантике естественных языков Дмитрий Орлов
      10.10.2007 Параллельные алгоритмы. Нижние оценки сложности Устинов В.Д.
      17.10.2007 Рекурсия и индукция Юдочев Д.В.
      24.10.2007 Теория сложности Мерзляков В.В.
      31.10.2007 Алгоритмы на графах. Поиск в глубину Сорокин А.С.
      07.11.2007 projector Введение в систему Maple 10 Строганов А.Ю. и Харченков С.Л.
      14.11.2007 Программирование в системе Maple 10 Строганов А.Ю. и Харченков С.Л.
      21.11.2007 Parametric polynomial system solving with Maple J. Gerhard
      28.11.2007 Один метод оптимизации вычисления градиента Платонов Д.В.
      05.12.2007 Полиномиальное деление Федулкин Алексей
      12.12.2007 Поиск медианы массива Мясников Алексей
      19.12.2007 Отчетный семинар Все студенты

      Архив докладов за весну 2007 года

      Дата Тема доклада Докладчик
      13.03.2007 Красно-черные деревья Александр Сучков
      20.03.2007 Арифметика Пресбургера Евгений Вареник
      27.03.2007 projector Теория Пойа Мальская Екатерина
      03.04.2007 Комбинаторика Швейкина Ольга, Бортаковская Мария
      10.04.2007 Матроиды Мерзляков Василий
      17.04.2007 Теоретико-числовые алгоритмы Масалин Ержан
      25.04.2007 Отчетный семинар Все студенты

      Архив докладов за осень 2006 года

      Дата Тема доклада Докладчик
      28.09.2006 Поиск медианы из множества n чисел Алексей Федулкин
      05.10.2006 Задача о суммах подмножеств Евгений Вареник
      12.10.2006 Алгоритмы поиска подстрок Екатерина Мальская
      19.10.2006 Система компьютерной алгебры Maple Александр Сучков
      26.10.2006 Система компьютерной алгебры Maple (продолжение) Александр Сучков
      02.11.2006 Сортировка с помощью кучи Ержан Масалин
      09.11.2006 Регулярные языки Василий Мерзляков
      16.11.2006 Жадные алгоритмы Алексей Федулкин
      23.11.2006 Построение элементарных комбинаторных объектов Денис Платонов
      30.11.2006 Системы непересекающихся подмножеств Алексей Мясников
      07.12.2006 Синтаксический анализ КС-языков Александр Алексеев
      14.12.2006 Отчетный семинар Все студенты

      Архив докладов за весну 2006 года

      Дата Тема доклада Докладчик
      28.02.2006 Об оптимальности схемы Горнера Евгений Вареник
      07.03.2006 40 лет быстрой сортировке: частный взгляд Дмитрий Логинов
      14.03.2006 Модулярные вычисления и интерполяция Алексей Щербаков
      21.03.2006 Арифметические схемы Александр Сучков
      28.03.2006 projector Web 2.0 Павел Сутырин
      04.04.2006 projector Формальные системы для визуализации развития растений Екатерина Мальская
      11.04.2006 projector Двумерные формальные языки Григорий Плотников
      18.04.2006 Вероятностые алгоритмы (Монте-Карло и Лас-Вегаса) Евгений Вареник
      25.04.2006 Китайская теорема об остатках и алгоритм быстрого умножения Александр Алексеев
      02.05.2006 Кратчайшие пути для пары вершин Алексей Мясников
      16.05.2006 projectorОтчетный семинар Все студенты

      Архив докладов за осень 2005 года

      Дата Тема доклада Докладчик
      06.10.2005 projector Свободное программное обеспечение Павел Сутырин
      13.10.2005 projector Клеточные автоматы Екатерина Мальская
      20.10.2005 projector Система Компьютерной алгебры Maple. Обзор возможностей. Начала программирования Александр Алексеев
      27.10.2005 projector Программирование в Maple Александр Сучков
      03.11.2005 Символьные вычисления над последовательностями Дмитрий Логинов
      10.11.2005 Построение выпуклой оболочки Алексей Мясников
      17.11.2005 projector TeX - система верстки текстов с формулами Алексей Федулкин
      24.11.2005 Алгоритмы быстрого умножения Антон Онуфриев
      01.12.2005 projector Производящие функции. Формальные грамматики с однозначным выводом. Разбиения и разложения Павел Сутырин,
      Григорий Плотников
      08.12.2005 Отчетный семинар Все студенты