- •Темы контрольных работ по дискретная математика
- •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. Решетки.
29. Последовательности над конечным полем.
Современная криптография черпает свои методы из математики и
информатики. При решении проблем кодирования широко используются алгебраические методы, в частности, алгебра последовательностей над конечным полем. В контрольной работе должны быть рассмотрены вопросы:
1) Понятие кода, кодирования, декодирования информации (/2/, с.253-255, /3/, с.238-240).
2) Псевдослучайные последовательности и их применение в криптографии (/1/, с. 49-51).
3) Алгебра последовательностей над конечным полем (/1/, с. 51-53).
4) Линейные последовательности над конечным полем (/1/, с. 53-56, /2/, с. 397-418).
Литература, рекомендуемая для изучения темы
1 Нечаев В.И. Элементы криптографии (Основы теории защиты
информации): Учеб. пособие для ун-тов и пед. вузов/ Под ред. В.А.
Садовничего – М.: Высш. шк.,1999.
2 Лидл Р., Пильц Г. Прикладная абстрактная алгебра: Учеб. пособие/
Пер. с англ. – Екатеринбург: Изд-во Урал. ун-та, 1996.
3 Берлекэмп Э. Алгебраическая теория кодирования. – М.: Мир, 1971.
30. Решетки.
Понятие решетки играет важную роль в алгебре и дискретной математике. В контрольной работе необходимо изучить характеристические
свойства решеток как упорядоченных множеств и как алгебр с двумя бинарными операциями, проанализировать взаимосвязь основных свойств
решеток, доказать критерии модулярности и дистрибутивности решеток.
Рекомендуется следующий план работы:
1) Изучить характеристические свойства решеток, доказать их основные свойства (/1/, глава 2, р. 4; /2/, глава 1, § 1; /3/, глава 2, § 2.4).
2) Рассмотреть основные классы решеток и доказать критерии модулярности и дистрибутивности решеток (/1/, глава 2, р. 4; /2/, глава 1, § 1;
/3/, глава 2, § 2.4).
Литература, рекомендуемая для изучения темы
1 Кон П., Универсальная алгебра. – М.: Мир, 1968.
2 Лидл Р., Пильц Г., Прикладная абстрактная алгебра. – Екатеринбург:
Изд-во УрГУ, 1996.
3 Богомолов А.В., Салий В.Н. Алгебраические основы теории
дискретных систем. – М.: Наука, 1997.