Lehrveranstaltungen in der Informatik

Algorithmen

Prof. Dr. H.W. Lang

zurück zurück

Inhalt

Vorlesung

Fundamentale Algorithmen

  • Sortieren: Quicksort
  • Sortieren: Heapsort
  • Textsuche: Algorithmus von Knuth-Morris-Pratt
  • Textsuche: Algorithmus von Boyer-Moore
  • Graphen: Minimaler Spannbaum: Algorithmus von Prim
  • Graphen: Kürzeste Wege: Algorithmus von Dijkstra
  • Graphen: Kürzeste Wege: Algorithmus von Floyd/Warshall

 

Analyse

  • O-Notation

 

Entwurfsmethoden

  • Divide and Conquer
  • Greedy
  • Dynamic Programming

 

Algorithmisch schwierige Probleme

  • Problem des Handlungsreisenden
  • Klassen P und NP, NP-Vollständigkeit
  • Approximationsverfahren

 

Übungen / Labor

In den begleitenden Übungen werden ausgewählte Algorithmen am Computer programmiert und empirisch hinsichtlich ihrer Laufzeiten verglichen.

Organisation

3. Semester, Vorlesung / Übung  4-std.

Sprache: deutsch

Präsenzstudium: 60 h, Eigenstudium: 90 h
Gesamtaufwand: 150 h

Leistungspunkte (credit points): 5

Medienformen: Tafel, Webseiten mit interaktiven Simulationen

Vorbedingungen: keine

Prüfung: PL (Hausarbeit)

Lernziele

Sie können Methoden zum Entwurf von Algorithmen anwenden, die Korrektheit von Algorithmen beweisen, Algorithmen hinsichtlich ihrer Laufzeit analysieren und Algorithmen in Programme umsetzen. Ferner kennen Sie die wichtigsten fundamentalen Algorithmen und Datenstrukturen.

Literatur

H.W. Lang: Algorithmen in Java. 2. Auflage, Oldenbourg (2006)

R. Sedgewick: Algorithms in Java, Parts 1-4. 3. Auflage, Addison-Wesley (2003)