Zum Inhalt springen

Kurs:Algorithmen und Datenstrukturen/Funktionale Algorithmen

Aus Wikiversity



Inhalte

Einleitung

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

Theoretische Grundlagen

[Bearbeiten]

Programmierparadigmen

[Bearbeiten]
  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

Laufzeitanalysen

[Bearbeiten]
  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

Entwurfsmuster

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

Suchen

[Bearbeiten]

Suchen in sortierten Folgen

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

Suchen in Texten

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

Sortieren

[Bearbeiten]

Algorithmen für vergleichsbasiertes Sortieren

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

Weitere Sortierprobleme

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

Dynamische Datenstrukturen

[Bearbeiten]

Binäre Suchbäume

[Bearbeiten]
  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äume

[Bearbeiten]
  1. AVL-Bäume

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

[Bearbeiten]
  1. 2-3-4-Bäume
  2. Rot-Schwarz-Bäume

Heaps

[Bearbeiten]
  1. Heap Sort
    1. Vorgehensweise
    2. Analyse

Hashtabellen

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

Graphen

[Bearbeiten]

Einführung

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

Breitendurchlauf

[Bearbeiten]
  1. Breitensuche

Tiefendurchlauf

[Bearbeiten]
  1. Tiefensuche

Topologisches Sortieren

[Bearbeiten]
  1. Topologisches Sortieren

Berechnung kürzester Wege

[Bearbeiten]
  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üsse

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

Spannbäume

[Bearbeiten]
  1. Spannbäume
    1. Algorithmus von Prim

Optimierung

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