TU Chemnitz, Fakultät für Informatik, Professur Theoretische Informatik: Fakultät für Informatik: Professur Theoretische Informatik: WS 2009/10

Zur Prüfung Theoretische Informatik I findet am 16.02. 13:00 - 14:30 und 17.02. 11:00 - 12:30 im Raum 1/346 eine Konsultaion statt.

Konkrete Fragen, die besprochen werden sollen, bitte bis zum 15.02. per Mail an mich.

Die Prüfung zu Theoretische Informatik I findet in diesem Semester für alle Studenten mündlich statt.

Im Raum 1/266a.

Vorerst sind die Termine 24., 25. und 26.02. vorgesehen. Falls sich jemand später prüfen lassen möchte oder die Termine nicht ausreichen, können auch individuelle Termine vereinbart werden.

Listen zur Anmeldung liegen bis zum 17.02. im ZPA bei Frau Himmelreich im Zimmer C004 aus.

Eine der Säulen der Informatik - in Theorie und Praxis - ist die Algorithmik. Die Vorlesung führt in das Gebiet ein.

Es werden algorithmische Lösungen für verschiedene Standardprobleme behandelt. Relativ breiten Raum nehmen die Graphalgorithmen ein. Bei ihnen geht es um das systematische Aufsuchen aller Knoten eines beliebigen, gerichteten oder ungerichteten Graphen. Als die beiden hauptsächlichen Lösungswege werden die Breitensuche und die Tiefensuche behandelt. Ferner werden verschiedene Verfahren für die Bestimmung kürzester Wege und von minimalen Spannbäumen in Graphen betrachtet.

Weiterhin werden effiziente Algorithmen zur Lösung verschiedener anderer Probleme eingeführt. Bei den betrachteten Problemen handelt es sich um das Sortieren, das Auswahlproblem und die Matrizenmultiplikation. Eine generelle Strategie zum Vermeiden von Sackgassen im Problemlösungsprozess ist das Backtracking. Zur Beschränkung der möglichen Lösungswege bei einer Aufgabe werden Branch-and-Bound-Verfahren eingesetzt. Schließlich werden noch die lokale Suche in Graphen und das Dynamische Programmieren behandelt.

Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. MIT Press, Cambridge, MA, 1994.

Kingston, J.H.: Algorithms and Data Structures. Design, Correctness, Analysis. 2 Addison-Wesley, Harlow, 1998.

Schöning, U.: Algorithmik. Spektrum Akademischer Verlag.

• Übungsaufgaben
• unkorrigiertes Vorlesungsskript Das vorliegende Vorlesungsskript umfasst nur einen Teil der Vorlesung. Für die Prüfung ist der gesamte Vorlesungsstoff relevant (einschließlich der späteren Kapitel.)
• Ein umfassenderes Skript liegt handschriftlich vor.

• Aussagenlogik
• Prädikatenlogik
• Logik-Programmierung

Uwe Schöning: Logik für Informatiker, Spektrum Verlag.

• Vorlesungsunterlagen
• Übungsaufgaben