Деятельность кафедры

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

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

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

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

Математическая логика сложилась как научная дисциплина в начале XX века в результате так называемого кризиса в основаниях математики. Выдающихся математиков и философов той героической эпохи (Гильберт, Пуанкаре, Брауэр, Вейль, Фреге, Рассел и др.) волновали такие фундаментальные вопросы, как:

• Что означает доказать математическую теорему? Какие средства при этом законно использовать?
• Что значит выразить то или иное математическое понятие или утверждение в том или ином языке?
• Как построить непротиворечивую систему аксиом теории множеств?
• Можно ли доказать любое истинное утверждение, скажем, относящееся к арифметике целых чисел?
• Противоречива ли математика? И если нет, то каким образом это можно установить?

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

Формальные языки и формальные системы впервые возникли именно в математической логике, поэтому неудивительно, что наиболее практически значимые системы такого рода — вычислительные модели, языки программирования — также обязаны своим открытием нашей науке. Важным толчком к анализу понятия вычислимости послужила формулировка Гильбертом так называемой Entscheidungsproblem — проблемы существования алгоритма, по данному утверждению в логике предикатов отвечающего на вопрос, доказуемо ли оно. Отрицательное решение этой проблемы, вместе со строгой формулировкой понятий вычислимой функции (и алгоритмически разрешимой проблемы) было дано А. Черчем и, независимо, А. Тьюрингом в 1935-36 годах. При этом Тьюринг сформулировал ставшее классическим понятие универсальной вычислительной машины, ключевые черты которой были еще через 15 лет воплощены, в том числе и самим Тьюрингом, в реально работающих компьютерах. (Работа Черча, основанная на другой универсальной вычислительной модели, λ-исчислении, так же не осталась забытой — это исчисление послужило прообразом целого класса языков программирования, так называемых функциональных языков, весьма популярных в настоящее время.)

При том, что проблематика оснований математики, теории доказательств и теории алгоритмов по прежнему остается актуальной, к настоящему времени область приложений методов математической логики значительно расширилась. Возникает более широкое понимание того, что составляет предмет и задачи математической логики.

Математическая логика и теория алгоритмов строят математические модели того, как человек мыслит, передает мысли другому, преобразует мысли в действия. Это явное присутствие человека отличает наш предмет от других областей математики, делает его особенно интересным и нужным, приводит к использованию, в том числе, гуманитарных источников задач и приложений. О гуманитарной природе всей математики можно читать в работах профессора Владимира Андреевича Успенского, который с 1995 по 2018 г. заведовал нашей кафедрой.

Математическая логика и теория алгоритмов являются фундаментальной основой когнитивных наук, начавших наиболее бурное развитие в XXI веке. Если XIX был веком математических моделей механических систем (включая модели «небесной механики» и «тепловых машин»), основной научно-технологического прогресса в XX веке были математические модели информационных систем, то в XXI веке математики строят модели, позволяющие сделать «точными», снабдить математическим аппаратом такие области знания, как биология и гуманитарные: психологию, философию, лингвистику, педагогику. Эти модели строятся именно в нашей области математики и, кроме того, служат основой для построения систем искусственного интеллекта. Не удивительно, что именно В. А. Успенскому принадлежала инициатива реформы лингвистического образования, введения в него курса математики. Реализацией этой инициативы стало открытие отделения «точного языкознания» (отделения теоретической и прикладной лингвистики) на филологическом факультете МГУ. Наша кафедра продолжает традицию сотрудничества с этим отделением — сотрудники и аспиранты преподают там математику и ведут научные семинары.

Традиции и наследие кафедры

Первый действующий семинар по математической логике существовал на мехмате МГУ с тридцатых годов XX века. Руководителями этого семинара были академик Петр Сергеевич Новиков, работавший в Математическом институте им. В. А. Стеклова (МИАН) и Московском государственном педагогическом институте им. В. И. Ленина (сейчас МПГУ), и профессора мехмата МГУ Софья Александровна Яновская и Иван Иванович Жегалкин. В наше время этот семинар функционирует как кафедральный семинар по математической логике и теории алгоритмов.

Решение о создании кафедры математической логики МГУ, а также одновременно с ней и отдела математической логики в МИАН, было принято на Третьем Всесоюзном математическом съезде. Кафедра была открыта в 1959 году, и первым её заведующим стал чл.-корр. АН СССР Андрей Андреевич Марков (мл.).

