Главная » Файлы » Лекции » Другое [ Добавить материал ]

Краткие лекции по теории автоматов

[Скачать с сервера (452.1Kb) - бесплатно] 21.05.2011, 18:38

Отличный краткий конспект лекций по предмету "теория автоматов" в Pdf-файле.

Содержание лекции

Синтез цифровых автоматов для реализации алгоритмов двоичной арифметики

  • Общие сведения о цифровых автоматах. Модель Глушкова. Синтез операционных автоматов
  • Пример синтеза операционного автомата для выполнения косвенного умножения беззнаковых чисел
  • Виды управляющих автоматов. Структуры автоматов Мили и Мура.
  • Пример синтеза управляющего автомата с жесткой логикой (УАЖЛ) для алгоритма умножения беззнаковых чисел в прямом коде
Вопросы из первого раздела для самоконтроля:
  • Опишите модель дикретного преобразователя Глушкова.
  • Каково назначение Операционного Автомата (ОА) ?
  • Роль информационных и управляющих сигналов.
  • Перечислите этапы синтеза ОА процедурного типа канонической структуры.
  • Проведите синтез ОА для выполнения умножения (используйте упрощенный
  • алгоритм косвенного умножения беззнаковых чисел).
  • Приведите пример умножения чисел по алгоритму косвенного умножения.
  • Опишите основные варианты (схемы) косвенного умножения.
  • Постройте временную диаграмму ОА для умножения. Поясните ее.
  • Синтезируйте алгоритм выполнения арифметической операции по вариантам.
  • Синтезируйте схему ОА по вашему алгоритму.
  • Каково назначение Управляющего Автомата (УА) ?
  • Роль информационных и управляющих сигналов.
  • Типы УА.
  • Перечислите этапы синтеза УА с жесткой логикой.
  • Опишите основные триггеры как элементарные конечные автоматы.
  • Каковы особенности синтеза УАЖЛ на разных типах триггеров ?
  • Приведите структурные схемы автоматов Мили и Мура. В чем их отличия ?
  • Опишите модели абстрактных автоматов Мили и Мура.
  • Какие формы описания абстрактных конечных автоматов Вы знаете ?
  • Постройте таблицы переходов / выходов и графы автоматов по схеме
  • алгоритма.
  • Проведите синтез УА для реализации алгоритма умножения (используйте
  • упрощенный алгоритм косвенного умножения беззнаковых чисел) как
  • автомат Мили / Мура.
  • Постройте временную диаграмму УА для умножения. Поясните ее.
  • Синтезируйте схему УАЖЛ для вашего алгоритма по вариантам.

Использование регулярных выражений (РВ). Программная реализация автоматов

  • Понятие о регулярных выражениях и автоматах-распознавателях
  • Краткие сведения о регулярных выражениях (РВ). Диалекты РВ.
  • Применение РВ в программировании
  • Пример формирования регулярного выражения
  • Пример работы с регулярным выражением для контроля вводимых пользователем IP адресов.
  • Синтез детерминированного автомата для распознавания языка, задаваемого регулярным выражением, и его программная реализация.
  • Преобразование РВ в НКА с ε – переходами
  • Преобразование НКА с ε-переходами в НКА без ε-переходов
  • Получение ДКА по НКА без ε-переходов
  • Минимизация ДКА
  • Получение РВ по КА
  • Программная реализация ДКА-распознавателя
Вопросы из первого раздела для самоконтроля:
  • Что такое регулярное выражение ?
  • Где используются РВ ?
  • Какие Вы знаете способы задания РВ ?
  • С помощью каких автоматов распознаются языки, задаваемые РВ ?
  • Что такое НКА ? ДКА ?
  • Как построить по РВ КА – распознаватель ?
  • Как построить по РВ ДКА – распознаватель ?
  • Как устранить e-переходы в КА ?
  • Как минимизировать КА – распознаватель ?
  • Как используются РВ в среде VS ?
  • Как РВ поддерживаются в .NET Framework ?
  • Опишите заданные цепочки с помощью РВ.
  • Какие цепочки задает данное РВ (примеры, характеристика).
  • Стратегии реализации поддержки РВ в программных системах.
  • Способы использования поддержки РВ при составлении программ обработки текстов.
  • Какие задачи обработки текстов решаются с помощью РВ ?
  • Перечислите известные Вам программные системы, поддерживающие РВ.
Похожие материалы:

Добавил: COBA (21.05.2011) | Категория: Другое
Просмотров: 6485 | Загрузок: 1171 | Рейтинг: 5.0/1 |
Теги: Краткий, теория автоматов, лекции
Комментарии (0)

Имя *:
Email *:
Код *: