Theoretische Informatik II: Effiziente Algorithmen - Einzelansicht

Alle Informationen im Moodle-Kurs "Theoretische Grundlagen: Effiziente Algorithmen (SoSe 2024)" (Kurztitel "TI-II-SoSe2024"). Einschreibeschlüssel bei der ersten Hörsaalübung (09.04.) oder per Anfrage an boehne@uni-potsdam.de

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Die Theoretische Informatik beschäftigt sich mit den grundlegenden Fragestellungen der Informatik. Hierzu werden Computer- und Automatenmodelle idealisiert und mathematisch untersucht.

Die Automatentheorie und die Theorie der formalen Sprachen (Thema des ersten Semesters) ist grundlegend für die Entwicklung von Programmiersprachen und Compilern. Sie untersucht, mit welchen Techniken welche Arten von Sprachen effizient analysiert werden können.
Die Berechenbarkeitstheorie befasst sich mit den prinzipiellen Grenzen des Berechenbaren und der Relation zwischen verschiedenen Computer- und Programmiermodellen. Die Komplexitätstheorie untersucht Effizienz von Algorithmen im Hinblick auf Platz- und Zeitbedarf und kümmert sich insbesondere um die Frage, wie effizient man bestimmte Probleme lösen kann.

Gliederung der Theoretischen Informatik II:

- Berechenbarkeitstheorie:

• Turingmaschinen
• Loop-, While- und Goto-Programme
• Rekursive Funktionen
• Lambda-Kalkül
• Churchsche These
• Berechenbarkeit, Aufzählbarkeit und Entscheidbarkeit
• Unlösbare Probleme
• Beweistechniken für Unlösbarkeit

- Komplexitätstheorie:

• Konkrete Komplexitätsanalyse
• Komplexitätsklassen
• Handhabbarkeit
• NP-Vollständigkeit
• Satz von Cook
• NP-Vollständigkeit bei konkreten Problemen nachweisen
• Kurzvorstellung weiterer Problemklassen und weiter Methoden

Dirk Hoffmann: Theoretische Informatik

Hopcroft, R. Motwani, J. Ullman: Einfuehrung in die Automatentheorie, Formale Sprachen und Komplexitaetstheorie, Pearson 2002

Michael Sipser: Introduction to the Theory of Computation. 2. Auflage, PWS 2005 J