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

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

Модификация алгоритма определения клик графа с параметрической адаптацией

Чашка "Неваляшка".
Ваши дети во время приёма пищи вечно проливают что-то на ковёр и пол, пачкают руки, а Вы потом тратите уйму времени на выведение пятен с
222 руб
Раздел: Тарелки
Крючки с поводками Mikado SSH Fudo "SB Chinu", №4BN, поводок 0,22 мм.
Качественные Японские крючки с лопаткой. Крючки с поводками – готовы к ловле. Высшего качества, исключительно острые японские крючки,
58 руб
Раздел: Размер от №1 до №10
Коврик для запекания, силиконовый "Пекарь".
Коврик "Пекарь", сделанный из силикона, поможет Вам готовить вкусную и красивую выпечку. Благодаря материалу коврика, выпечка не
202 руб
Раздел: Коврики силиконовые для выпечки

В.А. Литвиненко И.Ю. Черненко 1. Основные положения Кликой графа называется максимальный полный подграф, который не входит ни в один полный подграф более высокого порядка /1/ . Под точностью решения задачи определения клик графа будем понимать количество выделенных клик. При этом, если выделены все клики графа, то точность решения равна 100%. Рассматривается класс нериентированных графов без петель и кратных ребер. Комбинаторная сложность точных алгоритмов определения клик графа приводит к необходимости использовать приближенные методы при решении задач большой размерности. К таким задачам, в частности, относятся различные задачи конструкторского проектирования интегральных схем, в которых алгоритмы определения клик графа применяются в качестве алгоритмов проектных операций .  Известные алгоритмы /1,2/ позволяют определять только такие семейства клик графа, свойства и мощность которых зависят от структуры решаемых графов и последовательности выполнения самого алгоритма. От качественного решения алгоритмов проектных операций существенно зависит качество решения алгоритмов проектных процедур. Основными факторами, влияющими на качество выполнения алгоритмов проектных операций, являются: требуемая точность решения; ресурс времени, отведенный на выполнение проектной операции; размерность конкретной задачи. Из указанных факторов известные приближенные методы позволяют учитывать только ограничение на время выполнения алгоритма - ресурс времени путем прерывания решения в момент его истечения /2/ . Однако, возможна ситуация, когда ресурса времени достаточно для получения даже точного решения, а требуемая точность и размерность задачи позволяют выполнить алгоритм за время меньшее, чем ресурс времени. Возможна и другая ситуация, когда размерность задачи и ресурс времени не позволяют получить требуемую точность решения. Возможность алгоритмическими методами учитывать такие случаи позволяет оптимизировать время выполнения алгоритма проектной операции проектной процедуры и тем самым повышать эффективность использования математического и программного обеспечения САПР. 2. Базовый алгоритм В /3/ разработан алгоритм определения клик графа, отличающийся от известных возможностью адаптации к изменению ресурса времени, требуемой точности и размерности самой задачи, предназначенный для исследования неориентированных графов без петель и кратных ребер. В основу алгоритма положен метод параметрической адаптации, который позволяет с помощью входных параметров “настраивать” алгоритм определения клик графа на  получение решений с различной степенью точности. При этом  точность решения может изменяться от получения  точного решения задачи определения клик графа, т.е. определения всех клик графа,  до  определения такого  количества клик графа, которого достаточно для получения  решения проектной процедуры,  для которой задача определения клик графа используется в качестве алгоритма проектной операции. Таким образом, рассмотренный алгоритм позволяет получать решения с различной степенью точности и при этом допускает принципиальную возможность определения всех клик графа , т.е

