Автоматы и производящие функции|Дмитрий Голубенко|Семинар КТ №5

Как правило, олимпиадные задачи появляются сами по себе, мотивация формулировки же остается за кадром. Мы посмотрим, как за одной из задач олимпиады Патнема скрывается нетривиальная связь алгебры и теоретической информатики. Гость канала полагает, что слушатели владеют школьной математикой, остальные же понятия постарается объяснить по ходу рассказа. Таймкоды 00:00 начало 03:00 производящие функции 04:45 числа Фибоначчи 08:20 проблема с интернетом :( 12:05 продолжение примера 15:30 условие задачи 20:45 алфавиты и грамматики 23:05 контекстно-свободные грамматики 30:00 числа Каталана 40:50 производящая функция грамматики 47:30 теорема Хомского-Шютыенбергера 55:45 конечные автоматы 01:17:35 автомат для нашей задачи 01:24:00 автоматные (регулярные) грамматики 01:27:00 производящая функция автомата 01:36:30 Теорема Майхилла – Нероде 01:45:25 автомат с выходами 01:50:00 теорема Кристли про p-автоматные последовательности 02:08:00 завершение