se:algorithmendatenstrukturen
**Dies ist eine alte Version des Dokuments!**
Algorithmen und Datenstrukturen
Algorithmen
Game of life
Geburtstagsproblem
MinMax, AlphaBeta
* Syntaxbaum erstellen
* 8-Damen-Problem
* Sortieralgorithmen
* Bubblesort, Insertsort, Mergesort, Quicksort (+ randomisiert), Median-of-three, Heapsort
* Datenstrukturen
Verkettete Listen
Stack
Queue
Dequeue
Binäre Bäume
Sonstiges
Pipes auf der Bash
Sierpinski-Sieb (Huhn)
O-Notation
Klausur
Umwandlung Postfix/Infix
Lineare Rekursion
* Traversierung von Bäumen
Binärbäume
Komplexität von Algorithmen bestimmen, Laufzeitanalyse (quadratisch, kubisch etc.)
Codeoptimierung
Arrays mit Quicksort sortieren (C: qsort)
Heapsort, Countingsort, Radixsort
Backtracking (Was gibt vorgegebenes Programm aus?)
Postfix / Infix
mathematische Ausdrücke werden ublicherweise in der so genannten Infix-Schreibweise geschrieben:
(4 + 5) * (3 - 1) / 9
man kann solche Ausdrücke aber auch in der so genannten umgekehrten polnischen Notation angeben:
4 5 + 3 1 - * 9 /
Vorteile
keine Berücksichtigung von Prioritäten der Operatoren nötig, es werden keine Klammern benötigt
* kann leicht mit Hilfe eines Stacks implementiert werden
* Umwandlung Infix → Postfix (alle Ausdrücke müssen geklammert sein)
Ausdruck von links nach rechts durchgehen
Zahlen direkt ausgeben
Operatoren auf den Stack legen
bei schließender Klammer den obersten Operator ausgeben
Bäume
Ein Baum ist eine nicht-leere Menge von Knoten und Kanten, die gewisse Bedingungen erfüllen.
Ein Knoten ist ein Objekt, das einen Namen haben und weitere Informationen beinhalten kann.
Eine Kante ist eine Verbindung zwischen zwei Knoten.
Ein Pfad ist eine Folge von unterschiedlichen Knoten, die durch Kanten im Baum miteinander verbunden sind.
Die Wurzel eines Baums ist ein besonderer Knoten, der den Ursprung des Baums kennzeichnet. Es gilt immer, dass es zwischen der Wurzel und jedem beliebigen anderen Knoten eines Baums genau einen Pfad gibt.
Jeder Knoten (außer der Wurzel) hat genau einen Vorgänger, der sich direkt über ihm befindet und als sein direkter Vorgänger (parent) bezeichnet wird. Knoten, die sich direkt unter einem Knoten befinden, werden als seine direkten Nachfolger (children) bezeichnet.
Entsprechend eines Familienstammbaums spricht man auch von einem Großelterknoten oder von Geschwisterknoten.
Blätter, Endknoten und äußere Knoten sind Knoten ohne Nachfolger.
Innere Knoten sind Knoten mit mindestens einem Nachfolger.
Jeder Knoten ist die Wurzel eines Unterbaums, der aus ihm und den Knoten unter ihm besteht.
Die Ebene eines Knotens ist die Anzahl der Knoten auf dem Pfad von diesem Knoten zur Wurzel, wobei der Knoten selbst nicht mitgezählt wird und die Höhe eines Baums ist seine höchste Ebenennummer. Die Pfadlänge eines Baums ist die Summe der Ebenen aller Knoten.
Ein Wald ist ein Menge von Bäumen.
Geordnete Bäume sind Bäume, bei denen die Reihenfolge der direkten Nachfolger bei jedem Knoten festgelegt ist. Ist diese Reihenfolge nicht fest vorgeschrieben, spricht man von ungeordneten Bäumen.
Falls jeder Knoten nur eine bestimmte Anzahl n von direkten Nachfolgern haben darf, die in einer bestimmten Reihenfolge vorliegen müssen, spricht man von einem n-ären Baum.
Binärbäume
Der einfachste Typ eines n-ären Baums ist der binäre Baum, für den Folgendes gilt:
Es ist ein geordneter Baum mit zwei Typen von Knoten: inneren und äußeren Knoten. Innere Knoten haben immer maximal zwei direkte geordnete Nachfolger, die man auch als linker und rechter Nachfolger bezeichnet. Äußere Knoten sind Knoten ohne Nachfolger.
Ein binärer Baum ist leer, wenn er nur aus einem äußeren Knoten besteht und keinen inneren Knoten besitzt.
Ein voller binärer Baum ist ein binärer Baum, in dem sich in keiner Ebene, außer in der vorletzten, äußere Knoten befinden.
Ein vollständiger binärer Baum ist ein voller binärer Baum, bei dem sich in der letzten Ebene nur äußere Knoten befinden.
Für zwei Knoten in einem binären Baum gibt es immer nur genau einen Pfad, der sie verbindet.
Ein binärer Baum mit n inneren Knoten hat n+1 äußere Knoten.
Die äußere Pfadlänge eines binären Baums mit n inneren Knoten ist immer um 2n größer als die innere Pfadlänge.
Ein Baum mit n Knoten hat immer n-1 Kanten.
Die Höhe eines vollen binären Baums mit n inneren Knoten ist die nächste ganze Zahl zu log2(n).
Binärbäume vereinen die Vorteile von Arrays (schneller Zugriff auf ein Element) mit den Vorteilen von Listen (leichtes Einfügen/Löschen eines Elements).
Sie lassen sich am Besten mittels Rekursion verwalten.
nicht-binäre Bäume können einfach als binäre Bäume implementiert werden, indem jeder Knoten zwei Zeiger bekommt: einen auf sein erstes Kind (verkettete Liste aller Kinder) und einen auf seinen nächsten Geschwisterknoten
in balancierten Binärbäumen haben alle Knoten in etwa die gleiche Tiefe: bei n Knoten ist die Höhe log2(n+1)
bei einem balancierten Binärbaum sind somit maximal log2(n+1) Vergleiche (=Höhe des Binärbaums) notwendig, um ein Element in einem solchen balancierten Binärbaum zu finden
Heap
ein Heap ist ein Binärbaum, in dem alle Knoten Werte besitzen, die größer (oder gleich) sind als alle Werte ihrer Kindknoten
der größte Wert befindet sich somit im Wurzelknoten
Darstellung als Array: [0] = Wurzel, [1] und [2] 1. Ebene, [3], [4], [5], [6] 2. Ebene etc.
se/algorithmendatenstrukturen.1232219534.txt.gz · Zuletzt geändert: 2014-04-05 11:42 (Externe Bearbeitung)