https://wikicshse.ru/index.php?action=history&feed=atom&title=AT-25-26AT-25-26 - История изменений2026-06-06T09:57:41ZИстория изменений этой страницы в викиMediaWiki 1.45.3https://wikicshse.ru/index.php?title=AT-25-26&diff=60&oldid=previmported>Jpridgeway: Migrated current public revision from wiki.cs.hse.ru2026-04-07T17:20:13Z<p>Migrated current public revision from wiki.cs.hse.ru</p>
<p><b>Новая страница</b></p><div>= Теория автоматов, формальные языки, регулярные выражения (ОП ПМИ 4 курс), весна 2026 =<br />
<br />
Лекции проходят по субботам, 11:10–12:30. Первая лекция – 24 января 2026.<br />
<br />
Семинары проходят по субботам, 13:00–14:20. Первый семинар - 24 января 2026.<br />
<br />
Аудитория меняется, будет указана в РУЗе.<br />
<br />
==Контакты== <br />
<br />
Лектор и семинарист: [https://www.hse.ru/org/persons/218355200/ Запрягаев Александр Александрович], azapryagaev@hse.ru, телеграм: azapryagaev<br />
<br />
Группа в Телеграм: https://t.me/+ymCEMU8dmLVkMzJi<br />
<br />
==Информация==<br />
<br />
[https://drive.google.com/file/d/1o2aMcY2Zu4wSTuvo_8g75NvQLgZyE62I/view?usp=sharing Подробная информация]<br />
<br />
===Аннотация===<br />
<br />
Курс «Теория автоматов, формальные языки, регулярные выражения» познакомит слушателей одной из самых быстро развивающихся дисциплин теоретической информатики – теорией автоматов. Мы рассмотрим, как язык конечных автоматов применяется в алгебре и компьютерной лингвистике, позволяет исследовать грамматику реальных языков и языков программирования, характеризовать устройство алгебраических структур. Будут доказаны теоремы о выразительной силе формальных языков и алгоритмической разрешимости и неразрешимости различных классов структур, выражающихся автоматами.<br />
<br />
===Цели освоения курса===<br />
<br />
* Овладеть различными видами формальных грамматик на различных уровнях иерархии Хомского<br />
* Познакомиться с основными алгоритмами теории конечных автоматов<br />
* Научиться строить регулярные выражения<br />
* Уметь распознавать языки, не выразимые грамматиками или автоматами<br />
* Знать соответствия между разновидностями автоматов и различными категориями грамматик<br />
* Овладеть арифметиками Бюхи как методом проверки структур на автоматность<br />
* Изучить основные результаты об автоматности алгебраических структур<br />
<br />
===Планируемые результаты===<br />
* Уметь классифицировать формальные языки в соответствии с иерархией Хомского<br />
* Составлять грамматики и регулярные выражения, задающие конкретные формальные языки<br />
* Доказывать нераспознаваемость языков в грамматиках различного вида<br />
* Составлять конечные автоматы, соответствующие грамматикам, и наоборот<br />
* Детерминизовывать конечные автоматы<br />
* Знать роль арифметик Бюхи в представлении автоматных структур<br />
* Проверять автоматность произвольных алгебраических структур построением их представления в арифметиках Бюхи<br />
<br />
===Пререквизиты курса===<br />
Некоторый опыт в работе с математическими доказательствами<br />
Знакомство с основными структурами алгебры (группы, кольца, поля), а также с языком логики предикатов полезно, но не обязательно.<br />
<br />
==Отчётность по курсу и критерии оценки==<br />
<br />
* '''Проверочные работы''': Проводятся из расчёта примерно одной работы на 2 семинара в конце семинарских занятий и посвящены темам лекций и семинаров, пройденных с момента предыдущей проверочной работы.<br />
Решение каждой работы оценивается от 0 до 3 баллов. Итоговая оценка составляет 10*(набранное число баллов/(3*число проверочных работ)).<br />
* '''Письменное домашнее задание''': Выдаётся дважды за курс: по грамматикам и по конечным автоматам. Дедлайн первого - до начала лекции 6. Дедлайн второго - до контрольной работы.<br />
У каждой задачи указано количество баллов за неё, суммарное количество >10. Оценка равняется 0,5*min(20,сумма баллов, набранных за все задачи).<br />
* '''Контрольная работа''': Проводится во время и в аудитории семинара 9. Разрешено пользоваться написанными от руки собственными конспектами, но не распечатанными материалами и не электронными устройствами. Пересдача по уважительной причине проводится во время экзамена.<br />
Решение каждой задачи оценивается из максимума в 3 балла, до максимума 15 баллов (5 задач). Оценка равняется (2/3)*(баллы за задачи).<br />
* '''Экзамен''': Проводится в сессию 3 модуля в формате, идентичном контрольной работе, но вопросы включают не только задачи, но и определения, формулировки и простые доказательства.<br />
Решение каждой задачи оценивается из максимума в 3 балла, до максимума 15 баллов (5 задач). Оценка равняется (2/3)*(баллы за задачи).<br />
* '''Пересдача''': Первая пересдача проводится в формате, аналогичном экзамену, и представляет собой пересдачу экзамена. Формула итоговой оценки не меняется. Вторая пересдача (с комиссией) проводится в формате, аналогичном экзамену. Формула оценки не меняется.<br />
<br />
===Формула оценки и пересдачи===<br />
Накопленная оценка = Округление(0,3*проверочные+0,3*домашние задания+0,4*контрольная работа).<br />
<br />
Округление арифметическое.<br />
<br />
Если Накопленная оценка >=8, то то студент может получить Накопленную оценку в качестве итоговой оценки, не приходя на экзамен.<br />
<br />
В противном случае применяется формула:<br />
<br />
Оценка = 0.7*(Накопленная оценка)+0,3*(Экзамен).<br />
<br />
==Прочитанные лекции==<br />
<br />
[https://drive.google.com/file/d/11m--ZLP_YmGjjOQ2tWJsw6R9jnWfIzzc/view?usp=sharing Конспект лекций 1–8 и листки домашних заданий 1-2]<br />
<br />
====Лекция 1 (24 января)====<br />
Формальные языки. Порождающие грамматики. Основные классы порождающих грамматик.<br />
<br />
====Лекция 2 (31 января)====<br />
Конечные автоматы. Теоремы о нормальной форме конечных автоматов. Детерминированные конечные автоматы.<br />
<br />
====Лекция 3 (7 февраля)====<br />
Автоматные языки. Булевы операции над автоматными языками. Лемма о накачке. Примеры неавтоматных языков.<br />
<br />
====Лекция 4 (14 февраля)====<br />
Синтаксис регулярных выражений. Регулярные выражения и автоматы.<br />
<br />
====Лекция 5 (21 февраля)====<br />
Выводы в контекстно-свободных грамматиках. Однозначные грамматики. Нормальная форма Хомского.<br />
<br />
====Лекция 6 (28 февраля)====<br />
Лемма о накачке для контекстно-свободных языков. Булевы операции над контекстно-свободными языками.<br />
<br />
====Лекция 7 (5 марта)====<br />
Стековые автоматы. Автоматное представление контекстно-свободных языков.<br />
<br />
====Лекция 8 (7 марта)====<br />
Системы соответствий Поста. Неразрешимые проблемы в теории формальных языков.<br />
<br />
====Лекция 9 (19 марта)====<br />
Арифметическое представление автоматных языков. Арифметики Бюхи.<br />
<br />
==Ведомость==<br />
[https://docs.google.com/spreadsheets/d/1ASVeatepX-EBO0SDCnTD42Aq9egwlOfXnA392xVrrwc/edit?usp=sharing Ведомость курса]<br />
<br />
==Литература==<br />
* Eilenberg S., Tilson B. Automata, languages, and machines (Vol. A and B). – Нью-Йорк, Лондон: Academic press, 1974.<br />
* Пентус А. Е., Пентус М. Р. Теория формальных языков. – М.: Мехмат МГУ, 2004.<br />
* Khoussainov B., Nerode A. Automatic presentations of structures //International Workshop on Logic and Computational Complexity. – Berlin, Heidelberg : Springer Berlin Heidelberg, 1994. – С. 367-392.<br />
* Bruyère V. et al. Logic and p-recognizable sets of integers //Bulletin of the Belgian Mathematical Society Simon Stevin. – 1994. – Т. 1. – №. 2. – С. 191–238.</div>imported>Jpridgeway