Вопросы к экзамену
 Скачать 16.02 Kb.
|
|
ВОПРОСЫ К ЭКЗАМЕНУ 1. Что называется объединением, пересечением, разностью, симметрической разностью множеств, дополнением множества? 2. Что такое инъективное, сюръективное, биективное отображение (с примерами)?{\displaystyle X} 3. Что такое мощность множества двоичных наборов и мощность множества всех подмножеств данного множества? 4. Что такое правило произведения (с примером)? 5. Что такое перестановки и чему равно число всех перестановок (с примером)?{\displaystyle 1,2,\ldots ,n,}(( 6. Что такое размещения и чему равно число всех размещений (с примером)? 7. Что такое сочетания и чему равно число всех сочетаний (с примером)? 8. Что такое перестановки с повторениями и чему равно число всех перестановок с повторениями (с примером)? 9. Что такое рефлексивное, симметричное, транзитивное отношение, отношение эквивалентности и каково его основное свойство? 10. Что такое отношение нестрогого порядка, строгого порядка? 11. В чем состоит числовое сравнение двоичных наборов и как сравнить двоичные наборы по Парето? 12. Что такое орграф, граф, вершина, дуга, ребро, путь, цепь, контур, цикл? 13. Каков алгоритм решения задачи о кратчайшем пути в невзвешенном графе? 14. Каков алгоритм решения задачи о кратчайшем пути во взвешенном графе? 15. Что такое эйлерова цепь (цикл), у каких графов они существуют? 16. В чем состоит формула Эйлера и для каких объектов она верна? 17. Как выглядят непланарные графы № 1 и № 2, типов 1 и 2 и в чем состоит теорема Куратовского-Понтрягина? 18. Что такое хроматическое число графа и какова его величина? 19. Что такое хроматический индекс графа и какова его величина? 20. Что такое матрица смежности орграфа и каким свойством обладает матрица смежности неориентированного графа? 21. Что такое матрица инцидентности орграфа? Как по матрице инцидентности восстановить граф? 22. Как строится код Харари? 23. Что называется деревом, ордеревом и как они связаны между собой? 24. Как строится префиксный код бинарного ордерева? 25. Как строится код Прюфера? 26. Назовите три способа обхода бинарного ордерева (с примером)? 27. Что называется атомом, списком и как связаны деревья со списками? 28. Определение булевой функции. Как выглядят таблицы истинности для восьми важнейших булевых функций? 29. Как выразить дополнительные логические операции через три основные: дизъюнкцию, конъюнкцию и отрицание? 30. Что такое ЭК, ДНФ, правильная ЭК, полная ЭК, СДНФ? 31. Как получить СДНФ с помощью таблицы истинности? 32. Каковы основные шаги преобразования формулы в СДНФ? 33. Что такое двойственная булева функция, самодвойственная булева функция, закон двойственности? 34. Как получить СКНФ, используя двойственность? 35. Как получить СКНФ, используя таблицу истинности? 36. Что такое многочлен Жегалкина? Представление булевой функции в виде многочлена Жегалкина. 37. Что такое монотонная булева функция и как это связано с дизъюнкцией и конъюнкцией? 18 38. Что такое линейная функция, функция сохраняющая ноль и функция, сохраняющая единицу? 39. В чём состоит теорема Поста? Как практически применить теорему Поста? 40. Понятие абстрактного алфавита и кода, примеры. 41. Двоичные коды. 42. Коды с обнаружением и исправлением ошибок. 43. Коды Хемминга. Построение кодера и декодера (7,4) – кода Хемминга. 44. Коды, исправляющие несколько ошибок |