Allgemeines| Dozentin | Übungsleiter | Übungsleiter | Übungsleiter |  |  |  |  | Dorothea Wagner | Reinhard Bauer | Marcus Krug | Martin Holzer |
Deprecated: Function ereg_replace() is deprecated in /net/HomePages/i11/WWW_HomePages/i11www/extra/info3/includes/functions.php on line 144
| | | 2008-04-29: | Mündliche Nachprüfung | Anmeldung für die mündliche Nachprüfung ist nur noch bis zum 30. April möglich. Dazu bitte eine eMail an rbauer@ira.uka.de schicken.
|
| | 2008-04-14: | Ergebnisse Nachklausur | Die Ergebnisse der Nachklausur und weitere Informationen finden sich hier.
|
|
Inhalt der theoretischen Informatik Im Gegensatz zu anderen Grundstudiumsvorlesungen werden in der theoretischen Informatik Themen behandelt, die weiter von den Anwendungen entfernt sind. Es geht um prinzipielle Fragestellungen, d. h. Fragen, die unabhängig von "Programmierungsaspekten" oder "konkreten Rechnern" sind: Gibt es Aufgaben, die von einem Rechner — unabhängig von der Art der Programmierung beziehungsweise von physikalischen und elektronischen Beschränkungen — nicht gelöst werden können? Welche Aufgaben können prinzipiell effizient (in vernünftiger Rechenzeit, mit vernünftigem Speicherplatzbedarf) gelöst werden?
Einige Themen
Deterministische und nicht-deterministische endliche Automaten, Sprachen, Turing-Maschinen, Berechenbarkeit, Church'sche These, P und NP, NP-vollständige Probleme, Grammatiken, Chomsky-Hierarchie ...
|