Задача синхронизации

Задача о стрелках (в технике)

     Данная процедура может быть построена на автомате с тремя состояниями S₀, S₁, S.  S₀ - начальное состояние.

     Когда приходит сигнал, то автомат переходит в состояние S₁. Если сигнал приходит, когда автомат в состоянии S₁, и рядом с ним находятся соседи в состоянии S₁, то он переходит в состояние S.

     Бывают синхронные и асинхронные автоматы. В асинхронных не требуется одновременного прихода сигнала.

     Правила работы асинхронного автомата для решения этой задачи
1)  S_i^t = 0 AND S_j^t = 0 --> S_i^t+1 = 0; S_j^t+1 = 0
2)  V=1 S^t=0 --> S_i^t+1=1;
3)  S_i^t<>0 OR S_j^t<>0  -->  S_i^t+1 = min (S_i^t+1,S_j^t+1)+1; S_i^t+1 = min (S_i^t+1,S_j^t+1)+1;

     Автоматы можно заставить решить задачу (засинхронизироваться) за меньшее время. Для этого требуется увеличить количество состояний автомата.

     Примером самосинхронизирующейся системы является лазер, рассинхронизирующейся - транспортный поток.

     Наиболее остро проблема синхронизации стоит в системах ПВО и разработке чипов.

Задача вычисления

     Умножение двоичных чисел состоит из двух операции - сдвига и сложения. Автомат, каждая клетка которого может иметь 27 состояний за 15 тактов перемножает два четырехзначных числа. n - количество разрядов. 3*(2n+1) - количество состоянии. (8n +2) - количество тактов. Подробнее

     НП-полные задачи требуют перебора всех данных (всё со всем надо сравнивать). Сложность этих задач растет экспоненциально в зависимости от количества элементов. Но на макаронных машинах решаются моментально - решение определяется линейно. Подробнее

Игра "Жизнь" (Конвей)

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

Иллюстрации...

Свойства планера:

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

Возможные вариации

     Таким образом, автомат описывается как четверка параметров - (D, R, S, M). (1D, 1R, 2S, 1M) - самый простой, игра происходит на линии. (2D, 1R, 2S, 1M) реализует "Жизнь" Конвея. Были найдены автоматы, которые могут использоваться в криптографии, в процессе восстановления разрушенных изображении, в геоинформационных системах. Также успешно их используют для генерации изображения и музыки (3D, 2R, 256S, 3M); моделирования процессов в химии, биологии, экономике. Подробнее

Эволюционное программирование (генетические алгоритмы)

     Примеры

     Проектирование волнореза в Новороссийске. Требовалось сконструировать волнорез. Обычными средствами это сделать продолжительное время не удавалось. Тогда было использовано эволюционное программирование. В качестве генома использовались геометрические параметры волнореза. Была создана модель окружающей среды, на которой отрабатывались возникающие вариации.

     Генерирование реалистичных изображений. Описание можно посмотреть в статьях:
"Компьютер моделирует эволюцию растений",
"Программы, моделирующие эволюцию биологических видов палеозоя и эволюцию английских   фамилий",
"Программирование и искусство."

     Компоновка ракеты по обтекаемости. Есть три компоненты. Требуется сложить их вместе для получения максимального объема и максимальной обтекаемостью. С помощью эволюционного программирования был получен следующий результат.

     Геометрическое моделирование.

     Набирая комбинации элементарных функций D1-D8, можно спроектировать множество различных геометрических областей. Например, ФОРМУЛА для картинки сложной области может иметь вид: D1*(1-D2)+D3*D4*D7+D8*D6*D4*(1-D5) или подобный этому. Вариации могут подвергнуться в формуле знаки, скобки, индексы. Будут получаться все новые фигуры.

     Требуется очень тщательно прорабатывать параметры генома. Он должен иметь как можно более общий вид. Варьировать параметры нужно непрерывней.

     На данной идее развился метод, получивший название "Искусственная жизнь" Artificial life.

     Artificial life - обобщенный метод построения динамических моделей, базирующихся на совокупности генетических алгоритмов, теории хаоса, системной динамики.
Черты метода:
-адаптация решения к условиям внешнего мира,
-передача черт по наследству,
-мутации,
-имитация выживаемости.

     Понятия метода.
Хромосома - вектор варьируемых параметров решения
Операции - получение новых решений из существующих
Скрещивание - получение параметров хромосомы от родителей, расширение области поиска
Мутация - случайное изменение параметров при копировании
Реакция мира - уничтожение процента худших особей (по критерию среды), сужение области поиска

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