Задания

 

 

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

 

Перенос пересдачи


03 Февраля 2014

Внимание, пересдача по ТРЯПу перенесена со среды 5 февраля на четверг 6 февраля.
Время то же самое: к 9:00 приходят должники со штрафными задачами, к 9:30 приходят все остальные. Аудитория 117 ГК.

 

Пересдача


30 Января 2014

Пересдача по ТРЯПу состоится в среду 5 февраля.
К 9:00 приходят люди, имеющие штрафные задачи.
Остальные приходят к 9:30. Аудитория уточняется.

 

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


27 Декабря 2013

Досрочный экзамен, на котором по факту будет происходить проставление автоматов, состоится завтра 28 декабря в 13:00 в 903 или 907 КПМ. 

 

Последняя итерация


23 Декабря 2013

Последняя итерация сдачи ТРЯПа состоится в эту среду. Я буду сидеть в 907 КПМ начиная с 15:30 и до разумного времени, ориентировочно до 20:00.

 

Доклад Разборова


16 Декабря 2013

В связи с внезапным докладом Разборова, на который я рекомендую сходить всем, кто итересуется комбинаторикой и теоретической информатикой, обявление тут, сдача задания в среду на паре 18:30-20:00 проходить не будет. На месте решим что делать с теми, кто не успеет сдаться, в зависимости от состава участников (возможно продолжение сдачи начиная с 20:00).

 

Атрибутные грамматики


15 Декабря 2013

Меня замучили ещё одним вопросом: будут ли завтра атрибутные грамматики. Нет, их не будет: контрольная на КС-языки, в неё может войти всё, начиная с КС-языков и заканчивая анализаторами.

 

Ограничения на k в анализаторах


14 Декабря 2013

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

 

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


09 Декабря 2013

На этой и следующей неделе я буду принимать задание по средам с 14:00 до 20:00 (или раньше, если все вдруг внезапно разойдутся). Приоритет по разговорам у тех, у кого оценка выше, так что сдающим задание и пока не претендующим на автомат стоит писать всё достаточно подробно. Аудитории, в которых будет проходить действо: 

  • 14:00-15:20 521 ГК
  • 15:30-16:55 430 ГК
  • 17:05-18:30 113 ГК
  • 18:30-20:00 117 ГК
 

Ещё одна проблема 10 задание


18 Ноября 2013

В алгоритме вычисления ${\rm FIRST}_k$ на нулевом шаге была написана глупость. Теперь всё хорошо.

 

Исправление исправления опечатки


18 Ноября 2013

Я неправильно исправил опечатку в Задаче 4. Теперь всё хорошо. Если Вы решили старую версию задачи, то можно сдать её, но рекомендую поискать ошибку, если всё получилось гладко.

 

Опечатка в задании 10


17 Ноября 2013

В задаче №4 раньше стоял нетерминал $A$, правил для которого не было. Теперь там стоит нетерминал $S$, как и должно было быть.

 

Очные сдачи


15 Ноября 2013

Я планирую начать проводить очные сдачи на неделе 25 ноября - 1 декабря. Скорее всего они будут в среду после семинара. Возможно, что и до. Тем, у кого всё плохо: большинство еженедельных заданий не сдано, иметь при себе решённое каноническое задание. Начнём с него. Не рекомендую списывать те задачи, которые вы не сможете объяснить — не сдадите, пока не объясните.

Остальным будут подготовлены листочки с задачами, кому-то нужно будет прорешать листочек, чтобы получить зачёт по заданию, кому-то чтобы получить опцион на автомат, кому-то чтобы получить непосредственно автомат, в зависимости от успехов в работе в семестре. Статитсика будет ближе к делу.

 

Практическая часть курса


15 Ноября 2013

Мы подошли к практической части нашего курса, на этом книжка Хопкрофта, Мотвани и Ульмана кончается. Я рекомендую изучать алгоритмы по книжке Серебрякова и по Dragon Book (Ахо, Сети, Ульман). В последней они описаны более подробно. Почему это всё работает, написано в книжке Ахо и Ульмана, но её очень сложно понять и расстояние между двумя нужными для понимания утверждениями порой достигает 100 страниц. В теории к заданиям я попытаюсь пролить свет на некоторые вещи, но это довольно трудно, и не факт что получится. Про LR-анализаторы так же написано в книжке Шеня, там есть хороший шанс понять что происходит.

 

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

 

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


Кого поймаю на сдачах с этой программой —  задание засчитаю не раньше, чем будет построен руками LR(5) анализатор.

 

Можно получить +2 балла по десятибалльной системе, если вы запрограммируете свой конструктор LR(k)-анализаторов. Это достаточно трудная задача, программа должна пройти все наши тесты и пока она их не пройдёт, дополнительные баллы не гарантированны. Формат входа-выхода тестов будет описан позднее.  Попытка списать программу из старых версий лишает любого из автоматов.

 

