titel | date | autor |
---|---|---|
Algorithmen und Datenstrukturen |
Sommersemester 2020 |
Robert Jeutter |
- Wir werden Datentypen spezifizieren und Implementierungen betrachten. Ihnen sollten Stacks, Queues, Arrays und Lineare Listen bekannt sein. Wir benutzen diese als einfache Beispiele und um Techniken einzüben. Wörterbuch ist ein grundlegender Datentyp mit sehr vielen unterschiedlichen Implementierungsmöglichkeiten, insbesondere auf der Basis von Suchbäumen (verschiedene Varianten) und von Hashtabellen. Damit werden wir uns ausgiebig beschäftigen.
- Binäre Heaps sind eine Implementierung des Datentyps "Prioritätswarteschlange". (Man benutzt sie auch bei Heapsort, einem Sortieralgorithmus.)
- Wir werden eine Reihe von Algorithmen für Graphen sehen. Basis hierfür sind geeignete Datenstrukturen für die rechnerinterne Darstellung von Graphen. Die "Union-Find-Datenstruktur" ist ein Beispiel für einen Hilfsdatentyp für Graphalgorithmen.
- Ein fundamentales Thema der Vorlesung ist, dass man für (rechenzeit-)effziente Algorithmen clevere Datenstrukturen braucht und für effziente Datenstrukturen auch manchmal schlaue Algorithmen: Ein Wechselspiel!
- Mergesort und Quicksort sind schon bekannt. Hier werden Details der exakten Analyse nachgetragen.
- Bei Heapsort ist der Korrektheitsbeweis interessant, und die Anwendungen der Datenstruktur "Prioritätswarteschlangen".
- Breitensuche und Tiefensuche sind Methoden zur Exploration von Graphen, sehr großen Graphen, weit jenseits dessen, was man sich anschaulich machen kann. Denken Sie an zig Millionen von Knoten!
- Divide-and-Conquer: ein Algorithmenparadigma, das heißt, eine Entwurfsstrategie. Wir werden mehrere Entwurfsstrategien sehen, mit typischen klassischen Algorithmen, aber auch dem Potenzial, dass man selber Algorithmen nach dieser Methode entwirft.
- Greedy: Ein weiteres Algorithmenparadigma. Man konstruiert eine Lösung Schritt für Schritt, macht in jedem Schritt kurzsichtig "optimale" Entscheidungen, ohne an die Zukunft zu denken (daher "greedy/gierig"), und durch eine eingebaute Magie ergibt sich dann doch eine optimale Lösung. Manchmal, aber manchmal auch nicht. In die Kategorie greedy gehören extrem wichtige Graphalgorithmen, wie kürzeste Wege von einem Startknoten aus oder billigste Teilnetzwerke, die "alles verbinden" ...
- Dynamische Programmierung (DP) (Das hat mit Programmierung im modernen Sinn nichts zu tun.) Hier berechnen wir kürzeste Wege zwischen allen Knotenpaaren in einem Graphen oder die geringste Anzahl von Buchstabenoperationen, um aus einem String (z. B. "FREIZEIT") einen anderen zu machen (z. B. "ARBEIT").
- Schwierige Probleme (Rucksackproblem oder Traveling Salesperson Problem, beide NPvollständig) können durch DP-Algorithmen etwas schneller als ganz naiv gelöst werden.
- Sortieren: Mergesort, Quicksort, Heapsort
- Graphdurchläufe: Breitensuche, einfache Tiefensuche
- Volle Tiefensuche, starke Zusammenhangskomponenten
- Divide-and-Conquer: Multiplikation von ganzen Zahlen und von Matrizen, Auswahlproblem, Schnelle Fourier-Transformation (eventuell)
- Greedy-Ansatz: Kürzeste Wege, Human-Codes, Minimale Spannbäume, fraktionales Rucksackproblem
- Dynamische Programmierung: Kürzeste Wege, Editierdistanz, 0-1-Rucksackproblem
Beispiel Sortieren mit Insertion Sort (Sortieren durch Einfügen)
for i from 2 to n do // Runden i = 2,...,n
x A[i] ; // entnehme A[i]
j i ;
while j > 1 and* x.key < A[j-1].key do
A[j] A[j-1] ; // Einträge größer als A[i] werden einzeln
j j-1 ; // um 1 Position nach rechts verschoben
A[j] x ; // Einfügen
return A[1..n] . // Ausgabe
- Die erste (unnummerierte) Zeile gibt den Namen und den Input an.
- (1)-(7): Eine for-Schleife, die für i = 2,...,n (in i) ausgeführt wird.
- (2), wenn i Wert i enthält:
- Datensatz ai (in A[i]) wird nach x kopiert, ist dort gesichert.
- Speicherstelle A[i] ist jetzt frei verfügbar.
- (3)-(6): Diese Schleife durchläuft j=i, i-1, i-2;... und testet immer, ob der Schlüssel von A[j-1] größer ist als der Schlüssel von x. Falls ja: Verschiebe A[j-1] an Position j im Array.
- "sequenzielles and" bedeutet, dass die zweite Bedingung nur ausgeführt wird, wenn die erste "wahr" ergibt.
- Wenn also j=1 ist, stoppt die Schleife, ohne dass (fehlerhaft) auf A[0] zugegriffen wird.
- Wenn Zeile (7) erreicht wird, gibt j die Stelle an, an die x gespeichert werden muss.
- Ende des Algorithmus, Rückgabe des Arrays als Ausgabe.
Die Frage nach der Korrektheit eines gegebenen bzw. soeben neu entworfenen Algorithmus wird uns durch die Vorlesung begleiten. Damit die Frage nach einem Beweis der Korrektheit überhaupt sinnvoll ist, müssen wir zunächst die zu lösende Aufgabe spezifizieren. Bemerkung: Aus einer vagen Problemstellung eine präzise Spezikation des zu lösenden Problems zu gewinnen ist ein in der Praxis extrem wichtiger Schritt, dessen Bedeutung oft unterschätzt wird. Hier: Spezikationstechniken für grundlegende Algorithmen (und Datenstrukturen, siehe Kap. 2). Ein Beispiel: Beim Sortieren gibt es das Konzept des "stabilen Sortierverfahrens": Objekte mit demselben Schlüssel ändern ihre relative Reihenfolge nicht. Wenn die Implementierung diese Eigenschaft nicht hat, der Kunde sie aber für seine Anwendung voraussetzt, weil Softwareingenieur/in und Kunde sich nicht präzise verständigt haben oder die Beschreibung des Programms nur sagt, dass es "sortiert", kann dies unangenehme Folgen haben. Auf präziser Spezikation zu bestehen und sie bereitzustellen liegt in der Verantwortung des Informatikers/der Informatikerin! Man nennt dies "Stand der Technik" ("state of the art"), der angewendet werden muss.
Die "Laufzeitanalyse" ist das zweite Grundthema in Richtung Algorithmen. Erklärung: Ein Berechnungsproblem P besteht aus
- einer Menge I von möglichen Eingaben ("Inputs","Instanzen") (I kann unendlich sein!)
- einer Menge O von möglichen Ausgaben
- einer Funktion
Ein Algorithmus A "löst P", wenn A genau die Eingaben aus I verarbeitet und zu Eingabe Ausgabe liefert. Spezialfall P heißt Entscheidungsproblem. Bei der Festlegung, was Eingabemengen und Ausgabemengen eines Algorithmus sind, gibt es dieselben Unschärfen wie bei den Algorithmen selbst. Die Darstellungsform für den Input bleibt offen. Selbst wenn man weiß, dass die Schlüsselmenge die Menge N ist, ist nicht klar, ob eine Zahl in Dezimal- oder in Binärdarstellung gegeben ist. Beispiel: Beim Sortierproblem hat man es mit Objekten zu tun, die ein Attribut "Schlüssel" haben. Es muss eine Funktion geben, ja sogar ein algorithmisches Verfahren, das aus dem Objekt a den Schlüssel key(a) ermittelt. Die Details dieser Funktion werden aber nicht festgelegt. Es ist nicht präzisiert, in welcher Weise die Funktion f beschrieben sein soll. Aus praktischen Gründen will man dies auch nicht. Mathematische Beschreibungen sind in der Regel akzeptabel. Wenn Ein-/Ausgabeformat ignoriert werden und man beliebige mathematische Funktionen f als Beschreibung akzeptiert, kann man eine Problemspezikation durchaus als ein mathematisches Tripel (I;O; f) schreiben. Ein Entscheidungsproblem entspricht der Menge .
Ein Algorithmus A ist eine durch einen endlichen Text gegebene Verarbeitungsvorschrift, die zu jeder gegebenen Eingabe x aus einer Menge I (der Menge der möglichen Eingaben) eindeutig eine Abfolge von auszuführenden Schritten ("Berechnung") angibt. Wenn diese Berechnung nach endlich vielen Schritten anhält, wird ein Ergebnis A(x) aus einer Menge O (der Menge der möglichen Ausgaben) ausgegeben. Beschreibungsformen: Umgangssprache, Pseudocode, Programm in Programmiersprache, Programm f�ur formales Maschinenmodell, Programm in Maschinensprache, Turingmaschinenprogramm, . . . Es handelt sich nicht um eine formale Definition. Viele Formalismen können benutzt werden, um das Algorithmenkonzept formal/mathematisch zu erfassen: Turingmaschinenprogramme, while-Programme, Programme für andere (mathematisch genaue) Maschinenmodelle,... Man beweist, dass viele unterschiedliche Formalismen zu exakt derselben Klasse von "berechenbaren Funktionen" führt. Erfahrungstatsache: Alle bekannten Algorithmenkonzepte liefern dieselbe Klasse von "berechenbaren Funktionen". Die Church-Turing-These sagt, dass unsere informale, intuitive Beschreibung genau dem entspricht, was man mit diesen mathematischen Definitionen erfasst.
Eine grundlegende Tatsache der Berechenbarkeitstheorie, nämlich die Unentscheidbarkeit des Halteproblems hat als unangenehme Konsequenz, dass Folgendes passiert: Wenn man der Denition des Algorithmenbegriffs die Aussage "A hält auf allen Inputs" hinzufügt, dann kann ein Compiler einen vorgelegten Programmtext P nicht mehr automatisch (d.h. mit einem Computerprogramm, d.h. mit einem Algorithmus) darauf �überprüfen, ob P einen Algorithmus darstellt oder nicht. Das würde bedeuten, dass der Compiler entweder eigentlich legale Algorithmen zurückweist oder "Nicht-Algorithmen" passieren lässt. Einen Algorithmenbegriff ohne Entscheidungsverfahren will man nicht haben. (Man möchte Programme aufgrund einer reinen Syntax�überprüfung in korrekt/fehlerhaft einteilen.) Dies ist der Grund, weshalb Algorithmen mit nicht-stoppenden Berechnungen in Kauf genommen werden.
- Endlicher Text
- Ein Algorithmus für eine große (oft: unendliche!) Menge I von Eingaben x (Beachte: Zeitliche Trennung der Formulierung des Algorithmus bzw. der Programmierung und der Anwendung auf eine Eingabe.)
- Eindeutig vorgeschriebene Abfolge von Schritten, wenn Eingabe x vorliegt (im Rahmen des benutzten Modells)
- Wenn Verarbeitung anhält: Ausgabe
ablesbar - Nicht verlangt: Terminierung auf allen
.
Algorithmen werden erfunden und in Software umgesetzt. Der Algorithmus, den Sie in Ihrer späteren Tätigkeit entwerfen und implementieren, wird (hoffentlich!) vieltausendfach verkauft und von Kunden eingesetzt, in Umgebungen und für Inputs, an die beim Algorithmenentwurf und bei der Implementierung niemand gedacht hat. Reales Beispiel: Bankensoftware, in den 1960er Jahren in COBOL geschrieben, wurde bis weit ins 21. Jh. eingesetzt, auf Rechnern, die es bei der Erstellung der Programme noch gar nicht gab. Diese Situation ist ein großer Reiz im Informatiker/innen dasein, aber auch eine Riesenverantwortung. Es muss genauestens spezifiziert sein, was genau ein Stück Software tut, und für welche Inputs es geeignet ist. Je nach Modell oder Detaillierungsgrad des Algorithmus kann "eindeutig vorgeschriebene Abfolge von Schritten" unterschiedliche Dinge bedeuten. Beispiel: Man kann die Addition von natürlichen Zahlen als Elementaroperation ansehen oder die Details der Addition von Dezimalzahlen (Schulmethode) als Teil des Algorithmus betrachten. Nicht selten werden Algorithmen in einer Form beschrieben, die viele Details offen lässt. (Beispielsweise könnte es in einem Algorithmus ein Hilfsprogramm geben, das eine Folge sortiert. Der Algorithmus gilt oft auch dann als vollständig, wenn die verwendete Sortiermethode gar nicht fixiert ist.) Noch ein Wort zu Eingabe/Ausgabe: Vor der Verarbeitung durch einen Computer müssen Daten in eine interne Darstellung transformiert werden. Die Ausgabe eines Programms muss wieder in "reale" Daten übersetzt werden.
- Online-Algorithmen: Die Eingabe wird nicht am Anfang der Berechnung, sondern nach und nach zur Verfügung gestellt, Ausgaben müssen nach Teileingabe erfolgen. Häufige Situation bei Datenstrukturen, Standard bei Betriebssystemen, Systemprogrammen, Anwendungsprogrammen mit Benutzerdialog usw.
- Randomisierung: Algorithmus führt Zufallsexperimente durch, keine Eindeutigkeit der Berechnung gegeben.
- Verteilte Algorithmen: Mehrere Rechner arbeiten zusammen, kommunizieren, zeitliche Abfolge nicht vorhersagbar
Zu einer Eingabe
- Online-Situation: Eingabe wird "in Raten" geliefert, Zwischenausgaben werden verlangt.
Parameter: Die Grundbereiche (Klassen), aus denen die zu sortierenden Objekte und die Schlüssel stammen:
-
: total geordnete Menge (endlich/unendlich, Elemente heißen "Schlüssel"). - Beispiele: Zahlenmengen
Mengen von Strings. - D: Menge (Elemente heißen "Datensätze").
- key :
gibt zu jedem Datensatz einen "Sortierschlüssel" an. -
(die Menge aller endlichen Folgen von Datensätzen) Es ist häufiger der Fall als nicht, dass die zu verwendenden Grundbereiche bei einem Berechnungsproblem (oder einer Datenstruktur) als Parameter angegeben werden, die für eine konkrete Verwendung oder auch für eine konkrete Implementierung noch festgelegt werden müssen. Bei der objektorientierten Programmierung entspricht dies der Verwendung von "generischen Typen" (Java-Terminologie) oder Templates (C++-Terminologie). Der Schlüssel könnte ein simples Attribut des Objekts x sein, oder mit einer Methode aus x berechnet werden. In Beispielen lassen wir oft die Datensätze (fast) ganz weg und konzentrieren uns auf die Schlüssel. Dies ist bei realen Anwendungen fast nie so. (Sehr selten will man eine Liste von puren Zahlen sortieren, sondern man will meistens komplexere Datensätze nach ihnen zugeordneten Nummern sortieren.) ist die Menge aller n-Tupel von Datensätzen. hat nur das Element (die leere Folge). hat als Elemente die Folgen für . Die Menge erhält man, indem man alle diese Mengen zusammenwirft. Bitte die Notation einprägen!
Die Ausgabe ist nicht die sortierte Folge, sondern die Permutation
Gilt für jede Eingabe
Korrektheitsbeweis für Insertionsort
Zunächst erledigen wir zwei (triviale) Randfälle: Wenn n = 0 ist, also das Array leer ist, oder wenn n = 1 ist, es also nur einen Eintrag gibt, dann tut der Algorithmus gar nichts, und die Ausgabe ist korrekt.
Sei nun
- I.A.: i = 1: "Nach Durchlauf für i = 1" ist vor Beginn. Anfangs ist das Teilarray
(nur ein Eintrag) sortiert, also gilt (IB1). - I.V.: Wir nehmen an:
und gilt, d.h. ist sortiert, enthält dieselben Objekte wie am Anfang, und Schleifendurchlauf i beginnt. - I.-Schritt: Betrachte Schleifendurchlauf i (Zeilen 2-7).
-
ist das aktuelle Objekt; es wird in Variable x kopiert. - Position
kann man sich jetzt als leer vorstellen. - Sei
die größte Zahl in , so dass für . - (Wenn es gar kein
mit gibt, ist . - Wenn für alle
die Ungleichung erfüllt ist, ist .)
-
- Weil nach I.V.
sortiert ist, gilt: für . Die innere Schleife 4-7 mit der Initialisierung in Zeile 3 testet, durch direkten Vergleich in Zeile 4, die Zahlen nacheinander darauf, ob ist. Entweder wird dabei erreicht, dann ist , oder man stellt für ein fest, dass gilt. Dann ist offenbar ebenfalls . - Schon während der Suche nach m werden (in Zeile 5) die Einträge
, in dieser Reihenfolge, um eine Position nach rechts verschoben, ohne die Sortierung dieser Elemente zu ändern. Nun stehen an ihrer ursprünglichen Position, (vorher) stehen jetzt in . In Zeile 7 wird x (aus x) an die Stelle geschrieben. Nach den Feststellungen in den Boxen und aus der I.V. ergibt sich, dass nun aufsteigend sortiert ist. Also gilt . Nach Durchlaufen der äußeren Schleife Schleife für gilt die Aussage , also ist nach Abschluss des Ablaufs das Array sortiert.
Methoden für Korrektheitsbeweise
- Vollständige Induktion: Damit wird die Korrektheit von Schleifen bewiesen. Meist ist dabei die Formulierung einer geeigneten Induktionsbehauptung zentral, die dann "Schleifeninvariante" genannt wird.
- Verallgemeinerte Induktion (d.h. man schließt von (
) für alle auf ( ). Damit werden rekursive Prozeduren behandelt. (Siehe: Divide-and-Conquer.) - Diskrete Mathematik: Ad-hoc-Beweise. (Beispiele bei Graphalgorithmen)
Einen Algorithmus analysieren heißt, Kosten, Aufwand, "Rechenzeit" (synonym!) zu bestimmen oder zumindest abzuschätzen, die sich einstellt, wenn man eine Implementierung des Algorithmus A auf Eingabe x ablaufen lässt. Natürlich geht es schneller, kurze Arrays zu sortieren als lange. Daher ist ein zentraler Parameter einer solchen Analyse die Größe der Eingabe
Kosten für Elementaroperationen in Programm: Addition, Vergleich, Test, Sprung, Zuweisung, Auswertung eines Attributs, Zeiger-/Indexauswertung
Jede Elementaroperation
In dieser Sichtweise ist es egal, ob für einen Vergleich
Wir schreiben
Beispiel Insertionsort
Wir benutzen
Definition
Welchen Wert
Sei A Algorithmus für Inputs aus I (
Wir denieren best-case-Kosten oder Kosten im besten Fall:
Annahme: Jede der
Erklärung: Wir betrachten der Einfachheit halber Inputs die aus den Zahlen
Average-case-Kosten oder durchschnittliche Kosten: Gegeben sei, für jedes
Selbst für feste Implementierung eines Algorithmus A auf fester Maschien und feste Eingabegröße
Datentypen werden speziziert, sie geben (mathematisch exakt) ein Wunschverhalten einer Struktur an. Datenstrukturen sind Implementierungen von Datentypen.
(Aliasse: Keller, Stapel, LastInFirstOut-Speicher, Pushdown-Speicher) Informale Beschreibung der Operationen; Vorstellung ist ein Stapel (Alltagsbegriff). Einträge: Elemente einer Menge D (Parameter).
- empty(): erzeuge leeren Stapel ("Konstruktor").
- push(s; x): lege Element
oben auf den Stapel s. - pop(s): entferne oberstes Element von Stapel s (falls s leer: Fehler).
- top(s): gib oberstes Element des Stapels s aus (falls s leer: Fehler).
- isempty(s): Ausgabe "true" falls Stapel s leer, "false" sonst. Eine Beschreibung in Umgangssprache und durch ein Beispiel genügt aber nicht. Um die Frage nach der Korrektheit einer Implementierung überhaupt sinnvoll stellen zu können, benötigen wir eine präzise Beschreibung des Verhaltens, also eine Spezikation.
Namen von Sorten, Namen von Operationen mit Angabe der Namen der Argumentsorten und Resultatsorte für jede Operation.
- Signatur (Rein syntaktische Vorschriften! Verhalten (noch) ungeklärt)
- Sorten:
- Elements
- Stacks
- Boolean
- Operationen
- empty:
Stacks - push: Stacks X Elements
Stacks - pop: Stacks
Stacks - top: Stacks
Elements - isempty: Stacks
Boolean
- empty:
Um die Spezikation mit Inhalt zu füllen, muss erklärt werden, was die Namen "bedeuten" sollen, d.h. die Semantik muss beschrieben werden. Das mathematische Modell beschreibt ein eindeutig bestimmtes Verhalten der Operationen. Dieses Verhalten sollen korrekte Implementierungen dann nachbauen.
- Mathematisches Modell (Sortennamen werden durch Mengen unterlegt)
- Sorten:
- Elements: Menge D, nichtleer (Parameter)
- Stacks:
mit - Boolean: {true,false} bzw {1,0}
- Operationen:
- $pop((a_1,...,a_n)):= \begin{cases} (a_2,...,a_n), falls n\geq 1 \ undefiniert, falls (n = 0) \end{cases}$
- $top((a_1,...,a_n)):= \begin{cases} a_1, falls n\geq 1 \ undefiniert, falls (n = 0) \end{cases}$
- $isemtpy((a_1,...,a_n)):= \begin{cases} false, falls n\geq 1 \ true, falls (n = 0) \end{cases}$
Der Stack wird als Folge
- Signatur (wie oben)
- Axiome
s: Stacks, x: Elements - pop(push(s,x)) = s
- top(push(s,x)) = x
- isemtpy(empty()) = true
- isemtpy(push(s,x)) = false
Vorteil: Zugänglich für automatisches Beweisen von Eigenschaften des Datentyps. Nachteil: Finden eines geeigneten Axiomensystems für eine geplante Semantik evtl. nicht offensichtlich.
Die Methode, ADTs mit Axiomen zu spezifizieren, ist sehr effizient. Sie erleichtert Korrektheitsbeweise für Implementierungen, da man nur nachprüfen muss, dass die Implementierungen der Operationen, also die Methoden, die Axiome erfüllen. Das ist oft einfacher als mit unserem mathematischen Modell. Auch automatische Korrektheitsbeweise für Implementierungen werden so ermöglicht. Bei Verwendung der Axiomen-Methode ist die zentrale Schwierigkeit, einen geeigneten vollständigen Satz von Axiomen zu finden.
Nun wollen wir ihn durch Algorithmen und am Ende durch ein Programm (z. B. in Java) realisieren. Diese algorithmische Realisierung erfolgt durch eine "Datenstruktur". Die Signatur gibt dabei den Plan vor. Aus Sorten werden Klassen. Die Elemente einer Sorte werden also durch Objekte der entsprechenden Klasse realisiert. Aus Operationen werden Methoden einer passenden Klasse. Die Operationen der Signatur sind alle öffentlich ("public"), also durch den Benutzer der Datenstruktur aufrufbar.
Die Klasse "Boolean" mit Konstanten true und false ist in Programmiersprachen eingebaut. Wir bauen eine Klasse für "Stacks". Diese muss (öffentliche) Methoden für empty (den Konstruktor, der ein neues Stackobjekt liefert), für push, top und pop anbieten.
Üblich: Ein Stack-Objekt wird der Methode nicht als Argument übergeben, die Methode wird für dieses Objekt aufgerufen. Daher fehlt das Stack-Objekt in der Parameterliste.
Grundsätzlich, in beliebiger objektorientierter Sprache: als Klasse mit Methoden.
Prinzip: Kapselung (Information Hiding)
Ein Stack wird durch eine einfach verkettete Liste s dargestellt. Die Einträge stehen in der Liste in Reihenfolge
- s.empty: Erzeugt neue leere Liste
- s.push(x): Setzte neuen Listenknoten mit Eintrag x an den Anfang der Liste
- s.pop: Entferne ersten Listenknoten (falls vorhanden). Für eine leere Liste muss eine Fehlermeldung aufgerufen werden
- s.top: Gib Inhalt des ersten Listenknotens aus (falls vorhanden, sonst Fehler)
- s.isempty: Falls Liste leer
Ausgabe "true", sonst "false"; Ausgabetyp Boolean
Beobachtung 1: Wenn der Benutzer nie den Fehler macht, pop oder top für den leeren Stack (die leere Liste) aufzurufen, dann ist der einzige Fehler, der bei der Benutzung dieser Implementierung auftreten kann, ein Speicher�überlauf bei der Operation s.push(x), weil für das neue Listenelement im für das Programm verfügbaren Speicher kein Platz mehr ist.
Beobachtung 2: Jede der Methoden hat Rechenzeit
Korrektheit der Listenimplementierung
Eine beliebige Menge D sei gegeben. Wir betrachten eine Folge von Stackoperationen
Beispiel:
Eine Implementierung des Datentyps "Stack" heißt dann korrekt, wenn sie auf jede gegebene Operationenfolge als Eingabe genau dieselbe Ausgabefolge erzeugt wie das mathematische Modell. Ausnahme: Die Datenstruktur kann nicht für einen Speicherüberlauf verantwortlich gemacht werden.
Beweis: Man zeigt per Indukion über
Das Stackobjekt heißt s; es hat als Attribute einen Zeiger/eine Referenz auf ein Array
- s.empty: wird durch einen Konstruktor realisiert. m als Parameter oder fix gewählt. Erzeuge neues Objekt s mit
elementen und p:int; - s.push(x):
if p=A.length then "Fehler"
else p
p+1; x - s.pop:
if p=0 then "Fehler"
else p
p-1 - s.top:
if p=0 then "Fehler"
else return
- s.isempty if p=0 then return "true" else return "false"
Der wichtigste Punkt ist, dass das obere Ende des Stacks an der Position n (in p) in A sitzt, so dass die Operationen konstante Zeit benötigen. Es gibt eine neue Fehlermöglichkeit in der Implementierung: Das Array
Korrektheit der Arrayimplementierung
Die Arrayimplementierung ist korrekt, d.h. sie erzeugt auf Eingabe
Beweis
- p enthält die Länge
der Folge und -
und - die Implementierung gibt in Schritt i genau
aus. D.h. stellt genau in um gekehrter Reihenfolge dar.
Zeitaufwand von Arrayimplementierung
Bei der Initialisierung empty() (Aufruf des Konstruktors) muss man aber auf Folgendes achten: Wenn man m, die Arraygröße, vom Benutzer als Parameter angeben lässt (was sehr sinnvoll ist!), dann darf das Array
Verdopplungsstrategie: In push(x): Bei Überlaufen des Arrays
- Ein neues, doppelt so großes Array
allozieren. - m Einträge aus
nach kopieren. - x an Stelle
schreiben, Pegel auf setzen. -
in A umbenennen/Referenz umsetzen. (Altes Array freigeben, falls in der Programmiersprache sinnvoll. (C++ ja, Java nein.)) Kosten: , wo m = n = aktuelle Größe des Stacks.
Analyse der Gesamtkosten bei Verdoppelungsstrategie
Betrachte eine beliebige Operationenfolge$Op_0 = empty, Op_1,..., Op_N$. Arraygröße am Anfang:
von $m_02^{l-1}$ auf $m_02^l$. Bei der l-ten Verdopplung entstehen Kosten
.
k := Anzahl der push-Operationen in
Wenn ein Stack mit Arrays und der Verdoppelungsstrategie implementiert wird, gilt:
- Die Gesamtkosten für N Operationen betragen
. - Der gesamte Platzbedarf ist
, wenn k die maximale je erreichte Stackhöhe ist.
Arrayimplementierung | Listenimplementierung |
---|---|
|
|
Sequentieller, indexbasierter Zugriff im Speicher (cachefreundlich) | (jedoch: relativ hohe Allokationskosten bei push-Operationen) |
Höchstens 50% des allozierten Speicherplatzes bleibt ungenutzt | Zusätzlicher Platz für Zeiger benötigt. |
Experimente zeigen, dass die Arrayimplementierung spürbar kleinere Rechenzeiten aufweist.
Generelle Erkenntnis: Datentypen lassen sich ebenso exakt spezizieren wie Berechnungsprobleme.
Stacks + "wahlfreier Zugriff"
Neuer Grunddatentyp: Nat - durch
Operationen, informal beschrieben:
- empty(): liefert leeres Array, Länge 0
- read(A; i): liefert Eintrag A[i] an Position i, falls
. - write(A; i; x): ersetzt Eintrag A[i] an Position i durch x, falls
. - length(A): liefert aktuelle Länge n.
- addLast(A; x): verlängert Array um 1 Position, schreibt x an letzte Stelle (= push).
- removeLast(A): verkürzt Array um eine Position (= pop).
Wieso gibt es kein "isempty"? Überprüfung durch "length" zeigt ein leeres Array falls keine Einträge vorhanden
- Signatur
- Sorten:
- Elements
- Arrays
- Nat
- Operationen
- empty: -> Arrays
- addLast: Array x Elements -> Arrays
- removeLast: Arrays -> Arrays
- read: Arrays x Nat -> Elements
- write: Arrays x Nat x Elements -> Arrays
- length: Arrays -> Nat
- Mathematisches Modell
- Sorten:
- Elements: (nichtleere) Menge D (Parameter)
- Arrays: Seq(D)
- Nat:
- Operationen:
- emtpy():=()
- addLast$((a_1,...,a_n),x):= (a_1,...,a_n,x)$
- removeLast$((a_1,...,a_n)):= \begin{cases} (a_1,...,a_{n-1}), falls (n\geq 1) \ undefiniert, falls (n=0) \end{cases}$
- read$((a_1,...,a_n),i):= \begin{cases} a_i, falls (1\leq i \leq n) \ undefiniert, sonst \end{cases}$
- write$((a_1,...,a_n),i,x):= \begin{cases} (a_1,...,a_{i-1},x,a_{i+1},...,a_n), falls (1\leq i \leq n) \ undefiniert, sonst \end{cases}$
- length$((a_1,...,a_n)):= n$
Implementierung: Wir erweitern die Arrayimplementierung von Stacks in der offensichtlichen Weise, gleich mit Verdoppelungsstrategie.
Kosten:
- empty, read, write, length: O(1).
- addLast: k addLast-Operationen kosten Zeit O(k).
- removeLast: Einfache Version (Pegel dekrementieren): O(1).
(First-in-First-Out Listen) Stacks und Queues verhalten sich sehr unterschiedlich
- "enqueue": Man fügt ein Element ein, indem man hinten an die Kette anhängt.
- "dequeue": Man entnimmt ein Element am vorderen Ende der Kette.
- "first": Man kann den vordersten Eintrag auch lesen.
Die Signatur ist identisch zur Signatur von Stacks (bis auf Umbenennungen). Rein syntaktische Vorschriften!
- Signaur
- Sorten:
- Elements
- Queues
- Boolean
- Operationen:
- empty: -> Queues
- enqueue: Queues x Elements -> Queues
- dequeue: Queues -> Queues
- first: Queues -> Elements
- isemtpy: Queues -> Boolean
- Mathematisches Modell
- Sorten:
- Elements: (ncihtleere) Menge D (Parameter)
- Queues: Seq(D)
- Boolean: {true, false}
- Operationen:
- empty():=()
- enqueue$((a_1,...,a_n),x):= (a_1,...,a_n,x)$
- dequeue$((a_1,...,a_n)):= \begin{cases} (a_2,...,a_n), falls (n\geq 1)\ undefiniert, falls (n=0) \end{cases}$
- first$((a_1,...,a_n)):= \begin{cases} a_1, falls (n\geq 1)\ undefiniert, falls (n=0) \end{cases}$
- isemtpy$((a_1,...,a_n)):= \begin{cases} false, falls (n\geq 1)\ true, falls (n=0) \end{cases}$
Die leere Folge () stellt die leere Warteschlange dar. Das mathematische Modell ist fast identisch zu dem für Stacks. Nur fügt enqueue(x) das Element x hinten an die Folge an, während push(x) das Element x vorne anfügt.
Listenimplementierung Implementierung mittels einfach verketteter Listen mit Listenendezeiger/-referenz. Bei der Verwendung von Listen ist zu beachten, dass man mittels Zeigern/Referenzen Zugang zu beiden Enden der Liste benötigt: mit einem "head"-Zeiger hat man Zugriff auf den Anfang, mit einem "tail"-Zeiger Zugriff auf das Ende.
Arrayimplementierung
!TODO seite 40(394) #####################################################################################################################################
Ein Binärbaum T besteht aus einer endlichen Menge V von "inneren" Knoten, einer dazu disjunkten endlichen Menge L von "äußeren" Knoten sowie einer injektiven Funktion
D sei Menge von (möglichen) Knotenmarkierungen, Z sei Menge von (möglichen) Blattmarkierungen:
- Wenn
dann ist (z) ein (D,Z)-Binärbaum - Wenn
(D,Z)-Binärbaume sind und ist, dann ist auch ein (D,Z)-Binärbaum - nichts sonst ist (D,Z)-Binärbaum
- Signatur
- Sorten:
- Elements
- Bintrees
- Boolean
- Operationen
- empty: -> Bintrees
- buildTree: Elements x Bintrees x Bintrees -> Bintrees
- leftSubtree: Bintrees -> Bintrees
- rightSubtree: Bintrees -> Bintrees
- data: Bintrees -> Elements
- isemtpy: Bintrees -> Boolean
- mathematisches Modell
- Sorten:
- Elements: (nichtleere) Menge D
- Bintrees: {T | T ist (d,{-})-Binärbaum}
- Boolean: {true, false}
- Operationen:
- empty():= {}:= (-)
- $leftSubtree(T) := \begin{cases} T_1, falls\ T=(T_1,x,T_2) \ undefiniert, falls\ T=(-) \end{cases}$
- $rightSubtree(T) := \begin{cases} T_2, falls\ T=(T_1,x,T_2) \ undefiniert, falls\ T=(-) \end{cases}$
- $data(T) := \begin{cases} x, falls\ T=(T_1,x,T_2) \ undefiniert, falls\ T=(-) \end{cases}$
- $isempty(T) := \begin{cases} false, falls\ T=(T_1,x,T_2) \ true, falls\ T=(-) \end{cases}$
- Binärbaum T, engl: "binary tree"
- Wurzel, engl "root"
- (innerer) Knoten v, engl: "node"
- (äußerer) Knoten l = Blatt, engl: "leaf"
- Blatteintrag: z= data(l)
- Knoteneintrag:
-
: Unterbaum mit Wurzel v - Vater/Vorgänger, engl: "parent", von v: p(v)
- linkes Kind, engl: "left child", von v: von v: child(v, left)
- rechtes Kind, engl: "right child", von v: von v: child(v, right)
- Vorfahr (Vater von Vater von Vater . . . von u), engl: "ancestor"
- Nachfahr (Kind von Kind von . . . von v), engl: "descendant"
- Weg in T: Knotenfolge oder Kantenfolge, die von v zu einem Nachfahren u führt
- Länge eines Wegs
: Anzahl s der Kanten auf dem Weg - Tiefe/Level eines Knotens: Die Länge (das ist die Kantenzahl) des Wegs von der Wurzel zum Knoten heißt die Tiefe oder das Level
von Knoten v. Die Knoten mit Tiefe l bilden das Level l.
TIPL(T) = Anzahl der Knoten * Tiefe der Knoten
Mittlere innere Weglänge:
TEPL(T) = Anzahl der Blätter * Tiefe der Blätter
Mittlere äußere Weglänge:
TEPL(T) = TIPL(T) +2n
(D,Z)-Binärbäume kann man systematisch durchlaufen, die Knoten nacheinander besuchen und (anwendungsabhängige) Aktionen an den Knoten ausführen. Abstrakt gefasst: visit-Operation. Organisiere data-Teil der Knoten als Objekte einer Klasse; visit(T) löst Abarbeitung einer Methode von data(T) aus.
"Erst den linken Unterbaum, dann die Wurzel, dann den rechten Unterbaum"
Bsp: falls
- Inorder Durchlauf durch
- i-visit(x)
- Inorder Durchlauf durch
Man besucht abwechselnd externe und interne Knoten.
"Erst die Wurzel, dann den linken Unterbaum, dann den rechten Unterbaum"
Bsp: falls
- i-visit(x)
- Inorder Durchlauf durch
- Inorder Durchlauf durch
"Erst den linken Unterbaum, dann den rechten Unterbaum, zuletzt die Wurzel" Bsp: falls
- Inorder Durchlauf durch
- Inorder Durchlauf durch
- i-visit(x)
Ermöglicht Datentransport von der Wurzel nach unten in den Baum hinein und wieder zurück.
Bsp: falls
- preord-i-visit(x)
- Kombi Durchlauf durch
- inord-i-visit(x)
- Kombi Durchlauf durch
- postord-i-visit(x)
Die Baumdurchläufe können mittels rekursiver Prozeduren implementiert werden.
Beispiel: Inorder Durchlauf
- Angewendet auf einen Baum T mit n inneren Knoten
- Für jeden inneren und äußeren Knoten wird die Prozedur inorder() einmal aufgerufen, insgesamt
-mal - Kosten pro Aufrug
plus Kosten für i-visit/e-visit-Operation - Insgesamt:
wobei eine Schranke für die Kosten der visit-Operationen ist
Behauptung: Baumdurchläufe haben lineare Laufzeit.
Gegeben: Universum U (auch ohne Ordnung) und Wertebereich R. Hashverfahren (oder Schlüsseltransformationsverfahren) implementieren ein Wörterbuch (alias dynamische Abbildung, assoziatives Array)
Ziel: Zeit
Grundansatz: "x wird in h(x) umgewandelt/transformiert" (Ideal: Speichere Paar (x, f(x)) in Zelle T[h(x)] )
Eine Funktion
Uniformitätsannahme (UF): Werte
- U endlich ist und
- h das Universum in gleich große Teile zerlegt (
oder ) -
eine rein zufällige Menge der Größe n ist Pr(keine Kollision)=Pr(injektiv auf S)
"Geburtsparadoxon":
Wunsch: Linearer Platzverbrauch, also "Auslastungsfaktor"
engl.: chained hashing
Auch: "offenes Hashing", weil man Platz außerhalb von T benutzt. In
- empty(x)
- Erzeugt Array
mit m NULL-Zeigern/NULL-Referenzen und legt fest. - Kosten:
- Beachte: Man wählt h, ohne S zu kennen
- Erzeugt Array
- lookup(x)
- Berechne
suche Schlüssel x durch Durchlaufen der Liste bei ; falls Eintrag gefunden: ; sonst: - Kosten/Zeit: O(1+ Zahl der Schlüsselvergleiche "x=y?"); Erfolglose Suche exakt
; Erfolgreiche Suche höchstens
- Berechne
- insert(x,r)
- Berechne
suche Schlüssel x in Liste bei ; falls gefunden ersetze Daten bei x durch r - Kosten: wie bei lookup
- Berechne
- delete(x)
- Berechne
, suche Schlüssel x in Liste bei ; falls gefunden lösche Eintrag aus - Kosten: wie bei lookup
- Berechne
Ziel: analysiere erwartete Kosten für lookup, insert, delete. Hierfür genügt Analyse erwarteter Anzahl der Schlüsselvergleiche.
- Pr(A): Wahrscheinlichkeit für Ereignis A
- E(X): Erwartungswert der Zufallsvariablen X
- abgeschwächte "Uniformitätsannahme": Für je 2 Schlüssel
in U gilt:
Wenn nach
- Erzeuge neue Tabelle
der Größe . - Erzeuge neue Hashfunktion
. - Übertrage Einträge aus den alten Listen in neue Listen zu Tabelle
, gemäß neuer Hashfunktion. Dabei Einfügen am Listenanfang ohne Suchen. (Wissen: Alle Schlüssel sind verschieden!) Kosten: O(m) im schlechtesten Fall. - Benenne
in und in um.
Kriterien für Qualität:
- Zeit für Auswertung von
(Schnell!) entscheidend: Schlüsselformat - Wahrscheinlichkeit für Kollisionen (unter "realistischen Annahmen" über Schlüsselmenge S). (Klein, am besten
für c konstant.)
- Unflexibel: Nur eine feste Funktion für eine Tabellengröße.
- Bei strukturierten Schlüsselmengen (z. B. aus Strings übersetzte Schlüssel) deutlich erhöhtes Kollisionsrisiko.
- Kollisionen
nie auflösbar! - Selbst wenn n injektiv: Ineffziente Auswertung von
.
- Rechnung nur mit Zahlen
(wenn man nach jeder Multiplikation/Addition Rest modulo p bildet); - sehr effzient;
- theoretisch nachweisbares gutes Verhalten, wenn
aus zufällig gewählt werden.
Qualitätskriterien:
- Zeit für Auswertung von
(klein!) - geringe Wahrscheinlichkeit für Kollisionen ohne Annahmen über die Schlüsselmenge S (ähnlich der zufälligen Situation!)
- Effiientes Generieren einer neuen Hashfunktion (benötigt z.B. bei der Verdoppelungsstrategie)
- Platzbedarf für die Speicherung von h (Programmtext, Parameter) (gering gegenüber n!)
Universelles Hashing (Idee): Bei der Festlegung der Hashfunktion h wird (kontrolliert) Zufall eingesetzt ("Randomisierter Algorithmus"). (Bei Programmierung: "Pseudozufallszahlengenerator", in jeder Prog.-Sprache bereitgestellt.) Analyse beruht auf dadurch vom Algorithmus erzwungenen Zufallseigenschaften von h.
Wähle a aus
Mit multiplikativem Hashing (wobei
Tabellenhashing
Universum
- Nachteil: Array
benötigt Platz (Wörter). Sinnvoll nur für große Hashtabellen. - Platzsparend, etwas langsamer:
("Tetraden" bzw. Hexadezimalziffern.)
- Platzsparend, etwas langsamer:
- Vorteile von Tabellenhashing:
- Extrem schnelle Auswertung
- Dasselbe A kann für
benutzt werden. Ideal für die Kombination mit der Verdoppelungsstrategie: Verdopple Tabellengröße = erhöhe l um 1; Einträge in A bleiben unverändert. - Beweisbar gutes Verhalten, wenn Einträge von A zufällig.
Sei c konstant. Wenn
- höchstens
bei der erfolglosen Suche und - höchstens
bei der erfolgreichen Suche.
oder "offene Adressierung": Kollisionsbehandlungs-Methode. Idee: Für jeden Schlüssel
gibt es eine Sondierungsfolge in [m]. Beim Einfügen von x und Suchen nach x werden die Zellen von T in dieser Reihenfolge untersucht, bis eine leere Zelle oder der Eintrag x gefunden wird.
Ergebnisse für lineares Sondieren: Eine einzelne erfolglose Suche wird z.B. bei zu 90% gefüllter Tabelle durchaus teuer. Bei vielen erfolglosen Suchen in einer nicht veränderlichen Tabelle (anwendungsabhängig!) sind diese Kosten nicht tolerierbar.
Benutze zwei (unabhängig berechnete) Hashfunktionen
Keine Methode, sondern eine Wahrscheinlichkeitsannahme für Verfahren mit offener Adressierung:
Jede Zelle hat Statusvariable status (voll, leer, gelöscht ). Löschen: Zelle nicht auf leer, sondern auf gelöscht setzen (engl.:"tombstone"). Suchen: Immer bis zur ersten leeren Zelle gehen. Zellen, die gelöscht sind, dürfen mit einem neuen Schlüssel überschrieben werden.
Überlauf tritt spätestens ein, wenn die letzte leere Zelle beschrieben werden würde. Sinnvoller: Überlauf tritt ein, wenn die Anzahl der vollen und gelöschten Zellen zusammen eine feste Schranke bound überschreitet.
Operationen bei offener Adressierung
- empty(m):
- Lege leeres Array
an. - Initialisiere alle Zellen
mit . - Wähle Hashfunktion
. - Initialisiere inUse mit 0. (Zählt nicht-leere Zellen.)
- Initialisiere load mit 0. (Zählt Einträge.)
- Initialisiere bound (z.B. mit
, maximal ).
- Lege leeres Array
- lookup/delete(x)
- Finde erstes l in der Folge
mit - 1.Fall:
: return "not found" bzw mache nichts - 2.Fall:
und : return data bzw lösche key und setzte status auf gelöscht (load--)
- 1.Fall:
- Finde erstes l in der Folge
- insert(x)
-
- Fall:
: (Update)
- Fall:
-
- Fall: $T[l'].status = gelöscht: T[l']\leftarrow (x,r,voll); load++ (überschreibe gelöschtes Feld)
-
- Fall:
: , neue Zelle
- Fall:
-
Implementierung eines dynamisches Wörterbuchs. Zwei Tabellen
Hashfunktionen verteilen Schlüssel rein zufällig. Wenn man Cuckoo-Hashing mit
Input: Tupel
Stabil (Bei Vorkommen gleicher Sortierschlüssel) Sortierverfahren heißt stabil, wenn Objekte mit identischen Schlüsseln in der Ausgabe in derselben Reihenfolge stehen wie in der Eingabe.
Maßzahlen für Sortieralgorithmen (in Abhängigkeit von n):
- Laufzeit (in O-Notation)
- Anzahl der Vergleiche ( wesentliche Vergleiche“) ”$a_i.key < a_j.key$“ bzw. "$a_i.key \leq a_j.key“
- Anzahl der Datenverschiebungen oder Kopiervorgänge
- der neben dem Array (bzw. der linearen Liste) benötigte Speicherplatz;
wenn dieser nur
, also von n unabhängig, ist: Algorithmus arbeitet "in situ“ oder "in-place“.
(engl. merge = vermengen, reißverschlussartig zusammenfügen)
Algorithmenparadigma oder -schema: "Divide-and-Conquer“ (D-a-C, teile und herrsche“). (Kleine Teilarrays werden durch Insertionsort sortiert)
Sortiert stabil. Rechenzeit ist
Vorgehen auf Instanz
- Teile: Zerteile x in (zwei oder mehr) Stücke
. (Wesentlich für Korrektheit/Terminierung: Jedes der Stücke ist "kleiner“ als x .) - Rekursion: Löse P für
, separat, durch rekursive Verwendung von A. Teillösungen: . - Kombiniere: Baue aus
und und eine Lösung für auf auf.
function Mergesort (a, b) // 1 ≤ a ≤ b ≤ n , sortiert A[ a..b ]
if b − a ≤ n 0 // n 0 ≥ 0 ist vorausgesetzt
then Insertionsort (a, b)
else // Wissen: Länge von A[ a..b ] ist ≥ 2
m = a + $\lfloor$b(b − a)/2 $\rfloor$;
Mergesort(a, m);
Mergesort( m + 1, b) ;
Merge (a, m , b) // fügt sortierte Teilfolgen zusammen;
function Merge (a, m, b) // für 1 ≤ a ≤ m < b ≤ n , sortiert A[ a..b ], nimmt an, dass A[ a..m ] und A[ m + 1..b ] sortiert sind.
i = a; // Index in A[ a..m ]
j = m + 1; // Index in A[ m + 1..b ]
k = a; // Index in B[ a..b ]
while i ≤ m and j ≤ b do
if A[i] ≤ A[j]
then B[k] = A[i]; ++i; ++k
else B[k] = A[j]; ++j; ++k // verbleibendes Schlussstück kopieren:
while i ≤ m do B[k] = A[i]; ++i; ++k;
while j ≤ b do B[k] = A[j]; ++j; ++k;
// B[ a..b ] nach A[ a..b ] kopieren:
for k from a to b do A[k] = B[k]
Folgt ebenso wie Mergesort dem Divide-and-Conquer-Ansatz.
Quicksort ist nicht stabil.
Rechenzeit beträgt
Ansatz für qsort(a, b), gleichzeitig Korrektheitsbetrachtung:
0. Trivialitätstest: Wenn
- Teile: (Hier "partitioniere“) Wähle Pivotelement x ∈ {A[a].key,...,A[b].key}. Arrangiere die Einträge von A[a..b] so um, dass für ein p mit a ≤ p ≤ b gilt: A[p].key = x und A[a].key, . . . , A[p − 1].key ≤ x < A[p + 1].key, . . . , A[b].key.
- Rekursion auf Teilinstanzen x 1 = A[a..p − 1] und x 2 = A[p + 1..b]: qsort(a, p − 1); r qsort(p + 1, b). Nach I.V. gilt nun: A[a..p − 1], A[p + 1..b] sortiert.
- Kombiniere: Es ist nichts zu tun: A[a..b] ist sortiert.
- "Clever Quicksort“: Das Pivotelement x ist der Median der drei Schlüssel A[a].key, A[b].key, A[a + b(b − a)/2c].key
- "Randomisiertes Quicksort“: Wähle einen der b − a + 1 Einträge in A[a..b] zufällig.
- Allgemein: Wähle ein s mit a ≤ s ≤ b, vertausche A[a] mit A[s]. Das Pivotelement ist danach immer A[a].key.
function qsort(a, b) // Rekursive Prozedur im Quicksort-Algorithmus, 1 ≤ a ≤ n + 1, 0 ≤ b ≤ n.
if a < b then
s = ein Element von {a, . . . , b}; // Es gibt verschiedene Methoden, um s zu wählen;
vertausche A[a] und A[s];
partition(a, b, p); // p: Ausgabeparameter
qsort(a, p − 1);
qsort(p + 1, b);
function partition(a, b, p) // Voraussetzung: a < b; Pivotelement: A[a]
x = A[a].key;
i = a + 1;
j = b;
while i ≤ j do // noch nicht fertig; Hauptschleife
while i ≤ j and A[i].key ≤ x do ++i;
while j > i and A[j].key > x do --j;
if i = j then --j; // Wissen: A[i].key > x
if i < j then
vertausche A[i] und A[j];
++i; --j;
if a < j then vertausche A[a] und A[j];
p = j; // Rückgabewert
Heap-Ordnung in Binärbäumen
Min-Heapsort: Ein Binärbaum T mit Knotenbeschriftungen m(v) aus (U, <) heißt min-heapgeordnet (kurz oft: heapgeordnet), wenn für alle Knoten v und w gilt: v Vorgänger von w ⇒ m(v) ≤ m(w). ⇒ in Knoten v steht der minimale Eintrag des Teilbaums
Ein "linksvollständiger“ Binärbaum: Alle Levels j = 0, 1, . . . voll (jeweils 2 j Knoten) bis auf das tiefste. Das tiefste Level l hat von links her gesehen eine ununterbrochene Folge von Knoten.
(Unendlicher) vollständiger Binärbaum (mit Kunstwurzel), Kante zu linkem/rechtem Kind mit 0/1 beschriftet, Knoten gemäß Leveldurchlauf-Anordnung nummeriert. Beispiel:
- Knoten 1 ist die Wurzel;
- Knoten 2i ist linkes Kind von i;
- Knoten 2i + 1 ist rechtes Kind von i;
- Knoten i ≥ 2 hat Vorgänger
.
Min-Heap:
Heaps reparieren nach austausch von Knoten/Werten:
function bubbleDown (1, k) // Heap-Reparatur in A[ 1 . . k ]. Vorbedingung: Höchstens A[ 1 ] ist zu groß
j = 1; // aktueller Knoten“
done = (2 · j > k);
while not done do // (∗) höchstens A[j] ist zu groß, A[j] hat Kind A[ 2 · j] im Baum
m = 2 · j;
if m + 1 ≤ k and A[m+1].key < A[m].key
then m = m + 1 ; // nun gilt: A[m] ist einziges oder "kleineres“ Kind von A[j]
if A[m].key < A[j].key
then vertausche A[j] mit A[m];
j = m; // neuer aktueller Knoten
done = (2 · j > k) ; // wenn done = false, gilt wieder (∗)
else done = true. // fertig, kein Fehler mehr.
Die Idee von Heapsort für ein Array A[1..n] ist nun folgende:
- (Heapaufbau) Arrangiere A[1..n] so um, dass ein Heap entsteht.
- (Auswahlphase) Für k von n abwärts bis 2: Entnimm kleinsten Eintrag A[1] aus dem Heap A[1..k]. Stelle mit den in A[2..k] verbliebenen Einträgen in A[1..k − 1] wieder einen Heap her. (In A[k] ist dann Platz für den entnommenen Eintrag.)
function HeapSelect(1, n)
for k from n downto 2 do // in A[1] steht das Minimum von A[1..k]
vertausche A[1] mit A[k]; // in A[1..k − 1] ist höchstens A[1] zu groß
bubbleDown(1, k − 1); // Heapreparatur
Die Prozedur HeapSelect(1, n) führt höchstens 2n log n Vergleiche durch und hat Rechenzeit O(n log n).
Idee: Betrachte im linksvollständigen Baum mit n Knoten die Teilbäume
Also löst die folgende Variante von bubbleDown (s.o.) die Aufgabe (mit j=l als Startbedingung).
function makeHeap(1, n) // Transformiert Array A[1 . . n] in einen Heap
for ell from $\lfloor$ n/2 $\rfloor$ downto 1 do
bubbleDown(ell, n);
Ein Aufruf makeHeap(1, n) wandelt A[1..n] in einen Heap um. Die Anzahl der Vergleiche ist nicht größer als 2n; die Rechenzeit ist
Der Aufruf HeapSort(A[1 . . n]) sortiert A[1 . . n] in fallende Reihenfolge. Die gesamte Rechenzeit ist O(n log n), die Gesamtzahl der Vergleiche ist kleiner als 2n(log n + 1). HeapSort arbeitet in situ/in-place (ist aber nicht stabil).
function HeapSort(A[1 . . n])
makeHeap(1, n);
HeapSelect(1, n);
In einer Prioritätswarteschlange werden Objekte aufbewahrt, die mit einem Schlüssel aus einem totalgeordneten Universum (U, <) versehen sind. (Oft sind die Schlüssel Zahlen.) Objekte werden eingefügt und entnommen. Einfügungen sind beliebig möglich. Beim Entnehmen wird immer ein Eintrag mit minimalem Schlüssel gewählt. Idee: Schlüssel entsprechen hier "Prioritäten“ – je kleiner der Schlüssel, desto höher die Priorität. Wähle stets einen Eintrag mit höchster Priorität! Der Datentyp Prioritätswarteschlage ist mit Heaps effizient zu realisieren.
Datentyp: SimplePriorityQueue (Einfache Prioritätswarteschlange)
- Signatur:
- Sorten:
- Keys
- Data
- PrioQ // "Priority Queues“
- Boolean
- Operatoren:
- empty : → PrioQ
- isempty : PrioQ → Boolean
- insert : PrioQ × Keys × Data → PrioQ -extractMin: PrioQ → PrioQ × Keys × Data
- Sorten:
- Mathematisches Modell
- Sorten:
- Keys: (U, <) //totalgeordnetes Universum
- Data: D // Menge von "Datensätzen"
- Boolean: {false, true}
- PrioQ: die Menge aller endlichen Multimengen (Elemente dürfen mehrfach vorkommen) P ⊆ U × D
- Operationen:
- empty ( ) = ∅ // die leere Multimenge
- isemtpy(P) = true, für P = ∅; false, für
- insert(P, x, d) = P ∪ {(x, d)} (als Multimenge),
- extractMin(P) = undefiniert, wenn P = ∅; (P' , x_0 , d_0 ), wenn P \not= ∅
- Sorten:
extractMin: Implementierung von extractMin(P): Ein Eintrag mit minimalem Schlüssel steht in der Wurzel, d. h. in Arrayposition 1.
Zeitaufwand:
function extractMin()
// Entnehmen eines minimalen Eintrags aus Priority-Queue
// Ausgangspunkt: Pegelstand n (in n), A[1 . . n] ist Heap, n ≥ 1
if n = 0
then Fehlerbehandlung“;
x = A[1].key;
d = A[1].data;
A[1] = A[n];
n--;
if n > 1 then bubbleDown(1, n);
return (x, d);
Für Fehlerbehandlung z.B. bubbleUp um Heap zu reparieren
function bubbleUp(i) // Heapreparatur ab A[i] nach oben
j = i;
h = $\lfloor$ j/2 $\rfloor$ ;
while h ≥ 1 and A[h].key > A[j].key do
vertausche A[j] mit A[h];
j = h;
h = $\lfloor$ j/2 $\rfloor$.
Überlaufbehandlung
function insert(x, d) // Einfügen eines neuen Eintrags in Priority-Queue
// Ausgangspunkt: Pegel n enthält n, A[1 . . n] ist Heap.
if n = m
then "Überlaufbehandlung"; // z. B. Verdopplung
n++;
A[n] ← (x, d);
bubbleUp(n)
Allgemeinere Operation: "decreaseKey" ersetzt einen beliebigen Schlüssel im Heap (Position i) durch einen kleineren. Mit bubbleUp(i) wird die Heapeigenschaft wieder hergestellt.
function decreaseKey(x, i)
// Erniedrigen des Schlüssels an Arrayposition i auf x
if A[i].key < x
then Fehlerbehandlung
A[i].key = x;
bubbleUp(i)
Dabei erfordern empty und isempty (und das Ermitteln des kleinsten Eintrags) konstante Zeit, und insert, extractMin und decreaseKey benötigen jeweils Zeit O(log n). Dabei ist n jeweils der aktuelle Pegelstand, also die Anzahl der Einträge in der Prioritätswarteschlange.
Wie soll man der Datenstruktur "mitteilen“, welches Objekt gemeint ist, wenn decreaseKey auf einen Eintrag angewendet werden soll? Erweiterung der Datenstruktur: Objekt (x, d) erhält bei Ausführung von insert (x, d) eine eindeutige und unveränderliche "Identität“ p zugeteilt, über die dieses Objekt angesprochen werden kann. (Damit können sogar verschiedene Kopien ein und desselben Datensatzes unterschieden werden!)
Datentyp: PriorityQueue (Prioritätswarteschlange)
- Signatur:
- Sorten:
- Keys
- Data
- Id // "Identitäten“
- PrioQ
- Boolean
- Operationen:
- empty : → PrioQ
- isempty : PrioQ → Boolean
- insert: PrioQ × Keys × Data → PrioQ × Id
- extractMin: PrioQ → PrioQ × Id × Keys × Data
- decreaseKey : PrioQ × Id × Keys → PrioQ
- Sorten:
- Mathematisches Modell
- Sorten:
- Keys: (U, <) // totalgeordnetes Universum“
- Data: D // Menge von Datensätzen“
- Id: N = {0, 1, 2, . . .} // unendliche Menge möglicher Identitäten“
- Boolean: {false, true}
- PrioQ: die Menge aller Funktionen f : X → U × D, wobei X = Def (f ) ⊆ N endlich ist
- Operationen:
- empty () = ∅ // die leere Funktion
- isempty(f) = true, für f = ∅; false, für f \not = ∅
- insert(x, d, f ) = (f ∪ {(p, (x, d))}, p), für ein p ∈ N − Def(f )
- extractMin(f) = undefiniert, für f = ∅; (f 0 , p 0 , x 0 , d 0 ), für f \not= ∅
- decreaseKey(p,x) = (f − {(p, (y, d))}) ∪ {(p, (x, d))}, falls f (p) = (y, d) mit x ≤ y (sonst Fehler)
- Sorten:
Ein Sortieralgorithmus A heißt ein Schlüsselvergleichsverfahren, wenn in A auf Schlüssel x, y aus U nur Operationen:
Allgemein: Jeder vergleichsbasierte Sortieralgorithmus A erzeugt für jedes n einen Vergleichsbaum T A,n mit genau n! Blättern. Die Wege im Baum von der Wurzel zu den Blättern entsprechen den Berechnungen von A auf den n! genannten Eingaben; die Knoten auf einem solchen Weg entsprechen den in der Berechnung ausgeführten Vergleichen.
Wenn A ein Schlüsselvergleichsverfahren ist, das das Sortierproblem für beliebige Inputs mit n Komponenten löst, dann gibt es eine Eingabe (a 1 , . . . , a n ) (eine Permutation von {1, . . . , n} ) ,auf der A mindestens
Wenn A ein Schlüsselvergleichsverfahren ist, das das Sortierproblem für alle Inputs mit n Komponenten löst und dabei Randomisierung benutzt (d. h. Zufallsexperimente ausführt wie etwa Randomisiertes Quicksort) , dann gibt es eine Eingabe a = (a 1 , . . . , a n ), so dass die erwartete Vergleichsanzahl von A auf a (gemittelt über die Zufallsexperimente von A) mindestens log(n!) ist.
Wenn wir Schlüssel nicht als atomares Objekt, sondern z. B. als Index benutzen, dann gilt die untere Schranke nicht. Wir wollen (für besondere Schlüsselformate, ganze Zahlen oder Strings) in Linearzeit sortieren!
Idee, drei Phasen:
- Zähle in Komponente C[i] eines Arrays C[0..m − 1], wie oft der Schlüssel i vorkommt.
- Benutze das Ergebnis von 1., um (wieder in C[i]) zu berechnen, wie viele Einträge in A einen Schlüssel ≤ i haben.
- Übertrage die Einträge mit Schlüssel i aus A in die Positionen C[i−1]+1, . . . ,C[i] in Array B, stabil.
for i from 0 to m − 1 do C[i] = 0; // Zeitaufwand: Θ(m)
for j from 1 to n do C[A[j].key]++; // Zeitaufwand: Θ(n)
for i from 1 to m − 1 do C[i] = C[i−1] + C[i]; // Zeitaufwand: Θ(m)
for j from n downto 1 do // Zeitaufwand: Θ(n)
i = A[j].key;
B[C[i]] = A[j]; // aktueller Platz für Schlüssel i (in i)
C[i]--; // auf linken Nachbarn umsetzen
n Objekte mit Schlüsseln aus [m] (gegeben in Array) können in Zeit Θ(n + m) und mit Zusatzplatz Θ(n + m) sortiert werden. Das Sortierverfahren ist stabil. Linearzeit und linearer Platz, falls m ≤ cn, c konstant. Countingsort ist auch in der praktischen Anwendung sehr schnell
Nun seien die zu sortierenden Objekte mit Schlüsseln aus [m] als (einfach verkettete) lineare Liste gegeben. Durchlaufe Eingabeliste, übertrage Einträge mit Schlüssel i an den Anfang der Liste
- Bearbeite Elemente der Liste A nacheinander. Füge Listenelement (i, data) vorn in Liste B[i] ein. NB: Reihenfolge von Elementen mit demselben Schlüssel wird umgedreht.
- Für i = m − 1, . . . , 1, 0: lies B[i] von vorn nach hinten. Füge Element (i, data) vorn in Ausgabeliste ein. NB: Reihenfolge wird erneut umgedreht → Stabilität.
Korrektheit: klar. Laufzeit: 0. Anlegen von B, Initialisieren mit NULL-Zeigern: Θ(m).
- Verteilen auf die Listen: Θ(n)
- Zusammenfügen: Θ(m) + Θ(n) (Jeder Listenanfang B[i] muss inspiziert werden.) Gesamt: Θ(m + n). Linearzeit und linearer Platz, falls m ≤ cn, c konstant.
Anwendbar in verschiedenen Situationen:
- Schlüssel sind Folgen (Anordnungskriterium: lexikographisch)
- Schlüssel sind Zahlen
- k (möglicherweise verschiedene) geordnete Mengen
- Σ^{<∞} . Dabei: Σ ist "Alphabet“, d. h. nichtleere endliche Menge (z. B. ein ISO/IEC 8859-Alphabet) mit Ordnung <
Idee: sortiere k-mal mittels Counting-/Bucketsort und zwar gemäß Komponente k, dann k − 1, . . . , dann 1 (die "am wenigsten signifikante“ Komponente zuerst).
Graphen und Digraphen sind eine in der Informatik und zur Modellierung von Anwendungssituationen allgegenwärtige (Daten-)Struktur.
Ein gerichteter Graph oder Digraph G (wegen "directed graph“) ist ein Paar (V, E), wobei V eine endliche Menge und E eine Teilmenge von V × V = {(v, w) | v, w ∈ V } ist. Die Elemente von V heißen Knoten 1 , die Elemente von E heißen Kanten.
Ist e = (v, w) eine Kante (von G) bzw sei G = (V, E) ein Digraph, so
- v bzw. w heißen inzident zu e (v, w liegen auf“ e),
- Eine Kante (v, v) heißt Schleife ( loop“).
- Der Eingangsgrad ( "indegree“) eines Knotens v ist die Anzahl der Kanten, die in v hineinführen
- Der Ausgangsgrad ( "outdegree“) eines Knotens v ist die Anzahl der Kanten, die aus v herausführen
- Ein Kantenzug in G ist eine Folge p = (v 0 , v 1 , . . . , v k ) von Knoten, wobei (v i−1 , v i ) ∈ E für 1 ≤ i ≤ k.
- Ein Kantenzug (v 0 , v 1 , . . . , v k ) in einem Digraphen G heißt ein Kreis oder Zyklus ( "cycle"), wenn k ≥ 1 und v 0 = v k . Die Länge des Kreises ist k
- Ein Digraph G heißt kreisfrei oder azyklisch, wenn es in G keinen Kreis gibt, sonst heißt G zyklisch.
- Ein Graph G, der nur eine Zusammenhangskomponente hat, heißt zusammenhängend.
- Ein Graph heißt ein freier Baum (oder nur Baum), wenn er zusammenhängend und kreisfrei ist.
- maximal Kreisfrei für: G ist kreisfrei, aber das Hinzufügen einer beliebigen Kante zu G erzeugt einen Kreis
Ein ungerichteter Graph, oft auch: ein Graph G ist ein Paar (V, E), wobei V eine endliche Menge ist und E eine Teilmenge von
Handshaking-Lemma: Wenn G=(V,E) ein Graph ist, dann gilt
Sei G = (V, E) Graph oder Digraph.
V kann irgendeine endliche Menge sein. (z.B. {A,B,C,D,E}.)
Ordne die n = |V| Knoten beliebig an, z. B. als
Ist G = (V, E) Graph oder Digraph mit V = {1, . . . , n}, dann ist die Adjazenzmatrix von G die n × n-Matrix. Die Adjazenzmatrix eines Graphen ist symmetrisch: A[i, j] = A[j, i]. Die Anzahl der 1en in Zeile/Spalte i ist deg(i). Verwendet man zur Darstellung eines Graphen bzw. Digraphen mit n Knoten eine Adjazenzmatrix, so gilt:
- Der Speicherplatzbedarf ist
[Bits]; -
kann in Zeit ermittelt oder geändert werden; - die Ermittlung aller Nachfolger, Vorgänger oder Nachbarn eines Knotens erfordert Zeit
. (Zeilen/Spaltendurchlauf; Reihenfolge: 1, . . . , n ).
Erweiterungen der Adjazenzlistenstruktur:
- Knotenbeschriftungen: im nodes-Array zu platzieren.
- Kantenbeschriftungen: in zusätzlichen Komponenten (Attributen) in den Elementen für die Adjazenzlisten.
- In Graphen: Der Listeneintrag für j in
kann einen Zeiger zum Listeneintrag für i in (die "Gegenkante“) enthalten. - Bei Digraphen: Der Umkehrgraph
enthält in der Adjazenzliste für i die Knoten j, die Vorgänger von i in G sind.
Wenn ein Graph oder Digraph G = (V, E) mittels Adjazenzlisten dargestellt wird, gilt:
- Speicherplatz
wird benötigt - das Durchlaufen aller Kanten kann in Zeit
ausgeführt werden - das Durchlaufen der Adjazenzliste zu Knoten i benötigt Zeit
bzw. - (nur) falls Vorgängerlisten vorliegen, können auch die Vorgänger von Knoten i in Zeit
durchlaufen werden.
- Finde alle Knoten v, die von
aus erreichbar sind. - Nummeriere die entdeckten Knoten.
- Bestimme für jeden erreichbaren Knoten v einen Weg von
nach v mit minimaler Länge, und notiere diese Länge. - Diese Länge heißt der Abstand von
nach v, kurz , oder das Level von v (von aus gemessen).
Initialisierung: bfs_count=0; Alle bfs_num(v) werden auf 0 gesetzt. Q: Queue
function bfs (v_0 ) // Breitensuche von v 0 aus, v 0 wird entdeckt
bfs count++;
bfs num [v_0 ] = bfs count;
level [v_0 ] = 0 ;
p [v_0 ] = v_0 ; // Kennzeichne Startknoten
Q.enqueue (v_0 ) ; // Startknoten in Warteschlange stecken
while not Q.isempty do
v = Q.dequeue; // nun bearbeite v: für jeden Nachfolger w von v (Adjazenziste!) tue:
if bfs_num [ w ] = 0 then // w wird entdeckt:
bfs_count++;
bfs_num[ w ] = bfs_count;
level[ w ] = level[v] + 1 ;
p[ w ] = v; // w von v aus erreicht
Q.enqueue( w ) ;
Genau diejenigen Knoten, die von v_0 aus erreichbar sind, werden entdeckt, erhalten also eine bfs-Nummer, eine Levelnummer und einen Vorgänger, und sie werden bearbeitet, d. h., ihre Adjazenzliste wird durchlaufen. Die entdeckten Knoten mit den Kanten (p(v), v),
Wie erreichen wir die restlichen Knoten in G? Starte eine Breitensuche bei jedem Knoten v, der nicht bei einer vorherigen Breitensuche entdeckt worden ist. Behalte dabei die vorher vergebenen Nummern bei.
function BFS(G) // Breitensuche in G = (V, E)
bfs count ← 0;
for v from 1 to n do bfs num(v) ← 0;
for v from 1 to n do
if bfs num[v] = 0 then
bfs(v); // starte Breitensuche von v aus
Eingabeformat: Digraph
- Besuche alle Knoten und Kanten.
- Sammle einfache Strukturinformation.
Tiefensuche (Depth-First-Search)
Zunächst: Gehe von Knoten
Realisierung: Rekursive Prozedur "dfs(v)":
- "Besuche“ Knoten v (Aktion an diesem Knoten).
- Dann betrachte die Nachfolger
outdeg(v) von v nacheinander, aber: - Sobald neuer Knoten w "entdeckt“ wird, starte sofort dfs(w).
Man muss verhindern, dass Knoten v mehrfach besucht wird. Dazu: "Statusinformation“, in Array
- v neu – noch nie gesehen
- v aktiv – dfs(v) gestartet, noch nicht beendet
- v fertig – dfs(v) beendet Initialisierung: Alle Knoten sind neu .
Einfachversion:
Knoten werden in der Reihenfolge der Entdeckung durchnummeriert:
funcition dfs(v) // Tiefensuche an v, rekursiv, nur für v mit status[v] = neu aufzurufen
dfs count++;
dfs num[v] = dfs count;
status[v] = aktiv ;
dfs-visit(v); // Aktion an v bei Erstbesuch; für jeden Nachfolger w von v (Adjazenzliste!) tue:
if status[w] = neu // w wird entdeckt!
then dfs(w);
status[v] ← fertig .
Bei Tiefensuche von
Globale Tiefensuche in Digraphen: Alle Knoten und Kanten werden besucht.
function DFS(G) // Tiefensuche in G = (V, E) mit V = {1, . . . , n}
dfs count = 0;
for v from 1 to n do status[v] = neu ;
for v from 1 to n do
if status[v] = neu then
dfs(v);
// starte Tiefensuche von v aus
Wir bauen
- T ("Tree"): Baumkanten, die Kanten des Tiefensuchwaldes.
Kriterium: Wenn
die Kante betrachtet, ist noch neu. - B ("Back"): Rückwärtskanten. $(v, w) ist Rückwärtskante, wenn w Vorfahr von v im Tiefensuchwald ist.
Kriterium: Wenn
die Kante betrachtet, ist w aktiv . - F Vorwärtskanten ("Forward"): (v, w) ist Vorwärtskante, wenn w Nachfahr von v im Tiefensuchwald ist, und (v, w) keine Baumkante ist. Kriterium: Wenn dfs(v) die Kante (v, w) betrachtet, ist w fertig und dfs num(v) < dfs num(w).
- C Querkanten ("Cross"): (v, w) ist Querkante, wenn der gesamte Unterbaum von w schon fertig abgearbeitet ist, wenn dfs(v) aufgerufen wird. Kriterium: Wenn dfs(v) die Kante (v, w) betrachtet, ist w fertig und dfs num(v) > dfs num(w).
function dfs (v) // "volle“ Tiefensuche in v , nur für v neu erlaubt
dfs count++;
dfs num[ v ] ← dfs count;
status[ v ] ← aktiv ;
dfs-visit (v) ; // Aktion an v bei Entdeckung für jeden Nachfolger w von v (Adjazenzliste!) tue:
1. Fall: status[w] = neu: T ← T ∪ {(v, w )} ; dfs ( w ) ;
2. Fall: status[w] = aktiv: B ← B ∪ {(v, w )} ;
3. Fall: status[w] = fertig ∧ dfs num[ v ] < dfs num[w]: F ← F ∪ {(v, w )} ;
4. Fall: status[w] = fertig ∧ dfs num[ v ] > dfs num[w]: C ← C ∪ {(v, w )} ;
f count++;
f num[ v ] ← f count;
fin-visit (v) ; // Aktion an v bei Abschluss
status[ v ] ← fertig .
Initialisierung: dfs count ← 0; f count ← 0.
Alle Knoten sind neu ; Mengen T , B, F , C sind leer.
Tiefensuche von
Tiefensuche für den ganzen Graphen: DFS(G) wie vorher, nur mit der voll ausgebauten dfs-Prozedur, und der Initialisierung von f count und T , B, F , C.
function DFS (G) // Tiefensuche in G = (V, E) , voll ausgebaut
dfs count ← 0 ;
f count ← 0 ;
T ← ∅; B ← ∅; F ← ∅; C ← ∅;
for v from 1 to n do status[v] ← neu ;
for v from 1 to n do
if status[v] = neu then
dfs ( v ) ; // starte (volle) Tiefensuche von v aus
- Beobachtung 1: Jede Kante (v, w) wird genau einmal betrachtet und daher genau in eine der Mengen T , B, F und C eingeordnet.
- Beobachtung 2: Die dfs-Nummern entsprechen einem Präorder-Durchlauf, die f-Nummern einem Postorder-Durchlauf durch die Bäume des Tiefensuch-Waldes.
- Beobachtung 3: Folgende Aussagen sind äquivalent:
- dfs(w) beginnt nach dfs(v) und endet vor dfs(v) (d.h. dfs (w) wird (direkt oder indirekt) von dfs (v) aus aufgerufen);
- dfs num[v] < dfs num[w] ∧ f num[v] > f num[w];
- v ist Vorfahr von w im Tiefensuch-Wald.
Einfacher als Tiefensuche in gerichteten Graphen. Zweck:
- Zusammenhangskomponenten finden
- Spannbaum für jede Zusammenhangskomponente finden
- Kreisfreiheitstest
function udfs(v) // Tiefensuche von v aus, rekursiv; nur für v mit status[v] = neu aufrufen
dfs count++;
dfs num[v] ← dfs count;
dfs-visit(v); // Aktion an v bei Erstbesuch
status[v] ← aktiv ;
für jede neue“ Kante (v, w) (Adjazenzliste!) tue:
setze Gegenkante (w, v) auf gesehen“ ;
1. Fall: status[w] = neu : T ← T ∪ {(v, w)}; udfs(w);
2. Fall: status[w] = aktiv: B ← B ∪ {(v, w)};
f count++;
f num[v] ← f count;
fin-visit(v); // Aktion an v bei letztem Besuch
status[v] ← fertig.
//Globale Tiefensuche in (ungerichtetem) Graphen G:
function UDFS(G) // Tiefensuche in G = (V, E)
dfs_count ← 0;
f_count ← 0;
for v from 1 to n do status[v] ← neu ;
T ← ∅; B ← ∅;
for v from 1 to n do
if status[v] = neu then
udfs(v); // starte Tiefensuche von v aus
-
entdeckt genau die Knoten in der Zusammenhangskomponente von - Die Kanten (v, w), für die udfs(w) unmittelbar aus udfs(v) aufgerufen wird, bilden einen gerichteten Baum mit Wurzel v 0 ("Tiefensuchbaum")
- (Satz vom weißen Weg) u ist im DFS-Baum ein Nachfahr von v genau dann wenn zum Zeitpunkt des Aufrufs udfs(v) ein Weg von v nach u existiert, der nur neue (weiße) Knoten enthält.
- Die T -Kanten bilden eine Reihe von Bäumen (die Tiefensuch-Bäume). Die Knotenmengen dieser Bäume sind die Zusammenhangskomponenten von G.
- Die Wurzeln der Bäume sind die jeweils ersten Knoten einer Zusammenhangskomponente in der Reihenfolge, die in Zeile (2) benutzt wird.
Gesamtrechenzeit:
Kreisfreiheitstest in Graphen und Finden eines Kreises, wenn es einen gibt:
Nach Ausführung von UDFS(G) gilt:
-
Ein Kantenzug
in einem Digraphen G heißt ein Kreis oder Zyklus, wenn k ≥ 1 und . -
Ein Kreis
heißt einfach, wenn verschieden sind. -
Ein Digraph G heißt kreisfrei oder azyklisch, wenn es in G keinen Kreis gibt, sonst heißt G zyklisch.
-
Azyklische gerichtete Graphen: "Directed Acyclic Graphs", daher DAGs.
Zwei Knoten v und w in einem Digraphen G heißen äquivalent, wenn
Die Äquivalenzklassen zur Relation
- Trick 1: Führe DFS im "Umkehrgraphen“
durch, der durch Umkehren aller Kanten in G entsteht. - Beobachtung: G R hat dieselben starken Zusammenhangskomponenten wie G.
- Trick 2: Verwende die f-Nummern einer ersten DFS in G, um zu bestimmen, in welcher Reihenfolge die Knoten in der Hauptschleife der zweiten DFS (in
) betrachtet werden.
Strong Components(G) (von S. R. Kosaraju, 1978)
- Eingabe: Digraph G = (V, E)
- Ausgabe: Starke Zusammenhangskomponenten von G
- (1) Berechne die f-Nummern mittels DFS(G);
- (2) Bilde "Umkehrgraphen“
durch Umkehren aller Kanten in G; - (3) Führe
durch; Knotenreihenfolge: f-Nummern aus (1) absteigend - (4) Ausgabe: Die Knotenmengen der Tiefensuchbäume aus (3) .
Algorithmus Karatsuba(x, y)
Eingabe: Zwei n-Bit-Zahlen x und y, nichtnegativ
if n ≤ n 0
then return SM(x, y) // Schulmethode
else
k ← dn/2e;
zerlege x = A · 2 k + B und y = C · 2 k + D;
E ← A − B und F ← C − D; // auf dn/2e Bits aufgefüllt
G ← Karatsuba(A, C); // Rekursion
H ← Karatsuba(B, D); // Rekursion
I ← Karatsuba(|E|, |F |); // Rekursion
return G · 2 2k + (G + H − sign(E) · sign(F ) · I) · 2 k + H
Eingabe: Zwei
- Falls
: Berechne mit der direkten Methode. Kosten Multiplikationen. - Falls
, zerlege A, B in jeweils 4 quadratische -Teilmatrizen $A=(\frac{C | D}{E | F}); B=(\frac{G | H}{K | L}); AB=(\frac{CG+DK| CH+DL}{EG+FK| EH+F*L})$ Einfache Analyse ergibt: Dies führt zu Multiplikationen in R, kein Gewinn.
Mit "Straßentrick": 7 Multiplikationen genügen
-
Dann:
"Rekursionsbaum“: Veranschaulicht Kostenaufteilung
Wenn v ein Knoten auf Level i ist, dann gilt:
Es gelte $B(n) ≤ \begin{} g, falls n = 1; \ a · B(n/b) + f (n) , sonst, \end{}$
für ganzzahlige konstante
- Fall:
mit . Dann: - Fall:
mit . Dann: - Fall:
mit und , für c < 1 konstant. Dann gilt .
Gegeben ist eine Folge
Prozedur rqSelect(a, b, k)
// Rekursive Prozedur im Quickselect-Algorithmus, 1 ≤ a ≤ b ≤ n , a ≤ k ≤ b .
// Vorbedingung: Alle Einträge vom Rang < a [ > b ] links [rechts] von A[ a..b ]
// Nachbedingung: Eintrag vom Rang k in A[ k ], kleinere links, größere rechts davon.
if a = b (= k) then return;
s ← ein zufälliges Element von {a, . . . , b};
if (a < s) then vertausche A[a] und A[s];
partition(a, b, p); // wie bei rqsort
if k = p then return;
if k < p then rqSelect(a, p − 1, k)
else rqSelect(p + 1, b, k).
Greedy-Algorithmen sind anwendbar bei Konstruktionsaufgaben, deren Ziel es ist, eine optimale Struktur zu finden, die aus mehreren Komponenten besteht. Sie finden eine Lösung, die sie schrittweise aufbauen. In jedem Schritt wird eine "lokal“ oder aus der aktuellen Sicht optimale Entscheidung getroffen, ohne "an die Zukunft zu denken“. (Was dies konkret bedeutet, versteht man besser anhand der später betrachteten Beispiele.) Es werden dabei nicht mehr Teillösungen konstruiert als unbedingt nötig. Es werden nie Entscheidungen korrigiert oder zurückgesetzt.
Gegeben: Veranstaltungsort (Hörsaal), Zeitspanne
Gesucht: Belegung des Hörsaals, die möglichst viele Ereignisse mit disjunkten Zeitspannen stattfinden lässt.
$ A ⊆ {1, . . . , n}$ heißt zulässig, wenn alle
Trick: Bearbeite Ereignisse in der Reihenfolge wachsender Schlusszeiten. O.B.d.A.: Veranstaltungen nach Schlusszeiten aufsteigend sortiert (Zeitaufwand
Algorithmus Greedy Scheduling (GS)
Eingabe: Reelle Zahlen
Sortiere Paare // gemäß $f_1 , . . . , f_n$ , nummeriere um, so dass $f_1 ≤ · · · ≤ f_n$ ;
A ← {1};
f_last ← f_1 ;
for i from 2 to n do
if s_i ≥ f_last then // [s i , f i ) wählbar
A ← A ∪ {i};
f_last ← f_i ;
return A
Veranschaulichung: Ein Dieb stiehlt Säckchen mit Edelmetallkrümeln (Gold, Silber, Platin) und Edelsteinen. Er hat einen Rucksack mit Volumen b dabei. Durch teilweises Ausleeren der Säckchen kann er beliebige Teilvolumina herstellen. Der Wert pro Volumeneinheit ist unterschiedlich für unterschiedliche Materialien. Was soll er in seinen Rucksack mit Volumen b packen, um den Wert der Beute zu maximieren?
Dazu: Benenne den Bruchteil
- Volumina
, - Nutzenwerte
, - Volumenschranke b Gesucht:
- Vektor
, so dass ("zulässig") und maximal. Kern der Lösungsidee: - Berechne "Nutzendichten“:
, - und sortiere die Objekte gemäß
fallend. - Nehme von vorne beginnend möglichst viele ganze Objekte, bis schließlich das letzte Objekt teilweise genommen wird, so dass die Volumenschranke vollständig ausgeschöpft wird.
function Greedy_Fractional_Knapsack() //(GFKS)
for i from 1 to n do
d_i = c_i /a_i ;
λ_i = 0;
Sortiere Objekte gemäß d i fallend;
i = 0;
r = b; // Inhalt r ist das verfügbare Rest-Volumen
while r > 0 do
i++;
if a_i ≤ r
then λ_i = 1; r = r − a_i ;
else λ_i = r/a_i ;
r = 0;
Der Algorithmus GFKS ist korrekt (liefert eine zulässige Lösung mit maximalem Gesamtnutzen) und hat Rechenzeit
Charakteristika der Greedy-Methode:
- Der erste Schritt der Greedy-Lösung ist nicht falsch. Es gibt eine optimale Lösung, die als Fortsetzung des ersten Schrittes konstruiert werden kann.
- "Prinzip der optimalen Substruktur“: Kombiniert man das Ergebnis des ersten "Greedy-Schritts“ mit einer beliebigen optimalen Lösung für die reduzierte Instanz (Wegnehmen des Teils, der durch den ersten Schritt erledigt ist), dann ergibt sich eine optimale Lösung für die Originaleingabe.
- Der Algorithmus löst das verbleibende Teilproblem rekursiv (oder mit einem zur Rekursion äquivalenten iterativen Verfahren).
Gegeben: Alphabet A mit
Gesucht: ein "guter" binärer Präfixcode für (A, p)
Definition Präfixcode: Jedem
Kompakte Repräsentation des Codes als Binärbaum. Blätter sind mit Buchstaben markiert; Weg von der Wurzel zum Blatt gibt das Codewort wieder (links: 0, rechts: 1).
Decodierung: Laufe Weg im Baum, vom Codewort gesteuert, bis zum Blatt. Wiederhole mit dem Restwort, bis nichts mehr übrig ist. Präfixeigenschaft ⇒ keine Zwischenräume nötig.
- Idee: Mache alle Codewörter
gleich lang. Am besten ist dann eine Länge von Bits. ⇒ hat Länge . - Idee: Einsparmöglichkeit: Häufige Buchstaben mit kürzeren Wörtern codieren als seltenere Buchstaben. Ein erster Ansatz zur Datenkompression (platzsparendes Speichern, zeitsparendes Übermitteln)! Hier: verlustfreie Kompression“ – Information ist unverändert vorhanden
Ein Codierungsbaum für A ist ein Binärbaum T , in dem
- die Kante in einem inneren Knoten zum linken bzw. rechten Kind (implizit) mit 0 bzw. 1 markiert ist
- jedem Buchstaben
ein Blatt (externer Knoten) von T exklusiv zugeordnet ist. - Der Code
für a ist die Kanteninschrift auf dem Weg von der Wurzel zum Blatt mit Inschrift a. - Die Kosten von T unter p sind definiert als:
, wobei die Tiefe des a-Blatts in T ist. - Ein Codierungsbaum T für A heißt optimal oder redundanzminimal für p, wenn für alle Codierungsbäume
für A gilt: .
Aufgabe: Gegeben (A, p), finde einen optimalen Baum. Methode: "Greedy“
Es seien
Damit ist der erste Schritt zur Realisierung eines Greedy-Ansatzes getan! Man beginnt den Algorithmus mit "Mache die beiden seltensten Buchstaben zu Geschwistern“. Dann ist sicher, dass dies stets zu einer optimalen Lösung ausgebaut werden kann. Dann werden diese beiden Buchstaben "zusammengeklebt“, so dass man ein Alphabet erhält, das eine um 1 kleinere Größe hat. Konzeptuell wendet man dann Rekursion an.
Huffman-Algorithmus (rekursiv): Wir bauen "bottom-up“ einen Baum auf.
- Wenn |A| = 1: Baum hat nur einen (externen) Knoten. (Code für den einen Buchstaben ist das leere Wort. Seltsam, aber als Rekursionsbasis geeignet.) Die Kosten sind 0. (Optimalität ist klar.)
- Wenn |A| > 1, werden zwei "seltenste“ Buchstaben a, a 0 aus A zu benachbarten Blättern gemacht.
Man könnte nach dem angegebenen Muster eine rekursive Prozedur programmieren.
- PQ: Datenstruktur Prioritätswarteschlange,
- Einträge: Buchstaben und Kunstbuchstaben;
- Schlüssel: die Gewichte p(b), b (Kunst-)Buchstabe.
- Operationen:
- PQ.insert: Einfügen eines neuen Eintrags;
- PQ.extractMin: Entnehmen des Eintrags mit kleinstem Schlüssel.
- Beide Operationen benötigen logarithmische Zeit (s. Kap. 6).
- Anfangs in PQ: Buchstaben a ∈ A mit Gewichten p(a) als Schlüssel.
- Ermitteln und Entfernen der beiden seltensten“ Buchstaben a, a 0 durch zwei Aufrufe ”PQ.extractMin";
- Einfügen des neuen Kunstbuchstabens b durch PQ.insert(b).
- Resultierende Rechenzeit:
, für .
Iterative Implementierung mit ein paar Tricks wird viel effizienter.
Algorithmus Huffman(
Erweitere den Vektor p[ 1 .. n ] auf Länge 2n − 1 ;
pred[1] ← n + 1;
pred[2] ← n + 1;
mark[1] ← 0;
mark[2] ← 1;
p[n + 1] ← p[1] + p[2] ;
k ← 3 // erster nicht verarbeiteter Knoten in [ 1..n ]
h ← n + 1 // erster nicht verarbeiteter Knoten in [ n + 1..2n − 2 ]
for b from n + 2 to 2n − 1 do // Die folgenden beiden Zeilen finden, in i und j, die Positionen der beiden noch nicht verarbeiteten Buchstaben mit kleinsten Gewichten
if k ≤ n and p[k] ≤ p[h]
then i ← k;
k++
else
i ← h;
h++;
if k ≤ n and (h = b or p[k] ≤ p[h])
then j ← k;
k++
else
j ← h;
h++;
pred[i] ← b;
pred[j] ← b;
mark[i] ← 0 ;
mark[j] ← 1 ;
p[b] ← p[i] + p[j];
Ausgabe:
Aus
for i from 1 to n do
leaf[i].letter ← Buchstabe a_i
if mark[i] = 0
then inner[pred[i]].left ← leaf[i]
else inner[pred[i]].right ← leaf[i]
for i from (n + 1) to (2n − 2) do
if mark[i] = 0
then inner[pred[i]].left ← inner[i]
else inner[pred[i]].right ← inner[i]
return inner[ 2n − 1 ] // Wurzelknoten
Der Algorithmus Huffman ist korrekt und hat Laufzeit
- Ein gewichteter Digraph
besteht aus einem Digraphen und einer Funktion , die jeder Kante einen Wert zuordnet. - Ein gerichteter Kantenzug
in G hat Kosten/länge/Gewicht - Der (gerichtete) Abstand von
ist min{c(p) | p Kantenzug von v nach w} ( , falls kein Kantenzug von v nach w existiert; , falls es von v nach w Kantenzüge mit beliebig stark negativen Kosten gibt.)
Hier betrachten wir einen Algorithmus für das Problem "Single-Source-Shortest-Paths (SSSP) (Kürzeste Wege von einem Startknoten aus).
Gegeben: Gewichteter Digraph
Algorithmus Dijkstra-Distanzen(G, s)
Eingabe: gewichteter Digraph
S = ∅;
dist[s] = 0;
for w ∈ V − {s}
do dist[w] = ∞;
while ∃u ∈ V − S: dist[u] < ∞ do // "Runde"
u = ein solcher Knoten u mit minimalem dist[u];
S = S ∪ {u};
for w mit (u, w) ∈ E und w $\not ∈$ S do // Nachfolger von u, nicht bearbeitet
dist[w] = min{dist[w], dist[u] + c(u, w)};
Ausgabe: das Array dist[1..n].
Der Algorithmus Dijkstra-Distanzen gibt in
Wir wollen aber eigentlich nicht nur die Distanzen
Algorithmus Dijkstra(G, s)
Eingabe: gewichteter Digraph
S = ∅;
dist[s] = 0;
p[s] = −2;
for w ∈ V − {s}
do dist[w] = ∞; p[w] = −1;
while ∃u ∈ V − S: dist[u] < ∞ do
u = ein solcher Knoten u mit minimalem dist[u];
S = S ∪ {u};
for (u, w) ∈ E mit w $\not ∈$ S do // Nachfolger von u, nicht bearbeitet: update ( u , w )
dd = dist[u] + c(u, w);
if dd < dist[w] then
dist[w] = dd;
p[w] = u;
Ausgabe: dist[1..n] und p[1..n].
Nach dem Algorithmus ist klar, dass
Ergebnis:
Wenn der Algorithmus von Dijkstra anhält, führen die
Implementierungsdetails:
Noch zu klären: Wie findet man effizient einen Knoten u mit kleinstem Wert dist[u]?
Verwalte die Knoten
Dijkstra(G, s) // (Vollversion mit Prioritätswarteschlange)
Eingabe: gewichteter Digraph
for w from 1 to n do
dist[w] = ∞;
inS[w] = false;
p[w] = −1;
dist[s] = 0;
p[s] = −2;
PQ.insert(s);
while not PQ.isempty do
u = PQ.extractMin;
inS[u] = true; // u wird bearbeitet
for Knoten w mit (u, w) ∈ E and not inS[w] do
dd = dist[u] + c(u, w);
if p[w] ≥ 0 and dd < dist[w] then
PQ.decreaseKey(w,dd);
p[w] = u;
dist[w] = dd;
if p[w] = −1 then // w wird soeben entdeckt
dist[w] = dd;
p[w] = u;
PQ.insert(w);
Ausgabe: dist[1..n] und p[1..n].
Aufwandsanalyse:
Die Prioritätswarteschlange realisieren wir als (binären) Heap.
Maximale Anzahl von Einträgen: n.
Initialisierung: Zeit
Der Algorithmus von Dijkstra mit Verwendung einer Prioritätswarteschlange, die als Binärheap realisiert ist, ermittelt kürzeste Wege von Startknoten s aus in einem Digraphen
Resultierende Rechenzeit für Algorithmus von Dijkstra:
Ein Graph G heißt ein freier Baum (oder nur Baum), wenn er zusammenhängend und kreisfrei ist. Kreisfreie Graphen heißen auch (freie) Wälder.
Wenn
- G ist ein Baum.
- G ist kreisfrei und
. - G ist zusammenhängend und
. - Zu jedem Paar u, v von Knoten gibt es genau einen einfachen Weg von u nach v .
- G ist kreisfrei, aber das Hinzufügen einer beliebigen weiteren Kante erzeugt einen Kreis (G ist maximal "kreisfrei“).
- G ist zusammenhängend, aber das Entfernen einer beliebigen Kante erzeugt einen nicht zusammenhängenden Restgraphen ( G ist minimal "zusammenhängend“).
Aus dem Fundamental-Lemma für Bäume folgt, für einen Baum G mit n Knoten:
- G hat
-Kanten. - Wenn man zu G eine Kante
hinzufügt, entsteht genau ein Kreis (aus und dem eindeutigen Weg von u nach w in G). - Wenn man aus G eine Kante (u, w) streicht, zerfällt der Graph in 2 Komponenten (U und W)
Es sei
Es sei
Jeder Kantenmenge E ⊆ E wird durch
S: Menge von Knoten. Enthält die bisher "erreichten“ Knoten. R: Menge von Kanten. Enthält die bisher "gewählten“ Kanten.
- Wähle einen beliebigen (Start-)Knoten
. - Wiederhole
-mal: Wähle eine billigste Kante , die ein mit einem verbindet, d.h. finde und , so dass minimal unter allen Werten , ist. - Ausgabe: R.
Für den Korrektheitsbeweis des Algorithmus von Jarnı́k/Prim: "Cut property“ – Schnitteigenschaft. Eine Partition
Sei
Wir nehmen an, dass
- die Länge der billigsten Kante
falls es eine gibt: in ("Abstand von S“), für Array . - den (einen) Knoten
mit , falls ein solcher existiert: in ("Vorgänger in S“), für Array .
Solange es von S keine Kante nach w gibt, gilt
Eingabe: gewichteter Graph
for w from 1 to n do
dist[w] ← ∞ ; inS[w] ← false; p[w] ← −1 ;
dist[ s ] ← 0 ; p[ s ] ← −2 ; PQ.insert( s );
while not PQ.isempty do
u ← PQ.extractMin; inS[u] ← true;
for Knoten w mit ( u , w ) ∈ E and not inS[w] do
dd ← c( u , w ) ; // einziger Unterschied zu Dijkstra!
if p[w] ≥ 0 and dd < dist[w] then
PQ.decreaseKey(w,dd); p[w] ← u; dist[w] ← dd;
if p[w] = −1 then // w vorher nicht zu S benachbart
dist[w] ← dd; p[w] ← u; PQ.insert(w);
Ausgabe: T = {(w, p[ w ] ) | inS[ w ] = true , w 6 = s} . // Menge der gewählten Kanten
Der Algorithmus von Jarnı́k/Prim mit Verwendung einer Prioritätswarteschlange, die als Binärheap realisiert ist, ermittelt einen minimalen Spannbaum für
Starte mit
Eine offensichtlich korrekte Methode, dies zu organisieren: Durchmustere Kanten in aufsteigender Reihenfolge des Kantengewichts, und nimm eine Kante genau dann in R auf, wenn sie mit R keinen Kreis bildet.
Union-Find-Datenstrukturen dienen als Hilfsstruktur für verschiedene Algorithmen, insbesondere für den Algorithmus von Kruskal. Zwischenkonfiguration im Algorithmus von Kruskal: Menge
Ansatz: Repräsentiere die Knotenmengen, die den Zusammenhangskomponenten von
Eine Partition (In der Mathematik heißt die gesamte Aufteilung Partition, die Teile Klassen) von
Operationen:
-
: Erzeugt zu die diskrete Partition“ mit den n einelementigen Klassen , also . -
: Gibt zu den Namen der Klasse aus, in der sich i (gegenwärtig) befindet. -
: Die Argumente s und t müssen Repräsentanten verschiedener Klassen bzw. sein. Die Operation ersetzt in der Partition und durch die Vereinigung . Als Repräsentant von kann ein beliebiges Element verwendet werden. (Meistens: s oder t.)
Algorithmus von Kruskal mit Union-Find
Input: Gewichteter zusammenhängender Graph
-
Schritt: Sortiere Kanten
nach Gewichten aufsteigend. Resultat: Kantenliste . -
Schritt: Initialisiere Union-Find-Struktur für
. -
Schritt: Für
tue folgendes: -
;$ t ← find(w_i )$; -
then begin ; end; - // Optional: Beende Schleife, wenn
.
-
-
Schritt: Die Ausgabe ist R.
-
Der Algorithmus von Kruskal in der Implementierung mit Union-Find ist korrekt.
-
Die Rechenzeit des Algorithmus ist
, wenn man die Union-Find-Datenstruktur mit Arrays implementiert. -
Die Rechenzeit des Algorithmus ist
, wenn man die Union-Find-Datenstruktur mit mit wurzelgerichteten Bäumen (mit Pfadkompression) implementiert.
Prozedur init(n) // Initialisierung einer Union-Find-Struktur
Erzeuge r, size, next: Arrays der Länge n für int-Einträge
for i from 1 to n do
r[i] = i;
size[i] = 1;
next[i] = 0.
Zeitaufwand:
Prozedur find(i)
return r[i]
Zeitaufwand:
Prozedur union(s, t)
// Ausgangspunkt: s, t sind verschiedene Repräsentanten
if size[s] > size[t] then vertausche s, t; // nun: size[s] ≤ size[t]
z = s;
r[z] = t;
while next[z] 6 = 0 do // durchlaufe L_s , setzt r-Werte um
z = next[z];
r[z] = t;
// nun: z enthält letztes Element von L s ; next[z] = 0
// L s nach dem ersten Eintrag in L t einhängen:
next[z] = next[t]; next[t] = s;
size[t] = size[t] + size[s].
Aufwand:
In der Implementierung der Union-Find-Struktur mit Arrays hat jede find-Operation Rechenzeit
Union-find Prozedur mit Baumimplementierung
j = i ;
jj = p[j];
while jj != j do //verfolge Vorgängerzeiger bis zur Wurzel
j ← jj;
jj ← p[j] ;
return j
Ein
Eine interessante Variante der Union-Find-Datenstruktur, die mit einem wurzelgerichteten Wald implementiert ist, ist der Ansatz der "Pfadkompression“ (oder Pfadverkürzung). Bei einem
Prozedur find (i) // Pfadkompressions-Version
j = i ;
// verfolge Vorgängerzeiger bis zur Wurzel r(i) :
jj = p[j];
while jj != j do
j = jj;
jj = p[j] ;
r = j; // r enthält nun Wurzel r(i)
// Erneuter Lauf zur Wurzel, Vorgängerzeiger umhängen:
j = i ;
jj = p[j];
while jj != j do
p[j] = r;
j = jj;
jj = p[j];
return r
Algorithmenparadigma für Optimierungsprobleme. Typische Schritte:
- Definiere (viele) "Teilprobleme" (einer Instanz)
- Identifiziere einfache Basisfälle
- Formuliere eine Version der Eigenschaft: Substrukturen optimaler Strukturen sind optimal
- Finde Rekursionsgleichungen für Werte optimaler Lösungen: Bellmansche Optimalitätsgleichungen
- Berechne optimale Werte (und Strukturen) iterativ.
Das "APSP-Problem" ist zentrales Beispiel für die Strategie "Dynamische Programmierung“. Kürzeste Wege zwischen allen Paaren von Knoten.
Der im Folgenden beschriebene Algorithmus von Floyd–Warshall kann auch mit negativen Kantengewichten umgehen.
Es gibt keine Kreise mit (strikt) negativer Gesamtlänge, d.h.
- Wenn p Kantenzug von v nach w ist, dann existiert auch ein (einfacher) Weg
von v nach w mit . - Wenn es einen Kantenzug von v nach w gibt, dann auch einen mit minimaler Länge (einen kürzesten Weg“).
Für Digraphen
Bellmansche Optimalitätsgleichungen
Knoten k kommt im Inneren von p entweder einmal oder gar nicht vor.
- Falls k in p nicht vorkommt, ist p kürzester
-Weg von v nach w - Falls k im Inneren von p vorkommt, zerfällt p in zwei Teile die beide kürzeste
-Wege sind. Die Bellmanschen Optimalitätsgleichungen für den Algorithmus von Floyd-Warshall lauten dann: , für
S[v,v,0] = 0;
S[v,w,0] = c(v, w);
for k from 1 to n do
for v from 1 to n do
for w from 1 to n do
S[v,w,k] = min{ S[v,w,k-1] , S[v,k,k-1] + S[k,w,k-1] }
Algorithmus Floyd-Warshall(C[ 1 .. n , 1 .. n ]) Eingabe: C[ 1 .. n , 1 .. n ]: Matrix der Kantenkosten/-längen c(v, w) in R ∪ {+∞} Ausgabe: S[ 1 .. n , 1 .. n ]: Kosten S(v, w) eines kürzesten v - w -Weges I[ 1 .. n , 1 .. n ]: minimaler maximaler Knoten auf einem kürzesten v - w -Weg
for v from 1 to n do
for w from 1 to n do
if v = w then S[v,v] ← 0 ; I[v,v] ← 0
else S[v,w] ← C[v,w];
if S[v,w] < ∞ then I[v,w] ← 0 else I[v,w] ← −1 ;
for k from 1 to n do
for v from 1 to n do
for w from 1 to n do
if S[v,k] + S[k,w] < S[v,w] then
S[v,w] ← S[v,k] + S[k,w]; I[v,w] ← k;
Ausgabe: S[ 1 .. n , 1 .. n ] und I[ 1 .. n , 1 .. n ].
Der Algorithmus von Floyd-Warshall löst das All-Pairs-Shortest-Paths-Problem in Rechenzeit
Zweck: Kürzeste Wege von einem Startknoten s aus in gewichtetem Digraphen
Grundoperation, schon aus dem Dijkstra-Algorithmus bekannt:
update(u, v) // für (u, v) ∈ E
if dist[u] + c(u, v) < dist[v] then
p[v] ← u;
dist[v] ← dist[u] + c(u, v) ;
Algorithmus Bellman-Ford(
- In
: Abstand ; - In
: Baum von kürzesten Wegen (wie bei Dijkstra);
Initialisierung:
for v from 1 to n do
dist[v] ← ∞ ; p[v] ← −1 ;
dist[ s ] ← 0 ; p[ s ] ← −2 ; // wird nie geändert, wenn kein negativer Kreis existiert
Hauptschleife:
for i from 1 to n − 1 do // heißt nur: wiederhole (n − 1) -mal
forall (u, v) ∈ E do update (u, v) ; // beliebige Reihenfolge
Zyklentest:
forall (u, v) ∈ E do
if dist[ u ] + c(u, v) < dist[ v ] then return "negativer Kreis";
Ergebnis:
return dist[ 1 .. n ], p[ 1 .. n ]
Der Bellman-Ford-Algorithmus hat folgendes Verhalten:
- Wenn es keinen von s aus erreichbaren Kreis mit negativer Gesamtlänge gibt ("negativer Kreis"), steht am Ende des Algorithmus in dist[v] die Länge eines kürzesten Weges von s nach v, und die Kanten
(mit p[w] > 0) bilden einen Baum der kürzesten Wege von s aus zu den erreichbaren Knoten. - Der Algorithmus gibt "negativer Kreis“ aus genau dann wenn es einen von s aus erreichbaren negativen Kreis gibt.
- Die Rechenzeit ist
Problemstellung: Sei A ein Alphabet. (Bsp.: Lat. Alphabet, ASCII-Alphabet, { A,C,G,T } .)
Wenn
- Lösche einen Buchstaben aus einem String: Aus uav wird uv (
). Beispiel: Haut → Hut. - Füge einen Buchstaben in einen String ein: Aus uv wird uav (
). Beispiel: Hut → Haut. - Ersetze einen Buchstaben: Aus uav wird ubv (
). Beispiel: Haut → Hast. Der "Abstand" oder die Editierdistanz von x und y ist die minimale Anzahl von Editieroperationen, die benötigt werden, um x in y zu transformieren.
Man schreibt Strings aus Buchstaben und dem Sonderzeichen - untereinander, wobei die beiden Zeilen jeweils das Wort x bzw. y ergeben, wenn man die -’s ignoriert. Die Kosten einer solchen Anordnung: Die Anzahl der Positionen, an denen die oberen und unteren Einträge nicht übereinstimmen. Die Kosten, die eine solche Anordnung erzeugt, sind gleich der Anzahl der Editierschritte in einer Transformation.
Das Problem "Editierdistanz" wird folgendermaßen beschrieben:
Input: Strings
- Schritt: Relevante Teilprobleme identifizieren! Betrachte Präfixe
und , und setze , für
Die Zahlen E(i, j) berechnen wir iterativ, indem wir sie in eine Matrix
for i from 1 to m do
for j from 1 to n do
E[i,j] = min{E[i-1,j-1] + diff(a_i, b_j), E[i-1,j] + 1, E[i,j-1] + 1};
return E[m,n]
Rechenzeit:
Multiplikation von zwei Matrizen über einem Ring R: Gegeben
Die Matrizenmultiplikation ist assoziativ. Gesucht wird eine ("optimale") Klammerung, die bei der Berechnung von
Optimale Klammerung für
MatrixOptimal($(r_0, . . . , r_k )$)
Eingabe: Dimensionsvektor
-
enthält -
enthält Index zur Unterteilung der Multiplikation bei
for i from 1 to k
do C[i,i] = 0;
for i from 1 to k−1
do C[i,i+1] = r_i − 1 * r_i * r_i + 1;
for d from 2 to k−1 do
for i from 1 to k − d do
bestimme das l, i ≤ l < i+d, das C=C[i,l]+ C[l+1,i+d] + r_{i-1}*r_l*r_{i+d} minimiert;
l[i,i+d] = dieses l;
C[i,i+d] = das minimale C;
Ausgabe: C[1..k, 1..k] und l[1..k, 1..k]
Laufzeit: Die Minimumssuche in Zeilen (5)–(6) kostet Zeit
Prüfungsstoff: Vorlesung + Übungsaufgaben. Prüfungsklausur: 150 Minuten, 150 Punkte. max. 15 Bonuspunkte über Zwischenklausur (40 Minuten)
-
1. Vorbereitung
- 1.1. O-Notation
- 1.2. Spezifkationstechnik für Datentypen
- 1.3. Implementierungen fundamentaler Datentypen
- 1.4. Auswahlkriterien für elementare Datenstrukturen kennen und anwenden
- 1.5. Kenntnis grundlegender Entwurfsstrategien
- 1.6. Kenntnis grundlegender Algorithmen und ihrer Eigenschaften
- 1.7. Auswahlkriterien für Algorithmen, insbesondere Ressourcenverbrauch, kennen und anwenden
- 1.8. Standard-Analysemethoden für Ressourcenverbrauch (Rechenzeit, Speicherplatz)
- 1.9. Korrektheitsbeweise für Algorithmen verstehen und darstellen
-
2. Einführung und Grundlagen
- 2.1. Beispiel: Sortieren
- 2.2. Was ist ein Algorithmus
- 2.3. Merkmale eines Algorithmus
- 2.4. Erweiterung des Algorithmusbegriffs
- 3. Fundamentale Datentypen und Datenstrukturen
- 4. Binärbaume
- 5. Hashverfahren
- 6. Sortierverfahren
- 7. Graphen, Digraphen und Breitensuche
- 8. Tiefensuche
- 9. Divide-and-Conquer-Algorithmen
- 10. Greedy-Algorithmen: Prinzipien
- 11. Greedy-Algorithmen für Graphprobleme
- 12. Dynamische Programmierung
- 13. Prüfung