Рубрика «конечные автоматы»

image

Введение

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

image

«Чувства» в разработке игр — это полезная метафора для понимания, создания и обсуждения той части ИИ, которая занимается сбором информации о важных объектах симулируемой среды игры. Неигровыми персонажами в реалистичном трёхмерном пространстве обычно бывают люди, животные или другие создания со зрением и слухом, поэтому такая метафора очень удобна.

Но такую метафору разработки не стоит воспринимать слишком буквально. Несмотря на кажущуюся физическую природу ИИ игрового мира, эта аналогия не физическая и не нейрологическая. Грань между «чувством» и «знанием» в игре размыта. Чувство включает в себя идею осознания присутствия в игре других элементов игры, а также их оценку и знания о них. Игровая логика может быть привязана непосредственно к таким элементам.

Систему чувств в игре нужно создавать таким образом, чтобы она подчинялась потребностям дизайна игры и была эффективной в реализации. Система не должна быть слишком сложной, достаточно обеспечивать надёжность и интересный игровой процесс. Результат её работы должен быть воспринимаем игроком и понятен ему. Только в немногих играх ИИ необходимы ощущения вкуса, касания или осязания, в основном же используется зрение и слух. При правильном использовании чувства могут стать неоценимым инструментом для создания более интересного поведения простых конечных автоматов.

В этой статье описывается подход к дизайну и реализации высокоточной сенсорной системы для ИИ в игре от первого лица с упором на стелс. Описанные здесь техники взяты из опыта разработки ИИ для Thief: The Dark Project, а также из ознакомления с кодом Half-Life. В первой части статьи изложены базовые концепции чувств ИИ на мотивирующем примере Half-Life. Во второй части излагаются более строгие требования к сенсорным системам в дизайне стелс-игр и описывается система, созданная для Thief.
Читать полностью »

hh2e_lecture_slides_banner_3

Господа! Сегодня на 1 сентября, в День Знаний, группа из украинских преподавателей вузов, их аспирантов, а также российских инженеров, решили, по согласованию с британскими издателями Elsevier через компанию Imagination Technologies, сделать небольшой подарок всем учителям компьютерной архитектуры и цифровой схемотехники, особенно тем, которые используют популярный учебник Дэвида Харриса и Сары Харрис.

Просто нажмите вот на эту ссылку и вы получите zip-файл со слайдами для чтения лекций по этому учебнику на русском языке. Причем без регистрации, которая требуется для загрузки учебника как такового.

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

Итого, вырезка из слайдов, чтобы вы поняли, о чем идет речь:
Читать полностью »

Введение

SimInTech является средой для создания математических моделей любых систем, уравнение динамики которых можно представить в виде входо-выходных соотношений (представление DataFlow). Для реализации подхода конечных автоматов в среде SimInTech существовал блок условного выполнения субмодели, который обеспечивал остановку и запуск моделирования по условию, приходящему извне. Такой подход обеспечивает возможность разделить общую модель на состояния и в каждый момент времени рассчитывать только те субмодели, условия выполнения которых установлены в true. Однако, такая реализация автоматного подхода не очень удобна, с точки зрения наглядности, и требовала дополнительной настройки параметров системы.

В настоящее время все необходимые настройки реализованы в специальной библиотеке блоков, которая обеспечивает создание моделей систем в виде конечных автоматов, (представление State Flow) и может быть использована при создании моделей управления.

В данной статье показан пример использования элементов библиотеки «Конечные автоматы» для создания системы управления.
Читать полностью »

Господа! Только что на сайте Imagination Technologies вышло исправленное издание бесплатного учебника на русском языке «Цифровая схемотехника и архитектура компьютера» Дэвида Харриса и Сары Харрис (кстати, они не супруги и вообще не родственники – просто так совпало). Предыдущее издание этого учебника вышло год назад, пост о нем собрал 145,000 просмотров на Хабре, количество скачиваний с британского сайта вызвало у его британских админов подозрение, что их атакуют русские хакеры, а впоследствие команду переводчиков лично благодарили за учебник преподаватели МФТИ, МВТУ им. Баумана, харьковского ХНУРЭ и других университетов.

silicon_russia_ad_selected_160730_174932

Книжка содержит «введение во все», доступное способному школьнику или младшему студенту, который после ее прочтения может спроектировать, написать на SystemVerilog или VHDL и реализовать на ПЛИС несложный, но при этом совершенно настоящий конвейерный процессор. Книга написана живым языком и для введения концепций, например конечных автоматов, использует примеры типа:

Новая редакция популярного бесплатного учебника электроники, архитектуры компьютера и низкоуровневого программирования - 2
Читать полностью »

Привет!

Одна из сложных задач современной разработки — это программирование пользовательского интерфейса. С увеличением количества элементов сложность увеличивается нелинейно и совладать с огромным количеством вариантов, состояний и переходов становится практически невозможно. Фреймворки вроде Angular со своим двусторонним связыванием пытается решить эту проблему, но на фундаментальном уровне ничего не меняется.

Со-основатель, технический директор и главный учитель нашего образовательного проекта Хекслет Кирилл Мокевнин рассказывает про сложность программирования интерфейсов и каким образом можно совладать со сложностью если вы знакомы с одной базовой концепцией информатики. Заодно расскажет и покажет идеальный JS-фреймворк для программирования UI.

Читать полностью »

Почти каждый микроконтроллерщик сталкивался с громадными switch-case и мучительно их отлаживал.
И много кто, начиная писать реализацию какого-либо протокола, задумывался как написать её красиво, изящно, так чтобы через месяц было понятно что ты имел в виду, чтобы она не отжирала всю память и вообще какала бабочками.
И вот тут на помощь приходят машины состояний, они же конечные автоматы (те самые которые используются в регулярных выражениях).

Собственно через регулярные выражения я к ним и пришёл.
Читать полностью »

Изучаем алгоритм работы регулярных выражений в Ruby
Согласно Википедии, Oniguruma означает «колесница дьявола» в переводе с японского.

Мы все знакомы с регулярными выражениями. Они являются «швейцарским армейским ножом разработчика». Чтобы вы не искали, какой бы текст не разбирали, вы всегда можете сделать это используя регулярные выражения. На самом деле, вероятно, вы начали использовать регулярные выражения гораздо раньше, чем стали использовать Ruby — они уже давно включены в большинство популярных языков программирования: Perl, JavaScript, PHP, Java и прочие. Ruby появился в середине 1990-х годов, тогда как регулярные выражения еще в 1960-х, то есть почти на 30 лет раньше!

Но как на самом деле работают регулярные выражения?
Читать полностью »

Автоматический анализ текстов практически всегда связан с работой со словарями. Они используются для морфологического анализа, выделения персон (нужны словари личных имен и фамилий) и организаций, а также других объектов.

В общем виде словарь — множество записей вида {строка, данные ассоциированные с этой строкой}.

Например, для морфологического анализа словарь состоит из троек {словоформа, нормальная форма, морфологические характеристики}. При анализе слова «мыла» из предложения «мама мыла раму» надо уметь получать следующие варианты анализа:

Нормальная форма Характеристики
МЫЛО S (существительное), РОД (родительный падеж), ЕД (единственное число), СРЕД (средний род), НЕОД
(неодушевленность)
МЫЛО S (существительное), ИМ (именительный падеж), МН (множественное число), СРЕД (средний род), НЕОД (неодушевленность)
МЫЛО S (существительное), ВИН (винительный падеж), МН (множественное число), СРЕД (средний род), НЕОД (неодушевленность)
МЫТЬ V (глагол), ПРОШ (прошедшее время), ЕД (единственное число), ИЗЪЯВ (изъявительное наклонение), ЖЕН (женский род), НЕСОВ (несовершенный вид)

Читать полностью »

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

  • Команда grep операционной системы Unix или аналогичные команды для поиска цепочек, которые можно встретить в Web-броузерах или системах форматирования текста. В таких системах РВ используются для описания шаблонов, которые пользователь ищет в файле. Различные поисковые системы преобразуют РВ либо в детерминированный конечный автомат (ДКА), либо недетерминированный конечный автомат (НКА) и применяют этот автомат к файлу, в котором производится поиск.
  • Генераторы лексических анализаторов. Лексические анализаторы являются компонентом компилятора, они разбивают исходную программу на логические единицы (лексемы), которые могут состоять из одного или нескольких символов и имеют определенный смысл. Генератор лексических анализаторов получает формальные описания лексем, являющиеся по существу РВ, и создает ДКА, который распознает, какая из лексем появляется на его входе.
  • РВ в языках программирования.

В данной статье мы сначала ознакомимся с конечными автоматами и их видами(ДКА и НКА), и далее рассмотрим пример построения минимального ДКА по регулярному выражению.
Читать полностью »