. получать точное решение. Этот алгоритм используется в качестве базового алгоритма для модифицированного алгоритма, рассматриваемого в данной  работе. В основу базового алгоритма положена следующая теорема,  доказанная  в работе /4/. Пусть в графе G=(X,U) имеется вершина  и определена клика  с множеством вершин , где . Тогда, если  выделены все клики, то и  будут выделены все клики. Практическое значение этой теоремы заключается в следующем. Процесс определения всех клик графа в базовом алгоритме состоит  в выделении для каждой вершины клик графа, образованных этой вершиной, который заключается в перечислении полных подграфов и проверке их на максимальность. В соответствие с теоремой  для каждой вершины  можно исключить из процесса построения полных подграфов рассмотрение вершин, вошедших в одну какую-то клику, и процесс построения полных подграфов вести только для оставшихся вершин, смежных  с . При этом клики, содержащие одновременно  вершину  и вершины, исключенные из рассмотрения, будут выделены при выделении клик, содержащих одновременно вершину  и оставшиеся вершины. Если для каждой вершины  исключать из рассмотрения вершины, смежные с  и вошедшие только в одну клику, то в результате выполнение базового алгоритма будут выделены все клики графа. В том случае, если для каждой вершины  исключать из рассмотрения вершины, образующие несколько таких клик графа, то базовый алгоритм будет выделять не все клики, а только некоторое их подмножество, так как часть клик будет потеряна. Точность решения задачи определения клик графа в этом случае будет уменьшаться с увеличением числа клик,  вершины которых исключаются из рассмотрения. Обозначим такое число клик  l. Тогда, задавая значения l, можно “управлять” точностью решения, получаемого базовым алгоритмом, настраиваивая  его на получение решение с различной степенью точности.В таком случае l  является параметром базового алгоритма определения клик графа. Использование параметра для адаптации алгоритма к внешним условиям – требуемой точности решения и послужило введением названия класса алгоритмов – алгоритмы с параметрической адаптацией. Отметим, что при увеличении l в предельном случае точность решения, которую можно получить с помощью базового алгоритма, соответствует количеству клик графа,  которое может быть получена с помощью  алгоритма  определения   клик,  покрывающих   все  ребра  графа  /1,2/.Это означает, что с помощью базового алгоритма нельзя получить решение с нулевой точностью. Рассмотренный базовый алгоритм положен в основу модифицированного алгоритма, предлагаемого в дипломной работе. 3. Модифицированный алгоритм Процесс перебора полных подграфов для каждой вершины  в базовом алгоритме связан с перебором всех  вершин, смежных с вершиной .  Тогда чем больше вершин, смежных с вершиной , будет исключено из рассмотрения, тем больше будет сокращен перебор полных подграфов. В соответствие с рассмотренной выше теоремой для каждой вершины  из рассмотрения можно исключить вершины только одной клики, в которую входит вершина . Тогда, если такая клика, имеет как можно большее количество вершин, то из рассмотрения будут исключено большее число вершин, смежных вершине .

