Pflichtveranstaltung
"Theoretische Informatik I"
Veranstalter: |
Prof. Dr. Andreas Schwill,
Sandra
Nitz, Marco Thomas, Franziska
Biegler |
Zielgruppe: |
2. Semester |
Umfang: |
4 SWS (3 SWS Vorlesung, 1 SWS Übung) |
Informatikfach-
zuordnung: |
Theoretische Informatik |
Leistungspunkte: |
6 benotete Punkte |
Beginn: |
Vorlesung: 10.4.2002
Übungen der Gruppen 1-4 beginnen in der 16. Woche, Übungen
der Gruppen 5-8 in der 17. Woche |
Zeit: |
Vorlesung:
-
mittwochs 15.15-16.45 Uhr (wöchentlich)
-
freitags 15.15-16.45 Uhr (ab 12.4. 14-tägig)
Übungen im 14-tägigen Wechsel:
-
Gruppen 1/5: dienstags 15.15-16.45 Uhr (Betreuer: Biegler)
-
Gruppen 2/6: mittwochs 17.00-18.30 Uhr (Betreuer: Nitz)
-
Gruppen 3/7: donnerstags 11.00-12.30 Uhr (die beiden Gruppen entfallen)
-
Gruppen 4/8: donnerstags 17.00-18.30 Uhr (Betreuer: Thomas)
|
Ort: |
Vorlesungen: HPI HS1
Übungen: 3.04.1.03 |
|
-
Die vorläufigen Endergebnisse der Veranstaltung stehen im Netz.
Einsprüche können noch bis 21.10.2002 geltend gemacht werden.
-
Im Ordner Minimierung endlicher Automaten
finden Sie ein Selbstlernmodul, das den Abschnitt 4.5 der Vorlesung ersetzt.
Bitte arbeiten Sie den Abschnitt durch und senden Sie ggf. Korrekturen,
Anmerkungen, Fragen an Sandra Nitz.
|
Inhaltsübersicht
-
Motivation für Theoretische Informatik, Struktur des Gebiets, typische
Probleme
-
Grenzen der Algorithmisierung, Halteproblem, Selbstanwendungsproblem
-
Maschinenbegriff, abstrakte Maschinen
-
Endliche deterministische und nichtdeterministische Akzeptoren
-
Reguläre Sprachen und Ausdrücke
-
Minimierung von Automaten
-
Grammatiken unterschiedlichen Typs
Leistungserfassungsprozeß
Die Abschlußnote wird folgendermaßen
ermittelt:
-
Schriftliche Bearbeitung von Übungsaufgaben (40%).
Aus den zur Verfügung gestellten Übungsblättern wird
je Blatt eine Aufgabe ausgelost und bewertet. Wir bewerten Ihre Lösungen
für jede Aufgabe ternär: 2 Punkte stehen für eine gute,
1 Punkt für eine noch akzeptable, 0 Punkte für eine nicht mehr
akzeptable Bearbeitung. Die gesammelten Punkte rechnen wir am Schluß
der Veranstaltung in eine Note um (Faustregel: Erreichen
Sie die Hälfte aller möglichen Punkte, bekommen Sie eine 4,0).
-
eine Klausur im Umfang von 90 Minuten nach Schluß der Veranstaltung
(60%).
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. Bitte tragen Sie sich in Listen ein, die in den
Übungsgruppen ausliegen, wenn Sie zu einem bestimmten Termin vorrechnen
möchten.
Die Übungsaufgaben sowie die Klausur 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.05.2002 schriftlich 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
-
R. Wilhelm u.a.: Ganimal - Generierung endlicher Automaten, Interaktives
Online-Lehrbuch, 2000 (Link s. unten)
Skriptum
-
Mitschriften von Kommilitonen früherer Semester liegen auf diesem
Server bereit.
Übungsaufgaben
-
Die Übungsaufgaben liegen jeweils wöchentlich vor der Veranstaltung
auf diesem Server bereit. Die Aufgaben werden in den Übungen besprochen.
Zum Lesen der Übungsblätter können Sie den kostenlosen
Adobe Acrobat Reader verwenden.
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).
|