Библиотека Рефераты Курсовые Дипломы Поиск
Библиотека Рефераты Курсовые Дипломы Поиск
сделать стартовой добавить в избранное
Кефирный гриб на сайте www.za4et.net.ru

Компьютеры, Программирование Компьютеры, Программирование     Программное обеспечение Программное обеспечение

Алгоритмы на графах. Независимые и доминирующие множества

Фонарь садовый «Тюльпан».
Дачные фонари на солнечных батареях были сделаны с использованием технологии аккумулирования солнечной энергии. Уличные светильники для
106 руб
Раздел: Уличное освещение
Браслет светоотражающий, самофиксирующийся, желтый.
Изготовлены из влагостойкого и грязестойкого материала, сохраняющего свои свойства в любых погодных условиях. Легкость крепления позволяет
66 руб
Раздел: Прочее
Совок большой.
Длина 21,5 см. Расцветка в ассортименте, без возможности выбора.
21 руб
Раздел: Совки

Курсовая работа &quo ;Алгоритмы на графах. Независимые и доминирующие множества&quo ; Введение Определим граф как конечное множество вершин V и набор E неупорядоченных и упорядоченных пар вершин и обозначим G=(V, E). Мощности множеств V и E будем обозначать буквами и M. Неупорядоченная пара вершин называется ребром, а упорядоченная пара – дугой. Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги, – ориентированным, или орграфом. Вершины, соединенные ребром, называются смежными. Ребра, имеющие общую вершину, также называются смежными. Ребро и любая из его двух вершин называются инцидентными. Говорят, что ребро (u, v) соединяет вершины u и v. Каждый граф можно представить на плоскости множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам. В трехмерном пространстве любой граф можно представить таким образом, что линии (ребра) не будут пересекаться. Способы описания. Выбор соответствующей структуры данных для представления графа имеет принципиальное значение при разработке эффективных алгоритмов. При решении задач используются следующие четыре основных способа описания графа: матрица инциденций; матрица смежности; списки связи и перечни ребер. Мы будем использовать только два: матрицу смежности и перечень ребер. Матрица смежности – это двумерный массив размерности . A = Для хранения перечня ребер необходим двумерный массив R размерности M 2. Строка массива описывает ребро. 1. Независимые множества Задача поиска подмножеств множества вершин V графа G, удовлетворяющих определенным условиям, свойствам, возникает достаточно часто. Дан неориентированный граф G=(V, E). Независимое множество вершин есть множество вершин графа G, такое, что любые две вершины в нем не смежны, то есть никакая пара вершин не соединена ребром. Следовательно, любое подмножество S, содержащееся в V, и такое, что пересечение S с множеством вершин смежных с S пусто, является независимым множеством вершин. Пример. Множества вершин (1, 2), (3, 4, 5), (4, 7), (5, 6) – независимые. Независимое множество называется максимальным, когда нет другого независимого множества, в которое оно бы входило. Если Q является семейством всех независимых множеств графа G, то число a=maxЅSЅ SОQ называется числом независимости графа G, а множество S , на котором этот максимум достигается, называется наибольшим независимым множеством. Для нашего примера a=3, а S есть (3, 4, 5). Понятие, противоположное максимальному независимому множеству, есть максимальный полный подграф (клика). В максимальном независимом множестве нет смежных вершин, в клике все вершины попарно смежны. Максимальное независимое множество графа G соответствует клике графа G’, где G’ – дополнение графа G. Для нашего примера дополнение G’ приведено на следующем рисунке, клика графа G’ соответствует максимальному независимому множеству графа G. Число независимости графа G’ равно 4, максимальное независимое множество (2, 5, 7, 8), ему соответствует клика графа G. 2. Метод генерации всех максимальных независимых множеств графа Задача решается перебором вариантов.

