Prüfungsstoff für die Vorlesung
"Algorithmen und Datenstrukturen"
Fibonacci-Zahlen
- rekursive Berechnung
- iterative Berechnung
- iteriertes Quadrieren
Algorithmen
- Eigenschaften
- Darstellung
Turing-Maschinen
- Maschinenmodell
- Programmiersprache
- Turing'sche These
- Halteproblem
Sortieren durch Einfügen
Landau-Symbole
Maximum-Subarray-Problem
- Lösungsmethoden
- Laufzeit-Berechnung
Rekursionsgleichungen
- iterative Einsetzungsmethode
- Iterationsmethode
- Mastertheorem
Abstrakte Datentypen
- Motivation
- Beschreibungsmöglichkeiten
Stacks
- Definition
- Implementierung, Laufzeiten
Queues
- Definition
- Implementierung, Laufzeiten
Lineare Listen
- Definition
- sequentielle Speicherung
- Aufwand pro Operation bei sequentieller Speicherung
- verkettete Speicherung
- Aufwand pro Operation bei verketteter Speicherung
Amortisationsanalyse
- prinzipielle Idee
- Beispiel
Selectionsort
- Laufzeit, Anzahl Vergleiche
- Anzahl Bewegungen im Array
Bubblesort
- Laufzeit, gute und schlechte Eingaben, Anzahl Vergleiche
- durchschnittliche Laufzeit
- Anzahl Bewegungen im Array
Heapsort
- Heap-Bedingung
- Funktion heapify, Laufzeit
- Heaps und Binärbäume
- Funktion buildHeap, Laufzeit
- Variante von Carlsson
- Bottom-Up-Heapsort
- Vor- und Nachteile
Quicksort
- Ablauf
- beste, schlechteste, durchschnittliche Laufzeit
- Varianten
- Rekursionstiefe
- nichtrekursive Implementierung
- Vor- und Nachteile
Mergesort
- Ablauf
- Laufzeit
- nichtrekursive Implementierung
- Vor- und Nachteile
Untere Schranken für vergleichsbasierte Sortierverfahren
- Inversionszahl, Eigenschaften
- Entscheidungsbaum, Beweis
Sortieren ohne Schlüsselvergleiche
- Countingsort
- Radixsort
- Bucketsort
In-situ-Sortierverfahren
- Definition
- Beispiele, Gegenbeispiele
Stabile Sortierverfahren
- Definition
- Beispiele, Gegenbeispiele
Sortiernetzwerke
- Definition
- Netzwerk für Insertionsort
Externe Sortierverfahren
Prioritätswarteschlangen
- Definition
- Realisierung mit Heaps, Laufzeiten
Verwaltung disjunkter Mengen
- Implementierung mit Listen, Laufzeiten
- Implementierung mit Bäumen, Laufzeiten
- Pfadkompression
Medianproblem
- linearer Algorithmus
- Herleitung der Laufzeit
Suchen in linaren Listen
- sequentielle Suche
- binäre Suche
- exponentielle Suche
- Interpolationssuche
Allgemeine binäre Suchbäume
- Definition
- Abstrakter Datentyp Wörterbuch
- Laufzeit und Realisierung der Operationen
Rot-Schwarz-Bäume
- Definition
- Beweis der logarithmischen Höhe
- Rotationen
- Laufzeit für Einfügen und Löschen
Hashing
- Idee
- Häufigkeit von Kollisionen
- Typen von Hashfunktionen
- Universelle Hashklassen
- Hashing mit Verkettung, separate und direkte Verkettung
- mittlere Zeit für erfolgloses bzw. erfolgreiches Suchen
- offene Hashverfahren, Varianten
Elementare Graphen-Algorithmen
- Speicherung von Graphen
- Breadth-First-Search, Laufzeit, Eigenschaften
- Depth-First-Search, Laufzeit, Eigenschaften
Minimale aufspannende Bäume
- Problemdefinition
- prinzipieller algorithmischer Ansatz
- Algorithmus von Prim, effiziente Implementierung, Laufzeit
- Algorithmus von Kruskal, effiziente Implementierung, Laufzeit
Krzeste Wege
- Problemdefinition
- prinzipieller algorithmischer Ansatz
- Algorithmus von Dijkstra, effiziente Implementierung, Laufzeit
Suchen von Wörtern in Texten
- Endlicher-Automat-Algorithmus, Idee, Laufzeit
- Algorithmus von Knuth-Morris-Pratt, Idee, Laufzeit
- Algorithmus von Boyer-Moore, Idee, Laufzeit
Erkennung von Textmustern
- Nichtdeterministischer endlicher Automat
- Simulation eines NDEA, Laufzeit der Mustererkennung
Tries
- Idee, Radix-Trie, Indexed-Trie, Packed-Trie
Komplexität
- Entscheidungsprobleme, Klasse P, polynomiale Reduktion
- Nichtdeterministische Turing-Maschine
- Klasse NP, NP-Vollständigkeit
- Anwendung der Konzepte auf Optimierungsprobleme, NP-schwer
|
