Professur Theoretische Informatik

Veranstaltungen im Sommersemester 2013

Vorlesung: Effiziente Algorithmen

SWS (V/Ü/P)

 3/1/0

Inhalt

Die Vorlesung ist eine Fortsetzung der Theoretischen Informatik I. Es werden folgende Themen behandelt:

  • Komplexe Datenstrukturen und ihre Analyse (Fibonacci-Heaps, Splay-Bäume)
  • Analyse der mittleren Laufzeit von Algorithmen (Quicksort)
  • Einführung in randomisierte Algorithmen

Literatur
  • Cormen, Leiserson, Rivest: "Introduction to Algorithms."
  • Kingston: "Algorithms and Data Structures."
  • Weiss: " Algorithms."
  • Ottmann, Widmayer: "Algorithmen und Datenstrukturen."
  • Schöning: "Algorithmen - kurz gefasst" und "Algorithmen"
  • Kozen: "The design and analysis of algorithms"
  • Aho, Hopcroft, Ullman: "Data structures and algorithms"
  • Weiss: "Algorithms, data structures, and problem solving with C++"

Termine
Vorlesung: Montag (Woche 1) 9:15-10:45 1/208 Prof. Goerdt
Dienstag 17:15-18:45 1/375 Prof. Goerdt
Übung: Montag (Woche 2) 9:15-10:45 1/208 Falke

Links

Vorlesung: Einführung Quantencomputing

SWS (V/Ü/P)

 3/1/0

Inhalt

Die Vorlesung behandelt die Grundlagen des Quantencomputing und -- darauf aufbauend -- die bekanntesten Algorithmen für den Quantencomputer:

  • Grover's Suchalgorithmus, der es erlaubt, N Elemente in Zeit Wurzel N zu durchsuchen.
  • Shor's Faktorisierungsalgorithmus, der mit dem Quantenrechner in Polynomialzeit faktorisiert.

Besonders die Entdeckung des Faktorisierungsalgorithmus im Jahr 1994 ist für die Popularität des Quantencomputing in der Informatik verantwortlich. Es ist kein klassicher Algorithmus für dieses wichtige Problem mit polynomialer Laufzeit bekannt.

Im Gegensatz zur klassischen Algorithmenlehre der Informatik erfordert das Verständnis des Quantencomputing eine gewisse mathematische Vorbildung, insbesondere in linearer Algebra. Diese Vorbildung wird in der Vorlesung vermittelt und es sollte ganz interessant sein, zu erlernen wie die lineare Algebra angewandt werden kann.

Literatur

Wird in der Vorlesung bekannt gegeben.

Termine
Vorlesung: Dienstag 11:30-13:00 1/375 Prof. Goerdt
Freitag (Woche 1) 9:15-10:45 1/208 Prof. Goerdt
Übung: Freiteg (Woche 2) 9:15-10:45 1/208

Seminar: Allgemeine Fragen der Theoretischen Informatik

SWS

 2

Inhalt

Es werden Themen zu

  • Datenkompression und zu
  • Allgemeinen Themen der Theoretischen Informatik

behandelt.

Interessenten sind willkommen und wenden sich bitte an Lutz Falke (lutz.falke@...) oder an Prof. Dr. Andreas Goerdt (a.goerdt@...).

Literatur
  • Cormen, Leiserson, Rivest: "Introduction to Algorithms."

Weitere Literatur wird individuell bekannt gegeben.

Termine
Proseminar: Dienstag 15:30-17:00 1/367A
Hauptseminar: Mittwoch 11:30-13:00 1/368