Вопросы к экзамену по дискретной математике
жүктеу/скачать 33,5 Kb.
|
Вопросы по ДМ для подготовки к экзамену, зачёту (1)
|
Вопросы к экзамену по дискретной математике (АВТФ, 2 семестр) 1. Множества. Основные операции над множествами и их свойства. Диаграммы Эйлера-Венна. Декартово произведение множеств. 2. Отношения и бинарные отношения, область определения, область значения, обратные отношения. Произведение отношений. 3. Функции. Инъекции, сюръекции, биекции. Понятие последовательности. 4. Множество натуральных чисел. Два подхода к определению множества натуральных чисел. Аксиомы Дедекинда-Пеано. Принцип математической индукции. 5. Понятие мощности множества. Сравнение мощностей. Теорема Кантора-Бернштейна. Операции над кардинальными числами. 6. Конечные, счетные, континуальные множества. Мощность булеана. 7. Матрицы бинарных отношений, их свойства. Специальные бинарные отношения. 8. Отношения эквивалентности и разбиения. Фактор-множества. Матрица отношения эквивалентности. 9. Отношения порядка. Максимальные и минимальные, наибольший и наименьший элементы частично упорядоченного множества. Диаграммы Хассе. Линейно упорядоченные множества. Лексикографический порядок и порядок Парето. 10. Алгебраические системы: определение и примеры. Понятие полугруппы, моноида, группы; задание их с помощью таблицы Кэли. 11. Морфизмы алгебраических систем. 12. Подсистемы. Термы сигнатуры S. Подсистема, порожденная множеством, ее структура. 13. Конгруэнции, фактор-алгебры, теорема о гомоморфизме. 14. Решетки. Дистрибутивные решётки. 15. Булевы алгебры. Теорема Стоуна. Принцип двойственности для булевых алгебр. 16. Виды и способы задания графов. 17. Подграфы и части графа. Операции над графами. n-Мерные кубы. Изоморфные графы. 18. Маршруты, циклы, цепи. Достижимость и связность (матрицы достижимости, контрдостижимости, связности). 19. Расстояние в графах. Центральные и периферийные вершины. 20. Взвешенное расстояние. Алгоритм Форда-Беллмана. Алгоритм Дейкстры. 21. Степени вершин. Лемма о рукопожатиях. Эйлеровы графы, циклы, цепи. Алгоритм построения эйлерова цикла. 22. Гамильтоновы графы. Постановка задачи коммивояжера. 23. Деревья, леса. Остовы графов. Цикломатическое число, коранг. Алгоритм построения остова минимального веса. Обходы графов по глубине и ширине. Упорядоченные и бинарные деревья. 24. Фундаментальные циклы, разрезы. Матрицы фундаментальных циклов, разрезов. 25. Раскраска графов. 26. Планарные графы. 27. Формулы алгебры логики, их таблицы истинности. 28. Булевы функции, способы их задания. Представление булевых функций формулами. 29. Эквивалентность формул. 30. Двухэлементная булева алгебра. Алгебра булевых функций. Фактор-алгебра алгебры формул. 31. Дизъюнктивные и конъюнктивные нормальные формы. Алгоритм приведения формулы к ДНФ и КНФ. 32. Теорема о функциональной полноте. Способы построения СДНФ и СКНФ. 33. Импликанты, простые импликанты. Сокращенные, тупиковые, минимальные нормальные формы. Алгоритм Квайна построения МДНФ. 34. Карты Карно. Построение МДНФ с помощью карт Карно. 35. Принцип двойственности. Самодвойственные функции. 36. Теорема Жегалкина. Способы построения полиномов Жегалкина. Линейные функции. 37. Классы Поста. Полные системы булевых функций. Теорема Поста. Базисы. 38. Логические сети. Реализация булевых функций контактными схемами и схемами из функциональных элементов. Литература: Судоплатов С.В., Овчинникова Е.В. Дискретная математика: Учебник. жүктеу/скачать 33,5 Kb. Достарыңызбен бөлісу:
|