Suche Home Einstellungen Anmelden Hilfe  

UNI Didaktik der
Informatik
DdI

Pflichtveranstaltung
"Theoretische Informatik I"

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

info  Abzählbarkeit
Definition des Begriffs - Abzählbarkeit der Menge X*
info  Adobe Acrobat Reader - Software zum Betrachten von pdf-Dokumenten
info  Ankündigung SS 2000
info  Ankündigung SS 2001
info  Ankündigung SS 2002
info  Auswertung des FTI Kurztests - SS02
info  Epsilon
info  FAQ - Frequently Asked Questions zur Theoretischen Informatik I
info  Folien zum Satz von Chomsky-Schützenberger - A. Schwill - 2002
Grundidee, Beispiele, Beweisskizze
info  Formelgraphik für Wettbewerb (phi-Funktion) - 2002
info  Ganimal - Generierung endlicher Automaten - Interaktives Online-Lehrbuch - R. Wilhelm u.a. - *2000
Das Online-Lehrbuch beschreibt schrittweise die vollständigen Konstruktion eines minimalen endlichen Akzeptors zu einem regulären Ausdruck. Die hierzu notwendigen Definitionen werden ebenfalls eingeführt.
info  Grail+ - A symbolic computation environment for finite-state machines, regular expressions, and finite languages - Univ - Western Ontario - *2003
Using Grail+, one can input machines or expressions, convert them from one form to the other, minimize, make deterministic, complement, and perform many other operations.
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  Minimierung endlicher Automaten - S. Nitz - 2002
Multimediales Selbstlernmodul
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 SS 2000 - A. Schwill - 2001
info  PGP-Signatur für Leistungsstand SS 2001 - A. Schwill - 2002
info  Primzahlzwillinge.gif
info  Quickies
info  Sigma
info  Übersicht über den Leistungsstand aller Teilnehmer - SS2000
info  Übersicht über den Leistungsstand aller Teilnehmer - SS2001
info  Übersicht über den Leistungsstand aller Teilnehmer - SS2002
info  Übersicht über den Leistungsstand aller Teilnehmer - SS2003
info  Übungsblatt 1
info  Übungsblatt 2
info  Übungsblatt 3
info  Übungsblatt 3
info  Übungsblatt 4
info  Übungsblatt 4 - KORRIGIERTE FASSUNG V. 26.5.
info  Übungsblatt 5
info  Übungsblatt 5
info  Übungsblatt 6
info  Übungsblatt 6
info  Übungsblatt 7
info  Vereinigung.gif
info  Vorlesungsmitschriften zur Theoretischen Informatik I von Teilnehmern - SS2000
Bitte beachten Sie, daß es sich um unkorrigierte (daher z.T. fehlerhafte), unkommentierte Mitschriften Ihrer Kommilitonen handelt.
info  Wettbewerb "Das 1.000.000ste Computerprogramm" - SS 2002

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