Theoretische Informatik I
Wintersemester 2021/2022
Vorlesung: Theoretische Informatik I
Hinweis zu Theoretische Informatik I
Das Video der dreizehnten Übung ist online.
Hinweis zu Theoretische Informatik I
Herr Professor Goerdt sagt am Anfang der Vorlesung vom 14.12.2021 ein paar Worte zur Prüfung. Für die Terminanmeldung beachten Sie bitte unsere Seite zur Prüfungsanmeldung.
Hinweis zu Theoretische Informatik I
Die Vorlesungen und Übungen werden hochgeladen. Die Lösung können Sie per Mail an Julian Pape-Lange ( julian.pape-lange@…) senden.
Für die Prüfungsvorleistung werden 40% (in der Vorlesung habe ich fälschlicherweise 50% gesagt) der insgesamt erreichbaren
Punkte benötigt. Pro Übungsblatt wird es in der Regel 10 Punkte geben.
Hinweis zu Theoretische Informatik I
Bei Fragen zur Vorlesung können Sie sich an Julian Pape-Lange ( julian.pape-lange@…) wenden.
| SWS (V/Ü/P) |
4/2/0 |
| Voraussetzungen |
keine
|
| Inhalt |
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.
|
| Literatur |
- 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.
Addison-Wesley, Harlow, 1998.
- Schöning, U.:
Algorithmik. Spektrum Akademischer Verlag.
|
| Links |
|
