Магистратура по теоретической информатике, Академический Университет (РАН)

    image

    В Санкт-Петербурге есть замечательное место, где из программистов делают ученых — теоретиков Computer Science. Это Академический Университет Российской Академии Наук (АУ РАН).

    На тот момент, когда я поступила на Теоретическое Отделение кафедры Математических и Информационных Технологий АУ, отделение имело только один выпуск, состоящий из двух человек. Сейчас Академический Университет уже заработал себя прекрасное имя. Его выпускники работают в ведущих компаниях города, он принимает студентов из других городов, обеспечивая их жильем, а платное отделение стоит всего-навсего 10 тыс. рублей в семестр.

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


    Моя исследовательская работа в АУ


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

    Моей работой руководил Дмитрий Михайлович Ицыксон (ПОМИ РАН) и посвящена она была исследованию оптимальных алгоритмов. Это очень интересная тема, а замечательна она еще и тем, что ее легко объяснить, и я сейчас попробую это сделать.

    Мотивация

    Давайте посмотрим на какую-нибудь NP-полную задачу, например, на язык выполнимых формул. Будем рассматривать алгоритмы, которые останавливаются на любой формуле и возвращают в качестве ответа один бит — является формула выполнимой или нет. Вот уже 40 лет стоит вопрос, есть ли среди этого множества алгоритмов полиномиальный, и никто до сих пор не смог на него ответить. Однако, мы можем задаться другим, возможно, более простым вопросом, существует ли у этой задачи оптимальный алгоритм — алгоритм, который работает быстрее всех остальных с точностью до полинома (поскольку нас интересует только полиномиальность алгоритмов). Допустим, такой оптимальный алгоритм существует (назовем его A), тогда NP не равно P в том и только в том случае, если A не является полиномиальным. Это уже что-то, поскольку нам надо доказать неполиномиальность одного конкретного алгоритма, вместо того, чтобы делать это для всех возможных алгоритмов, решающих нашу задачу.

    Посмотрим на другой пример — на co-NP полную задачу, например, язык тавтологий (всюду верных формул). Существует большое количество систем доказательств для тавтологий: метод резолюций, система секущих плоскостей, системы Фреге и др. Вопрос о существовании системы доказательств, которая имела бы доказательства полиномиального размера эквивалентен открытому вопросу о равенстве классов NP и co-NP. На самом деле, удивительно, как много людей занимается сравнением конкретных систем доказательств и нахождением нижних оценок для них. Было бы здорово иметь оптимальную систему доказательств, тогда нам достаточно было бы изучать ее одну.

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

    Предыдущие исследования

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


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

    Результаты

    Вместо того, чтобы использовать случайные биты, надо постараться извлечь случайность (энтропию) из входа (поскольку больше неоткуда). Это можно сделать с помощью двудольного «перемешивающего» графа (что-то вроде lookup table), где в левой доле мы будем индексироваться по входу, а множество смежных вершин из правой доли будет давать нам множество псевдослучайных битов.

    После первой попытки сформулировать необходимые условия на граф, мы поняли, что сделать это в общем случае не представляется возможным, поэтому мы решили рассматривать более простой случай — язык множества образов инъективной функции, увеличивающей свой вход на один бит. Здесь у читателя (если есть читатели, которые сюда добрались) должно появиться законное возмущение: «кому же интересны такие языки»? Однако, допустим, мы интересуемся псевдослучайным генератором (существование доказуемо надежных инъективных генераторов, увеличивающих свой вход на один бит, является открытым вопросом). Тогда мы получим оптимальный алгоритм, который будет говорить: «правда ли, что данное (ему) число было порождено нашим генератором»? Если этот оптимальный алгоритм окажется полиномиальным, мы «сломаем» генератор, т.е. мы отличим числа, которые он порождает от действительно случайных! Это было бы действительно очень здорово, потому что мы бы нашли атаки на практически все существующие криптосистемы.

    Итак, в этом случае, дерандомизация нам удалась и более того, мы построили не только оптимальный эвристический полуалгоритм, но дополнили его до полного алгоритма.

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

    Пять причин, чтобы пойти в магистратуру АУ...


    … если вы хотите заниматься теоретической информатикой:
    1. АУ единственное место в Питере и одно из немногих в России, где вы можете посвятить себя изучению теоретической информатики.
    2. В АУ работают энергичные и бесспорно талантливые ученые.
    3. В АУ студенты могут влиять на программу обучения и выбирать часть курсов по своему усмотрению.
    4. АУ спонсирует поездки на школы, зарубежные в том числе.
    5. В АУ вы найдете бесплатный кофе из чудесной эспрессо машины! (дабы было что перерабатывать в теоремы).


    Что я делаю после окончания АУ?


    Я продолжаю заниматься теоретической информатикой в Стэнфорде. В предыдущей четверти я занималась вычислениями на зашифрованных данных с Dan Boneh, а сейчас буду заниматься схемной сложностью с Ryan Williams.

    Так что, мой совет — дерзайте, это стоит попробовать! Заявление можно подать прямо сейчас.
    Computer Science Center
    152,00
    Компания
    Поделиться публикацией

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

      +3
      Не зря наши программисты одни из лучших в мире. И все страны нам завидуют.
        0
        А чего вы минусуете человека, он правильно говорит.
          +12
          Вторая часть вызывает сомнения.
        • НЛО прилетело и опубликовало эту надпись здесь
            +17
            Простите, что? Наши программисты одни из лучших в мире?? Нет, я не спорю, что у нас есть очень хорошие программисты. Я даже не спорю, что, возможно, в теоретической информатике мы лидируем. Но делать вывод о том, что наши программисты одни из лучших на основании одного Академического университета, когда на западе во многих университетах похожие учебные программы даются ещё в бакалавратуре, это, простите, немного некорректно. Посмотрите открытые курсы MIT или Стэнфорда (в котором, если вы обратили внимание, сейчас и учится автор статьи), почитайте вопросы на StackOverflow, в конце концов, посчитайте количество компаний, занимающихся разработками, требующими серьёзных познаний в программировании, а потом уже делайте выводы.

            Я не хочу преуменьшать уровень наших разработчиков — многие из них действительно (вопреки всему) рвут программистов из других стран, но это всё ещё скорее одиночные случаи, а не потоковое явление. А фразы «наши одни из лучших» — это советский миф, от которого нужно избавляться, чтобы открыто воспринимать и улучшать западные наработки (как в программировании, так и в образовании).
              +2
              >> А фразы «наши одни из лучших» — это советский миф
              Если быть точнее — «советское образование — лучшее в мире»
                –2
                Это специальная уловка такая. Люди должны думать, что у них хоть что-то в этой жизни еще осталось. Вот и… самые лучшие программисты, самые красивые девушки, и вообще Советские_X_—_самые_Y_X_в_мире.
                  0
                    –2
                    Девушки действительно красивые. Точнее больше следят за собой и откровенней\сексуальней одеваются.
                    А вот насчет образования — «лучшего в мире» вузовского не то что не осталось, его не было. То, что сейчас оно хуже, чем раньше, не значит, что раньше оно было лучше всех.
                      0
                      >Точнее больше следят за собой и откровенней\сексуальней одеваются
                      угу. пытаются продать себя подороже а лучше «американ бой уеду с тобой». такие дела
                        0
                        Да ну. Те, что пытаются себя продать именно американ-боям реально стремноватые. Видел одну такую в кафе. Сидела за соседним столиком и в паре с сводницей-переводчиком и что-то рассказывали иностранцу про красный диплом вместе с демонстрацией оного :)

                        Нормально выглядящие либо просто выглядят нормально, либо клеят кого-нибудь из местных обеспеченных индивидуумов.
                –2
                По-моему, никто не понял, что это цитата из «Нашей Раши»
                  +6
                  По-моему, это характеризует хабралюдей с лучшей стороны.
                    0
                    Не спорю.
                    Но и не оправдываюсь =)
                  –2
                  именно, «завидуют»
                  >Его выпускники работают в ведущих компаниях города
                  если бы вместо «города» было бы «мира» то это понятно. А так, работа в питере, в ведущей компании(вконтакте чтоли, пхп писать?) не понятно что «крутого».
                    +2
                    Вообще, «ведущие компании города», если говорить о Питере, это вполне себе «ведущие компании мира». Google, Parallels, EMC, Яндекс, HP, JetBrains, Oracle, для примера.
                  +3
                  Господа питерцы — завидую вам белой завистью.
                    +12
                    В Академическом Университете учится много ребят, приехавших из других городов. Приезжающим предоставляется хорошее общежитие на время учебы. Кстати, недавно на Хабре была заметка от студента 6 курса.
                    –3
                    Преподавателям подобных учебных заведений, хочется пожелать азарта, терпения и любви к своей работе. То насколько оперативно и качественно они постигают новые веяния, влияет на интерес студентов к учёбе.
                    Если бы нам в университете преподавали jQuery в дополнение к javascript, было бы интереснее учиться. А наши программисты, это действительно повод гордиться за нашу страну. Они лучшие, вопреки стараниям чиновников.
                      –2
                      То, что программисты с просторов ex-USSR лучше программистов из некоторых других стран, не повод говорить о том, что они лучшие во всем мире.
                        0
                        _Некоторые_ программисты из стран ex-USSR.
                          0
                          Я имел ввиду средний уровень. Оценка очень грубая, но все же.
                      +2
                      Расскажите о вашей работе с Dan Boneh, и вообще о нем.
                        +2
                        С Dan Boneh я работала три месяца. За это время в познакомилась с рядом статей посвященных FHE и написала на C++ собственно последнюю из предложенных схем (пока все-таки это штука очень медленная).

                        Сам Dan Boneh человек невероятного энтузиазма и трудоспособности, с отличным чувством юмора.
                        0
                        Вычисления на зашифрованных данных? HE штоле? От ето «перевод» :]
                          0
                          Fully Homomorphic Encryption (FHE), а как вы бы перевели?
                            0
                            Как гомоморфное шифрование
                            +1
                            «Гомоморфное Шифрование» — так хотите перевести? =)
                              +1
                              Именно. А лучше вообще никак :]
                                0
                                Я хочу, чтобы люди понимали, о чем я пишу, и им не надо было гуглить для этого термины.
                                Что неправильного в том, чтобы называть это «вычисления на зашифрованных данных», я не понимаю.
                                  0
                                  Ну, я бы не догадался о чем речь идет, если бы не помнил последних интересов Бонеха :)
                            0
                            Круто, вы молодец! Жалко нельзя так круто изменить свою жизнь, чтобы в свои 21 пойти на CS-факультет и изучать то, что нравится :)
                              0
                              Почему же нельзя? 21 как раз, казалось бы, подходящий возвраст (я туда пришла в 21).
                                0
                                Ну у вас за плечами наверное было хорошее мат. образование? Выигранные олимпиады и все такое?
                                  0
                                  Нет, у меня было немного от всего этого. Самое важное — желание и мотивация. Ну и не так сложно попробовать — процедура поступления очень простая и не отнимет много времени.
                                    0
                                    А можно подробнее про процедуру поступления? Какие экзамены, каков порядок?
                                      +1
                                      Думаю здесь можно найти избыточную информацию по Вашему вопросу.
                                      0
                                      Большое спасибо :) Может быть попробую.
                                  0
                                  Мне кажется нас тут от силы половина таких, кто сразу после бакалавриата поступил. Многие старше.
                                    0
                                    Стоп, так раньше никто в приципе и не поступает :) Я в 20, но это потому что школу в 16 окончил.
                                      0
                                      Да дело то не только в возрасте, но и в накопленном ранее багаже знаний.
                                    +1
                                    В 21 все очень даже можно, если вы в 21 поступите на PhD куда-нибудь в США, то обнаружите, что вы один из самых молодых студентов. Так что не все еще потеряно, даже в 25 можно без проблем.
                                    +1
                                    Ожидал в статье услышать критерии отбора студентов при поступлении. Надеюсь, про это будет написано позднее.
                                      0
                                      Я не знаю, какими критериями руководствуется комиссия. А экзамен в моем случае состоял из задач по комбинаторике и теории графов (если я правильно помню) и собеседования.
                                      Здесь более подробная информация о приеме.
                                        +2
                                        Могу сказать точку зрения «со стороны комиссии» про CS-специализацию (у нас есть ещё SE и BI). Мы берём тех, кто способен к научной работе. Определяется это в процессе математического теста (пример есть на сайте, в нём много заданий — это не значит, что обязательно успеть все их решить) и получасового собеседования, на котором мы поговорим и о задачках из теста и других задачках, но главное — о том, чем Вы занимались до того, как придти к нам, и чем интересуетесь. Математический тест на самом деле предназначен для того, чтобы убедиться в Вашей возможности воспринимать математические знания, и способности строго рассуждать.

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

                                        Некоторое время назад на Хабре был официальный пост про приём на все специализации (в блоге «Образование в IT»).
                                        –1
                                        Всё-таки статья больше о теме Вашей диссертации, чем об университете.
                                          0
                                          Вы большой молодец! Завидую белой завистью :-) Жаль, что мои шансы на учебу хорошему CS уже невелики.
                                            –2
                                            Пару комментариев.
                                            магистратура в любом вузе подразумевает наличие достаточно большого количества курсов по выбору.

                                            Сей университет суть отпочковавшееся изделие Политеха и физтеха Иоффе.

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

                                            И Ицыксон на ФТК есть свой:) (возможно что и родственник указанного т.к. на ФКТ — Владимир Михайлович Ицыксон)
                                              +1
                                              А расскажите, пожалуйста, чуть подробнее про специалистов с мировым именем.
                                                0
                                                На вскидку, например, Карпов который про темпоральную логику.
                                                  +2
                                                  Да, с Юрием Глебовичем недавно совсем познакомились. А ещё? Буду также благодарен, если Вы сможете ссылки на страницы учёных дать.
                                                +2
                                                В.М.Ицыксон — брат Д.М.Ицыксона, преподаёт и на ФТК и в АУ. А аналога направления CS в АУ на ФТК, насколько мне известно, нет. Да и если говорить о том, чему ФТК собственно должен учить — SE, то и АУ и, скажем, ФизМех того же Политеха (кафедра Клавдиева) дают — если судить по выпускникам, приходящим на собеседования, значительно лучшее образование.
                                                0
                                                Любопытно, а если поступить на одну специальность, потом можно будет перевестись на другую? Ну, если в ходе обучения поймёшь, что та, другая, тебе ближе?
                                                  0
                                                  Если быстро сообразить это, и если туда подходите, то можно.
                                                  0
                                                  (не туда попал сначала)

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

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