Экзаменационные вопросы (Вопросы к экзамену (Дискра))

Посмотреть архив целиком

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

(2004г. 8 факультет 3 семестр)

1. Эффективная вычислимость. Примитивно рекурсивные функции. Частично рекурсивные функции. Тезис Чёрча.

2. Бинарные операции. Полугруппы. Моноиды.

3. Группы. Примеры. Группы преобразований. Полугруппы. Полугруппы, порождённые множеством.

4. Циклические группы. Свойства. Примеры.

5. Подстановки. Симметрические группы. Разложение подстановки в произведение независимых циклов. Транспозиции.

6. Изоморфизм групп. Свойства. Теорема Кэли.

7. Смежные классы. Теорема Лагранжа.

8. Нормальные делители. Фактор-группа. Сопряженные элементы

9. Гомоморфизм групп. Ядро гомоморфизма. Основная теорема о гомоморфизмах. Свободные группы.

10. Образующие и определяющие соотношения в группе.

11. Кольца. Примеры. Свойства. Подкольца. Кольцо классов вычетов.

12. Делители нуля. Обратимые элементы кольца. Поле. Определения. Примеры. Свойства.

13. Основные понятия теории графов. Изоморфизм, связанность.

14. Матричное задание графа. Матрица смежности. Матрица инцидентности. Число путей длины k в графе.

15. Пути и цепи. Алгоритм поиска цепи (пути) кратчайшей длины.

16. Матрица связности. Её нахождение по матрице смежности. Число компонент связности.

17. Пути в нагруженном графе. .Алгоритм Форда.

18. Эйлеровы и гамильтоновы циклы и цепи. Теорема об Эйлеровом цикле.

19. Внутренне устойчивые множества. Число внутренне устойчивых множеств. Алгоритм нахождения.

20. Внешне устойчивые множества. Число внешне устойчивых множеств. Алгоритм нахождения.

21. Ядро графа. Необходимое и достаточное условие существования ядра. Ядро графа без контуров.

22. Уровни графа. Алгоритм разбиения графа на уровни.

23. Функция Гранди. Её свойства..

24. Цикломатическое число графа. Вектор - циклы. Теорема о цикломатическом числе.

25. Деревья. Их свойства.

26. Остовное дерево графа. Алгоритм нахождения остовного дерева и остовного дерева наименьшей длины.

27. Алгоритм нахождения базиса вектор - цикла.

28 Транспортные сети. Поток в сети. Максимальный поток.

29. Полный и максимальный поток. Алгоритм нахождения полного и максимального потоков.

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

31. Матричное кодирование. Групповые поля. Схемы декодирования групповых КОДОВ.

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

33. Граф группы.


Случайные файлы

Файл
124266.rtf
ЭКОЛАБ11.DOC
27056.rtf
106344.rtf
44568.doc




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.