Отметим, что Математический институт РАН им. В. А. Стеклова (МИАН) является центром научных исследований в области математики в России, бесспорна и его роль во всей мировой математике. Профессор нашей кафедры, академик С.И. Адян руководит отделом математической логики МИАН, в котором работают и сотрудники нашей кафедры проф. Л. Д. Беклемишев, асс. С. Л. Кузнецов, В. В. Подольский. Плодотворное взаимодействие между кафедрой и отделом математической логики МИАН возникло со времени их основания и продолжает быть важным фактором для поддержания высокого уровня научных исследований в нашей области, для перспектив аспирантуры и для дальнейшей работы способных выпускников нашей кафедры, заинтересованных в продолжении научной деятельности и сильном научном руководстве. (Можно отметить, что в настоящее время из восьми сотрудников отдела семеро являются выпускниками нашей кафедры.)

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

А. Н. Колмогоров был автором первых результатов по математической логике в нашей стране, которые касались формализации интуиционистской логики и её интерпретации как «логики задач». В дальнейшем он (вместе со своим учеником В.А. Успенским) внес важный вклад в исследование понятия алгоритма и стал основоположником алгоритмической теории информации (колмогоровской сложности).

П. С. Новиков внес выдающийся вклад в теорию множеств, в теорию доказательств, исследование алгоритмических проблем в алгебре и комбинаторную теорию групп. Им была построена конечно определенная группа с неразрешимой проблемой равенства слов (решение так называемой проблемы слов в группах). Он был автором одного из первых учебников по математической логике в нашей стране «Элементы математической логики». Наконец, совместно со своим учеником С.И. Адяном, им была решена одна из труднейших математических проблем, имеющих многолетнюю историю — проблема Бернсайда о периодических группах.

Ан. А. Марков был основоположником традиции в основаниях математики, известной в мире как «русский конструктивизм». Ему принадлежит понятие алгорифма Маркова, одной из стандартных в настоящее время универсальных вычислительных моделей. Он также получил фундаментальные результаты, касающиеся неразрешимых алгоритмических проблем в математике: теорему о нераспознаваемости свойств конечно определенных полугрупп, а также теорему о нераспознаваемости гомеоморфизма топологических многообразий в размерностях больше четырех.

Ниже мы подробнее расскажем об основных направлениях работы кафедры.

Теория доказательств и основания математики

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

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

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

Традиция исследований по теории доказательств на кафедре восходит к работам П. С. Новикова по формальной арифметике 1940-х годов и работам Ан. А. Маркова по конструктивной математике, которые были c успехом продолжены его учениками А. Г. Драгалиным и С. Н. Артёмовым (см. далее). долгое время работавшими на нашей кафедре В настоящее время в области теории доказательств работает профессор кафедры, чл.-корр. РАН Лев Дмитриевич Беклемишев, а также его ученики, Данияр Салкарбекович Шамканов и Федор Николаевич Пахомов (МИАН и факультет математики НИУ ВШЭ).

Исследования Л. Д. Беклемишева касаются формальной арифметики, связей между аксиомами арифметики и классами вычислимых функций, которые можно верифицировать с помощью тех или иных аксиом. Другое направление относится к изучению прогрессий Тьюринга — последовательностей теорий, получающихся каждый раз расширением системы аксиомой, выражающей её непротиворечивость. Эти результаты приводят к глубоким обобщениям теоремы Гёделя о неполноте и позволяют увидеть интересные математические (порядковые и алгебраические) структуры в мире арифметических теорий.

Ф.Н. Пахомов, защитивший кандидатскую диссертацию в 2015 году, в одной из своих последних работ исследовал остроумное понятие «медленной доказуемости», которое приводит к новому классу независимых утверждений более слабых, чем гёделевское утверждение о непротиворечивости формальной арифметики.

Д.С. Шамканов занимается структурной теорией доказательств, то есть наукой о построении формальных доказательств и о преобразованиях одного формального доказательства в другое. Недавно им был исследован новый интересный класс выводов — так называемые циклические выводы — которым позволяется до некоторой степени иметь «порочный круг». С помощью этого понятия, проходящего в опасной близости от противоречивости, он получил несколько впечатляющих результатов, относящихся к исследованию традиционных систем.

