УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»

Об автоматах

1. Фридл Дж. (автор книги Регулярные выражения. Питер, 2001) на странице 121 пишет: "Две базовые технологии, на основе которых строятся механизмы регулярных выражений, носят устрашающие названия "недетерминированный конечный автомат" и "детерминированный конечный автомат"". А в примечании, приведенном на этой странице, он пишет: "Вероятно, мне бы следовало объяснить азы теории конечных автоматов..., если бы я ее знал!".
   
   PS. Я думаю, что аналогичное впечатление о теории автоматов возникает и многих других людей, которые знакомились с ней, например, по хорошей, но очень математической книге Ахо А. и Ульмана Дж. Теория синтаксического анализа, перевода и компиляции. М.: Мир, 1978, изданной в двух томах. Поэтому, мне кажется, что у людей, познакомившихся с этой книгой, когда они слышат об автоматном программировании, положительных эмоций не возникает.
   
   В дополнение к сказанному отметим, что даже в значительно более понятной "простым" людям книге Хопкрофта Д., Мотвани Р. и Ульмана Д. Введение в теорию автоматов, языков и вычислений. М.: Вильямс, 2002, у автоматов нет выходов, а в резюме по второй главе сказано, что "автомат допускает цепочки". При такой трактовке автоматов, они весьма специфичны и об их широком применении для решения различных задач, отличных от работы с текстами , на первый взгляд, нет речи. Материалы, представленные на настоящем сайте, призваны показать, что это не так.
   А.А. Шалыто
2. Для автоматов мною предлагается формула, аналогичная предложенной Н. Виртом для программ "Алгоритмы + Данные = Программы", которая в двузвенном варианте имеет вид:
   
   "Состояния + Входные воздействия = Автоматы без выходов"; "Автоматы без выходов + Выходные воздействия = Автоматы",
   
   (обычно конечные и в большинстве случаев детерминированные).
   А.А. Шалыто
3. Ноль и единица от Бога, остальное дело рук человеческих.
   Кронекер
4. Девочки любят картинки, - сказала Алиса.
   
   PS. Они похоже, в отличии от программистов, не любят тексты программ, даже самодокументирующихся.
   А.А. Шалыто
5. Прошу вас, ради всего святого, сначала научитесь простому и только потом переходите к сложному.
   Эпиктет
6. То, что сделано однажды, может быть повторено вновь.
   Оправдание математической индукции.
7. Я помню Дуга Росса (создателя методологии IDEF0) из компании SofTech, много лет назад говорившего, что 80 или даже 90 процентов информатики (Computer Science) будет в будущем основываться на теории конечных автоматов.
   Brian Randell. Семинар "Software 2000: a View of the Future". 10.04.1994. Из книги Карпов Ю.Г. Теория автоматов. СПб.: Питер, 2002.
8. Мы создали язык генерации машин с конечным числом состояний, так как реальный селекторный телефонный разговор - это группа взаимодействующих машин с конечным числом состояний. Этот язык применяется в "Bell Labs" по прямому назначению - для создания указанных машин. Кроме того, с его помощью стали разрабатывать драйверы.
   Из интервью с создателем операционной системы UNIX Кена Томпсона. Открытые системы. 1999. N4.
9. Большая часть теории автоматов была успешно использована в системных программах и текстовых фильтрах в операционной системе UNIX. Это позволяет множеству людей работать на высоком уровне и разрабатывать очень эффективные программы.
   Brian Randell. Семинар "Software 2000: a View of the Future". 10.04.1994. Из книги Карпов Ю.Г. Теория автоматов. СПб.: Питер, 2002.
10. Я знаю людей из Боинга, занимавшихся системами стабилизации самолетов с использованием чистой теории автоматов. Даже трудно себе представить, что им удалось сделать с помощью этой теории.
    Herve Gallaire. Семинар "Software 2000: a View of the Future". 10.04.1994. Из книги Карпов Ю.Г. Теория автоматов. СПб.: Питер, 2002.
