ФИВТ:ДС:Лабораторные задания:2013

Материал из TDS

Версия 12:39, 25 сентября 2013

Для того, чтобы взять задание нужно направить e-mail лектору с номером задания. В случае возникновения конкуренции получает задачу тот, кто раньше направил письмо. При нехватке заданий, например, если остались только сложные задания, мы дополняем список заданиями соответствующего уровня сложности.

Лабораторные работы следует сдать до 20 декабря.

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

Внимание! В списке приводятся лишь формулировки заданий. Подробное описание и литературу предоставят преподаватели. Большинство задач опирается на опубликованные исследовательские статьи, а некоторые решены в простейших случаях. Эти упрощённые модели могут служить образцами. Мы предоставим всю сопутствующую информацию по каждой из задач.

Задания

Визуальные модели динамических систем

1.1. [Захаров, 096] Кодирование преобразования перекладывания отрезков.
Построить визуальную модель, отражающую процесс кодирования и диаграммы кодов для преобразований перекладывания 2 и 3 отрезков (в случае двух отрезков система изоморфна повороту окружности). Необходимо особо учесть случай рациональных длин отрезков.

1.2. Кодирование гиперболического автоморфизма Аносова.
Построить визуальную модель для марковского кодирования гиперболического автоморфизма A двумерного тора с матрицей {{2,1},{1,1}}. Модель должна: а) иллюстрировать построение стандартных прямоугольников, задающих базовое разбиение П фазового пространства; б) иллюстрировать замощение плоскости сдвигами стандартных прямоугольников; в) иллюстрировать одну итерацию разбиения AП (как оно пересекается с П).

1.3. [Павленко, 097] Гомоклинические точки гиперболического автоморфизма.
Построить визуальную модель, которая отображает кодирование гомоклинических точек последовательностями Фибоначчи.

1.4. [Блинцов, 097] Гладкий поток на торе.
Построить визуальную модель гладкого потока на двумерном торе. Нужно: а) отразить совместную динамику нескольких (1 или 2) точек; 2) проиллюстрировать перемешивающие свойства, а именно, показать, как движется множество, шар или квадрат, под действием потока.

1.5. Динамика оператора случайного блуждания на группе L₂ в проекции на граф Шрейера
Граф Г изоморфен графу De Bruijn'a. Вершины графа интерпретируются как элементы поля Галуа F_2ⁿ, а рёбра отвечают преобразованиям b : x --> mx, s : x --> x+1. Отобразить собственные функции оператора случайного блуждания.

1.6. [?] Клеточный автомат на графе Шрейера L₂
Визуализировать клеточный автомат на графе Г задачи 1.5 с различными правилами взаимодействия.

Студенты, решающие задачи 1.5 и 1.6, могут объединить усилия и сделать модель на унифицированной основе.

1.7. Автоморфизм Паскаля.
Визуализировать системы базовых блоков (кодов) и конструкцию cutting-and-stacking для автоморфизма Паскаля.

1.8. Специальный поток над перекладыванием.
Построить визуальную модель специального потока Кочергина над перекадыванием отрезков с логарифмическими особенностями (достаточно для 2, 3 и 4 отрезков). Нужно: а) отразить совместную динамику нескольких (1 или 2) точек; 2) проиллюстрировать перемешивающие свойства.

1.9. Специальный поток над поворотом окружности с кусочно линейной "крышей".
Проиллюстрировать перемешивающие свойства указанного потока с возможностью варьировать параметры системы и наблюдать изменения в динамическом поведении.

1.10. Модель символической системы "айсберг" в размерности 2.
Построить визуальную модель системы "айсберг", отображая процесс кодирования с переходами между уровнями детализации 1 --> 2, 2 --> 1, 1 --> 3, как в презентации Complexity of iceberg systems.

1.11. Граф De Bruijn'a и аттракторы.
Построить модель графа De Bruijn'a, демонстрирующую его гиперболическое поведение.

1.12. [Зиятдинов, 096] Графы и динамика на полях Галуа F_3ⁿ.
Придумать способ визуализации графов De Bruijn'a / spider graph'ов для p = 3 и нескольких младших n.

1.13. Диофантовы свойства потоков на торе.
Изобразить распределение участка траектории потока на торе и увидеть зависимость от диофантовых свойств вектора - направления движения.

1.14. Квазикристалл Фибоначчи.
Построить модель квазикристалла Фибоначчи и аппроксимировать соответствующее ему спектральное распределение.