Исследованиями в области аксиоматики теории множеств занимаются наши выпускники, ученики В. А. Успенского: профессор нашей кафедры Василий Александрович Любецкий и профессор Владимир Григорьевич Кановей, работающие также в Институте проблем передачи информации РАН.

В течение столетий и даже тысячелетий математики в своих рассуждениях использовали интуитивные представления о бесконечно малых и бесконечно больших величинах. Формальное построение математики на основе теории действительных чисел обошлось без этих представлений. Однако математическим логикам удалось построить так называемый «нестандартный анализ», где бесконечно малые и бесконечно большие существуют и помогают доказывать теоремы обычного анализа. В. Г. Кановей и В. А. Любецкий ведут работы и в этом направлении.

Логика структур

Что можно выразить? Что можно проверить? Теория моделей, теория множеств

Вопросом о том, что можно определить, выразить на языке математики, обладая некоторым исходным запасом понятий, занимается выпускник нашей кафедры академик РАН Алексей Львович Семенов вместе с ее выпускником, учеником В. А. Успенского Сергеем Федоровичем Сопруновым, с ними работал и рано умерший замечательный математик, и тоже наш выпускник Андрей Альбертович Мучник, ученик А. Л. Семенова. Примером результата о выразимости является теорема Семенова о выразимости через сложение натуральных чисел всех отношений, задаваемых конечные автоматами в двух разных системах счисления. Недавний результат — описание всех подпространств выразимости в пространстве сложения рациональных чисел.

Среди других их результатов — решение вопросов о существовании алгоритма, который проверяет истинность утверждения в логическом языке относящихся к некоторых естественным структурам чисел и слов. Примером такой структуры являются натуральные числе со сложением и операцией экспоненты с фиксированным натуральным основанием. Ан. А. Мучник решил проблему, относящуюся к разрешимости теории бесконечного дерева и множества его вершин, поставленную М. Рабином на Международном математическом конгрессе в Ницце.

Одной из основных областей математической логики является теория моделей. Эта теория исследует соотношения между теориями и классами структур, ими описываемых. Исследования в теории моделей также ведет В. А. Любецкий.

Модальная логика

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

Пытаясь математически охватить самый широкий круг человеческих рассуждений, математические логики стали рассматривать понятия «возможно», «необходимо», «когда-нибудь будет» и т. д., так называемые «модальности». На этом пути еще в древности возникла модальная логика. Современная модальная логика стала одним из инструментов решения задач информатики — как теоретических, так и вполне прикладных. При этом используется развитый в математической логике аппарат — алгебраический, топологический, теоретико-модельный. Модальными логиками занимается профессор Валентин Борисович Шехтман, которому принадлежит ряд результатов в данной области, ставших классическими. Ученик В. Б. Шехтмана Илья Борисович Шапировский работает в Институте проблем передачи информации (ИППИ РАН), другой ученик — Андрей Валерьевич Кудинов — в ИППИ и Высшей школе экономики. Выпускник нашей кафедры Станислав Павлович Кикоть в своей диссертации по модальной логике, защищенной на мехмате, получил обобщение известной теоремы Салквиста; в настоящий момент он работает в Лондоне (Birbeck University of London).

Интересно рассмотреть и такую модальность, возникающую внутри самой математики, как «доказуемость». Логикой доказуемости занимается проф. Л. Д. Беклемишев и его ученики.

К модальным логикам близки логики описания понятий — дескрипционные логики, используемые для представления знаний. На дескрипционных логиках основан компьютерный язык сетевых онтологий OWL (Web Ontology Language), применяемый для представления знаний как о реальных объектах, таких, как лекарства, заболевания, белки, гены, так и о виртуальных, как веб-ресурсы, веб-сервисы, базы данных, и компьютерного вывода следствий из известных фактов или проверки, следует ли тот или иной факт из уже имеющихся. Возникающие здесь задачи решают методами модальной логики, а также — создавая специфические новые подходы и алгоритмы. Модальными логиками вообще, и дескрипционными логиками в частности, занимается старший научный сотрудник кафедры Евгений Евгеньевич Золин, ученик С.Н. Артемова и В.А. Успенского. В 2004-2007 гг. Е. Е. Золин работал в Манчестерском университете (Великобритания) в проекте “Dynamic Ontologies”, связанным с дескрипционными логиками.

