ТРЯП 2020

 

Лекции

  • 1. Алгебра регулярных выражений. Конечные автоматы  
  • 2. Конечные автоматы  
  • 3. Недетерминированные конечные автоматы  
  • 4. Конечные автоматы и алгоритмы обработки текстов  
  • 5. Структурные свойства регулярных языков  
  • 6. Суффиксные автоматы. Формалные грамматики  
  • 7. Контекстно-свободные грамматики  
  • 8. Автоматы с магазинной памятью  
  • 9. Структурные свойства КС-языков  
  • 10. LL-анализ  
  • 11. Атрибутные грамматики  
  • 12. LR-анализ  .  Презентация , текст про LR-анализ 

Листки (901+)

  • Задание 1         листок семинара  
  • Задание 2         листок семинара  
  • Задание 3         листок семинара  
  • Задание 4         листок семинара  
  • Задание 5         листок семинара  
  • Задание 6         листок семинара  
  • Задание 7         листок семинара   
  • Задание 8      
  • Задание 9         листок семинара   
  • Задание 10       листок семинара  
  • Задание 11: № 56.2, № 57 по каноническому заданию
  • Задание 12     (задание на всю тему LR, не сдаётся на проверку)

 

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

На еженедельных контрольных можно пользоваться любыми печатными и письменными материалами, любые электронные устройства запрещены: формат OPENBOOK/NODEVICE. Пожалуйста НЕ архивируйте свою файлы при отправке по почте. Это затрудняет проверку.

Теория к домашним заданию по теме «регулярные языки и конечные автоматы» приведена в книжке   , которую можно взять в библиотеке.

 

Формат второй семестровой контрольной


01 Декабря 2020

Вторая семестровая контрольная будет состоять из двух частей: тестовая часть и содержательные задачи. До второй части допускаются только студенты, хорошо выполнившие тестовую часть. Если тестовая часть выполнена недостаточно хорошо, то за контрольную выставляется оценка «удовлетворительно» или «неудовлетворительно». Начало контрольной в понедельник 7 декабря в 10:45. Обе части контрольной планируется дать на 1:20 с перерывом 15 минут между частями (оценки за тестовую часть будут вычислены автоматически).

Проверка тестовых задач будет осуществляться с помощью тестирующей системы. Я разослал токены по email-адресам, которые у меня были с прошлого года (проверьте папку спам!). Если вы писали в прошлом году тест по алгоритмам и не получили письмо, то подождите полдня — если письмо не придёт заполните форму. Если вы не писали в прошлом году тест по алгоритмам — сразу заполняйте форму. 

Для написания содержательной части вам понадобятся чистая бумага и ручка, и подготовленная заранее программа для создания pdf (для телефонов есть программы, которые сразу позволяют копировать в pdf). Отсканированные или хорошо отфотографированные решения нужно будет отправить на специальный почтовый адрес (сообщим позднее). Важно отправить решения в едином pdf-файле с правильным порядком страниц и правильной ориентацией.

 

Вторая семестровая контрольная и оценки автоматом


26 Ноября 2020

Вторая семестровая контрольная состоится в понедельник 7 декабря. Организационная информация будет опубликованна в скором времени.

 

Контрольная будет проходить с помощью прокторинга http://exams.mipt.ru. Большинство из вас уже хорошо знакомо с этой системой, но лучше лишний раз проверить, всё ли у вас работает. Для этого можно подключиться к тестированию проведения контрольной по АЛКТГ в одну из пятниц 27 ноября или 4 декабря с 18:30 до 20:00. Связываться при этом с проктором не обязательно. Если вы не работали ранее с этой системой прокторинга, то пройдите полноценное тестирование системы в рамках тестирования для АЛКТГ (см. информацию на странице АЛКТГ).

 

Вторую контрольную пишут все студенты. Те, кто не писал первую контрольную из-за обучения на дистанте или по уважительной причине. Оценка автоматом в этом случае формируется следующим образом: 60% оценка семинариста, 40% — оценка за КР-II. Последяя должна быть не ниже, чем на 3.0, иначе получения оценки автоматом невозможно. Также есть возможность просто получить оценку семинариста как автомат (в случае, если оценка за КР-II не ниже 3.0).

 

Разослал проверку КР-I


26 Ноября 2020

Я разослал проверку первой семестровой контрольной на адреса, полученные от кафедры. Если Вы не получили результаты проверки — напишите мне письмо.

 

