Кафедра математической логики и теории алгоритмов

Механико-математического факультета МГУ


Научная работа студентов

Home Papers Teaching CV Leisure

Научная работа студентов

М. Р. Пентус
профессор кафедры математической логики и теории алгоритмов

Учебники

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

Сложность вычислений

  • Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.
  • Китаев А., Шень А., Вялый М. Классические и квантовые вычисления. М.: МЦНМО, ЧеРо, 1999. 192 с.
  • Крупский В. Н. Введение в сложность вычислений. М.: Факториал Пресс, 2006. 128 с.

Исчисление Ламбека и линейная логика

  • Lambek J. The mathematics of sentence structure // American Mathematical Monthly. 1958. Vol. 65, N 3. P. 154-170.
    Русский перевод: Ламбек И. Математическое исследование структуры предложения // Математическая лингвистика: Сборник переводов / Под ред. Ю. А. Шрейдера и др. М.: Мир, 1964. С. 47-68.
  • Di Cosmo R., Miller D. Linear Logic // Stanford Encyclopedia of Philosophy. <http://plato.stanford.edu/entries/logic-linear/> (04.12.2006).

Математическая лингвистика

  • Гладкий А. В., Мельчук И. А. Элементы математической лингвистики. М.: Наука, 1969. 192 с.
  • Carpenter B. Type-Logical Semantics. The MIT Press, 1997. 575 pp.
  • Dowty D. 2005-04-05. Ling 795D: Categorial Grammar.
  • Partee B., Meulen A. ter, and Wall R. E. Mathematical Methods in Linguistics. Kluwer, 1993.

Алгоритмы на графах

  • Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 1999. 960 с.
  • Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы. Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001. 288 с.
  • Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985.

Комбинаторные алгоритмы

  • Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. СПб.: Невский Диалект; БХВ-Петербург, 2003. 654 с.
  • Шень А. Программирование: теоремы и задачи. М.: МЦНМО, 1995. 264 с.
  • Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. 478 с.

Комбинаторная теория слов

  • Саломаа А. Жемчужины теории формальных языков. М.: Мир, 1986. 159 с.

Сжатие текстов

  • Романовский И. В. Дискретный анализ. СПб.: Невский диалект, 2000. 240 с.

Статьи для студентов 1—3-го курсов мехмата

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

Сложность вычислений

Исчисление Ламбека и линейная логика

Комбинаторная теория слов

Сжатие текстов

Библиографические списки

Темы для курсовых работ

Лингвистических тем здесь нет. Кто интересуется лингвистикой и математикой, может почитать, чем занимается математическая лингвистика.

Исчисление Ламбека и линейная логика

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

Логика первого порядка


R-полнота L*(/) над множеством целых чисел

Определение. Типы исчисления L*(/) строятся из переменных p1p2p3,… с помощью скобок и двуместной операции /. Множество всех таких типов обозначается Tp(/). Буквы ABC будут обозначать типы, а буквы ГПФ — конечные последовательности типов (возможно, пустые). Секвенции исчисления L*(/) имеют вид Г → A. Единственная аксиома — A → A.
Первое правило: если выводится Ф, A → B, то выводится Ф → (B / A).
Второе правило: если выводится Ф → A и выводится Г, B, П → C, то выводится Г, (B / A), Ф, П → C.

Пример. Секвенция (p1 / (p2 / p2)) → p1 выводится в L*(/) так:
p2 → p2
→ (p2 / p2)
p1 → p1
(p1 / (p2 / p2)) → p1.

Пример. Секвенцию (p1 / (p2 / (p3 / p4))) → ((p1 / (p4 / p3)) / p2) невозможно вывести в L*(/).

Определение. Реляционной моделью называется пара (W, w), где W — произвольное рефлексивное, транзитивное бинарное отношение (рассматриваемое как подмножество декартова квадрата некоторого множества D), а w — произвольная функция из Tp(/) в множество всех подмножеств множества W, такая что (r, s) принадлежит w(B / A) тогда и только тогда, когда для каждого t, если (s, t) принадлежит w(A), то (r, t) принадлежит w(B). Секвенция A → B истинна в реляционной модели (W, w), если w(A) является подмножеством w(B).

Вопрос. Существует ли невыводимая в исчислении L*(/) секвенция A → B, истинная в каждой реляционной модели, где W — стандартный линейный порядок на множестве целых чисел?


Задача выводимости в небольших грамматиках

Вопрос. Разрешима ли задача проверки выводимости слова в порождающих грамматиках, содержащих не более 9 правил?


Распознавание общезначимости эквивалентностных формул

Пример. Формула ∀x (∀y R(x,y) ↔ ∃y R(y,x)) ↔ ∀x (∃y R(x,y) ↔ ∀y R(y,x)) общезначима (то есть истинна при любой интерпретации предикатного символа R).

Пример. Формула ∃x (∀y R(x,y) ↔ ∃y R(y,x)) ↔ ∃x (∃y R(x,y) ↔ ∀y R(y,x)) не является общезначимой.

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

