Theoretische Informatik I
Wintersemester 2022/2023
Vorlesung: Theoretische Informatik I
Hinweis zu Theoretische Informatik I
In der Übung vom Dienstag habe ich die Variable k fälschlicherweise sowohl für das ausgewählte Element als auch für die Größe der Teilfelder verwendet. Die (hoffentlich) richtige Lösung ist online.
Hinweis zu Theoretische Informatik I
Der Raum für die mündlichen Prüfungen wird noch mitgeteilt. Voraussichtlich wird die Prüfung in Herrn Professor Goerdts Büro (Raum 1/266) oder in einem der Hörsäle darüber stattfinden. Raumplan
Hinweis zu Theoretische Informatik I
Die Vorlesungen und Übungen aus dem letzten Semester sind online.
Für die Prüfungsvorleistung werden 40% der insgesamt erreichbaren Punkte benötigt. Pro Übungsblatt wird es in der Regel 10 Punkte geben.
Die Lösung können Sie per Mail an Julian Pape-Lange ( julian.pape-lange@…) senden.
|
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 |
|
||||||||||||||||||||||||||||||
|
Termine |
|
||||||||||||||||||||||||||||||
|
Links |
|
||||||||||||||||||||||||||||||