Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Белов А.Г. Теория автоматов - файл 1.doc


Белов А.Г. Теория автоматов
скачать (656 kb.)

Доступные файлы (1):

1.doc656kb.08.12.2011 19:12скачать

содержание
Загрузка...

1.doc

Реклама MarketGid:
Загрузка...
Министерство образования и науки Российской Федерации

Дальневосточный институт коммуникаций

(ДВИК)


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

Методические рекомендации и контрольные задания

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


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

Специальность Вычислительные машины, комплексы, системы и сети
Разработал доцент, к.т.н. А.Г.Белов

Одобрено Методическим Советом ДВИК

(Протокол МС № 01/07/04-/2007 от 12.04.2007)
Владивосток

2007
Методические рекомендации и контрольные задания по дисциплине «Теория автоматов» составлены в соответствии с требованиями Государственного образовательного стандарта высшего профессионального образования по специальности «Вычислительные машины, комплексы, системы и сети».

Одобрено Методическим Советом ДВИК (протокол МС № 01/07/04-2007 от 12.04.2007).

Председатель Совета проф., к.т.н. В.Л.Лосев

Разработал доц., к.т.н. А.Г.Белов

Рецензент проф. д.т.н. И.М.Орощук
(Тихоокеанский высший военно-морской институт им.С.О.Макарова)



^ 1. ЦЕЛЬ И ЗАДАЧИ ДИСЦИПЛИНЫ
Целью изучения дисциплины является приобретение знаний и навыков в вопросах применения теории автоматов для решения практических задач компьютерной техники.

В задачи дисциплины входит:

- математическое моделирование цифровых автоматов,

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

- анализ способов задания и принципов построения цифровых автоматов,

- освоение методов и средств синтеза цифровых аппаратов.

^ 2. ТРЕБОВАНИЯ К УРОВНЮ ОСВОЕНИЯ СОДЕРЖАНИЯ ДИСЦИПЛИНЫ
Изучение дисциплины базируется на знаниях студентами дисциплин «Дискретная математика», «Математическая логика и теория алгоритмов», «Программирование на языке высокого уровня», «Электротехника и электроника», «Информатика».
В результате теоретического изучения дисциплины студент должен:

- иметь представление о месте и роли теории автоматов, алгоритмов и языков при решении реальных задач компьютерной техники;

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

- знать элементы теории формальных языков.
В результате практического изучения дисциплины студент должен:

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

- иметь навыки синтеза и анализа конечных автоматов с комбинационными схемами и памятью.

^ 3. Объем дисциплины и виды учебной работы
Полная и сокращенная заочные формы обучения (на базе среднего (полного) общего образования и среднего профессионального образования)

Виды учебной работы

Всего часов

Распределение по курсам

1

2

3

4

5

Общая трудоемкость дисциплины

153










153




Лекции

8










8




Практические занятия



















Лабораторные занятия

6










6




Всего самостоятельная работа, в том числе:

139










139




Курсовая работа



















Контрольная работа

20










20




Рефераты

20










20




Изучение литературы

99










99




Вид итогового контроля (экзамен, зачет)

экз.










экз.





^ 4. Содержание дисциплины
4.1. Содержание программы дисциплины
Введение

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

Определение цифрового автомата. Абстрактная и структурная теория автоматов. Модель дискретного преобразователя В.М.Глушкова. Основные понятия теории автоматов: входной и выходной алфавиты, множества состояний автомата, автоматные языки. Типы и математические модели автоматов. Бесконечные и конечные автоматы.

Обобщения, модификации и подклассы конечных автоматов.

Конечные автоматы Мура и Мили (частичные конечные автоматы Мура и Мили) и их эквивалентные преобразования. Автоматы с магазинной памятью. Детерминированные и недетерминированные конечные автоматы. Автоматы без памяти. Операционные и управляющие автоматы. Микропрограммные автоматы (понятия микрооперации, микрокоманды, микропрограммы). Другие виды автоматов.

