Algorithmen und Datenstrukturen im SS 2017

Aktuelles

• Die Einsicht zur Nachholklausur findet am 15.11. von 10:00-12:00 Uhr im Raum 157 in der Oettingenstraße 67 statt.
• Die Nachholklausur findet am 05.10.2017 von 14:00-16:00 in den Räumen A 240 (A-G), M 218 (H-O) sowie M 118 (P-Z) im Hauptgebäude statt.
• Die Einsicht wird am 19.09.2017 in Raum 157 in der Oettingenstraße stattfinden. Um die Wartezeit etwas zu reduzieren, werden Sie nach folgendem Hashverfahren zeitlich verteilt:
  • Zeitslot = Länge(1. Vorname) * Länge(1. Nachname) mod 5
  • Slot 0: 9:00 Uhr - 9:30 Uhr
  • Slot 1: 9:30 Uhr - 10:00 Uhr
  • Slot 2: 10:00 Uhr - 10:30 Uhr
  • Slot 3: 10:30 Uhr - 11:00 Uhr
  • Slot 4: 11:00 Uhr - 11:30 Uhr
• Die Übungen am 20.7. von 10 bis 14 Uhr in der Edmund-Rumpler-Straße fällt aus. Stattdessen besuchen die betroffenen Studenten bitte die parallele Übung in der Amalienstraße.
• UniWorX ist wieder verfügbar. Bitte kontrollieren Sie Ihre Klausuranmeldungen. Vor allem für Anmeldungen im kritschen Interval Sonntag-Montag sollten geprüft werden.
• UniWorX scheint gerade nicht erreichbar zu sein. Für den Übungsablauf:
  

Bitte schauen Sie nach, ob bis 12 Uhr wieder eine Abgabe möglich ist. Falls nicht, werde ich die Abgabe auf 14 Uhr verlängern. Plan C ist noch in der Bearbeitung.
Der Fehler scheint kurzfristig nicht behebbar zu sein. Daher wird Blatt 10 nicht bewertet werden. Es tut uns Leid, falls Sie sich mit diesem Blatt besonders viel Mühe gegeben haben, aber dies ist die in unseren Augen fairste Variante. Das Blatt wird dennoch in den Übungen vorgerechnet und ist klausurrelevant. Hier nochmal das Aufgabenblatt:
u10.pdf

• Da der Prim-Algorithmus noch nicht in der Vorlesung vorkam, wird die Aufgabe 10-1-e auf die nächste Woche verschoben. Gerne können Sie diese Aufgabe schon diese Woche erledigen, es wird dann aber erst auf Blatt 11 bewertet. Denken Sie daher daran, die Aufgabe bei Abgabe 11 einzureichen.
• Die Klausur wird am 08.08.2017 (Dienstag) ca. zwischen 17 und 20 Uhr im Hauptgebäude stattfinden.
• Für die Bearbeitung der Übungen wird ein Klausurpunktebonus gewährt, der maximal 10% der Klausurpunkte bei 100% zu erreichender Übungspunkte beträgt. Dieser wird nur dann angerechnet, wenn die Klausur ohne diesen Bonus als bestanden gilt.
• Geben Sie in Gruppen von zwei bis drei Personen ab. Wenn Sie Probleme mit der Teambildung haben, dann besteht am Dienstag nach der Vorlesung die Moglichkeit, die Räumlichkeit als Forum für die Suche weiterer Personen zu nutzen. Falls Sie dennoch das erste Ubungsblatt alleine abgeben, werden wir Sie mit den verbleibenden einzeln abgebenden Studenten zufallig gruppieren. Ab dem zweiten Blatt sollte jeder eine Abgabegruppe haben, daher werden wir ab dann keine Einzelabgaben mehr korrigieren.
• Da am Montag, 1.5. Feiertag ist, gibt es die erste Übung ab heute zum Download in UniWorX.
• Sie können die Abgabe in UniWorX mit einem Testabgabenblatt üben. Dies ist nicht obligatorisch.

Inhalt

In der Vorlesung wird der Entwurf effizienter Algorithmen für die Bereiche Suchen, Sortieren sowie Graphmethoden behandelt. Besonderer Schwerpunkt liegt hierbei auf allgemeinen algorithmischen Techniken, wie etwa divide-and-conquer, lokal-optimierender Berechnung ("greedy methods"), backtracking, branch-and-bound sowie dynamischer Programmierung.

In den Übungen können Konzepte durch Java-Programmierbeispiele und -aufgaben vertieft werden. Daher werden Basiskenntnisse in Java-Programmierung empfohlen.

Organisation

• Umfang: 3+2 Semesterwochenstunden
• Vorlesung: Prof. Dr. Thomas Seidl
• Übungsleiter: Florian Richter, Daniel Kaltenthaler, Johannes Lohrer, Markus Mauder

