Navigation

Inhalt Hotkeys
Professur Theoretische Informatik und Informationssicherheit
Lehre

Theoretische Informatik 2

(Vorlesung, SS 2004, 4/2/0 SWS)

Inhalt:
In dieser Vorlesung werden zunächst Probleme betrachtet, welche sich prinzipiell nicht mit Rechnern lösen lassen. Hat man dann die Lösbarkeit eines Problems (unter Rechnereinsatz) nachgewiesen, fragt man nach der praktischen Lösbarkeit. Für eine große Klasse von Problemen ist jedoch bekannt, dass sie alle effizient (in Polynomialzeit) lösbar sind oder alle nicht effizient lösbar sind. Die Entscheidung dieses Sachverhalts ist das größte offene Problem der theoretischen Informatik.
In dieser Vorlesung werden die entsprechenden Konzepte vorgestellt. Die erzielten negativen Resultate ersparen die Suche nach nicht existierenden bzw. effizienten Algorithmen. Weiter werden endliche Automaten, welche eine Grundlage moderner Schaltwerke modellieren, vorgestellt.
Grammatiken beschreiben die Syntax von Programmiersprachen. Zum einen erwartet man hier Komfortabilität, zum anderen jedoch sollen auch etwa Tests auf syntaktische Korrektheit schnell durchführbar sein, was gewisse Einschränkungen ergibt. Es zeigt sich in dieser Vorlesung, dass die so genannten kontextfreien Grammatiken als Basis von Programmiersprachen geeignet sind.
Eine aktive Teilnahme in den angebotenen Übungen ist sehr zu empfehlen.
Literatur:
  • vorläufiges, unvollständiges Skript (230 KB) - nur mit URZ-Passwort
  • Ingo Wegener: Theoretische Informatik - eine algorithmische Einführung, Teubner Verlag, Stuttgart 1999.
  • Weitere Literatur wird in der Vorlesung bekannt gegeben!
Teilnehmer:
Informatik (4. Semester)
Übungen:

Presseartikel

  • Mit neuer Alumni-Strategie in die Zukunft

    TU Chemnitz möchte ihre Alumni in ein lebendiges Netzwerk integrieren - Mehr Kontakte auch außerhalb zentraler Veranstaltungen - Regionalbotschafter können "Alumni-Clubs" aufbauen …

  • Die eigene Sichtbarkeit kennen

    Universitätsbibliothek unterstützt Forschende bei bibliometrischer Analyse der eigenen Publikationsleistung – Umfrage zur Nutzung von Zitations-Datenbanken …

  • Für die Uni an den Start

    Am 6. September 2017 hat die TU Chemnitz die Chance, den Titel "Sportlichste Firma" beim WiC Firmenlauf zu erobern - Laufbegeisterte können sich noch bis zum 25. August anmelden …