Вопросы № 1-25 к экзамену по курсу “Дискретная математика” (Бинарные отношения, их свойства. Отношения эквивалентности и порядка. Булева алгебра)

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

ЭКТ-III, 2003г.

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. Булева алгебра.

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

ЭКТ-III, 2003г.

1. На множестве из трех элементов уметь приводить примеры бинарных отношений,

являющихся или не являющихся: рефлексивными, симметричными, антисимметричными, транзитивными, отношениями эквивалентности или порядка.

2. Знать определение группы.
3. Хорошо разобраться с группой движения треугольника. ( Знать что такое движение, какие движения входят в группу движения треугольника, каков их геометрический смысл, как перемножаются движения, в каком порядке действует произведение движений на точки треугольника и т.д. ).
4. Знать, что такое группа и кольцо Z_n вычетов по модулю n. При каких n кольцо

Z_n будет полем.

5. Знать, что такое (7,4)-код Хемминга.
6. Уметь находить фундаментальные циклы и разрезы для данного связанного

графа и выбранного остова.

7. Уметь записывать совершенную дизъюнктивную нормальную форму ( СДНФ )

Для булевой функции, заданной своей таблицей истинности.