Композиции автоматов (структурные автоматы). Структурная теория автоматов и ее основные результаты.

Системы канонических уравнений и системы выходных функций автоматов.

Задачи теории автоматов: синтез, анализ, полнота, минимизация, эквивалентные преобразования. Эксперименты с автоматами.
^ Раздел 2. Формальные языки и грамматики

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

Основные понятия теории формальных языков и грамматик, классификация языков по Хомскому. Автоматы распознаватели и преобразователи. Регулярные выражения и языки. Свойства регулярных языков. Связь регулярных языков и конечных автоматов. Задача распознавания и синтаксического анализа. Контекстно-свободные грамматики и языки, их свойства. Связь абстрактных автоматов с формальными языками и грамматиками.

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

Машина Тьюринга. Техника программирования машин Тьюринга. Расширения базовой машины Тьюринга. Машины Тьюринга с ограничениями. Машины Тьюринга и компьютеры.

Назначение, характеристика, структура и способы представления сетей Петри.
^ Раздел 3. Основные понятия и законы алгебры логики

Алгебра состояний. Логические функции (ЛФ) одной и двух переменных. Контактная и бесконтактная реализация ЛФ.

Законы алгебры логики. Законы де Моргана. Обобщение Шеннона. Дизъюнктивная и конъюнктивная нормальные формы. Конституенты нуля и единицы. Совершенные дизъюнктивная и конъюнктивная нормальные формы.

Теорема разложения совершенной дизъюнктивной и совершенной конъюнктивной нормальных форм. Принцип двойственности. Суперпозиция ЛФ. Полная, максимальная и минимальная системы ЛФ.
^ Раздел 4. Синтез комбинационной схемы автомата

Этапы синтеза автоматов: системное, программно- логическое, техническое и технологическое проектирование.

Реализация комбинационной части автоматов комбинационной схемой (КС). Логические элементы и их характеристики. Функциональная схема и базис КС. Задание автоматов таблицей состояний. Использование условных состояний автоматов.

Диаграмма Вейча - карта Карно (КК). Составление КК по таблицам истинности. Свойства КК. Соседние клетки КК. Получение по КК алгебраических выражений ЛФ. Минимизация ЛФ с помощью КК. Представление КК бòльшего числа переменных через сумму КК меньшего числа переменных.

Пример синтеза КС посредством КК.
^ Раздел 5. Синтез автоматов с памятью

Абстрактный синтез автоматов: представление автоматов на стандартном языке на основе их задания на начальном языке. Минимизация автоматов, заданных на стандартном языке.

Канонический метод структурного синтеза автоматов. Теорема о структурной полноте В.М.Глушкова. Основные этапы структурного синтеза автоматов. Обобщенные структурные схемы автоматов с памятью. Представление функционирования автомата в виде прямой таблицы переходов и выходов. Проблема отражения времени при проектировании схем автоматов: синхронные, асинхронные и апериодические схемы. Кодирование внутренних состояний автомата для синхронных и асинхронных автоматов с учетом сложности КС и с учетом гонок в автоматах. Учет неиспользованных кодовых групп. Использование метода прямого кодирования и применение элементов памяти для кодирования состояний автомата. Выбор элементов памяти. Построение функций возбуждения элементов памяти и функций выходов автомата.

Пример синтеза автомата на основе таблицы переходов и КК.

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

Пример синтеза автомата по циклограмме.
Заключение

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

Минимизация ЛФ. Построение бесконтактных и релейно-контактных схем автомата.

Синтез КС автомата по заданным условиям ее функционирования.

Исследование КС на стенде-тренажере.

Стандартные способы задания автоматов с памятью.

Синтез автомата с памятью по заданному графу.

Исследование автоматов с памятью на стенде-тренажере.

Синтез автоматов по циклограмме.

