Комбинаторика слов и ее приложения. Лекция 9. Бесповторность
ЛекцияПредмет:
- Computer Science
Лектор:
Курс лекций:
Дата записи:
26.03.15
Дата публикации:
01.07.15
Код для блога:
Бесповторность. Квадраты и кубы. Слова Туэ-Морса, теорема о сильной бескубности. Избегаемые экспоненты. Слова Аршона, теорема о 7/4. Граничная теорема (гипотеза Дежан). Цилиндрические слова. Бесповторные раскраски графов. Циклические слова и граф К33 Шаблоны, их избегание. Неизбежные шаблоны. Слова Зимина. Критерий неизбежности (Бина- Эренфойхта-Макналти-Зимина). Алгоритмические проблемы о словах Зимина. Генератор случайных бесквадратных слов.
Другие лекции курса
11