- •Темы контрольных работ по дискретная математика
- •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. Решетки.
26. Минимизация чистых автоматов.
Понятие конечного автомата широко применяется при конструировании электронно-вычислительных машин и в компьютерной науке. В контрольной работе необходимо изучить основные понятия теории конечных автоматов, рассмотреть понятие эквивалентных состояний автомата и доказать теоремы об эквивалентных состояниях. Рекомендуется следующий план работы:
1) Изучить основные понятия теории автоматов (/1/, с. 16-18, /2/, с. 446-455, 477-483, /3/, с. 75-79).
2) Разобрать понятия гомоморфизма, покрытия и эквивалентности автоматов. Доказать теоремы об эквивалентных состояниях (/1/, с. 20-25, /3/, с. 81-87).
3) Проанализировать связь понятий эквивалентного и минимального автоматов. Рассмотреть процедуру построения для данного автомата минимального (/2/, с. 501-508, /3/, 87-90).
Литература, рекомендуемая для изучения темы
1 Плоткин Б.И., Гринглаз Л.Я., Гварамия А.А. Элементы
алгебраической теории автоматов. – М.: Высш. школа, 1994.
2 Лидл Р., Пильц Г. Прикладная абстрактная алгебра. – Екатеринбург:
Изд-во Урал. ун-та, 1996.
3 Биркгоф Г., Барти Т. Современная прикладная алгебра. – М.: Мир,
1976.
27. Конструкции чистых автоматов.
Понятие конечного автомата широко применяется при конструировании электронно-вычислительных машин и в компьютерной науке. В контрольной работе необходимо изучить основные понятия теории конечных автоматов, рассмотреть понятия гомоморфизма автоматов, свободного автомата и разобрать вопрос о каскадных соединениях чистых автоматов. Рекомендуется следующий план работы:
1) Изучить основные понятия теории автоматов (/1/, с. 16-18, /2/, с. 446-455, 477-483).
2) Разобрать понятие гомоморфизма автоматов (/1/, c. 20-25).
3) Рассмотреть каскадные соединения абсолютно чистых автоматов (/1/, с. 67-74, /2/, 487-501).
Литература, рекомендуемая для изучения темы
1 Плоткин Б.И., Гринглаз Л. Я., Гварамия А.А. Элементы алгебраической теории автоматов. – М.: Высш. школа, 1994.
2 Лидл Р., Пильц Г. Прикладная абстрактная алгебра. – Екатеринбург:
Изд-во Урал. ун-та, 1996.
28. Цифровое шифрование.
Современная криптология является важным разделом прикладной
математики. В контрольной работе предлагается рассмотреть вопросы, вязанные с алгебраическими методами криптографии. Рекомендуется следующий план изложения материала:
1) Понятие кода, кодирования, декодирования информации (/1/, с.9, /3/, с.253-255).
2) Криптосистема без передачи ключей (/1/, с. 27-28).
3) Криптосистема с открытым ключом (/1/, с. 28-31, /3/, с. 377-397).
4) Электронная подпись (/1/, с. 31-34).
Литература, рекомендуемая для изучения темы
1 Нечаев В.И. Элементы криптографии (Основы теории защиты
информации): Учеб. пособие для ун-тов и пед. вузов/ Под ред. В.А.
Садовничего – М.: Высш. шк.,1999.
2 Лебедев А.Н. Криптография с открытым ключом и возможности ее
практического применения// Защита информации. 1992. Вып. 2. С. 129-147.
3 Лидл Р., Пильц Г. Прикладная абстрактная алгебра: Учеб. пособие/
Пер. с англ. – Екатеринбург: Изд-во Урал. ун-та, 1996.