11. Стефан Вольфрам (создатель выдающегося пакета программ символьных вычислений "Mathematica") утверждает, что изобрел новый вид науки, базирующийся на простых компьютерных программах, а не на уравнениях. На это ему понадобилось 20 лет.
    
    Он начал с очень простых программ, называемых cellular automata (клеточный автомат), со строки ячеек, каждая из которых может быть черная или белая.
    
    Предполагалось, что поведение будет очень простым, но интуиция в данном случае подвела.
    
    При некоторых начальных условиях поведение совокупности ячеек становится чрезвычайно сложным, несмотря на простые правила, описывающие поведение каждой ячейки.
    
    После этого он предположил, что природа использует простые программы для создания всех сложностей мира.
    Из интервью с создателем программы "Mathematica" С.Вольфрамом Компьютер-информ. 2002/2. 04.02 - 17.02 (www.ci.ru)
    PS. При этом следует отметить, что математический аппарат, используемый в клеточных автоматах, проще, чем в классической теории фракталов и в теории хаоса.
12. Психология автоматного программирования.
    Название статьи Кузнецов Б.П. в журнале Byte/Россия,2000, 10. (www.softcraft.ru)
13. При объяснении объектно-ориентированного программирования часто утверждают, что поведение совокупности объектов определяется их взаимодействием, осуществляемым путем обмена сообщениями.
    
    При таком объяснении, видимо, предполагается, что логика совокупности объектов децентрализована и распределена по этим объектам.
    
    Такая модель справедлива для децентрализованных систем, например, для группы людей, отдыхающих на лужайке.
    
    Однако в производственных, а особенно в военных организациях, модель управления является иерархической. Такая модель является основной в критических ситуациях, превращаясь практически в централизованную. В таких ситуациях страна без "президента" становится практически нежизнеспособной. Такая же структуру обычно используется и при управлении ответственными технологическими объектами.
    
    Да, и поведение человека формируется не в результате взаимодействия всех его составляющих (ноги, ногтя, волоса, глаза и т.д.), а существенно иначе - иерархически. Основная "логика" сосредоточена в головном, а частично - в спинном мозгу. При этом часть составляющих человека функционирует практически автономно по "своей" логике. Когда человек умирает, эти составляющие могут продолжать работать уже полностью автономно. Например, говорят, что ногти и волосы продолжают расти после смерти. Можно сказать, что комплексная система, превращается в комплекс систем.
    
    Из изложенного следует, что централизация логики должна быть обеспечена как для совокупности объектов за счет выделения автоматов для координации работы совокупности, так и внутри объектов для координации работы их компонент.
    
    Даже без использования объектов логика должна делиться на основную и вспомогательную.
    
    При этом большинство проблем возникает обычно с основной логикой, которая практически всегда взаимосвязана и уникальна. Поэтому во многих задачах для ее описания целесообразно применение автоматов.
    
    Вспомогательная логика, если она и сложна, обычно не приводит к большим проблемам из-за ее автономности, а часто и стандартности.
    
    Главное попасть в состояние, где следует выполнить сортировку, а уж саму сортировку с помощью Д.Кнута или H.Вирта мы, как-нибудь, выполним даже и без применения автоматов.
    А.А. Шалыто
14. В автоматном программировании на выходные функции нет ограничений, что позволяет на их основе строить гибридные системы (логико-дифференциальные или логико-алгебраические).
15. Во многих науках базовым является понятие "состояние". К таким наукам, например, относятся механика ("точка в пространстве состояний"), квантовая механика, металлургия,теория управления, теория автоматов.
    
    Я знаю только две науки, в которых основным является понятие "событие". Это программирование и история.
    
    "История - ряд выдуманных событий по поводу действительно совершившихся", - говорил Шарль Монтескье.
    
    Не исключено, что именно отсутствие состояний позволяет прийти в историю, например, академику Фоменко и сдвинуть в ней отсчет времени.
16. Мне кажется, что Switch-технология простирается от микроконтроллеров с двумя килобайтами памяти до серверов, у которых проблемы с объемом памяти не существует.
    
    Другие технологии проектирования программ, эффективно работающие в таком "диапазоне", мне не известны.
    А.А. Шалыто
17. Фирма "Apple" поменяла девиз рекламной компании - вместо слов "Think Different" она, наконец-то, стала применять "правильное" слово "Switch".
18. В свое время в музее Революции я слышал, что Ленин о необходимости Октябрьской революции в 1916-1917 гг. написал и выступил 317 раз. В результате ему удалось выполнить задуманное.
    
    О необходимости применения автоматного программирования я еще ленинских норм не достиг, но стремлюсь.
