Benutzer-Werkzeuge
se:algorithmendatenstrukturen
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
|
se:algorithmendatenstrukturen [2009-01-11 17:51] stefan |
se:algorithmendatenstrukturen [2014-04-05 11:42] |
||
|---|---|---|---|
| Zeile 1: | Zeile 1: | ||
| - | ====== 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 | ||
| - | * umgekehrte polnische Notation | ||
| - | * 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: <code>(4 + 5) * (3 - 1) / 9</code> | ||
| - | * man kann solche Ausdrücke aber auch in der so genannten umgekehrten polnischen Notation angeben: <code>4 5 + 3 1 - * 9 /</code> | ||
| - | * 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 | ||
| - | |||
| - | ===== Lineare Rekursion ===== | ||
| - | * eine Funktion heißt rekursiv, wenn sie sich selbst oder ein von ihr aufgerufenes Programm sie selbst wieder aufruft | ||
| - | * jede Rekursion kann durch entsprechende Wiederholungen ausgedrückt werden und umgekehrt | ||
| - | * Beispiele für Anwendung von Rekursion | ||
| - | * Quadratzahlen: ''n<sup>2</sup> = (n - 1)<sup>2</sup> + 2n - 1'' | ||
| - | * größter gemeinsamer Teiler: ''ggT(n, m) = 0, wenn m = 0, sonst ggT(m, n mod m)'' | ||
| - | * Dreieckszahlen: ''(k * (k + 1)) / 2'' | ||
| - | * Umwandlung von Dezimal- in Dualzahl: ''bis zahl = 0: rest = zahl % 2, zahl = zahl / 2; Reste umgekehrt ausgeben''' | ||
| - | * wenn eine Funktion sich mehrmals aufruft erhält man eine nicht-lineare Rekursion in Baumstruktur | ||
| - | * Fibonacci-Zahlen: ''F(0) = 1; F(1) = 1; F(n) = F(n - 2) + F(n - 1)'' | ||
| - | * Binomialkoeffizient: ''n über k = 1, wenn n oder k = 0, sonst (n - 1 über k) + (n - 1 über k - 1)'' | ||
| - | * Pascal'sches Dreieck | ||
se/algorithmendatenstrukturen.txt · Zuletzt geändert: 2014-04-05 11:42 (Externe Bearbeitung)
Seiten-Werkzeuge
Falls nicht anders bezeichnet, ist der Inhalt dieses Wikis unter der folgenden Lizenz veröffentlicht: CC Attribution-Noncommercial-Share Alike 4.0 International