Конструкторы LR-анализаторов


21 Ноября 2020

Ссылки на материалы с лекции размещены рядом с ссылкой на запись лекции. При построении таблицы анализатора и графа автомата Кнута я пользовался пакетом Parsing Table Generator for Compiler Theory, руководство к пакету по ссылке. Рекомендую его попробовать.  

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

 

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

P.S. Спустя 10 лет использования в учебных целях в последнем конструкторе нашли ошибку, так что будьте бдительными. На достаточно простых грамматиках конструктор работает верно 

 

Семинар 13.12


12 Ноября 2020

Семинар 13.12 пройдёт по расписанию в зуме — используйте стандартную ссылку для лекций. 

 

Критерии проверки


09 Ноября 2020

Публикуем критерии проверки первой семестровой контрольной.

 

Показ работ сегодня


09 Ноября 2020

Сегодня, понедельник (9 ноября). 903 КПМ 16.00

Валеев Сергей Валерьевич
Ведерников Роман Алексеевич
Востриков Даниил Дмитриевич
Зарезина Елизавета Михайловна
Зенькова Валерия Витальевна
Ибрагимов Абдульхамид Нурисламович
Каленюк Аким Александрович
Кошелев Егор Артурович
Кошкелян Тигран Артурович
Меликсетян Вячеслав Араикович
Мусатов Георгий Васильевич
Орлов Алексей Станиславович
Полещук Глеб Александрович
Соловьев Михаил
Топоровский Владислав Олегович
Федоров Артём Рубенович
Фомичев Арсений Сергеевич
Черников Тимофей Антонович
Шорин Дмитрий Александрович
Юрманов Данила Иванович
Яремус Дмитрий Константинович

Сегодня, понедельник (9 ноября). 907 КПМ 16.00

Антышев Тихон Глебович
Астанова Камилла Сайфидиновна
Бодрова Юлия Михайловна
Галлямов Ислам Маратович
Гладких Алексей Владимирович
Зятьков Михаил Васильевич
Исыпов Илья Игоревич
Колосов Арсений Владимирович
Королев Алексей Владимирович
Крыжановская Дарья Константиновна
Лукьяненко Иван Андреевич
Малышева Елизавета Владиславовна
Мельников Владимир Алексеевич
Овсянников Кирилл Сергеевич
Рахматов Сунатулло Парвизович
Редкозубова Анастасия Сергеевна
Трифонов Данил Витальевич
Турнова Мария Антоновна
Файзуллин Музаффар Рустамович
Хузин Руслан Робертович
Шевцов Виктор Дмитриевич
Петров Артем

 

Расписание показа работ второй семестровой КР


10 Ноября 2020

Среда 11.11.20, 18.30, 412 ГК

907 Алиев Даниял Камилевич
903 Атласова Екатерина Сергеевна
907 Бердин Артём Андреевич
904 Гайнутдинова Диляра Ильсияровна
902 Гришанов Никита Вадимович
902 Дергачев Дмитрий Игоревич
904 Карначев Сергей Леонидович
906 Кузьминов Александр Александрович
908 Макаров Глеб Евгеньевич
904 Мельникова Елена Андреевна
905 Меркулова Маргарита Дмитриевна
909 Мурадов Тимур Русланович
901 Никишин Максим Андреевич
907 Потурило Евгений Николаевич
904 Салихов Айрат Ильгамович
904 Тураев Виктор Андреевич
903 Федосеев Марк Андреевич
906 Храмов Артем Егорович
904 Хроменков Кирилл Александрович
907 Чумаченко Арина Сергеевна
903 Шаймарданова Диана Ришатовна

Среда 11.11.20, 18.30, 411 ГК

903 Алтынов Алексей Александрович
908 Глазунова Ирина Алексеевна
905 Зайченкова Екатерина Евгеньевна
901 Зинец Анастасия Николаевна
905 Колесников Сергей Владимирович
903 Конин Георгий Олегович
904 Кулигин Дмитрий Александрович
906 Куляпин Александр Алексеевич
901 Латарцев Павел Васильевич
904 Лопатин Илья Александрович
906 Лубин Николай Константинович
904 Ненашев Николай Андреевич
903 Оверчук Анна Дмитриевна
906 Петрушина Ксения Евгеньевна
909 Сенькин Николай Алексеевич
908 Хайдаров Дустмухаммад Илхомович
901 Хожаев Илья Сергеевич
908 Шамбер Элина Владиславовна
909 Широкова Ирина Сергеевна
902 Шушко Андрей Игоревич
773 Захарин Богдан
??? Торшина А. С.