19. Эффект сотой обезьяны состоит в следующем.
    
    На большой остров высадили обезьян. Потом очистили банан и бросили в песок.
    
    Одна из обезьян взяла этот банан и стала его есть. Ей это не понравилось. Через некоторое время она поняла, что банан до еды необходимо мыть.
    
    Вторая обезьяна, наблюдавшая этот процесс, значительно быстрее пришла к выводу, что до еды следует банан мыть.
    
    Начиная с сотой, каждая из обезьян сразу же стала мыть бананы, включая и тех, что находились на другом конце острова и не могли наблюдать за процессом обучения.
    
    Просто начиная с некоторой "критической массы обезьян" идея стала передаваться "по воздуху".
    
    PS. В автоматном программировании еще нет ста обезьян, но этот миг я приближаю, как могу.
20. Это смешно, но моя глобальная цель применительно к Switch-технологии, образно говоря, состоит в том, чтобы в цивилизованной стране средний программист зарабатывал не больше среднего учителя.
    
    Сейчас имеет место минимум двукратная разница, что, видимо, связано в том числе и с тем, что программисты в большинстве случаев не оставляют после себя легко понятных "следов", что делает их практически незаменимыми и во многом определяет размер зарплаты.
21. Для систем со сложным поведением о Switch-технологии по аналогии с высказыванием У. Черчилля о капитализме, видимо, можно сказать: "Это плохая технология, но лучшей пока никто не придумал". В этой технологии, по крайней мере, "сходятся концы с концами" в том смысле, что проектирование, реализация и протоколирование выполняется в одних терминах - в терминах автоматов.
22. Также, как реле за счет небольшой энергии управляющего сигнала, поданного на обмотку, может коммутировать сигналы большой мощности, так и автомат, обладая небольшим числом состояний, может управлять большим числом состояний "объекта управления", как это имеет место, например в задаче о ханойских башнях (см. раздел "Статьи").
23. Один студент, впервые увидев проектную документацию, оформленную по технологии автоматного программирования (см. раздел "Проекты"), воскликнул: "Она лучше, чем на телевизор. Видимо, такая же, как для подводной лодки".
24. В чем главное достоинство автоматного подхода?
    
    Каждое состояние выделяет из множества входных (выходных) переменных то подмножество, которое существенно при переходах из этого состояния.
25. Что такое автомат Калашникова?
    
    Преобразователь стека в очередь.
    Программистский фольклор
26. Автоматное программирование достаточно узкая область - оно может использоваться только в 98% всех микропроцессоров, выпускаемых в мире, которые применяются в управлении.
27. Технология автоматного программирования должна ответить на вопрос Александра Чижова (chizh@irk.ru): "Теорию конечных автоматов мы проходили, но при чем здесь программирование?"
28. Понятие "состояние" широко не применяется в программировании, так как в нем не различаются управляющие и все остальные состояния, а в качестве состояний рассматриваются значения ячеек памяти. Компьютер содержит огромное число ячеек, поэтому и состояний чрезвычайно много, и с ними непонятно, что делать.
    
    Если, как в машине Тьюринга, такое разделение провести, то все в этом вопросе становится на свои места. Этому посвящена статья "От тьюрингова программирования к автоматному", приведенная в разделе "Статьи".
29. С чего должна начинаться программа?
    
    Обычно она начинается с опроса значений входных переменных.
    
    При автоматном программировании программа начинается с проверки внутреннего состояния алгоритма (программы), а не состояния объекта управления, определяемого значениями соответствующих входных переменных.
30. Управлять многими объектами на основе состояний весьма естественно и удобно.
    
    Если каждому состоянию объекта сопоставить соответствующее состояние управляющего "устройства", то последнее, изменив свое состояние под воздействием входных воздействий, может за счет формирования выходных воздействий перевести объект в "одноименное" состояние.
    
    Число состояний управляющего "устройства" может быть не только равно числу состояний в управляемом объекте, но и меньше этого числа (одно состояние "устройства" поддерживает несколько, например два, состояния объекта), а также больше указанного числа, например, когда "устройство" введены дополнительные состояния, предназначенные, например, для отражения неисправных состояний объекта.
31. Кроме управления, состояния естественно и удобно применять также и при моделировании многих процессов и сред. Например, для воды характерны три основных состояния (жидкое, твердое и газообразное). Если температура воды понизится до некоторого значения, то осуществляется переход в новое состояние, в котором вода может выполнить действия, вызывающие, например, разрыв труб.
32. В ряде книг написано, что состояния проявляются через действия. Я считаю, что это не так, ввиду того, что состояние души это внутреннее свойство, по крайней мере в начале, никак не связанное с действиями.
33. Не все золото, что блестит.
    
    Не все автомат, что switch.
