Ученики будут исследовать систему, представляющую собой двумерную прямоугольную сетку размера 𝑁×𝑁. Каждая клетка сетки моет быть в открытом с вероятностью 0<𝑝<1 или закрытом состоянии (с вероятностью 1−𝑝). Условие протекания возникает в случае существования непрерывного пути от нижнего края к верхнему только по открытым клеткам.

Эта система может быть моделью таяния льда или старения диэлектрика.

Интересным свойством такой системы является существование «фазового перехода»: для некоторых 𝑝∗ и 𝛿, 𝛿≪𝑝∗, при 𝑝>𝑝∗+𝛿 вероятность протекания близка к единице, а при 𝑝<𝑝∗−𝛿 близка к нулю. Значение порога 𝑝∗ можно определить только с помощью численного эксперимента. Теоретически показано только существование порога.

Ученик освоит методы планирования и проведения численного эксперимента, работу с генераторами псевдослучайных чисел, изучит структуры данных и алгоритмы (структура данных union-find), позволяющие эффективно моделировать предложенную систему. Результатом работы будет выяснение свойств системы:

• доказательство существования порога (оценка значений параметров 𝑝∗ и 𝛿)

• исследование зависимости значения порога от размера задачи 𝑁

Куратор проекта: Воробьев Виталий Сергеевич

Вам предлагается реализовать ascii или графическую версию игры «Гекс». Программа должна позволять играть двум игрокам и определять условие победы.

Гексагональная доска будет описана с помощью структуры данных граф. Условие выигрыша будет определяться с помощью алгоритма поиска в глубину.

Ключевой частью проекта является алгоритм выбора хода (искусственный интеллект, «движок»). Полный перебор ходов невыполним уже для досок небольшого размера. Вам предлагается реализовать алгоритм выбора хода на основе метода Монте-Карло: для каждого возможного хода выполняется 𝑁 случайных доигрываний. Выбирается ход с максимальной долей доигрываний, завершившихся победой. Этот алгоритм относительно прост в реализации и позволяет получить довольно сильный движок, который легко обыграет не слишком опытного игрока.

Вы изучите структуру данных граф, освоите алгоритм поиска в глубину, получите опыт работы с генераторами псевдослучайных чисел, получите представление о численных экспериментах и методе Монте-Карло. В результате выполнения проекта будет создана программа для игры в «Гекс» с возможность игры против компьютера.

Куратор проекта: Воробьев Виталий Сергеевич

Молекулу ДНК можно описать как очень длинную строку, составленную из четырех букв A, C, G, T. Молекула ДНК человека имеет длину около 3.1×109 «букв». Реконструкция последовательности ДНК – сложная задача. Еще не изобрели способа «чтения» ДНК от начала до конца. Вместо этого используют следующую процедуру (мы опускаем здесь множество деталей): с помощью специального прибора получают большое количество 𝑁 фрагментов молекулы ДНК длиной несколько сотен букв 𝑘, так что 𝑁×𝑘≫𝐿, где 𝐿 – длина молекулы ДНК. Относительный порядок фрагментов неизвестен, фрагменты могут частично перекрываться. Затем с помощью алгоритмов, развитых в биоинформатике, реконструируют полный «текст» ДНК.

В этом проекте Вы решите задачу реконструкции строки по большому количеству ее подстрок длины 𝑘. Эта задача решается остроумным способом, с использованием структуры данных граф и метода обхода ребер графа, предложенным Л. Эйлером.

(Наш алгоритм не подойдет для реконструкции генома в реальном эксперименте, например, потому что фрагменты ДНК читаются с ошибками)

Мы применим алгоритм для реконструкции ДНК сенной палочки (Bacillus subtilis), используя более 100000 фрагментов ее ДНК длиной 60 «букв». В качестве побочного результата наш алгоритм решит задачу поиска 𝑘-универсальных циклических бинарных строк.

В результате выполнения проекта Вы изучите структуру данных граф, алгоритм поиска цикла Эйлера в графе, получите представление о некоторых методах, применяемых в биоинформатике.

Куратор проекта: Воробьев Виталий Сергеевич

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

Мы реализуем алгоритм динамического расположения графа на плоскости. Будем считать граф механической системой на плоскости. Ребра графа – это прямые отрезки, соединяющие вершины. Для каждой пары вершин определим силу отталкивания 𝐹⃗rep(|𝑟⃗|), где 𝑟⃗ – вектор, соединяющий эти вершины. Для каждого ребра определим силу притяжения 𝐹⃗att(|𝑟⃗|), которая зависит только от длины ребра. В начальный момент времени расположим вершины случайным образом на плоскости и позволим системе эволюционировать по законам механики. При удачном подборе функций 𝐹⃗rep и 𝐹⃗att этот алгоритм приводит к удачному расположению почти любого графа.

Ваша задача состоит в реализации описанного алгоритма, поиске подходящих функций 𝐹⃗rep и 𝐹⃗att, и демонстрации работы алгоритма для различных графов.

Предложенный алгоритм можно развивать. Например, можно ввести дополнительную силу, которая будет мешать появлению малых углов между ребрами; можно ввести массу вершин и описать механику движения в соответствии со вторым законом Ньютона.

В результате выполнения проекты Вы изучите структуру данных граф, получите опыт моделирования временной эволюции механических систем, получите навык создания динамической визуализации и создадите программу, которая сможет удачно визуализировать различные графы на плоскости.

Куратор проекта: Воробьев Виталий Сергеевич

В этом проекте Вы реализуете мощный алгоритм сжатия данных, в основе которого лежит преобразование Барроуза-Уилера и алгоритм Хаффмана. Алгоритм состоит из трех этапов:

1. Преобразование Барроуза-Уилера

2. Кодирование «move-to-front»

3. Сжатие по Хаффману

Качество сжатия этого алгоритма превосходит качество сжатия распространенной утилиты для сжатия данных gzip и лежит в основе утилиты bzip2 системы Unix.

После реализации алгоритма мы исследуем эффективность сжатия различных типов данных (например: английский текст, последовательность ДНК, случайные данные); сравним скорость работы и качество сжатия нашего алгоритма с другими программами.

В ходе выполнения проекта Вы узнаете о замечательных свойствах преобразования Барроуза-Уилера, хорошо разберетесь с алгоритмом кодирования Хаффмана, изучите структуру данных «суффиксный массив».

В результате выполнения проекта Вы создадите программу для архивирования и распаковки данных.

Куратор проекта: Воробьев Виталий Сергеевич