Интуиционизм, логика задач, конструктивизм

Желание построить убедительный фундамент для математики, выделить «наиболее надежные» методы доказательства и построения составляли важнейший мотив и двигатель исследований крупных математиков XX века. Это привело, в частности, к появлению подхода, называемого «интуиционизмом». Предложение интуиционизма состоит, в частности, в том, чтобы не считать, что какое-то из двух утверждений верно, если мы не знаем, какое именно. Академик Андрей Николаевич Колмогоров еще в 1925 году опубликовал работу, в которой с обычной логикой соотносил логику, возникающую, если принять эту позицию интуиционизма. Понимание интуиционистской логики как логики задач, было предложено Колмогоровым в 1932 году. Это понимание послужило источником для многих последующих работ, в том числе, выполняемых на нашей кафедре. Великий российский ученый А. Н. Колмогоров заведовал нашей кафедрой с 1980 г. и до своей смерти в 1987 году. О его исследованиях, связанных с теорией алгоритмов, мы скажем далее.

Среди математических рассуждений и построений часто хочется выделить «более конструктивные», помогающие не только доказать, что что-то существует, но и найти соответствующий объект, построить, сконструировать его. Это стало основой математической философии «конструктивизма» и большого цикла исследований выдающегося российского математика, члена-корреспондента АН СССР Андрея Андреевича Маркова, заведовавшего кафедрой с момента ее основания в 1959 году и до последних дней своей жизни в 1979 г., его учеников и последователей А.Г. Драгалина и С.Н. Артёмова, долгое время работавших на нашей кафедре. Сейчас С.Н. Артемов занимает должность Distinguished professor в CUNY Graduate Center, Нью Йорк. А. Г. Драгалин скончался, работая профессором Дебреценского университета (Венгрия).

Исследованиями логик, в которых используются различные модальности, доказуемость, идеи конструктивности, занимаются ученики В. А. Успенского и сегодняшние сотрудники нашей кафедры: Владимир Николаевич Крупский, Валерий Егорович Плиско, Татьяна Леонидовна Яворская.

Комбинаторика слов. Алгоритмические проблемы

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

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

Заметим, наконец, что Слово оказывается началом всего сущего в мировых религиях.

В 1900 году Гильберт сформулировал свой знаменитый список проблем, в котором десятая состояла в поиске алгоритма решения полиномиальных уравнений в целых числах. Эта проблема получила отрицательное решение в 1970-м году в работе студента Ленинградского университета, ныне академика РАН Юрия Владимировича Матиясевича, представителя научно школы Андрей Андреевича Маркова в Санкт-Петербурге. В работах Геделя, Поста, Тьюринга в 1930-е годы появилось формальное определение того, что значит, что некоторая функция вычислима, что значит, что задача построения алгоритма — неразрешима. В конце 1940-ых годов общее определение вычислимости функций над словами было предложено А. А. Марковым. Замечательно, что еще до начала распространения компьютеров и программирования А. А. Марков построил систему структурного программирования и индуктивного доказательства правильности программ и детально доказал правильность работы компилятора (для своих — абстрактных, алгоритмов). Общий вид алгоритмов, работающих с графами был описан А. Н. Колмогоровым и В. А. Успенским в начале 1950-ых гг.

П. С. Новиков построил конечно определенную группу с неразрешимой проблемой равенства (в группе) элементов, задаваемых с помощью определяющих соотношений — словами над алфавитом порождающих. В терминах слов естественно формулируются и свойства самих групп и полугрупп. А. А. Марков доказал нераспознаваемость нетривиальных свойств конечно определенных полугрупп. Некоторые свойства групп оказывается возможным (алгоритмически) распознать по заданию группы. Однако для всех «естественно интересных» свойств нужного алгоритма не существует. Это доказал С. И. Адян в 1955 г. и двумя годами позже М. Рабин. Результат Адяна был вскоре использован А. А. Марковым для доказательства неразрешимости классической проблемы распознавания гомеоморфности топологических многообразий в размерностях больше четырех.

С. И. Адяну принадлежит и весьма тонкое доказательство существования алгоритма для задачи, которую легко понять школьнику: фиксировано слово, его разрешается вставлять в другие слова или вычеркивать в них; можно ли из одного слова получить другое?

Решение проблемы Бернсайда и алгебраические приложения

