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

Математика Математика

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

Крючки с поводками Mikado SSH Fudo "SB Chinu", №4BN, поводок 0,22 мм.
Качественные Японские крючки с лопаткой. Крючки с поводками – готовы к ловле. Высшего качества, исключительно острые японские крючки,
58 руб
Раздел: Размер от №1 до №10
Совок №5.
Длина совка: 22 см. Цвет в ассортименте, без возможности выбора.
18 руб
Раздел: Совки
Горшок торфяной для цветов.
Рекомендуются для выращивания крупной рассады различных овощных и цветочных, а также для укоренения саженцев декоративных, плодовых и
7 руб
Раздел: Горшки, ящики для рассады

Градиентный алгоритм для систем независимости с отрицательными весами И.В. Оффенбах, Омский государственный университет, кафедра прикладной и вычислительной математики 1. Основные понятия Пусть E - конечное множество, - непустое семейство его подмножеств. Семейство называется системой независимости, если Множества семейства называются независимыми множествами, а подмножества E, не вошедшие в семейство , - зависимыми. Базой множества называется любое максимальное по включению независимое подмножество F. Базы множества E называются базами системы независимости. Множество всех баз будем обозначать . Введем обозначения: Числа lr(F), ur(F) называются соответственно нижним и верхним рангом множества F. Величина называется кривизной системы независимости (минимум берется по всем ). Очевидно, что для любой системы независимости . Рассмотрим задачу максимизации на системе независимости: где - семейство баз системы независимости , а - аддитивная весовая функция. Для решения задачи (1) применим следующий Алгоритм A: Шаг 0: Упорядочить множество по невозрастанию весов; ; Шаг i: . Если , то ; если i &l ; , то перейти на шаг i 1, иначе результат SA. Алгоритмы такого типа в англоязычной литературе имеют наименование greedy, что обычно переводится как жадный. Жадный алгоритм является дискретным аналогом градиентного алгоритма, поэтому его называют также градиентным алгоритмом. Договоримся далее через SA обозначать результат работы алгоритма A на системе независимости , а через S0 - базу максимального веса Алгоритм A в общем случае не находит оптимального решения и может рассматриваться лишь как приближенный метод решения задачи (1). В связи с этим большой интерес представляет получение оценок погрешности градиентного алгоритма. В работе ) получена следующая нижняя оценка погрешности градиентного алгоритма решения задачи (1). Теорема 1 (Корте и Хаусманн). Пусть - произвольная система независимости. Тогда для любой неотрицательной аддитивной весовой функции задачи максимизации (1) имеет место достижимая оценка где k - кривизна системы . Cистема независимости называется матроидом, если семейство ее баз обладает следующим свойством: В дальнейшем нам понадобится следующая Лемма 1. Доказательство. При lr(E)=ur(E) лемма, очевидно, следует из определения матроида. Рассмотрим случай lr(E)&l ;ur(E). Пусть . Перенумеруем элементы и так, что если среди них есть одинаковые, то они имеют первые m номеров (), иначе m=0. Определим где r=ur(E). Шаг 0: Am=A - база. Шаг i: . Am i-1 - база, следовательно, множество независимо и не база. Если - не база, то мы нашли требуемые базы Am i-1, B и элемент u=am i. Иначе пусть - база. Переход на шаг i 1. Учитывая, что A B зависимо (т.к. B - база и ), алгоритм завершится не позднее, чем на шаге B 1 доказательством леммы. 2. Характеристика и ее свойства Фронтом данного независимого множества F назовем . Fr(F) - это множество элементов, каждый из которых может быть добавлен к F без нарушения его независимости. Именно из этих элементов градиентный алгоритм выберет на очередном шаге самый "тяжелый" для добавления к F.

Введем новую характеристику системы независимости: Она характеризует "узкое место" в работе градиентного алгоритма. Будем называть предбазами максимальные по включению независимые множества, не являющиеся базами. Тогда определение (4) можно записать как поскольку каждое независимое подмножество, которое не является базой, содержится в некоторой предбазе и . Теорема 2. 1) Для систем независимости , базы которых представляют собой все r-элементные подмножества (r-однородные матроиды), где = E , r=ur(E). 2) Для систем независимости, отличных от r-однородных матроидов, Доказательство. 1) Очевидно, т.к. Fr(F) = - F = 1-ur(E) для любой предбазы F. 2) Если матроид (не r-однородный), то . Пусть F - база A. Т.к. F &l ; A , то F не является базой матроида и . Если не матроид, то по лемме 1 . Заметим, что . Замечание. На различных системах независимости может принимать значения от 1 до = E включительно, причем только в случае 1-однородного матроида. Теорема 3 (оценка кривизны). Для любой системы независимости, отличной от 1-однородного матроида, имеет место оценка Доказательство. Если система независимости представляет собой r-однороный матроид, , то k=1 и оценка (6) верна. Иначе , следовательно, и т.к. и (), то Пусть дана система независимости , через (через ) обозначим такое минимальное число, что существует весовая функция , ровно () значений которой отрицательны, и SA (S0) содержит по крайней мере один элемент с отрицательным весом. Теорема 4. для любой системы независимости . Доказательство. Пусть . Присвоим элементам множества F0 вес E , элементам Fr(F0) вес -1, а остальным элементам вес 0. Тогда SA и S0 будут содержать элементы с отрицательным весом и, следовательно, и (всего отрицательных весов ). Если число "отрицательных" элементов меньше , то SA и S0 не могут содержать элементов с отрицательным весом (для SA это очевидно. Если же S0 содержит "отрицательные", то рассмотрим подмножество его "неотрицательных" элементов C. В силу определения мы можем добавлять к C "неотрицательные" элементы, пока не получим базу, вес которой строго больше веса S0). Следовательно, и . Замечание. Отрицательность здесь не играет принципиальной роли. Основной ее смысл в том, что выделяется класс "отрицательных" элементов, вес каждого из которых меньше веса любого "неотрицательного". К примеру, теорему 4 можно интерпретировать так: S0 и SA не содержат ни одного из наименьших по весу элементов. 3. Оценки погрешности  градиентного алгоритма Лемма 2. Пусть - произвольная система независимости, - весовая функция, допускающая отрицательные веса. Если при этом веса всех элементов SA неотрицательны, то справедлива оценка (2). Доказательство. Рассмотрим новую задачу, в которой все отрицательные веса исходной задачи сделаем нулевыми, оставив тот же порядок элементов (для новой задачи используются обозначения c', S'A, S'0). Тогда S'A=SA, c'(S'A)=c(SA) и . А поскольку в новой задаче все веса неотрицательны, то теорема 1 справедлива и Из теоремы 4 и леммы 2 непосредственно следует Теорема 5. Пусть дана система независимости и весовая функция , количество отрицательных значений которой меньше, чем .

Тогда Теперь рассмотрим ситуацию, когда нет ограничения на число элементов отрицательного веса. Хорошо известна теорема Радо-Эдмондса, которая утверждает, что если система независимости является матроидом, то для произвольной неотрицательной весовой функции градиентный алгоритм всегда находит точное решение задачи (1). Нетрудно показать, что этот результат остается верным и для случая, когда допускаются отрицательные веса. Однако из следующей теоремы вытекает, что если система независимости отлична от матроида, то в общем случае невозможно получить оценку погрешности градиентного алгоритма. Теорема 6. Если система независимости отлична от матроида, то для произвольных существует такая весовая функция , что и . Причем, если , то существует с этим же свойством. Доказательство. Так как отлична от матроида, то по лемме 1 , B =lr(E), и . Рассмотрим два случая: 1) . Среди всех баз, которые являются подмножествами выберем максимальную по мощности базу C. Присвоим всем элементам вес, условно говоря, , элементам вес , а элементу u вес . Если S0 содержит u, то , иначе, очевидно, . А т.к. , то нетрудно понять, что . 2) . Среди всех баз, которые являются подмножествами , выберем базу C, для которой минимальна. Пусть v произвольный элемент . Присвоим элементам вес , элементу u вес , элементу v вес , а всем остальным элементам вес 0 (в этом случае ). Т.к. минимальна, то любая база, веса отличного от и не содержащая u, содержит v, поэтому . В обоих случаях можно так упорядочить элементы равного веса, что SA=A и . Замечание. Задачу максимизации с весами можно интерпретировать как задачу минимизации с весами (весовой функцией c'(e)=-c(e)). Теорема 6 показывает, что для любой системы независимости, отличной от матроида, и задачи минимизации на ней (все веса неотрицательные) в принципе не может существовать гарантированной оценки погрешности градиентного алгоритма. Список литературы Hausma D., Kor e B. Lower bou ds o he wors -case complexi y of some oracle algori hms // Discre e Ma h. 1978. V.24. 3. P.261-276. Kor e B. Approxima ive algori hms for discre e op imiza io problems // A als of Discre e Ma h. Ams erdam: or h-Holla d. 1979. V.4. P.85-120.

Меновая концепция в этнологии и буржуазная политэкономия... сводят общественное воспроизводство к сфере обращения. Сохраняется лишь объективная видимость в том виде, как она описана социусом, без учета реальной инстанции, которая ее записывает, а также экономических и политических сил, с помощью которой она записана... Первобытные формации оральны, вокальны, но не потому, что у них нет графической системы: танец на земле, рисунок на стене, отметка на теле являются графическими системами, гео-графизмом, гео-графией. Эти формации оральны исключительно потому, что имеют графическую систему, независимую от голоса, которая не равняется на голос, не подчиняется ему, но присоединена к нему, скоординирована с ним. Иначе обстоят дела... в случае линейного/фонетического/ письма: цивилизации перестают быть оральными лишь в случае потери независимости и собственной структуры графической системы: именно равняясь на голос, графизм его вытесняет, индуцируя фиктивный голос. /Леруа-Гуран прекрасно эти два полюса описал: пара голос-слух и пара рука-графизм/

1. Алгоритм выбора и реализации предпринимательской идеи

2. «Сократический поворот» в философии: идеи и метод философии Сократа

3. Методы проявления системной идеи. Эвристические методы исследования систем управления

4. Новые и сверхновые звезды (Доклад)

5. Kитообразные и их особенности (Доклад)

6. Обитатели подводного мира (Доклад)
7. Факторы вызывающие мутацию (Доклад)
8. Мерзлотные явления в земной коре (кpиолитология) (. Иpкутская область. Доклад)

9. Особенности озёр России (Доклад)

10. Греция (Доклад)

11. Коста-Рика (Доклад)

12. Озеро Байкал (Доклад)

13. Саудовская Аравия (Доклад)

14. Таиланд (Доклад)

15. Урбанизация и заселенность территории (Доклад)

16. Экономическое развитие Западносибирского региона (Доклад)

Набор детской посуды "София. Дисней", 3 предмета.
Детский набор посуды "София" сочетает в себе изысканный дизайн с максимальной функциональностью. Предметы набора выполнены из
447 руб
Раздел: Наборы для кормления
Набор для уборки Vileda "Easy Wring. Turbo", швабра+ведро с педальным отжимом.
Набор Vileda "Easy Wring. Turbo" состоит из плоской швабры с телескопической ручкой и ведра с педальным отжимом. Подходит для
3699 руб
Раздел: Швабры и наборы
Брелок для поиска ключей.
Брелок для поиска ключей - просто находка для тех, кто часто теряет ключи либо какие-нибудь вещи в доме. Просто прикрепите брелок к
315 руб
Раздел: Пластиковые брелоки

17. Понятие государственного бюджета (Доклад)

18. Мусульманское право (Доклад)

19. Доклад: Страны мира во второй половине XX века. Франция.

20. Внешнеэкономические сделки: правовое регулирование и коллизии (Доклад)

21. Возникновение и идеи правового государства

22. Идеи правого государства и его основные признаки
23. Идеи декабризма в комедии Грибоедова "Горе от ума"
24. Владимир Галактионович Короленко (Доклад)

25. Ради чего стоит жить, или почему погасло сердце Данко ? ("Старуха Изергиль" А.М.Горького)

26. Бальзак: структура и основные идеи "Человеческой комедии"

27. Крушение идеи "сверхчеловека" в романе Ф.М. Достоевского "Преступление и наказание"

28. Биография Джеральда Даррелла (Доклад)

29. Иван Сергеевич Тургенев. Жизнь и творчество (Доклад)

30. Джордано Бруно и его философские идеи

31. Национально-освободительная война сирийского и ливанских народов в 1919-1927 гг. (Доклад)

32. Политические и правовые идеи Реформации

Пеногенератор для минимоек, для пистолета 375 серии.
Пеногенератор для мойки высокого давления ЗУБР предназначен для расширения функциональности моек ЗУБР. Регулировка выхода пены. Большой
1855 руб
Раздел: Мойки высокого давления
Настольная игра "Маленький балансир".
Классическая настольная игра – балансир. Смешные, зеленые лягушата прыгают в пруду, нужно помочь им забраться на кувшинки. Настольная игра
1699 руб
Раздел: Игры на ловкость
Сейф-книга Alparaisa СС0072/1 "Вокруг света", 17х11х5 см.
Размеры: 17х11х5 см. Бокс-сейф в виде книги для хранения мелких ценных вещей. Встроенный замок, запирающийся на ключ. Аксессуары: ключ - 2 штуки.
572 руб
Раздел: Копилки

33. Московский Кремль (Доклад)

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

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

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

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

38. Написание игровой программы Tetris и описание алгоритма
39. VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования
40. Алгоритм создания базы данных складского учета

41. Разработка диалоговой системы, оформленной в виде пакета прикладных программ и реализующей идею искусственного интеллекта (WinWord, PASCAL)

42. Применение метода частотных диаграмм к исследованиям устойчивости систем с логическими алгоритмами управления

43. Основные определения и теоремы к зачету по функциональному анализу

44. Теорема Пифагора и способы ее доказательства

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

46. Комплексные числа и действия с ними (Доклад)

47. Некоторые Теоремы Штурма

48. Практика перевода числа из одной системы счисления в другую + блок-схема алгоритма определения наименьшего числа

Наклейки на стену "Космос", светящиеся в темноте (62 штуки).
Удивительный набор "Космос" от Djeco представляет собой 62 фосфоресцентные пластиковые наклейки для декора комнаты. Наклейки
879 руб
Раздел: Интерьерные наклейки
Овощечистка "Mayer & Boch".
Овощечистка - это удобный инструмент, с помощью которого удобно чистить овощи и фрукты как с тонкой, так и со слишком толстой кожурой.
308 руб
Раздел: Овощечистки, рыбочистки
Автомобиль со звуковым сигналом "Джип-каталка", красный.
Автомобиль Джип-каталка - это удобное транспортное средство для малыша! Каталка сделана в виде машинки. Малыш отталкиваясь ножками сможет
1698 руб
Раздел: Каталки

49. Хромосомные болезни (Доклад)

50. Дознание. Его виды (Доклад)

51. Изучение и разработка очистки стоков от ионов тяжелых металлов (Доклад)

52. Чернобыльская авария (Доклад)

53. Обучение в Германии (Доклад)

54. Идеи развития в трудах Я.А. Коменского, М. Монтеня, Ж.-Ж. Руссо
55. Дистанционное обучение: идеи, технологии, проблемы и перспективы
56. Процесс становление власти в России (Доклад)

57. Ангола после обретения независимости (Доклад)

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

59. Легитимность власти (Доклад)

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

61. Получение, использование цемента и его продуктов (Доклад)

62. Попов (изобретатель Радио)

63. Изобретение радио Поповым

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

Шкатулка декоративная "Стиль", 15,5x12,5x11,5 см (бутылочный).
Шкатулка декоративная для ювелирных украшений, с выдвижными ящичками. Размер: 15,5x12,5x11,5 см. Материал: комбинированный.
1586 руб
Раздел: Шкатулки для украшений
Набор ковриков "Kamalak Tekstil" для ванной, 50х50 см и 50x80 см (фиолетовый).
Ковры-паласы выполнены из полипропилена. Ковры обладают хорошими показателями теплостойкости и шумоизоляции. Являются гипоаллергенными. За
607 руб
Раздел: Коврики
Фоторамка на 11 фотографий С31-021 Alparaisa "Family", коричневый, 47x53,5 см.
Размеры рамки: 47x53,5 cм. Размеры фото: - 10х15 см (4 штуки), - 15х10 см (7 штук). Фоторамка-коллаж для 11-ти фотографий. Материал:
868 руб
Раздел: Мультирамки

65. История возникновения радио и радиолокации

66. Эниология как паранаука (Доклад)

67. Идеи раннего христианства

68. Социологическое исследование на тему "Вредные привычки среди молодежи" (Доклад)

69. Концепции "Я" у Ч.Кули и Дж.Мида (Доклад)

70. Этническая специфика (Доклад)
71. Контент-анализ "Городские новости радио "Европа плюс Шахты"
72. Устройство глаза человека (Доклад) (WinWord 98)

73. Дианетика современная наука душевного здоровья (Доклад)

74. Немецкая классическая философия (Доклад)

75. Жизнь и деятельность Роберта Милликена (Доклад)

76. Материализм в учении древнегреческих атомистов (Доклад)

77. Основные идеи русского космизма

78. Зарождение философской традиции (Доклад)

79. Философские идеи И. Канта

80. Пифагорейский союз: история возникновения и основные идеи

Беговел "Funny Wheels Basic" (цвет: голубой).
Беговел - это современный аналог детского велосипеда без педалей для самых маленьких любителей спорта. Удобный и простой в
2550 руб
Раздел: Беговелы
Сковорода чугунная с деревянной ручкой 2505/27, 27 см.
Диаметр: 27 см. Чугунная сковорода с деревянной ручкой. Обладает высокой теплопроводностью, несравнимой износостойкостью, устойчивостью к
755 руб
Раздел: Сковороды чугунные
Магический шар 8.
Во все времена люди желали знать ответы на интересующие их вопросы, для этого они прибегали к помощи всевозможных гадалок, шаманов, и
585 руб
Раздел: Прочее

81. Софисты и Сократ (Мир идей Платона. Этика Аристотеля)

82. Джордано Бруно и его философские идеи

83. Философские идеи как основания учений о воспитании и образовании

84. Крахмал (Доклад)

85. Нефть (Доклад)

86. Банковская система СССР (Доклад)
87. Кредитные ресурсы коммерческого банка (Доклад)
88. Инвестиционные банки (Доклад)

89. Товарная биржа (Доклад)

90. Безналичные расчеты (Доклад)

91. Появление денег (Доклад)

92. Адам Смит (Доклад)

93. Кейнс и кейнсианство (Доклад)

94. Использование маркетингового подхода при выживании ВУЗов в современных условиях (Доклад)

95. Анализ макроэкономических показателей США (Доклад)

96. Подходы к поэтапному формированию платежного союза (Доклад)

Набор цветных карандашей "Progresso", 24 штуки.
Цветные монолитные карандаши в лаковой оболочке. Бездревесные цветные карандаши "Progresso" имеют прочное лаковое покрытие,
793 руб
Раздел: 13-24 цвета
Кружка "Ниндзя".
Всем, кто очарован искусством японских самураев, наверняка понравится этот чайный набор: необычная глазастая кружка в тканевой чёрной
524 руб
Раздел: Кружки
Брелок "FIFA 2018. Забивака с подвесками".
Брелок с символикой чемпионата мира FIFA 2018. Материал: металл.
562 руб
Раздел: Брелоки, магниты, сувениры

97. ЭКЮ - (European Currency Unit) (Доклад)

98. Секретарь (Доклад)

99. Анализ альтернатив и выбор стратегии (Доклад)


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