Lehrveranstaltungen in der Informatik

Algorithmen

Prof. Dr. J. Christiansen

zurück zurück

Inhalt

Vorlesung

Fundamentale Algorithmen

  • Sortieren: Insertionsort, Quicksort, Heapsort
  • Textsuche: Algorithmus von Knuth-Morris-Pratt, Algorithmus von Boyer-Moore
  • Graphen: Zusammenhangs­komponenten, minimaler Spannbaum, kürzeste Wege

 

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.

Veranstaltungsnummer: 70346   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 (Sonstige Prüfungsleistung)

Lernvoraussetzungen

Sie beherrschen die mathematischen Grundlagen Menge, Relation, Abbildung, Graph. Sie können objektorientiert programmieren.

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

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms. 2. Auflage, The MIT Press (2001)

H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

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

G. Saake, K.U. Sattler: Algorithmen und Datenstrukturen. dpunkt (2002)