Русский  
English
Сайт ДонНТУ  
Портал магістрів

Реферат за темою випускної роботи

Зміст

Вступ

Кінцеві автомати (КА) становлять цікавість для дослідження і застосування на практиці. Простою мовою, КА – це якась абстрактна модель, що має кінцеву кількість станів. Дана модель призначена для опису і аналізу поведінки різноманітних пристроїв дискретної дії або протікання процесів дискретної обробки інформації, для моделювання і побудови пристроїв і процесів [1]. У свою чергу ці пристрої і процеси можуть зазнавати змін, зумовлених зовнішніми факторами. У ряді випадків такий вплив призводить до зміни поведінки автомата. Подібні зміни можна розглядати як процес перекидання дуг в автоматі. Практичну цінність представлятимуть перекидання, при яких поведінка автомата збережеться. У випадку з автоматами-розпізнавача це будуть автомати, які приймають ту саму мову, що й початковий автомат після проведення ряду перетворень. У даній роботі буде розглянута можливість перекидання дуг в автоматі-акцепторі зі збереженням його поведінки.

1. Актуальність теми

Універсальність теорії автоматів дозволяє розглядати з єдиної точки зору різні об'єкти, враховувати зв'язки та аналогії між ними, переносити результати з однієї області в іншу [1].

Кінцеві автомати мають широкий діапазон використання. Теорія автоматів застосовується в комп'ютерних іграх при написанні штучного інтелекту для персонажу [2]. Автомати використовують в системах підготовки і редакції текстів [3], в розробці керуючих програмних систем [4], при програмуванні мобільних пристроїв [5], для тестування програмних рішень [6].

Широко використовуються кінцеві автомати в криптографії: в побудові криптосистем і як компонент криптоалгоритмів [7]. Зокрема, застосовуються КА в поточних і автоматних шифросистемах, в симетричних шифрах і криптосистемах з відкритим ключем [8].

Таким чином, дослідження автоматів є актуальним завданням і може згодом знайти широке застосування в різних областях.

2. Цель и задачи исследования, планируемые результаты

Об'єктом дослідження є поведінка приведеного автомата-розпізнавача при перекиданні дуг.

Предметом дослідження виступає знаходження умов, при яких автомат після перекидання k дуг приймає ту саму мову, що й початковий – автомат-еталон.

Цiль: Розробка та дослідження методу аналізу автоматів-розпізнавачів, породжуваних локальними перетвореннями еталона.

Основні завдання дослідження:

  1. Провести аналіз поведінки автомата-розпізнавача при перекиданні k дуг, k ≥ 1.
  2. Систематизувати отримані в ході вирішення практичних прикладів результати.
  3. Знайти закономірності, при яких можливе або не можливе перекидання k дуг зі збереженням поведінки автомата.
  4. Зробити висновки і описати клас автоматів, що допускають перекидання дуг зі збереженням еквівалентності.

3. Огляд досліджень і розробок

3.1 Огляд міжнародних джерел

Аналіз і дослідження структури автоматів зі схожим поводженням є досить поширеними явищами, і проводяться давно. Ці завдання належать до експериментальної теорії з автоматами, яка ретельно викладена в книзі А. Гілла Введення в теорію кінцевих автоматів [9].

Основні положення теорії експериментів над автоматами були описані Едвардом Муром [10]. Він зробив великий внесок в розвиток методів дослідження КА, вперше запропонувавши алгоритм розпізнавання еквівалентних автоматів.

Зокрема, теорію експериментів висвітлюють роботи Р. Брауера [11], П. Штарке [12], Ф. Хенні [13] і багатьох інших авторів.

3.2 Огляд національних джерел

На національному рівні дослідження автоматів і їх поведінки за допомогою експериментів було розглянуто М.П. Василевським [14], Н.В. Євтушенко, А.Ф. Петренко [15-18], В.Б. Кудрявцевим, І.С. Грунським, В.А. Козловським [19-28], В.А. Буєвичем, Н.Г. Каландарашвілі, А.А. Талем [29, 30].

3.3 Огляд локальних джерел

Дослідження поведінки автоматів при перекиданні на локальному рівні було проведено О.М. Копитовою [31-33], а також О.С. Швець [34] і Є.І. Бурлаевою [35] в рамках виконання магістерських робіт.

Для приведених автоматів Мілі були отримані наступні результати:

4. Автоматна модель

У даній роботі розглядається автомат-розпізнавач. Це такий автомат, який дозволяє визначити приналежність ланцюжка символів деякій мові. Завдання розпізнавача полягає в тому, щоб на підставі початкового ланцюжка дати відповідь, чи належить вона заданій мові чи ні.

Нами буде розглядатися приведений детермінований акцептор.

Проводити аналіз перекидання дуг в автоматі будемо поетапно:

5. Теоретичні результати

Теорема 1. Перекидання однієї дуги в приведеному автоматі-розпізнавачі призводить до неізоморфного автомату.

Теорема 2. Для будь-якого k ≥ 3 існує автомат-розпізнавач, що допускає перекидання k-дуг.