34. Виктор Михайлович Глушков понимал, что в силу своей большой общности теория автоматов может быть применена для разработки моделей кибернетических систем в самых разнообразных прикладных областях.
    
    За разработку теории цифровых автоматов и другие работы международная организация IEEE Computer Society в 1998 году посмертно удостоила академика В.М. Глушкова медали Computer Pioneer, которую получило около 50 человек во всем мире.
    Кибернетик. Информатика. 2003. N40.
35. У Гради Буча "вложенные состояния", у меня "вложенные автоматы".
    
    Мне кажется, что вложенность матрешек более понятна, по сравнению с вложенностью состояния "дружба" в состояние "любовь".
36. Документация на программное обеспечение должна не только описывать результат, но и процесс его получения!
37. Когда читая проектную документацию, спотыкаешься на каждом слове, то автор либо разгильдяй, либо не умеет писать, либо сам до конца не понимает о чем пишет, либо сделанное неправильно.
    
    Если документацию на проект можно "проглотить" не останавливаясь, то скорее всего и сам проект сделан по-человечески.
38. Где по-халявному написано, там и сбой, а где на автоматах, там работает железно.
    Высказывание одного из студентов
39. — Учитель, — проговорил Сунь-У-кун.
    — Я человек простой и вашего городского языка не понимаю. Что значит подпорки к стене?
    — Когда люди начинают строить дом и хотят сделать его прочным и крепким,то между стенами ставят подпорки. Но проходит время, и здание рушится, а это значит, что подпорки сгнили.
    У Чен-эль. Путешествие на Запад. Глава 2.
    PS. Конец этой истории напоминает, конец программ, логика которых реализована на флагах.
40. Философ Теренций сказал: «Когда двое делают одно и то же, это уже не одно и то же».
    
    У меня в жизни был случай, на основании которого можно сказать, что даже «когда один делает одно и то же, не всегда получается не одно и то же».
    
    Это было так. Я попросил квалифицированного инженера по словесному описанию простого последовательностного алгоритма, который он хорошо знал, построить схему алгоритма и функциональную схему. При этом он, естественно, предполагал, что построенные схемы будут эквивалентны.
    
    Каково же было его удивление, когда я показал ему несколько отличающиеся друг от друга графы переходов, построенные по каждой из указанных схем формально.
    
    Это объясняется тем, что все особенности применяемого языка алгоритмизации практически невозможно учесть эвристически: инженер интуитивно доопределил неполностью определенные булевы функции на входах триггера в функциональной схеме иначе, чем они были определены при использовании другого языка формализации.
41. В книге Козлова  В.Н. Математика и информатика. СПб.: Питер, 2004 в виде аксиом сформулированы условия, которые должны выполняться при построении систем автоматизированного управления. Приведем две из них, на которых основана switch-технология.
    
    Аксиома 1. Наличие наблюдаемости объекта управления. Наблюдаемость обеспечивается, если по результатам наблюдения за объектом можно определить любое его состояние, что используется при формировании управляющих воздействий на объект управления.
    
    Аксиома 2. Наличие управляемости — способности объекта управления переходить из текущего состояния в требуемое под воздействием управляющей системы.
42. Некоторые люди говорят мне, что при создании простых программ нецелесобразно использовать автоматный подход, а такие программы можно писать проще (другими словами, как «Бог на душу положит»).
    
    Может быть это и так, но зачем что-то делать как-нибудь, если знаешь как правильно.
    
    Посмотрите, к примеру, документацию на игру «Космонавт», размещенную на этом сайте в разделе «Проекты», и Вам станет ясно зачем применять автоматы даже при написании такой сравнительно простой игры, как это стало ясно моим соавторам по этой статье, которые раньше использовали для реализации поведения флаги.
43. В этом семестре юнимодно использовать при выполнении курсовых проектов инструментальное средство UniMod.
    Максим Мазин
44. В пакете Borland Developer Studio 2006 улучшена система моделирования UML. В частности, введена возможность использования при моделировании диаграмм состояний.
    Computerworld Россия. 29.11.2005
45. Представлен инструментарий для разработчиков Sun Java Studio Enterprise 8, в состав которого входит интерфейс визуального моделирования UML (диаграммы классов и диаграммы последовательностей).
    Computerworld Россия. 29.11.2005