Таким образом,  одним из возможных путей улучшения базового алгоритма может быть определение для каждой вершины  одной клики, содержащей наибольшее количество вершин, вершины которой будут исключаться из рассмотрения. В  работе предлагается для реализации этого пути рассматривать вершины графа в порядке, соответствующем уменьшению локальных степеней вершин.Это связано с предположением, что вершины, имеющие большую локальную степень, вероятнее всего будут образовывать и клики, содержащие большее число вершин. Такой подход и положен в основу модификации базового алгоритма. 4. Оценка сложности модифицированного алгоритма Оценим сложность модифицированного алгоритма.Оценка сложности  производится с целью показать аналитически правильность сделанного выше предположения. Алгоритм соотоит из иттераций, каждая из которых связана с одной стокой треугольной матрицы смежности. Нетрудно заметить, что трудоемкость выполнения одной иттерации  будет наибольшей для первой строки матрицы смежности. Поэтому для того, чтобы оценить преимущество  модифицированного алгоритма,  достаточно оценить сложность определения клик графа для первой строки матрицы смежности. Пусть – количество столбцов первой строки матрицы, а b - средняя мощность клик в графе. Тогда, если оценивать количество операций логического умножения элементов двух столбцов двух строк матрицы смежности, то количество операций определения одной клики будет составлять сумму членов арифметической прогрессии с шагом 1, первый член которой равен ( -1), а количество членов прогресси равно (b-1), т.е.                                      0,5(b-1)(2 -b- ). Так как вершины каждой первой выделенной клики из рассмотрения исключаются, то количество операций логического умножения элементов строки со строками матрицы, номерам которых в строке соответствуеют значения, равные 1, в худшем случае будет равно (b-1). Таким образом оценка числа операций логического умножения, которые необходимо произвести для элементов строки  , составляет                          O(0,5(b-1)(2 -b-4)( -b)). В соответствие с правилами преобразования O-функций последнее выражение можно преобразовать к следующему виду                                   O(b(2 -b)( -b)). Теперь, при b, стремящемся к , O(0,5(b-1)(2 -b-4)( -b)) ® O( ), а при b, стремящемся к 0,5 ,   O(0,5(b-1)(2 -b-4)( -b)) ® O( ). Таким образом, эффективность модифицированного алгоритма возрастает с увеличением b -средней мощности клик в графе, т.е. аналитичеки подтверждается предположение, положенное в основу модификации базового алгоритма. 5. Реализация модифицированного алгоритма Разработана программа на Borla d C Builder  для Wi dows`95 и проведено исследование эффективности предложенного модифицированного алгоритма на графах размерности до 500 вершин, а также на графах Муна-Мозера, которые являются критическими для задачи определения клик графа, так как содержат набольшее количество клик для графов с одинаковым числом вершин. Программа ориентированна на использование в системах автоматизированного проектирования, а так же в других областях, связанных с решением комбинаторно-логических задач на графах.

С этого времени в биологии утвердилось положение, согласно которому А. не есть нечто внутренне присущее и заранее данное организмам, но всегда возникает и развивается под воздействием трёх основных факторов органической эволюции — изменчивости, наследственности и естественного отбора (а равно и искусственного, т. е. производимого человеком). К понятию А. в эволюционноисторическом аспекте примыкают ненаследственные адаптивные реакции организма (модификации) на изменение условий существования (см. Адаптация физиологическая, Аккомодация). Адаптивность организации обеспечивает выживание любого организма, повышает коэффициент его размножения и снижает коэффициент смертности. Наиболее демонстративно А. проявляется в динамическом соответствии морфо-физиологической организации и приспособительных реакций животного или растения к типичным и ведущим условиям среды, в которой данный организм сложился. Форма и функция как каждого органа, так и всей их совокупности в организме всегда скоррелированы и коадаптированы, т. е. соответствуют друг другу

1. Менструальный цикл и его регуляция

2. Капиталистический цикл и его фазы

3. Цикличность экономического развития. Экономический цикл и его фазы

4. Налоговый контроль в Республике Беларусь и пути его совершенствования

5. Путь среди революций (Блок-лирик и его современники)

6. Модернизация узла блокировки капота автомобиля ЗАЗ-1102 "Таврия" и его модификаций
7. Финансовый кризис в Кыргызстане: формы его проявления и пути преодоления
8. Имидж делового человека и пути его формирования

9. Инвестиционный климат в России и пути его активизации

10. Анализ резервирования кредитных операций КБ и пути повышения его результативности

11. Налогообложение предприятий и пути его совершенствования

12. Девиантное поведение и пути его преодоления

13. Состояние и пути совершенствования учета труда и его оплаты

14. Имидж менеджера и пути его совершенствования

15. Реальное функционирование русского языка и пути его развития

16. Агроэкологическое состояние почвенного покрова ООО "Агро-Союз" Ровенского района и пути его стабилизации

Держатель балдахина с двойным креплением (в пенале).
Крепление для балдахина состоит из двух полых трубок, которые вставляются одна в другую, верхней спирали для балдахина и двух креплений к
303 руб
Раздел: Балдахины, держатели
Пенал "Радужная коллекция", серый-лайм.
Пенал очень компактен, удобен для хранения и переноски карандашей, ручек, фломастеров, кистей. Без наполнения. Размер: 22x11x6,5 см. 1
475 руб
Раздел: Без наполнения
Одеяло байковое "Карапуз" с рисунком (цвет: бежевый).
Байковое одеяло для новорожденных детей и подростков изготовлено из 100% хлопка (натуральная байка), имеет мягкую фактуру полотна,
695 руб
Раздел: Одеяла для детей

17. Воспроизводство стада и пути его улучшения

18. Организация производства молока и основные пути его совершенствования по данным хозяйства ЗАО ПЗ "Нива" Муромский р-н, Владимирской области

19. Кругооборот оборотных средств и пути его ускорения

20. Состояние организации первичного бухгалтерского учета ЗАО "ххх" и пути его совершенствования

21. Анализ состояния делопроизводства и поиск путей его совершенствования

22. Организационный механизм подготовки и принятия нормативных правовых актов в Республике Беларусь и пути его совершенствования
23. Реформирование института подсудности гражданских дел и пути его совершенствования
24. Принцип резолюции в исчислении высказываний и логике предикатов и его модификации

25. Исследование мировоззрения Василия Жуковского путем анализа его поэзии

26. Сложно ли реализовать CRM-проект? О взаимосвязи характера CRM-проекта и его ключевых рисков

27. Анализ состояния рынка логистических услуг и пути его развития

28. Персонал предприятия и пути увеличения эффективности его использования

29. Стимулирование труда и пути его совершенствования

30. Управление персоналом в организации малого бизнеса и пути его совершенствования

31. Пути и методы педагогического опыта и его обобщение

32. Причины суицида в армии и пути его преодоления

Чудо трусики для плавания, от 0 до 3-х лет, трехслойные, арт. 1432, для девочек.
Детские специальные трусики для плавания в бассейне и открытом водоеме. Плотно прилегают, отлично защищают! Изготовлены из хлопка, имеют
376 руб
Раздел: Многоразовые
Шкатулка музыкальная "Балерина и звездное небо".
Музыкальная шкатулка для украшений с классической музыкой. Когда шкатулка открыта - звучит музыка и фигурка кружится. Необычное зеркальце,
1116 руб
Раздел: Шкатулки музыкальные
Подставка для сортировки писем и бумаг "Germanium", черная.
Выполнена из металла (сетка). 5 вместительных секций. Размер - 195х365х205 мм. Цвет - черный.
758 руб
Раздел: Подставки, лотки для бумаг, футляры

33. Тест восьми влечений Сонди и его модификация

34. Анализ финансового состояния ООО НПП "ТТ" и разработка путей улучшения финансовых результатов его деятельности

35. Государственный финансовый контроль и пути его совершенствования

36. Инвестиционный проект по производству электроплит и пути его реализации

37. Налогообложение на предприятии и пути его совершенствования

38. Проблемы оценки финансового состояния и пути его улучшения
39. Финансовый контроль и пути повышения его эффективности
40. Мелиоративное состояние орошаемых земель в Кыргызской Республике и пути его улучшения

41. Анализ объема выработанной продукции и пути его увеличения

42. Меркантилизм как учение о богатстве страны и путях его приумножения

43. Организация складского хозяйства и пути его совершенствования

44. Оценка финансового состояния ООО "Строительные технологии" и пути его улучшения

45. Повышение эффективности работы предприятия путем его реорганизации (на примере ОАО "Горизонт")

46. Анализ финансового состояния предприятия и пути его улучшения

47. Капитальный ремонт пути на щебеночном балласте с укладкой железобетонных шпал с применением машин тяжелого типа

48. Жан Батист Валлен Деламот и его творчество

Музыкальная игрушка "Осьминог".
Веселый "Осьминог" станет настоящим музыкальным центром для вашего малыша, в нем так много звуков! Ребенок будет с восторгом
335 руб
Раздел: Животные
Брелок оленёнок "Rike. Принцезин Лиллифи. Prinzessin Lillifee".
Брелок олененок Rike с карабином. Отличное украшение для сумки и рюкзака.
886 руб
Раздел: Детские брелоки
Набор насадок для кондитерского мешка BE-0389/4 "Webber", 4 штуки.
Размеры: Ø3,5х2,5х4 см. Набор кондитерских насадок открывает невообразимое число возможностей сделать десерт роскошным и неповторимым
307 руб
Раздел: Кондитерские принадлежности

49. Внешняя задолженность государства. Пути повышения пользы

50. Солнце и его строение

51. Марс и его спутники

52. Исследование клеточного цикла методом проточной цитометрии

53. Хлорофилл: его свойства и биосинтез

54. Жизнь и творческий путь И.В. Вернадского
55. Пути и способы повышения устойчивости работы РЭА
56. Химическое оружие и проблемы его уничтожения в России

57. Индия. Проблемы и пути их решения

58. Вулканизм на земле и его географические следствия

59. Бюджет и его устройство

60. Государственный бюджет России, проблемы преодоления его дефицита

61. Разгосударствление и приватизация: пути и формы. Опыт России и зарубежных стран

62. Аппарат государственной власти и его структура

63. Государственный служащий и его административно-правовой статус. Классификация государственных служащих

64. Договор подряда и его виды

Багетная рама "Wendy", 30x40 см.
Багетные рамы предназначены для оформления картин, вышивок и фотографий. Оформленное изделие всегда становится более выразительным и
558 руб
Раздел: Размер 30x40
Шкатулка для ювелирных украшений, 16x13 см, арт. 84575.
Шкатулка сохранит ваши ювелирные изделия в первозданном виде. С ней вы сможете внести в интерьер частичку элегантности. Регулярно удалять
592 руб
Раздел: Шкатулки для украшений
Комплект постельного белья Perina "Ника" (цвет: бежевый, 7 предметов).
Комплект постельного белья Perina «Ника» обладает изысканным, утонченным и даже благородным дизайном. Он способен стать подлинным
5356 руб
Раздел: Комплекты в кроватку

65. Потребитель и его права

66. А. Гамильтон и американская Конституция

67. Международный туризм и его роль в развитии экономики Киргизской Республики

68. Судебник 1550 года, его историческое значение

69. Соборное Уложение 1649 г. и его значение

70. Монголо-татарское иго и его последствия
71. М.М.Богословский и его методология по изучению истории России
72. Суверенная Россия на пути радикальной социально-экономической модернизации (90-е годы 20 века - начало 21 века)

73. Финансовый менеджмент и его роль

74. Референдум и его социальная функция

75. Человек, его права и свободы

76. Судебная система РФ и пути ее реформирования

77. Международный комитет красного креста и его роль в установлении гуманитарных норм международных конфликтов

78. Устав муниципального образования и его роль в М.С.У.

79. Понятие налога, налогового права, его система, их функции

80. Государственный долг: понятие, состав и его обслуживание (по Казахстану)

Горка детская большая (2 м).
Горка предназначена для игры на свежем воздухе или в игровой комнате. Есть возможность подключить воду. Игрушка выполнена из качественного
8450 руб
Раздел: Горки
Машинка детская с полиуретановыми колесами "Бибикар-лягушонок", синий.
Вашему крохе едва исполнилось 3 годика, а он уже требует дорогой квадроцикл на аккумуляторе, как у взрослых соседских мальчишек? Никакие
2350 руб
Раздел: Каталки
Брелок "FIFA 2018. Забивака Фристайл! 3D".
Брелок с символикой чемпионата мира FIFA 2018. Материал: ПВХ.
590 руб
Раздел: Брелоки, магниты, сувениры

81. Римское право, его значение в истории правового развития человечества и в современной юриспруденции

82. Страховой рынок и его развитие в РФ

83. Медицинское страхование в России, проблемы его развития

84. Идеи правого государства и его основные признаки

85. Процесс законотворчества и его стадии в России

86. Право граждан на отпуск и гарантия его реализации
87. Развитие финансового контроля и его эффективность в РФ
88. Цикл-метод обучения. (Методика преподавания эстонского языка)

89. Mozart: Symphony #40 in G Minor, K.550 Моцарт: Симфония №40 в си-минор, К. 550

90. Сниженная лексика английского языка и ее перевод на русский язык (на примере перевода новеллы С.Кинга "Долгий путь")

91. Клод Моне (жизненный путь)

92. Томас Гейнсборо и его творчество

93. Жизнь и творческий путь Суйменкула Чокморова

94. Русское юродство как феномен культуры, его национальное значение

95. Фараон Эхнатон и его жена Нефертити, развитие искусства и культуры при их царствовании

96. Лермонтов в искусстве его времени

Бумага для струйных принтеров "Lomond", 220 г/м, 50 листов, матовая, двухсторонняя, А4.
Изображение отпечатанное на матовой бумаге, не бликует, линии высококонтрастные, чистые тона имеют характерную бархатистую глубину.
355 руб
Раздел: Фотобумага для цветной печати
Пресс для формирования котлет с начинкой "От шефа" 3 в 1.
Мечтаете примерить на себя роль настоящего шеф-повара? Хотите, чтобы Ваши блюда искренне хвалили? С прессом для формирования котлет
328 руб
Раздел: Прочее
Подставка для колец "Кошка", 12 см.
Регулярно удалять пыль сухой, мягкой тканью. Материал: металл (сплав цинка с покрытием золотой краской), стекло. Высота: 12 см. Товар не
365 руб
Раздел: Подставки для украшений

97. Эразм Роттердамский и его «Похвала глупости»

98. Образ автора и его роль в романе А.С. Пушкина "Евгений Онегин"

99. И. А. Бунин и его проза


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