Множество вопросов к зачету/экзамену по спецкурсу «Комбинаторика слов» (Шур А. М.)



Скачать 14.59 Kb.
Дата08.10.2012
Размер14.59 Kb.
ТипДокументы
Множество вопросов

к зачету/экзамену по спецкурсу «Комбинаторика слов»

(Шур А.М.)

1. Слова и языки. Конкатенация. Уравнение XY=YX. Примитивные слова. Отношение сопряженности. Сохранение примитивности. Классы сопряженности. Уравнение XY=YZ.

2. Периоды слова. Экспонента слова. Лексикографический порядок. Слова Линдона-Ширшова. Экспонента слов Л-Ш. Теорема Линдона.

3. Свойство взаимодействия периодов. Теорема Файна-Вильфа. Точность оценки. Следствие о числе различных букв в слове.

4. Частичные слова. Глобальные и локальные периоды ЧС. Длина взаимодействия. Невзаимодействие локальных периодов. Теорема о взаимодействии периодов ЧС.

5. Локальный период слова в точке. Теорема о критическом разбиении. Критерий периодичности бесконечного слова.

6. Морфизмы. Задание бесконечных слов морфизмами. Слова Туэ-Морса. «Равновесное» разбиение натурального ряда на два класса.

7. Избегаемость. Шаблоны. Отношение избегаемости, его простейшие свойства. Избегаемые экспоненты. Несводимость «шаблонной» и «степенной» избегаемости друг к другу.

8. Теоремы Туэ: 2-Избегаемость экспоненты 2+ , 3-избегаемость экспоненты 2.

9. Гипотеза Дежан. Доказательство нижней оценки. Случай n=3. Кодировка Пансьё.

10. Избегание морфизмами. Сохранение экспонент морфизмом Туэ-Морса. Классификация бинарных 2+-свободных морфизмов.

11. Неизбежные шаблоны. Слова Зимина, их свойства. Связки и свободные множества. Стирания. Теорема Бина-Эренфойхта-Макналти-Зимина.

12. Комбинаторная сложность языка. Сложность бесконечного слова. Теорема о поведении сложности БС. Сложность слова Фибоначчи. Слова Штурма. Теорема классификации бесконечных слов, порожденных морфизмами.

13. Комбинаторная сложность регулярных языков.

Основной источник: Шур А.М., Комбинаторика слов. Учебное пособие. Изд-во УрГУ, 2003.

Другие полезные источники, к примеру, Choffrut C., Karhumäki J., Combinatorics of words. In: Rosenberg G., Salomaa A. Eds., Handbook of formal languages. Berlin, 1997. V.1, Ch.6, 329-438, могут быть без труда нагуглены.

Похожие:

Множество вопросов к зачету/экзамену по спецкурсу «Комбинаторика слов» (Шур А. М.) icon«Крайнов» хушамат пулса кайни
Крайнов Иван пулса т=н=. Ял хушшинче в=л в=х=тра =на ёак хушаматпа никам та ч\нмен, пурте Шур Иван тесе калан=. Ачисене те Шур Иван...
Множество вопросов к зачету/экзамену по спецкурсу «Комбинаторика слов» (Шур А. М.) icon7-8 классы Модуль 1: Основы теории множеств
С математической точки зрения вместо разных слов можно использовать одно «множество»: множество учеников, множество берез, множество...
Множество вопросов к зачету/экзамену по спецкурсу «Комбинаторика слов» (Шур А. М.) iconВопросы к зачету/экзамену по спецкурсу «Теория неотрицательных матриц и ее приложения»
Оценки корня Фробениуса: через строчные суммы, через координаты вектора и его образа
Множество вопросов к зачету/экзамену по спецкурсу «Комбинаторика слов» (Шур А. М.) iconВопросы к зачету/экзамену по спецкурсу «Языки и автоматы»
...
Множество вопросов к зачету/экзамену по спецкурсу «Комбинаторика слов» (Шур А. М.) iconПримерный перечень вопросов к зачёту (экзамену) по курсу
Окрестности. Свойства окрестностей. Типы точек по отношению к заданному множеству
Множество вопросов к зачету/экзамену по спецкурсу «Комбинаторика слов» (Шур А. М.) iconКак организовать подготовку к экзамену?
Перед сессией студентов волнует множество вопросов: как успеть подготовиться ко всем экзаменам, где взять дополнительное время для...
Множество вопросов к зачету/экзамену по спецкурсу «Комбинаторика слов» (Шур А. М.) iconПримерный перечень вопросов к экзамену и зачету по курсу
Эсхил – «отец трагедии». Символическое истолкование образа Прометея и его судьба в последующей культуре
Множество вопросов к зачету/экзамену по спецкурсу «Комбинаторика слов» (Шур А. М.) iconПеречень вопросов к экзамену и зачёту (последние помечены *)
Определение полного метрического пространства. Примеры. Подпространство. Полнота пространства
Множество вопросов к зачету/экзамену по спецкурсу «Комбинаторика слов» (Шур А. М.) iconОтношения эквивалентности и комбинаторика
Определение. Пусть m – множество. Произвольное множество упорядоченных пар элементов из м называется отношением на M. Если, то пишут...
Множество вопросов к зачету/экзамену по спецкурсу «Комбинаторика слов» (Шур А. М.) iconКафедра Математической теории интеллектуальных систем (Матис) 2010-2011 учебный год Список вопросов к зачёту по спецкурсу Г. И. Сыркина «Введение в алгоритмическую алгебру. Часть 2»
Теорема Аккермана о мажорируемости всех одноместных примитивно рекурсивных функций двуместной функцией в и одноместной диагональной...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org