1.15. Экзотические квазикристаллы: арифметические и динамические свойства.
Провести собственное исследование публикаций и построить две визуальных модели экзотических (малоизвестных, либо обнаруженных недавно) квазикристаллов (исключая предмет задачи 1.14).

1.16. Динамика экспоненциального отображения.
Построить бифуркационную диаграмму семейства экспоненциальных отображений f(z) = exp(z) + c (см. Exponential map и External ray).

Задачи на исследование динамических свойств

2.1. [Булатов, 097?] Тайлинги Робинсона.
Визуализировать и исследовать эргодические свойства тайлингов Робинсона (см. Aperiodic tiling).

2.2. [Волков, 096] Меры максимальной энтропии прямоугольных тайлингов.
Известно, что тайлинг плоскости фигурами "домино" {2 x 1, 1 x 2} имеет единственную стационарную меру максимальной энтропии, которая асимптотически соответствует равномерному распределению на всех замощениях квадрата 2N x 2N. Придумать алгоритм построения стационарных случайных замощений плоскости заданным набором прямоугольников и вычислить экспериментально энтропию полученной системы (рассматриваем некоторый набор простых комбинаций фигур).

2.3. Символическая сложность подстановочных систем.
Вычислить, экспериментально или, используя известный результат, и визуализировать сложность нескольких классических подстановок: система Фибоначчи, система Морса, система Рози...

2.4. Символическая сложность систем ранга 1.
Построить модель, демонстрирующую эффект комбинированного поведения функции сложности символической последовательности, основанную на конструкции системы ранга 1. Вычислить функцию сложности до некоторого l = h_n и отобразить её график относительно: а) шкалы, в которой h_n растут линейно и функция сложности растёт квадратично; б) максимальной шкалы, в которой l растет линейно, а функция сложности дана в логарифмической шкале.

2.5. Спектральные меры автоморфизма Паскаля.
Вычислить и построить графическую модель спектрального распределения автоморфизма Паскаля, отвечающего стандартному кодированию символами {a,b}.

Студенты, решающие задачи 1.7 и 2.5, могут объединить усилия и использовать общий алгоритм построения базовых блоков, либо использовать генератор кодов, созданный авторами задачи 3.3.

2.6. Спектральные меры Салема.
Вычислить и визуализировать спектральные мера Салема на квадрате для системы "айсберг" в случае действия Z².

2.7. Инвариантные меры и мультипликативная эргодическая теорема.
Исследовать инвариантные распределения m на P¹, порождённые случайным произведением матриц. Изучить хаусдорфову размерность меры m и другие динамические свойства системы.

2.8.* Динамика систем частиц с агрегированием.
Построить динамическую визуальную модель систем движущихся частиц в жидкости с агрегированием. Частицы помещены в прямоугольную среду (жидкость), обладают скоростью прямолинейного движения, а также дополнительно совершают локальное броуновское движение и подвержены агрегированию (слипанию). Считать, что агрегаты могу разрушаться, а частицы как покидают среду (свободно через границу), так и поступают через границу. Исследовать эргодические свойства стационарных режимов: энтропия, перемешивание, хасдорфова размерность агрегатов.

2.9.* Динамика систем частиц с агрегированием (нестационарный случай).
В условиях задачи 2.8 иссделовать только рост агрегатов, визуализировать и изучить их геометрические свойства. Модель без разрушения агрегатов. Допустить, что в модели могут участвовать 2 или 3 сорта частиц.

Студенты, решающие задачи 2.8 и 2.9, могут объединить усилия и использовать общую визуальную основу и динамическую модель. Задачи могут быть также решены совместно двумя студентами в форме единой модели.

Задачи, связанные с численными экспериментами

Распределённые вычисления

Следующие задачи по умолчанию предполагают создание системы распределённых вычислений, так как требуемый объём вычислений заранее неизвестен.

3.1.* Оценка сумм Вейля.
Литература:

• A. Fedotov, F. Klopp, An exact renormalization formula for Gaussian exponential sums and applications

3.2.* Поиск конструктивных примеров плоских полиномов Литлвуда, соответствующих квантовым солитонам с мультипликативной симметрией спектра
Литература:

• А. Приходько. О семействах плоских полиномов Литлвуда с унимодулярными коэффициентами

3.3.* Перемешивающие свойства автоморфизма Паскаля
Литература:

• X. Mela, K. Petersen. Dynamical properties of the Pascal adic transformation

Библиотека визуальных моделей

4.1. [Романов, 097] Вариант на английском языке
Оформить описания лабораторных работ 2012 и 2013 гг. на английском языке.

Задания и Работы 2012/13 учебного года