питання до екзамену ДА 2022 (2). Питання до екзамену з Дискретного аналізу для кн11, пм11, іпз11

• Название: Питання до екзамену з Дискретного аналізу для кн11, пм11, іпз11
• Дата: 17.10.2022
• Размер: 139.17 Kb.
• Имя файла: питання до екзамену ДА 2022 (2).pdf
• Тип: Закон; #738091

ПИТАННЯ ДО ЕКЗАМЕНУ
з «Дискретного аналізу»
для КН-11, ПМ-11, ІПЗ-11
1.
Інтуїтивне поняття множини. Основні принципи теорії множин.
2.
Операції над множинами. Закони для операцій над множинами.
3.
Декартовий добуток множин. Властивості декартового добутку множин.
4.
Відношення: унарні, бінарні, тернарні, n-арні відношення. Приклади.
5.
Способи задання бінарних відношень.
6.
Повне, тотожне, порожнє відношення. Область визначення та область значень відношення. Операції над відношеннями.
7.
Властивості відношень: рефлексивне, іррефлексивне. Їх матриця та граф.
Рефлексивне замикання відношення.
8.
Властивості відношень: симетричне, антисиметричне, асиметричне. Їх матриця та граф. Симетричне замикання відношення.
9.
Властивості відношень: транзитивне. Матриця та граф транзитивного відношення.
Транзитивне замикання відношення.
10. Функціональне відношення. Образ та прообраз. Область визначення та область значень.
11. Відображення. Види відображень.
12. Композиція відображень. Властивості композицій. Суперпозиція.
13. Відношення еквівалентності. Матриця та граф відношення еквівалентності. Клас еквівалентності.
14. Потужність множин. Злічені множини та їх властивості.
15. Потужність множин. Незлічені множини та їх властивості. Теорема Кантора (про незліченні множини).
16. Основні принципи комбінаторики: правило множення та правило суми.
17. Розміщення без повторень. Розміщення з повтореннями.
18. Перестановки без повторень. Перестановки з повтореннями.
19. Комбінації без повторень. Комбінації з повтореннями.
20. Біном Ньютона. Трикутник Паскаля. Властивості біноміальних коефіцієнтів.
21. Поліноміальна формула. Метод включень та виключень.
22. Означення булевих функцій від n змінних. Число булевих функцій від n змінних.
Булеві функції одного аргументу.
23. Булеві функції двох аргументів.
24. Основні тотожності булевої алгебри.
25. Нормальні форми булевих функцій.
26. Досконалі нормальні форми булевих функцій. Алгоритм зведення булевих функцій до досконалої нормальної форми.
27. Утворення досконалої нормальної форми булевої функції по таблиці істинності.
28. Геометричне подання булевих функцій від двох та трьох змінних.

29. Мінімізація булевих функцій з використанням карт Карно.
30. Застосування булевих функцій до аналізу контактних схем.
31. Поняття графа. Основні поняття теорії графів. Підграфи. Способи задання графів.
32. Різновиди графів. Приклади.
33. Суміжність вершин, інцидентність вершин та ребер, степінь вершини. Лема про рукостискання.
34. Матриці суміжності та інцидентності. Властивості. Застосування. Матриці відстаней.
35. Поняття та способи задання орієнтованих графів.
36. Операції над графами (операція вилучення ребра, операція введення ребра, операція стягування ребра, операція вилучення вершини, операція введення вершини, операція злиття вершин, об’єднання графів, операція добутку графів, доповненням графа). Приклади. Властивості операцій.
37. Зв’язність графів. Компоненти зв’язності. Розділова вершина, міст, блок.
38. Ознаки зв’язності.
39. Маршрути, ланцюги, цикли.
40. Зв’язність орграфів.
41. Властивості зв’язних графів.
42. Відстань між вершинами. Ексцентриситет, радіус, діаметр, центр графа.
43. Ейлерові та гамільтонові графи. Властивості.
44. Дерево, ліс. Основні властивості дерев.
45. Кістякове дерево. Алгоритм Краскала. Цикломатичне число графа.
46. Поняття ізоморфізму графів. Інваріанти ізоморфних графів. Реберні графи.
47. Укладання графа. Плоскі та планарні графи. Критерії планарності.
48. Теорема Ейлера та властивості планарних графів.
49. Розфарбування. Хроматичне число графа. Критичні графи.
50. Гіпотеза чотирьох фарб та теорема про п’ять фарб для планарних графів.
51. Алгоритми пошуку маршрутів вшир/вглиб у графі.
52. Модифікація алгоритмів пошуку вшир/вглиб.
53. Хвильовий алгоритм пошуку мінімального шляху в графі.
54. Алгоритму Дейкстри пошуку мінімальних шляхів у зважених графах.
55. Поняття скінченного автомата. Автомати Мілі та Мура. Основні поняття теорії автоматів.
56. Еквівалентність автоматів. Теорема про еквівалентність автоматів Мілі та Мура.
57. Алгоритм побудови автомата Мура, еквівалентного автомату Мілі.
58. Алгоритм побудови автомата Мілі, еквівалентного автомату Мура.
59. Мінімальний автомат. Алгоритм мінімізації скінченного автомата.