Перелік питань з курсу дискретної математики



Скачати 15.15 Kb.
Дата конвертації28.01.2021
Розмір15.15 Kb.
ТипЗадача

ПРИКЛАДНА МАТЕМАТИКА

ПЕРЕЛІК ПИТАНЬ З КУРСУ ДИСКРЕТНОЇ МАТЕМАТИКИ (доц. Коковська Я.В.)

2018/2019 навчальний рік (1 семестр)

  1. Множина. Кортеж. Декартів добуток множин.

  2. Операції над множинами. Доведення рівностей з множинами.

  3. Відношення. Означення відношень із однієї множини в іншу. Означення відношення на множині.

  4. Бінарні відношення . Властивості відношень. Способи подання бінарних відношень.

  5. Операції над відношеннями. Властивість степеня транзитивного відношення.

  6. Відношення еквівалентності. Розбиття множини на класи еквівалентності.

  7. Конгруентність за модулем m.

  8. Відношення часткового порядку.

  9. Рефлексивне замикання відношення. Симетричне замикання відношення.

  10. Транзитивне замикання відношення. Алгоритм Уоршала.

  11. Основні правила комбінаторики.

  12. Поняття вибірки. Розміщення та сполучення.

  13. Обчислення кількості розміщень та сполучень(без повторень і з повтореннями).

  14. Перестановки( без повторень і з повтореннями).

  15. Задача про цілочислові розв’язки.

  16. Розв’язування однорідних рекурентних рівнянь зі сталими коефіцієнтами: випадок простих коренів характеристичного рівняння. (Теореми без доведення).

  17. Розв’язування однорідних рекурентних рівнянь зі сталими коефіцієнтами: випадок кратних коренів характеристичного рівняння. (Теореми без доведення).

  18. Розв’язування неоднорідних рекурентних рівнянь зі сталими коефіцієнтами. (Теореми без доведення).

  19. Принцип коробок Діріхле (Без доведення).

  20. Принцип включення – виключення.

  21. Принцип включення – виключення в альтернативній формі.

  22. Неорієнтовані графи, основні означення та властивості.

  23. Орієнтовані графи, основні означення та властивості.

  24. Спеціальні класи простих графів.

  25. Способи подання графів.

  26. Шляхи та цикли. Зв’язність.

  27. Характеристики зв’язності графа, точки з’єднання та мости. Поняння двозв’язного графа.

  28. Теорема про оцінку ребер у простому графі.(Без доведення).

  29. Критерій двочастковості графа.( Теорема Кьоніга без доведення).

  30. Ізоморфізм графів.

  31. Ейлерів цикл у графі. Алгоритм Флері.

  32. Гамільтонів цикл у графі.(Теорема Дірака без доведення).

  33. Задачі про найкоротші шляхи у зважених графах. Алгоритм Дейкстри. Алгоритм Флойда.

  34. Обхід графа вглиб та вшир. Протокол обходу.

  35. Планарні графи. Теорема Куратовського(без доведення).

  36. Розфарбування графів.

  37. Незалежні множини вершин. Кліки.

  38. Паросполучення у графах. Теорема Холла(без доведення).

  39. Найбільше паросполучення у дводольних графах.

  40. Дерева, основні означення та властивості. Поняття m-арного дерева.

  41. Рекурсія. Обхід дерев. Префіксна, постфіксна, інфіксна форми запису.

  42. Бінарне дерево пошуку. Алгоритм додавання об’єкта в дерево. Алгоритм пошуку об’єкта в дереві

  43. Дерево прийняття рішень. Алгоритм ID3.

  44. Бектрекінг. Застосування на конкретних прикладах.

  45. Каркаси. Способи побудови каркасів у графах.

  46. Алгоритм Краскала для знаходження мінімального (максимального) каркасу.


Поділіться з Вашими друзьями:


База даних захищена авторським правом ©res.in.ua 2019
звернутися до адміністрації

    Головна сторінка