Содержание
- 2. 2.1 Требования к математическим моделям С точки зрения возможности и эффективности выполнения формальных преобразований к математической
- 3. Требования к математическим моделям Правила перехода устанавливают соответствия между компонентами объекта и элементами математической модели, а
- 4. Математические модели объектов «В виде графов можно представлять блок-схемы программ (вершины – блоки, а дуги –
- 5. Пример. Модель алгоритма поиска максимального элемента массива
- 6. 2.2. Графы: ультра-, гипер- и обыкновенные 2.2.1. Общее определение графа. 1. Граф – множество вершин X,
- 7. Общее определение графа Положим, что при X={x1,x2,x3} и U={u1,u2,u3,u4} предикаты Г1(X,U) и Г2(U,X) принимают значение «истина»
- 8. Общее определение графа Предикаты Г1(X,U) и Г2(U,X) таковы, что для всех графов при X≠ ∅ и
- 9. Виды графов Данная трактовка графов допускает существование в них петель и кратных ребер. Вид графа –
- 10. Отношения смежности На элементах множеств X и U определены также отношения смежности F1(X,X) и F2(U,U) .
- 11. Отношения смежности В соответствии с определением понятия «смежность» предикат смежности F1(X, X) является композицией предикатов Г1(X,U)
- 12. 2.3 Предикаты-свойства Определим одноместные предикаты-свойства, производные от предикатов Г1, Г2, F1, F2 (подстановка в двуместный предикат
- 13. Предикаты-свойства зафиксировав в предикате Г2(U,X) ребро uj, придем к предикату-свойству Г2 uj(X) – «ребру uj инцидентны
- 14. Предикаты-свойства Характеристические множества рассмотренных предикатов-свойств будем обозначать через Г1xi, Г1uj, Г2uj, Г2xi, где: Г1xi =U1i ={uj
- 15. Предикаты-свойства Зафиксировав в F1(X,X) некоторую вершину xi ∈ X, получим предикат-свойство F1xi(X) – «вершине xi смежны
- 16. 2.4 Ультраграфы Определенный выше граф называется ультраграфом HU(X,U,Г1,Г2), если предикаты Г1(X,U) и Г2(U,X) обладают следующим свойством
- 17. Представление ультраграфа матрицами инцидентности Полным и достаточно наглядным способом формального задания ультраграфа является его представление через
- 18. Представление ультраграфа матрицами инцидентности Матрица инцидентности А2 задает связь между ребрами и вершинами. Ее строки соответствуют
- 19. Представление ультраграфа матрицами инцидентности u1 u2 u3 x1 1 1 0 x1 x2 x3 x4 x5
- 20. Аналитическое представление ультраграфа Аналитически ультраграф полностью задается множествами X, U и образами этих множеств относительно предикатов
- 21. Пример аналитического представления ультраграфа Ультраграф данным способом будет задан, если заданы множества вершин X, ребер U
- 22. Аналитическое представление ультраграфа образами и прообразами вершин и ребер Рассмотренное представление ультраграфа, является полным, однако в
- 23. Аналитическое представление ультраграфа образами и прообразами вершин и ребер Элементы обратных предикатов Г2-1(X,U) и Г1-1(U,X) определяются
- 24. Аналитическое представление ультраграфа образами и прообразами вершин и ребер Аналогично множество вершин, которым инцидентно ребро uj
- 25. Аналитическое представление ультраграфа образами и прообразами вершин и ребер Геометрическая интерпретация предикатов Г1-1(U,X) и Г2-1(X,U) показана
- 26. Представление ультраграфа матрицами смежности Предикат смежности вершин F1(X, X). Вершине xi смежна вершина xt, если существует
- 27. Представление ультраграфа матрицами смежности Предикат смежности ребер F2(U, U). Ребру uj смежно ребро uk, если существует
- 28. Образ и прообраз множества X относительно предиката смежности вершин F1(X, X) Образ и пробраз вершины xi–
- 29. Образ и прообраз множества U относительно предиката смежности ребер F2(U, U). Образ и прообраз ребра ui
- 30. 2.5 Гиперграфы Данный вид графа получим в соответствии со сформулированным выше определением при выполнении условий (1)
- 31. Гиперграфы Вектор-строка таблицы истинности двуместного предиката-отношения Г1(X,U) – матрицы инцидентности вершины-ребра A1 совпадает с вектором-столбцом таблицы
- 32. Гиперграфы Отсюда, гиперграф будет полностью задан, если заданы множество вершин X, ребер U и один из
- 33. Представление гиперграфов В качестве матрицы инцидентности AH будем использовать матрицу истинности предиката Г1(X,U). Аналитическое в форме
- 34. Представление гиперграфа матрицами смежности Предикат смежности вершин F1(X, X). Элементы матрицы смежности R1 гиперграфа по его
- 35. Представление гиперграфа матрицами смежности Предикат смежности ребер F2(U, U). Элементы матрицы смежности R2 гиперграфа по его
- 36. Образы вершин гиперграфа относительно предиката смежности F1 Для каждой вершины xi ∈X гиперграфа H(X, U) ее
- 37. Образы ребер гиперграфа относительно предиката смежности F2 Образ F2uj ребра uj∈U гиперграфа H(X, U) относительно предиката
- 38. 2.6 Обыкновенные ориентированные графы Этот вид графа получим в том случае, если предикаты Г1(X,U) и Г2(U,X)
- 39. Представление ориентированного графа Матрицы инцидентности A1 и A2 этого графа определяются так же как и ультраграфа.
- 40. Смежность вершин и ребер ориентированного графа Для ориентированного графа элементы матриц смежности вершин R1 и ребер
- 41. 1.2.6. Обыкновенные неориентированные графы Неориентированный граф можно определить как два непересекающихся множества вершин X и ребер
- 42. Представление неориентированного графа Образы вершин и ребер относительно предикатов Г1 и Г2: X={x1, x2, x3, x4},
- 43. Смежность вершин и ребер неориентированного графа Для неориентированного графа элементы матриц смежности вершин R1 и ребер
- 44. 2.8 Характеристики вершин и ребер графов Характеристики вершин ультра- и ориентированного графа : ρ+(xi) – полустепень
- 45. Характеристики вершин и ребер графов Характеристики ребер ультра- и ориентированного графа : A+(uj) – количество вершин,
- 46. Характеристики вершин и ребер графов Характеристики вершин гипер- и неориентированного графа : ρ(xi) –локальная степень вершины,
- 47. 2.9 Некоторые особенные графы Конечный, пустой и смешанный графы. Граф G(X,U) называется конечным, если число его
- 48. Полный и однородный неориентированный графы Количество ребер неориентированного графа определяется через локальные степени вершин как: n
- 49. Полный ориентированный граф Количество ребер ориентированного графа n n r = Σ ρ+(xi) или r =
- 50. Двудольный граф (граф Кенига) Граф называется двудольным или графом Кенига, если его множество вершин Х распадается
- 51. Мультиграф Граф, у которого хотя бы для двух ребер uj,ul∈U справедливо Г2uj= Г2ul& Г1uj= Г1ul, называется
- 52. Маршрут, цепь, цикл Последовательность смежных ребер неориентированного графа без петель и кратных ребер называется маршрутом. В
- 53. Эйлеров и гамильтонов циклы Цикл, включающий все ребра графа, называется эйлеровым. Связный граф содержит эйлеров цикл,
- 54. Связность графа Две вершины xi, xj∈X называются связанными, если в графе G(X,U) существует маршрут S =
- 55. Деревья Связный граф, не имеющий циклов, называется деревом. Начальная вершина дерева называется корнем, выходящие из него
- 56. Части графа Граф Gi(Xi,Ui) называется частью графа G(X,U), если он находится в отношении включения к нему
- 57. Минимальные массивы Множество Xi вершин куска Hi(Xi,Ui) гиперграфа H(X,U) называется минимальным массивом, если удаление из него
- 58. 2.10 Представление структур сложных систем графами Для перехода от объектов задач структурного синтеза к их математическим
- 59. Представление структур сложных систем графами задать способ отображения свойств и характеристик компонент объекта в характеристики графа
- 60. 2.10.1 Представление схемы ультраграфом Ультраграф является универсальной (обобщенной) моделью, так как позволяет в общем случае отобразить
- 61. Представление схемы ультраграфом Для этих задач адекватность математической модели объекту следует рассматривать в смысле полноты и
- 62. Представление схемы ультраграфом При разработке математической модели системы в общем случае будем рассматривать множества подсистем (компонентов)
- 63. Представление схемы ультраграфом Адекватность ультраграфа как структурной модели в указанных выше условиях обеспечивается следующими правилами перехода:
- 64. Представление схемы ультраграфом Формальная запись правил перехода от структуры системы к ее модели в виде ультраграфа
- 65. Представление схемы ультраграфом Информации о номерах выводов подсистемы и времени распространения сигнала от подсистемы-источника до каждого
- 66. 2.10.2 Представление схемы ориентированным графом Обыкновенный ориентированный граф является частным случаем ультраграфа - в нем нет
- 67. 2.10.4 Представление структуры объекта гиперграфом и неориентированным графом В соответствии с характерными особенностями задач декомпозиции/композиции, размещения,
- 68. Представление структуры объекта гиперграфом и неориентированным графом Для решения указанных задач в математической модели системы должна
- 69. Представление схемы гиперграфом При переходе от схемы к гиперграфу: множеству элементов Э поставим во взаимнооднозначное соответствие
- 70. Представление схемы гиперграфом с точностью до выводом элементов Типы элементов, а также имена или типы цепей
- 71. Представление схемы взвешенным гиперграфом Гиперграф в форме H( ,U, Г1X, ). X = { , ,
- 72. Определение связности элементов по гиперграфу Для того, чтобы определить, соединены ли элементы эi и эk с
- 73. Представление схемы неориентированным графом Такая модель, как правило, используется для задач коммутации. В ней необходимо отобразить:
- 74. Пример представления схемы неориентированным графом Правила перехода от объекта (схемы соединения элементов) к неориентированному графу такие
- 75. Представление цепей деревом и полным графом Если соединение связывает более двух элементов, то в качестве модели
- 76. 2.10.5 Математические модели монтажного пространства Математические модели монтажного пространства используются для задач размещения и трассировки. Сущность
- 77. Математические модели монтажного пространства В качестве математической модели монтажного пространства используется неориентированный граф решетки Gr. Каждую
- 78. Модель монтажной плоскости фрагмента верхнего слоя печатной платы с ортогональным монтажом при запрещении проведения проводников под
- 79. Математические модели монтажного пространства (3) В модели многослойной печатной платы вертикальные ребра интерпретируют межслойные переходы. Вершины,
- 80. Математические модели монтажного пространства (4) Расстояние между i-м и j-м узлами графа решетки в общем случае
- 81. Приближенный подсчет суммарной длины соединений между модулями Пусть моделью схемы соединений является неориентированный мультиграф G с
- 82. 2.11 Математические модели структур данных Отображение данных в память ЭВМ требует реализации содержа-тельных связей между их
- 83. Требования к моделям структур данных Эти модели должны: – обеспечивать реализацию операций над данными соответствующими операциями
- 84. Требования к моделям структур данных Таким образом в модели необходимо отобразить следующую информацию о структуре данных:
- 85. Выбор или разработка структур данных Полный анализ применимости различных структур данных должен включать оценку вычислительной и
- 86. Вектор Векторное представление данных имеет следующие преимущества: непосредственный доступ к любому элементу массива, быстрая и эффективная
- 87. Односвязный и двусвязный списки Линейный односвязный список – это линейный массив перемен-ного размера, каждый элемент которого
- 88. Односвязный и двусвязный списки Для списковых структур характерны следующие преимущества: - низкая трудоемкость выполнения операций удаления/добавления
- 89. Комбинированные одноуровневые структуры данных Такие структуры позволяют эффективно выполнять операции прямого доступа к элементам множества, являющегося
- 90. Модель вектора Основными компонентами вектора данных как непрерывной последовательности элементов памяти, являются множество адресов элементов –
- 91. Модель вектора Возможность непосредственного доступа к элементам памяти определяет свойство достижимости адресов множества AЭ из адреса
- 92. Модель вектора Модели достижимости адресов вектора: достижимость адресов из адреса базы (а), достижимость адреса из любого
- 93. Модель вектора Достижимость элемента памяти от любого другого Д(AЭ, AЭ) реализуется отношением Rm «текущий – все
- 94. Модель вектора Наличие значения знi в элементе памяти с адреcом аi задает отношение достижимости Д(АЭ, ЗЭ).
- 95. Модель вектора Тогда моделью достижимости значений данных будет граф GЗ→({ZЭ, Y}, F3ZЭ), в котором ZЭ ∩
- 96. Модель вектора Модели достижимости значений данных (а), вектора данных (б) и вектора упорядоченных данных (в)
- 97. Модель двусвязного списка Переход от списковой структуры к его модели в виде ориентированного графа проиллюстрируем на
- 98. Модель двусвязного списка адресам элементов списка AЭ – вершины множества ZЭD, значениям элементов данных ЗЭ –
- 99. Модель двусвязного списка
- 100. Модель двусвязного списка В моделях элементов списка необходимо отобразить их адреса аi ∈ AЭ, рассмотренные выше
- 101. Модель двусвязного списка Этот граф является объединением графов gi→(Zi, Fzi), gi←(Zi, Fzi) и графа gЗi→({zi, yi},
- 102. Модель комбинированной одноуровневой структуры Рассматриваемая структура предназначена для обеспечения вычислительной сложности равной 1 операции добавления/удаления и
- 103. Модель комбинированной одноуровневой структуры Моделью этой комбинированной структуры является граф – объединение моделей вектора прямого доступа
- 104. Модель комбинированной одноуровневой структуры В этом графе: zБ ↔ аБ, ZЭP ↔ AЭP, ZЭP = {zi
- 105. Модель комбинированной одноуровневой структуры ZD = {{zу.н, zу.к}, ZЭD}, Fzу.н = zd1, Fzу.к = zdm, Fzd1
- 106. Двухуровневые структуры данных Представление графов множествами вершин, рёбер и их образов (прообразов) требуют организации двухуровневых структур,
- 107. Двухуровневые структуры данных Ниже рассмотрены структуры для представления графа в форме G(X,F1X). Неориентированный граф Матрица смежности
- 108. Двухуровневые структуры данных Список векторов Список списков Вектор n-связных списков Список n-связных списков
- 109. Модель двухуровневой структуры данных список-списков Модель двухуровневой структуры данных рассмотрим для части аналитического представления гиперграфа H(X,
- 110. Модель двухуровневой структуры данных список-списков В данной структуре хранятся два вида данных: множество ребер U и
- 111. Модель двухуровневой структуры данных список-списков Моделью этой двухуровневой структуры является граф GS({Zу, ZЭD, ZУ, ZЭL, YD,
- 112. Модель двухуровневой структуры данных список-списков Правила перехода от двусвязного списка к его модели те же, что
- 113. Пример двухуровневой комбинированной структуры данных добавления подразумевают предварительный поиск с вычислительной сложнос-тью O(n) необходимо орга-низовать прямой
- 114. Пример двухуровневой комбинированной структуры данных (2) При удалении вершины из множества X ее необходимо удалять из
- 115. Пример двухуровневой комбинированной структуры данных (3) В разработанной выше структуре поиск xi в Г2U требует максимум
- 116. Трехсвязный список с векторами прямого доступа
- 117. Модель двухуровневой комбинированной структуры На рисунке представлена модель двухуровневой структуры – комбинация трехсвязного списка с векторами
- 118. 2.12 Математическая модель алгоритма Для автоматизации анализа вычислительной и емкостной сложности, а также выполнения оптимизирующих преобразований
- 119. Математическая модель алгоритма Элементарный базис логической структуры алгоритма составляют операторы: начала и конца работы алгоритма; ввода/вывода
- 120. Математическая модель алгоритма Помимо операций и их связей, компонентами алгоритма, отражающими процедурный подход, являются входные и
- 121. Математическая модель алгоритма В математической модели должны быть отражены следующие компоненты алгоритма, связи между ними, характеристики
- 122. Математическая модель алгоритма 6) связи данные – операторы и наоборот, их типы, определяющие вычислительную сложность чтения-записи
- 123. Математическая модель алгоритма Моделью алгоритмов данного класса является управляющий граф, в котором не отражены конкретные наборы
- 124. Математическая модель алгоритма События передачи управления порождают отношения достижимости оператор – оператор, обозначим его Д1(О, О).
- 125. Математическая модель алгоритма 2. Тип и вычислительную сложность оператора отобразим, задав однозначное (возможно, взаимно однозначное) отношения
- 126. Математическая модель алгоритма 5. Отношения П1(O, С) – «управление передаётся от оператора» и П2(С, O) –
- 127. Математическая модель алгоритма 8. Вершинам прообразов F1-1xi вершин разветвления потока управления, присвоим аналогичные веса: xi R7
- 128. Математическая модель алгоритма На рисунке следующего слайда показаны схемы алгоритмов программ: А1 – определения номера последнего
- 129. Математическая модель алгоритма Схемы алгоритмов
- 130. Математическая модель алгоритма На рис. в: DB ={di /i = 1,6}, где di – символы данных;
- 131. Математическая модель алгоритма Граф GУ алгоритмов данного класса
- 132. Математическая модель алгоритма Вторая компонента модели алгоритма должна отображать отношения данные – операторы, разделяя для каждого
- 133. Математическая модель алгоритма Тогда вторая модель алгоритма будет представлять собой двудольный граф, множество вершин которого Z
- 134. Математическая модель алгоритма Переход к этому графу выполняется по правилам: 1. Множеству операторов алгоритма О поставим
- 135. Математическая модель алгоритма Модель класса алгоритмов, отображающая отношения между данными и операторами
- 136. Математическая модель алгоритма Интегральной моделью класса алгоритмов будет граф: GA({X, Y}, F1Х, F1-1Х , F2Х, F2-1Х,
- 137. Математическая модель алгоритма В модели конкретного алгоритма должны быть отражены реализуемые функции и предикаты, а также
- 138. Математическая модель алгоритма I1(PB) : I1(p1(2) (DB)) = p1(2) (d5, d1) = «i меньше или равно
- 139. 2.13 Модель сети Неформально сеть можно определить следующим образом: имеется система, состоящая из некоторого множества объектов,
- 141. Скачать презентацию