Конструирование Компиляторов, Проведение Экзамена
Материал из eSyr's wiki.
(добавлены теоретические вопросы на 2009 год) |
|||
| Строка 1: | Строка 1: | ||
| - | Условия проведения экзамена в 2008 году | + | = Условия проведения экзамена в 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? | ||
| - | |||
| - | Что такое основа правой сентенциальной формы | ||
| - | |||
=== Практическая часть === | === Практическая часть === | ||
| Строка 151: | Строка 31: | ||
Теоретическая часть состоит из двух вопросов из [[Конструирование_Компиляторов,_Определения|списка определений]] и [[Конструирование_Компиляторов,_Теоретический_минимум|теормина]]. Корректное написание обоих вопросов или успешная сдача их на лекции расценивается в 0 баллов, каждый незачтенный вопрос — в -0.5 баллов. | Теоретическая часть состоит из двух вопросов из [[Конструирование_Компиляторов,_Определения|списка определений]] и [[Конструирование_Компиляторов,_Теоретический_минимум|теормина]]. Корректное написание обоих вопросов или успешная сдача их на лекции расценивается в 0 баллов, каждый незачтенный вопрос — в -0.5 баллов. | ||
| - | |||
| - | |||
| - | '''(Информация от лектора: в 2009 году каждый незачтенный вопрос оценивается в -1 балл)''' | ||
| - | |||
| - | ''//Sirian (Василий Хайрулин) 28.05.2009'' | ||
| - | |||
Максимум набирается 5 баллов, минимум -1. | Максимум набирается 5 баллов, минимум -1. | ||
| Строка 238: | Строка 112: | ||
5 можно получить только если набрать 3 и после '''дополнительной усложненной задачи от лектора'''. Автору неизвестны попытки эту задачу получить и решить. | 5 можно получить только если набрать 3 и после '''дополнительной усложненной задачи от лектора'''. Автору неизвестны попытки эту задачу получить и решить. | ||
| + | |||
| + | = Условия проведения экзамена в 2009 году = | ||
| + | |||
| + | Информация от лектора: в 2009 году каждый незачтенный вопрос оценивается в -1 балл. <!-- ''//Sirian (Василий Хайрулин) 28.05.2009'' --> | ||
{{Курс Конструирование Компиляторов}} | {{Курс Конструирование Компиляторов}} | ||
Текущая версия
Содержание |
[править] Условия проведения экзамена в 2008 году
[править] Досрочная сдача
Сдача теоретической и практической частей независимы, любую из них можно как получить досрочно, так и сдать на экзамене.
[править] Теоретическая часть
Лектор на лекциях проводит две контрольные работы. Успешное их написание расценивается, как сдача теоретической части экзамена, иначе теоретическую часть придется писать на экзамене.
[править] Практическая часть
Все семинаристы проводят на итоговом занятии контрольную работу. Контрольная работа состоит из трех задач, за каждую дается +1 балл к базовым двум. Тем не менее, автоматы получают немногие.
[править] Экзамен
[править] Условия проведения
Весь поток пишет одновременно, в одной аудитории. Время отводится 3 часа (изначально планировалось 2ч 30мин, но экзаменаторы «намудрили с накрученностью задач» и добавили еще 30 минут).
Выдается 4 задачи и 2 теоретических вопроса.
Времени хватает вполне, и даже на спокойную проверку всех заданий остается.
Работы проверяют к вечеру, примерно к 17 часам. После объявления результатов возможна апелляция, проводимая с проверявшим работу. Случаи успешного оспаривания баллов достаточно распространены.
[править] Критерии оценки
Разбалловка задач:
- (1 балл) Построение минимального ДКА по регулярному выражению, построение соответствующей грамматики.
- (2 балла) LR, LL. (P.S. LR(2) ни в одном условии строить было не нужно).
- (1 балл) Генерация кода для логических/арифметических выражений.
- (1 балл) Генерация оптимального кода методом сопоставления образцов.
Каждая задача делится на части. Например, в задаче 2: построил схему с замыканиями - столько то баллов из 2х, сделал таблицу - еще сколько то из 2х, разобрал цепочку - оставшиеся до 2х баллов. (что-то типа 0.7+0.7+0.6).
Теоретическая часть состоит из двух вопросов из списка определений и теормина. Корректное написание обоих вопросов или успешная сдача их на лекции расценивается в 0 баллов, каждый незачтенный вопрос — в -0.5 баллов.
Максимум набирается 5 баллов, минимум -1.
Критерии оценки:
| Оценка | Баллы |
|---|---|
| 3 | ≥ 2.5 |
| 4 | ≥ 3.5 |
| 5 | ≥ 4.5 |
[править] Пересдача
[править] Условия проведения
Время отводится теперь 1.5 часа.
Выдается теперь уже 3 задачи и снова 2 теоретических вопроса (если в предыдущие попытки, вам удалось сдать хотя бы родну из теорий, то вы освобождаетесь от её сдачи на всех последующих попытках).
Работы проверяют чуть ли не к 12—13 часам. После объявления результатов возможна апелляция, проводимая с проверявшим работу. Случаи успешного оспаривания баллов достаточно распространены.
[править] Критерии оценки
Разбалловка задач:
- (1 балл) Построение минимального ДКА по регулярному выражению, построение соответствующей грамматики.
- (1.5 балла) LR, LL. (P.S. LR(2) ни в одном условии строить было не нужно).
- (1 балл) Генерация кода для логических/арифметических выражений или генерация оптимального кода методом сопоставления образцов.
Теоретическая часть абсолютна такая же. Если ранее, например на основном экзамене ты за них уже получил плюс, то далее этот теор. вопрос снимается.
Максимум набирается 3.5 баллов, минимум -1.
Критерии оценки:
| Оценка | Баллы |
|---|---|
| 3 | ≥ 2 |
| 4 | ≥ 3 |
5 можно получить только если набрать 3.5 и после разговора с лектором, в результате которого оценка может и понизиться.
[править] Вторая пересдача
[править] Условия проведения
Время отводится ещё меньше: 1 час, но задачи субъективно простые.
Выдается опять 3 задачи и снова 2 теоретических вопроса (если в предыдущие попытки, вам удалось сдать хотя бы одну из теорий, то вы совобождаетесь от её сдачи на всех последующих попытках).
Работы проверяют в течение 15-30 минут.
[править] Критерии оценки
Разбалловка задач:
- (1 балл) Построение минимального ДКА по регулярному выражению, построение соответствующей грамматики.
- (1 балл) LR и LL. (P.S. LR(2) ни в одном условии строить было не нужно).
- (1 балл) Генерация кода для логических/арифметических выражений или генерация оптимального кода методом сопоставления образцов.
Максимум набирается 3 балла, минимум -1.
Критерии оценки:
| Оценка | Баллы |
|---|---|
| 3 | ≥ 2 |
| 4 | ≥ 3 |
5 можно получить только если набрать 3 и после дополнительной усложненной задачи от лектора. Автору неизвестны попытки эту задачу получить и решить.
[править] Условия проведения экзамена в 2009 году
Информация от лектора: в 2009 году каждый незачтенный вопрос оценивается в -1 балл.
