Лекция 1 Ф. Н. Царев >08. 09. 2009




НазваниеЛекция 1 Ф. Н. Царев >08. 09. 2009
Дата конвертации31.01.2013
Размер445 b.
ТипЛекция


Теория автоматов в программировании

  • Лекция 1

  • Ф. Н. Царев

  • 08.09.2009


План курса

  • Основные понятия автоматного программирования

  • Инструментальные средства автоматного программирования

  • Применение генетических алгоритмов

  • Верификация автоматных программ

  • Текстовые языки автоматного программирования



Преподаватели курса

  • Шалыто А. А.

  • Царев Ф. Н.



Место и время проведения занятий

  • Пятница, 17-20

  • Аудитория 218, 219 или 146



Как получить зачет?

  • 5 семестр

  • Сдать лабораторную работу по генетическим алгоритмам

  • Сообщить тему своей курсовой работы



Виртуальная лаборатория по ГА

  • Два варианта: Java или C#

  • Сайт is.ifmo.ru, раздел «Генетические алгоритмы», подраздел «Лабораторные работы»

  • Сдать работу = сдать программу + выложить на сайт отчет



Как сдать курсовую работу?

  • 6 семестр

  • Написать программу

  • Написать проектную документацию

  • Выложить ее на сайт is.ifmo.ru

  • Не забывать записываться в календарь Шалыто



Цель выполнения курсовой работы

  • Привести ее в такое состояние, чтобы было не стыдно выкладывать в Интернет



Материалы по курсу

  • Сайт кафедры «Технологии программирования» по автоматному программированию и мотивации к творчеству is.ifmo.ru

  • Книга Н. Поликарпова, А. Шалыто Автоматное программирование

  • Материалы лекций



1.1 Области применения автоматного программирования



1.1.1. Классификация программ по Харелу

  • Трансформирующие системы

    • некоторое преобразование входных данных
    • например: компиляторы, архиваторы
  • Интерактивные системы

    • взаимодействуют с окружающей средой в режиме диалога
    • например: текстовые редакторы
  • Реактивные системы

    • обмен со средой сообщениями, в темпе задаваемом средой
    • например: системы контроля


1.1.2. Критерии применимости

  • «Сложное поведение»

    • поведение, зависящее от состояния
    • реакция зависит от предыстории
  • «Простое поведение»

    • поведение, не зависящее от состояния
    • реакция зависит только от воздействия


Сущность с простым поведением



Пример использования: ЭЛЕКТРОННЫЕ ЧАСЫ

  • Простое поведение

    • H – увеличивает на единицу число часов
    • M – увеличивает на единицу число минут


Пример использования: ЭЛЕКТРОННЫЕ ЧАСЫ

  • Сложное поведение

    • H – увеличивает на единицу число часов
    • M – увеличивает на единицу число минут
    • A – включает и выключает настройку «будильник»


1.1.3. Идеи автоматного программирования:

  • отделение логики от семантики

  • описание логики при автоматном подходе строго структурировано



1.1.4. Рекомендации при использовании автоматного подхода

  • используйте автоматный подход при создании любой программной системы, в которой есть сущности со сложным поведением

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



1.2. Основные понятия автоматного программирования



1.2.1. Основные понятия

  • Состояние

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


1.2.1. Основные понятия

  • Свойства состояния системы:

    • текущее состояние несет в себе всю информацию о прошлом системы, необходимую для определения ее реакции на любое входное воздействие, формируемое в момент времени t 0
    • не требуется знание предыстории


1.2.1. Основные понятия

  • Входное воздействие

    • это вектор, составляющие которого - события и входные переменные
  • Функция переходов

    • правила, по которым происходит смена состояний
  • Выходное воздействие



1.2.1. Основные понятия

  • Функция выходов

    • правила формирования выходных воздействий
  • Автомат без выходов (конечный)

    • совокупность конечного множества состояний и конечного множества входных воздействий


1.2.2. Конечный автомат



1.3. Парадигма автоматного программирования



Тезис Тьюринга-Черча

  • Все, что можно «вычислить», «запрограммировать» или «распознать» в любом смысле (из формально определенных в настоящее время) можно вычислить, запрограммировать или распознать с помощью подходящей машины Тьюринга



1.3.1. Машина Тьюринга

  • Машина Тьюринга

  • состоит из 2-х частей:

  • Устройство управления

  • Запоминающее устройство - лента



1.3.1. Машина Тьюринга

  • Устройство управления представляет собой конечный автомат

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


1.3.2. Программирование на Машине Тьюринга

  • Реализация функции инкремент:

    • двигаться вправо, пока не встретится пустой символ
    • сдвинуться на одну ячейку влево
    • пока в текущей ячейке находится '1', заменять его на '0' и двигаться влево
    • если в текущей ячейке находится '0' или 'blank', записать в ячейку '1' и завершить работу


1.3.3. Краткое описание поведение машины

  • Граф переходов, где:

    • вершины - состояния автомата
    • дуги – переходы между состояниями


