Grundgebiete der Informatik
1. Semester Wirt. Ing. RWTH AACHEN
1. Semester Wirt. Ing. RWTH AACHEN
-
- 1 / 121
-
Cartes-fiches
Laufzeit von Quicksort
O(N log N)
Erkläre Heapsort
Verbesserter Selection Sort. Man verwendet einen Heap und vertauscht das Minimun immer mit der richtigen Stelle.
Definiere (Minimums-) Heap
Gelten im Array A[1...N] für jedes A[i] die Eigenschaften A[i] \(\le\) A[2i] (falls 2i \(\le\) N) und A[i] \(\le\) A[2i+1] (falls 2i+1 \(\le\) N), so ist A ein (Minimums-)Heap
Wie ist die Laufzeit des Heapsort?
O(N log N) -> worst case
Definiere verkettete Liste
Eine (verkettete) Liste ist entweder leer oder besteht aus einer Referenz auf einen Knoten, der sein Element und eine Referenz auf eine verkettete Liste enthält.
Definiere Stack
Ein Stack (Stapel) ist ein ADT, der folgende Grundoperationen unterstützt:
1. Einfügen eines neuen Elementes ("Push")
2. Entfernen des zuletzt eingefügten Elementes ("pop")
Definiere Queue
Eine Queue (Warteschlange) ist ein ADT, der folgende Grundoperationen unterstützt:
1. Einfügen eines neuen Elements ("Put")
2. Entfernen des zuerst eingefügten Elements ("Get")
Definiere Baum
Ein Baum besteht aus einem ausgezeichneten Knoten r (Wurzel) und k\(\geq\) 0 disjunkten Bäumen T1,..,Tk
Definiere Binärbaum
Ein Binärbaum B=(r, BL, BR) ist entweder leer oder besteht aus einer Wurzel r sowie einem linken und rechten Teilbaum BL und BR
Nenne die drei Baum Durchlaufschemata
Inorder, Preorder, Postorder
Definiere Suchbaum
Sei B=(r, BL, BR) ein Binärbaum und bezeichne key(n) den Suchschlüssel für jeden Knoten n. B heißt Suchbaum, falls gilt:
1. Für alle n \(\in\) BL: key(n) < key (r)
2. Für alle n \(\in\) BR: key(n) > key(r)
3. BL und BR sind Suchbäume
Laufzeit eines Suchbaums
O(log N) -> average case
O(N) -> worst case
Definiere gerichteter Graph
Ein (gerichteter) Graph G=(V,E) besteht aus einer Menge V von Knoten (vertices) und einer Menge E von Kanten (edges) mit E \(\subseteq\) V X V
Definiere ungerichtet (Graph)
Gilt für alle Kanten (u,v) eines Graphen G=(V,E)
(u,v) \(\in\) E => (v,u) \(\in\) E so heißt G ungerichtet.
Schreibweise: {u,v} \(\in\) E
Definiere Pfad
Eine Folge (v1,...,vn) von Knoten eines Graphen G=(V,E) heißt Pfad, falls für alle i=1...n+1: {vi,vi+1} \(\in\) E
Definiere zusammenhängend (Graph)
Ein Graph G=(V,E) heißt zusammenhängend, falls zwischen zwei beliebigen Knoten u,v \(\in\) V mindestens ein Pfad existiert.
Definiere zyklenfrei (Graph)
Ein Graph G = (V,E) heißt zyklenfrei, falls zwischen zwei beliebigen Knoten u,v \(\in\) V höchstens ein Pfad existiert.
Definiere Baum (Graph)
Ein zusammenhängender, zyklenfreier Graph G=(V,E) heißt Baum.
Definiere kantengewichteter Graph
Ein Graph G=(V,E,w) mit einer Abbildung w: E -> R heißt kantengewichteter Graph
Erkläre den Dijkstra-Algorithmus
findet alle kürzesten Pfade von einem Startknoten aus gesehen auf einmal.
Definiere Vorgänger und Nachfolger (Graph)
Ist G=(V,E) ein Graph und {uv,} \(\in\) E, so heißt v Nachfolger von u und u heißt Vorgänger von v
Wie ist die Laufzeit des Dijkstra Algorithmus?
O(|V|²)
Definiere Adjazenzmatrix
Ist G=(V,E) ein Graph mit Knotenmenge V={v1,..,vn}, so heißt die (n X n)Matrix A= (aij) mit aij=1, falls {vi, vj} \(\in\) E aij=0, sonst
Adjazenzmatrix zu G
Erkläre Adjazenzlisten
Bei dieser Datenstruktur werden nur die Graphenkanten explizit abgespeichert. Jeder Knoten besitzt eine Liste seiner Nachbarn.
-> Bei wenigen Kanten platzsparend
Wie ist der Platzbedarf bei Adjazenzlisten?
O(|V| + |E|)
Erkläre garbage collection
Es werden alle Speicherblöcke als "nicht mehr benötigt" markiert. Ist ein Block über einen Zeiger erreichbar wird er als "benötigt" markiert. Alle übrigen können freigegeben werden.
Erkläre Depth first search
ausgehend vom Startknoten möglichst lange Pfade verfolgen
Erkläre Breadth first search
ausgehend vom Startknoten weitere Knoten in der Reihenfolge wachsenden Abstands vom Startknoten besuchen
Definiere Spannbaum
Ein Spannbaum in einem ungerichteten, zusammenhängenden und kantengewichteten Graphen G=(V,E,w) ist ein zyklenfreier, zusammenhängender Teilgraph G'=(V',E',w) mit V' = V und E' \(\subseteq\) E
Definiere minimaler Spannbaum
Ein minimaler Spannbaum in einem ungerichteten, zusammenhängenden und kantengewichteten Graphen G=(V,E,w) ist ein Spannbaum mit minimaler Kantengewichtssumme unter allen Spannbäumen zu G
Erkläre den Kruskal Algorithmus
Der Kruskal Algorithmus ist ein greedy Algorithmus. Er betrachtet stets die nächste Kanten mit dem geringsten Gewicht.
Wie ist die Laufzeit des Kruskal Algorithmus?
O(|E| log |E|)
Erkläre Iteration
- Berechnung einer Funktion f durch einzelne Schritte auf bestimmter Datenstruktur
- Typischerweise als Schleife realisiert
- Vor- und Nachteile wie Rekursion
Wie hoch ist die Laufzeit der Berechnung der Fibonacci Zahlen bei Rekursion?
O(2^n) -> exponentielles Wachstum
Wie hoch ist die Laufzeit der Berechnung der Fibonacci Zahlen bei Iteration?
O(N)
Erkläre Backtracking
- Rücksetzverfahren
- Teillösungen führen zur Gesamtlösung
- Raten und korrigieren
Erkläre Kombinatorische Optimierung
Konstruktion einer Lösung eines Problems durch Auswahl einer Teilmenge einer Menge von diskreten Elementen
Erkläre Heuristik
Kompromis zwischen Laufzeit und Qualität der Lösung
Erkläre Approximationsalgorithmen
Bei Approximationsalgorithmen gibt es keine Ausreißer, denn man kann nachweisen, dass eine bestimmte Güte nie unterschritten wird
Erkläre Dynamische Programmierung
Effizientes exaktes Lösen von Optimierungsproblemen mit folgender Eigenschaft:
Die opt. Lösung des Gesamtproblems kann effizient aus opt. Lösungen von Teilproblemen berechnet werden