«Изюминкой» является отсутствие необходимости запоминать генерируемые множества с целью проверки их на максимальность путем сравнения с ранее сформированными множествами. Идея заключается в последовательном расширении текущего независимого множества (k – номер шага или номер итерации в процессе построения). Очевидно, что если мы не можем расширить текущее решение, то найдено максимальное независимое множество. Выведем его и продолжим процесс поиска. Будем хранить текущее решение в массиве Ss (Ss:array of i eger), его первые k элементов определяют текущее решение. Логика вывода. procedure Pri (k:i eger); var i:by e; begi wri el ; for i:=1 o k do wri e (Ss, ’ ‘); e d; В процессе решения нам придется многократно рассматривать вершины графа, смежные с данной. При описании графа матрицей смежности – это просмотр соответствующей строки, при описании списками связи – просмотр списка. Упростим нахождение смежных вершин за счет использования нового способа описания графа. Используем множественный тип данных. Введем тип данных: ype Sse =se of 1. ; и переменную varA:array of Sse ;. Итак, чтобы определить вершины графа, смежные с вершиной i, необходимо просто вызвать соответствующий элемент массива A. Пример. Основная сложность алгоритма в выборе очередной вершины графа. Введем переменную Gg для хранения номеров вершин – кандидатов на расширение текущего решения. Значение переменной формируется на каждом шаге k. Что является исходной информацией для формирования Gg? Очевидно, что некоторое множество вершин, свое для каждого шага (итерации) алгоритма. Логически правомерно разбить это множество вершин на не использованные ранее (Qp) и использованные ранее (Qm). Изменение значений Qp и Qm происходит при возврате на выбор k-го элемента максимального независимого множества. Мы выбирали на k шаге, например, вершину с номером i, и естественно исключение ее из Qp и Qm при поиске следующего максимального независимого множества. Кроме того, при переходе к шагу с номером (k 1) из текущих множеств Qp и Qm для следующего шага необходимо исключить вершины, смежные с вершиной i, выбранной на данном шаге (из определения независимого множества) и, разумется, саму вершину i. Итак, общая логика. procedure Fi d (k:i eger; Qp, Qm: Sse ); var Gg: Sse ; i:by e; begi if (Qp=) he begi Pri (k); exi e d; {черный ящик А} &l ;формирование множества кандидатов Gg для расширения текущего решения (k элементов в массиве Ss) по значениям Qp и Qm&g ;; i:=1; while i&l ;= do begi if i i Gg he begi Ss); {черный ящик Б} &l ;изменение Qp, Qm для этого уровня (значения k) и, соответственно, изменение множества кандидатов Gg&g ;; e d; I c(i); e d; {while} e d; {Fi d} Продолжим уточнение логики. Нам потребуется простая функция подсчета количества элементов в переменных типа Sse . fu c io umber (A: Sse ):by e; var i, c :by e; begi c :=0; for i:=1 o do if i i A he I c(c ); umber:=c ; e d; Используем метод трассировки для того, чтобы найти дальнейшую логику уточнения решения. Будем делать разрывы таблицы для внесения пояснений в работу черных ящиков. k Qp Qm Gg Ss Примечания 1 (1) Выбираем первую вершину 2 (1,4) Итак, первое уточнение черного ящика А.