1.3.4. Выводы по работе машины Тьюринга

  • Для того, чтобы задать алгоритм для машины Тьюринга, достаточно описать ее поведение в каждом из трех состояний управляющего автомата

  • Состояния управляющего автомата определяют действия машины, а состояние ленты – результат этих действий



1.3.4. Выводы по работе машины Тьюринга

  • Состояния устройства управления

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

    • в программе в явном виде не участвуют, построить граф переходов между ними невозможно
    • количественные состояния машины
    • называют вычислительными


1.3.5. Управляющие и вычислительные состояния

  • Управляющие состояния

  • Их относительно немного

  • Каждое из них имеет вполне определенный смысл и качественно отличается от других

  • Они определяют действия, которые совершает сущность



1.3.5. Управляющие и вычислительные состояния

  • Вычислительные состояния

  • Их количество либо бесконечно, либо конечно, но очень велико

  • Большинство из них не имеет смысла и отличается от остальных лишь количественно

  • Они непосредственно определяют лишь результаты действий



1.3.6. Сущность со сложным поведением

  • Управляющая часть

    • управляющий автомат
    • отвечает за логику поведения – выбор выполняемых действий, зависящий от текущего состояния и входных воздействий, а также за переход в новое состояние


1.3.6. Сущность со сложным поведением

  • Управляемая часть

    • объект управления
    • отвечает за выполнение действий, выбранных для выполнения управляющей частью, и, возможно, за формирование некоторых компонентов входных воздействий для управляющей части – обратных связей


1.3.6. Сущность со сложным поведением

  • Парадигма автоматного программирования состоит в представлении сущностей со сложным поведением в виде автоматизированных объектов управления

  • Автоматизированный объект управления - объект управления, интегрированный вместе с системой управления в одно устройство



Спасибо за внимание

  • Следующий раз – в пятницу, 11 сентября в 17-20

  • А. А. Шалыто



Похожие:

Лекция 1 Ф. Н. Царев >08. 09. 2009 iconЦарев Ф. Н., Шалыто А. А. IV международная научно-практическая конференция
Применение генетического программирования для генерации автомата в задаче об «Умном муравье»
Лекция 1 Ф. Н. Царев >08. 09. 2009 iconРуководитель проекта – А. А. Шалыто Докладчик – Ф. Н. Царев
Разработка технологии генетического программирования для генерации автоматов управления системами со сложным поведением
Лекция 1 Ф. Н. Царев >08. 09. 2009 iconЛекция 1 Основные понятия и определения теоретической механики Лекция 2 Виды связей и реакции связей Лекция 3 Момент силы относительно точки Лекция 4 Кинематика точки
Теоретическая механика это наука о наиболее общих законах механиче­ского движения и равновесия материальных объектов
Лекция 1 Ф. Н. Царев >08. 09. 2009 iconПлан работы школы на 2008-2009 учебный год
С 29 октября 2008г по 4 ноября 2008 г. 7 дней с 29 декабря 2008 г по 11 января 2009 г. 14 дней с 23 марта 2009 г по 31 марта 2009...
Лекция 1 Ф. Н. Царев >08. 09. 2009 iconЛекция на тему: "Идиопатические заболевания с прогрессирующим лизисом тканей пародонта. Клиника, диагностика, лечение" Лектор професор Каськова Л. Ф. Полтава 2009
Украины «Украинская медицинская стоматологическая академия» Кафедра детской терапевтической стоматологии с профилактикой стоматологических...
Лекция 1 Ф. Н. Царев >08. 09. 2009 iconВоспитание способности к духовному развитию, нравственному самосовершенствованию
Федерации от 2 августа 2009 г. (Пр-2009 вп-п44-4632) и распоряжение Председателя Правительства Российской Федерации от 11 августа...
Лекция 1 Ф. Н. Царев >08. 09. 2009 iconЛекция Лекция 1
Мир, окружающий нас материален: он состоит из вечно существующей и непрерывно движущейся материи
Лекция 1 Ф. Н. Царев >08. 09. 2009 iconЛекция Лекция Семинар Психологическая консультация Научная конференция Деловая игра Тренинг личностного роста

Лекция 1 Ф. Н. Царев >08. 09. 2009 iconЛекция 9 Пять механизмов нарушения
Гештальт терапия Перлза «Человек находится в равновесии с самим собой и окружающим его миром» Лекция 9
Лекция 1 Ф. Н. Царев >08. 09. 2009 icon«Определение качественной упаковки молочных продуктов.» (2008-2009 уч г) «Определение качественной упаковки молочных продуктов.» (2008-2009 уч г)
«Химический анализ сказки Николая Носова «Приключения Незнайки и его друзей» (2009-2010 уч г.)
Разместите кнопку на своём сайте:
hnu.docdat.com


База данных защищена авторским правом ©hnu.docdat.com 2012
обратиться к администрации
hnu.docdat.com
Главная страница