Navigation

Chair of Theoretical Computer Science and Information Security
Chair of Theoretical Computer Science and Information Security

Theoretische Informatik 2

(lecture, summer 2003, 4/2/0 SWS)

Content:
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.
Literature:
  • vorläufiges, unvollständiges Skript (230 KB) - access only with URZ password
  • Ingo Wegener: Theoretische Informatik - eine algorithmische Einführung, Teubner Verlag, Stuttgart 1999.
  • Weitere Literatur wird in der Vorlesung bekannt gegeben.
Participants:
Informatik (4. Semester)
Exercises:

Press

  • Living the Life on Campus

    Students in Chemnitz enjoy living on campus - In the ten TU Chemnitz dormitories, there are 1,800 beds in single apartments, doubles or apartments shared among multiple people …

  • Wanted: Diplomats for New York

    Students from all disciplines at the TU Chemnitz can apply to participate in the world’s largest UN simulation, which will take place in New York City in early 2017. Deadline to apply is July 29, 2016 …