Курсовые работы для студентов

Конкретные задачи для курсовых работы

Области научных интересов

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

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

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

Имеется некоторая функция f(x,y), значение которой должны вычислить совместно Алиса и Боб. При этом первый аргумент x есть только у Алисы, а второй — только у Боба. Функция f известна и Алисе, и Бобу и до получения ее аргументов они договариваются об алгоритме общения, для которого количество переданных друг другу бит минимально. Это минимально возможное количество бит и называется коммуникационной сложностью функции f. Примером задачи о коммуникационной сложности является пятая задача из списка задач.

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

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

Непериодические замощения плоскости многоугольниками

Пусть имеется конечный набор многоугольников и некоторые локальные правила их соединения. Рассмотрим замощения плоскости этими многоугольниками (при замощении мы можем применять к исходным многоугольникам любые изометрии), удовлетворяющие этим локальным правилам. Исходный набор называется апериодическим, если такие замощения существуют, и при этом все они непериодические. Известным примером апериодического набора является набор Пеноруза из двух ромбов, см. Википедию.