Харків 2013

УНІВЕРСИТЕТ РАДІОЕЛЕКТРОНІКИ

ТИПОВІ КОНТРОЛЬНІ ТА ТЕСТОВІ ЗАВДАННЯ

З дисципліни

«ДИСКРЕТНА МАТЕМАТИКА»

для студентів усіх форм навчання

напряму 6.050101 – «Комп’ютерні науки»

Електронне видання

ЗАтверДжЕно

кафедрою ІУС

Протокол № 1 от 29.08.2013 р.

ХАРКІВ 2013

Типові контрольні та тестові завдання з дисципліни «Дискретна математика» для студентів усіх форм навчання напряму 6.050101 «Комп’ютерні науки» [Електронне видання] / Упоряд. Н.В. Васильцова, Л.Е Чала. – Харків: ХНУРЕ, 2013. – 14 с.

Упорядники Н.В. Васильцова

Л.Е. Чала

Теоретичні запитання

1. Мета і задачі дисципліни, її місце в системі підготовки фахівців з комп'ютерних наук.

2. Історія зародження, розвитку і становлення дискретної математики. Внесок вчених у її розвиток.

3. Основні поняття і позначення теорії множин. Інтуїтивне поняття множини. Способи задання множин. Потужність множин. Множина і підмножини.

4. Геометрична інтерпретація множин: кола Ейлера та діаграми Венна.

5. Операції на множинах.

6. Загальне визначення алгебри. Поняття алгебри множин. Аксіоми алгебри множин. Тотожні перетворення формул алгебри множин.

7. Поняття відношення. Бінарні та n-арні відношення. Область визначення та область значень відношення.

8. Способи задання відношень.

9. Операції над відношеннями.

10. Властивості бінарних відношень. (рефлексивність, антирефлексивність, симетричність, антисиметричність, асиметричність, транзитивність, антитранзитивність відношень).

11. Класи бінарних відношень. Відношення еквівалентності. Класи еквівалентності. Відношення порядку. Відношення толерантності.

12. Функціональні відношення. Області визначення і значень. Функції і відображення. Типи відображень: сюр'єкція, ін'єкція, бієкція.

13. Елементи реляційної алгебри. Реляційна модель даних. Поняття реляційної алгебри. Операції реляційної алгебри.

14. Алгебраїчні операції та їх властивості. Унарна, бінарна, n-арна операція. Способи записів операцій. Основні властивості операцій. Операції додавання та множення за модулем.

15. Поняття алгебраїчної структури Підструктура. Морфізми (гомоморфізм, ізоморфізм). Найпростіші алгебраїчні структури. Кільці і поля. Гратки.

16. Булеві змінні і функції. Область визначення та область значень булевий функцій. Способи задання булевих функцій.

17. Булева алгебра. Реалізація булевих функцій формулами. Елементарні функції алгебри логіки.

18. Двоїстість в булевій алгебрі. Двоїсті та самодвоїсті булеві функції. Принцип двоїстості.

19. Закони і тотожності булевої алгебри. Еквівалентні перетворення формул булевої алгебри.

20. Нормальні форми булевих функцій. Основні поняття.

21. Досконалі нормальні форми (ДДНФ, ДКНФ). Диз’юнктивні та кон’юнктивні розкладання булевих функцій. Перехід від таблиці булевої функції до формули алгебри логіки і навпаки.

22. Мінімізація булевих функцій. Основні поняття. Критерії мінімізації.

23. Основні методи мінімізації булевих функцій. Метод мінімізуючих карт (діаграми Карно-Вейча).

24. Алгебра Жегалкіна. Структура і тотожністі алгебри Жегалкіна. Поліном Жегалкіна та правило його побудови. Лінійні булеві функції.

25. Функціональна повнота наборів булевих функцій. Типи булевих функцій. Замкнені класи булевих функцій. Теореми Поста про функціональну повноту набору булевих функцій.

26. Логічні схеми. Синтез комбінаційних схем. Перемикальні ланцюги; двох- і багатоступінчасті комбінаційні схеми.

27. Висловлення (основні поняття). Логічні зв'язки і формули логіки вісловлень. Побудова складних формул.

28. Алгебра логіки і логіка висловлень. Інтерпретація формул логіки висловлень. Правильні міркування.

29. Обчислення висловлень. Аксіоми та повнота обчислення логіки висловлень. Висновки в обчисленні висловлень. Дедуктивні висновки у логіці висловлень. Різні аксіоматизації обчислення висловлень.

30. Основні поняття логіки предикатів. Операції логіки предикатів. Кванторні операції. Формули та їх інтерпретація у логіці предикатів.

