Kurs:Algorithmen und Datenstrukturen/Funktionale Algorithmen



Inhalte

EinleitungBearbeiten

  1. Begriffserklärungen
  2. Eigenschaften von Algorithmen
  3. Algorithmenentwurf
  4. Größter gemeinsamer Teiler
  5. Berechenbarkeit

Theoretische GrundlagenBearbeiten

ProgrammierparadigmenBearbeiten

  1. Überblick
  2. Paradigmenbegriff
  3. Funktionale Algorithmen
    1. Grundidee
    2. Funktionsdefinition und Signatur
    3. Auswertung von Funktionen
    4. Auswertung von rekursiven Funktionen
    5. Fakultät
    6. Größter gemeinsamer Teiler
    7. Fibonacci-Zahlen
    8. Weiteres Beispiel
  4. Logische Algorithmen
    1. Einführung
    2. Prädikatenlogik&Hornlogik
    3. Prolog
    4. Listen
  5. Imperative Algorithmen
    1. Einführung
    2. Variablen
    3. Zustände
    4. Ausdrücke
    5. Anweisungen
    6. Syntax und Semantik
    7. Fakultätsfunktion
  6. Funktional vs. Imperativ
    1. Fibonacci-Zahlen
    2. Größter gemeinsamer Teiler

LaufzeitanalysenBearbeiten

  1. Komplexität
  2. Notationen
    1. O-Notation
    2. Omega-Notation
    3. Theta-Notation
    4. Eigenschaften
    5. Komplexitätsklassen
  3. Aufwandsanalyse von iterativen Algorithmen
  4. Aufwandsanalyse von rekursiven Algorithmen
    1. Vollständige Induktion
    2. Mastertheorem
  5. Rekursionsbäume

EntwurfsmusterBearbeiten

  1. Entwurfsprinzipien
  2. Greedyalgorithmen
    1. Wechselgeldalgorithmus
  3. Divide and Conquer
  4. Backtracking
  5. Dynamische Programmierung

SuchenBearbeiten

Suchen in sortierten FolgenBearbeiten

  1. Einleitung
  2. Sequentielle Suche
  3. Binäre Suche
  4. Fibonacci Suche

Suchen in TextenBearbeiten

  1. Einleitung
  2. Naiver Algorithmus zur Textsuche
  3. Knuth-Morris-Path

SortierenBearbeiten

Algorithmen für vergleichsbasiertes SortierenBearbeiten

  1. Grundlagen
  2. InsertionSort
  3. SelectionSort
  4. BubbleSort
  5. MergeSort
  6. Zwischenbemerkungen
  7. QuickSort
  8. Untere Schranke

Weitere SortierproblemeBearbeiten

  1. Rückblick und Ausblick
  2. Nicht-Vergleichsbasiertes-Sortieren: Bucket Sort
  3. Verteiltes Sortieren: Batcher Sort

Dynamische DatenstrukturenBearbeiten

Binäre SuchbäumeBearbeiten

  1. Einleitung
  2. Einschub Bäume und Traversierung
  3. Binäre Suchbäume
    1. Suchen
    2. Einfügen
    3. Löschen
    4. Implementierung
    5. Weitere Aspekte
  4. AVL-Bäume
  5. 2-3-4-Bäume und Rot-Schwarz-Bäume
  6. Heaps
  7. Hashtabellen

AVL-BäumeBearbeiten

  1. AVL-Bäume

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

  1. 2-3-4-Bäume
  2. Rot-Schwarz-Bäume

HeapsBearbeiten

  1. Heap Sort
    1. Vorgehensweise
    2. Analyse

HashtabellenBearbeiten

  1. Hashtabellen
    1. Kollisionsstrategie
    2. Aufwand
    3. Dynamische Hashverfahren
    4. Hashen in Java

GraphenBearbeiten

EinführungBearbeiten

  1. Typen von Graphen
  2. Definitionen zu Graphen
  3. Repräsentation von Graphen
  4. Datenstrukturen für Graphen

BreitendurchlaufBearbeiten

  1. Breitensuche

TiefendurchlaufBearbeiten

  1. Tiefensuche

Topologisches SortierenBearbeiten

  1. Topologisches Sortieren

Berechnung kürzester WegeBearbeiten

  1. Einleitung
  2. Der Algorithmus von Dijkstra
  3. Der Algorithmus von Bellmann-Ford
  4. Der Algorithmus von Floyd-Warshall
  5. Das Traveling Salesman Problem

Berechnung maximaler FlüsseBearbeiten

  1. Berechnung Maximaler Flüsse
  2. Der Algorithmus von Ford-Fulkerson

SpannbäumeBearbeiten

  1. Spannbäume
    1. Algorithmus von Prim

OptimierungBearbeiten

  1. Grundlagen der Optimierung
  2. Kombinatorische Optimierung
  3. Lineare Optimierung
  4. Das Simplex Verfahren