Студентам

Курсы лекций

Коды с исправлением ошибок

ЕНС на иностранном языке для шестого курса мехмата МГУ.

Коммуникационная сложность.

Спецкурс по выбору кафедры математической логики и теории алгоритмов.

Курсы прошлых лет

Области научных интересов (в порядке значимости)

Колмогоровская сложность и её применения

Колмогоровскую сложность слова в данном алфавите можно определить как длину в битах кратчайшей программы, печатающей это слово. Интуитивно, сложность x равна количеству информации в x. Например, сложность достаточно длинной последовательности из одних нулей примерно равна сложности двоичной записи ее длины. А сложность "случайной" последовательности примерно равна ее длине. Последнюю фразу можно принять за определение случайной последовательности и на этом основании строить теорию вероятностей как науку о свойствах случайных последовательностей. Например, закон больших чисел будет сформулирован так: в любой случайной последовательности доля единиц примерно равна 1/2. (В обычной формулировке, закон больших числе говорит, что в большинстве последовательностей доля единиц примерно равна 1/2.) На том же основании можно построить и математическую статистику. О применении колмогоровской сложности в математической статистике можно прочитать здесь. Большинство задач о колмогоровской сложности могут быть переведены на комбинаторный язык, благодаря чему формулировка становится простой, и задача становится понятной и интересной даже младшекурсникам. Вот примеры таких (нерешенных) задач: задача о кошках и муравьях, задача о разделении ресурсов в иерархической структуре, задача об он-лайн паросочетаниях, задача об избегании окрашенных мест. Другие задачи этого типа можно найти этом обзоре.

Коммуникационная сложность

Сложность вычислений

Существование компьютерной программы вычисления функции f(x) еще не означает возможности ее вычисления на практике. Например, алгоритм распознавания простоты натурального числа x, имеющего n десятичных знаков, с помощью решета Эратосфена требует перебора 10^{n/2} возможных делителей $x$. Предположим, что этот алгоритм выполняется на компьютере с тактовой частотой 10^{15} Гц (частота атомных переходов). Тогда, для проверки простоты 44-значного числа потребуется никак не меньше 10^7 секунд, что примерно равно 7 годам! Поэтому важно не просто найти программу вычисления данной функции, но найти такую программу, которая работает достаточно быстро. В теории сложности вычислений как раз и разрабатываются методы, позволяющие это сделать. С другой стороны люди научились использовать и функции, для которых не существует быстрой программы вычисления. А именно, их можно использовать в криптографии для построении надежных шифров, электронных подписей и пр.

Самоподобные замощения плоскости