16. Теорема Рамсея и ее приложения.
Теорема Рамсея является одной из наиболее важных теорем существования в комбинаторике, имеющей самые разнообразные приложения в теории графов, алгебре, теории информации и других разделах математики. Цель контрольной работы – изучить доказательства теоремы Рамсея и рассмотреть приложения этой теоремы к решению алгебраических задач теории полугрупп и регулярных языков. Рекомендуется следующий план работы:
1) Рассмотреть задачу Рамсея о существовании специальных чисел для определенных комбинаторных конфигураций, удовлетворяющих свойству
Рамсея (/1/, с. 340-342; /2/, с. 282-283; /3/, с. 28-30).
2) Разобрать доказательства теоремы Рамсея средствами математической логики и комбинаторными методами теории графов (/1/, с. 342-349; /2/, с. 282-287; /4/, с. 2-4).
3) Рассмотреть приложения этой теоремы к решению алгебраических задач теории полугрупп и регулярных языков (/4/, с. 4-9).
Литература, рекомендуемая для изучения темы
1 Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.
- Темы контрольных работ по дискретная математика
- 1. Эйлеровы графы .
- 2. Гамильтоновы графы.
- 1 Уилсон р. Дж. Введение в теорию графов. – м.: 1977.
- 3. Связность графа.
- 4. Циклы в графах.
- 1 Уилсон р. Введение в теорию графов. – м.: Мир, 1977.
- 5. Плоские графы.
- 1 Уилсон р. Введение в теорию графов. – м.: Мир, 1977.
- 2 Белов в.В., Воробьев е.М., Шаталов в.Е. Теория графов. – м.: вш,
- 3 Березина л.Ю. Графы и их применения: Пособие для учителей. – м.,
- 6. Деревья.
- 1) Изучить такие основополагающие понятия теории графов, как граф, маршрут и цикл (/1/, с. 9-43; /2/, с. 5-22).
- 7. Свойства эйлеровых графов.
- 8. Свойства гамильтоновых графов.
- 1 Уилсон р. Введение в теорию графов. – м.: Мир, 1977.
- 2 Белов в.В., Воробьев е.М., Шаталов в.Е. Теория графов. – м.: вш,
- 3 Березина л.Ю. Графы и их применения: Пособие для учителей. – м.,
- 9. Ориентированные графы.
- 1 Уилсон р. Введение в теорию графов. – м.: Мир, 1977.
- 2 Белов в.В., Воробьев е.М., Шаталов в.Е. Теория графов. – м.: вш,
- 3 Березина л.Ю. Графы и их применения: Пособие для учителей. – м.,
- 10. Паросочетания.
- 1 Уилсон р. Введение в теорию графов. – м.: Мир, 1977.
- 2 Белов в.В., Воробьев е.М., Шаталов в.Е. Теория графов. – м.: вш,
- 4 Березина л.Ю. Графы и их применения: Пособие для учителей. – м.,
- 11. Теория трансверсалей.
- 1 Уилсон р. Введение в теорию графов. – м.: Мир, 1977.
- 2 Белов в.В., Воробьев е.М., Шаталов в.Е. Теория графов. – м.: вш,
- 4 Березина л.Ю. Графы и их применения: Пособие для учителей. – м.,
- 12. Потоки в сетях.
- 1 Уилсон р. Введение в теорию графов. – м.: Мир, 1977.
- 2 Белов в.В., Воробьев е.М., Шаталов в.Е. Теория графов. – м.: вш,
- 4 Березина л.Ю. Графы и их применения: Пособие для учителей. – м.,
- 13. Производящие функции в теории графов.
- 14. Теорема Пойа и перечисление графов.
- 1 Уилсон р. Введение в теорию графов. – м.: Мир, 1977.
- 2 Белов в.В., Воробьев е.М., Шаталов в.Е. Теория графов. – м.: вш,
- 14. Графы на двумерных поверхностях.
- 1 Уилсон р. Введение в теорию графов. – м.: Мир, 1977.
- 2 Белов в.В., Воробьев е.М., Шаталов в.Е. Теория графов. – м.: вш,
- 3 Березина л.Ю. Графы и их применения: Пособие для учителей. – м.,
- 15. Конечные группы и их графы.
- 2 Оре о. Теория графов. – м.: Наука, 1968.
- 16. Теорема Рамсея и ее приложения.
- 2 Оре о. Теория графов. – м.: Наука, 1968.
- 17. Полугруппы преобразований.
- 18. Копредставления полугрупп.
- 19. Логика на словах.
- 20. Алгебры отношений и полугруппы преобразований.
- 21. Рациональные языки.
- Тема 71. Соответствие Эйленберга
- 22. Отношения Грина.
- 23. Декомпозиция конечных моноидов.
- 24. Рациональные и алгебраические языки над полукольцами.
- 25. Элементы теории конечных автоматов.
- 1 Белов в.В., Воробьев е.М., Шаталов в.Е. Теория графов. – м.: вш,
- 26. Минимизация чистых автоматов.
- 27. Конструкции чистых автоматов.
- 28. Цифровое шифрование.
- 29. Последовательности над конечным полем.
- 30. Решетки.