Benutzerspezifische Werkzeuge
Sie sind hier: Startseite Willkommen Professuren Ordentliche Professuren Theoretische Informatik Lehrveranstaltungen Wintersemester 2011/2012 Theoretische Informatik I: Automaten und formale Sprachen

Theoretische Informatik I

Die Theoretische Informatik beschäftigt sich mit den grundlegenden Fragestellungen der Informatik. Hierzu werden Computer- und Automatenmodelle idealisiert und mathematisch untersucht.
    • Die Automatentheorie und die Theorie der formalen Sprachen ist grundlegend für die Entwicklung von Programmiersprachen und Compilern. Sie untersucht, mit welchen Techniken welche Arten von Sprachen effizient analysiert werden können.

    • Die Berechenbarkeitstheorie (Thema des vierten Semesters) befasst sich mit den prinzipiellen Grenzen des Berechenbaren und der Relation zwischen verschiedenen Computer- und Programmiermodellen.

    • Die Komplexitätstheorie (Thema des vierten Semesters) untersucht Effizienz von Algorithmen im Hinblick auf Platz- und Zeitbedarf und kümmert sich insbesondere um die Frage, wie effizient man bestimmte Probleme lösen kann.

 

Inhaltliche Gliederung der Vorlesung

Einführung in die Theoretische Informatik

Endliche Automaten und reguläre Sprachen:
    • Deterministische und nichtdeterministische endliche Automaten

    • Reguläre Ausdrücke und Typ-3 Grammatiken

    • Charakterisierung und Abschlusseigenschaften regulärer Sprachen

    • Minimierung von Automaten

    • Grenzen regulärer Sprachen (Pumping Lemma)

Kontextfreie Sprachen:
    • Kontextfreie Grammatiken

    • Pushdown Automaten

    • Charakterisierung und Abschlusseigenschaften kontextfreier Sprachen

    • Grenzen und Normalformen kontextfreier Sprachen

Allgemeine und kontextsensitive Sprachen
    • Turingmaschinen

    • Modelle für Typ-0 und Typ-1 Sprachen

    • Eigenschaften von Typ-0 und Typ-1 Sprachen

 

Ablauf

    • In der Vorlesung werden die zentralen Konzepte der theoretischen Informatik vorgestellt und an Beispielen illustriert. Sie werden ein grösseres Verständnis erreichen, wenn Sie jede Vorlesungsstunde vor- und nachbereiten. Daher werden die in der Vorlesung verwendeten Folien auf den Servern des Lehrgebiets im Voraus bereitgestellt.

    • Es werden wöchentlich Übungsblätter herausgegeben, die von den Studierenden zu bearbeite sind schriftlich zur Bewertung durch das Tutorenteam abzugeben sind.

    • Es werden wöchentliche Übungen angeboten (siehe Termine). Die Übungen dienen der Vertiefung und Anwendung der in der Vorlesung vorgestellten Themen in einer kleineren Gruppe unter Betreuung einer Tutorin oder eines Tutors. Hier werden Übungsaufgaben gemeinsam bearbeitet und Fragen und Probleme zu den Vorlesungsthemen und den Übungsblättern besprochen.

    • Das zusätzliche Tutorium ist eine freiwillige Zusatzveranstaltung, die zur Besprechung allgemeiner Fragen mit dem Dozenten vorgesehen ist.

    • Die Sprechstunden dienen der persönlichen Beratung: Hier können Sie spezifische Probleme oder individuelle Schwierigkeiten besprechen.

    • Das wichtigste ist jedoch das Selbststudium: Sie werden nur dann wirklich etwas lernen und optimal auf die Abschlussklausur vorbereitet sein, wenn Sie sich selbstständig und regelmaßig mit den Vorlesungsthemen auseinandersetzen und die Übungsblätter bearbeiten.

Artikelaktionen
Auf einen Blick
Lehrform diverse Formen
Empfohlen ab FS 0
Voraussetzungen

Die Veranstaltung ist prinzipiell für Studenten des ersten Semesters geeignet, setzt jedoch ein gutes Verständnis mathematischer Konzepte und Methoden voraus. Für die meisten Studenten ist daher die Teilnahme an dem Mathematik Brückenkurs dringend zu empfehlen.

Benotet Ja
Punkte gesamt 6
davon praktisch 0
Sprache deutsch
Fremdhörer zugelassen? Nein
Teilgebiete Theoretische Informatik(2000)
Studiengang Bachelor
Belegung via PULS