31. Закони і тотожності логіки предикатів. Випереджені нормальні форми.

32. Обчислення предикатів. Логічний висновок у логіці предикатів.

33. Багатозначна логіка. Основні поняття і функції k-значної логіки.

34. Історія розвитку комбінаторики. Класичні задачі комбінаторного аналізу. Сучасні задачі, які вирішуються комбінаторними методами.

35. Загальні визначення комбінаторики. Моделі типових комбінаторних конфігурацій. Поняття r-вибірки.

36. Загальні правила і задачі комбінаторики. Правила суми і добутку.

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

38. Властивості сполучень. Біном Ньютона. Біноміальні коефіцієнти. Трикутник Паскаля. Поліноміальна теорема.

39. Принцип включення і виключення. Теорема та формула включень і виключень.

40. Задачі про розподіл предметів за урнами (урнові схеми вирішення комбінаторних задач).

41. Композиції і розбиття.

42. Підходи до вивчення комбінаторних об’єктів і чисел. Поняття про продуктивні функції. Поняття про рекурентні співвідношення.

43. Метод продуктивних функцій. Продуктивні функції сполучень. Продуктивні функції розміщень та перестановок. Продуктивні функції для розбиття чисел.

44. Метод рекурентних співвідношень. Числа Фібоначчі.

45. Основи теорії кодування. Алфавітне кодування. Кодування з мінімальною надлишковістю. Алгоритм Фано. Алгоритм Хаффмена. Завадостійке кодування. Стиснення даних. Криптографія.

46. Зародження теорії графів як математичної дисципліни. Типові задачі теорії графів. Походження графів.

47. Визначення графів. Різновиди графів. Неорієнтовані та орієнтовані графи. Основні терміни для неорієнтованих та орієнтованих графів.

48. Способи задання графів. Геометрична реалізація графів. Матриця суміжності. Матриця інциденцій. Число вершин і ребер графа.

49. Операції над графами. Операції вилучення ребер та вершин. Операція введення ребра, операція введення вершини у ребро. Операція об’єднання графів. Операції додавання і множення графів.

50. Ізоморфізм графів. Підграфи. Алгебраїчний критерій ізоморфізму графів. Зв'язок з відношеннями. Ізоморфізм як відношення еквівалентності.

51. Плоскі та планарні графи. Гомеоморфні графи. Теорема Понтрягіна-Куратовського. Теорема Жордана. Жорданова крива. Побудова плоского зображення графа.

52. Зв'язність графів. Ейлерові та гамільтонові графи. Поняття зв'язності графів, компонента зв'язності, n-зв'язний граф. Властивості зв'язних графів. Метричні характеристики зв'язних графів.

53. Ейлерові графи. Теорема Ейлера. Алгоритм знаходження ейлерова цикла (теорема Флері).

53. Гамільтонові графи. Ознаки існування гамільтонових циклів, шляхів і контурів.

54 Цикломатика графів. Цикломатичне число та його властивості. Цикломатична матриця. Базис циклів. Алгоритм побудови базису циклів.

55. Задача комівояжера. Приклади практичних задач, що зводяться до задачі комівояжера.

56. Дерева. Визначення дерева, властивості дерев, ліс.

57. Перелічення графів і дерев. Остови графа.

58. Орієнтовані і бінарні дерева. Правила обходу бінарних дерев. Еквівалентні бінарні дерева.

59. Розфарбування графів. Фарбування вершин та ребер. Хроматичне число, теорема про біхроматичний граф. Хроматичний клас. Теорема Брукса.

60. Гіпотеза чотирьох фарб. Теорема про п'ять фарб. Прикладні задачі, що зв’язані з розфарбуванням графів

61. Двудольні та k-дольні графи.

62. Найкоротші відстані та шляхи у мережах. Алгоритм визначення відстані між вершинами на графі з одиничними довжинами ребер. Алгоритм Дейкстри (Форда) визначення відстані між вершинами на графі з довільними довжинами ребер.

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

64. Течії у мережах. Задача про максимальну течію у мережі. Розріз мережі. Теорема про максимальну течію і мінімальний розріз. Алгоритм Форда-Фалкерсона.

65. Елементи теорії формальних граматик. Задачі формалізації мов та перекладу. Задання мов за допомогою граматик. Типи граматик.

66. Елементи теорії скінчених автоматів. Загальна характеристика автоматів. Розпізнавачі.

67. Скінченні автомати. Способи задання автоматів. Автомати Мили і Мура. Автомати з магазинною пам’яттю. Машина Тьюринга.