Курсовые и дипломные работы прошлых лет

  • Дмитрий Михайлович Кирноценский
    • Сравнение фрагмента UML и ComponentSpecs. 1998.
    • О задаче поиска изоморфных подграфов. 1999.
    • Среда для грамматических архиваторов. 2000.
  • Ольга Михайловна Урюпина
    • Некоторые однозначные грамматики Ламбека. 1998.
    • Алгоритмы разбиения на морфемы. 1999.
    • Об автоматическом разбиении на морфемы. 2000.
  • Вера Александровна Минина
    • Необходимое условие эквивалентности формул некоммутативной линейной логики. 1999.
    • R-полнота исчисления Ламбека с операцией инволюции. 2000.
    • Полнота синтаксического исчисления Ламбека с операцией инволюции. 2001.
  • Дмитрий Евгеньевич Корочкин
    • Достаточное условие живости некоторого подкласса сетей Петри. 1999.
    • Неполнота исчисления Ламбека относительно конечных классов конечных реляционных моделей. 2000.
    • Исчисление Ламбека и языки деревьев. 2001.
  • Екатерина Викторовна Илюшкина
    • Необходимое условие контекстно-свободности формальных языков. 1999.
    • Пример неоднозначной контекстно-свободной грамматики. 2000.
    • О соотношении между размерностью и степенью неоднозначности КС-языков. 2001.
  • Ирина Александровна Болгова
    • Построение полиномиального автомата для быстрого поиска подстрок особого вида. 2001.
    • Критерий эквивалентности типов в исчислении Ламбека с одним делением. 2002.
    • Эквивалентность типов в исчислении Ламбека с одним делением. 2003.
  • Пётр Александрович Стрелков
    • Анализ современных методов поиска заданного образца в текстовых файлах. 2002.
    • Некоторые методы поиска закономерностей в программах на языке C. 2003.
    • Использование деревьев суффиксов для декодирования программ на языке C. 2004.
  • Юрий Вячеславович Саватеев
    • Варианты исчисления Ламбека с одним делением. 2004.
    • Совместность типов в исчислении Ламбека с одним делением. 2005.
    • Проблема выводимости для исчисления Ламбека с одним делением. 2006.
  • Алексей Наифович Сафиуллин
    • Исследование сложности выводимости конкретных контекстно-свободных языков. 2004.
    • Начальные факты, касающиеся класса порождаемых детерминированными грамматиками Ламбека языков. 2005.
    • Выводимость допустимых правил в исчислении Ламбека. 2006.
  • Кирилл Валериевич Чепурин
    • О языковых моделях фрагментов коммутативного исчисления Ламбека. 2005.
    • Приложения теории информационных потоков. 2006.
    • Реляционная семантика неассоциативного исчисления Ламбека и теории информационных сетей. 2007.
  • Анна Александровна Черниловская
    • Об интерполяционном свойстве и устранимости сечения в исчислении Ламбека с опреатором сферы действия. 2005.
    • О логике В. Н. Гришина и её применении в лингвистике. 2006.
    • Неконсервативность линейной логики с одним отрицанием, расширяющей LG. 2007.
  • Владимир Андреевич Климонтович
    • Оптимизирующая топологическая сортировка ориентированных ациклических графов. 2006.
  • Андрей Иванович Фёдоров
    • Алгоритмы сжатия, использующие грамматики. 2006.
    • Метод построения грамматики типа 1 для дополнения языка типа 1. 2007.
    • Модели исчисления Ламбека. 2008.
  • Степан Львович Кузнецов
    • Об исчислении Ламбека с одним делением и двумя примитивными типами. 2007.
    • Об исчислении Ламбека с одним делением и одним примитивным типом. 2008.
    • О грамматиках, основанных на двух вариантах исчисления Ламбека. 2009.
  • Александр Валентинович Харитонов
    • Полнота исчисления Ламбека относительно моделей на конечных полугруппах с делением. 2007.
    • О сложности построения минимального суффиксного автомата для скользящего окна. 2008.
    • О построении сжатого суффиксного автомата в скользящем окне. 2009.
  • Алексей Андреевич Сорокин
    • Непосредственное доказательство эквивалентности различных критериев выводимости в циклической линейной логике. 2009.
    • О длине совмещающего типа в исчислении Ламбека. 2010.
    • О сетях доказательства для различных вариантов исчисления Ламбека. 2011.
  • Михаил Михайлович Звонкин
    • О взаимосвязи критериев выводимости секвенций в исчислении Ламбека без умножения. 2010.
    • Языковые модели исчисления Ламбека с единицей. 2011.
    • Языковые модели фрагментов исчисления Ламбека с операциями объединения и пересечения. 2012.
  • Станислав Сергеевич Макеев
    • Критерии выводимости в исчислении Ламбека. 2010.
    • Эквивалентность критериев выводимости в исчислении Ламбека с одним делением. 2011.
    • Сложность проблемы распознавания выводимости в исчислении Ламбека без умножения при ограничении на количество вхождений одной из связок. 2012.
  • Иван Михайлович Смуров
    • Поиск минимального интерполянта в исчислении Ламбека для данного множества примитивных типов. 2010.
    • Минимальные постинтерполянты в исчислении Ламбека без умножения. 2011.
    • Предынтерполянты и постинтерполянты в исчислении Ламбека без умножения. 2012.
  • Надежда Сергеевна Рыжкова
    • Некоторые правила исчисления Ламбека с положительной итерацией. 2011.
    • Об исчислении Ламбека с двумя делениями и итерацией. 2012.
    • Свойства категориального исчисления зависимостей. 2013.
  • Натали Аларкон Лопэс
    • О решении некоторых уравнений в исчислении Ламбека с одним делением. 2012.
    • Поиск вывода в исчислении Ламбека с одним делением. 2013.
    • Различные аксиоматизации фрагментов исчисления Ламбека. 2014.
  • Анастасия Сергеевна Александрова
    • Сравнение сетей доказательства для некоммутативной линейной логики. 2014.

Диссертации

Home Papers Teaching CV Leisure
MPАдрес: http://lpcs.math.msu.su/~pentus/problems.htm
Изменения внесены 01.10.2019.
Мати Рейнович Пентус
Телефон/факс: + 7 — 495 — 939 30 31