Бывают ситуации, когда существование объекта с какими-то свойствами доказать легко, но это доказательство неконструктивно (не даёт возможности предъявить такой объект). Например, можно установить, что число всех объектов определённого вида, не обладающих нужным свойством, меньше числа всех объектов этого вида. Это можно переформулировать в терминах вероятности, а также в терминах сложности описания (плохие объекты можно коротко описать, поэтому их мало). Мы рассмотрим простые примеры такого рода, а также более сложную вероятностную технику, называемую "леммой Ловаса", а также вероятностный алгоритм построения объектов, придуманный Мозером и модифицированный Тардошем, и его следствия (слова без запрещённых подслов и другие применения).
Задачи Вопросы по рассказанному и решения этих задач можно посылать по адресу sasha.shen@gmail.com — информацию о решённых задачах я перешлю в computer science center. (Предупреждение: несколько последних задач я решать не умею и потому особенно заинтересован в их решениях.)
Ссылки
Date and time | Class|Name | Venue|short | Materials |
---|---|---|---|
28 February 17:20–18:55 |
Вероятностный метод: средние, Lecture | ПОМИ РАН | video |
28 February 19:15–20:50 |
Вероятностный метод: оценка суммы, Lecture | ПОМИ РАН | video |
01 March 11:15–12:50 |
Вероятностные оценки: метод сжатия, Lecture | ПОМИ РАН | video |
01 March 13:00–14:35 |
Ещё о вероятностных доказательствах, Lecture | ПОМИ РАН | video |
01 March 15:35–17:10 |
Дерандомизация, Lecture | ПОМИ РАН | video |
07 March 17:20–18:55 |
Лемма Ловаса: формулировка, Lecture | ПОМИ РАН | video |
07 March 19:15–20:50 |
Доказательство леммы Ловаса, Lecture | ПОМИ РАН | video |
08 March 11:15–12:50 |
Применения леммы Ловаса, ещё о запрещённых подсловах, выполнимость n-кнф с 2n−3 соседей у каждого клоза, Lecture | ПОМИ РАН | video |
08 March 13:00–14:35 |
Общий алгоритм Мозера-Тардоша и его оценка, Lecture | ПОМИ РАН | video |
08 March 15:35–17:10 |
Вероятностные алгоритмы для бесконечных задач, машины с переписыванием ответа, Lecture | ПОМИ РАН | video |