Veranstalter:	Prof. Dr. Andreas Schwill, Ralf Romeike
Zielgruppe:	2. Semester
Umfang:	4 SWS (3 SWS Vorlesung, 1 SWS Übung)
Informatikfach- zuordnung:	Theoretische Informatik
Leistungspunkte:	6 benotete Punkte
Beginn:	Vorlesung: 8.4.2003 Übungen der Gruppen 1-4 beginnen in der 16. Woche, Übungen der Gruppen 5-8 in der 17. Woche
Zeit:	Vorlesung: freitags 15.15-16.45 Uhr (wöchentlich)  dienstags 17.00-18.30 Uhr (14-tägig)  Übungen im 14-tägigen Wechsel: Gruppen 1/5: montags 15.15-16.45 Uhr (Sandro Schugk)  Gruppen 2/6: mittwochs 15.15.-16.45 (Hermann Schwarting)  Gruppen 3/7: donnerstags 17-18.30 Uhr (fallen aus)  Gruppen 4/8: freitags 11.00-12.30 Uhr (Ralf Romeike)
Ort:	Vorlesungen: HPI HS1 Übungen: Gruppen 1, 3, 4 , 5, 7, 8: 3.04.1.02  Gruppen 2, 6: 3.04.0.02
Aktuelles:	Die Klausurergebnisse und Endnoten sind ab sofort in der "Übersicht über den Leistungsstand aller Teilnehmer" einsehbar. Die Klausuren können am Mittwoch, den 10.9.03 zwischen 15 und 17 Uhr im Zi. 2.20 eingesehen werden. Eine Nachklausur wird nicht angeboten.

• 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

• 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 3 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.

Belegung
Die Belegung erfolgt elektronisch entsprechend der Bestimmungen des Instituts für Informatik.

Literaturhinweise

• A. Asteroth, C. Baier: Theoretische Informatik, Pearson 2002 
• K. Erk, L. Priese: Theoretische Informatik, Springer Verlag 2000 
• J. Hopcroft, R. Motwani, J. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Pearson 2002 
• 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)

• Mitschriften von Kommilitonen früherer Semester liegen auf diesem Server bereit.

• 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).