if Qm&l ;&g ;[] he &l ;черный ящик АА &g ; else Gg:=Qp; Его суть в том, что если выбирать из ранее использованных вершин нечего, то множество кандидатов совпадает со значением Qp, и далее по логике мы «тупо» выбираем первую вершину из Qp. Переходим к следующему вызову процедуры Fi d. 3 (1,4) Вывод первого максимального независимого множества и выход в предыдущую копию Fi d. 2 (1,5) Исключаем вершину 4 из Qp и включаем ее в Qm. Продолжает работу цикл while процедуры Fi d. Выбираем следующую вершину – это вершина 5. И вызываем процедуры Fi d с другими значениями параметров. 3 (1,5) Вывод второго максимального независимого множества. 2 Цикл while закончен, выход в предыдущую копию процедуры Fi d. Уточнение черного ящика Б. Первое: необходимо исключить вершину i из Qp и включить ее в Qm. Второе: следует откорректировать множество Gg. Выбор на этом шаге вершин, не смежных с i, приведет к генерации повторяющихся максимальных независимых множеств, поэтому следует выбирать вершины из пересечения множеств Qp и A; if umber (Qp A⋙ Следующий шаг – выход в предыдущую версию Fi d, при этом значение k равно 1. 1 Однако после работы черного ящика Б имеем следующие значения переменных 1 (2) 2 (2,3) 3 (2,3,5) 4 Вывод третьего максимального независимого множества. 3 2 Согласно логике черного ящика Б множество кандидатов Gg становится пустым. 1 (3) 2 Итак, мы первый раз попадаем в процедуру Fi d, и множество Gm при этом не пусто. Должна работать логика черного ящика АА. Замечание 1. Если существует вершина j, принадлежащая Qm, такая, что пересечение A и Qp пусто, то дальнейшее построение максимального независимого множества бессмысленно – вершины из A не попадут в него. Замечание 2. Если нет вершин из Qm, удовлетворяющих первому замечанию, то какую вершину из Qp следует выбирать? Ответ: вершину iО(QpЗA) для некоторого значения jОQm, причем мощность пересечения множеств A и Qp минимальна. Данный выбор позволяет сократить перебор. Итак, логика черного ящика АА. begi del := 1; for j:=1 o do if j i Qm he if umber (A Qp); e d; Gg:=Qp A; e d Закончим трассировку примера. 2 1 Выход в основную программу. Мы нашли все максимальные независимые множества. 3. Доминирующие множества Для графа G=(V, E) доминирующее множество вершин есть множество вершин SМV, такое, что для каждой вершины j, не входящей в S, существует ребро, идущее из некоторой вершины множества S в вершину j. Доминирующее множество называется минимальным, если нет другого доминирующего множества, содержащегося в нем. Пример. Доминирующие множества (1, 2, 3), (4, 5, 6, 7, 8, 9), (1, 2, 3, 8, 9), (1,2, 3, 7) и т.д. Множества (1, 2, 3), (4, 5, 6, 7, 8, 9) являются минимальными. Если Q – семейство всех минимальных доминирующих множеств графа, то число b=mi ЅSЅ SОQ называется числом доминирования графа, а множество S , на котором этот минимум достигается, называется наименьшим доминирующим множеством. Для нашего примера b=3. Задача. Пусть город можно изобразить как квадрат, разделенный на 16 районов. Считается, что опорный пункт милиции, расположенный в каком-либо районе, может контролировать не только этот район, но и граничащие с ним районы.

Подсостояние это состояние, которое является составной частью другого состояния, именуемого суперсостоянием или составным состоянием. Такое представление означает, что состояние можно разбить на несколько подсостояний. Эти подсостояния могут существовать последовательно или параллельно. Параллелизм подсостояний означает, что один объект может быть занят в двух независимых поведенческих множествах. Это справедливо для нашего объекта «классной доски» (blackboard). При обработке каждого возможного расписания он должен обновлять соответствующие структуры и выполнять другие обслуживающие процедуры. Каждое подсостояние отображается в отдельном разделе. Подсостояния синхронизируются и объединяются перед выходо м из составного состояния. Когда одно подсостояние подходит к концу, оно ожидает, пока другие состояния подойдут к концу, после чего подсостояния снова соединяются в одно. На рис. 10.16 показана диаграмма состояний для объекта blackboard, который генерирует расписание для студентов. Состояние Генерирование расписания (с м. рис. 10.16) яв л яется составны м

1. Динамическое программирование, алгоритмы на графах

2. Линейное и динамическое программирование

3. Динамическое программирование

4. Динамическое программирование

5. Выбор параметров контроля с использованием метода динамического программирования и метода ветвей и границ

6. Счётные множества
7. Нечеткие множества в системах управления
8. Кто открыл множество Мандельброта?

9. Аксиоматика теории множеств

10. Счётные множества

11. Градиентный алгоритм для систем независимости с отрицательными весами

12. Применение теории нечетких множеств к финансовому анализу предприятий

13. Франция с множеством лиц

14. Максимальное ускорение алгоритма поиска

15. Множества

16. Элементы теории множеств

Подставка для колец Zoola "Кролик", хром.
Серия стильных и функциональных держателей для украшений от Umbra. Они предназначены как для хранения украшений, так и общего декора
590 руб
Раздел: Подставки для украшений
Подгузники Moony, 6-11 кг, экономичная упаковка, 62 штуки.
Максимально удобны и просты в применении. "Дышащая поверхность" подгузников обеспечивает доступ воздуха к коже ребенка, а
1423 руб
Раздел: 6-10 кг
Рамка деревянная со стеклом, формат 40х40 см, арт. 2N66.
Размер: 40х40 см. Цвет: клён. Материал: дерево.
404 руб
Раздел: Багетные рамы, для икон

17. Алгоритмические языки: использование множеств

18. ЛИСП-реализация основных операций над нечеткими множествами

19. Определение связанного множества пикселей на бинарном изображении

20. Программирование алгоритма цифровой подписи ГОСТ Р 34.10-94

21. Разработка статических и динамических библиотек на языке программирования С/C++ в операционных системах UNIX

22. Задачи линейного программирования. Алгоритм Флойда
23. Измеримые множества
24. Размерность конечных упорядоченных множеств

25. Структура и алгоритмы работы спутниковых радионавигационных систем

26. Генетические алгоритмы

27. Россия и независимые государства (перевод из "Economic and Post-Soviet Economic Structure and Performance")

28. Путь к независимости или Ганди как символ свободы

29. Управление потоками данных в параллельных алгоритмах вычислительной линейной алгебры

30. Распределенные алгоритмы

31. Информационные потоки в ЭВМ. Алгоритм работы процессора

32. Разработка программной и аппаратной поддержки к методическим указаниям "Программирование микроконтроллеров"

Швабра для пола, с отжимом.
Швабра может использоваться для мытья пола, стен и окон. Пригодна для чистки ковров. Моющая губка - 27 см. Ручка - телескопическая, длина
331 руб
Раздел: Швабры и наборы
Игра "Городки".
Игра в городки заключается в выбивании фигур, построенных из пяти городков, с ограниченной площадки, называемой "городом",
378 руб
Раздел: Городки
Конструктор "Цветной", 65 деталей.
Конструктор - это игра развивающая кругозор, знакомящая с различными формами и цветами, а также развивающая воображение Вашего ребёнка.
584 руб
Раздел: Деревянные конструкторы

33. Алгоритмы сортировки

34. Языки и технология программирования. Начальный курс /Pascal/

35. Динамические объекты /TurboPacal/

36. Объектно-ориентированное программирование на С с использованием библиотеки OpenGL

37. Программирование на С

38. Программирование - интерфейс RS-232
39. Динамическое распределение памяти
40. Динамическое представление данных

41. Системное программирование

42. Аналитический обзор книги "Программирование на языке ассемблера..."

43. Математическое программирование

44. Системы программирования

45. Языки программирования

46. Понятие, назначение и составные элементы систем программирования

47. Лекции по высокоуровневым методам информатики и программированию

48. Курсовая работа по основам программирования. Игра "Паровоз"

Каталка-автомобиль "Sokol" (с ручкой).
Каталка-автомобиль "Sokol" рекомендуется для малышей, которые пока еще неуверенно сидят и часто падают. Эта модель каталки
2249 руб
Раздел: Каталки
Пазл "Арктика", 75 элементов.
Яркий красочный пазл познакомит ребенка с удивительным миром животных Северного полюса. Это и белые медведи, и морские котики, и белый
548 руб
Раздел: Пазлы (54-99 элементов)
Подгузники-трусики "Pampers. Pants. Джамбо", Maxi (9-15 кг), 52 штуки.
Для активных и любознательных мальчиков и девочек так важен комфорт, поэтому Pampers разработал универсальные подгузники-трусики Pampers
1117 руб
Раздел: Более 11 кг

49. Двунаправленный динамический список

50. Помощь в обучении программированию

51. Программирование на С++

52. Сравнительный анализ языков программирования JavaScript и VBScript

53. Понятие алгоритма, его свойства. Описание алгоритмов с помощью блок схем на языке Turbo Pascal

54. Общая терминология программирования
55. Алгоритм создания базы данных складского учета
56. Программирование логической игры на visual basic

57. Тест на языке программирования Visual Basic

58. Учебник по программированию на Java для мобильных устройств

59. Структура и программирование ПЛИС фирмы Altera в САПР Quartus II, её применение в лабораторном стенде

60. Практика оператора (WINDOWS 95, MICROSOFT WORD 97, MATHCAD, ЯЗЫКИ ПРОГРАММИРОВАНИЯ, ЭЛЕКТРОННЫЕ КНИГИ, VISIO, Norton Utilites 3.0 for Windows 95)

61. Эволюция языков программирования

62. Программирование на языке Турбо Паскаль

63. Разработка отказоустойчивой операционной системы реального времени для вычислительных систем с максимальным рангом отказоустойчивости

64. Понятие об алгоритмах

Перчатки виниловые одноразовые, размер M, 100 штук.
Виниловые одноразовые перчатки применяются во время разных видов работ: в пищевой сфере, косметологии, при уборке. Перчатки мягкие и
305 руб
Раздел: Перчатки
Трусики Merries Юниор, 12-22 кг, экономичная упаковка, 38 штук.
Изготовлены из чистого хлопка, гладкого как шёлк и очень мягкого на ощупь, удобны в период обучения малыша к горшку; надеваются и
1448 руб
Раздел: Обычные
Багетная рама "Sally" (цвет: серый+золото), 30x40 см.
Багетные рамы предназначены для оформления картин на холсте, на картоне, а также вышивок и фотографий. Оформленное изделие всегда
504 руб
Раздел: Размер 30x40

65. Лабораторная работа №4 по "Основам теории систем" (Послеоптимизационный анализ задач линейного программирования)

66. Лабораторная работа №2 по "Основам теории систем" (Решение задач линейного программирования симплекс-методом. Варианты разрешимости задач линейного программирования)

67. Адаптивное параметрическое оценивание квадратно-корневыми информационными алгоритмами

68. Решение оптимизационной задачи линейного программирования

69. Решение задач линейного программирования

70. Постановка задачи линейного программирования и двойственная задача линейного программирования.
71. Транспортные сети. Задача о максимальном потоке в сети
72. Использование алгоритмов при изучении орфографии в начальных классах

73. Гана до обретения независимости (Доклад)

74. Расчет и построение тягово-динамической характеристики тягача с гидромеханической трансмиссией

75. Тепловой и динамический расчет двигателей внутреннего сгорания

76. Устройство динамической индикации

77. Разработка средств оценки эффективности алгоритмов поиска и обнаружения целей прицельных радиоэлектронных комплексов

78. Методы и алгоритмы компоновки, размещения и трассировки печатных плат

79. Структура и программирование ПЛИС фирмы Altera в САПР Quartus II, её применение в лабораторном стенде

80. Технология производства, прогнозирования, программирования и планирования урожаев

Автомобиль со звуковым сигналом "Джип-каталка с ручкой", красный.
Отличная мини-машинка белорусского производства, выполненная по лицензии испанской компании Molto — настоящая находка для энергичных
2126 руб
Раздел: Каталки
Логическая игра "IQ-ХоХо", арт. SG 444 RU.
Заполните игровое поле десятью двухсторонними деталями головоломки, располагая Х и О в определённой последовательности. Выполните все 120
525 руб
Раздел: Игры логические
Шары для сухого бассейна, 100 штук.
Шары для сухого бассейна упакованы в тубус, что удобно для хранения и переноски. Количество шаров 100 штук вполне хватит для детской ванны
1037 руб
Раздел: Шары для бассейна

81. Тепловой и динамический расчет двигателя внутреннего сгорания

82. Динамические законы и механический детерминизм

83. Аудит как независимая форма контроля

84. Экономические проблемы Содружества Независимых государств

85. Программирование и планирование в ситуациях коллективного взаимодействия

86. Задача квадратичного программирования с параметром в правых частях ограничений и ее применение при формировании портфеля ценных бумаг
87. Математическое программирование и моделирование в экономике и управлении
88. Обоснование точки безубыточности и зависимость максимально допустимых переменных издержек от объёма продаж

89. Потеря независимости Бретани

90. Финляндия: путь к независимости

91. Рациональная философия истории: ценности, сферы бытия и динамические стратегии

92. Ангола после независимости

93. Борьба народов на Руси за независимость в XIII в.

94. Востановление независимости Армении в IX-XI веках

95. День независимости России старше на 800 с лишним лет

96. Сравнительный анализ нейросетевых реализаций алгоритмов распознавания образов

Шторка антимоскитная "Завитки" с магнитными замками (серая).
Размеры: 100х220 см. Препятствует проникновению насекомых. Не нарушает естественную циркуляцию воздуха. Подходит для любых типов дверных
424 руб
Раздел: Сетки противомоскитные
Органайзер автомобильный "Stels" на спинку сиденья.
Органайзер крепится за стойки подголовника на спинки передних сидений. Прочные регулируемые ремни крепления. Два маленьких сетчатых
406 руб
Раздел: Прочее
Пакеты фасовочные в пластах, 18(+8)x35 см (1000 штук).
Область применения: расфасовка, упаковка продуктов питания и товаров народного потребления как на производстве, так и в быту. Размер:
573 руб
Раздел: Пакеты для продуктов

97. Технологии программирования Web

98. Генетический алгоритм

99. Нормальные Алгоритмы Маркова. Построение алгоритмов из алгоритмов.


Поиск Рефератов на сайте za4eti.ru Вы студент, и у Вас нет времени на выполнение письменных работ (рефератов, курсовых и дипломов)? Мы сможем Вам в этом помочь. Возможно, Вам подойдет что-то из ПЕРЕЧНЯ ПРЕДМЕТОВ И ДИСЦИПЛИН, ПО КОТОРЫМ ВЫПОЛНЯЮТСЯ РЕФЕРАТЫ, КУРСОВЫЕ И ДИПЛОМНЫЕ РАБОТЫ. 
Вы можете поискать нужную Вам работу в КОЛЛЕКЦИИ ГОТОВЫХ РЕФЕРАТОВ, КУРСОВЫХ И ДИПЛОМНЫХ РАБОТ, выполненных преподавателями московских ВУЗов за период более чем 10-летней работы. Эти работы Вы можете бесплатно СКАЧАТЬ.