Моделирование автоматов c использованием компьютерных программ Electronics Workbench v5.12 и Electronics Workbench Multisim 7.

^ 4.3. Темы рефератов (для студентов полной и сокращенной заочных форм обучения)


  1. Понятие об информации и ее преобразованиях. Преобразование алфавитной информации.

  2. Основные понятия теории формальных грамматик.

  3. Концепция порождения и распознавания. Распознающие и порождающие формальные грамматики.

  4. Способы задания автоматов.

  5. Основные понятия и определения теории абстрактных автоматов. Абстрактный синтез автомата.

  6. Структурный синтез автомата: задачи синтеза, канонический метод структурного синтеза.

  7. Элементарные автоматы с памятью (триггерные устройства) и их свойства.

  8. Кодирование внутренних состояний автомата.

  9. Методы анализа и синтеза КС.

  10. Управляющие и операционные автоматы.

  11. Способы описания алгоритмов и микропрограмм.

  12. Структурный синтез микропрограммных автоматов Мура и Мили.

  13. Гонки в автоматах и способы их устранения.


^ 4.4. Распределение часов по разделам дисциплины
4.4.1. Полная и сокращенная заочные формы обучения (на базе среднего (полного) общего и среднего профессионального образования)


Наименование раздела дисциплины

Всего

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

Самост. работа

Лекции

Лаборат.занятия

Практич. занятия

Раздел 1. Классификация и характерис-тики автоматов

30

2







28

Раздел 2. Формальные языки и грамматики

33

2

2




29

Раздел 3. Основные понятия и законы алгебры логики

30

2







28

Раздел 4. Синтез комбинационной схемы автомата

30

1

2




27

Раздел 5. Синтез автоматов с памятью

30

1

2




27

Всего

153

8

6




139



^ 5. УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ
5.1. Рекомендуемая литература
5.1.1. Основная литература:

  1. Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений. М.: Вильямс, 2002 – 528 с.(21. pdf )

  2. Карпов Ю.Г. Теория автоматов: Учебник для вузов. СПб.: Питер, 2003 – 208 с.

  3. Лазарев В.Г., Пийль Е.И. Синтез управляющих автоматов. М.: Энергоатомиздат, 1989 – 327 с.

  4. Савельев А.Я. Прикладная теория цифровых автоматов: Учебник для вузов. М.: Высшая школа, 1987 – 272 с.


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

  1. Гилл А. Введение в теорию конечных автоматов. М.: СП ЭКОМ, 1966 – 272 с.

  2. Глушков В.М., Трахтенброт Б.А. Введение в теорию конечных автоматов. М.: СП ЭКОМ, 1962 – 384 с.

  3. Глушков В.М. Синтез цифровых автоматов. М.: Физматгиз, 1962 – 476 с.

  4. Лазарев В.Г., Маркин Н.П., Лазарев Ю.В. Проектирование дискретных устройств автоматики: Учебное пособие для вузов связи. М.: Радио и связь, 1985 – 168 с.

  5. Миллер Р. Теория переключательных схем. Т. 1. Комбинационные схемы. М: Наука, 1970 – 416 с.

  6. Миллер Р. Теория переключательных схем. Т. 2. Последовательностные схемы и машины. М: Наука, 1971 – 304 с.

  7. Проектирование бесконтактных управляющих логических устройств промышленной автоматики /Грейнер Г.Р., Ильяшенко В.П., Май В.П. и др. М.: Энергия, 1977 – 384 с.

  8. Широков Л.А. Исследование систем управления. Учебное пособие. М.: МГИУ, 1999.-123с. (43. pdf )

  9. Кузнецов А.П. Теория автоматического управления. Учебное пособие. Минск: Дизайн-ПРО, 2002.-352с. (141. pdf )

  10. Белов А.Г. Теория автоматов. Методические рекомендации и контрольные задания для студентов заочной формы обучения вузов. Владивосток: ДВИК, 2007. - 20 с.


