Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
В январе-сентябре 2011 года социально-экономическое развитие Чувашии характеризовалось ростом объемов промышленного производства (114,1%), производст...полностью>>
'Реферат'
Учитывая природные, социальные условия мира, в котором мы живем, физкультурно-оздоровительная работа должна стать неотъемлемой частью деятельности до...полностью>>
'Автореферат диссертации'
Защита состоится «29» апреля 2010 г. в 12.00 часов на заседании диссертационного совета Д.850.013.01 при Московском городском психолого-педагогическо...полностью>>
'Программа'
Основной целью дисциплины является формирование у студентов четкого представления о сущности и роли финансового рынка в экономическом развитии общест...полностью>>

Теория автоматов (2)

Главная > Лекции
Сохрани ссылку в одной из сетей:

Министерство образования Российской Федерации

Санкт-Петербургский государственный электротехнический

университет “ЛЭТИ”

РАБОЧАЯ ПРОГРАММА

дисциплины

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

Для подготовки дипломированных специалистов по направлению

654600 – “Информатика и вычислительная техникапо специальности

220100 – “Вычислительные машины, комплексы, системы и сети

Санкт-Петербург

2002

Санкт-Петербургский государственный электротехнический

университет “ЛЭТИ”

“УТВЕРЖДАЮ”

Проректор по учебной работе

проф. ___________ Ушаков В.Н.

“_____”_______________2002 г.

РАБОЧАЯ ПРОГРАММА

дисциплины

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

Для подготовки дипломированных специалистов по направлению

654600 – “Информатика и вычислительная техника” по специальности

220100 – “Вычислительные машины, комплексы, системы и сети

Факультет компьютерных технологий и информатики

Кафедра вычислительной техники

Курс 3

Семестр 5

Лекции

80 ч.

Экзамен

семестр

5

Курсовое проектирование

16 ч.

Аудиторные занятия

96 ч.

Самостоятельные занятия

70 ч.

Всего часов

166 ч.

2002

Рабочая программа обсуждена на заседании кафедры Вычислительной техники “____”_______________2002г., протокол №______.

Рабочая программа согласована с рабочими программами изученных ранее дисциплин:

  1. Информатика

  2. Программирование

Рабочая программа утверждена на методической комиссии факультета Компьютерных технологий и информатики “____”_____________2002г.

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

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

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

В результате изучения дисциплины студенты должны:

- знать элементы теории конечных автоматов, основные этапы абстрактного и структурного синтеза конечных автоматов, элементарную зарубежную терминологию в данной предметной области, необходимые элементы ЕСКД;

- знать элементы теории формальных грамматик;

- уметь синтезировать по заданному автоматному отображению конечный автомат в заданном структурном базисе, пользоваться стандартами ЕСКД при выполнении схем управляющих автоматов;

- уметь строить магазинный автомат, реализующий перевод;

- иметь представление об актуальных задачах теории автоматов;

- иметь представление о соответствии классов языков и моделей автоматов.

Содержание рабочей программы

Введение

Предмет дисциплины, ее объем, содержание и связь с другими дисциплинами учебного плана, значение в подготовке инженеров. Краткий исторический очерк развития теории автоматов, обзор литературы по курсу.

Тема 1. Теория абстрактных автоматов

Определение абстрактного автомата. Модели Мура и Мили. Способы задания абстрактных автоматов.

Эквивалентность автоматов. Эквивалентные преобразования автоматов Мили и Мура.

Алфавитный оператор. Автоматный оператор. Переход от алфавитного оператора к абстрактному автомату.

Обобщенная модель дискретного устройства. Задание автоматного отображения операторной схемой алгоритма. Языки операторных схем

алгоритма. Синтез абстрактного автомата по операторной схеме алгоритма.

Минимизация числа состояний полностью определенного автомата.

Отношение эквивалентности, классы эквивалентности.

Минимизация числа состояний полностью определенного автомата. Построение множества классов эквивалентности и минимального автомата.

Определение частичного автомата. Свойства частичного отображения. Преобразования частичных автоматов Мили и Мура.

Учет взаимодействия управляющего и операционного автоматов. Построение частичного автомата.

Минимизация частичных автоматов. Совместимость состояний, классы совместимости. Построение множества максимальных классов совместимости. Построение минимального замкнутого покрытия и минимального частичного автомата.

Тема 2. Теория структурных автоматов

Модель структурного автомата. Структурный базис. Типы триггеров.

Канонический метод структурного синтеза конечного автомата.

Асинхронные автоматы. Гонки в автоматах. Устойчивость структурного автомата. Противогоночное кодирование.

Методы кодирования, ориентированные на упрощение автомата. Кодирование, учитывающее частоту переходов. Унитарное кодирование. Кодирование, использующее понятие "соседства" состояний. Кодирование минимизирующее число переключений элементов памяти.

Структурные методы обеспечения устойчивости структурного автомата. Одноступенчатые синхронизируемые триггеры. "Двойная память". Двухступенчатые триггеры.

