Universität Rostock  |   Institut für Informatik  |   Wissenschaftsbereich Theoretische Informatik Impressum
 
 
 
 
 
 
Vertiefungsgebiet Theoretische Informatik
 


Inhaltliche Charakteristik

Jede wissenschaftliche Disziplin bedarf einer stabilen theoretischen Grundlage. Die Theoretische Informatik spielt diese Rolle für das Gebiet der Informatik. Forschungen in der Theoretischen Informatik haben zum Entwurf von effizienten Datenstrukturen und Algorithmen geführt, die in viele Softwarepakete und Hardwareprodukte Eingang gefunden haben.

Durch theoretische Forschungen wurde für wichtige und häufig auftretende Probleme nachgewiesen, daß es keine effizienten Lösungsalgorithmen geben kann bzw. in schwächerer Form, daß es wahrscheinlich keine solchen gibt.

Die Theoretische Informatik hat grundlegende Konzepte, Prinzipien und Techniken zum Inhalt, die nötig sind, um das sich schnell entwickelnde Gebiet der Informatik zu verstehen und mit weiterentwickeln zu können.

Jeder Informatikstudent muß sich daher während seines Studiums (im Grund- und Kernstudium) theoretische Grundkenntnisse aneignen. Im Vertiefungsgebiet werden diese Kenntnisse entscheidend erweitert und - wie der Name schon sagt - vertieft.

Ein Absolvent des Vertiefungsgebietes hat in aller Regel keine umfangreicheren praktischen Spezialkenntnisse, die er im Berufsleben sofort einsetzen kann, ohne sich einarbeiten zu müssen, er hat aber ein fundamentales Verständnis für viele Entwicklungen der Informatik, das es ihm ermöglicht, sich schnell in ganz verschiedene Spezialgebiete der Informatik und angrenzender Bereiche einarbeiten zu können. Er ist vor allem prädestiniert, an der Bearbeitung wissenschaftlicher Forschungsprojekte zur Weiterentwicklung der Informatik mitzuwirken.

zurück



Lehrveranstaltungen des Vertiefungsgebietes

Zum Vertiefungsgebiet gehören die folgenden obligatorischen Vorlesungen (Basiskomplexe):

  • Symbolisches Rechnen I (2 SWS)
  • Algorithmentechnik (2 SWS)
  • Komplexitätstheorie I (2 SWS)
  • Effiziente Graphenalgorithmen I (2 SWS)

Aus einem weiteren Angebot von wahlobligatorischen Vorlesungen (Erweiterungskomplexe) sind 8 SWS auszuwählen:

  • Symbolisches Rechnen II (2 SWS)
  • Computeranalytik (2 SWS)
  • Rewrite-Systeme (2 SWS)
  • Logik-Programmierung (2 SWS)
  • LISP-Programmierung und Theorie (2 SWS)
  • Numerisches Rechnen (2 SWS)
  • Komplexitätstheorie II (2 SWS)
  • Kryptographie (2 SWS)
  • Effiziente Graphenalgorithmen II (2 SWS)
  • Graphen- und Hypergraphenmodelle in der Informatik (2 SWS)
  • Grundlagen für Parallelrechner und parallele Algorithmen (2 SWS)
zurück

Basisprüfungskomplexe

  • Symbolisches Rechnen
  • Algorithmen und Komplexität

Erweiterungsprüfungskomplexe

Zugehörig zu den wahlobligatorischen Vorlesungen


Bestandteil der Ausbildung im Vertiefungsgebiet ist die aktive Teilnahme an zwei Forschungsseminaren sowie die Anfertigung der Studien- und Diplomarbeit im Vertiefungsgebiet.
zurück



Inhaltliche Schwerpunkte

  • Symbolisches Rechnen I
    • Grundprobleme des symbolischen Rechnens
    • Algebraische Grundlagen
    • Elementare Algorithmen der Computeralgebra
    • Arbeiten mit dem CA-System MAPLE

  • Algorithmentechnik
    • Mathematische Grundlagen
    • Entwurfstechniken für Algorithmen
    • Algorithmen der INTEGER- und Polynomarithmetik
    • Matrixoperationen
    • NP-vollständige Probleme und approximative Lösung NP-vollständiger Probleme
    • Parallele Algorithmen

  • Komplexitätstheorie I
    • Raum und Zeit auf Turingmaschinen
    • Komplexität auf anderen Maschinenmodellen
    • Determinismus/Nichtdeterminismus
    • Vollständigkeit und Reduzierbarkeitsbegriffe in verschiedenen Komplexitätsklassen
    • Komplexitätsklassenhierarchien

  • Effiziente Graphenalgorithmen I
    • Algorithmische Graphenprobleme
    • Durchsuchen von Graphen
    • Greedy-Algorithmus, Minimalgerüste und Matroide
    • Kürzeste Wege
    • Das Steinerbaum-Problem

  • Symbolisches Rechnen II
    • Modulare Methoden
    • p-adische Methoden
    • Symbolische Integration
    • Lösung von Differentialgleichungen

  • Computeranalytik
    • Grundprobleme der C-Analytik
    • Adaptive Approximation von Funktionen
    • Näherungslösungen für Differentialgleichungen
    • Fehleranalyse und -abschätzung
    • Anforderungen an CA-Systeme aus der Sicht der Computeranalytik

  • Rewrite-Systeme
    • Reduktionen; Terme und Algebren
    • Termination; Unifikation; Kritische Paare; Vervollständigungen; Erweiterungen;

  • Logik-Programmierung
    • Die Programmiersprache PROLOG
    • Ausgewählte Programmierbeispiele
    • Anwendungen in der Übersetzertechnik
    • Anwendungen in der KI
    • PROLOG und die mathematische Logik
    • Aktuelle Tendenzen in der Logikprogrammierung

  • LISP-Programmierung und Theorie
    • Programmieren mit COMMON LISP
    • CLOS
    • λ-Kalkül

  • Numerisches Rechnen
    • Grundprobleme der Computerarithmetik; Rundungsfehleranalyse;
    • Intervallarithmetik; Axiome einer optimalen Arithmetik; Numerische Stabilität;
    • Sensibilitätsanalyse; Programmsysteme mit automatischer Ergebnisverifikation

  • Komplexitätstheorie II
    • Komplexität auf Parallelrechnermodellen
    • Schaltkreiskomplexität
    • Approximation
    • Strukturelle Komplexitätstheorie

  • Kryptographie
    • Klassische Verfahren
    • Public-key-Verfahren
    • Das RSA-Verfahren
    • Protokolle

  • Effiziente Graphenalgorithmen II
    • Das Maximalflußproblem und Algorithmen
    • ''Maximum Matching''-Algorithmen
    • Färbungsprobleme und Algorithmen
    • Verallgemeinerte Baumstrukturen und ihr algorithmischer Nutzen

  • Graphen- und Hypergraphenmodelle in der Informatik
    • Graphen, Halbordnungen und ''Scheduling''
    • Azyklische Hypergraphen und relationale Datenbankschemata
    • Spezielle Graphenklassen und Genetik-Probleme
    • Graphenmodelle für Parallelrechner

  • Grundlagen für Parallelrechner und parallele Algorithmen
    • Parallelrechnermodelle
    • Effiziente parallele Algorithmen
    • Kommunikation in Parallelrechnernetzen
    • Schwer parallelisierbare Probleme
zurück