- Titel: Rautavistische Algorithmen und Datenstrukturen
- Organisation: UNI ESCHWEILERHOF
- Seitenzahl: 37
Inhalt
- Rautavistische Algorithmen und Datenstrukturen
- Harald Schiöberg Technische Universität München
- Graphenalgorithmen und Berechenbarkeitstheorie DEGGraphen als Turingmaschinenzustandsübergangsgraphen Universelle Graphenalgorithmen
- Bäume Klassische Bäume Satz der winterunendlichen Bäume GelbGrünBäume
- Hashing Schnelle WriteOperationen Platzsparendes Hashing
- Kryptographie Verteilung von Geheimnissen
- Sortieren und klassische Methoden
- KAPITEL SORTIEREN UND KLASSISCHE METHODEN
- Vorzeitigen Abbruch verhindern
- VERGLEICHSBASIERTES SORTIEREN IN LINEARER ZEIT
- Vergleichsbasiertes Sortieren in linearer Zeit
- Satz Die Laufzeit von MergeSort beträgt On logn
- was offensichtlich in On log n liegt
- also eine lineare Laufzeit für vergleichsbasiertes Sortieren
- Graphenalgorithmen und Berechenbarkeitstheorie
- DEGGraphen als Turingmaschinenzustandsübergangsgraphen
- KAPITEL GRAPHENALGORITHMEN UND BERECHENBARKEITSTHEORIE
- Kopfbewegung geschriebenes Zeichen gelesenes Zeichen
- Abbildung Unser Ausgangsgraph
- Abbildung Herstellung des starken Zusammenhangs
- Abbildung Anwendung der RBedingung
- Abbildung Nochmalige Anwendung der RBedingung
- Abbildung Das Endresultat Ein DEGGraph
- Abbildung Ein typischer DEGGraph
- Abbildung Ein komplexer DEGGraph
- b ist sommergrün
- KAPITEL BÄUME
- Eichen und Buchen sind sich denitionsgemäß recht ähnlich
- Denition Ein Baum E heißt Eiche wenn gilt
- max Alter ist sommergrün
- Pr ist immergrün
- h wertvolles Nutzholz
- wobei für E gilt dass
- SATZ DER WINTERUNENDLICHEN BÄUME
- Satz der winterunendlichen Bäume
- zu hashende Werte x x x x
- Hashfunktion Hashtabelle x x x x
- Abbildung Rautavistisches Hashing verursacht keine Kollisionen
- Verteilung von Geheimnissen
- Der Angreifer wusste das
- neue Recht Schreibung sieht irgendwie doof aus
- Wiederholung von Grundlagen
- Die Komplexitätsklasse NN
- KAPITEL KOMPLE ITÄTSTHEORIE
- Die Klasse NN und die Komplexitätshierarchie
- DIE KLASSE NN UND DIE KOMPLE ITÄTSHIERARCHIE
- Tabelle Übersicht über Verschiedene Komplexitätsklassen
- Par Ray Sed Sip Wik
Vorschau
Rautavistische Algorithmen und Datenstrukturen
Nils Kammenhuber, Rautavistische Universität Eschweilerhof und Technische Universität München Sebastian Marius Kirsch, Rautavistische Universität Eschweilerhof 8. Juli 2005
¦ 5 2 0 ¦ ( # ¦ ‘ ¦ % # ¨ ¦ ¨ ¦ £ £ ¡ 76431))§&¢¥$¥”!¥¥¥¥©§¥¤¢
Harald Schiöberg, Technische Universität München
2
Inhaltsverzeichnis
Das Inhaltsverzeichnis, das Sie gerade lesen 1 Sortieren und klassische Methoden 1.1 1.2 1.3 2 Elementare Sortieralgorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . . Laufzeitpessimierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Vergleichsbasiertes Sortieren in linearer eit . . . . . . . . . . . . . . . . . . . . 3 5 5 7 11 15 15 15 15 15 17 17 19 23 23 25 25 27 27 28 29 29
Rekursion 2.1 2.2 2.3 2.4 Die Abbruchbedingung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Verschränkte Rekursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Einfache Rekursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Verschränkte Rekursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Graphenalgorithmen und Berechenbarkeitstheorie 3.1 3.2 DEG-Graphen als Turingmaschinenzustandsübergangsgraphen . . . . . . . . Universelle Graphenalgorithmen . . . . . . . . . . . . . . . . . . . . . . . . . .
Bäume 4.1 4.2 4.3 Klassische Bäume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Satz der winterunendlichen Bäume . . . . . . . . . . . . . . . . . . . . . . . . . Gelb-Grün-Bäume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Hashing 5.1 5.2 Schnelle Write-Operationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Platzsparendes Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .