Vorlesung: Theoretische Informatik 1 (B-GL1) (WS 2018/2019)

Vorlesung über 4 SWS mit Übungen über 2 SWS
Pflichtveranstaltung des Moduls B-GL

Raumänderung am Do 22.11.: Die Vorlesung findet an diesem Tag in Raum H IV (römisch 4) statt. In H V soll ein neuer Beamer installiert werden.
In der Vergangenheit kam es immer wieder zu Zustellungsproblemen bei externen E-Mail Providern. Wenn Sie eine Antwort auf Ihre E-Mail erwarten, verwenden Sie bitte Ihre Uni-Mailadresse.

Vorlesung

Prof. Dr. Ulrich Meyer
Dienstag 08:00 - 10:00 und Donnerstag 08:00 - 10:00
Hörsaal H V (Jügelhaus/Hörsaalgebäude)
Alle anderen Termine werden rechtzeitig hier angekündigt.
LSF
Sprechstunde: Nach Vereinbarung

Übungsbetrieb

Alex Schickedanz
Hung Tran
Sprechstunde: Nach Vereinbarung
Fragen rund um die Vorlesung bitte an gl118@ae.cs.uni-frankfurt.de

Die Übungsgruppen beginnen ab Dienstag, den 23.10.2018, mit Blatt 0.

Das Lösen von Übungsaufgaben geschieht auf freiwilliger Basis. Dennoch ist die Teilnahme am Übungsbetrieb unbedingt zu empfehlen. Es werden weiterführende Inhalte vermittelt und es gibt die Möglichkeit Bonuspunkte zu sammeln. Eine Beobachtung unsererseits ist: Je höher die Bonuspunkte, desto höher die Wahrscheinlichkeit, eine gute Note zu erhalten. Weiterhin gilt aber, dass leider in der Vergangenheit immer wieder Betrugsversuche bei Übungsabgaben vorkamen. Deshalb bitten wir Sie darum, von solchen Täuschungsversuchen abstand zu nehmen. Es lohnt sich nicht! Eine Zuwiderhandlung kann dazu führen, dass wir Ihnen alle Bonuspunkte aberkennen (genaue Regelung: siehe "Hinweise zu den Übungsabgaben").

Der Übungsbetrieb ist im wöchentlichen Rhythmus organisiert. Die Abgabe des Blattes erfolgt am Dienstag in der Folgewoche vor Beginn der Vorlesung. Für eine frühere Abgabe benutzen Sie bitte den Briefkasten neben Raum 312.

Termine der Übungsgruppen

Gruppe 01 Mo 10 - 12 NM 123
Gruppe 02 Mo 12 - 14 NM 123
Gruppe 03 Mo 14 - 16 NM 123
Gruppe 04 Di 10 - 12 NM 103
Gruppe 05 Di 10 - 12 NM 126
Gruppe 06 Di 10 - 12 NM 130
Gruppe 07 Di 14 - 16 NM 126
Gruppe 08 Mi 10 - 12 NM 103
Gruppe 09 Mi 12 - 14 NM 126
Gruppe 10 Do 10 - 12 NM 103
Gruppe 11 Do 10 - 12 NM 130
Gruppe 12 Do 12 - 14 NM 130
Gruppe 13 Do 14 - 16 NM 130
Gruppe 14 Fr 12 - 14 NM 130
Gruppe 15 Fr 14 - 16 NM 130

Aus gegebenem Anlass sehen wir uns verpflichtet auf folgendes hinzuweisen:

Hinweise zu den Übungsabgaben

Hinweise zu den Korrekturen

Übungsgruppeneinteilung

Weitere Informationen folgen.

GL-1 als Modul TIWI für Wirtschaftsinformatiker:

Die Themen "Dynamische Programmierung", "Lineare Programmierung" und "Entscheidbarkeit und Berechenbarkeit" sind nicht Bestandteil des Moduls TIWI.
Auf Übungszetteln wird dies entsprechend berücksichtigt werden, so dass Aufgaben zu diesen Themengebieten entfallen.

Inhalt

Die Vorlesung behandelt fundamentale Algorithmen und allgemeine Methoden für den Entwurf und die Analyse von Algorithmen sowie die NP-Vollständigkeit. Algorithmen für Ordnungsprobleme wie Sortieren und Mischen wie auch Algorithmen für Graphprobleme wie die Berechnung kürzester Wege und minimaler Spannbäume werden beschrieben und analysiert. Algorithmentypen bzw. Entwurfsmethoden wie Greedy-Algorithmen, Teile-und-Beherrsche und dynamisches Programmieren werden eingeführt und angewandt. Das Konzept der NP-Vollständigkeit erlaubt die Untersuchung der algorithmischen Komplexität von Problemen. Die NP-Vollständigkeit des Erfüllbarkeitsproblems und weiterer Berechnungsprobleme wird gezeigt. Abschließend wird ein Ausblick auf die Behandlung komplexer algorithmischer Probleme unter Betonung der Approximationsalgorithmen gegeben. Dazu werden Branch & Bound und Backtracking Verfahren wie auch verschiedene Varianten der lokalen Suche für den Entwurf vorgestellt.

Lernziele:

Die Kenntnis fundamentaler Algorithmen sowie die Fähigkeit, den Prozess des Entwurfs und der Analyse von Algorithmen eigenständig durchführen zu können.

Literatur

Klausur

Hauptklausur: 26.02.2019, 09:00 - 12:00, Hörsaal V (römisch 5) und Hörsaal VI (römisch 6)
Nachklausur : TBA

Die Klausur ist bestanden, wenn mindestens 50% aller in ihrem Klausurteil erreichbaren Punkte erzielt wurden.
Zur Benotung werden neben dem Klausurergebnis Bonuspunkte aus den Übungen mit einem Maximalgewicht von 10% eingehen.

Ressourcen

Materialien für Studierende befinden sich hier.