Еще в 1902 г. Уильям Бернсайд поставил проблему конечности конечнопорожденной группы, в которой одна и та же степень каждого элемента равна единице. В 1959 году П. С. Новиков объявил о существовании бесконечных групп с этим свойством. Построение полного доказательства потребовало нескольких лет напряженной работы ученика П.С. Новикова — ныне академика, профессора нашей кафедры Сергея Ивановича Адяна. Развитые при этом методы работы со словами позволили решить целый ряд других сложных проблем в теории групп, в течение многих лет не поддававшихся решению.

Модели языка. Математическая лингвистика

От языков математики вернёмся к разнообразию естественных и искусственных языков человека. Математики создают инструменты для их описания и устанавливают различные свойства возникающих моделей.

К области алгоритмического анализа контекстно-свободны грамматик и структурных свойств порождаемых ими языков относятся первые работы А. Л. Семенова. Сегодня проблематикой математической лингвистики на кафедре занимаются профессор Мати Рейнович Пентус и его ученики: Степан Львович Кузнецов и Алексей Андреевич Сорокин. Еще в тридцатые годы логик К. Айдукевич предложил подход, а в 1950-60 гг. алгебраист И. Ламбек развил формализм, центральным понятием которых является понятие синтаксической категории. Законы, управляющие преобразованиями категорий, позволяющие строить синтаксически правильные предложения, похожи на алгебраические или логические правила. Система таких правил образует так называемую категориальную грамматику.

Категориальная грамматика позволяет не только установить, является ли фраза грамматически корректной, но и извлечь из неё некоторую информацию о её семантике («смысле»), т.е. играет роль интерфейса между синтаксисом и семантикой в модели «смысл — текст». М. Р. Пентусу принадлежат основные теоретические результаты об исчислении Ламбека: точная оценка задаваемого им класса формальных языков, теорема о полноте исчисления относительно его естественной интерпретации, алгоритмическая сложность проблемы выводимости в исчислении. Исходного исчисления, введённого Ламбеком, не хватает для описания всех феноменов естественного языка, поэтому были предложены многочисленные расширения этого формализма. Некоторые из этих расширений используются для автоматического разбора предложений и извлечения их семантики в системах искусственного интеллекта. Расширения грамматик Ламбека исследовались А. А. Сорокиным («разрывные» синтаксические операции, также называемые операциями замещения) и С. Л. Кузнецовым (субструктурные модальности, операции пересечения и объединения, операция обращения) — в том числе совместно с коллегами из других городов: М. И. Кановичем (Лондон), Г. Морриллом (Барселона), А. С. Охотиным (Санкт-Петербург), А. Щедровым (Филадельфия). С различными вариантами категориальных грамматик связано много интересных нерешённых математических задач, и будущие студенты кафедры приглашаются присоединиться к их решению.

Сверхслова. Символическая динамика

Слова и их бесконечные аналоги — сверхслова, помимо логики и алгебры, изучаются и в теории динамических систем: если в дискретные моменты времени с ограниченной точностью регистрируются состояния системы, возникает сверхслово. В широком классе ситуаций это сверхслово оказывается почти периодическим, то есть содержит частые повторения любого слова, которое встречается в нем бесконечное число раз. Логикой сверхлов занимались А. Л. Семенов, Ан. А. Мучник и их ученик Юрий Львович Притыкин, выпускник нашей кафедры. После защиты кандидатской диссертации в МГУ он получил степень PhD в Принстонском университете и теперь занимается в США математическими проблемами биологии. Работы С. И. Адяна, А. Л. Семенова и их учеников в последние годы получили продолжение в результатах федерального профессора математики Алексея Яковлевича Канеля-Белова и его учеников.

Эффективные алгоритмы на словах и графах

Выпускник и профессор нашей кафедры, ученик В. А. Успенского Василий Александрович Любецкий, известный своими результатами в области теории моделей и теории множеств, работает также в Институте проблем передачи информации РАН, где заведует лабораторией математических методов и моделей в биоинформатике. Биоинформатика относится к числу наиболее перспективных, быстро развивающихся и дающих важные практические применения областей знания. Применение в ней методов математической логики и теории алгоритмов обусловило эффективность исследований В. А. Любецкого, упомянутых выше Ю. Л. Притыкина, Т. А. Стариковской, профессора Михаила Абрамовича Ройтберга, тоже нашего выпускника, работавшего в Институте математических проблем биологии — филиале Института прикладной математики им. М. В. Келдыша РАН.

