Уточнение разбиения - История изменений

Patarakin в 08:35, 19 октября 2022

2022-10-19T08:35:36Z

← Предыдущая версия		Версия от 11:35, 19 октября 2022
Строка 2:		Строка 2:


	* Упорядоченная последовательность множеств ~~{{Math\|''S''<sub>''i''</sub>}}~~ в семействе в такой форме, как [[Связный список#Двусвязный список (двунаправленный связный список)\|двусвязный список]], который позволяет вставлять новые наборы в середину последовательности.		* Упорядоченная последовательность множеств в семействе в такой форме, как [[Связный список#Двусвязный список (двунаправленный связный список)\|двусвязный список]], который позволяет вставлять новые наборы в середину последовательности.
	* Соответствующая каждому множеству ~~{{Math\|''S''<sub>~~''i''~~</sub>}}~~ [[Коллекция (программирование)\|коллекция]] его элементов, организованная как [[Связный список#Двусвязный список (двунаправленный связный список)\|двусвязный список]] или [[Массив (тип данных)\|массив,]] чтобы обеспечить возможность быстрого удаления отдельных элементов из коллекции. Альтернативно этот компонент структуры данных может быть представлен путем хранения всех элементов всех множеств в одном массиве, отсортированном по идентификатору множества каждого элемента, или путем представления коллекции элементов в любом множестве ~~{{Math\|''S''~~<sub>''i''</sub>}} по его начальной и конечной позициям в этом массиве.		* Соответствующая каждому множеству ''i'' [[Коллекция (программирование)\|коллекция]] его элементов, организованная как [[Связный список#Двусвязный список (двунаправленный связный список)\|двусвязный список]] или [[Массив (тип данных)\|массив,]] чтобы обеспечить возможность быстрого удаления отдельных элементов из коллекции. Альтернативно этот компонент структуры данных может быть представлен путем хранения всех элементов всех множеств в одном массиве, отсортированном по идентификатору множества каждого элемента, или путем представления коллекции элементов в любом множестве <sub>''i''</sub> по его начальной и конечной позициям в этом массиве.
	* С каждым элементом связан набор, к которому он принадлежит.		* С каждым элементом связан набор, к которому он принадлежит.

	Уточнение разбиения также является ключевым этапом в [[Лексикографический поиск в ширину\|лексикографическом поиске]]		Уточнение разбиения также является ключевым этапом в [[Лексикографический поиск в ширину\|лексикографическом поиске]]


	[[Категория:Структуры данных]]		[[Категория:Структуры данных]]

Patarakin в 08:34, 19 октября 2022

2022-10-19T08:34:49Z

@@ Строка 1: / Строка 1: @@
 При разработке [[алгоритм]]ов '''уточнение разбиения''' — это метод представления [[Разбиение множества|разбиения множества]] в виде [[Структура данных|структуры данных,]] которая позволяет разбивать его множества на большее количество меньших множеств. В этом смысле уточнение разбиения двойственно [[Система непересекающихся множеств|системе непересекающихся множеств]], которая также поддерживает разбиение на [[Непересекающиеся множества|непересекающиеся множества,]] но в которой операции объединяют пары наборов. В некоторых приложениях уточнения разбиения, таких как [[лексикографический поиск в ширину]], структура данных поддерживает также порядок наборов в разделе.
 * Упорядоченная последовательность множеств {{Math|''S''<sub>''i''</sub>}} в семействе в такой форме, как [[Связный список#Двусвязный список (двунаправленный связный список)|двусвязный список]], который позволяет вставлять новые наборы в середину последовательности.
@@ Строка 12: / Строка 6: @@
 * С каждым элементом связан набор, к которому он принадлежит.
-Чтобы выполнить операцию уточнения, алгоритм перебирает элементы данного множества {{Mvar|X}}. Для каждого такого элемента {{Mvar|x}} он находит множество {{Math|''S''<sub>''i''</sub>}} которое содержит {{Mvar|x}}, и проверяет, произведено ли пересечение {{Math|''S''<sub>''i''</sub> &cap; ''X''}}. Если нет, он создает второе множество и добавляет {{Math|''S''<sub>''i''</sub>}} в список {{Mvar|L}} множеств, разделенных операцией. Затем, независимо от того, было ли сформировано новое множество, алгоритм удаляет {{Mvar|x}} из {{Math|''S''<sub>''i''</sub>}} и добавляет его к {{Math|''S''<sub>''i''</sub> &cap; ''X''}} В представлении, в котором все элементы хранятся в одном массиве, перемещение {{Mvar|x}} из одного множества в другое может выполняться путем обмена {{Mvar|x}} местами c последним элементом {{Math|''S''<sub>''i''</sub>}} а затем уменьшения концевого индекса {{Math|''S''<sub>''i''</sub>}} и начального индекса нового множества. Наконец, после того, как все элементы {{Mvar|X}} были обработаны таким образом, алгоритм проходит через {{Mvar|L}}, разделяя каждое текущее множество {{Math|''S''<sub>''i''</sub>}} на два, рассматривая оба этих множества как сформированные в результате операции уточнения.
+Уточнение разбиения также является ключевым этапом в [[Лексикографический поиск в ширину|лексикографическом поиске]]
 [[Категория:Структуры данных]]

Patarakin: 1 версия импортирована

2022-10-19T07:30:54Z

1 версия импортирована

← Предыдущая версия	Версия от 10:30, 19 октября 2022
(нет различий)

ru_wikipedia>InternetArchiveBot: Спасено источников — 2, отмечено мёртвыми — 0. Сообщить об ошибке. См. FAQ.) #IABot (v2.0.9

2022-08-20T06:35:38Z

Спасено источников — 2, отмечено мёртвыми — 0. Сообщить об ошибке. См. FAQ.) #IABot (v2.0.9

Новая страница

При разработке [[алгоритм]]ов '''уточнение разбиения''' — это метод представления [[Разбиение множества|разбиения множества]] в виде [[Структура данных|структуры данных,]] которая позволяет разбивать его множества на большее количество меньших множеств. В этом смысле уточнение разбиения двойственно [[Система непересекающихся множеств|системе непересекающихся множеств]], которая также поддерживает разбиение на [[Непересекающиеся множества|непересекающиеся множества,]] но в которой операции объединяют пары наборов. В некоторых приложениях уточнения разбиения, таких как [[лексикографический поиск в ширину]], структура данных поддерживает также порядок наборов в разделе.

Уточнение разбиения является ключевым компонентом нескольких эффективных алгоритмов на [[Теория графов|графах]] и [[Конечный автомат|конечных автоматах]], включая [[Минимизация ДКА|минимизацию ДКА]], [[алгоритм Коффмана – Грэма]] для параллельного планирования и [[лексикографический поиск в ширину]].<ref>{{Citation|last1=Paige|first1=Robert|last2=Tarjan|first2=Robert E.|author2-link=Robert Tarjan|doi=10.1137/0216062|issue=6|journal=[[SIAM Journal on Computing]]|pages=973–989|title=Three partition refinement algorithms|volume=16|year=1987}}.</ref><ref>{{Citation|last1=Habib|first1=Michel|last2=Paul|first2=Christophe|doi=10.1142/S0129054199000125|issue=2|journal=[[International Journal of Foundations of Computer Science]]|pages=147–170|title=Partition refinement techniques: an interesting algorithmic tool kit|volume=10|year=1999}}.</ref><ref>{{Citation|last1=Habib|first1=Michel|last2=Paul|first2=Christophe|doi=10.1007/BFb0028546|pages=25–38|title=STACS 98: 15th Annual Symposium on Theoretical Aspects of Computer Science Paris, France, February 25–27, 1998, Proceedings|volume=1373|year=1998}}.</ref>

== Структура данных ==
Алгоритм уточнения разбиения поддерживает семейство непересекающихся множеств {{Math|''S''''i''}} . В начале алгоритма это семейство содержит единственное множество всех элементов в структуре данных. На каждом шаге алгоритм получает множество {{Mvar|X}}, и каждое множество {{Math|''S''''i''}} в семействе, содержащем элементы {{Mvar|X}}, разбивается на два множества: [[Пересечение множеств|пересечение]] {{Math|''S''''i'' ∩ ''X''}} и [[Разность множеств|разность]] {{Math|''S''''i'' \ ''X''}}

Этот алгоритм может быть эффективно реализован с помощью [[Структура данных|структур данных,]] представляющих следующую информацию:<ref>{{Citation|first1=Antti|volume=1|url=http://drops.dagstuhl.de/opus/volltexte/2008/1328|location=Dagstuhl, Germany|publisher=Schloss Dagstuhl: Leibniz-Zentrum fuer Informatik|editor2-last=Weil|editor2-first=Pascal|editor1-link=Susanne Albers|editor1-last=Albers|editor1-first=Susanne|year=2008|last1=Valmari|isbn=978-3-939897-06-4|series=Leibniz International Proceedings in Informatics (LIPIcs)|pages=645–656|title=25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008)|journal=|chapter=Efficient minimization of DFAs with partial transition functions|last2=Lehtinen|first2=Petri|doi=10.4230/LIPIcs.STACS.2008.1328}} {{Wayback|url=http://drops.dagstuhl.de/opus/volltexte/2008/1328 |date=20210718160752 }}</ref><ref>{{Citation|last1=Knuutila|first1=Timo|doi=10.1016/S0304-3975(99)00150-4|title=Re-describing an algorithm by Hopcroft|journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]]|volume=250|year=2001|pages=333–363}}</ref>

* Упорядоченная последовательность множеств {{Math|''S''''i''}} в семействе в такой форме, как [[Связный список#Двусвязный список (двунаправленный связный список)|двусвязный список]], который позволяет вставлять новые наборы в середину последовательности.
* Соответствующая каждому множеству {{Math|''S''''i''}} [[Коллекция (программирование)|коллекция]] его элементов, организованная как [[Связный список#Двусвязный список (двунаправленный связный список)|двусвязный список]] или [[Массив (тип данных)|массив,]] чтобы обеспечить возможность быстрого удаления отдельных элементов из коллекции. Альтернативно этот компонент структуры данных может быть представлен путем хранения всех элементов всех множеств в одном массиве, отсортированном по идентификатору множества каждого элемента, или путем представления коллекции элементов в любом множестве {{Math|''S''''i''}} по его начальной и конечной позициям в этом массиве.
* С каждым элементом связан набор, к которому он принадлежит.

Чтобы выполнить операцию уточнения, алгоритм перебирает элементы данного множества {{Mvar|X}}. Для каждого такого элемента {{Mvar|x}} он находит множество {{Math|''S''''i''}} которое содержит {{Mvar|x}}, и проверяет, произведено ли пересечение {{Math|''S''''i'' ∩ ''X''}}. Если нет, он создает второе множество и добавляет {{Math|''S''''i''}} в список {{Mvar|L}} множеств, разделенных операцией. Затем, независимо от того, было ли сформировано новое множество, алгоритм удаляет {{Mvar|x}} из {{Math|''S''''i''}} и добавляет его к {{Math|''S''''i'' ∩ ''X''}} В представлении, в котором все элементы хранятся в одном массиве, перемещение {{Mvar|x}} из одного множества в другое может выполняться путем обмена {{Mvar|x}} местами c последним элементом {{Math|''S''''i''}} а затем уменьшения концевого индекса {{Math|''S''''i''}} и начального индекса нового множества. Наконец, после того, как все элементы {{Mvar|X}} были обработаны таким образом, алгоритм проходит через {{Mvar|L}}, разделяя каждое текущее множество {{Math|''S''''i''}} на два, рассматривая оба этих множества как сформированные в результате операции уточнения.

Оценка времени для выполнения одной операции уточнения таким образом составляет {{Math|''O''({{pipe}}''X''{{pipe}})}}, независимо от количества элементов в семействе множеств, а также независимо от общего количества множеств в структуре данных. Поэтому время исполнения последовательности уточнений пропорционально общему размеру множеств, заданных алгоритму на каждом этапе уточнения.

== Применение ==
Одно из первых применений уточнение разбиения нашло в алгоритме Хопкрофта для [[Минимизация ДКА|минимизации ДКА]]<ref name=":0" />. В этой задаче на входе задается [[детерминированный конечный автомат]], и он должен найти эквивалентный автомат с как можно меньшим количеством состояний. Алгоритм Хопкрофта поддерживает разделение состояний входного автомата на подмножества с тем свойством, что любые два состояния в разных подмножествах должны отображаться в разные состояния выходного автомата. Изначально существует два подмножества, одно из которых содержит все принимающие состояния автомата, а другое — остальные. На каждом шаге выбираются одно подмножество {{Math|''Si''}} и один из входных символов {{Mvar|x}} автомата, и подмножества состояний уточняются до состояний, для которых переход, помеченный {{Mvar|x}}, приведет в {{Math|''Si''}}, и состояний, для которых {{Mvar|x}} приведет в другое место. Когда выбранное множество {{Math|''Si''}} разделяется уточнением, только одно из двух результирующих множеств (меньшее из двух) нужно рассмотреть снова; таким образом, каждое состояние участвует в множествах {{Mvar|X}} в течение {{Math|''O''(''s'' log ''n'')}} шагов уточнения, а общая оценка времени алгоритма составляет {{Math|''O''(''ns'' log ''n'')}}, где {{Mvar|n}} — количество начальных состояний, а {{Mvar|s}} — размер алфавита.<ref name=":0">{{Citation|last=Hopcroft|first=John|author-link=John Hopcroft|contribution=An {{math|''n'' log ''n''}} algorithm for minimizing states in a finite automaton|location=New York|pages=189–196|publisher=Academic Press|title=Theory of machines and computations (Proc. Internat. Sympos., Technion, Haifa, 1971)|year=1971}}.</ref>

Уточнение разделения было применено Sethi<ref>{{Статья|ссылка=http://epubs.siam.org/doi/10.1137/0205005|автор=Ravi Sethi|заглавие=Scheduling Graphs on Two Processors|год=1976-03|язык=en|издание=SIAM Journal on Computing|том=5|выпуск=1|страницы=73–82|issn=0097-5397, 1095-7111|doi=10.1137/0205005|archivedate=2021-11-04|archiveurl=https://web.archive.org/web/20211104003751/https://epubs.siam.org/doi/10.1137/0205005}}</ref> в эффективной реализации [[Алгоритм Коффмана – Грэма|алгоритма Коффмана — Грэма]] для параллельного планирования. Сетхи показал, что его можно использовать для построения [[Лексикографический порядок|лексикографически упорядоченной]] [[Топологическая сортировка|топологической сортировки]] заданного [[Ориентированный ациклический граф|ориентированного ациклического графа]] за линейное время; такое лексикографическое топологическое упорядочение является одним из ключевых шагов алгоритма Коффмана — Грэма. В этом приложении элементы непересекающихся множеств являются вершинами входного графа, а множества {{Mvar|X}} используемые для уточнения разбиения, являются множествами соседей вершин. Поскольку общее количество соседей всех вершин — это просто количество ребер в графе, алгоритм требует времени, линейного по количеству ребер.

Уточнение разбиения также является ключевым этапом в [[Лексикографический поиск в ширину|лексикографическом поиске]] в ширину, алгоритме поиска по графу с приложениями для распознавания [[Хордальный граф|хордовых графов]] и некоторых других важных классов графов. В этих случаях элементы непересекающихся множеств являются вершинами, а множество {{Mvar|X}} представляет собой [[Окрестность (теория графов)|множества точек окрестности]], поэтому алгоритм занимает линейное время.<ref>{{Citation|first1=D. J.|last1=Rose|first2=R. E.|last2=Tarjan|author2-link=Robert Tarjan|first3=G. S.|last3=Lueker|year=1976|title=Algorithmic aspects of vertex elimination on graphs|journal=[[SIAM Journal on Computing]]|volume=5|pages=266–283|issue=2|doi=10.1137/0205021}}.</ref><ref>{{Citation|first1=Derek G.|last1=Corneil|title=Graph-Theoretic Methods in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers|volume=3353|year=2004|pages=1–19|doi=10.1007/978-3-540-30559-0_1}}.</ref>

== См. также ==
* [[Сигма-алгебра|Уточнение (сигма-алгебра)]]

== Примечания ==
{{примечания}}

== Литература ==

[[Категория:Структуры данных]]