AG Algorithmen und Komplexität
>

Sommersemester 2017

Sebastian bietet im Sommersemester 2017 die Vorlesungen Advanced Algorithmics an.


 

Übungen

Anmeldung
Prozedere
Übungstermine
Zusatzangebot
Übungsblätter
Zusatzmaterial

Anmeldung

Die Verwaltung der Übungsgruppen findet in OLAT statt.

Achtung: Eine Anmeldung (im richtigen Track) ist unbedingt nötig, wenn eine Zulassung erworben werden soll! Teilnehmer aus dem Track AI, die noch nicht die Beweistechniken bestanden haben, melden sich hierfür bitte zusätzlich an.

Hinweis: Melden Sie sich bitte auch an, wenn Sie nicht am Übungsbetrieb teilnehmen möchten, etwa weil Sie die Zulassung schon früher erworben haben; wir haben hierfür Pseudogruppen "Keine" vorgesehen. Dies erleichtert uns die Verwaltung eben dieser vorhandenen Zulassungen und Ihnen die Prüfung, um Missverständnisse und Fehler zu vermeiden.

Prozedere

Die Auswahl der Übungs- und Klausuraufgaben richtet sich nach dem belegten Modul. Hierfür teilen wir die Teilnehmerschaft in Track ε (Inf, Math) und Track AI (AI, WII) ein; Studenten aus anderen Studiengängen halten bitte mit uns Rücksprache. Bitte achten Sie unbedingt darauf, die richtigen Übungen zu besuchen!

Unser Ziel ist, möglichst viel individuelles Feedback zum Fähigkeitsstand zu bieten. Im Idealfall würden also alle Teilnehmer Lösungen zu so vielen Aufgaben wie möglich selbst aufschreiben und eine detaillierte Korrektur nach Klausurmaßstäben zurückbekommen. Leider können wir das personell nicht stemmen und müssen daher Kompromisse eingehen.

Es gibt Basis- und Aufbauaufgaben. Erstere zielen in der Regel darauf ab, grundlegende technische Fertigkeiten zu üben, wohingegen Letztere über Anwendung und Transfer des Gelernten dem tieferen Verständnis dienen sollen. Die Basisaufgaben werden einzelnabgegeben, die Aufbauaufgaben in Vierergruppen. Wir formalisieren das wie folgt:

  • Jeder Teilnehmer gibt von jedem Übungsblatt (genau) eine Basisaufgabe ab.
  • Die Mitglieder einer jeden Abgabegruppe (je vier Teilnehmer) geben unterschiedliche Basisaufgaben ab. Doppelabgaben werden nicht gewertet.
  • Jede Abgabegruppe gibt von jedem Blatt beliebig viele Aufbauaufgaben ab.
  • Von den Punkten auf Basisaufgaben müssen insgesamt 50% der Grundgesamtheit erreicht werden; diese ergibt sich aus der Summe der mittleren Basispunktzahl über alle Blätter. Das Mittel pro Blatt wird stets bei drei Punkten liegen und wir rechnen mit 13 Blättern, womit voraussichtlich 19 Punkte erreicht werden müssen.
    Es wird in der Zwischenklausur die Möglichkeit geben, bis zu fünf Basispunkte zu erwerben.
  • Von den Punkten für Aufbauaufgaben müssen 20% aller Aufbaupunkte (des jeweiligen Tracks) erreicht werden. Erreichte Punkte zählen natürlich für jedes Abgabegruppenmitglied gleichermaßen.

Die genauen Zulassungsvoraussetzungen finden Sie hier.

Termine

Lösungen zu den Basisaufgaben werden in einer zentralen Saalübung präsentiert. Diese findet ab der zweitenVorlesungswoche immer

Dienstags, 15:30 Uhr in 52-207

statt; bitte beachten Sie die Ausnahmen am 12., 19. und 26. November wie im KIS angegeben.

Achtung: am Dienstag, den 11.02.2014 findet um 15:30 Uhr in 48-208 eine weitere Saalübung statt, in der Aufgabe 3 der Zwischenklausur besprochen wird.

Die Termine und Orte der Kleingruppenübungen entnehmen Sie bitte den untenstehenden Tabellen. In diesen Stunden werden die Aufbauaufgaben besprochen.

Nr.TagZeitTutorRaum
ε1 Dienstag 11:45 Jan Bormann 46-268
ε2 Mittwoch 13:45 Jan Bormann 46-280
ε3 Donnerstag 11:45 Jan Bormann 56-230
ε5 Mittwoch 15:30 Johannes Freiermuth 48-462
ε6 Donnerstag 10:00 Lars Hüttenberger 13-370
ε7 Donnerstag 11:45 Lars Hüttenberger 13-305
ε8 Dienstag 11:45 Lisa Jöckel 48-379
ε9 Mittwoch 15:30 Lisa Jöckel 48-379
ε10 Mittwoch 13:45 David Wahl 57-165
ε11 Mittwoch 15:30 David Wahl 56-232
Nr.TagZeitTutorRaum
AI1 Mittwoch 08:15 Olaf Diether 48-379
AI2 Mittwoch 10:00 Olaf Diether 48-654
AI3 Dienstag 15:30 Markus Löwenstein 56-232
AI4 Donnerstag 11:45 Markus Löwenstein 56-232
AI5 Donnerstag 15:30 Elisabeth Neumann 48-654
AI6 Donnerstag 10:00 David Wahl 48-654