Эффективные алгоритмы на словах — тема студенческой работы и кандидатской диссертации Татьяны Андреевны Стариковской, ученицы А. Л. Семенова и М. А. Бабенко. Студенткой она получила грант Аниты Борг, работала в Яндексе, ВШЭ, была постдоком в IRIF в Париже, работала в Бристольском университете; сейчас — в Высшей нормальной школе (Ecole normale superieure, Париж).

Задачами дискретной оптимизации занимаются В. А. Любецкий и выпускники нашей кафедры К. Ю. Горбунов, О. А. Зверков и др. Приведём пример их результата: фиксированы операции над графами; найден алгоритм с линейным временем работы, который преобразует этими операциями один данный граф в другой, тоже данный.

Построение эффективных алгоритмов на графах — тема исследований нашего выпускника, ученика Н. К. Верещагина Максима Александровича Бабенко, который сейчас заведует базовой кафедрой Яндекса в Высшей школе экономики.

Компьютерные технологии. Сложность вычислений и проблема перебора

Естественно, что построенный в математической логике аппарат анализа интеллектуальной, в частности, математической деятельности оказался востребованным, когда электроника «доросла» до математики в деле создания «математических машин», называемых компьютерами. В «эру компьютеров» и под влиянием вычислительных наук в математике были получены важные результаты, в том числе — нашими сотрудниками и выпускниками. На вводных лекциях по системному программированию часто вспоминают теорему Успенского, которая утверждает алгоритмическую невозможность распознать по программе какого-либо нетривиального свойства вычисляемой ею функции. С 1988 г. до последних дней жизни в 1993 г. нашей кафедрой заведовал академик Владимир Андреевич Мельников, участник создания самого знаменитого советского компьютера БЭСМ-6 и многих других отечественных компьютеров, включая супер-ЭВМ. (В последней работе принимал участие и А. Л. Семенов.)

Самой важной и самой загадочной проблемой современной математики и ее приложений сегодня называют проблему перебора — выяснения того, можно ли некоторые естественно возникающие в практике и теории задачи решать существенно быстрее, чем просто перебором вариантов. Явная формулировка этой проблемы и соответствующие математические утверждения были найдены параллельно американским математиком Куком и студентом нашей кафедры, учеником А.Н. Колмогорова Леонидом Анатольевичем Левиным. Сегодня Л. А. Левин — лауреат премии Кнута, профессор Бостонского университета.

Среди наиболее впечатляющих попыток частичного решения этой проблемы — результат Александра Александровича Разборова, который рассмотрел алгоритмы некоторого естественного вида и решил проблему для них. А. А. Разборов получил свой результат, будучи студентом нашей кафедры. Сегодня он — член-корреспондент РАН, сотрудник Математического института им. В.А. Стеклова РАН и Чикагского университета, лауреат премий Неванлинны и Гёделя.

В настоящее время широкий спектр исследований по теории сложности ведется и выпускниками нашей кафедры, учениками В. А. Успенского, профессором Николаем Константиновичем Верещагиным и Александром Шенем, при участии их учеников. В них также принимал участие Ан. А. Мучник. В этом и последующих разделах мы приводим несколько примеров нерешенных задач в данной области, связанных с результатами, полученными этими математиками. Среди важных объектов изучения — так называемые односторонние функции. Так называются функции, которые легко (быстро) вычислить, но трудно обратить (чтобы найти некоторый прообраз данного объекта, требуется много времени). Односторонние функции применяются во всех современных протоколах защиты информации, а также при построении генераторов псевдослучайных чисел. Сложность вычислений связана с колмогоровской сложностью (о ней речь пойдет дальше) и с коммуникационной сложностью. И та, и другая используются в сложности вычисления как средство доказательства нижних оценок времени, необходимого для решения конкретных задач. Другим важным инструментом являются коды с исправлением ошибок. Вот пример нерешенной задачи в коммуникационной сложности: задача о различении близких и далеких слов.

Искусственный интеллект. Автоматизация доказательства

