Achtung! Das Lehrangebot ist noch nicht vollständig und wird bis Semesterbeginn laufend ergänzt.
406231 VU Theoretische Informatik 2 (2003W)
Theoretische Informatik 2
Prüfungsimmanente Lehrveranstaltung
Labels
Details
Sprache: Deutsch
Lehrende
Termine (iCal) - nächster Termin ist mit N markiert
- Dienstag 07.10. 10:30 - 13:00 (ehem. Seminarraum 10 Hauptgebäude, Tiefparterre Stiege 5 Hof 3)
- Donnerstag 09.10. 15:30 - 18:00 (ehem. Hörsaal 28 Hauptgebäude, 1.Stock, Stiege 1)
- Dienstag 14.10. 10:30 - 13:00 (ehem. Seminarraum 10 Hauptgebäude, Tiefparterre Stiege 5 Hof 3)
- Donnerstag 16.10. 15:30 - 18:00 (ehem. Hörsaal 28 Hauptgebäude, 1.Stock, Stiege 1)
- Dienstag 21.10. 10:30 - 13:00 (ehem. Seminarraum 10 Hauptgebäude, Tiefparterre Stiege 5 Hof 3)
- Donnerstag 23.10. 15:30 - 18:00 (ehem. Hörsaal 28 Hauptgebäude, 1.Stock, Stiege 1)
- Dienstag 28.10. 10:30 - 13:00 (ehem. Seminarraum 10 Hauptgebäude, Tiefparterre Stiege 5 Hof 3)
- Donnerstag 30.10. 15:30 - 18:00 (ehem. Hörsaal 28 Hauptgebäude, 1.Stock, Stiege 1)
- Dienstag 04.11. 10:30 - 13:00 (ehem. Seminarraum 10 Hauptgebäude, Tiefparterre Stiege 5 Hof 3)
- Donnerstag 06.11. 15:30 - 18:00 (ehem. Hörsaal 28 Hauptgebäude, 1.Stock, Stiege 1)
- Dienstag 11.11. 10:30 - 13:00 (ehem. Seminarraum 10 Hauptgebäude, Tiefparterre Stiege 5 Hof 3)
- Donnerstag 13.11. 15:30 - 18:00 (ehem. Hörsaal 28 Hauptgebäude, 1.Stock, Stiege 1)
Information
Ziele, Inhalte und Methode der Lehrveranstaltung
Art der Leistungskontrolle und erlaubte Hilfsmittel
Mindestanforderungen und Beurteilungsmaßstab
Die Vorlesung Theoretische Informatik II befasst
sich mit weiterfuehrenden Konzepten der Theoretischen
Informatik, basierend auf der Vorlesung Theoretische
Informatik I. Das Ziel der Vorlesung besteht darin,
die wichtigsten der Informatik zugrundeliegenden
Konzepte kennenzulernen und ihre Relevanz fuer die
Loesung konkreter Fragen im Zusammenhang mit Anwendungen
zu studieren.Die Vorlesung befasst sich mit vier Themenbereichen:
Berechenbarkeit und Entscheidbarkeit, Komplexitaet,
Praedikatenlogik und Sematik von Programmiersprachen.Der erste Teil, Berechenbarkeit und Entscheidbarkeit,
weist nach, dass nicht jede beliebige Problemstellung
algorithmisch loesbar ist und geht der Frage nach, wie
algorithmische Berechenbarkeit und Entscheidbarkeit
formal gefasst werden
kann. Hierzu werden mehrere Modelle diskutiert, die
sich alle hinsichtlich ihrer theoretischen Ausdrucksfaehigkeit
als aequivalemt erweisen.Berechenbarkeit stellt sich nur die Frage nach der
prinzipiellen algorithmischen Loesbarkeit eines Problems
und ignoriert den dafuer noetigen Rechenaufwand.
Komplexitaetstheorie wendet sich genau dieser Frage
zu und studiert die praktische Loesbarkeit bzw.
Unloesbarkeit von Problemen durch Klassifikation des
benoetigten Zeit und/oder Speicheraufwands.Die Praedikatenlogik, der dritte in der Vorlesung
angesprochene Problemkreis, definiert ein formales System,
mit dessen Hilfe mechanisch gueltige Saetze aus
Axiomen abgeleitet werden koennen. Die Praedikatenlogik
stellt einen Rahmen zur Verfuegung, in dem die
Korrektheit von Programmen verifiziert werden kann.Der abschliessende Teil der Vorlesung befasst sich mit
formalen Methoden zur Spezifikation der Semantk von
Programmiersprachen und der Verifikation und Validation
von Programmen. Operationelle Semantik, Hoaresche
Semantik, wp-Semantik und denotationelle Semantik werden
in diesem Rahmen vorgestellt.
sich mit weiterfuehrenden Konzepten der Theoretischen
Informatik, basierend auf der Vorlesung Theoretische
Informatik I. Das Ziel der Vorlesung besteht darin,
die wichtigsten der Informatik zugrundeliegenden
Konzepte kennenzulernen und ihre Relevanz fuer die
Loesung konkreter Fragen im Zusammenhang mit Anwendungen
zu studieren.Die Vorlesung befasst sich mit vier Themenbereichen:
Berechenbarkeit und Entscheidbarkeit, Komplexitaet,
Praedikatenlogik und Sematik von Programmiersprachen.Der erste Teil, Berechenbarkeit und Entscheidbarkeit,
weist nach, dass nicht jede beliebige Problemstellung
algorithmisch loesbar ist und geht der Frage nach, wie
algorithmische Berechenbarkeit und Entscheidbarkeit
formal gefasst werden
kann. Hierzu werden mehrere Modelle diskutiert, die
sich alle hinsichtlich ihrer theoretischen Ausdrucksfaehigkeit
als aequivalemt erweisen.Berechenbarkeit stellt sich nur die Frage nach der
prinzipiellen algorithmischen Loesbarkeit eines Problems
und ignoriert den dafuer noetigen Rechenaufwand.
Komplexitaetstheorie wendet sich genau dieser Frage
zu und studiert die praktische Loesbarkeit bzw.
Unloesbarkeit von Problemen durch Klassifikation des
benoetigten Zeit und/oder Speicheraufwands.Die Praedikatenlogik, der dritte in der Vorlesung
angesprochene Problemkreis, definiert ein formales System,
mit dessen Hilfe mechanisch gueltige Saetze aus
Axiomen abgeleitet werden koennen. Die Praedikatenlogik
stellt einen Rahmen zur Verfuegung, in dem die
Korrektheit von Programmen verifiziert werden kann.Der abschliessende Teil der Vorlesung befasst sich mit
formalen Methoden zur Spezifikation der Semantk von
Programmiersprachen und der Verifikation und Validation
von Programmen. Operationelle Semantik, Hoaresche
Semantik, wp-Semantik und denotationelle Semantik werden
in diesem Rahmen vorgestellt.
Prüfungsstoff
Literatur
Zuordnung im Vorlesungsverzeichnis
Zur Zeit sind keine Zuordnungsinformation verfügbar.
Letzte Änderung: Di 01.10.2024 00:20
Konzepten der Theoretischen Informatik, basierend
auf der Vorlesung Theoretische Informatik I.
Im einzelnen werden die folgenden Themenbereiche
angesprochen:- Berechenbarkeit und EntscheidbarkeitEinfuehrung der wichtigsten formalen Modelle fuer
Berechenbarkeit; rekursive Funktionen; Turing-
Maschinen; Churchsche These; Entscheidbarkeit;
Entscheidbarkeitsfragen fuer Sprachen und Automaten
der Chomsky-Hierarchie- KomplexitaetKomplexitatetsmasse; die Klassen P und NP;
Sprachen und Probleme; NP-Vollstaendigkeit
des Erfuellungsproblems (satisfiability problem);
weitere NP-vollstaendige Probleme;
Ausblick auf weitere Komplexitaetsklassen.- PraedikatenlogikAllgemeine Einfuehrung in die Praedikatenlogik;
Deduktion.- Semantik von ProgrammiersprachenPraedikatenlogik als Spezifikationssprache;
operationelle Semantik;
Hoare-Semantik und wp-Semantik; Elemente der
Denotationellen Semantik; Programmverifikation
und Validation.