zum Seiteninhalt
Ruprecht-Karls-Universität Heidelberg Institut fü Informatik
Siegel der Universitaet Startseite der Arbeitsgruppe Kontakt: Anschriften und Ansprechpartner Suche: Volltext; Personen; E-Mail; Forschungsdatenbank

Arbeitsgruppe Logik > Lehre Sommersemester 2007 >

Theoretische Informatik

Vorlesung von Prof. K. Ambos-Spies im Sommersemester 2007

Vorlesung
Tutoren
Inhalt
Scheinvergabe
Übungen
Übungsaufgaben
Zielgruppe
Voraussetzungen
Folien
Klausur
Aktuelles

Aktuelles

KLAUSURERGEBNISSE UND NACHPRÜFUNGEN Die Klausurergebnisse hängen am Schwarzen Brett vor dem Sekretariat der AG Math. Logik und Theor. Inform. (INF 294, Raum 016) und im Schaukasten vor der Geschäftsstelle des Instituts für Informatik (INF 348, Raum 021) aus.
Die Klausuren können im Sekretariat der AG Math. Logik und Theor. Inform. vom 23.7. bis zum 26.7. 2007 zu den üblichen Öffnungszeiten eingesehen werden. Spätere Einsichtnahme nach Vereinbarung.
Studierende, die die Klausur nicht bestanden haben, können an einer mündlichen Nachprüfung (im Zeitraum 1. - 10. 8. oder am 18./19.10.) teilnehmen. Anmeldung zu der Nachprüfung in den Sprechstunden am 25.7. und 1.8.

Vorlesung

Mo, Mi 11-13 Uhr, Raum: OMZ (INF 350), U014 siehe Lageplan
Prof. Dr. Klaus Ambos-Spies
INF 294, Zimmer 015
Telefon: 06221/54-8203
email: ambos@math.uni-heidelberg.de
Sprechstunde: Mi 10-11 h und nach Vereinbarung
(in der vorlesungsfreien Zeit nach Vereinbarung)

Übungen

Mo, 14-16 Uhr, AM, HS -103 (Peter Antes)
Di, 14-16 Uhr, AM, HS -102 (Jens Lechner)
Fr, 9-11 Uhr, AM, HS -101 (Thorsten Kräling)

Tutoren

Peter Antes
Jens Lechner
Thorsten Kräling

Aktuelles

Die KLAUSUR zur Vorlesung findet am Mittwoch, den 18. Juli 2007, von 11.15h bis 13.15 Uhr im Raum OMZ (INF 350), U014 statt. ANMELDUNG: Bitte geben Sie das ausgefüllte Anmeldeformular(pdf) bis spätenstens Montag, den 16. Juli 2007, in der Vorlesung, den Übungen oder im Sekretariat der AG Mathematische Logik und Theoretische Informatik (INF 294, Raum 016, Mo - Do 9-11 h) ab.

Inhalt