К числу наиболее бурно развивающихся сегодня областей применения компьютеров относится так называемое машинное обучение. С самого начала создания и применения компьютеров в 1950-ых гг. предпринимались попытки использовать компьютеры не просто для быстрых вычислений по заданному заранее относительно несложному алгоритму, но и для автоматизации не до конца описанных, или при формализации приводящих к переборным задачам, видов интеллектуальной деятельности человека. В последние десятилетия в данной области — искусственно интеллекте, были достигнуты огромные успехи. Исследованиями в данном направлении на кафедре занимается наш выпускник, сотрудник МИАН и руководитель Департамента больших данных и информационного поиска ВШЭ Владимир Владимирович Подольский.

Появление компьютера, как инструмента автоматизации интеллектуальной деятельности человека, закономерно привело и к созданию компьютерных инструментов автоматизации построения и проверки математических доказательств. Все студенты кафедры знакомятся с одним из наиболее известных таким инструментов — системой Coq — в практическом курсе, разработанном В.Н. Крупским и С.Л. Кузнецовым для студентов 3-го курса кафедры. Участвовать в занятиях Coq-практикума могут и другие студенты мехмата, а также других факультетов и университетов.

Колмогоровская сложность

Колмогорову принадлежит одно из наиболее замечательных определений математики — сложности объекта, как минимальной длины его описания. Основы теории колмогоровской сложности объектов были построены А.Н. Колмогоровым во время его поездки в Индию в 1964 году. Поставленная в его индийской статье проблема была решена 40 лет спустя Ан.А. Мучником и А.Л. Семеновым, за что они получили премию Колмогорова Российской академии наук. Подход Колмогорова является основой сегодняшних представлений о количестве информации и меры случайности. Этот подход, как и проблематику сложности вычислений развивают сегодня Н. К. Верещагин, А. Шень и их ученики. Многие важные проблемы о колмогоровской сложности понятны и интересны даже младшекурсникам. Вот примеры таких (нерешенных) проблем: задача о кошках и муравьях, задача о разделении ресурсов в иерархической структуре, задача об он-лайн паросочетаниях, задача об избегании окрашенных мест.

Алгоритмическая статистика. Случайность

Последней областью интересов А. Н. Колмогорова была основанная им «алгоритмическая статистика». Сейчас многие исследования в этом направлении, также идут в научной школе Н. К. Верещагина. Классическая теория вероятностей не объясняет, почему, имея последовательность из тысячи нулей, полученную бросанием монетки, мы отвергаем гипотезу о том, что монетка была симметричной, а бросания независимыми. Теория алгоритмов позволяет объяснить этот факт — эта последовательность слишком проста (ее колмогоровская сложность ничтожна). Колмогоров предложил измерять правдоподобность статистической гипотезы о происхождении данной двоичной последовательности (здесь и далее в данном абзаце — конечной) разностью модуля двоичного логарифма ее вероятности (относительно распределения вероятностей, задаваемого гипотезой) и ее сложности. Эту разность он назвал «дефектом случайности x». Последовательность x называется стохастической, если существует простая статистическая гипотеза, дефект случайности x относительно которой мал. Колмогоров не знал, существуют ли нестохастические последовательности. На этот вопрос ответили выпускники кафедры, ученики В. А. Успенского Владимир Вячеславович Вьюгин и Александр Шень, которые доказали их существование и оценили количество. В алгоритмической статистике много открытых вопросов. Например, неясно, всегда ли метод наибольшего правдоподобия, выбирающий среди простых гипотез ту, которая максимизирует вероятность последовательности, дает оптимальную статистическую гипотезу, то есть, гипотезу с наименее возможным дефектом случайности (среди простых гипотез).

Дефект случайности можно определить и для бесконечных последовательностей (относительно вероятностной меры на пространстве бесконечных 0-1-последовательностей). В отличие от конечных, бесконечные последовательности можно разделить на случайные (их дефект случайности конечен) и неслучайные. Впервые это было сделано учеником Колмогорова шведским логиком Пером Мартин-Лёфом. П. Мартин-Лёф — академик Шведской королевской академии наук; он руководил объединенной кафедрой математики и философии Стокгольмского университета до 2009 г. Итоги исследований в этом направлении были подведены в статье «Математическая метафизика случайности» Ан.А. Мучника, А. Л. Семенова и В. А. Успенского и книге В.А. Успенского, Н.К Верещагина и А. Шеня «Колмогоровская сложность и алгоритмическая случайность». Тематику случайности продолжают ученики А. Шеня.

