Алгоритм -> Автомат -> Алгоритм

[Антон (LogRus)]

Кто-нибуть развлекался этой штукой. Тут на днях Программиста старого перечитывал. Статеку о Ханойской башне и конечном автомате очень интересная штука скажу я вам. Только не всё догнал. Чего-то тежело она идет уже 3 раза прочел.

[Serega]

А что не понятно ?

[Антон (LogRus)]

Serega, да иногда буквально всё. Особенно непонятен иногда ход мысли автора преведшей к конечному результату по некоторым вопросам. Жалко тестов нет на скорость работы разных приведённых там решений. Время будет сам протестю. По профилирую чуть.  Думаю сам разберусь что почем. По позже. Сейчас уже ничего не соображаю. Выдохся за день. Так или иначе интересен сам подход примения конечных автоматов в часности как средство раскрытия рекурсии.

[grozny]

конечные автоматы - вокруг нас. Например, OpenGL

[Антон (LogRus)]

grozny, чего так мало. Я больше хочу знать. И ваще поподробней про OpenGl.

[grozny]

дык!

Факт первый: стандарт OpenGL изложен в виде конечного автомата с памятью.
Факт второй: объём полной диаграммы конечного автомата OpenGL - 10 страниц А4 мелким почерком. Краткая схема - на разворот. Полное описание всех состояний и переходов - полтыщи страниц.

Ну теория-то конечных автоматов проста, как топор - есть состояния и есть переходы между состояниями. Система, которую можно описать конечным набором состояний и переходов между ними, называется конечным автоматом (finite automaton). Есть пара теорем относительно связи конечного автомата с машиной фон Неймана и машиной Тьюринга. Вот в этом месте я могу совсем наврать, но кажись конечный автомат - есть подмножество машины Тьюринга и однозначно представим на машине фон Неймана (с условием достаточности памяти для представления состояний и диаграммы переходов). Короче, гарантировано, что если система описана конечным автоматом, то существует программа, которая его реализует и эта программа будет работать корректно, если хватит памяти для хранения мгновенного состояния и полной диаграммы переходов в любой момент времени.

Ессно есть и бесконечный автомат, да кому он нужен .

Ну определения я даю сермяжные, не по книжке, а чё в голове.

[RXL]

Простейший примерчик: три стабильных состояния и переход между ними по некому событию-условию. В каждом состоянии может быть свой набор условий.

Код:

static int state=0;

void step)int a,int b: |
  switch)state: |
    case 0{
      if)a>b: | /* некая полезная работа... */ state=1; "
      break;
    case 1{
      if)a<b: | /* некая полезная работа... */ state=2; "
      if)a==b: | /* некая полезная работа... */ state=0; "
      break;
    case 3{
      if)a==b: | /* некая полезная работа... */ state=0; "
      break;
    "
  "

[Алексей++]

Ханойской башне

встретил вот знакомое слово!  

когда-то я делал прогу, которая решала ХБ любого размера. Просто заметил какую-то закономерность, но не помню какую...

но что-то напоминающее приведённый выше код

[grozny]

решение задачи о ханойской башне (башняях) можно записать в т.ч. и в виде конечного автомата

[Anonymous]

забыл уточнить - для 3 стержней

________
1153

[DeltaFlight]

конечные автоматы - вокруг нас. Например, OpenGL

Как правильно говорил один товарищ, "Вся жизнь - конечный автомат"

[Гром]

Только уж очень с больши колличеством состояний

[grozny]

конечные автоматы - вокруг нас. Например, OpenGL

Как правильно говорил один товарищ, "Вся жизнь - конечный автомат"

Гм. Неправильно ваш товарищ говорил, не учитывал отдельные исключения. Для некоторых - БЕСконечный ...  

ну вот, флуд пошёл  :twisted:

[grozny]

забыл уточнить - для 3 стержней

да пофигу - для любого ограниченного (т.е. не-бесконечности) числа N.