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

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

Am Mittwoch, den 29.03.2017, wird eine erweiterte Fragestunde zur Vorbereitung auf die Nachklausur angeboten.
Die Fragestunde findet von 10:30-12:00 und von 13:00-14:30 in H 16 statt. Sie haben die Möglichkeit, Ihre Fragen vorab bis zum 27.03.2017 an die Supportadresse zu senden.
  • Die Nachklausur wird am 04.04.2017 um 9:00 Uhr (s.t.) beginnnen und in den Hörsälen III (römisch 3), IV (römisch 4) und V (römisch 5) stattfinden.
  • Die Raumaufteilung wird kurz vor der Klausur bekannt gegeben.
  • Alle Studierende, außer Lehrämtler, sind verpflichtet sich über das QIS beim Prüfungsamt für Informatik rechtzeitig für die Klausur anzumelden. Das betrifft auch(!!!) die Mathematiker und Physiker.
  • Es wird drei Varianten der Klausur geben: Eine Variante mit 10 CP für B.Sc./M.Sc. Informatik und B.Sc. Bioinformatik sowie Nebenfächler, eine Variante mit 8 CP für Bioinformatik in der alten Bachelorordnungen (Kapitel über Entscheidbarkeit und Berechenbarkeit entfällt) und eine Variante für das Modul TIWI(siehe unten).
  • Für die Klausur ist als einziges Hilfsmittel ein beidseitig handschriftlich beschriebener DIN-A4 Zettel zugelassen.
  • Es dürfen nur dokumentenechte Stifte in den Farben blau und schwarz verwendet werden.
  • Tipp-Ex und andere Korrekturwerkzeuge sind nicht erlaubt!!! Wenn Textstellen nicht gewertet werden sollen, so sind diese mit einem zugelassenen Stift durchzustreichen. Das Durchstreichen mit einem nicht zugelassenen Hilfsmittel zählt als nicht durchgestrichen!
  • Die in diesem Semester erlangten Bonuspunkte gelten auch für die Zweitklausur.
  • Sicher bestanden hat, wer mindestens 50% der maximalen Klausurpunkte (inklusive Bonus) aus der zutreffenden Klausurvariante erreicht.
  • Wer am Tag der Klausur den Anweisungen zur Sitzordnung nicht Folge leistet, darf die Klausur nicht mitschreiben und wird des Saals verwiesen.
  • Wenn ein Täuschungsversuch vorliegt bzw. beabsichtigt wurde, wird die Klausur sofort als 5.0 gewertet. Bitte nehmen Sie Abstand von Versuchen mit Smartwatches, Handys und anderen elektronischen Hilfsmitteln oder ihrem Nachbarn zu arbeiten.
  • 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.
In der Zeit vom 25.01. bis 31.01.2017 finden in den Tutorien Fragestunden statt. Ausnahme bildet das Tutorium am Freitag, den 27.01.2017. Aus organisatorischen Gründen muss die Freitagsgruppe entfallen.

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.