Редактирование: Конструирование Компиляторов, Проведение Экзамена
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 1: | Строка 1: | ||
- | + | Условия проведения экзамена в 2008 году: | |
== Досрочная сдача == | == Досрочная сдача == | ||
Строка 6: | Строка 6: | ||
=== Теоретическая часть === | === Теоретическая часть === | ||
Лектор на лекциях проводит две контрольные работы. Успешное их написание расценивается, как сдача теоретической части экзамена, иначе теоретическую часть придется писать на экзамене. | Лектор на лекциях проводит две контрольные работы. Успешное их написание расценивается, как сдача теоретической части экзамена, иначе теоретическую часть придется писать на экзамене. | ||
+ | |||
+ | ====Список теоретических вопросов (2009 год)==== | ||
+ | |||
+ | ''//Sirian (Василий Хайрулин) 28.05.2009'' | ||
+ | |||
+ | '''Список вопросов был взят у лектора''' | ||
+ | |||
+ | |||
+ | Определение грамматик типа 0 по Хомскому | ||
+ | |||
+ | Определение грамматик типа 1 (неукорачивающих) по Хомскому | ||
+ | |||
+ | Определение детерминированной машины Тьюринга | ||
+ | |||
+ | Определение недетерминированной машины Тьюринга | ||
+ | |||
+ | Определение конфигурации машины Тьюринга | ||
+ | |||
+ | Определение языка, допускаемого машиной Тьюринга | ||
+ | |||
+ | Соотношение между языками, порождаемыми грамматиками типа 0 и языками, допускаемыми машинами Тьюринга | ||
+ | |||
+ | Объяснить разницу между недетерминированной и детерминированной машиной Тьюринга | ||
+ | |||
+ | Определение регулярного множества | ||
+ | |||
+ | Определение регулярного выражения | ||
+ | |||
+ | Определение праволинейной грамматики | ||
+ | |||
+ | Определение недетерминированного конечного автомата | ||
+ | |||
+ | Определение детерминированного конечного автомата | ||
+ | |||
+ | Объяснить разницу между недетерминированным и детерминированным конечным автоматом | ||
+ | |||
+ | Определение конфигурации конечного автомата | ||
+ | |||
+ | Определение языка, допускаемого конечным автоматом | ||
+ | |||
+ | Определение е-замыкания для подмножества состояний НКА | ||
+ | |||
+ | Определение расширенной функции переходов для ДКА | ||
+ | |||
+ | Определение расширенной функции переходов для НКА | ||
+ | |||
+ | Определение функции firstpos для поддерева в дереве регулярного выражения | ||
+ | |||
+ | Определение функции lastpos для поддерева в дереве регулярного выражения | ||
+ | |||
+ | Определение функции followpos для позиций в дереве регулярного выражения | ||
+ | |||
+ | Сформулировать соотношение между регулярными множествами и языками, допускаемыми КА | ||
+ | |||
+ | Определение регулярной грамматики | ||
+ | |||
+ | Сформулировать соотношение между языками, порождаемыми праволинейными грамматиками и языками, допускаемыми КА | ||
+ | |||
+ | Определение эквивалентных состояний ДКА | ||
+ | |||
+ | Определение различимых состояний ДКА | ||
+ | |||
+ | Определение контекстно-свободной грамматики без е-правил | ||
+ | |||
+ | Определение контекстно-свободной грамматики | ||
+ | |||
+ | Определение вывода в КС-грамматике | ||
+ | |||
+ | Определение языка, порождаемого КС-грамматикой | ||
+ | |||
+ | Определение сентенциальной формы | ||
+ | |||
+ | Определение однозначной КС-грамматики | ||
+ | |||
+ | Определение неоднозначной КС-грамматики | ||
+ | |||
+ | Определение недетерминированного МП автомата | ||
+ | |||
+ | Определение детерминированного МП автомата | ||
+ | |||
+ | Определение конфигурации МП автомата | ||
+ | |||
+ | Определение языка, допускаемого МП автоматом | ||
+ | |||
+ | Что означает, что недетерминированный МП автомат допускает опустошением магазина | ||
+ | |||
+ | Соотношение, между языками, порождаемыми КС-грамматиками, и языками, допускаемыми недетерминированными МП автоматами | ||
+ | |||
+ | Формулировка леммы о разрастании для КС-языков | ||
+ | |||
+ | Определение нормальной формы Хомского для КС-грамматики | ||
+ | |||
+ | Определение правостороннего вывода в КС-грамматике | ||
+ | |||
+ | Определение левостороннего вывода в КС-граммати | ||
+ | |||
+ | Какая грамматика называется леворекурсивной? | ||
+ | |||
+ | Определение множества FIRST1 | ||
+ | |||
+ | Определение множества FOLLOW1 | ||
+ | |||
+ | Определение LL(1) Грамматики | ||
+ | |||
+ | Определение LR(1) ситуации | ||
+ | |||
+ | Определение LR(1) грамматики | ||
+ | |||
+ | Какого типа конфликты могут появиться в канонической системе множеств LR(1) ситуаций? | ||
+ | |||
+ | Определение конфигурации LR-анализатора | ||
+ | |||
+ | Как меняется конфигурация LR-анализатора при дейстьвии reduce? | ||
+ | |||
+ | Какие типы действий выполняет LR-анализатор? | ||
+ | |||
+ | Как меняется конфигурация LR-анализатора при дейстьвии shift? | ||
+ | |||
+ | Что такое основа правой сентенциальной формы | ||
+ | |||
=== Практическая часть === | === Практическая часть === | ||
Строка 31: | Строка 151: | ||
Теоретическая часть состоит из двух вопросов из [[Конструирование_Компиляторов,_Определения|списка определений]] и [[Конструирование_Компиляторов,_Теоретический_минимум|теормина]]. Корректное написание обоих вопросов или успешная сдача их на лекции расценивается в 0 баллов, каждый незачтенный вопрос — в -0.5 баллов. | Теоретическая часть состоит из двух вопросов из [[Конструирование_Компиляторов,_Определения|списка определений]] и [[Конструирование_Компиляторов,_Теоретический_минимум|теормина]]. Корректное написание обоих вопросов или успешная сдача их на лекции расценивается в 0 баллов, каждый незачтенный вопрос — в -0.5 баллов. | ||
+ | |||
+ | |||
+ | '''(Информация от лектора: в 2009 году каждый незачтенный вопрос оценивается в -1 балл)''' | ||
+ | |||
+ | ''//Sirian (Василий Хайрулин) 28.05.2009'' | ||
+ | |||
Максимум набирается 5 баллов, минимум -1. | Максимум набирается 5 баллов, минимум -1. | ||
Строка 112: | Строка 238: | ||
5 можно получить только если набрать 3 и после '''дополнительной усложненной задачи от лектора'''. Автору неизвестны попытки эту задачу получить и решить. | 5 можно получить только если набрать 3 и после '''дополнительной усложненной задачи от лектора'''. Автору неизвестны попытки эту задачу получить и решить. | ||
- | |||
- | = Условия проведения экзамена в 2009 году = | ||
- | |||
- | Информация от лектора: в 2009 году каждый незачтенный вопрос оценивается в -1 балл. <!-- ''//Sirian (Василий Хайрулин) 28.05.2009'' --> | ||
{{Курс Конструирование Компиляторов}} | {{Курс Конструирование Компиляторов}} |