Перечень экзаменационных вопросов

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. Шары, сферы и циклы в n-мерном кубе. Кодовое расстояние Хемминга. Коды, обнаруживающие и исправляющие ошибки.
34. Код Хемминга, исправляющий одну ошибку.
35. Порождающая и проверочная матрицы кода. Двойственный код.

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