Экзаменационные вопросы по дискретной математике

Экзаменационные вопросы по дискретной математике

(2007 год, 8 факультет, 2 семестр)

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. Двоичный(m,n)-код. Расстояние Хемминга. Обнаружение и исправление ошибок.

27. Матричное кодирование. Групповые коды.

28. Коды Хемминга.

29. Сочетания и размещения.

30. Бином Ньютона. Полиномиальная формула.

31. Треугольник Паскаля и его свойства.

32. Формула включения и исключения для числа объектов не обладающих данными свойствами.

33. Нахождения количества целочисленных решений системы.