Berechenbarkeit und Komplexität (WS 2014/15)
Abschnittsübersicht
-
In dieser Lehrveranstaltung behandeln wir wesentliche Bereiche der Theoretischen Informatik, d.h., der "ewigen Wahrheiten" der Informatik, die auf der Grundlage der Mathematik/Logik ein für allemal bewiesen wurden und die unabhängig von weiteren technologischen Entwicklungen sind. Zentrale Fragestellungen sind dabei der Begriff der Berechenbarkeit (was ist berechenbar und was nicht?) und der Komplexität (wie groß ist der für eine Berechnung notwendige Aufwand?).
Um an der Lehrveranstaltung teilzunehmen, müssen Sie sich wie üblich im KUSSS System dafür (jeweils Vorlesung und Übung separat) anmelden. Wenn Sie sich auch im Moodle einloggen und als Kursteilnehmer eintragen, erhalten Sie per Email alle ins "Ankündigen"-Forum gestellte Nachrichten und können selbst Nachrichten ins "Fragen und Antworten"-Forum stellen.
-
A.Univ.Prof. DI Dr. Wolfgang Schreiner
326.023, Freitag 12:00-13:30, HS 9, Beginn: 10.10.2014
No lecture on December 12, additional lecture on December 19, 14:15-15:45, HS 8
Folien
- Computability and Complexity (4 on 1)
- Finite State Machines and Regular Languages (4 on 1)
- Turing Machines (4 on 1)
- Turing Complete Computational Models (4 on 1)
- Limits of Computability (4 on 1)
- Basics of Complexity (4 on 1)
- Analysis of Complexity (4 on 1)
- Limits of Feasibility (4 on 1)
Lehrbücher
- Dirk W. Hoffmann:Theoretische Informatik
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman:Introduction to Automata Theory, Languages and Computation (deutsche Ausgabe: Einführung in Automatentheorie, Formale Sprachen und Berechenbarkeit)
- Michael Sipser: Introduction to the Theory of Computation
- Thomas H. Cormen et al: Introduction to Algorithms
Das Buch von Hoffmann bietet eine sehr lesenswerte deutsche Einführung in das Thema.Klausur (2. Termin)- Mittwoch 25. März 2015, 17:15-18:45, HS 17
- Anmeldung in KUSSS bis Montag 23. März 2015 12:00.
- Alle schriftlichen Unterlagen sind erlaubt.
- Lichtbildausweis nicht vergessen!
- Computability and Complexity (4 on 1)
-
- 326.004 (Dr. Nikolaj Popov)
Neue Termine und Räume: - 13.10. bis 3.11.: 19:00-19:45, S2 046
- 10.11. und 15.12.: 17:15-18:00, S2 059
- Alle anderen Termine: 17:15-18:00, S2 053
- 326.016 -- Fr, 10:15-11:00 H12 (Dr. Ralf Hemmecke)
Beginn: 10. Oktober 2014 - 326.050 -- Fr, 11:00-11:45 H12 (Dr. Ralf Hemmecke)
Beginn: 10. Oktober 2014
Übungsklausuren (für alle 3 Übungsgruppen):
(Unterlagen sind nicht zugelassen)
1. Klausur: 21.11.2014 11:00-11:45, H 1
2. Klausur: 16.01.2015 14:30-15:15, H 1Die Übungsaufgaben sind ca. eine Woche vor Übungsbeginn hier verfügbar.
- 326.004 (Dr. Nikolaj Popov)