^ 5.2. Задания на контрольные работы (для студентов полной и сокращенной форм заочного обучения)

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

Студент-заочник до начала установочной сессии выбирает вариант задания, номер которого совпадает с последней цифрой номера зачетной книжки, и, выполнив его, отправляет почтой на проверку в ДВИК.

Студент, не приступивший к выполнению расчетно-графического задания до начала сессии, получает вариант задания у преподавателя дисциплины из дополнительного списка.


^ Контрольная работа № 1
Синтез комбинационной схемы автомата


  1. По заданной таблице истинности, описывающей функционирование КС автомата, построить КК. Таблицу истинности, соответствующую своему варианту, взять из таблицы 1.




  1. По КК получить алгебраические выражения ЛФ, описывающих КС автомата, в двух формах:

а) в дизъюнктивной форме, получаемой по единичным контурам КК;

б) в конъюнктивной форме, получаемой по нулевым контурам КК;

в) по единичным и нулевым контурам с учетом условных (безразличных) состояний ~ .
3. Проверить правильность полученных ЛФ.
4. По одному из полученных выражений построить КС автомата:

а) на логических элементах И – НЕ;

б) на логических элементах ИЛИ – НЕ.

Таблица 1

Варианты таблиц истинности

0

1

2

3

4

a

b

c

x

a

b

c

x

a

b

c

x

a

b

c

x

a

b

c

x

0

0

0

1

0

0

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

1

0

0

1

0

0

0

1

0

0

0

1

0

0

0

1

0

0

1

0

0

0

1

0



0

1

0

0

0

1

0

0

0

1

0

1

0

1

1

0

0

1

1



0

1

1

0

0

1

1

1

0

1

1



1

0

0



1

0

0

1

1

0

0

0

1

0

0

1

1

0

0



1

0

1

0

1

0

1

1

1

0

1

0

1

0

1

0

1

0

1

1

1

1

0

1

1

1

0

0

1

1

0

1

1

1

0

0

1

1

0

0

1

1

1

0

1

1

1

0

1

1

1



1

1

1



1

1

1

0

5

6

7

8

9

a

b

c

x

a

b

c

x

a

b

c

x

a

b

c

x

a

b

c

x

0

0

0

1

0

0

0

1

0

0

0



0

0

0



0

0

0

0

0

0

1

0

0

0

1



0

0

1



0

0

1

1

0

0

1

0

0

1

0

1

0

1

0

0

0

1

0

1

0

1

0

0

0

1

0

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

0

1

0

0

0

1

0

0

0

1

0

0

0

1

0

0

1

1

0

0



1

0

1

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

1

1

1

0

0

1

1

0

1

1

1

0

0

1

1

0

1

1

1

0

1

1

1

1



1

1

1

1

1

1

1

0

1

1

1

0

1

1

1

0


Контрольная работа № 2

Синтез автомата с памятью


  1. По заданному графу переходов построить исходную таблицу переходов. Граф, соответствующую своему варианту, взять из таблицы 2.

  2. Выбрать дополнительные переменные, ввести промежуточные состояния, построить измененную таблицу переходов.

  3. Построить общую КК для дополнительных и выходных переменных.

  4. Построить отдельные КК для каждой из переменных, по которым в соответствии с методом простого кодирования получить алгебраические выражения для соответствующих выходных и дополнительных переменных. Построить схему автомата, используя логические элементы И, ИЛИ, И – НЕ, ИЛИ - НЕ.

  5. Применив в качестве кодирующих элементов ^ RS – триггеры и используя таблицу переходов RS – триггера построить для каждой переменной КК, в клетках которой проставить значения функции возбуждения элемента памяти. Получить алгебраические выражения для входов S и R триггеров выходных и дополнительных переменных. Привести схему автомата на триггерах и логических элементах.


Таблица 2
Варианты графов


0

1





2

3





4

5





6

7





8

9






