Верещагин: материалы студентам
Курсы лекций в весеннем семестре 2020 года
- Сложность вычислений. Спецкурс по выбору кафедры математической логики и теории алгоритмов.
Программы и конспекты курсов прошлых лет выложены здесь.
Задачи для студентов, желающих пойти на кафедру (список не полный)
1. Доказать (или опровергнуть), что в любом двудольном графе, содержащем m рёбер, найдется регулярный подграф с не менее, чем m^{0.9} рёбрами. Пояснение: двудольный граф — это граф, вершины которого разделены на две доли L,R, левую и правую, причем рёбра соединяют только вершины разных долей; подграф — это произвольное множество рёбер исходного графа, регулярный подграф — это такой подграф, что все левые концы его ребер имеют одну и ту же степень в подграфе, и то же самое верно для всех правых концов, но степени левых концов могут быть не равны степени правых концов.
2. Придумать укладку двоичного дерева высоты h на плоскости в круге диаметра O(sqrt(2^h)). Пояснение: вершины дерева нужно изображать кружками радиуса, скажем 2, а рёбра — отрезками прямых толщины 1 и длины не менее, скажем, 10. Различные рёбра не должны пересекаться.
3. задача о кошках и муравьях,
4. задача о разделении ресурсов в иерархической структуре,
5. задача об он-лайн паросочетаниях,
Области научных интересов (в порядке значимости)
Колмогоровская сложность и её применения
Колмогоровскую сложность слова в данном алфавите можно определить как длину в битах кратчайшей программы, печатающей это слово. Интуитивно, сложность x равна количеству информации в x. Например, сложность достаточно длинной последовательности из одних нулей примерно равна сложности двоичной записи ее длины. А сложность «случайной» последовательности примерно равна ее длине. Последнюю фразу можно принять за определение случайной последовательности и на этом основании строить теорию вероятностей как науку о свойствах случайных последовательностей. Например, закон больших чисел будет сформулирован так: в любой случайной последовательности доля единиц примерно равна 1/2. (В обычной формулировке, закон больших числе говорит, что в большинстве последовательностей доля единиц примерно равна 1/2.) На том же основании можно построить и математическую статистику. О применении колмогоровской сложности в математической статистике можно прочитать здесь. Большинство задач о колмогоровской сложности могут быть переведены на комбинаторный язык, благодаря чему формулировка становится простой, и задача становится понятной и интересной даже младшекурсникам. Вот примеры таких (нерешенных) задач: задача о кошках и муравьях, задача о разделении ресурсов в иерархической структуре, задача об он-лайн паросочетаниях, задача об избегании окрашенных мест. Другие задачи этого типа можно найти этом обзоре.
Коммуникационная сложность
Сложность вычислений
Существование компьютерной программы вычисления функции f(x) еще не означает возможности ее вычисления на практике. Например, алгоритм распознавания простоты натурального числа x, имеющего n десятичных знаков, с помощью решета Эратосфена требует перебора 10^{n/2} возможных делителей $x$. Предположим, что этот алгоритм выполняется на компьютере с тактовой частотой 10^{15} Гц (частота атомных переходов). Тогда, для проверки простоты 50-значного числа потребуется никак не меньше 10^10 секунд, что примерно равно 317 годам! Поэтому важно не просто найти программу вычисления данной функции, но найти такую программу, которая работает достаточно быстро. В теории сложности вычислений как раз и разрабатываются методы, позволяющие это сделать. С другой стороны люди научились использовать и функции, для которых не существует быстрой программы вычисления. А именно, их можно использовать в криптографии для построении надежных шифров, электронных подписей и пр.