Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

Übung: Theoretische Informatik III

Dozent: Dr. Wolfgang Kössler
Übung: Dr. Wolfgang Kössler

Termine: UE Di 15-17 RUD 25, 3.101 W. Kössler
Zuordnung: Grundstudium, 4. Semester


Übungsbeginn: 10.4.2012

 

Es findet nur noch die Übung ohne Vorlesung statt.

Die Klausur findet voraussichtlich am 17.7.2012 um 10 Uhr statt.
 

Inhalte und Lernziele


Während in der Vorlesung ThI2 die Themengebiete Automaten und formale Sprachen im Mittelpunkt standen, befassen wir uns in der VL ThI3 vorwiegend mit verschiedenen Entwurfsmethoden für effiziente Algorithmen. Die hierzu nötigen Kenntnisse über algebraische und relationale Strukturen wie etwa Graphen werden ebenfalls in der VL vermittelt. Da die gefundenen Algorithmen "nur" obere Schranken für den benötigten Rechenaufwand liefern, untersuchen wir auch Methoden der Komplexitätstheorie, diesen Aufwand nach unten abzuschätzen. Um auch NP-vollständige Probleme in der Praxis mit vertretbarem Aufwand bewältigen zu können, werden u.a. auch approximative und/oder randomisierte Lösungsverfahren eingesetzt, die oftmals auf heuristischen Ansätzen beruhen.

Empfohlene Literatur

  • Cormen, Leiserson, Rivest, Stein: Algorithmen - Eine Einführung. Oldenbourg 2007.
  • Emden-Weinert, Hougardy, Kreuter, Prömel, Steger: Einführung in Graphen und Algorithmen, Vorlesungsskript, 450 Seiten, Berlin 1996.
  • Garey, Johnson: Computers and Intractability - A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979.
  • Hopcroft, Ullman: Introduction to Automata Theory, Languages, and Computation. Addison Wesley, 1979.
  • Lewis, Papadimitriou: Elements of the Theory of Computation. Prentice-Hall, 1981.
  • Motwani, Raghavan: Randomized Algorithms. Cambridge University Press, 1995.
  • Ottmann, Widmayer: Algorithmen und Datenstrukturen. Spektrum Akademischer Verlag, 2002.
  • Papadimitriou: Computational Complexity. Addison-Wesley, 1994.
  • Schöning: Algorithmik. Spektrum Akademischer Verlag, 2001.
  • Sedgewick: Algorithmen. Pearson Studium, 2002.
  • Sipser: Introduction to the Theory of Computation. PWS Publishing Company, 2005.
  • Wagner: Einführung in die Theoretische Informatik, Grundlagen und Modelle. Springer Verlag, 1994.
  • Wegener: Theoretische Informatik. Teubner Verlag, 1993.
  • Applets für verschiedene Sortieralgorithmen: http://www.sortieralgorithmen.de/ und http://www.sorting-algorithms.com/
  • Suchbaum-Applet für verschiedene Baum-Strukturen
  •  

Aufgabenblätter

Skript

Folien