Arbeitsgruppe Mathematische Logik und Theoretische Informatik
Auf dieser Seite finden sich Übungsaufgaben, das Skript und weitere Informationen zur Vorlesung Theoretische Informatik (Informatik IV) von Prof. Ambos-Spies im Sommersemester 2004.
Theoretische Informatik (Informatik IV)
|
Prof. Dr. Klaus Ambos-Spies (Vorlesung, Übungen)
INF 294, Zimmer 015 Tel.: 06221-54-8203 email: ambos@math.uni-heidelberg.de Sprechstunde: Mittwoch, 10-11 Uhr, und nach Vereinbarung (in der vorlesungsfreien Zeit nach Vereinabrung).
Dr. Wolfgang Merkle (Übungen)
|
|
Vorlesung: Mo, Mi 11-13h.
Bis auf Weiteres findet die Vorlesung im großen Seminarraum des Rechenzentrums statt (INF 293, Raum 119 im 1. Stock)
Übung: Di 14-16h, AM HS -101 und Do 14-16h, AM HS -111 Beginn der Vorlesung: Mi 21. 04. 2004 |
Skript |
|
|
Übungsblatt 1 vom 26.04.2004
[PS]
[PDF] Übungsblatt 2 vom 03.05.2004 [PS] [PDF] Übungsblatt 3 vom 10.05.2004 [PS] [PDF] Übungsblatt 4 vom 17.05.2004 [PS] [PDF] Übungsblatt 5 vom 24.05.2004 [PS] [PDF] Übungsblatt 6 vom 01.06.2004 [PS] [PDF] Übungsblatt 7 vom 14.06.2004 [PS] [PDF] Übungsblatt 8 vom 21.06.2004 [PS] [PDF] Übungsblatt 9 vom 28.06.2004 [PS] [PDF] Übungsblatt 10 vom 05.07.2004 [PS] [PDF] |
|
Die Vorlesung gibt eine Einführung in drei zentrale Gebiete der Theoretischen Informatik: die Berechenbarkeitstheorie, die Komplexitätstheorie sowie die Automatentheorie und die Theorie Formaler Sprachen. In dem Teil über Berechenbarkeitstheorie werden Formalisierungen des Berechenbarkeitskonzepts (Turingmaschinen, Registermaschinen, rekursive Funktionen) eingeführt, die Existenz universeller Maschinen bewiesen und die Grenzen der Berechenbarkeit aufgezeigt. Die Komplexitätstheorie beschäftigt sich mit quantitativen Aspekten von Computer-Rechnungen. Es werden die Grundkonzepte dieser Theorie eingeführt und das berühmte P-NP-Problem erörtert. Im Teil über Formale Sprachen werden die verschiedenen Typen von Chomsky-Grammatiken vorgestellt, der Chomsky-Hierarchiesatz bewiesen und die Mächtigkeit der verschiedenen Konzepte durch Angabe entsprechender Automatentypen, die die jeweils darstellbaren Sprachen erkennen können, beschrieben. |
|
Die Vorlesung ist eine Pflichtgrundvorlesung im 4. Semester für Studierende im Bachelorstudiengang Anwendungsorientierte Informatik. Für Studierende der Mathematik kann die Vorlesung als Kursusvorlesung im Nebenfach Informatik oder im Bereich Mathematik gewählt werden. Die Vorlesung wird im Wintersemester fortgesetzt. |
|
Spezielle Kenntnisse werden nicht vorausgesetzt jedoch Vertrautheit mit grundlegenden mathematischen Konzepten und Methoden. |
|
|
|
|
|
Verantwortlich: Jan
Reimann
|
|
Letzte Änderung:
9. Oktober 2001
|