ПРИЛОЖЕНИЕ № 1. Перечень вопросов для проверки практических

навыков студентов по дисциплине «Дискретная математика»

1. Доказательство тождеств с множествами.
2. Построение булеана данного множества.
3. Основные формулы алгебры множеств.
4. Доказательство тождеств с декартовыми произведениями, бинарными отношениями, функциями.
5. Нахождение области определения, области значений бинарного отношения, обратного бинарного отношения, композиции.
6. Исследование бинарных отношений специального вида: доказательство рефлексивности (иррефлексивности), симметричности, антисимметричности, транзитивности.
7. Эквивалентность.
8. Арифметические операции с кардинальными числами.
9. Правила суммы и произведения.
10. Решение задач на основные формулы комбинаторики (перестановки, размещения, сочетания).
11. Бином Ньютона.
12. Свойства биномиальных коэффициентов.
13. Формула включений и исключений.
14. Нахождение производящей, экспоненциальной производящей функции для данной последовательности.
15. Нахождение последовательности, для которой данная функция является производящей, экспоненциальной производящей.
16. Действия над производящими функциями.
17. Применение производящих функций для доказательства комбинаторных тождеств.
18. Производящие функции выборок для некоторых схем выбора.
19. Метод рекуррентных соотношений.
20. Решение линейных рекуррентных уравнений с постоянными коэффициентами.
21. Упорядочение дуг и вершин орграфа.
22. Экстремальные задачи теории графов (алгоритм Дейкстры, Беллмана-Мура, Прима, нахождения максимального пути и др.).
23. Распознавание эйлеровости и гамильтоновости графа. Нахождение эйлерова цикла, гамильтонова контура и пути.
24. Нахождение фундаментальных циклов.
25. Алгоритм укладки графа на плоскости.
26. Оценка хроматического числа графа.
27. Алгоритм Форда-Фалкерсона.
28. Построение потока минимальной стоимости.
29. Распознавание однозначности кодирования (теорема Маркова, неравенство Макмиллана).
30. Вычисление избыточности кода.
31. Код Хаффмена.
32. Кодовое расстояние Хемминга.
33. Код Хемминга, исправляющий одну ошибку.

Дата добавления: 2015-07-20