You are here: Home Previous Events 2024 Vorlesung Theoretische Informatik …

Vorlesung Theoretische Informatik SoSe 2024

Die Vorlesung gibt eine Einführung in die theoretische Informatik. Sie führt in die Themen endliche Automaten, formale Sprachen und Grammatiken ein und diskutiert den Berechenbarkeitsbegriff. Es schließt sich eine Einführung in die Komplexitätstheorie, speziell die Theorie der NP-Vollständigkeit, an. Behandelt werden abstrakte Modelle von Maschinen und Sprachen, mit deren Hilfe Komplexitätsmaße wie Schrittzahl (Laufzeit) und Speicherbedarf von Algorithmen definiert werden.

Aktuelles

  • 16.04.2024: Veröffentlichung erstes Übungsblatt
  • 17.04.2024: Für die Studierende ohne Account sind die Vorlesungsaufnahmen, Folien und Übung hier verfügbar. Das ist nur eine Übergangslösung. 

    Vorlesungsmaterialien

    Die Vorlesungsmaterialien (Vorlesungsaufzeichnungen, Folien, Übungsaufgaben, Bibliographie) wird über ILIAS bereitgestellt.

    Sprache

    Die Vorlesung wird auf Deutsch gehalten. Übungen und Klausur sind in deutscher oder englischer Sprache zu bearbeiten.

    Lernziel und Vorlesungsinhalt

    Die Vorlesung gibt eine eingehende Einführung in die Theoretische Informatik. Neben verschiedenen formalen Präzisierungen des Berechenbarkeitsbegriffs, werden als Themen endliche Automaten, formale Sprachen und Grammatiken, Entscheidbarkeit und Komplexitätstheorie behandelt. Das Lernziel der Vorlesung ist es, Studierende dazu zu befähigen, Konzepte wie Algorithmen, Berechenbarkeit, Komplexität und deren grundsätzliche Bedeutung für die Lösbarkeit von Problemen zu verstehen.

    Die Vorlesung richtet sich an Informatik-Studenten im Bachelor-Studiengang. Die Veranstaltung hat einen Umfang von 6 ECTS Punkten.

    Klausur

    In jeden Semester wird eine schriftliche Klausur von 90 Minuten für diese Veranstaltung angeboten. In diesem Semester findet die Klausur am 07.08.2024 ab 09:15 in den Räumen des Gebäudes 101 statt. Als Hilfsmittel ist ein eigenhändig handbeschriebenes (beidseitig verwendetes) A4 Blatt zugelassen. Als besonderer Service wird eine Probeklausur am 25.07.2024 von 10-12 Uhr in Raum 101-00-026 angeboten. Beide Klausuren sind bilingual auf Deutsch und Englisch gestellt. Die Probeklausur wird am folgenden Tag auf ILIAS veröffentlicht.

    Kriterien für die Studienleistung

    Während des Semesters werden wöchentliche Aufgabenblätter ausgegeben. Um die Studienleistung zu erlangen, müssen mindestens 50% der Übungspunkte erreicht werden. Die Übungsblätter können in Gruppen von drei Studierenden bearbeitet werden. Es ist möglich durch aktive Beteiligung in der Übungsgruppe (z.B. Vorrechnen) Extrapunkte zu erhalten. Sollte aufgrund besonderer Umstände die Mindestpunktzahl nicht erreicht werden, so ist es möglich auf Antrag beim Tutor die Probeklausur am 25.07.2024 von 10-12 Uhr in Raum 101-00-026 zu nutzen, um das Punktekonto aufzufüllen. In diesem Fall sind als Hilfsmittel nur ein eigenhändig handbeschriebenes (beidseitig verwendetes) A4 Blatt zugelassen. Bitte informieren Sie die Aufsicht vor der Probeklausur davon.

    Ablauf der Veranstaltung

    Die Veranstaltung wird in Präsenz organisiert; Aufzeichnungen der Vorlesung werden zur Verfügung gestellt.  

    • Vorlesung Montag, 16:00 - 18:00 Uhr in 101-00-026
    • Übungen
      • Übungsgruppe 1: Mittwoch 8-10 Uhr,  051-00-006, Christoph Ullinger
      • Übungsgruppe 2: Mittwoch 8-10 Uhr, 106-00-007, Julian Schur
      • Übungsgruppe 3: Donnerstag 8-10 Uhr, 051-00-031, Sebastian Friedrich
      • Übungsgruppe 4: Donnerstag 16-18 Uhr, 051-00-006, Hans Albert 
      • Übungsgruppe 5: Donnerstag 16-18 Uhr, 051-00-034, Ahmet Ercem Bulut (englisch)
      • Übungsgruppe 6: Freitag 8-10 Uhr, 101-01-016/18, Sebastian Friedrich

     

    In der ersten Vorlesungswoche findet kein Übungsbetrieb statt. Jeden Dienstag Abend wird ein Übungsblatt veröffentlicht. Sie haben bis Montag 16:00 Uhr Zeit, die Aufgaben auf dem Übungsblatt zu bearbeiten und Ihre Lösungen auf  ILIAS hoch zu laden.

    Literatur

    1. M. Sipser: Introduction to the Theory of Computation, Cengage India, 3rd Edition, 2014, ISBN 8131771865
    2. I. Wegener: Theoretische Informatik - eine algorithmenorientierte Einführung, 2. Auflage 1999, Teubner, Stuttgart. ISBN 3-5191-2123-9
    3. U. Schöning: Theoretische Informatik kurzgefasst, Spektrum Taschenbuch, 5. Auflage, 2008, Spektrum Akademischer Verlag, Heidelberg. ISBN 3-8274-1824-0
    4. H. Lewis, C. Papadimitriou: Elements of the Theory of Computation, 2. Auflage, 1997, 361 Seiten, kart., Prentice Hall, New Jersey. ISBN 0-13-262478-8
    5. J. Hopcroft, J. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, 3. Auflage 1994, 461 Seiten, kart., Addison Wesley, Bonn. ISBN 3-89319-744-3