Benutzer-Werkzeuge
se:algorithmendatenstrukturen
**Dies ist eine alte Version des Dokuments!**
Inhaltsverzeichnis
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:
(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
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:
n2 = (n - 1)2 + 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.1231692688.txt.gz · 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
