„External Memory Minimaler Spannbaum“ – Versionsunterschied
| [ungesichtete Version] | [ungesichtete Version] |
→Semiexterne Berechnung: Quellen |
|||
| Zeile 5: | Zeile 5: | ||
== Semiexterne Berechnung == |
== Semiexterne Berechnung == |
||
[[Datei:Edge_Contraction_Example.png|alternativtext=|mini|Beispiel einer Kantenkontraktion. Die Kante <math>\{1,2\}</math>wurde kontrahiert. Die neue Kante <math>\{1,3\}</math>war vorher <math>\{2,3\}</math>. ]] |
[[Datei:Edge_Contraction_Example.png|alternativtext=|mini|Beispiel einer Kantenkontraktion. Die Kante <math>\{1,2\}</math>wurde kontrahiert. Die neue Kante <math>\{1,3\}</math>war vorher <math>\{2,3\}</math>. ]] |
||
Eine Einschränkung zur Definition aus der Einleitung, bilden '''semiexterne''' Algorithmen zur Berechnung minimaler Spannbäume. Jene Algorithmen verarbeiten Graphen <math>G = (V,E)</math>, von denen nur die Knoten in den Hauptspeicher passen. Formal ist das durch die Beziehung |
Eine Einschränkung zur Definition aus der Einleitung, bilden '''semiexterne''' Algorithmen zur Berechnung minimaler Spannbäume. Jene Algorithmen verarbeiten Graphen <math>G = (V,E)</math>, von denen nur die Knoten in den Hauptspeicher passen. Formal ist das durch die Beziehung<ref>{{Literatur |Titel=Algorithms for Memory Hierarchies |Sammelwerk=Lecture Notes in Computer Science |Datum=2003 |ISSN=0302-9743 |DOI=10.1007/3-540-36574-5 |Online=https://link.springer.com/book/10.1007/3-540-36574-5 |Abruf=2019-07-18}}</ref> |
||
<math>M = c \cdot |V| < |E| </math><br />gegeben, wobei <math>c</math>eine beliebige, aber feste Konstante ist. |
<math>M = c \cdot |V| < |E| </math><br />gegeben, wobei <math>c</math>eine beliebige, aber feste Konstante ist. |
||
Der [[Algorithmus von Kruskal]] lässt sich leicht als semiexterne Variante umsetzen. Dazu muss man die Kanten zunächst nach aufsteigendem Gewicht extern sortieren, was sich mithilfe von <math>sort(E) := \Theta(\frac{E}{B} \cdot \log_{\frac{M}{B}}(\frac{E}{B}))</math>(die ''Sortier''schranke) I/Os realisieren lässt. Die [[Union-Find-Struktur]] lässt sich vollständig im Hauptspeicher verwalten, wodurch sich insgesamt <math>O(sort(E))</math>I/Os ergeben. |
Der [[Algorithmus von Kruskal]] lässt sich leicht als semiexterne Variante<ref>{{Literatur |Autor=Abello, Buchsbaum, Westbrook |Titel=A Functional Approach to External Graph Algorithms |Sammelwerk=Algorithmica |Band=32 |Nummer=3 |Datum=2002-03-01 |ISSN=1432-0541 |DOI=10.1007/s00453-001-0088-5 |Seiten=437–458 |Online=https://doi.org/10.1007/s00453-001-0088-5 |Abruf=2019-07-18}}</ref> umsetzen. Dazu muss man die Kanten zunächst nach aufsteigendem Gewicht extern sortieren, was sich mithilfe von <math>sort(E) := \Theta(\frac{E}{B} \cdot \log_{\frac{M}{B}}(\frac{E}{B}))</math>(die ''Sortier''schranke) I/Os realisieren lässt. Die [[Union-Find-Struktur]] lässt sich vollständig im Hauptspeicher verwalten, wodurch sich insgesamt <math>O(sort(E))</math> I/Os ergeben. |
||
Version vom 18. Juli 2019, 11:08 Uhr
Ein externer minimaler Spannbaum bezeichnet in der Informatik einen minimalen Spannbaum, der für einen in den Sekundärspeicher ausgelagerten Graphen berechnet wurde. Letzteres ist für Graphen nötig, deren Anzahl Knoten und Kanten zu groß ist, als das sie gleichzeitig vollständig in den Hauptspeicher passen.
Als Berechnungsmodell zieht man das External Memory Modell heran. Es besteht aus Haupt-und Sekundärspeicher, wobei ersterer eine Kapazität von hat und Datenblöcke der Größe zwischen ersterem und letzterem hin- und hergeschoben werden können. Das Verschieben eines Blocks von einem Speicher zum anderen, bezeichnet man als I/O (= Input/Output).
Semiexterne Berechnung
Eine Einschränkung zur Definition aus der Einleitung, bilden semiexterne Algorithmen zur Berechnung minimaler Spannbäume. Jene Algorithmen verarbeiten Graphen , von denen nur die Knoten in den Hauptspeicher passen. Formal ist das durch die Beziehung[1]
gegeben, wobei eine beliebige, aber feste Konstante ist.
Der Algorithmus von Kruskal lässt sich leicht als semiexterne Variante[2] umsetzen. Dazu muss man die Kanten zunächst nach aufsteigendem Gewicht extern sortieren, was sich mithilfe von (die Sortierschranke) I/Os realisieren lässt. Die Union-Find-Struktur lässt sich vollständig im Hauptspeicher verwalten, wodurch sich insgesamt I/Os ergeben.
- ↑ Algorithms for Memory Hierarchies. In: Lecture Notes in Computer Science. 2003, ISSN 0302-9743, doi:10.1007/3-540-36574-5 (springer.com [abgerufen am 18. Juli 2019]).
- ↑ Abello, Buchsbaum, Westbrook: A Functional Approach to External Graph Algorithms. In: Algorithmica. Band 32, Nr. 3, 1. März 2002, ISSN 1432-0541, S. 437–458, doi:10.1007/s00453-001-0088-5 (doi.org [abgerufen am 18. Juli 2019]).