Программа к экзамену по курсу Дискретная математика

Булевы функции

1. Определение Б.Ф., способы задания Б.Ф.

2. Определение СДНФ, СКНФ для Б.Ф.

3. Многочлен Жегалкина, теорема о представлении Б.Ф. многочленом Жегалкина.

4. Способы вычисления коэффициентов многочлена Жегалкина для Б.Ф.

5. Понятие веса Б.Ф., простейшие свойства весов, вес линейной функции.

6. Представление Б.Ф. рядом Фурье.

7. Смысл коэффициентов Фурье, быстрое преобразование Фурье.

8. Функциональная полнота, классы Поста, примеры.

9. Теорема Поста.

Теория графов

1.Основные определения теории графов.

2. Цепи, пути, маршруты в графе. Теорема о числе путей.

3. Минимальный путь, алгоритм построения минимального пути.

4. Нагруженный граф, алгоритм Дейкстры построения кратчайшего пути. Пример.

5. Теорема о корректности работы алгоритма Дейкстры.

6. Понятие связности и сильной связности в графе. Примеры.

7. Оценка числа дуг в графе. Критерий сильной связности

8. Цикловой базис в графе, число векторов в цикловом базисе

9. Деревья, теорема о свойствах деревьев. Критерий связности графа.

10. Алгоритм построения остовного дерева графа, алгоритм построения циклового базиса графа.

11. Алгоритм Краскала построения минимального остовного дерева графа. Пример.

12. Теорема о корректности работы алгоритма Краскала.

13. Корневые деревья, теорема о свойствах корневых деревьев.

14. Необходимое и достаточное условие «быть корневым деревом» для ориентированного графа.

15. Теорема Татта.

16. Понятие Эйлерова графа. Критерий того, что граф Эйлеров для ориентированных и неориентированных графов.

17. Понятие Гамильтонова графа. Достаточное условие того, что граф Гамильтонов.

Теория кодов

1. Основные определения теории кодов, примеры.

2. Корректирующие возможности кодов.

3. Граница Синглтона, МДР-коды, примеры.

4. Граница Хемминга, коды плотной упаковки, примеры.

5. Двоичный код Хемминга, его декодирование.

6. Линейные коды: основные определения, расстояние линейного кода.

7. Декодирование по синдрому.

8. Линейные циклические коды: основные определения, проверочная и порождающая матрица линейного циклического кода.

9. Двойственные коды: основные соотношения.

Комбинаторика

1. Понятие трансверсали, теорема Холла.

2. Перманенты и их свойства, формула Райзера

3. Теорема Биркгофа.

4. Метод включения-исключения. Примеры