Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/dubna/2012/notes/Fernique-problems.pdf Дата изменения: Mon Jul 30 23:44:18 2012 Дата индексирования: Mon Feb 4 18:08:31 2013 Кодировка: Windows-1251

Задачи к лекции Ферника
Оранжевые плитки находятся около Х , красные-белые плитки около Х

2

1

и синяя плиткa около КЗ.

Просьба плитки на месте оставить3

Золотая энтропияF Энтропия множества слов ! lim

log xn D где xn число n n подслов длины nF Почему она существуетc Вычислите энтропию мноE жества слов из символов 0 и 1D где 1 никогда не следует за 1F
с символом 0 на nом месте если ( + n) mod 1 [0, 1 - )D 1 иначеF ДокажитеD что у любого слова Штурма ровно n + 1 подслов длины nF Как замостить всю плоскость бесконечным числом таких плитокc
d

Слова ШтурмаF Слово Штурма угла R\Q и выпуска R ! слово

Оранжевые плиткиF Соберите плитки чтобы замостить квадрат 15 Ч 15F Ч? eтный сдвигF Пусть X {0, 1}Z множество dEмерных слов такихD что

размер каждой конечной компоненты связности символа 0 ! ч? eтныйF Является ли ч? eтный сдвиг X софическимc А неч? eтный сдвигc лом таких плитокc

КрасныеEбелые плиткиF Как замостить всю плоскость бесконечным чисE Трудолюбивая машинаF Машина Тьюринга в состоянии q0 D с одними #
на лентеF Переходит ли она когдаEнибудь в состояние читает 0/#
состояние пиш. двиг. в сост. пиш.

c

читает 1
двиг. в сост. пиш.

читает 2
двиг. в сост.

q q q

0 1 2

1 0 1



q q

1 0

2 2 1



q q q

0 1 0

1 1 1



q q q

2 1 2

Синяя плиткF ДокажитеD что такой плиткой нельзя замостить плоскостьF
Какой максимальный радиус кругаD который Вы можете замоститьc Можете ли Вы придумать плиткуD которая замостит больший кругD но не всю плоскость @или только непериодическим способомAc и

ПодпериодичностьF Пусть E R4 ! плоскостьD порожд?нная векторами
(cos(2k /4))0
k 3

(sin(2k /4))0

k 3

.

Найдите все плоскости F такиеD что k (F ) Z3 = k (E ) Z3 D 1 k 4D k ! ортогональная проекция вдоль k ого вектора стандартного базисаF