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

Материал из TDS

Версия 07:52, 13 октября 2014

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

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

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

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

Задания

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

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

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

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

1.4. Гладкий поток на торе.
Построить визуальную модель гладкого потока на двумерном торе. Нужно: а) отразить совместную динамику нескольких (1 или 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. Модель символической системы "айсберг" в размерности 2.
Построить визуальную модель системы "айсберг", отображая процесс кодирования с переходами между уровнями детализации 1 --> 2, 2 --> 1, 1 --> 3, как в презентации Complexity of iceberg systems.

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

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

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

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

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

1.15.* Топологические свойства многомерных фракталов Рози.
Поставить эксперимент, который подтвердит или опровергнет гипотезу о связности данного фрактала (см. Обобщённый_фрактал_Рози_-_3D-модель).

1.16. Дерево Пифагора и его динамические свойства.
Изобразить фрактальное дерево с конечным набором линейных правил, рёбра которого подвержены случайному возмущению. исследовать зависимость Хаусдорфовой размерности границы дерева от величины случайного возмущения.

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

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

2.2. Меры максимальной энтропии прямоугольных тайлингов.
Известно, что тайлинг плоскости фигурами "домино" {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, могут объединить усилия и использовать общую визуальную основу и динамическую модель. Задачи могут быть также решены совместно двумя студентами в форме единой модели.

2.10.* Модель Изинга.
Наглядно визуализировать динамику и/или структуру инвариантных мер для классической модели Изинга.

2.11.* Задача многих тел на сфере.
Построить динамическую модель движения большого числа точек одинаковой массы на двумерной сфере под действием гравитационного поля, создаваемого другими частицами. Особо необходимо уделить внимание вычислительной эффективности, так как число точек должно быть весьма большим: n >> 10000. Экспериментально исследовать динамически устойчивые состояния, спектральные характеристики, энтропию. Вместо сферы можно рассмотреть двумерный тор, либо исследовать оба случая. (О происхождении задачи см., например, Wikipedia).

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

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

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

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

Задания (см. также 2012) и Работы 2012 - 2013

• Курс Динамические системы на факультете ФИВТ