Основные положения теории автоматов. До 20 минут

ЛЕКЦИИ

По дисциплине 1425 «Теория автоматов»

Для студентов 2 курса факультета ИТ

Специальности 230101

«Вычислительные машины, комплексы, системы и сети»

Обсуждены на заседании кафедры

«___»________________2007г.

Протокол № _____

Москва 2007

Общие положения

Цели и задачи дисциплины

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

Требования к уровню освоения содержания дисциплины

Знания, приобретенные в результате освоения дисциплины:

§ Принципы и основные понятия теории автоматов;

§ Применение теории автоматов для построения трансляторов алгоритмических языков;

§ Применение теории автоматов при разработке устройств и дискретной аппаратуры в рамках персональных ЭВМ;

Умения и навыки, приобретенные в результате освоения дисциплины:

§ Применение теории автоматов для решения прикладных задач;

§ Проектирование дискретных устройств;

§ Проектирование трансляторов;

Рекомендуемая литература

Основная литература

1. Савельев А.Я. Основы информатики: учебник для вузов.-М.:Издательство МГТУ им. Н.Баумана,2001.-328с.

2. Карпов Ю.Г.Теория автоматов:СПб.:Питер,2003.-224 с.:ил.

3. Зайцев Е.И. Теория автоматов: Учебное пособие.-М.:МГАПИ,2002.-59с.

Дополнительная литература

1. Хопкрофт Д., Мотвани Р., Введение в теорию автоматов, языков и вычислений: пер с англ.-М.:Издат. Дом Вильямс,2002.-528с.

2.

Лекция №1.

Основные понятия и определения

Продолжительность: 2 часа (90) минут

Ключевые (основные) вопросы (моменты)

-Место дисциплины «Теория автоматов» в ряду дисциплин, читаемых на кафедре

-Объекты Теории автоматов

-Задачи Теории автоматов

- Основные понятия и определения.

Текст лекции

ТЕОРИЯ АВТОМАТОВ.

Основные положения теории автоматов. До 20 минут

Автомат (от греческого automat oz - самодействующий) - управляющая система, являющаяся конечным автоматом или некоторой его модификацией, полученной путем изменения его компонент или функционирования. Основное понятие - конечный автомат - возникло в середине 20 века в связи с попытками описать на математическом языке функционирование нервных систем, универсальных вычислительных машин и других реальных автоматов. Характерной особенностью такого описания является дискретность соответствующих математических моделей и конечность областей значений их параметров, что приводит к понятию конечного автомата.

Теория автоматов - это раздел теории управляющих систем, изучающий математические модели преобразователей дискретной информации, называемые автоматами. С определенной точки зрения такими преобразователями являются как реальные устройства (вычислительные машины, автоматы, живые организмы и т.д.), так и абстрактные системы (например, формальная система, аксиоматические теории и т.д.). Наиболее тесно теория автоматов связана с теорией алгоритмов.

Большинство задач теории автоматов - общие для основных видов управляющих систем. К ним относятся задачи анализа и синтеза автоматов, задачи полноты, минимизации, эквивалентных преобразований автоматов и другие. Задача анализа состоит в том, чтобы по заданному автомату описать его поведение или по неполным данным об автомате и его функционированию установить те или иные его свойства. Задача синтеза автоматов состоит в построении автомата с наперед заданным поведением или функционированием. Задача полноты состоит в выяснении, обладает ли множество M' Í M автоматов свойством полноты, т.е. совпадает ли с M множество всех автоматов, которые получаются путем конечного числа применений некоторых операций к автоматам из заданного подмножества автоматов M'. Задача эквивалентных преобразований в общем виде состоит в том, чтобы найти систему правил преобразований (так называемую полную систему правил) автоматов, которые удовлетворяют определенным условиям и позволяют преобразовать произвольный автомат в любой эквивалентный ему автомат (два автомата эквивалентны, если они имеют одинаковое поведение автомата. Поведение автомата - математическое понятие, описывающее взаимодействие автомата с внешней средой. Примером внешней среды конечного автомата является множество входных слов, а поведением - словарная функция, реализуемая автоматом, или событие, представимое автоматом.)

Помимо перечисленных, в теории автоматов имеются специфические проблемы, характерные для автоматов. Так, в зависимости от условий задачи поведение автомата удобно задавать на разных языках, в связи с чем важными задачами являются выбор достаточно удобного адекватного языка и перевод с одного языка на другой. В тесной связи с задачами синтеза и эквивалентных преобразований находится задача минимизации числа состояний автомата, а также получение соответствующих оценок. Близкий круг вопросов возникает в связи с моделированием поведения автоматов одного класса автоматами другого класса. Здесь также представляют интерес вопросы минимизации моделирующих автоматов и оценки их сложности. Специальный раздел теории автоматов связан с так называемыми экспериментами с автоматами (т.е. способами получения информации о внутренней структуре автоматов по их поведению). Основная задача здесь состоит в том, чтобы получить определенные сведения о строении автомата путем наблюдения его реакции на те или иные внешние воздействия. При этом возникает большой круг задач, связанный с классификацией экспериментов и с вопросами разрешимости задач определенными видами экспериментов, а также с оценками длин минимальных экспериментов, достаточных для решения тех или иных задач. Понятие эксперимента с автоматами используется также в задачах надежности и контроля управляющих систем, в частности контроля автоматов. Многие из перечисленных выше задач могут рассматриваться как алгоритмические проблемы. Для конечных автоматов большинство из них имеют положительное решение.

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

Дата добавления: 2015-12-01