Доказ. Побудуємо приведений акцептор, що містить n > 3 станів, з одним вхідним і одним заключним станом. За одиницею кожне стан переходить саме в себе. За нулем – переходить в стан i + 1. Перший стан – вхiдний, n-ий стан – заключний (за нулем теж переходить саме в себе).

На малюнку 1 представлений автомат-розпізнавач.

Загальний вигляд акцептора

Малюнок 1 – Загальний вигляд акцептора

Покажемо, що автомат приведений. Візьмемо два стани i и j, де n – 1 > i ≥ 1, n ≥ j ≥ 1, j > i. З побудови видно, що δ (j, 0n-j) ∈ F, а δ (i, 0n-i) ∉ F. А стани n и n – 1 розрізняються за одиницею: δ (n, 1) ∈ F, а δ (n – 1, 1) ∉ F.

перекидання k-дуг здійснюється наступним чином:

Для наочності наведемо результат перекидання k-дуг в акцепторi (рисунок 2).

Автомат-розпізнавач після перекидання

Малюнок 2 – Автомат-розпізнавач після перекидання

З малюнка 2 видно, що в результаті отримали автомат, еквівалентний початковому.

На малюнку 3 проілюстрований приклад перекидання 3-х дуг зі збереженням еквівалентності автомата.

Приклад перекидання 3-х дуг в акцепторі

Малюнок 3 – Приклад перекидання 3-х дуг в акцепторі
(анiмацiя: 18 кадрiв, 3 цикла повтору, 134 кiлобайт)
(на вхід подається слово 00100, червоним кольором відзначений процес розпізнавання слова автоматом, синім – процес перекидання дуг)

Висновки

На підставі отриманих даних були зроблені наступні висновки:

При написанні даного реферату магістерська робота ще не завершена. Остаточне завершення: травень 2018 року. Повний текст роботи та матеріали за темою можуть бути отримані у автора або його керівника після зазначеної дати.