^ 5.3. Методические указания к выполнению контрольной работы № 1
Таблица истинности (таблица 3) задает ЛФ автомата

Таблица 3

Таблица истинности

a

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

b

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

c

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

d

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

x

1

1





1

1





0

0

1

1

1

0

1

1


где a, b, c, d – входные переменные автомата, а x = f(a, b, c, d) – его выходная функция.

По таблице 3 составляется КК (рис. 1).


Рис. 1. КК для таблицы 3

КК позволяет задавать ЛФ в более компактной форме и получать минимизированные алгебраические выражения ЛФ.

Правила, которыми следует руководствоваться для получения формул ЛФ посредством КК, следующие:

  1. Все единицы (при записи ЛФ в дизъюнктивной форме) или все нули (при записи ЛФ в конъюнктивной форме) КК заключаются в прямоугольные контуры. Контуры могут пересекаться, т.е. одна и та же единица или один и тот же нуль могут входить в несколько контуров.

  2. Число клеток в контуре должно быть равно 2n , где = 0, 1, 2,

  3. Увеличение размеров контуров упрощает (минимизирует) получаемое выражение ЛФ.

  4. В контур можно включать только соседние клетки. Соседними являются такие клетки, при переходе от одной из которых к другой изменяется значение лишь одной из входных переменных автомата.

  5. Единичному контуру соответствует конъюнкция входных переменных, определяющих этот контур. Переменные, имеющие в этом контуре единичные значения, записываются без инверсий, а переменные, имеющие в контуре нулевые значения, записываются с инверсиями.

  6. Нулевому контуру соответствует дизъюнкция входных переменных, определяющих этот контур. Переменные, принимающие в этом контуре единичные значения, записываются с инверсиями, а переменные, принимающие в нем нулевые значения, записываются без инверсий.

  7. Выражения, соответствующие контурам, не содержат тех переменных, чьи границы пересекаются данным контуром.

  8. Выражение ЛФ в дизъюнктивной форме (использование единичных контуров) составляется в виде дизъюнкции конъюнкций, соответствующих единичным контурам КК. Выражение ЛФ в конъюнктивной форме (использование нулевых контуров) представляется в виде конъюнкции дизъюнкций, соответствующих нулевым контурам.


Полученное по КК согласно вышеуказанным правилам алгебраическое выражение ЛФ автомата в дизъюнктивной форме (по единичным контурам 1, 2 и 3 на рис. 1):

. (1)
Алгебраическое выражение ЛФ автомата, полученное в конъюнктивной форме (по нулевым контурам 4 и 5 на рисунке 1):
. (2)
Раскрытие скобок в формуле (2) с последующим упрощением получаемого выражения по правилам преобразования алгебры логики минимизирует ЛФ автомата:
. (3)
На рис.2 приведена КК, в которой в три единичных контура включены условные состояния () .



Рис. 2. КК с включением в контура условных состояний
Полученное по этой КК выражение ЛФ совпадает с выражением по формуле (3).

Для построения КС автомата на логических элементах И – НЕ применяем к формуле (3) законы двойной инверсии и де Моргана:
. (4)
Для реализации автомата на элементах ИЛИ – НЕ также применяем к формуле (3), но иначе, законы двойной инверсии и де Моргана:
. (5)
Схемы автомата на логических элементах приведены на рис. 3.








Рис. 3. Реализации КС на логических элементах
^ 5.4. Методические указания по выполнению контрольной работы № 2

На рис.4а приведен граф переходов автомата с памятью, имеющего три входные переменные a, b, c, и три состояния A, B, C, отличающиеся значениями выходных переменных автомата = f1(a,b,c) и = f2(a,b,c) [8]. Соответствие между значениями входных и выходных переменных обозначено как abc / xy.

Но в схеме автомата возможно возникновение состязаний (гонок), т.к. при переходе из состояния B в состояние C меняют свое состояние обе выходные переменные. Для устранения такого критического перехода вводится промежуточное состояние C1 (рис. 4б).