Zusatzangebot

Unsere Übungsleiter bieten in der Vorlesungszeit zu mehreren Terminen eine Lern- bzw. Arbeitsbetreuung an. Wenn also im Zuge der Vor- und Nachbereitung der Vorlesung oder beim Bearbeiten der Übungen Fragen aufkommen, finden Sie zu den folgenden Zeiten im jeweils ausgezeichneten Terminalraum des SCI Unterstützung:

  • Montag, 15:30 - 17:00 Uhr (48-231),
  • Dienstag, 13:45 - 15:15 Uhr (48-231),
  • Mittwoch, 17:15 - 18:45 Uhr (48-231) und
  • Donnerstag, 15:30 - 17:00 Uhr (48-211).

Eine Anmeldung ist nicht nötig; wer kommt, der kommt.

Nach Ende der Vorlesungszeit haben wir bis zur Abschlussklausur täglich von 10:00 - 17:00 Uhr den Raum 48-462 reserviert. Dort können Sie sich gemeinsam in Laufnähe zum Getränke- und Snackangebot der Fachschaft auf die Klausur vorbereiten.

In den 2 Wochen vor der Klausur (10.–21.02.) ist Sebastian Wild jeweils Mo, Mi und Fr von 10 bis 12 Uhr im Lernraum 48-462 für Sie da. Neben allgemeinen Fragen und Hinweisen hat jeder Termin ein Schwerpunktthema. Anhand einer ausgewählten Altklausur-Aufgabe besprechen wir u.a. die Richtlinien für unsere Korrektur.

Termin          Schwerpunktthema Musteraufgaben                                         
Mo 10.02. Asymptotiken Aufgabe 1, Aufgabe 2
Mi 12.02. Rekursionsgleichungen Aufgabe 1, Aufgabe 2
Fr 14.02. Beweisen oder Widerlegen? Aufgabe 1, Aufgabe 2
Mo 17.02. Komplexitätstheorie

Aufgabe 1, Aufgabe 2, Aufgabe 3

Mi 19.02. Algorithmenentwurf 1 Aufgabe 1, Aufgabe 2
Fr 21.02. Algorithmenentwurf 2 Aufgabe 1, Aufgabe 2

 

Übungsblätter

Die Übungsblätter werden in der Regel donnerstags in der Vorlesung herausgegeben – Reste liegen im SCI aus – und sind am jeweils übernächsten (Vorlesungszeit)Freitag fällig. Die genaue Abgabezeit entnehmen Sie bitte dem jeweiligen Übungsblatt.

Vorkenntnistest Track ε Track AI  
Blatt 1 Track ε Track AI  
Blatt 2 Track ε und AI *
Blatt 3 Track ε Track AI *
Blatt 4 Track ε Track AI *
Blatt 5 Track ε und AI *
Blatt 6 Track ε Track AI *
Blatt 7 Track ε Track AI  
Blatt 8 Track ε Track AI  
Blatt 9 Track ε und AI *
Blatt 10 Track ε Track AI
Blatt 11 Track ε Track AI
Blatt 12 Track ε und AI  
Blatt 13 Track ε Track AI

* Geändert seit Ausgabe in der Vorlesung.

Zusatzmaterial

  • Why Generating Functions Rule
    Ein kleiner Überblick darüber, wie und warum Erzeugendenfunktionen funktionieren. "Lücken" im formal-mathematischen Gefüge werden benannt und diese schließende Literatur angegeben.
  • Rechenregeln für Grenzwerte von Quotienten
    Zum asymptotischen Vergleich von Funktionen bestimmen wir gerne Grenzwerte von Quotienten von Funktionen. Hierfür gibt es einige "Rechenregeln", die zum Teil in unpräziser Form überliefert sind. Einige bieten wir hier in sauber bewiesener Form – soll heißen, bitte teilen Sie uns Fehler mit! – an.
  • Self-Deceit Sheet
    Dies ist eine in Anlehnung an das TCS Cheat Sheet benannte Sammlung von Fehlern, die frühere Teilnehmer in Klausuren gemacht haben. Sie soll nicht der humoristischen Erbauung auf Kosten Anderer dienen – unter Klausurbedingungen passieren die komischsten Dinge, das weiß jeder – sondern ein Werkzeug zur Klausurvorbereitung sein. Vielleicht ist doch der ein oder andere Eintrag zu finden, zu dem man sich auch hätte hinreißen lassen?