ТВП-Вопросы для подготовки к экзамену
.doc
«УТВЕРЖДАЮ»
Заведующий 43 кафедрой
доктор технических наук,
профессор В.И.ХИМЕНКО
«___» ___________ 200_ г.
СПИСОК
вопросов для подготовки к экзамену
по дисциплине
«Теория вычислительных процессов»
-
Понятие алгоритма. Теория алгоритмов и ее необходимость.
-
Основные подходы к построению алгоритмов (Уточнения понятия алгоритмов). Алгоритмическая система.
-
Определение примитивно-рекурсивной функции.
-
Оператор примитивной рекурсии и его использование.
-
Обоснование недостаточности примитивно-рекурсивных функций.
-
Оператор наименьшего корня и его использование.
-
Частично-рекурсивные функции. Общерекурсивные функции. Классификация рекурсивных функций.
-
Значение рекурсивных функций. Тезис ЧЕРЧА.
-
Определение и принципы функционирования машины ТЬЮРИНГА.
-
Способы задания машины ТЬЮРИНГА.
-
Вычисления на машине ТЬЮРИНГА.
-
Тезис ТЬЮРИНГА и его связь с тезисом ЧЕРЧА.
-
Определение формальной системы.
-
Определение системы (полусистемы) ТУЭ. Примеры систем.
-
Определение канонической системы ПОСТА. Примеры систем.
-
Неклассические алгоритмические системы. Виды и применение.
-
Разрешимые и перечислимы множества. Их применимость.
-
Алгоритмическая проблема неразрешимости. Источники возникновения, сущность и способы устранения.
-
Определение конечного автомата. Примеры.
-
Способы задания конечного автомата. Примеры.
-
Основные свойства конечных автоматов (инициальность, полнота, детерминированность, …).
-
Процедуры синтеза и анализа конечного автомата. Определение и взаимосвязь.
-
Определение регулярного выражения. Примеры.
-
Регулярные выражения и примеры их использования. Определяемые регулярными выражениями множества.
-
Регулярные выражения и их разметка.
-
Правила подчинения мест в регулярном выражении.
-
Правило отметки состояний регулярного выражения. Теорема обоснования допустимости входных слов конечным автоматом.
-
Правила алгоритма синтеза конечного автомата по заданному множеству регулярных выражений и их использование.
-
Операции на множестве конечных автоматов. Определение гомоморфизма на множестве конечных автоматов.
-
Неотличимость и эквивалентность состояний конечных автоматов
-
Формулировка задачи минимизации конечного автомата. Теорема существования минимального конечного автомата.
-
Описание алгоритма минимизации конечного автомата.
-
Теорема КЛИНИ о синтезе и анализе конечного автомата.
-
Описание алгоритма анализа конечного автомата.
-
Определение формальной грамматики.
-
Выводимость в формальных грамматиках. Дерево (граф) вывода.
-
Свойства формальных грамматик (однозначность, неоднозначность). Примеры формальных грамматик, обладающих заданными свойствами.
-
Определение формального языка.
-
Виды классификации формальных грамматик. Распознающие, порождающие, преобразующие формальные грамматики.
-
Виды классификации формальных грамматик. Классификация грамматик по Н.ХОМСКОМУ.
-
Определение иерархии формальных грамматик и языков.
-
Формальные свойства грамматик и языков.
-
Автоматные грамматики и языки. Их связь с конечными автоматами.
-
Синтез (восстановление) автоматных грамматик.
-
Анализ автоматных грамматик.
-
КС грамматики и языки. Нормальная форма ХОМСКОГО.
-
КС грамматики и языки. Нормальная форма ГРЕЙБАХ.
-
Анализ и синтез КС грамматик.
-
Определение автомата с магазинной памятью.
-
Функционирование автомата с магазинной памятью.
Составил:
профессор 43 кафедры
«___» ___________ 200_ г. М.ОХТИЛЕВ