- •1. Понятие множества.
- •2. Способы представления множеств.
- •3. Операции над множествами.
- •4. Разбиения и покрытия.
- •5. Свойства операций над множествами. Доказательства.
- •6. Универсальное множество. Булеан.
- •7. Представление множеств в эвм.
- •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. Класс функций, сохраняющих значение 0.
- •39. Класс функций, сохраняющих значение 1.
- •40. Принцип двойственности. Класс самодвойственных функций.
- •41. Класс монотонных функций.
- •42. Класс линейных функций.
- •43. Алгебра Жегалкина. Полином Жегалкина.
- •44. Полином Жегалкина. Теорема.
- •45. Полнота.
- •46. Лемма о немонотонных функциях.
- •47. Лемма о нелинейных функциях.
- •48. Функциональная полнота. Первая теорема о функциональной полноте.
- •49. Функциональная полнота. Теорема Поста.
- •50. Логические исчисления.
- •51. Высказывания. Формулы.
- •52. Интерпретация формулы. Теорема.
- •53. Логическое следование и логическая эквивалентность.
- •54. Логические эквивалентности. Доказательство.
- •55. Исчисление высказываний.
- •56. Понятие предиката.
- •57. Понятие квантора. Квантор существования. Квантор всеобщности.
- •58. Исчисление предикатов.
- •59. Аксиомы исчисления предикатов. Правила логического вывода.
- •60. Графы. Типы задач теории графов.
- •61. Графы. Основные определения.
- •62. Способы представления графов.
- •63. Идентификация графов, заданных своими представлениями.
- •64. Обходы графов.
- •65. Степени вершин графа.
- •66. Операции с частями графа.
- •67. Маршруты, цепи, циклы.
- •68. Связные компоненты графа.
- •69. Расстояния в графе.
- •70. Диаметр, радиус, центр графа.
- •71. Произведение графов.
- •72. Прямое произведение графов.
- •73. Эйлеровы циклы.
- •74. Теорема Эйлера.
- •75. Эйлеровы цепи.
- •76. Гамильтоновы циклы.
- •77. Некоторые классы графов и их частей. Дерево и лес.
- •78. Концевые вершины и ребра.
- •82. Цикломатическое число графа.
- •83. Ориентированные графы. Пути и циклы в ориентированном графе.
- •86.Деревья
- •49.Функциональная полнота. Теорема Поста
- •94. Блок-схемы алгоритмов
- •95.Машины Тьюринга. Основные определения.Машина
- •96.Машины Тьюринга.Сложение
- •96.Машины Тьюринга.Копирование
- •80.Типы вершин
- •84.Начальные и конечные вершины. Ранги вершин
- •90. Бінарне дерево
- •79. Дерево с корнем. Ветви.
- •81. Центры деревьев. Теорема.
- •85. Отношение достижимости. Базисный граф
- •88.Способы представления деревьев
84.Начальные и конечные вершины. Ранги вершин
Вершина графа наз. начальной, если в неё не входит ни 1 ребро, конечной – если из неё не выходит ни одно ребро. Во всяком конечном ациклическом графе есть хотя бы 1 нач. и 1 кон. Вершины. Доказательство. Все пути графа G конечны и имеют длину, не превосходящую вершины, т.к. в ациклическом графе в пути вершины повторяться не могут. Существует максимальный путь, который нельзя удлинить ни в начале, ни в конце. Начало пути – начальная вершина, конец – конечная. Максимальным рангом R(V) ориентированного графа G наз. максимальная из длин путей этого графа с концом в V. Если рассмотреть начальную вершину графа, то её ранг =0. Если через V проходит цикл, то её ранг =+∞. В ациклическом графе все ранги вершин конечны. В ациклическом графе ранг неначальной вершины определяется R(V)=max(R(Vi-1))+1
90. Бінарне дерево
Бінарне дерево – кінцева множина вершин в яких або пуста або складається з кореня і двох неперетинаючихся бінарних піддерев. Бінарне дерево не впорядковане.
91. «И-ИЛИ» дерево
Вершина, з якої виходять «И» - зв’язки називається вершиною типу «И», щоб розглянути вершину типа «И» - треба вирішити всі її дочерні вершини. Вершина, що зв’язує альтернативи називається вершина типу «або» і для того щоб розглянути її необхідно вирішити будь-яку з її дочірних вершин.
Для аналізу таких графів і пошуку рішень в них можна використовувати алгоритми обхода в глубину і в вширину але вони не є ефективними через велику комбінаторну складність. Для таких графів існують алгоритми евристичного пошуку.
У якості оціночної функції вводиться вартість. Вона визначається як сума вартостей його ребер. Ціль алгоритма знайти рішающе дерево мін. вартості. Вартість вершин = вартості отриманого вирішального дерева.
Для оцінки вартості вершин будемо використовувати додаткову інфу про дочірні вершини. Для оцінки вартості вершин типу «АБО»
На будь-якій стадії пошуку кожна дочірня вершина («АБО») відповідає альтернативному вирішальному дереву. Процес пошуку приймає рішення продовжити пошук для дерева, ціна шляху для якого є мінімальною.
79. Дерево с корнем. Ветви.
Пусть в дереве g отлична вершина V0 – эта вершина корень дерева, а дерево – дерево с корнем, в таком дереве можно естественным образом ориентировать ребра. Вершину V’ дерева g можно соединить с корнем V0 при помощи единственно возможной цепи.
Если на ребрах дерева обозначить ориентацию от V’ к V” то такое дерево будет наз. ориентированым.
Обычно в ориентированном дереве все ребра имеют направление от корня к концу вершины, однако если определено противоположное направление от конца вершины к корню, то такой граф наз. сетью сборки. В каждую вершину ориентиро - ванного дерева, за искл. корня, входит только одно ребро, все инцидентные корню ребра связывают корень с вершинами, следовательно корень явл. началом ребер. В конечном дереве число вершин на 1-у больше числа ребер. Пусть V-вершина дерева g с корнем V0. В(V)- множество всех вершин, связанных с корнем, цепям проходящими через вершину V.Это множество порождает подграф g(V), кот. наз. ветвью вершины V в дереве с корнем V0. Как подграф дерева, g(V) тоже не имеет циклов. Любые две вершины V’,V” принадлежат В(V), связанные в этой ветви маршрутом, составленным из участков цепей L(V’) и L(V”) от корня V0 до этих вершин. Докажем, что эти участки целиком принадлежат g(V). Это справедливо, т.к. в каждую вершину такого участка ведет цепь из корня V0, являющаяся начальным участком соотв. цепи LV’ и LV” и проходящая через вершину V, т.е. ветвь g(V) является связанной и сама является деревом. Рассмотрим g(V) как дерево с корнем V. Для любой вершины V’ принад ле - жащей g(V), связывающая ее с вершиной V цепь LVV’ является концом цепи LV0V’, связывающей в дереве g эту вершину с корнем V0.