Перенос пересдачи
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, письма с вопросами на этот адрес, пожалуйста, не отправляйте!