• Tutoren/Korrektoren: Dominik Acker, Isabella Galter, Georg Hagemann, Daniel Hämmerle, Martin Pletl, Sabrina Richter, Simon Schäfer, Maximilian Schwarzfischer, Alina Uhrmann, Adrian Westermeier

• Für: Studierende der Informatik, Medieninformatik und Bioinformatik im Bachelor-Studium

Zeit und Ort

Planung

Übungsbetrieb

Nachholklausur

• Die Klausur findet Dienstag, den 05.10.2017 14-16 Uhr statt.
• Zur Teilnahme an der Klausur ist eine rechtzeitige Anmeldung per UniWorX notwendig.
• Die Aufteilung auf die Hörsäle erfolgt nach dem ersten Buchstaben des Nachnamens:
  • A - G → A 240
  • H - O → M218
  • P - Z → M 118

Klausur

• Die Klausur findet Dienstag, den 08.08.2017 17-20 Uhr statt.
• Zur Teilnahme an der Klausur ist eine rechtzeitige Anmeldung per UniWorX notwendig.
• Die Aufteilung auf die Hörsäle erfolgt nach dem ersten Buchstaben des Nachnamens:
  • A - E → B 101
  • F - J → B 201
  • K - L → M 218
  • M - R → Audimax
  • S → N 120
  • T - Z → A 140

Alle Räume befinden sich im Hauptgebäude.
Hinweis: Diese Zuweisung ist eine Hashfunktion. Wir bilden einen (theoretisch unendlich großen) Wertebereich auf eine 6-elementige Zielmenge ab. Denken Sie als Vorbereitung mal darüber nach, welche Eigenschaften diese Funktionen erfüllt (z.B. Clusterbildung, Gleichverteilung, ...).

Klausur-FAQ:

• Q: Ist eine Notenverbesserung möglich?

Dies ist von der Prüfungsordnung abhängig. Ihr jeweiliges Prüfungsamt regelt dies. Lesen Sie dazu in Ihrer gültigen Prüfungsordnung nach oder erfragen Sie dies bei den zuständigen Stellen.

• Q: Muss man sich zur ersten Klausur anmelden? Kann man auch die zweite Klausur mitschreiben?

Sie können sich auch ausschließlich zur zweiten Klausur anmelden, sobald ein Termin für diese feststeht.

• Q: Kann man die Klausur entwerten?

Auch dies ist in der Prüfungsordnung geregelt. Daher können wir dies nicht im Allgemeinen beantworten. Wir bieten ein Feld zum Entwerten in der Klausur an, aber dies erlaubt das Entwerten nicht pauschal. Falls Ihre Prüfungsordnung ein Entwerten nicht vorsieht und Sie dennoch unterschreiben, so wird Ihre Klausur wie ein Fehlversuch mit allen Konsequenzen einer 5.0 gewertet. Informieren Sie sich bitte vorher darüber in der Prüfungsordnung oder beim für Sie zuständigen Prüfungsamt.

• Q: Müssen die Quellcodes der Algorithmen auswendig gelernt werden?

Nein, eine sprachenspezifische Implementation auswendig zu lernen ist nicht sinnvoll in den meisten Fällen. Es gibt vielleicht ein paar Studenten unter Ihnen, die sich so am besten die Algorithmen merken können. Für den Rest macht es aber mehr Sinn, den Algorithmus in seiner konzeptuellen Wirkungsweise und Ablauf so zu lernen, dass Sie ihn (a) auf einer Eingabe anwenden können und (b) mit verwandten Algorithmen vergleichen und Unterschiede aufzeigen können. Insbesondere sind Randfälle interessant (Wann arbeitet der Algorithmus besonders gut/schlecht? Welche Eingabe und welche Parameter werden gebraucht? Laufzeiten? ...).

• Q: Gibt es alte Klausuren?

Bestimmt irgendwo. Aber nicht hier und auch nicht auf Anfrage bei uns.

• Q: Wann ist die Nachholklausur?

Wird noch bekannt gegeben. Aber schreiben Sie doch erstmal die normale Klausur.

Sonstiges

• Als Zusatzliteratur oder Nachschlagewerk können folgende Werke empfohlen werden:
  • Robert Sedgewick: Algorithmen in Java: Grundlagen, Datenstrukturen, Sortieren, Suchen. Teil 1-4 (Pearson Studium)
  • Thomas Ottmann, Peter Widmayer: Algorithmen und Datenstrukturen (Spektrum Lehrbuch)
  • Thomas H. Cormen et al.: Algorithmen - Eine Einführung (Oldenbourg)

• Für Java-Anfänger außerdem empfehlenswert:
  • Matthias Hölzl, Allaithy Raed, Martin Wirsing: Java kompakt: Eine Einfuhrung in die Software-Entwicklung mit Java (Springer) (Universitätsbibliothek-Zugang)

Vorhergehende Semester

SS 15, SS 14, SS 13, SS 12, SS 11, SS 10, SS 08