Владимир Подольский о преподавании и научной работе
.jpg)
– Владимир, расскажите о своей преподавательской деятельности.
– Я веду курс “Дискретной математики” для студентов образователной программы “Прикладная математика и информатика” факультета компьютерных наук, а также курс “Вычислимость и сложность” в программе Math in Moscow в Независимом Московском Университете, где обучаются американские студенты. Их приезжает примерно пятнадцать человек в семестр, через полгода они возвращаются в свои университеты, где им засчитывают сданные в Москве курсы.
Кроме того, уже несколько лет я веду на мехмате МГУ семинар для младшекурсников по математической логике и информатике.
Раньше я преподавал в школе 54 в классе при мехмате МГУ. Это был класс детей, которые специально хотели учиться математике, поэтому ощущения от преподавания у меня были только положительные.
– Вы работаете в математическом институте В. А. Стеклова. Расскажите чем Вы занимаетесь там.
– Это научно-исследовательский институт Российской Академии Наук – то есть, не учебное заведение, а научно-образовательное, там нет студентов. Есть немного аспирантов, но это люди, ориентированные на научную работу. Там я занимаюсь, собственно, научной деятельностью – задачами в области математики и теоретической информатики.
– Расскажите в общих чертах, что из себя представляет теоретическая информатика.
– Можно сказать, что это теоретические основы информатики. Есть собрание наук – компьютерные науки – и в них есть часть, которая занимается теоретическими основами. Можно провести такую аналогию: теоретическая информатика по отношению к другим компьютерным наукам – это как математика по отношению к естественным наукам.
Конкретно я занимаюсь сложностью вычислений. Это раздел, который изучает и классифицирует алгоритмические задачи с точки зрения сложности, рассматривает разные модели вычисления и сравнивает их вычислительные способности.
– Расскажите о каких-нибудь Ваших результатах в этой области?
– Есть такая наука, которая занимается базами данных. В ней есть направление, которое занимается теми базами, которые дополнительно снабжены некоторой логической теорией с разными утверждениями вида “если то, то это”. Из нее можно выводить какие-то новые следствия. Простой пример: допустим, у нас в базе записаны люди, и хранится информация о родственных связях между ними. Тогда мы можем сказать, что если кто-то является чьим-то отцом, то он мужчина. Это всегда верно, и если в базе не было информации про этот объект, что он мужчина, то мы можем ее вывести и пополнить базу.
База данных может быть огромной и разнородной, в ней может содержаться куча информации, которая конкретному пользователю не нужна. Логическая теория помогает создать для него какой-то удобный язык для работы с базой. Тогда он будет работать только с теми данными, которые ему нужны, вместо того, чтобы разбираться, как устроена вся база полностью, и читать огромные мануалы.
Вот для таких баз данных мы с соавторами исследуем некоторые вопросы. Мы показываем, что в случае слишком сложных теорий и запросов к базе, их обработка будет очень долгой. Эти результаты получены с помощью сведения этой задачи к другой, более классической, задаче теоретической информатики об оценках размера булевых схем. Мы доказали, что если бы некоторые, специально нами построенные, запросы было легко обрабатывать, то тогда некоторые булевы функции можно было бы вычислять булевыми схемами маленького размера. При этом, известно, что последнее неверно. Значит, и наш запрос сложный, и обрабатывать его будет тяжело.
– Вы недавно участвовали в двух конференциях по теоретической информатике – в Иркутске и в Германии.
– Это очень разного типа конференции. Computer Science in Russia, которая в этом году была в Иркутске – это крупнейшая в России ежегодная конференция по теоретической информатике. На нее люди подают работы, их рецензируют и, соответственно, принимают или не принимают.
Мне посчастливилось там быть приглашенным докладчиком, я делал обзорный доклад по тем результатам, про которые сейчас Вам рассказал. В целом, это типичная конференция по теоретической информатике. В мире есть более сильные конференции, очень много ученых работает в Америке и понятно, что все крупнейшие конференции проводятся там. Но в Европе эта конференция на серьезных позициях.
Конференция в Германии – совершенно другой формат. Она была посвящена 60-летию Дмитрия Юрьевича Григорьева – это известный специалист по теоретической информатике из Петербурга. Это была конференция, посвященная именно ему, организаторы – соавторы и близкие друзья Дмитрия Юрьевича – приглашали тех, кого они считали нужным, кого, по их мнению, было бы интересно послушать. Меня пригласили как соавтора, у нас с Григорьевым есть ряд совместных результатов. Я на эту тему делал доклад на коллоквиуме нашего факультета.
Конференция проходила в Дагштуле, замок в лесу. Там каждую неделю проводятся конференции по компьютерным наукам. Обычно в расписании не очень много докладов, поэтому есть свободное время и днем, и вечером, чтобы люди могли познакомиться, пообщаться и обсудить науку в спокойной обстановке.
– Можете выделить какие-то наиболее значимые прорывы в теоретической информатике за последнее время?
– Пожалуй, я бы назвал такую вещь: есть детерминированные алгоритмы, которые не используют случайные числа и вероятность, а есть, соответственно, вероятностные алгоритмы. Мы можем отдельно рассмотреть задачи, которые можно быстро решать детерминированными и вероятностными алгоритмами. “Быстро” здесь означает “за полиномиальное время”.
Получается два таких вот типа задач, и мы не знаем, совпадают эти классы задач или различаются, это открытый вопрос. Еще в начале 90-х специалисты, которые этим занимаются, считали, что это разные классы задач, то есть что бывают такие задачи, которые вероятностными алгоритмами можно решить быстро, а детерминированными нельзя.
А где-то в начале 2000-х были получены новые результаты, после которых люди стали считать наоборот, что, скорее всего, это одно и то же: если какую-то задачу можно быстро решить вероятностным алгоритмом, то можно и детерминированным. Было доказано, что из того, что верны некоторые нижние оценки на алгоритмическую сложность для некоторых задач, следует, что эти классы должны совпадать.
Благодаря новым результатам, интуиция у специалистов в этой области радикально сменилась.
Другое важное достижение было получено еще в начале 90-х, но его плоды ученые пожинают до сих пор. Центральная проблема в теоретической информатике – это проблема P=NP, про которую многие, наверное, слышали. Грубо говоря, она состоит в том, что у нас есть класс задач P, которые можно быстро решать, и есть класс задач NP, для которых потенциальное решение можно быстро проверить. И вопрос такой: совпадают ли эти классы задач?
То есть, если можно быстро проверить решение, то можно ли тогда быстро решить задачу? Вопрос хорош тем, что он фундаментальный, у него есть сотни эквивалентных формулировок в разных областях компьютерных наук.
Есть такое понятие как NP-полная алгоритмическая задача. Если для такой задачи построить быстрый алгоритм, то окажется, что названные выше классы совпадают. То есть, по существу, NP-полная задача – это самая трудная задача в классе NP.
Это все теоретическая модель. На практике NP-полную задачу может быть трудно решать только на тех входных данных, которые в каких-то практических приложениях реально не встречаются. Или, например, в задаче требуется найти какую-нибудь величину, но необязательно в точности, достаточно приближенно вычислить. Соответственно, есть такая область – приближенные алгоритмы. Задача сама по себе может быть трудная, а приближенное значение найти может быть легко.
Ученые в этой области научились доказывать, что такие приближенные задачи также трудны. То есть, если сама задача трудная, то и приближенное решение искать трудно. И тут уже среди NP-полных задач наблюдается большое разнообразие. Какие-то задачи можно приблизить до разумной степени, какие-то можно приближать очень хорошо, какие-то, наоборот, очень плохо поддаются приближению. И доказательство неприближаемости задачи потребовало очень нетривиальных рассуждений, это один из самых больших прорывов в теоретической информатике.
И это, кстати, хороший пример того, зачем в принципе заниматься теорией, не глядя на непосредственные практические приложения. В первых работах, которые привели к этому прорыву, люди интересовались не теми вопросами, которые я описал выше, а совсем другими, слабо связанными с практикой. В итоге же это привело к описанным выше результатам, которые для практики уже весьма интересны.
Интервью подготовил Сергей Заварин.
Подольский Владимир Владимирович