Формальные языки, 2 курс, весна 2016 — различия между версиями
Материал из SEWiki
Darnley (обсуждение | вклад) |
|||
| Строка 1: | Строка 1: | ||
| − | '''Лекции:''' Михаил Эдуардович Дворкин | + | '''Лекции:''' Михаил Эдуардович Дворкин (<b>mikhail.dvorkin@gmail.com</b>) |
'''Практика:''' Николай Карпов (I подгруппа), Михаил Слабодкин (II подгруппа). | '''Практика:''' Николай Карпов (I подгруппа), Михаил Слабодкин (II подгруппа). | ||
| + | |||
| + | == План == | ||
| + | |||
| + | Лекция 1 | ||
| + | * Языки и yes/no-задачи. Теоретико-множественное доказательство невозможности описания языков. | ||
| + | * Детерминированные конечные автоматы. Принятие слова. | ||
| + | * Эквивалентность состояний. Минимизация ДКА. | ||
| + | Лекция 2 | ||
| + | * Правые контексты. | ||
| + | * Эквивалентность ДКА. | ||
| + | * Прямое произведение ДКА. | ||
| + | * Динамическое программирование по ДКА. | ||
== К занятиям Николая Карпова == | == К занятиям Николая Карпова == | ||
| Строка 10: | Строка 22: | ||
[https://docs.google.com/spreadsheets/d/13ELlUZn098B5opdQrn1UWfMmDbwosVZ5vKNX7NZDGc8/edit Результаты] | [https://docs.google.com/spreadsheets/d/13ELlUZn098B5opdQrn1UWfMmDbwosVZ5vKNX7NZDGc8/edit Результаты] | ||
| + | |||
| + | == Ссылки == | ||
| + | |||
| + | * Важная книга для первой части курса: Хопкрофт, Мотвани, Ульман. Введение в теорию автоматов, языков и вычислений. | ||
| + | * [http://neerc.ifmo.ru/wiki/index.php?title=Теория_формальных_языков] | ||
| + | * [http://www.ics.uci.edu/~goodrich/teach/cs162/notes/] | ||
| + | * [http://www.eecs.wsu.edu/~ananth/CptS317/] | ||
| + | * [http://users.utu.fi/jkari/automata/fullnotes.pdf] | ||
Версия 13:51, 1 марта 2016
Лекции: Михаил Эдуардович Дворкин (mikhail.dvorkin@gmail.com)
Практика: Николай Карпов (I подгруппа), Михаил Слабодкин (II подгруппа).
План
Лекция 1
- Языки и yes/no-задачи. Теоретико-множественное доказательство невозможности описания языков.
- Детерминированные конечные автоматы. Принятие слова.
- Эквивалентность состояний. Минимизация ДКА.
Лекция 2
- Правые контексты.
- Эквивалентность ДКА.
- Прямое произведение ДКА.
- Динамическое программирование по ДКА.