46. Нашим традиционным текстовым языкам не хватает средств для того, чтобы оценивать и понимать поведение программ. В результате моделирование становится неизбежной реальностью. Буч  Г. Будущее моделирования выглядит оптимистично
    //PC Week/RE. 2005. N42, с.23,38.
47. Программирование — это умение организовать сложную систему и управлять ее бесчисленными элементами, пресекая всеми силами присущую им тенденцию к изначальному хаосу.
    Эдсгер Дейкстра
48. Четвертая глава полностью посвящена так называемому «автоматному программированию». Суть этой концепции состоит в том, чтобы писать алгоритмы, по своему поведению напоминающие устройства, подобные конечным автоматам.
    
    Конечные автоматы, по сути, вымышленные устройства, оказались на редкость полезными в практическом программировании. Работа со строками и подстроками — не единственная область, в которой конечные автоматы могут принести пользу. Существуют процессы, удобно представимые в виде состояний и переходов. Представление подобных устройств с помощью конечных автоматов может заметно сэкономить наши усилия по их моделированию.
    
    Говорю о конечные автоматах, нельзя не затронуть еще одну тему, довольно популярную в последние годы: автоматное программирование, которую я хочу представить как новый блестящий инструмент для вашей коллекции.
    
    Видимо, расплывчатое понятие «удобства» использования той или иной парадигмы во многом определяется личными склонностями и образованием программиста. Вполне возможно, что математику всегда проще думать в терминах предикатов и функций, а инженеру - в терминах автоматов.
    
    Под «автоматом» в автоматном программировании понимается куда более мощное устройство, чем конечный автомат, традиционно применяемый применяемый в программировании: очередное состояние автомата определяется с помощью вычисления любой, сколь угодно сложной функции, а при переходе автомата из одного состояния в другое может выполняться сколь угодно сложный фрагмент кода.
    
    Таким образом, получается гибридное устройство, в котором чисто автоматная модель сочетается с произвольными фрагментами кода на используемом языке программирования.
    
    Психологическое значение автоматов очень велико. Компьютеру все равно, какую программу выполнять, а для человека есть существенная разница в том, как написана программа.
    
    Конечный автомат — еще одна абстракция, которую целесообразно применять в программировании, которая может помочь взглянуть на задачу по-новому.
    Мозговой М.В. Классика программирования: языки, автоматы, компиляторы. Практический подход. СПб.: Наука и Техника, 2006.
49. Под термином "автоматное программирование" понимается не построение и реализация конечных автоматов, а проектирование и исполнение программ в целом, поведение которых описывается автоматами. А.Ш.
50. Похоже, что на долю информатики в школе выпадает сейчас общекультурная роль, выходящая за чисто математическую.
    
    В частности, современный человек должен пользоваться понятиями: "объект и его состояние", "переход в новое состояние", "взаимодействие между объектами" и т.д.
    
    Рассмотрение ситуации информационного взаимодействия элементов системы, особенно при управлении, послужило основой для возникновения целого научного направления - кибернетики.
    
    Понятия "управление", "обратная связь" также сегодня относятся к общекультурному багажу.
    
    Информатика рассматривает сегодня общую ситуацию перехода от объектов реального мира к их дискретным информационным образам, "дискретизацию" непрерывных математических объектов, возникновение глобального поведения, задаваемого локальными правилами (на школьном уровне это реализуется, например, игрой "Жизнь").
    
    Перечисленные элементы современной культуры можно донести в "чисто информирующей" форме увлекательного рассказа. Однако среди важнейших традиций российской математического образования имеется его деятельностный, "задачный" характер. Многие такие задачи могут поставляться, например, "теорией конечных автоматов", затем - "теорией клеточных автоматов" и т.д.
    Академик РАН Журавлев Ю.И. Фундаментально-математический и общекультурный аспекты школьной информатики //Информатика. 2007. N2, с.28-32.
51. При создании ПТК "Саргон" основой прикладного ПО стало использование математического аппарата теории автоматов, что позволило построить алгоритмы высокой сложности и гарантированной надежности. При этом реализовывались весьма сложные алгоритмы, в том числе автоматизированного пуска турбокомпрессора.
    Менделевич В.А. Рождение ПТК "Саргон" //Промышленные АСУ и контроллеры. 2006. N12, с.3-5.
52. Если программа написана традиционно, то не ясно как объснять ее работу: рассказывать что она делает или как она делает.
    
    При использовании автоматного подхода "что" и "как" практически совпадает.