Среда 11.11.20, 18.30, 903 КПМ

902 Алферов Илья Сергеевич
903 Апокин Сергей Антонович
905 Ахмедов Эльдар Шамилович
901 Белопольских Даниил Дмитриевич
901 Высоких Дмитрий Константинович
902 Заречнева Елизавета Никитична
908 Иевлев Артем Александрович
905 Коврижных Дмитрий Юрьевич
901 Кормщикова Валерия Александровна
909 Лунев Леонид Александрович
908 Миронова Наталья Сергеевна
902 Нечитайло Лев Геннадьевич
901 Нистюк Василий Анатольевич
903 Остеров Никита Владиславович
908 Селезнев Григорий Игоревич
908 Ставцев Никита Романович
907 Степанюк Денис Александрович
904 Стрепетов Петр Александрович
908 Сыроваткин Степан Михайлович
909 Телякова Екатерина Алексеевна
905 Шлотова Надежда Евгеньевна
902 Гасанов Тимур

Пятница 13.11.20, 18.30, 903 КПМ   Новая дата показа будет объявлена позже

908 Акшаев Никита Игоревич
901 Баранов Виталий Юрьевич
904 Зайцева Алла Сергеевна
906 Захаров Артемий Сергеевич
906 Кадыгров Евгений Владиславович
909 Касапенко Наталья Алексеевна
902 Корнилов Никита Максимович
908 Кудряшов Антон Александрович
909 Людвиковский Евгений Владиславович
901 Маркелова Анна Михайловна
906 Моложавенко Александр Александрович
909 Мясникова Арина Андреевна
909 Никишин Георгий Сергеевич
909 Панышев Александр Сергеевич
908 Рубаненко Валерий Викторович
905 Рябых Владислав Юрьевич
908 Садыков Сергей Игоревич
909 Тихонова Мария Валерьевна
905 Тумасян Артём Вадимович
909 Усманов Абубакр Алишерович
908 Филонов Роман Сергеевич

 

Семестровая контрольная в понедельник


07 Ноября 2020

Семестровая контрольная в понедельник пройдёт с 9:00 до 12:00. На контрольной нельзя пользоваться никакими вспомогательными материалами.

Распределение по аудиториям

Аудитория определяется по первой букве вашей фамилии:

  • А-К: 115 КПМ
  • Л-О, Ю-Я: 123 ГК
  • П-Э: 110 КПМ 

 

 

Семестровая контрольная I


21 Октября 2020

Первая семестровая контрольная запланированна на понедельник 9 ноября. Мы ещё ожидаем подтверждения брони аудиторий. Вариант для подготовки доступен по ссылке

 

Куртка


18 Сентября 2020

Забытая куртка в 430 ГК находится в гардеробе ГК

 

Сдача домашних заданий (901+)


04 Сентября 2020

Домашние задания нужно отправлять на адрес homework@rubtsov.su до 23:00 четверга (перед семинаром). Все задания принимаются только в формате $\TeX$. Прикрепите к письму два файла: pdf и tex-исходник. Не забудьте указать вашу фамилию и группу в pdf-файле! Не архивируйте файлы!

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

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

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

В качестве редактора, я рекомендую использовать Texmaker. Это довольно удобный кроссплатформенный редактор. Есть также множество онлайн-редакторов — мне понравился Overleaf.

Пожалуйста, присылайте на адрес «homework» только домашние задания. Отправляйте вопросы и обычные письма на адрес alex@rubtsov.su.

 

Не можете войти в zoom? Discord


02 Сентября 2020

Онлайн на лекции в zoom могут присутствовать только 100 человек, поэтому я также буду транслировать лекцию в Discord, где нет ограничения по численности. Чтобы не было путаницы с чатами, я сделал отдельный чат в телеграме — пожалуйста, зайдите в него и задавайте вопросы там.

 

Лекции в zoom


26 Августа 2020

Я буду читать лекции в режиме онлайн через zoom по расписанию занятий (четверг 12:20-13:45), после чего буду выкладывать запись лекции. Постоянная ссылка на zoom-конференцию: https://us02web.zoom.us/j/85886366224.