а)



б)

Рис. 4. Графы переходов автомата
Для кодирования состояний автомата используем выходную переменную автомата ^ Х и вводим дополнительную переменную P так, чтобы при переходе сначала из состояния B в C1 , а затем из C1 в C изменялось бы состояние только одной из выбранных переменных.

На рис. 5 приведена таблица переходов, соответствующая измененному графу.

Рис. 5. Таблица переходов
По таблице переходов строятся две КК: первоначальная (совмещенная) КК для переменных X и P (рисунок 6а) и КК для переменной Y (рисунок 6б). В клетках этих карт вместо символов состояния таблицы переходов проставляются значения выходных и дополнительной переменной.






а) б)

Рис. 6. КК для выходных (а ) и дополнительной (б ) переменной
Затем совмещенная КК (рисунок 6а) разделяется на две карты: одна – для переменной ^ X (первые цифры в клетках карты) и вторая – для переменной P (вторые цифры). Далее, в соответствии с методическими рекомендациями по выполнению первого задания контрольной работы, по первой КК (по единичным контурам) получается алгебраическое выражение для выходной переменной X:
, (6)
а по второй КК (по нулевым контурам) - алгебраическое выражение для дополнительной переменной ^ P:
. (7)
Выходная переменная автомата Y определяется формулой (рисунок 6б):
. (8)
В формулах (6), (7), (8) прописными буквами (например, Х) обозначены выходные сигналы автомата, а строчными буквами (соответственно, х) – эти же сигналы, заводимые с выходов по обратным связям на входы элементов схемы автомата.

По этим формулам воспроизводится схема автомата на типовых логических элементах.

Рассмотренный способ синтеза автомата реализован методом простого кодирования и не использует элементы памяти: триггеры различных типов, счетчики, регистры и т.д. В случае же их использования в КК вместо значений выходной или дополнительной переменной проставляются значения функций возбуждения элементов памяти. Причем, если значение сигнала соответствует устойчивому состоянию устройства, функции возбуждения тоже проставляются для устойчивого состояния, а если состояние неустойчивое, то учитывается процесс перехода типа 0  1 или 1  0 и функции возбуждения элемента памяти проставляются с учетом этого перехода.

Таким образом, таблицы состояний элементов памяти или КК составляются по таблице переходов, где каждой строке таблицы поставлено в соответствие определенное состояние элементов памяти.

Состояния R S – триггера отражены на рисунке 7:







Рис. 7. Таблица переходов ^ RS – триггера
Основываясь на таблице переходов автомата (рис. 5) и таблице переходов RS – триггера (рис. 7) строится общая КК для функций возбуждения (входов) RS – триггеров переменных X и P - рисунок 8.

Рис. 8. Общая КК функций возбуждения RS – триггеров X и P

В верхней строке каждой клетки КК проставлены значения функций возбуждения триггера выходной переменной Х - Sx и Rx , соответственно, а в нижней строке – значения функций возбуждения триггера дополнительной переменной Р - Sр и Rр .

Далее по общей КК создаются КК для каждого из входов триггеров - Sx , Rx , Sр , Rр . По КК получены следующие выражения:
(9)
По формулам (9) строится синтезированная схема автомата на RS – триггерах и логических элементах (рис. 9).

Рис. 9. Схема автомата с использованием триггеров

^ 6. МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ
Компьютерный класс кафедры «Электроника и информационные системы».

8 ПК, 2 лазерных принтера, многофункциональный копировальный аппарат, струйный принтер, цифровая камера, видеокарты, жесткие диски, звуковые карты, флэш-диски, компакт диски, программное обеспечение Electronics Workbench v5.12, Electronics Workbench Multisim 7, пакеты LOGO! Soft Comfort и Mathlab, MS Office2000, MS Visual Basic 6.0, Adobe Photoshop 7.0, Autodesk Autocad2000, MS Visual Studio 6.0 и др, компьютерные тесты: Компас3, БЖС, Охрана труда, Дельта-танкер, Unitest, Turbo Diesel, Unitest Auxiliary Steam Boiler, локальная сеть, сеть ДВИК, Интернет.