Список джерел

  1. Паулин О.Н. Основы теории алгоритмов: учебное пособие / О.Н. Паулин. – Одесса: Автограф, 2005. – 188 с.
  2. Алимов А.А., Шабалина О.А. Искусственный интеллект в компьютерных играх. Многоуровневое планирование и реактивное поведение агентовагентов / А.А. Алимов, О.А. Шабалина // Известия ВолгГТУ. – 2011. – № 10. – С. 90-94.
  3. Капитонова Ю.В. Основы дискретной математики / Ю.В. Капитонова, С.Л. Кривий, А.А. Летичевский, Г.М. Луцкий, Н.К. Печурин. – К.: Наукова думка, 2002. – 568 с.
  4. Смирнова Н.В., Смирнов В.В. Применение теории конечных автоматов в разработке программных систем / Н.В. Смирнова, В.В., Смирнов // Збірник наукових праць Кіровоградського національного технічного університету. Техніка в сільськогосподарському виробництві, галузеве машинобудування, автоматизація. – 2014. – Вип. 27. – С. 316-320.
  5. Салмре И. Программирование мобильных устройств на платформе .Net Compact Framework / И. Салмре. – М.: Вильямс, 2006. – 702 с.
  6. Бурдонов И.Б., Косачев А.С., Кулямин В.В. Использование конечных автоматов для тестирования программ / И.Б. Бурдонов, А.С. Косачев, В.В Кулямин // Программирование. – 2000. – № 2. – С. 12-28.
  7. Фомичев В.М. Дискретная математика и криптология / В.М. Фомичев. – М.: ДИАЛОГ-МИФИ, 2003. – 400 с.
  8. Агибалов Г.П. Конечные автоматы в криптографии / Г.П. Агибалов // Прикладная дискретная математика. Приложение. – 2009. – № 2. – С. 43-73.
  9. Гилл А. Введение в теорию конечных автоматов / А. Гилл. – М.: Наука, 1966. – 272 с.
  10. Мур Э.Ф. Умозрительные эксперименты с последовательностными машинами / Э.Ф. Мур // Автоматы. – М.: Иностр. лит. – 1956. – С. 179-210.
  11. Брауэр Р. Введение в теорию конечных автоматов/ Р. Брауэр. – М.: Радио и связь, 1987. – 392 с.
  12. Starke P. Abstract automata / P. Stapke // American Elsevier, 1972. – 419 с.
  13. Hennie F.C. Fault detecting experiments for sequential circuits / F.C. Hennie // Proc. 5 Annual Symp. «Switch. Circuits Th. and Logic. Design». – 1964. – P. 95-110.
  14. Василевский М.П. О распознавании неисправностей автомата / М.П. Василевский // Кибернетика. – 1973. – № 4. – С. 93-108.
  15. Евтушенко Н.В., Лебедев А.В., Петренко А. Ф. О проверяющих экспериментах с недетерминированными автоматами / Н.В. Евтушенко, А.В. Лебедев, А.Ф. Петренко // Автоматика и вычислительная техника. – 1991. – № 6. – С. 81-85.
  16. Евтушенко Н.В., Петренко А.Ф. Метод построения проверяющих экспериментов для произвольного недетерминированного автомата / Н.В. Евтушенко, А.Ф. Петренко // Автоматика и вычислительная техника. – 1990. – № 5. – С. 73-76.
  17. Евтушенко Н.В., Петренко А.Ф. О проверяющих возможностях кратных экспериментов / Н.В. Евтушенко, А.Ф. Петренко // Автоматика и вычислительная техника. – 1989. – №3. – С. 9-14.
  18. Петренко А.Ф. Эксперименты над протокольными объектами / А.Ф. Петренко // Автоматика и вычислительная техника. – 1987. – № 1. – С. 16-21.
  19. Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию автоматов/ В.Б. Кудрявцев, С.В. Алешин, А.С. Подколзин. – М.: Наука, 1985. – 320 с.
  20. Кудрявцев В.Б., Грунский И.С., Козловский В.А. Анализ поведения автоматов / В.Б. Кудрявцев, И.С. Грунский, В.А. Козловский // Дискретная математика. – 2009. – №1. – С. 3-35.
  21. Кудявцев В.Б., Грунский И.С., Козловский В.А. Анализ и синтез абстрактных автоматов / В.Б. Кудрявцев, И.С. Грунский, В.А. Козловский //Фундаментальная и прикладная математика. – Т. 15, № 4. – 2009. – С. 101-175.
  22. Грунский И.С., Козловский В.А., Пономаренко Г.Г. Представления конечных автоматов фрагментами поведения/ И.С. Грунский, В.А. Козловский, Г.Г. Пономаренко. – Киев: Наукова думка, 1990. – 232 с.
  23. Грунский И.С. Анализ поведения конечных автоматов/ И.С. Грунский. – Луганск: изд-во Луганск. гос. пед. ун-та, 2003. – 318 с.
  24. Грунский И.С., Козловский В.А. Синтез и идентификация автоматов/ И.С. Грунский, В.А. Козловский. – Киев: Наукова думка, 2004. – 246 с.
  25. Грунский И.С., Максименко И.И. Об экспериментах с автоматами при отсутствии верхней оценки числа состояний / И.С. Грунский, И.И. Максименко // Кибернетика и системный анализ. – 1999. – № 4. – С. 59-71.
  26. Козловский В.А. О структуре контрольных экспериментов с автоматом / В.А. Козловский // Кибернетика. – 1978. – № 3. – С. 19-33.
  27. Козловский В.А. О распознавании автомата относительно локально порожденного класса / В.А. Козловский // ДАН СССР. – 1981. – № 5. – С. 1047-1049.
  28. Козловский В.А., Копытова О.М. Представления автоматов относительно m-плотных классов / В.А. Козловский, О.М. Копытова // Матер. VIII Межд. семинара «Дискретная математика и ее приложения» (Москва, 2-6 февраля 2004 г.) – М.: Изд. МГУ. – С. 277-280.
  29. Буевич В.А., Каландарашвили Н.Г., Таль А.А. Об описании конечного автомата с помощью конечного множества вход-выходных слов / В.А. Буевич, Н.Г. Каландарашвили, А.А. Таль // Автоматика и телемеханика. 1970. – № 1. – С. 112-122.
  30. Буевич В.А., Каландарашвили Н.Г., Таль А.А. Конечные автоматы – эквивалентность и поведение/ В.А. Буевич, Н.Г. Каландарашвили, А.А. Таль. – М.: Наука, 1984. – 192 с.
  31. Копытова О.М. О структуре автоматов, сохраняющих поведение при перебросках дуг / О.М. Копытова // Труды VIII Международной конференции «Дискретные модели в теории управляющих систем». – М.: Макс-Пресс, 2009. – C. 155-159.
  32. Копытова О.М. О возможности сохранения поведения автомата при перебросках дуг / О.М. Копытова // Материалы VI Международной научно–практической конференции Новости научной мысли – 2010 (27.10-05.11.2010), Чехия. Прага. Издательский дом Образование и наука, 2010 – C. 41-46.
  33. Копытова О.М. Устойчивость автоматов к неисправностям их функции переходов / О.М. Копытова // Труды ИПММ АН Украины. – 2010. – № 21. – С. 57-66.
  34. Швец О.С., Копытова О.М. О сравнении поведения ОДk-эталона и автоматов, порождаемых его локальными преобразованиями / О.С. Швец, О.М. Копытова // Материалы V всеукраинской научно-технической конференции студентов, аспирантов и молодых ученых «Информационные управляющие системы и компьютерный мониторинг (ИУС КМ 2014)» (22.04-23.04.2014). Донецк: ДонНТУ, 2014. – С. 365-369.
  35. Бурлаева Е.И., Копытова О.М. Об одном типе локальных преобразований автомата / Е.И. Бурлаева, О.М. Копытова // Материалы IV всеукраинской научно-технической конфиренции студентов, аспирантов и молодых ученых «Информационные управляющие системы и компьютерный мониторинг (ИУС КМ 2013)» (24.04-25.04.2013). Донецк: ДонНТУ, 2013. – C. 479-484.