Явление риска в логических схемах. Условия возникновения риска. Построение логических схем без риска.

Построение структурных автоматов на основе ПЗУ и ПЛМ.

Тема 3. Теория формальных грамматик

Классификация формальных грамматик по Хомскому. Вывод. Язык, порождаемый грамматикой.

Задача распознавания и синтаксического анализа. Cворачивание.

Cоответствие автоматных грамматик и конечных автоматов. Недетерминированный конечный автомат. Построение автоматной грамматики для языка, допускаемого конечным автоматом.

Магазинный автомат. Язык, допускаемый магазинным автоматом. Построение магазинного автомата по заданной грамматике. Построение магазинного преобразователя выполняющего синтаксический разбор.

Заключение

Связь разделов курса. Интерпретация микропрограмм конечными автоматами. Соответствие классов языков и моделей автоматов.

Цели и содержание курсовой работы

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

Исходными данными для решения задачи синтеза являются:

1. алгоритм функционирования управляющего автомата в виде микропрограммы;

2. тип элемента памяти и система логических элементов;

3. требования к схеме автомата по стоимости и быстродействию.

Результатом курсовой работы являются функционально-логическая схема управляющего автомата и пояснительная записка к ней.

Ориентировочная трудоёмкость 32 часа.

Распределение учебных часов по темам и видам занятий

те мы

Название разделов и тем

Объем учебных часов

Лекции

Лабор.

занятия

Практ.

занятия

Аудит.

занятия

Самост

работа

Всего

Семестр

Введение

2

2

2

5

1

Теория абстрактных автоматов

20

20

14

34

5

2

Тория структурных автоматов

26

26

22

48

5

3

Теория формальных грамматик

30

30

18

48

5

Заключение

2

2

2

5

Курсовое проектирование

16

16

32

5

ИТОГО:

80

96

70

166

ЛИТЕРАТУРА

Основная
Название, библиографическое описание
Л
Кп

(р)

К-во экз. в библ. (на каф.)
Гриф
1

Синтез конечных автоматов: Учебное пособие /В.С. Дудкин,

Р.Ш. Исмаилов, А.В. Крайников; Под ред. В.Б. Смолова.-ЛЭТИ, Л., 1987.
5
5
30(0)
2

Методические указания к курсовой работе по дисциплине

'Микропрограммное управление в ЭВМ и теория автоматов'. /Сост.: В.C. Дудкин, А.В. Крайников, А.В. Плотников; ЛЭТИ. -С.-Пб., 1991.-30 с.
5
5
70(0)
Дополнительная
Название, библиографическое описание
К-во экз. в библ. (на каф.)
1
С.И. Баранов. Синтез микропрограммных автоматов (графсхемы и автоматы). -Л.: Энергия,1979.

20(0)

2

Грис Д. Конструирование компиляторов для цифровых машин.

-М.: Мир, 1975.

10(0)

Автор:

к.т.н., доц.

Дудкин В.С.

Рецензент

к.т.н., доц. кафедры МО ЭВМ

Сидоров Ю.Н.

Зав. кафедрой Вычислительной техники

д.т.н., проф

Пузанков Д.В.

Декан факультета

Компьютерных технологий и информатики

д.т.н., проф.

Герасимов И.В.

Программа согласована:

Зав. кафедрой Вычислительной техники

д.т.н., проф

Пузанков Д.В.

Зав. отделом учебной литературы

Смирнова О.Н.

Председатель методической комиссии

факультета

Компьютерных технологий и информатики

к.т.н., доц.

Чугунов Л.А.

Руководитель методического отдела,

к.т.н., доцент

Марасина Л.А.



Скачать документ

Похожие документы:

  1. Теория автоматов (1)

    Документ
    1. Понятие автомата, предпосылки его возникновения, основные определения. Синхронные и асинхронные автоматы. Примеры автоматов, описывающих сложение n-разрядных чисел (порядок от младших разрядов к старшим) и деление на фиксированное
  2. Теория автоматов и формальных языков составил доцент А. А. Мальцев

    Программа курса
    Настоящий курс ставит своей целью ознакомление обучаемых с устройством теории формальных языков, а также с основными принципами, методами и алгоритмами синтаксического анализа формальных языков (в т.
  3. Рабочая программа дисциплины «Теория автоматов и формальных языков» Направление подготовки

    Рабочая программа
    Рабочая программа основана на требованиях Федерального государственного стандарта высшего профессионального образования по направлению подготовки 231 Программная инженерия, утвержденного Приказом Минобрнауки 09.
  4. Учебно-методический комплекс дисциплины (умк-д) " Теория автоматов "

    Учебно-методический комплекс
    Содержание дисциплины из Государственного образовательного стандарта высшего профессионального образования по направлению подготовки дипломированных специалистов 552801 - "Информатика и вычислительная техника".
  5. Программа дисциплины по кафедре Вычислительной техники Теория автоматов

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

Другие похожие документы..