Theoretische Informatik 1 (WS 2016/2017)

Vorlesung

Prof. Dr. Ulrich Meyer

Dienstag 08:00 - 10:00
Donnerstag 08:00 - 10:00
Hörsaal H V (Jügelhaus/Hörsaalgebäude)

QIS

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

  • Montag, 13:00 – 16:00
  • Dienstag, 10:00 – 12:00 und 14:00 – 16:00

Ü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

Gruppe 1Mo. 10:00 - 12:00NM 117Tobias Kapetanopoulos
Gruppe 2Mo. 12:00 - 14:00NM 114Joshua Sole
Gruppe 3Di. 10:00 - 12:00NM 117Noleen Köhler
Gruppe 4Di. 12:00 - 14:00H 15Robert Jabs
Gruppe 5Di. 14:00 - 16:00NM 117Tim Ingelfinger
Gruppe 6Mi. 12:00 - 14:00NM 117Julian Lorenz
Gruppe 7Mi. 14:00 - 16:00NM 117Marcus Klötzl
Gruppe 8Do. 12:00 - 14:00NM 123Aleksey Koschowoj
Gruppe 9Do. 14:00 - 16:00NM 117Hung The Tran
Gruppe 10Fr. 14:30 - 16:00H 16Philipp Reusch

Aus gegebenem Anlass sehen wir uns verpflichtet auf folgendes hinzuweisen:

  • Ein Wechsel der zugeteilten Übungsgruppe für die Abgabe ist NICHT möglich!
  • Wenn Abgaben mit der falschen Gruppennummer abgegeben werden, wird die Abgabe ab Blatt 2 mit 0 Punkten gewertet.

Hinweise zu den Übungsabgaben

  • Die Abgabe der Übungen hat stets bis zu Beginn der Vorlesung zu erfolgen.
  • Eine Abgabe via E-Mail ist nur in Ausnahmefällen (z.B. Krankheit) möglich.
  • Der Tutor ist nicht verpflichtet schwer lesbare Abgaben zu korrigieren.
  • Wir stellen eine LaTeX Vorlage zur Verfügung.
  • Abgaben ohne vollständigen Namen, Matrikelnummer und Gruppennummer werden nicht korrigiert.
  • Mehrseitige Übungsabgaben sind zu tackern.
  • Jedes(!) Blatt ist mit dem vollständigen Namen, Matrikelnummer und Gruppennummer zu versehen.
  • Wenn festgestellt wird, dass eine Aufgabe abgeschrieben wurde, dann…
    • … gibt es beim ersten Mal für alle Beteiligten 0 Punkte auf die Aufgabe.
    • … gibt es beim zweiten Mal für alle Beteiligten 0 Punkte auf die gesamte Abgabe.
    • … wird beim dritten Mal allen Beteiligten die Bonifikation sowohl für die Erst- als auch die Zweitklausur aberkannt.
  • Sie dürfen in Gruppen über die Aufgaben diskutieren und zusammen Lösungswege erarbeiten (es ist sogar empfohlen). Jedoch muss jeder Student in der Abgabe die Lösung selbst schreiben und somit erkennbar machen, dass der Lösungsweg verstanden wurde. Im Zweifelsfall kann der Tutor verlangen, dass Sie eine Lösung vorrechnen. Sind Sie im Tutorium gar nicht anwesend, so kann der Tutor die Punkte vom Übungsblatt aberkennen.

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

  • J. Kleinberg und E. Tardos, Algorithm Design, Pearson Education Limited 2013, ISBN 1292023945
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest und C. Stein, Introduction to Algorithms, Third Edition, The Mit Press 2009, ISBN 0262533057 (4. deutsche Auflage: 3486748610)

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.

Materialien

Folien

Klickerfolien und weitere Materialien

Videoaufzeichnungen

Die Videoaufzeichnungen der Vorlesung stehen hier zur Verfügung.

Übungsblätter

Wenn keine Übungsblätter besprochen werden, finden in den Tutorien Wiederholungsstunden statt. Änderungen an den Ausgabeterminen vorbehalten.

Frühere Klausuren

Klausuren vergangener Semester finden Sie hier.

Weitere Materialien

  • Es steht das Skript von Herrn Prof. Dr. G. Schnitger zum download bereit, an dem sich diese Veranstaltung orientiert.