Задания

• Задание 1      
• Задание 2      
• Задание 3      
• Задание 4      
• Задание 5      
• Задание 6      
• Задание 7      
• Задание 8      
• Задание 9      
• Задание 10    
• Задание 11     

 

Программа курса и каноническое задание находятся здесь. Отношение к этому заданию следующее. Я накрываю это задание еженедельными. На выходе предполагается, что вы умеете решать любую задачу из этого задания. Поэтому, если у вас возникают сомнения в ваших способностях, обязательно поднимите этот вопрос.

---

Для подготовки ко второй контрольной и экзамену доступны варианты экзаменов предыдущих лет: 1 2, 3.

Сдача задания

---

Я буду принимать задание 10 января с 17:30 в 903 КПМ.

Сдачи

---

Ближайшие сдачи пройдут в четверг и следующий вторник с 18:30 до 21:00 в 11 ГК. В этот четверг последний семинар: половину времени я расскажу про атрибутные грамматики, вторая половина уйдёт на показ работ. В следующий четверг (25 декабря) ни семинара, ни сдачи не будет.

Задачи для подготовки к контрольной

---

Для подготовки ко второй контрольной и экзамену доступны варианты экзаменов предыдущих лет: 1, 2.

Контрольная 15 декабря начнётся в 8:30 в актовом зале.

LR-конструктор

---

Для проверки и более наглядного изучения есть конструктор анализаторов.  По умолчанию все нетерминалы — заглавные буквы, все терминалы — строчные. Правила записываются в виде "A -> a|B". Каждое правило, быть может с разделителями, начинается с новой строки. Пустое слово = e.

 

Если запускать программу под IE, то можно, при некоторой удаче, увидеть дерево разбора анализируемого слова. Под остальными браузерами придётся включать воображение и соединять точки.

Комментарии к семестровым контрольным

---

В прошлом году Сергей Тарасов подготовил комментарии к прошлогодним семестровым контрольным. Автор предупреждает, что в тексте возможны ошибки и неточности.

Варианты для подготовки к контрольной

---

Для подготовки ко второй семестровой контрольной доступны варианты прошлогодней контрольной. Я рекомендую прорешать вариант до разбора во вторник.

Дополнительный семинар и сдача

---

Дополнительный семинар, на котором будет разбор прошлогодней семестровой контрольной состоится во вторник 9 декабря с 17:05 до 18:30 в 202 НК. Сдача задания будет проходить с 18:30 до 21:00 в 532 ГК 202 НК.

Очная сдача

---

Очная сдача в четверг будет проходить в 521 ГК начиная с 18:30.

План действий

---

Задание на эту неделю я давать не буду — последнее задание будет по теме LL-анализа, которое я дам после ближайшего семинара. Если хотите посмотреть теорию, то смотрите задание 10 прошлого года. В четверг начиная с 18:30 ожидается первая итерация очной сдачи (подробности будут после того как выделят аудиторию). Вторая семестровая контрольная состоится 15 декабря.

Половина задания

---

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

Половина семинара

---

На этой неделе будет только первая половина семинара: вторая будет отдана под показ работ. График показа старосты получили или скоро получат по почте.

Материалы для подготовки к контрольной

---

Прелагаю задачи для подготовки к контрольной: этот набор совпадает с одним из вариантов задания, которое я давал в позапрошлом году, а этот вариант взят Сергеем Тарасовым из одного из топовых вузов с аналогичным курсом.

 

Контрольная

---

СЕМЕСТРОВАЯ КОНТРОЛЬНАЯ РАБОТА

по ТЕОРИИ И РЕАЛИЗАЦИИ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ

ДЛЯ СТУДЕНТОВ II КУРСА ФУПМ

БУДЕТ ПРОВОДИТЬСЯ

10 НОЯБРЯ, в понедельник,

с 8:15 до 11:15.

 

Для студентов, чьи фамилии начинаются на буквы

от «А» до «М»  – в ауд.  117 ГК,

от «Н» до «Я»  – в ауд.  123 ГК.

   

 

 ПОКАЗ РАБОТ, ВЫСТАВЛЕНИЕ ОЦЕНОК

14 НОЯБРЯ, в пятницу, во время лекции в 239 нк .

 

P.S. В связи с контрольной (а именно для времени на подготовку к ней), домашнего задания на следующую неделю не даю.

P.P.S. Напоминаю, что на оценку автоматом можно претендовать только если обе семестровых контрольных написаны на положительную оценку (≥3).

Подготовка к контрольной

---

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

Рецензии на задание 4

---

Рецензия на задание 4 разосланы. Если вы не получили результаты проверки, напишите мне об этом. Поскольку общественностью был проявлен особый интерес к необязательным задачам на морфизмы, написавшим решение близкое к Хопкрофту, придётся его рассказывать на очной сдаче.

Рецензии на задание 3

---

Рецензии на третье задаие разосланы. Если кто не получил свою рецензию, сообщите об этом. Некоторые из вас получили по несколько копий письма из-за моей неаккуратности в работе со скриптом, прошу прощения.

Замена задачи

---

Я осознал, что сделал задачу про двоичную и троичную запись слишком сложной (возможно некорректной), поэтому заменил её на более простую.

 

P.S. Сейчас выложено правильное задание

Share Latex

---

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

Рассылка рецензий

---

Результаты проверки второго домашнего задания разосланы. Я впервые использовал для этого скрипт, поэтому если что-то пошло не так, сообщите пожалуйста.

Задание

---

У меня случился небольшой форс-мажор, завтра (уже сегодня) выложу и новое задание и пришлю результаты по старому.

Экспоненциальный разрыв

---

Под экспоненциальным разрывом в третьем задании понимается, что состояний в ДКА не может быть меньше, чем $2^{cn}$, где $c$ константа, а $n$ — число состояний НКА.

Домашние работы

---

Результаты проверки первой домашней работы разосланы. Если вы их не получили, напишите мне об этом.

Пожалуйста, не отправляйте свои задания в архивах — просто прикрепляйте оба файла к письму. Особено это касается людей, выдрессированных уважаемым Сергеем Павловичем. И не забывайте подписывать свои работы внутри самих файлов. Если вы не из 371/373 группы, то указывайте также своё имя и номер группы.

Система тэгов

---

При проверке письменных работ я использую систему тэгов. Ознакомиться с их значением можно на соответствующей странице.

Критическая ошибка в задаче 4

---

Я плохо написал условие: на самом деле в задаче надо доказать, что существует процедура построения ДКА по НКА данного вида с оценкой сверху на число состояний $|w|+1$.

Ошибка во втором задании

---

В номере 4 задания два была указана неправильная оценка на число состояний: правильная оценка $|w|+1$.

Замена аудитории

---

Поскольку в прошлый раз парт на всех не хватило, и ещё несколько людей грозились, что придут, мы переезжаем в большую аудиторию 202 НК.