Математическое образование

Гуманитарная составляющая математической логики и теории алгоритмов, о которой говорилось выше, и содержание этого предмета ведёт к педагогике — вопросам преподавания математики. Сотрудники нашей кафедры всегда принимали участие в математическом образовании, в различных формах и на различных уровнях. Навыки системного, логичного представления математического знания, понимание оснований математики, того, как она строится, наряду со связью с современными компьютерными науками, помогает нашим выпускникам в построении математических курсов. Выше упоминалась роль В.А. Успенского в создании отделения теоретической и прикладной лингвистики МГУ и преподавание там наших сотрудников. Заслуги В.А. Успенского в математическом образовании и распространении математической культуры отмечены престижной премией «Просветитель». А.Н. Колмогоров, а в последние годы А.Л. Семенов, оказали существенное влияние на развитие в стране школьного математического образования и особенно школьной информатики, что было отмечено премией ЮНЕСКО, полученной А. Л. Семеновым в 2009 г. А.Л. Семенов — автор ряда школьных учебников по информатике и математике, в которых базовые понятия математики (не только арифметики) излагаются на наглядном материале, главный редактор журнала «Квант», которым при его основании руководил А.Н. Колмогоров. А.Н. Колмогоров основал Физико-математическую школу-интернат при МГУ, теперь — СУНЦ им. А.Н. Колмогорова. В течение многих лет А. Л. Семенов работал ректором педагогического вуза, сейчас руководит Институтом образовательной информатики ФИЦ «Информатика и управление» РАН. С.Ф. Сопрунов — лидер важного направления в творческом применении компьютера в школе и обучении детей программированию, которое использует язык Лого и образовательную философию конструкционизма. Наши выпускники: С. Л. Кузнецов, А. Е. Подгайц — ведущие преподаватели Малого мехмата, математических школ и кружков. Сегодня преподавание в хорошей школе дает существенно лучшую зарплату выпускнику университета, чем работа ассистента в вузе. Кафедра может помочь в получении работы в лучших школах города.

Но, конечно, работа в высшей школе может представляться выпускнику более естественной. Ряд наших сотрудников совмещает преподавание в МГУ с преподаванием в Высшей школе экономики, МФТИ и т.д. Мы оказываем содействие нашим выпускникам и в направлении преподавательской деятельности.

Наши награды

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

• С. И. Адян: премия им. П. Л. Чебышёва АН СССР, Государственная премия РФ, премия Александра фон  Гумбольдта (Германия), золотая медаль «За выдающийся вклад в математику» Института математики им. С. Л. Соболева СО РАН, премия фонда Династия «Жизнь, посвященная математике»;
• Л. Д. Беклемишев: премия Московского математического общества;
• М. Р. Пентус: премия Московского математического общества;
• А. А. Разборов: премия Р. Неванлинны Международного математического союза, премия им. К. Гёделя ACM SIGACT и EATCS;
• А. Л. Семенов: премия Президента РФ, премия Правительства РФ, премия ЮНЕСКО, премия им. А.Н. Колмогорова РАН;
• В. А. Успенский: премия «Просветитель».

Ещё о перспективах студентов после окончания университета

Научные исследования

Многие наши студенты получают серьезные научные результаты еще до окончания бакалавриата. Они продолжают свою научную работу, публикуют статьи, участвуют в конференциях, в том числе — международных, защищают диссертации. Научная работа может идти как во время обучения, так и после его окончания. Основные организации, ведущие математические исследования, сосредоточены в Российской академии наук (РАН) — это уже упомянутые МИАН, ИППИ РАН и другие. Многие выпускники нашей кафедры (в том числе упомянутые выше) работают в университетах других стран. Вот ещё один пример: Александр Шень, выпускник нашей кафедры, начавший заниматься на ней, еще будучи школьником, и знаменитый среди многих поколений школьников преподаватель математики, работает сейчас в городе Монпелье (Франция), в лаборатории при университете Монпелье и CNRS (французском национальном центре научных исследований).

Преподавание

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

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

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

Информационные технологии

Как вы уже понимаете, еще одна область успешного приложения сил для наших выпускников, — это программирование и компьютерные системы, связанные с естественными языками. Естественно, что при приёме на работу в таких компаниях, как Яндекс или Google, наши выпускники востребованы.