Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Автоматное программирование

Содержание

А.А. ШалытоАвтоматное программированиеАвтоматное программированиеПредложено мною в 1991 годуПрограммные системы предлагается разрабатывать так же, как выполняется автоматизация технологических (и не только) процессовСистема управления является системой взаимодействующих конечных автоматовСостоянияСобытия и входные переменныеВыходные воздействияКонечный автоматСистема конечных автоматов
Автоматное программированиеА.А. ШалытоСанкт-Петербургский государственный университет информационных технологий, механики и оптики2007 г. А.А. ШалытоАвтоматное программированиеАвтоматное программированиеПредложено мною в 1991 годуПрограммные системы предлагается разрабатывать так А.А. ШалытоАвтоматное программированиеАвтоматное программированиеСистема управленияМашина Тьюринга А.А. ШалытоАвтоматное программированиеКак строить программы?Поставщики событийСистема конечных автоматовОбъекты управленияОбратная связь А.А. ШалытоАвтоматное программированиеПреимуществаОбладает наибольшей эффективностью для систем со сложным поведениемФормальное и понятное А.А. ШалытоАвтоматное программированиеПрименение«Железо»МикропроцессорыМикроконтроллерыПрограммируемые логические контроллерыПарадигмыПроцедурнаяОбъектно-ориентированнаяЯзыки контроллеровЛестничные схемыФункциональные схемыПрограммное обеспечениеСистемы высокой надежностиВоенные приложенияАэрокосмическая индустрияВстроенные системыМобильные системыВизуализаторыWeb-приложенияКлиент-сервер приложения А.А. ШалытоАвтоматное программированиеИнструментальное средство UniMod (1)Инструментальное средство для поддержки автоматного программированияСоздано в рамках А.А. ШалытоАвтоматное программированиеИнструментальное средство UniMod (2)Локальная и удаленная отладка диаграмм в терминах А.А. ШалытоАвтоматное программированиеИнструментальное средство UniMod (3)Семь автоматов А.А. ШалытоАвтоматное программированиеИнструментальное средство UniMod (4)Один из автоматов – AL А.А. ШалытоАвтоматное программированиеДвижение за открытую проектную документациюТри задачи:Повышается качество обучения – обучение А.А. ШалытоАвтоматное программированиеПримеры. Игра «Космонавт» (1) А.А. ШалытоАвтоматное программированиеПримеры. Игра «Космонавт» (2) А.А. ШалытоАвтоматное программированиеПримеры. Игра «Космонавт» (3) А.А. ШалытоАвтоматное программированиеПримеры. Игра «Космонавт» (4) А.А. ШалытоАвтоматное программированиеПримеры. Игра «Lines» (1) А.А. ШалытоАвтоматное программированиеПримеры. Игра «Lines» (2)Управление игройУправление клеткой А.А. ШалытоАвтоматное программированиеНовые направления в автоматном программированииВ рамках Федеральной целевой программы «Исследования А.А. ШалытоАвтоматное программированиеГенерация автоматов и генетическое программированиеОсновная сложность в автоматном программировании – А.А. ШалытоАвтоматное программированиеТри рассматриваемые задачи«Простая» задача – задача об «Умном муравье»«Сложная» задача А.А. ШалытоАвтоматное программирование«Простая» задача – задача об «Умном муравье»Тор – 32x3289 клеток А.А. ШалытоАвтоматное программированиеЭвристическое построение задачу не решаетПять состояний, за 200 ходов съедается А.А. ШалытоАвтоматное программированиеРешение «простой» задачиИзвестные подходы – кодирование битовыми строками + генетический А.А. ШалытоАвтоматное программирование«Сложная» задача – задача «Беспилотные летательные объекты»Соревнование на дальность полетаДве А.А. ШалытоАвтоматное программированиеРешение (1)Система управления = нейронная сеть + конечный автоматНейронная сеть А.А. ШалытоАвтоматное программированиеРешение (2)Особь = две системы управления беспилотным объектомОсобь из двух А.А. ШалытоАвтоматное программированиеРешение (3)Мутация особиМутация системы управления летательным объектомМутация нейронной сетиМутация элемента А.А. ШалытоАвтоматное программированиеРезультаты применения генетического программированияЗа сутки была построена управляющая система, содержащая А.А. ШалытоАвтоматное программированиеЗадача: налить как можно больше бутылок за заданный промежуток времени«Народная» задача – «Разливочная линия» А.А. ШалытоАвтоматное программированиеРешения «народной» задачи    Построен вручную		 Построен автоматически А.А. ШалытоАвтоматное программированиеТри традиционных подхода к верификации программТестирование – ничего не доказываетДоказательства А.А. ШалытоАвтоматное программированиеНедостатки Model Checking для программ общего видаНе ясно, как построить А.А. ШалытоАвтоматное программированиеВерификация автоматных программТак как поведение автоматных программ задается графами переходов А.А. ШалытоАвтоматное программированиеПовышение качества программного обеспеченияNASA (Открытые системы #03/2004)Использование состоянийГенерация программ с А.А. ШалытоАвтоматное программированиеНадеждаЕсть области, в которых верификация необходима: авиация, управление ядерными реакторамиАвтор А.А. ШалытоАвтоматное программированиеСпасибо за внимание!Спасибо за внимание!
Слайды презентации

Слайд 2 А.А. Шалыто
Автоматное программирование
Автоматное программирование
Предложено мною в 1991 году
Программные

А.А. ШалытоАвтоматное программированиеАвтоматное программированиеПредложено мною в 1991 годуПрограммные системы предлагается разрабатывать

системы предлагается разрабатывать так же, как выполняется автоматизация технологических

(и не только) процессов
Система управления является системой взаимодействующих конечных автоматов

Состояния
События и входные переменные
Выходные воздействия
Конечный автомат
Система конечных автоматов


Слайд 3 А.А. Шалыто
Автоматное программирование
Автоматное программирование
Система управления
Машина Тьюринга

А.А. ШалытоАвтоматное программированиеАвтоматное программированиеСистема управленияМашина Тьюринга

Слайд 4 А.А. Шалыто
Автоматное программирование
Как строить программы?
Поставщики
событий
Система
конечных
автоматов
Объекты

А.А. ШалытоАвтоматное программированиеКак строить программы?Поставщики событийСистема конечных автоматовОбъекты управленияОбратная связь

управления
Обратная связь


Слайд 5 А.А. Шалыто
Автоматное программирование
Преимущества
Обладает наибольшей эффективностью для систем со

А.А. ШалытоАвтоматное программированиеПреимуществаОбладает наибольшей эффективностью для систем со сложным поведениемФормальное и

сложным поведением
Формальное и понятное описание поведения
Автоматическая генерация кода по

диаграммам переходов
Возможность верификации программ
Проектная документация

Слайд 6 А.А. Шалыто
Автоматное программирование
Применение
«Железо»
Микропроцессоры
Микроконтроллеры
Программируемые логические контроллеры
Парадигмы
Процедурная
Объектно-ориентированная
Языки контроллеров
Лестничные схемы
Функциональные схемы
Программное

А.А. ШалытоАвтоматное программированиеПрименение«Железо»МикропроцессорыМикроконтроллерыПрограммируемые логические контроллерыПарадигмыПроцедурнаяОбъектно-ориентированнаяЯзыки контроллеровЛестничные схемыФункциональные схемыПрограммное обеспечениеСистемы высокой надежностиВоенные приложенияАэрокосмическая индустрияВстроенные системыМобильные системыВизуализаторыWeb-приложенияКлиент-сервер приложения

обеспечение
Системы высокой надежности
Военные приложения
Аэрокосмическая индустрия
Встроенные системы
Мобильные системы
Визуализаторы
Web-приложения
Клиент-сервер приложения


Слайд 7 А.А. Шалыто
Автоматное программирование
Инструментальное средство UniMod (1)
Инструментальное средство для

А.А. ШалытоАвтоматное программированиеИнструментальное средство UniMod (1)Инструментальное средство для поддержки автоматного программированияСоздано

поддержки автоматного программирования
Создано в рамках ФЦНТП «Исследования и разработки по приоритетным направлениям

развития науки и техники» на 2002-2006 годы по приоритетному направлению «Информационно-телекоммуникационные системы»
Критическая технология – «Технология производства программного обеспечения»
Вошел в число 15 наиболее инновационно перспективных и социально значимых проектов Федерального агентства по науке и инновациям

Слайд 8 А.А. Шалыто
Автоматное программирование
Инструментальное средство UniMod (2)
Локальная и удаленная

А.А. ШалытоАвтоматное программированиеИнструментальное средство UniMod (2)Локальная и удаленная отладка диаграмм в

отладка диаграмм в терминах состояний
Проверка формальных свойств диаграмм
Интерпретируемый и

компилируемый подходы
Запись автоматов в нотации UML-диаграмм классов и состояний
Встраиваемый редактор UML-диаграмм для платформы Eclipse
Запуск диаграмм в «одно нажатие»

Слайд 9 А.А. Шалыто
Автоматное программирование
Инструментальное средство UniMod (3)
Семь автоматов

А.А. ШалытоАвтоматное программированиеИнструментальное средство UniMod (3)Семь автоматов      Вручную	Автоматическая генерация	 Вручную


Вручную Автоматическая генерация Вручную

Слайд 10 А.А. Шалыто
Автоматное программирование
Инструментальное средство UniMod (4)
Один из автоматов

А.А. ШалытоАвтоматное программированиеИнструментальное средство UniMod (4)Один из автоматов – AL

– AL


Слайд 11 А.А. Шалыто
Автоматное программирование
Движение за открытую проектную документацию
Три задачи:
Повышается

А.А. ШалытоАвтоматное программированиеДвижение за открытую проектную документациюТри задачи:Повышается качество обучения –

качество обучения – обучение на проектах
Создаются предпосылки для научной

работы и отбор «ученых»
Совершенствуется технология автоматного программирования
Создано более 100 студенческих проектов, содержащих не только программную часть, но и открытую проектную документацию
Из них – 15 UniMod-проектов
Проекты опубликованы на сайте http://is.ifmo.ru

Слайд 12 А.А. Шалыто
Автоматное программирование
Примеры. Игра «Космонавт» (1)

А.А. ШалытоАвтоматное программированиеПримеры. Игра «Космонавт» (1)

Слайд 13 А.А. Шалыто
Автоматное программирование
Примеры. Игра «Космонавт» (2)

А.А. ШалытоАвтоматное программированиеПримеры. Игра «Космонавт» (2)

Слайд 14 А.А. Шалыто
Автоматное программирование
Примеры. Игра «Космонавт» (3)

А.А. ШалытоАвтоматное программированиеПримеры. Игра «Космонавт» (3)

Слайд 15 А.А. Шалыто
Автоматное программирование
Примеры. Игра «Космонавт» (4)

А.А. ШалытоАвтоматное программированиеПримеры. Игра «Космонавт» (4)

Слайд 16 А.А. Шалыто
Автоматное программирование
Примеры. Игра «Lines» (1)

А.А. ШалытоАвтоматное программированиеПримеры. Игра «Lines» (1)

Слайд 17 А.А. Шалыто
Автоматное программирование
Примеры. Игра «Lines» (2)
Управление игрой
Управление клеткой

А.А. ШалытоАвтоматное программированиеПримеры. Игра «Lines» (2)Управление игройУправление клеткой

Слайд 18 А.А. Шалыто
Автоматное программирование
Новые направления в автоматном программировании
В рамках

А.А. ШалытоАвтоматное программированиеНовые направления в автоматном программированииВ рамках Федеральной целевой программы

Федеральной целевой программы «Исследования и разработки по приоритетным направлениям

развития научно-технологического комплекса России на 2007–2012 годы»
Технология генетического программирования для генерации автоматов управления системами со сложным поведением (шифр «2007-4-1.4-18-01-033»)
Разработка технологии верификации управляющих программ со сложным поведением, построенных на основе автоматного подхода (шифр «2007-4-1.4-18-02-041)

Слайд 19 А.А. Шалыто
Автоматное программирование
Генерация автоматов и генетическое программирование
Основная сложность

А.А. ШалытоАвтоматное программированиеГенерация автоматов и генетическое программированиеОсновная сложность в автоматном программировании

в автоматном программировании – построение автоматов
В большинстве случаев автоматы

проектируются вручную
Однако эвристическое построение автоматов часто затруднено или невозможно
Решение – автоматическое построение конечных автоматов с помощью генетического программирования
Это позволит повысить уровень автоматизации построения программ рассматриваемого класса
Материалы – на сайте http://is.ifmo.ru (раздел «Генетические алгоритмы»)

Слайд 20 А.А. Шалыто
Автоматное программирование
Три рассматриваемые задачи
«Простая» задача – задача

А.А. ШалытоАвтоматное программированиеТри рассматриваемые задачи«Простая» задача – задача об «Умном муравье»«Сложная»

об «Умном муравье»
«Сложная» задача – задача «Беспилотные летательные объекты»
«Народная»

задача – «Разливочная линия»

Слайд 21 А.А. Шалыто
Автоматное программирование
«Простая» задача – задача об «Умном

А.А. ШалытоАвтоматное программирование«Простая» задача – задача об «Умном муравье»Тор – 32x3289

муравье»
Тор – 32x32
89 клеток с едой
200 ходов
Расположение еды и

начальная позиция муравья фиксированы
Цель – создать муравья, который съест всю еду
Муравей = конечный автомат

Слайд 22 А.А. Шалыто
Автоматное программирование
Эвристическое построение задачу не решает
Пять состояний,

А.А. ШалытоАвтоматное программированиеЭвристическое построение задачу не решаетПять состояний, за 200 ходов

за 200 ходов съедается 81 единица еды или все

89 единиц еды за 314 ходов


Слайд 23 А.А. Шалыто
Автоматное программирование
Решение «простой» задачи
Известные подходы – кодирование

А.А. ШалытоАвтоматное программированиеРешение «простой» задачиИзвестные подходы – кодирование битовыми строками +

битовыми строками + генетический алгоритм
Известные решения:
13 состояний (1992)
11 состояний

(1993)
8 состояний (1999)
Предлагаемый подход – генетическое программирование
Построены два автомата с 7 состояниями после генерации 160 и 250 млн. автоматов
Полный перебор ~3·1018 автоматов

Слайд 24 А.А. Шалыто
Автоматное программирование
«Сложная» задача – задача «Беспилотные летательные

А.А. ШалытоАвтоматное программирование«Сложная» задача – задача «Беспилотные летательные объекты»Соревнование на дальность

объекты»
Соревнование на дальность полета
Две команды по восемь объектов
Ограничения: запас

топлива, столкновения, аэродинамическое взаимодействие
Цель – разработка управляющей программы
Задача заочного тура VI Открытой Всесибирской олимпиады по программированию (2005 год)
Была решена при участии автора путем эвристического построения автоматов http://is.ifmo.ru/unimod-projects/plates/

Слайд 25 А.А. Шалыто
Автоматное программирование
Решение (1)
Система управления = нейронная сеть

А.А. ШалытоАвтоматное программированиеРешение (1)Система управления = нейронная сеть + конечный автоматНейронная

+ конечный автомат
Нейронная сеть преобразует вещественные входные переменные в

логические



Слайд 26 А.А. Шалыто
Автоматное программирование
Решение (2)
Особь = две системы управления

А.А. ШалытоАвтоматное программированиеРешение (2)Особь = две системы управления беспилотным объектомОсобь из

беспилотным объектом
Особь из двух систем – для учета взаимодействия

объектов

Слайд 27 А.А. Шалыто
Автоматное программирование
Решение (3)
Мутация особи
Мутация системы управления летательным

А.А. ШалытоАвтоматное программированиеРешение (3)Мутация особиМутация системы управления летательным объектомМутация нейронной сетиМутация

объектом
Мутация нейронной сети
Мутация элемента сети
Мутация конечного автомата
Изменение начального состояния
Мутация

перехода
Скрещивание особей
Скрещивание систем управления летающей тарелкой
Скрещивание автоматов
Скрещивание нейронных сетей


Слайд 28 А.А. Шалыто
Автоматное программирование
Результаты применения генетического программирования
За сутки была

А.А. ШалытоАвтоматное программированиеРезультаты применения генетического программированияЗа сутки была построена управляющая система,

построена управляющая система, содержащая нейронную сеть и один автомат

с шестью состояниями (вместо семи автоматов с 21 состоянием)

Слайд 29 А.А. Шалыто
Автоматное программирование
Задача: налить как можно больше бутылок

А.А. ШалытоАвтоматное программированиеЗадача: налить как можно больше бутылок за заданный промежуток времени«Народная» задача – «Разливочная линия»

за заданный промежуток времени
«Народная» задача – «Разливочная линия»


Слайд 30 А.А. Шалыто
Автоматное программирование
Решения «народной» задачи

А.А. ШалытоАвтоматное программированиеРешения «народной» задачи  Построен вручную		 Построен автоматически

Построен вручную Построен автоматически


Слайд 31 А.А. Шалыто
Автоматное программирование
Три традиционных подхода к верификации программ
Тестирование

А.А. ШалытоАвтоматное программированиеТри традиционных подхода к верификации программТестирование – ничего не

– ничего не доказывает
Доказательства теорем – все доказывает, но

практически нигде не используется
Верификация на моделях – Model Checking (модель программы с конечным числом состояний и свойства программы в темпоральной логике)


Слайд 32 А.А. Шалыто
Автоматное программирование
Недостатки Model Checking для программ общего

А.А. ШалытоАвтоматное программированиеНедостатки Model Checking для программ общего видаНе ясно, как

вида
Не ясно, как построить модель
Не ясно, как записать темпоральные

свойства
Не ясно, как перейти от модели к реальной программе в случае обнаружения ошибки




Слайд 33 А.А. Шалыто
Автоматное программирование
Верификация автоматных программ
Так как поведение автоматных

А.А. ШалытоАвтоматное программированиеВерификация автоматных программТак как поведение автоматных программ задается графами

программ задается графами переходов конечных автоматов, то все три

указанные проблемы для этого класса программ эффективно решаются
Работы проводятся совместно с кафедрой «Теоретическая информатика» Ярославского государственного университета им. П.Г. Демидова
Материалы – на сайте http://is.ifmo.ru (раздел «Верификация»)

Слайд 34 А.А. Шалыто
Автоматное программирование
Повышение качества программного обеспечения
NASA (Открытые системы

А.А. ШалытоАвтоматное программированиеПовышение качества программного обеспеченияNASA (Открытые системы #03/2004)Использование состоянийГенерация программ

#03/2004)
Использование состояний
Генерация программ с помощью инструментального средства Stateflow
Верификатор SPIN
СПбГУ

ИТМО http://is.ifmo.ru
Использование состояний
Генерация программ с помощью инструментального средства UniMod
Верификаторы SPIN и Bogor

Слайд 35 А.А. Шалыто
Автоматное программирование
Надежда
Есть области, в которых верификация необходима:

А.А. ШалытоАвтоматное программированиеНадеждаЕсть области, в которых верификация необходима: авиация, управление ядерными

авиация, управление ядерными реакторами
Автор надеется, что в этих областях

заказчики могут заставить программировать автоматно, если они поймут, что только такие программы можно формально верифицировать

  • Имя файла: avtomatnoe-programmirovanie.pptx
  • Количество просмотров: 115
  • Количество скачиваний: 0