Kommentare/ Inhalte:

Das Modul behandelt über den Bachelor-Stoff hinausgehende Modelle universeller Berechenbarkeit und Ersetzungssysteme, deren Komplexität und Struktur. Parallele Registermaschinen, Variationen von sequentiellen Maschinen aber auch neuere Konzepte werden entsprechend dem aktuellen Stand der Forschung vorgestellt. Die Komplexität paralleler und sequentieller Verfahren wird hinsichtlich struktureller Klassifikation betrachtet (z.B.: arithmetische, polynomielle Alternierungs- und weitere Hierarchien), wie auch mit Hilfe der Analyse konkreter Algorithmen untersucht (z.B.: algorithmische Geometrie). Kryptographische Verfahren (vom RSA-Verfahren bis zu elliptischen Kurven) werden hier genauso vorgestellt, wie Möglichkeiten und Techniken des Membrane- und DNA-Computings.

Ersetzungssysteme, die in allen Bereichen der Informatik vorkommen, werden in diesem Modul als höhere sequentielle und parallele Grammatiken vorgestellt (Matrix- und IndexGrammatiken, bzw. Lindenmayer- und P-Systeme, usw.), wie auch in der Form von Reduktions- Termersetzungs- oder Deduktionssystemen studiert. Klassifi-kation über Eigenschaften, wie Konfluenz und Existenz eindeutiger Normalformen

in Church/Rosser Systemen (Knuth-Bendix Vervollständigungsverfahren) spielt eine genauso wichtige Rolle wie die abstrakte Theorie, Klassifikation und Transformation der Sprachfamilien (AFL-Theorie).

Lernziel:

Die Studierenden sollen die grundlegenden Konzepte der sequentiellen und parallelen Automaten bzw. Algorithmen verstehen; Verfahren und Techniken zur Analyse der Komplexität kennen lernen; die Rolle von Parallelität im Vergleich zu sequentiellen Verfahren als wichtiges Entwurfskriterium für Algorithmen erkennen.

Die Studierenden sollen weiter die universelle Rolle von Ersetzungssystemen in verschiedensten Strukturen mit vielfältigsten Objekten erkennen; Sie sollen formale Ersetzungssysteme (Rewriting) als weitere Möglichkeit zur Definition von Klassen syntaktischer Konstrukte (formaler Sprachen) begreifen und gleichfalls im Gewand von Reduktionssystemen als nichtdeterministisch arbeitende Algorithmen mit eindeutigem Ergebnis verstehen und anwenden können; sie sollen unterschiedlich definierte Klassen von formalen Sprachen über die Kenntnis von den Eigenschaften dieser Sprachfamilien klassifizieren können.

Vorgehen:

Vorlesung mit integrierten Übungsaufgaben und Diskussion zu Konzepten und Verfahren.

Literatur:

Jozef Gruska: Foundations of Computing, International Thomson Computer Press, Boston 1997.

Ingo Wegener: Complexity Theory, Springer Verlag, Berlin, Heidelberg, New York, 2005.

Volker Turau: Algorithmische Graphentheorie, Oldenbourg Verlag, München, Wien, 2004.

Gheorghe Păun, Grzegorz Rozenberg & Arto Salomaa: DNA Computing, Springer Verlag, Berlin, Heidelberg, New York, 1998.

Jürgen Dassow & Gheorghe Păun: Regulated Rewriting in Formal Language Theory, EATCS Monograph 18, Springer Verlag, Berlin, Heidelberg, New York, 1990.

Lawrence C. Washington: Elliptic Curves, Chapman & Hall/CRC, 2008.

Weitere Veröffentlichungen in wissenschaftlichen Zeitschriften, die in der Vorlesung Verwendung finden, werden bekanntgegeben.