Pflichtveranstaltung
"Theoretische Informatik II"
| Veranstalter: |
Prof. Dr. Andreas Schwill,
Dipl.-Math.
Oliver Boldt |
| Zielgruppe: |
3. Semester |
| Umfang: |
4 SWS (ca. 3 SWS Vorlesung, 1 SWS Übung) |
| Beginn: |
13.10.00 |
| Zeit: |
Vorlesung: freitags 13.30-15.30 Uhr
Übung: 15.45-17.15 alle 14 Tage |
| Ort: |
1.9.1.11 |
Aktuelles: |
Die Leistungsbewertung ist abgeschlossen. Bitte kontrollieren Sie Ihr Ergebnis.
Entgegen der Ankündigung werden keine Scheine mehr ausgegeben. Erworbene Leistungspunkte werden Ihrem Konto gutgeschrieben.
|
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:
-
Schriftliche Bearbeitung der Übungsaufgaben (30%).
Wir bewerten Ihre Lösungen für jede Aufgabe mit einer Note.
-
einmaliges Vorrechnen einer bearbeiteten Übungsaufgabe in den Übungsstunden
(10%).
Sie bekommen für Ihren Vortrag eine Note.
-
Mitschrift und Ausarbeitung einer Vorlesungsstunde (20%).
Ihre Ausarbeitung bitten wir innerhalb von 14 Tagen nach der protokollierten
Vorlesung vorzulegen. Sie bekommen für Ihre Ausarbeitung eine Note.
-
ca. 10-minütiges Fachgespräch nach Schluß der Veranstaltung
(40%).
Wir unterhalten uns über wesentliche Inhalte des Vorlesung und
der Übungsaufgaben. Sie bekommen eine Note.
Alle Teilleistungen müssen mindestens mit 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.2000 bei einem der Veranstalter
zurückgenommen werden.
Literaturhinweise
-
K. Erk, L. Priese: Theoretische Informatik, Springer Verlag 2000
-
J. Hopcroft, J. Ullman: Introduction to Automata Theory, Languages, and
Programming, Addison-Wesley 1979
-
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
-
wird auf der Basis der Ausarbeitungen (s. Leistungserfassungsprozeß)
evtl. nachschüssig zur Verfügung gestellt.
Übungsaufgaben
-
Die Übungsaufgaben liegen jeweils wöchentlich auf diesem Server
bereit. Der Abgabetermin ist auf den Übungsblättern vermerkt.
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).
|
