Suche Home Einstellungen Anmelden Hilfe  

UNI Didaktik der
Informatik
DdI

Pflichtveranstaltung
"Theoretische Informatik II"

       
      Veranstalter: Prof. Dr. Andreas Schwill, Sandra Nitz, Franziska Biegler
      Zielgruppe: 3. Semester
      Umfang: 4 SWS (3 SWS Vorlesung, 1 SWS Übung)
      Informatikfach- 
      zuordnung:
      Theoretische Informatik
      Leistungspunkte: 6 benotete Leistungspunkte
      Beginn: Vorlesung: 16.10.02
      Übungen: 23.10.02
      Zeit: Vorlesung:
      Mi 15.15-16.45 Uhr (wöchentlich)
      Fr 15.15-16.45 Uhr (gerade Wochen)
      Übung 1: Mo 13.30-15.00 Uhr (ungerade Wochen)
      Übung 2: Di 13.30-15.00 Uhr (ungerade Wochen)
      Übung 3: Mo 13.30-15.00 Uhr (gerade Wochen)
      Übung 4: Di 13.30-15.00 Uhr (gerade Wochen)
      Ort: Vorlesung: HPI-Hörsaal HS2
      Übung 1: 3.04.0.02
      Übung 2: 3.04.1.02
      Übung 3: 3.04.0.02
      Übung 4: 3.04.1.02
      Aktuelles:  
    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 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.
    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 15.11.2002 bei einem der Veranstalter zurückgenommen werden.

    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
    Skriptum
    • Ausarbeitungen von Kommilitonen aus früheren Semestern liegen auf diesem Server vor.
    Ü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 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).

info  Ankündigung WS 2000/01
info  Ankündigung WS 2001/02
info  Folien zum Satz von Chomsky-Schützenberger - A. Schwill - 2002
Grundidee, Beispiele, Beweisskizze
info  Hier geht es zu den Quickies - *2001
Sie kommen von hier zu einer Web-Seite unter dem Online-Learning-System WebCT. Dort müssen Sie zunächst Ihren eigenen Studienbereich erzeugen (create account). Anschließend können Sie sich einloggen.
info  Nachweis der Äquivalenz von NPDA und kontextfreien Grammatiken - V. Claus - 2001
Hier sehen Sie ein Beispiel und zugleich die Konstruktionsidee des Beweises der Äquivalenz von NPDA und kontextfreien Grammatiken.
info  PGP-Signatur fŸr Leistungsstand WS 2001/2002 - A. Schwill - 12.06.2002
info  PGP-Signatur für Leistungsstand WS 2000/2001 - A. Schwill - 24.06.2001
info  Übersicht über den Leistungsstand aller Teilnehmer - WS2000/2001
info  Übersicht über den Leistungsstand aller Teilnehmer - WS2001/2002
info  Übersicht über den Leistungsstand aller Teilnehmer - WS2002/2003
info  Übersicht über den Leistungsstand aller Teilnehmer - WS2002/2003
info  Übungsblatt 1
info  Übungsblatt 1
info  Übungsblatt 2
info  Übungsblatt 2
info  Übungsblatt 3
info  Übungsblatt 3
info  Übungsblatt 4
info  Übungsblatt 4
info  Übungsblatt 5
info  Übungsblatt 5
info  Übungsblatt 6
info  Übungsblatt 6
info  Übungsblatt 7
info  Vorlesungsmitschriften zur Theoretischen Informatik II von Teilnehmern - WS2000/01
Bitte beachten Sie, daß es sich um unkorrigierte (daher z.T. fehlerhafte), unkommentierte Mitschriften Ihrer Kommilitonen handelt.

Benutzer: gast • Besitzer: schwill • Zuletzt geändert am: