Benutzer-Werkzeuge

Webseiten-Werkzeuge


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
      • 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

Binärbä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.
  • 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.

Lineare Rekursion

  • eine Funktion heißt rekursiv, wenn sie sich selbst oder ein von ihr aufgerufenes Programm sie selbst wieder aufruft
  • Rekursion ist eine Wiederholung durch Schachtelung → Schachtelmodell
  • 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

ToDo

  • Wichtige Bereiche im Skript mit Klebi kennzeichnen


se/algorithmendatenstrukturen.1231952615.txt.gz · Zuletzt geändert: 2014-04-05 11:42 (Externe Bearbeitung)