Питання на іспит з “Основ Дискретної Математики”

Питання на іспит з “Основ Дискретної Математики”

Семестр 1

1. Множини. Інтуїтивне означення множини. Сімейство. Мультимножина. Способи задання множин. Парадокс Рассела. (одинична множина, клас, уникнення парадоксу).

2. Універсум. Порожня множина. Підмножина. Рівність множин. Властивість транзитивності у термінах множин. Булеан (надмножина, власна підмножина, лема про рівність, єдина порожня множина).

3. Операції над множинами. Діаграми Венна. Властивості операцій (комутативність, асоціативність, дистрибутивність,… з доведенням) (узагальнені операції).

4. Розбиття множини. Декартовий добуток (покриття, декартовий квадрат, ступінь, кортеж).

5. Відношення. Способи задання відношень. Області визначення та значень. Обернене відношення. Композиція відношень. Властивості композиції (арність відношень, повне, тотожне, порожнє відношення, ступінь відношення, теорема про властивості відношення, граф відношення, матриця відношення).

6. Властивості відношень (рефлективність, іррефлексивність, симетричність, асиметричність, антисиметричність, транзитивність). Рефлексивне, симетричне та транзитивне замкнення. Алгоритм Уоршала.

7. Функціональні відношення. Типи відображень (сюр’єкція, ін’єкція, бієкція) (область визначення, область значень, образ, прообраз, відображення).

8. Властивості відображень. Композиція відображень. Суперпозиція (образ множини, повний прообраз, теорема про властивості, продовження, звуження, теореми про обернене функціональне відношення, композицію функціональних відношень, композицію різних типів відношень).

9. Відношення еквівалентності. Класи еквівалентності. Властивості матриці та графа відношення еквівалентності. Відношення толерантності (теореми про властивості класів еквівалентності, теорема про зв’язок відношення еквівалентності і розбиття множини).

10. Відношення порядку. Впорядкована множина. Принцип подвійності (строгий та частковий порядок, ланцюг, теорема про обернене відношення до відношення порядку, теорема про підмножину частково упорядкованої множини).

11. Найбільші, найменші, мінімальні та максимальні елементи. Діаграма Хассе. Верхні та нижні межі (теореми про існування найбільшого, максимального елементів, доповнення порядку до лінійного, відношення домінування, точні межі).

12. Повністю впорядкована множина. Ізоморфні множини. Метод трансфінітної індукції (аксіома повної упорядкованості, аксіома вибору, метод трансфінітної індукції).

13. Потужність множин. Рівнопотужні множини. Кардинальні числа (теорема Кантора-Бернштейна б/д, наслідки теореми, операції над кардинальними числами).

14. Злічені множини. Зліченість множин цілих та раціональних чисел. Трансфінітне число (теорема про найменше трансфінітне число, теорема про об’єднання злічених множин, теорема про властивості трансфінітних чисел – додавання та добуток).

15. Незлічені множини. Теорема Кантора. Потужність континууму. Континуум-гіпотеза.

16. Алгебра. Закон композиції. Підалгебра. Замкнення множини відносно сигнатури. Система твірних. Властивості операцій (сигнатура, носій, операції, замкнення відносно операції).

17. Гомоморфізм та ізоморфізм алгебр (теорема про обернений ізоморфізм).

18. Півгрупа. Група. Моноїд. Абелева група (нейтральний елемент, теорема про єдиність нейтрального елементу, обернений елемент, теорема про єдиність оберненого елементу, теорема про співвідношення у групі, розв’язок рівняння у групі).

19. Кільце. Властивості кілець. Поле. Властивості полів (розв’язок рівняння у полі).

20. Ґратки. Підґратки. Властивості ґраток. Нижні та верхні півґратки (теорема про властивості операцій ґраток, теорема про ізотонність операцій, теорема про зв’язок ґраток і алгебри).

21. Дистрибутивні ґратки. Булеві ґратки (нерівність дистрибутивності, теорема про зв’язок рівностей дистрибутивності, доповнення елементу, єдність доповнення до елементу у булевих ґратках).

22. Модулярні ґратки (теорема про умови модулярності та дистрибутивності ґраток, нерівність модулярності).

23. Матроїд. Побудова базису матроїда. (максимально незалежна підмножина, теорема про еквівалентність аксіом 3 та 4, теорема про рівнопотужність базисів матроїда).

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. Асиметричне шифрування. Шифрування з відкритим ключем. Алгоритм RSA. Цифровий підпис.

50. Нечіткі множини. Визначення. Функція приналежності. Операції над нечіткими множинами.

Дата добавления: 2015-11-04