К контрольной


10 Ноября 2013

Меня завалили вопросами о построении РВ по ДКА. Есть алгоритм, который есть в книжке и рассказывался (?) на лекции, его можно и нужно использовать. Также по ДКА можно построить ПГ и по ней построить РВ — этот путь разбирался на семинарах и он является допустимым.

Напоминаю, что контрольная начинается завтра в 9:00 (начало рассадки, не опаздывайте!), группы с чётными номерами пишут в 239 НК, а с нечётными в 202 НК. На контрольной ничем нельзя пользоваться.

 

Курс Ульмана


04 Ноября 2013

На Coursera начался курс Джеффри Ульмана, близкий к ТРЯПу. Я рекомендую там зарегистрироваться и если уж не поучаствовать, хотя большую часть курса, Вы уже прошли, то хотя бы посмотреть его лекции.

 

Ещё одна дырка в задании 7


20 Октября 2013

В первоначальной версии файла было дано неверное определение языка Дика.

 

Дырка в задании 7


18 Октября 2013

Раньше в задании 7 в первой задаче я дал не тот язык, который на самом деле хотел дать и задача получилась скучной. Теперь всё нормально.

 

Задание 3


17 Октября 2013

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

 

Неаккуратность в задании 5


07 Октября 2013

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

 

Дырка в задаче из задания 4


30 Сентября 2013

В первой задаче четвёртого задания была обнаружена дырка — для её решения нужен ещё один оракул, который сообщает о том, принадлежит ли слово языку $L$ или нет. Условие исправлено.

 

Второе задание


26 Сентября 2013

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

 

Также часть работ была кластеризована. Одну достаточно большую кластверизацию я не указал, ибо мне стало лень тратить время на перелопачивание всех работ — речь о задаче 1, где автомат построен не по алгоритму и доказательство кривое с долгим и нудным расписыванием  почему там на цикле именно звёздочка. Участники и так наказаны —+.

 

Общая беда — доказательства в одну сторону. Если необходимо доказать, что два языка равны, а вы в доказательстве пользуетесь индукцией, то в 95% случаев, вы доказываете только в одну сторону: либо $L \subseteq L({\cal A})$, либо $L({\cal A}) \subseteq L$. 

 

Ещё одна распространённая проблема — в задаче 7 просто указаны значения префикс-функции. Это не полный протокол, потому что, например, на символе $b$ в $abba\#abb{\bf b}ababbab$ значение префикс функции не просто меняется на $0$, а сначала меняется на $l[3]$,  а затем идёт проверка  на то, можно ли продолжить $l[3]$. Если в вашем решении это не отражено, значит вы предъявили не протокол.

 

Ликбез


20 Сентября 2013

Настал момент, когда нам потребуется работать со стандартными вещами, которые вы должны были изучить в рамках курса дискретного анализа. Однако, как показывает практика, большинство из вас с высокой вероятностью не слышали о части из них, а может и обо всех них вообще или хорошо успели их забыть. Вообще, весь курс дискретного анализа стоит знать хорошо, в следующем семестре жизни без него совсем не будет. Стоит вспомнить вещи, связанные с теорией групп, особенно факторизациюнормальные подгруппы, ${\mathbb Z}_n$ (кольца вычета по модулю n), отношение эквивалентности, гомоморфизмы. В ближайшее время мы будем тесно работать с тремя последними.

Я предлагаю воспользоваться книжкой «Дискретный Анализ. Основы высшей алгебры», которая должна быть хорошо вам знакома. Также я рекомендую ознакомиться с главой 0 из книжки Сипсера — в ней хорошо объясняется что такое доказательство, какие они бывают вообще, а также рассказывается о материале курсов по теоретической информатике в целом. И вообще книжка замечательная, её почти полностью покрывают наши курсы Дискретный анализ, ТРЯП и Алгоритмы и Модели Вычислений и я очень рекомендую её прочесть всем, кому интересна эта наука.

 

Первое задание


17 Сентября 2013

Первое задание проверено и его результаты разосланы. Если вы сдали задание, но не получили от меня ответ, напишите мне об этом.

Технические замечания. При компиляции Latex $\to$ PS/DVI $\to$ PDF текстовой слой в PDF становится кракозябрами. Пользуйтесь, пожалуйста, pdflatex, который переводит Tex в PDF без промедуточных форматов.

Пожалуйста, не присылайте файлы в архивах. Если высылаете новую версию файла, пожалуйста оставьте ту же тему письма.

 

Информация


15 Сентября 2013

Задания необходимо сдавать до 23:00 вторника перед соответствующим семинаром. За опоздания идут штрафные очки по 0.1 за каждый час. Высылайте задания на homework@rubtsov.su, письма с вопросами на этот адрес, пожалуйста, не отправляйте!