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

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

  • Die Ergebnisse der Nachklausur sind da!
  • Wer mindestens 45% der maximalen Klausurpunkte für die entsprechende Variante erreicht hat, hat die Klausur bestanden.
  • Klausureinsicht ist am Freitag, den 15.04.2016, von 12 - 14 Uhr in Raum 311. Abweichende Termine auf Anfrage.
  • Die Nachklausur 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 04.03.2016, 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)

Übungsbetrieb

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

Die Übungsgruppen beginnen ab Mittwoch, dem 21.10.2015, 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

Hinweise zu den Übungsabgaben

Übungsgruppeneinteilung

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: 16.02.2016, 09:00 - 12:00, Hörsaal V (römisch 5) und Hörsaal VI (römisch 6)
Nachklausur : 05.04.2016, 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 20% eingehen.

Ressourcen

Materialien für Studierende befinden sich hier.