https://www.wikicshse.ru/index.php?action=history&feed=atom&title=%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82_%D0%BF%D0%BE_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B9_%D0%B8%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B5_2018Проект по теоретической информатике 2018 - История изменений2026-06-06T18:17:24ZИстория изменений этой страницы в викиMediaWiki 1.45.3https://www.wikicshse.ru/index.php?title=%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82_%D0%BF%D0%BE_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B9_%D0%B8%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B5_2018&diff=1956&oldid=previmported>Nichichileva: Migrated current public revision from wiki.cs.hse.ru2018-10-22T16:21:09Z<p>Migrated current public revision from wiki.cs.hse.ru</p>
<p><b>Новая страница</b></p><div>{{Карточка_проекта<br />
|name=Проект по теоретической информатике<br />
|mentor=Подольский Владимир Владимирович<br />
|mentor_login={{URLENCODE:Nichichileva|WIKI}}<br />
|semester=Осень 2018<br />
|course=2<br />
|summer=<br />
|number_of_students=30<br />
|categorize=yes<br />
}}<br />
<br />
== Что за проект? ==<br />
<br />
Проект по теоретической информатике является научным исследованием в области теоретического Computer Science. Проект предназначен для тех, кто всерьез рассматривает для себя возможность заниматься в будущем теоретическими исследованиями.<br />
<br />
== Правила отбора ==<br />
<br />
Отбор на проект по теоретической информатике производится по результатам собеседования. На собеседовании проверяется владение студентом знаниями и навыками, достаточными для успешной работы по выбранной теме, а также мотивация студента. В частности, в рамках описания мотивации от студента ожидаются примеры того, что он уже делал ранее, подтверждающие его интерес к теоретическим исследованиям (это может быть посещение факультатива, прохождение соответствующей летней практики, самостоятельное изучение какой-то области и т.д.).<br />
<br />
== Критерии оценивания ==<br />
<br />
Критериями для выставления оценки по данному проекту является глубина освоения материала, уровень полученных новых результатов, качество изложения работы. <br />
<br />
== Контакты == <br />
<br />
Владимир Подольский<br />
<br />
vpodolskii@hse.ru<br />
<br />
== Возможные темы проекта ==<br />
<br />
Ниже приведен список возможных тем проекта. Если у Вас есть свои пожелания, возможен вариант договориться с конкретным ментором о другой теме.<br />
<br />
<br />
'''Тема проекта: Формулы для функций Шпрага-Гранди.'''<br />
<br />
Ментор: [https://www.hse.ru/org/persons/176125335 Владимир Александрович Гурвич]<br />
<br />
<br />
Будет рассматриваться широкий класс комбинаторных симметричных (impartial) игр. Цель — получить явные формулы для функций Шпрага-Гранди в нормальной и мизерной версиях и выявить связь между этими версиями. Это возможно далеко не всегда. Хотелось бы найти такие формулы для широкого класса игр. <br />
<br />
<br />
Литература <br />
<br />
1. Winning Ways for your mathematical plays, volume 1; <br />
Elwyn Berlekamp, John H. Conway, and Richard Guy, <br />
https://annarchive.com/files/Winning%20Ways%20for%20Your%20Mathematical%20Plays%20V1.pdf<br />
<br />
2. On the misere version of game Euclid and miserable games;<br />
Discrete Math. 307:9-10 (2007) 1199-1204;<br />
Vladimir Gurvich.<br />
<br />
<br />
Примечания: <br />
Проект не требует от студента существенных предварительных знаний (всё необходимое будет объяснено). Однако, проект потребует существенных затрат времени. Необходим также хороший программистский уровень: умение поставить эффективный вычислительный эксперимент (алгоритмы будут подробно объяснены). Опыт показывает, что формулы для функций Шпрага-Гранди могут быть довольно сложными и, чтобы угадать такую формулу, потребуется вычислить значение функции для большого числа позиций. В октябре 2018 и 20 января - 12 мая 2019 связь по скайпу. <br />
<br />
<br />
'''Тема проекта: Чувствительность булевых функций'''<br />
<br />
Ментор: [https://www.hse.ru/org/persons/14007605 Михаил Николаевич Вялый]<br />
<br />
Одной из важных характеристик в анализе булевых функций является чувствительность. На самом деле существует два варианта определения чувствительности и взаимосвязь между ними до конца не прояснена. Так называемая гипотеза чувствительности (sensitivity conjecture) формулируется очень просто и остается недоказанной уже много лет. За это время выяснилось, что эта гипотеза имеет много равносильных (или более сильных) формулировок. В проекте предлагается разобраться с этими достижениями.<br />
<br />
Литература<br />
https://theoryofcomputing.org/articles/gs004/gs004.pdf (хороший, хотя уже несколько устаревший, обзор по вариантам гипотезы чувствительности) <br />
https://arxiv.org/abs/1207.1824 (продолжение одной из тем обзора об одном из самых интересных вариантов гипотезы чувствительности)<br />
С гипотезой чувствительности связана интересная игра, про которую пока известно очень немного (поэтому есть основательная надежда получить какие-то новые результаты даже не очень сложными рассуждениями). Несколько ссылок<br />
https://iuuk.mff.cuni.cz/~koucky/LBCAD/papers/sensitivity%20game.pdf (формулировка игры и связь с гипотезой чувствительности)<br />
(верхние оценки для GKS игры)<br />
https://arxiv.org/abs/1506.06456<br />
https://arxiv.org/abs/1712.01149<br />
<br />
<br />
'''Тема проекта: Исправление ошибок в коммуникационных протоколах.'''<br />
<br />
Ментор: [https://www.hse.ru/org/persons/176000058 Александр Николаевич Козачинский]<br />
<br />
<br />
Предположим A, B --- подмножества множества из n элементов такие, что |A| + |B| > n. Тогда A и B пересекаются. Пусть Алиса получает на вход A, а Боб --- B. <br />
Они хотят найти какой-нибудь элемент пересечения. Нетрудно понять, как им передать друг другу не более O(\log^2 n) битов, чтобы с этим справиться. А что если какая-то доля посылаемых битов может приходить с ошибкой? Достаточно ли и в этом случае O(\log^2 n) битов? Из общей теоремы Бравермана и Рао (применимую не только к этой задаче, а и к любой другой) вытекает, что если доля ошибок меньше 1/8, то ответ положительный. А если доля ошибок, скажем, 1/6, будет ли ответ положительным хотя бы только для этого (или для какого-нибудь другого интересного) частного случая?<br />
<br />
<br />
Литература:<br />
Теорема Бравермана-Рао:<br />
Braverman M., Rao A. Toward coding for maximum errors in interactive communication. // IEEE Transactions on Information Theory, 2014.<br />
<br />
Более старый, более слабый и более простой результат Шульмана:<br />
Leonard J. Schulman. Coding for interactive communication. IEEE Transactions on Information Theory, 1996<br />
<br />
Полиномиальный алгоритм исправления ошибок в коммуникационных протокола:<br />
Zvika Brakerski and Yael Tauman Kalai. Efficient interactive coding against adversarial noise. In FOCS, pages 160–166, 2012<br />
<br />
<br />
'''Тема проекта: Вычисление булевых функций многочленами.'''<br />
<br />
Ментор: [https://www.hse.ru/org/persons/134220270 Владимир Владимирович Подольский]<br />
<br />
Вычисление булевых функций многочленами рассматривается в области сложности вычислений в связи с тем, что эта модель помогает доказывать нижние оценки для ряда других вычислительных моделей, например, для булевых схем и разрешающих деревьев. Есть несколько разных моделей вычисления функций многочленами, например, точные и приближенные вычисления над действительными числами, вычисления по модулю, пороговые функции. Предлагается изучить некоторые из этих моделей и взаимосвязи между ними. Чтобы больше узнать об этой области можно посмотреть обзор by Richard Beigel http://knight.cis.temple.edu/~beigel/papers/polynomial-survey-structures.html<br />
<br />
<br />
'''Тема проекта: Пороговые функции и пороговые схемы.'''<br />
<br />
Ментор: [https://www.hse.ru/org/persons/134220270 Владимир Владимирович Подольский]<br />
<br />
Пороговые функции – это булевы функции, определяемые следующим образом. Пусть дан целочисленный многочлен (часто линейный) от n переменных. Подставим вместо его переменных входы булевой функции и вычислим его значение над целыми числами. Если результат больше нуля, то выход функции полагаем равным 1, иначе полагаем функцию равной 0. Пороговые функции и булевы схемы, составленные из пороговых функций, являются важными моделями в теоретической информатике. Немного больше об этом можно узнать в обзоре by Richard Beigel http://knight.cis.temple.edu/~beigel/papers/polynomial-survey-structures.html<br />
<br />
<br />
'''Тема проекта: Сложность булевых схем.'''<br />
<br />
Ментор: [https://www.hse.ru/org/persons/134220270 Владимир Владимирович Подольский]<br />
<br />
Булевы схемы – одна из основных вычислительных моделей в теории сложности вычислений. Основной интерес к ней связан с доказательством нижних оценок сложности вычислений. Это большая тема и в ней можно либо изучить основы, либо подробно разобраться в каком-то конкретном направлении. Из доступных в Интернете источников в этой области можно посмотреть книгу by Ingo Wegener http://eccc.hpi-web.de/resources/pdf/cobf.pdf. Также на эту тему есть свежая книга “Boolean Function Complexity”, Stasys Jukna.<br />
<br />
<br />
'''Тема проекта: Коммуникационная сложность и ее приложения.'''<br />
<br />
Ментор: [https://www.hse.ru/org/persons/134220270 Владимир Владимирович Подольский]<br />
<br />
Типичная задача коммуникационной сложности выглядит так. Есть два человека, которые хотят вычислить функцию f(x,y) на какой-то паре входов (x,y). При этом первый знает только x, а второй только y, то есть чтобы вычислить функцию им нужно обмениваться информацией. Какое минимальное количество информации им нужно передать друг другу, чтобы вычислить функцию? Например, x и y могут быть файлами, и участники вычисления хотят узнать, совпадают ли эти файлы. Коммуникационная сложность оказывается очень полезной при доказательстве нижних оценок сложности вычислений в множестве вычислительных моделей. Подробнее об этом можно почитать в обзоре by Eyal Kushilevitz http://www.cs.technion.ac.il/~eyalk/cc-survey.ps.Z</div>imported>Nichichileva