Kurs:Algorithmen und Datenstrukturen/Funktionale Algorithmen

Startseite

Vorlesung

1.Einleitung

2. Theoretische Grundlagen

2.1 Programmierparadigmen

2.2. Laufzeitanalysen

2.3. Entwurfsmuster

3. Suchen

3.1 Suchen in sortierten Folgen

3.2 Suchen in Texten

4. Sortieren

4.1 Algorithmen für vergleichsbasiertes Sortieren

4.2 Weitere Sortierprobleme

5. Dynamische Datenstrukturen

5.1 Binäre Suchbäume

5.2 AVL Bäume

5.3 2-3-4-Bäume und Rot-Schwarz Bäume

5.4 Heaps

5.5 Hashtabellen

6. Graphen

6.1 Einführung

6.2 Breitensuche

6.3 Tiefensuche

6.4 Topologisches Sortieren

6.5 Berechnung kürzester Wege

6.6 Berechnung maximaler Flüsse

6.7 Spannbäume

7. Optimierung

7.1 Grundlagen

7.2 Kombinatorische Optimierung

7.4 Lineare Optimierung

7.5 Simplex Verfahren

Inhalte Einleitung Begriffserklärungen Eigenschaften von Algorithmen Algorithmenentwurf Größter gemeinsamer Teiler Berechenbarkeit Theoretische Grundlagen Programmierparadigmen Überblick Paradigmenbegriff Funktionale Algorithmen Grundidee Funktionsdefinition und Signatur Auswertung von Funktionen Auswertung von rekursiven Funktionen Fakultät Größter gemeinsamer Teiler Fibonacci-Zahlen Weiteres Beispiel Logische Algorithmen Einführung Prädikatenlogik&Hornlogik Prolog Listen Imperative Algorithmen Einführung Variablen Zustände Ausdrücke Anweisungen Syntax und Semantik Fakultätsfunktion Funktional vs. Imperativ Fibonacci-Zahlen Größter gemeinsamer Teiler Laufzeitanalysen Komplexität Notationen O-Notation Omega-Notation Theta-Notation Eigenschaften Komplexitätsklassen Aufwandsanalyse von iterativen Algorithmen Aufwandsanalyse von rekursiven Algorithmen Vollständige Induktion Mastertheorem Rekursionsbäume Entwurfsmuster Entwurfsprinzipien Greedyalgorithmen Wechselgeldalgorithmus Divide and Conquer Backtracking Dynamische Programmierung Suchen Suchen in sortierten Folgen Einleitung Sequentielle Suche Binäre Suche Fibonacci Suche Suchen in Texten Einleitung Naiver Algorithmus zur Textsuche Knuth-Morris-Path Sortieren Algorithmen für vergleichsbasiertes Sortieren Grundlagen InsertionSort SelectionSort BubbleSort MergeSort Zwischenbemerkungen QuickSort Untere Schranke Weitere Sortierprobleme Rückblick und Ausblick Nicht-Vergleichsbasiertes-Sortieren: Bucket Sort Verteiltes Sortieren: Batcher Sort Dynamische Datenstrukturen Binäre Suchbäume Einleitung Einschub Bäume und Traversierung Binäre Suchbäume Suchen Einfügen Löschen Implementierung Weitere Aspekte AVL-Bäume 2-3-4-Bäume und Rot-Schwarz-Bäume Heaps Hashtabellen AVL-Bäume AVL-Bäume 2-3-4-Bäume und Rot-Schwarz-Bäume 2-3-4-Bäume Rot-Schwarz-Bäume Heaps Heap Sort Vorgehensweise Analyse Hashtabellen Hashtabellen Kollisionsstrategie Aufwand Dynamische Hashverfahren Hashen in Java Graphen Einführung Typen von Graphen Definitionen zu Graphen Repräsentation von Graphen Datenstrukturen für Graphen Breitendurchlauf Breitensuche Tiefendurchlauf Tiefensuche Topologisches Sortieren Topologisches Sortieren Berechnung kürzester Wege Einleitung Der Algorithmus von Dijkstra Der Algorithmus von Bellmann-Ford Der Algorithmus von Floyd-Warshall Das Traveling Salesman Problem Berechnung maximaler Flüsse Berechnung Maximaler Flüsse Der Algorithmus von Ford-Fulkerson Spannbäume Spannbäume Algorithmus von Prim Optimierung Grundlagen der Optimierung Kombinatorische Optimierung Lineare Optimierung Das Simplex Verfahren