Программа экзамена
по курсу “Дискретная математика”
ЭКТ-III, 2003г.
- Бинарные отношения, их свойства. Отношения эквивалентности
и порядка.
- Группы. Гомоморфизмы и изоморфизмы.
- Подгруппы. Теорема Лагранжа.
- Нормальные подгруппы. Фактор группы.
- Циклические группы. Теорема о строении конечных абелевых
групп.
- Кольцо, тело, поле.
- Строение конечных полей.
- Линейные коды.
- Коды Хемминга.
- Циклические коды.
- БЧХ коды.
- Графы. Основные понятия.
- Деревья.
- Помеченные графы. Код Прюфера.
- Алгоритм Краскала.
- Метод ветвей и границ.
- Фундаментальные циклы и разрезы.
- Линейные пространства, связанные с графами.
- Матрицы, связанные с графами.
- Планарные графы.
- Алгоритм плоской укладки графа.
- Булевы функции.
- Полные системы и замкнутые классы булевых функций.
- Критерий Поста.
- Булева алгебра.
Программа минимум
по курсу “Дискретная математика”
ЭКТ-III, 2003г.
- На множестве из трех элементов уметь приводить примеры
бинарных отношений,
являющихся или не являющихся:
рефлексивными, симметричными, антисимметричными, транзитивными, отношениями
эквивалентности или порядка.
- Знать определение группы.
- Хорошо разобраться с группой движения треугольника. (
Знать что такое движение, какие движения входят в группу движения
треугольника, каков их геометрический смысл, как перемножаются движения, в
каком порядке действует произведение движений на точки треугольника и т.д.
).
- Знать, что такое группа и кольцо Zn вычетов по модулю n. При каких n кольцо
Zn будет
полем.
- Знать, что такое (7,4)-код Хемминга.
- Уметь находить фундаментальные циклы и разрезы для данного
связанного
графа и выбранного остова.
- Уметь записывать совершенную дизъюнктивную нормальную
форму ( СДНФ )
Для булевой функции, заданной
своей таблицей истинности.