Pflichtveranstaltung
"Theoretische Informatik II"
| Veranstalter: |
Prof. Dr. Andreas Schwill,
Dipl.-Math.
Oliver Boldt |
| Zielgruppe: |
3. Semester |
| Umfang: |
4 SWS (ca. 2 SWS Vorlesung, 2 SWS Übung) |
| Beginn: |
Vorlesung: 18.10.01
Übungen: 23.10.01 bzw. 1.11. (Übung3) |
| Zeit: |
Vorlesung: donnerstags 13.30-15.00 Uhr
Übung1: dienstags 15.15-16.45 Uhr (14-tägig)
Übung2: mittwochs 17.00-18.30 Uhr (14-tägig)
Übung3: donnerstags 11.00-12.30 Uhr (wöchentlich) |
| Ort: |
Vorlesung: HPI-Hörsaal HS1 (donnerstags)
Übung1: 03.04.0.03-0.04
Übung2: HPI HS3
Übung3: 3.04.0.03-0.04 |
Aktuelles: |
Die endgültigen Veranstaltungsergebnisse liegen vor.
|
Inhaltsübersicht
-
kontextfreie Sprachen, Grammatiken, Normalformen
-
Kellerautomaten
-
Turingmaschinen, Registermaschinen
-
Chomsky-Hierarchie
-
while-Programme, loop-Programme, primitive Rekursion, mu-Rekursion
-
Aufzählbarkeit und Entscheidbarkeit
-
Komplexitätstheorie, NP-Vollständigkeit
Leistungserfassungsprozeß
Für die erfolgreiche Teilnahme an der Veranstaltung werden
6 benotete Leistungspunkte
vergeben.
Die Abschlußnote wird folgendermaßen
ermittelt:
-
ein Quickie etwa in der Mitte des Veranstaltungszeitraums (30%).
Sie bekommen eine Note.
-
eine Klausur nach Schluß der Veranstaltung (70%).
Sie bekommen eine Note. Durch ein oder mehrmaliges
Vorrechnen einer Übungsaufgabe während der Übungsstunden
können bis zu 5 Punkte Guthaben für die Klausur erworben werden.
Beide Teilleistungen müssen mit mindestens 4,0 bewertet worden sein.
Einen Überblick über Ihren aktuellen Leistungsstand erhalten
Sie jederzeit auf diesem Server.
Belegung
Innerhalb der ersten zwei Wochen werden während der Veranstaltung
Teilnehmerlisten ausliegen, in die sich alle Studenten eintragen müssen,
die am Leistungserfassungsprozeß teilnehmen möchten. Die Anmeldung
ist verbindlich und kann nur bis zum 13.11.2001 bei einem der Veranstalter
zurückgenommen werden.
Literaturhinweise
-
K. Erk, L. Priese: Theoretische Informatik, Springer Verlag 2000
- J. Hopcroft, R. Motwani, J. Ullman: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley 2001
-
H. Lewis, C. Papadimitriou: Elements of the Theory of Computation, Prentice-Hall
1981
-
U. Schöning: Theoretische Informatik - kurzgefaßt, Spektrum-Verlag
1994
-
I. Wegener: Theoretische Informatik, Teubner Verlag 1993
Skriptum
-
Ausarbeitungen von Kommilitonen aus früheren Semestern liegen auf
diesem Server vor.
Übungsaufgaben
-
Die Übungsaufgaben liegen jeweils wöchentlich auf diesem Server
bereit. Sie können bearbeitete Übungsaufgaben ohne Abgabefrist
zur Korrektur einreichen. Die Aufgaben gehen nicht in die Bewertung ein.
Zum Lesen der Übungsblätter benötigen Sie den kostenlosen
Adobe Acrobat Reader.
Note: §10 der Prüfungsordnung
bestimmt die Form der Noten: Zulässig sind 1,0 bis 4,0 mit Zwischennoten
sowie 5,0 (= nicht bestanden, kein Erwerb von Leistungspunkten).
|