Лабораторный стенд «Тренажер для испытаний и исследований элементов и схем вычислительной техники и дискретной автоматики».
^ 7. ПЕРЕЧЕНЬ ВОПРОСОВ ДЛЯ ИТОГОВОГО КОНТРОЛЯ


  1. Определение автомата.

  2. Абстрактная и структурная теория автоматов.

  3. Модель дискретного преобразователя В.М. Глушкова.

  4. Тривиальные и нетривиальные автоматы. Примеры элементарных автоматов.

  5. Конечные, синхронные, асинхронные, идеализированные, абстрактные, структурные автоматы.

  6. Отличие КА Мура и Мили.

  7. Эквивалентность автоматов.

  8. Автомат без памяти, автономный автомат, автомат без выхода, частичный автомат.

  9. Детерминированные и вероятностные КА.

  10. Понятия операционного и управляющего автоматов.

  11. Способы задания автоматов.

  12. Принцип микропрограммного управления.

  13. Формулировка понятия «конечный автомат» как распознающего устройства.

  14. Определение понятий «алфавит», «буква», «слово» («цепочка»), «язык и проблема», «грамматика».

  15. Основные функции языка.

  16. Четыре типа грамматик и языков согласно классификации их по Хомскому.

  17. Регулярные выражения и языки.

  18. Контекстно – свободные грамматики и языки.

  19. В связи с какими исследованиями появилась теория формальных грамматик?

  20. Определение регулярного языка и грамматики с точки зрения формальных грамматик.

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

  22. Что представляют собой распознающая грамматика и задача распознавания?

  23. Что является основными объектами теории формальных языков? Привести примеры описания этих объектов.

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

  25. Определение автомата с точки зрения формальных грамматик.

  26. Характеристика автоматов с магазинной памятью.

  27. Описание и характеристика машины Тьюринга.

  28. В чем заключается проблема распознавания для машины Тьюринга?

  29. Почему машина Тьюринга в общем виде не используется в кибернетических моделях?

  30. Чему равно число значений ЛФ n входных переменных и количество ЛФ от n переменных?

  31. Основные ЛФ двух переменных и их бесконтактные и релейно-контактные эквиваленты.

  32. Основные законы алгебры логики.

  33. Законы де Моргана.

  34. Функционально полная система элементарных ЛФ.

  35. Получение КК по таблицам состояний.

  36. Определение по КК алгебраических выражений ЛФ.

  37. Условные состояния и их использование при синтезе автомата.

  38. Синтез КС автоматов. Основные понятия: КС, логический элемент, функциональная схема, базис.

  39. Задачи анализа и синтеза КС.

  40. Критерии качества технической реализации КС.

  41. Основная задача теории структурного синтеза автоматов.

  42. Теорема В.М. Глушкова о структурной полноте.

  43. Содержание канонического метода структурного синтеза автоматов.

  44. Построение таблиц переходов и выходов.

  45. Гонки и неустойчивые состояния в автоматах.

  46. Способы кодирования состояний автоматов.

  47. Построение функций возбуждений триггеров.

  48. Привести пример описания работы автомата циклограммой.

  49. Изображение на циклограмме характерных тактов и периодов работы элементов.

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

  51. Содержание трех проверок (условий) реализуемости циклограммы.

  52. Научные дисциплины, используемые при проектировании дискретных электронных схем для вычислительной техники и современных средств связи.


Адрес для переписки:

690013, г. Владивосток, ул. Каплунова, 7, ДВИК, заочное отделение,

тел/факс (4232)52-71-71, mstc@mail.ru


Скачать файл (656 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru