Теорема Радо-Эдмондса (жадный алгоритм) - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:33:26Z

rollbackEdits.php mass rollback

88.208.225.209 в 04:15, 1 сентября 2022

2022-09-01T04:15:08Z

188.227.78.184: /* Графовый матроид */

2015-05-25T16:39:56Z

‎Графовый матроид

188.227.78.184: /* Графовый матроид */

2015-05-25T16:39:23Z

‎Графовый матроид

188.227.78.184: /* Матричный матроид */

2015-05-25T16:38:18Z

‎Матричный матроид

Shersh в 16:07, 14 марта 2015

2015-03-14T16:07:28Z

Firespace в 21:26, 17 июня 2014

2014-06-17T21:26:22Z

Firespace в 21:24, 17 июня 2014

2014-06-17T21:24:54Z

Firespace в 21:15, 17 июня 2014

2014-06-17T21:15:32Z

Firespace в 20:54, 17 июня 2014

2014-06-17T20:54:17Z

← Предыдущая		Версия 16:33, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	== Теорема Радо-Эдмондса ==		== Теорема Радо-Эдмондса ==
	{{Теорема		{{Теорема

← Предыдущая		Версия 04:15, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	== Теорема Радо-Эдмондса ==		== Теорема Радо-Эдмондса ==
	{{Теорема		{{Теорема

@@ Строка 49: / Строка 49: @@
 === Графовый матроид ===
-Примером задачи, которая решается с помощью жадного алгоритма, является поиск [[Лемма о безопасном ребре| остовного дерева]]. Остовное дерево — это база в [[Примеры матроидов#.D0.93.D1.80.D0.B0.D1.84.D0.BE.D0.B2.D1.8B.D0.B9_.D0.BC.D0.B0.D1.82.D1.80.D0.BE.D0.B8.D0.B4| графовом матроиде]]. Данная задача решается с помощью [[Алгоритм Краскала| алгоритма Краскала]]. Код данного алгоритма совпадает с псевокодом алгоритма поиска базы минимального веса, который был приведен выше.
+Примером задачи, которая решается с помощью жадного алгоритма, является поиск [[Лемма о безопасном ребре| остовного дерева]]. Остовное дерево — это база в [[Примеры матроидов#.D0.93.D1.80.D0.B0.D1.84.D0.BE.D0.B2.D1.8B.D0.B9_.D0.BC.D0.B0.D1.82.D1.80.D0.BE.D0.B8.D0.B4| графовом матроиде]]. Данная задача решается с помощью [[Алгоритм Краскала| алгоритма Краскала]]. Код данного алгоритма совпадает с псевдокодом алгоритма поиска базы минимального веса, который был приведен выше.
 === Матроид паросочетаний ===

@@ Строка 49: / Строка 49: @@
 === Графовый матроид ===
-Примером задачи, которая решается с помощью жадного алгоритма, является поиск [[Лемма о безопасном ребре| остовного дерева]]. Остовное дерево — это база в [[Примеры матроидов#.D0.93.D1.80.D0.B0.D1.84.D0.BE.D0.B2.D1.8B.D0.B9_.D0.BC.D0.B0.D1.82.D1.80.D0.BE.D0.B8.D0.B4| графовом матроиде]]. Данная задача решается с помощью [[Алгоритм Краскала| алгоритма Краскала]]. Код данного алгоритма один в один копирует код алгоритма поиска базы минимального веса, который был приведен выше.
+Примером задачи, которая решается с помощью жадного алгоритма, является поиск [[Лемма о безопасном ребре| остовного дерева]]. Остовное дерево — это база в [[Примеры матроидов#.D0.93.D1.80.D0.B0.D1.84.D0.BE.D0.B2.D1.8B.D0.B9_.D0.BC.D0.B0.D1.82.D1.80.D0.BE.D0.B8.D0.B4| графовом матроиде]]. Данная задача решается с помощью [[Алгоритм Краскала| алгоритма Краскала]]. Код данного алгоритма совпадает с псевокодом алгоритма поиска базы минимального веса, который был приведен выше.
 === Матроид паросочетаний ===

@@ Строка 55: / Строка 55: @@
 === Матричный матроид ===
-Рассмотрим задачу о нахождение максимального количества линейно независимых строк в матрице. Возьмем матрицу с действительными кэффициентами <tex>[a_{ij}]</tex>. Пусть <tex>E</tex> — множество её строк, <tex>I</tex> — семейство множеств линейно независимых строк. Тогда <tex>M = \langle E, I \rangle</tex> — [[Примеры матроидов#.D0.9C.D0.B0.D1.82.D1.80.D0.B8.D1.87.D0.BD.D1.8B.D0.B9_.D0.BC.D0.B0.D1.82.D1.80.D0.BE.D0.B8.D0.B4| матричный матроид]]. Данная задача, как и задача о решении системы линейных алгебраических уравнений, решается с помощью метода Гаусса<ref>[http://e-maxx.ru/algo/linear_systems_gauss MAXimal :: algo :: Метод Гаусса]</ref>
+Рассмотрим задачу о нахождении максимального количества линейно независимых строк в матрице. Возьмем матрицу с действительными кэффициентами <tex>[a_{ij}]</tex>. Пусть <tex>E</tex> — множество её строк, <tex>I</tex> — семейство множеств линейно независимых строк. Тогда <tex>M = \langle E, I \rangle</tex> — [[Примеры матроидов#.D0.9C.D0.B0.D1.82.D1.80.D0.B8.D1.87.D0.BD.D1.8B.D0.B9_.D0.BC.D0.B0.D1.82.D1.80.D0.BE.D0.B8.D0.B4| матричный матроид]]. Данная задача, как и задача о решении системы линейных алгебраических уравнений, решается с помощью метода Гаусса<ref>[http://e-maxx.ru/algo/linear_systems_gauss MAXimal :: algo :: Метод Гаусса]</ref>
 == См. также ==

← Предыдущая		Версия 16:07, 14 марта 2015
Строка 71:		Строка 71:
	[[Категория:Алгоритмы и структуры данных]]		[[Категория:Алгоритмы и структуры данных]]
	[[Категория:Матроиды]]		[[Категория:Матроиды]]
		+	[[Категория:Основные факты теории матроидов]]

@@ Строка 4: / Строка 4: @@
 Радо-Эдмондса
 |statement=
-На носителе [[Определение матроида| матроида]] <tex>M = \langle X, I \rangle</tex> задана весовая функция <tex>\omega: X \to \mathbb R</tex>. Пусть <tex>A \in I</tex> {{---}} множество минимального веса среди независимых подмножеств <tex>X</tex> мощности <tex>k</tex>. Возьмем <tex>x: A \cup x \in I</tex>, <tex>x \notin A</tex>, <tex>\omega (x)</tex> {{---}} минимальна.
+На носителе [[Определение матроида| матроида]] <tex>M = \langle X, I \rangle</tex> задана весовая функция <tex>\omega: X \to \mathbb R</tex>. Пусть <tex>A \in I</tex> {{---}} множество минимального веса среди [[Определение матроида| независимых подмножеств]] <tex>X</tex> мощности <tex>k</tex>. Возьмем <tex>x: A \cup x \in I</tex>, <tex>x \notin A</tex>, <tex>\omega (x)</tex> {{---}} минимальна.
 <br> Тогда <tex>A \cup x</tex> {{---}} множество минимального веса среди независимых подмножеств <tex>X</tex> мощности <tex>k + 1</tex>.
 |proof=

@@ Строка 49: / Строка 49: @@
 === Графовый матроид ===
-Примером задачи, которая решается с помощью жадного алгоритма, является поиск [[Лемма о безопасном ребре| остовного дерева]]. Остовное дерево — это [[Определение матроида| база]] в графовом матроиде. Данная задача решается с помощью [[Алгоритм Краскала| алгоритма Краскала]].
+Примером задачи, которая решается с помощью жадного алгоритма, является поиск [[Лемма о безопасном ребре| остовного дерева]]. Остовное дерево — это [[Определение матроида| база]] в графовом [[Определение матроида| матроиде]]. Данная задача решается с помощью [[Алгоритм Краскала| алгоритма Краскала]]. Код данного алгоритма один в один копирует код алгоритма поиска базы минимального веса, который был приведен выше.
 === Матроид паросочетаний ===
-Типичной задачей из этого класса, является поиск наибольшего паросочетания в двудольном графе. Здесь мы имеем дело с [[Примеры матроидов| трансверсальным матроидом]]. Решается эта задача с помощью [[Алгоритм Куна для поиска максимального паросочетания| Алгоритма Куна]].
+Типичной задачей из этого класса, является поиск наибольшего паросочетания в двудольном графе. Здесь мы имеем дело с [[Примеры матроидов| трансверсальным матроидом]]. Решается эта задача с помощью [[Алгоритм Куна для поиска максимального паросочетания| алгоритма Куна]].
 === Матричный матроид ===
-Классической задачей, которую мы рассмотрим, будет нахождение максимального количества линейно независимых строк в матрице. Рассмотрим матрицу с действительными кэффициентами <tex>[a_{ij}]</tex>. Пусть <tex>E</tex> — множество её строк, <tex>I</tex> — семейство множеств линейно независимых строк. Тогда <tex>M = \langle E, I \rangle</tex> — матроид. Задача решается с помощью метода Гаусса<ref>[http://e-maxx.ru/algo/linear_systems_gauss e-maxx:ru:Метод Гаусса]</ref>
+Рассмотрим задачу о нахождение максимального количества линейно независимых строк в матрице. Возьмем матрицу с действительными кэффициентами <tex>[a_{ij}]</tex>. Пусть <tex>E</tex> — множество её строк, <tex>I</tex> — семейство множеств линейно независимых строк. Тогда <tex>M = \langle E, I \rangle</tex> — матроид. Данная задача, как и задача о решении системы линейных алгебраических уравнений, решается с помощью метода Гаусса<ref>[http://e-maxx.ru/algo/linear_systems_gauss MAXimal :: algo :: Метод Гаусса]</ref>
 == См. также ==
@@ Строка 67: / Строка 67: @@
 * [[wikipedia:ru:Жадный алгоритм Радо — Эдмондса | Википедия — Жадный алгоритм Радо-Эдмондса]]
 * [http://www.mathematik.hu-berlin.de/~wilhelm/greedy-vortrag.pdf| Greedy Algorithm And Edmonds Matroid Intersection Algorithm]
-* [http://habrahabr.ru/post/120343/| Habrahabr:Жадные алгоритмы]
+* [http://habrahabr.ru/post/120343/| Habrahabr — Жадные алгоритмы]
 [[Категория:Алгоритмы и структуры данных]]
 [[Категория:Матроиды]]