Die Vorlesung gibt eine Einführung in drei zentrale Gebiete der Theoretischen Informatik:

  • 1. die Berechenbarkeitstheorie,
  • 2. die Komplexitätstheorie sowie
  • 3. die Automatentheorie und die Theorie Formaler Sprachen.

    • In dem Teil über Berechenbarkeitstheorie werden Formalisierungen des Berechenbarkeitskonzepts (Turingmaschinen, Registermaschinen, rekursive Funktionen) eingeführt, die Existenz universeller Maschinen bewiesen und die Grenzen der Berechenbarkeit aufgezeigt. Die Komplexitätstheorie beschäftigt sich mit quantitativen Aspekten von Computer-Rechnungen. Es werden die Grundkonzepte dieser Theorie eingeführt und das berühmte P-NP-Problem erörtert. Im Teil über Formale Sprachen werden die verschiedenen Typen von Chomsky-Grammatiken vorgestellt, der Chomsky-Hierarchiesatz bewiesen und die Mächtigkeit der verschiedenen Konzepte durch Angabe entsprechender Automatentypen, die die jeweils darstellbaren Sprachen erkennen können, beschrieben.

    Scheinvergabe

    Gegen Ende der Vorlesungszeit wird eine Klausur als studienbegleitende Prüfung (für Bachelor-Studierende) angeboten. Die Teilnahme an der Klausur setzt die erfolgreiche Bearbeitung der Übungsblätter voraus. Die Klausur ist auch die Grundlage für die Vergabe von Übungsscheinen mit ECTS-Punkten. Übungsscheine ohne ECTS-Punkte werden bei Bearbeitung der Übungsblätter vergeben. Alle Scheine sind benotet.

    Übungsaufgaben

    Übungsblatt 0 vom 23.04.2007 [PDF]
    Übungsblatt 1 vom 23.04.2007 [PDF]
    Übungsblatt 2 vom 30.04.2007 [PDF]
    Übungsblatt 3 vom 7.05.2007 [PDF]
    Übungsblatt 4 vom 14.05.2007 [PDF]
    Übungsblatt 5 vom 21.05.2007 [PDF]
    Übungsblatt 6 vom 4.6.2007 [PDF]
    Übungsblatt 7 vom 11.06.2007 [PDF]
    Übungsblatt 8 vom 18.06.2007 [PDF]
    Übungsblatt 9 vom 25.06.2007 [PDF]
    Übungsblatt 10 vom 2.07.2007 [PDF]
    Übungsblatt 11 vom 9.07.2007 [PDF]

    Zielgruppe

    Die Vorlesung ist eine Pflichtgrundvorlesung im 4. Semester für Studierende im Bachelorstudiengang Anwendungsorientierte Informatik. Für Studierende der Mathematik kann die Vorlesung als Kursvorlesung im Nebenfach Informatik oder im Bereich Reine Mathematik gewählt werden. Die Vorlesung wird im Wintersemester fortgesetzt.

    Voraussetzungen

    Spezielle Kenntnisse werden nicht vorausgesetzt; jedoch Vertrautheit mit grundlegenden mathematischen Konzepten und Methoden.

    Folien

    Teil I: Berechenbarkeitstheorie

  • Kapitel 1: Einführung (pdf)(pdf)
  • Kapitel 2: Algorithmen (pdf)(pdf)
  • Kapitel 3: Turingmaschinen (pdf)(pdf)
  • Kapitel 4: Varianten des Turingmaschinen-Konzeptes (pdf)(pdf)
  • Kapitel 5: Registermaschinen (pdf)(pdf)
  • Kapitel 6: Rekursive Funktionen (pdf)(pdf)
  • Kapitel 7: Beispiele primitiv rekursiver Funktionen (pdf)(pdf)
  • Kapitel 8: Der Äquivalenzsatz (pdf)(pdf)
  • Kapitel 9: Universelle Maschinen (pdf)(pdf)
  • Kapitel 10: Unentscheidbare Probleme (pdf)(pdf)
  • Kapitel 11: Rekursiv aufzählbare Mengen (pdf)(pdf)


    • Teil II: Komplexitätstheorie

  • Kapitel 12: Zeit- und Platzkomplexität (pdf)
  • Kapitel 13: Nichtdeterministische Turingmaschinen und ihre Komplexität (pdf)
  • Kapitel 14: Die polynomiell beschänkten Komplexitätsklassen (pdf)


    • Teil III: Formale Sprachen

  • Kapitel 15: Termersetzungssysteme und Chomsky-Grammatiken (pdf)
  • Kapitel 16: Die Chomsky-Hierarchie (pdf)
  • Kapitel 17: Kontextsensitive Sprachen (pdf)
  • Kapitel 18: Kontextfreie Sprachen I (pdf)
  • Kapitel 19: Kontextfreie Sprachen II (pdf)
  • Kapitel 20: Reguläre Sprachen (pdf)

    • Seitenbearbeiter: Felicitas Hirsch