Vorlesung: Theoretische Informatik 1 (B-GL1) (WS 2016/2017)

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

  • Die Ergebnisse der Nachklausur sind da!
  • Wer mindestens 50% der maximalen Klausurpunkte für die entsprechende Variante erreicht hat, hat die Klausur bestanden. Die Grenze von 50% wird, auch nach der Klausureinsicht, nicht herabgesetzt.
  • Klausureinsicht ist am Freitag, den 21.04.2017, von 14 - 16 Uhr in Raum 307. Abweichende Termine auf Anfrage, aber nicht vor dem 18.4.2017
  • Die Klausur und Musterlösung sind nun online.
  • Die Ergebnisse der Klausur sind da!
  • Wer mindestens 45% der maximalen Klausurpunkte für die entsprechende Variante erreicht hat, hat die Klausur bestanden.
  • Klausureinsicht ist am Freitag, den 17.02.2017, von 12 - 14 Uhr in Raum 311. Abweichende Termine auf Anfrage.
  • Die Klausur und Musterlösung sind nun online.

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)

Fragestunde zu den Übungsaufgaben mit Frederik Harwath und Ronja Düffel (Büro 1 bzw. im Lernzentrum)

Übungsbetrieb

David Veith, M.Sc.
Sprechzeiten: Immer, wenn im Büro anzutreffen und nach Vereinbarung.
Fragen rund um die Vorlesung bitte an gl116-support@ae.cs.uni-frankfurt.de

Die Übungsgruppen beginnen ab Mittwoch, den 26.10.2016, 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

Aus gegebenem Anlass sehen wir uns verpflichtet auf folgendes hinzuweisen:

Hinweise zu den Übungsabgaben

Ü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: 14.02.2017, 09:00 - 12:00, Hörsaal V (römisch 5) und Hörsaal VI (römisch 6)
Nachklausur : 04.04.2017, 09:00 - 12:00, Details werden noch bekannt gegeben.

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.