Search:
Lehrstuhl  |  Institut  |  Fakultät  |  LMU
print

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

  • 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

Veranstaltung Zeit Ort Beginn
Vorlesung Di,   8.30 - 11.00 Uhr Raum B 201 (Hauptgebäude)
25.04.2017
Übung 01 Mo, 14.00 - 16.00 Uhr Raum 220 (Amalienstr. 73A) 08.05.2017
Übung 02 Mo, 16.00 - 18.00 Uhr Raum A 023 (Edmund-Rumpler-Str. 9) 08.05.2017
Übung 03 Mo, 16.00 - 18.00 Uhr Raum 220 (Amalienstr. 73A) 08.05.2017
Übung 04 Mo, 18.00 - 20.00 Uhr Raum 018 (Amalienstr. 73A) 08.05.2017
Übung 05 Di, 14.00 - 16.00 Uhr Raum A U115 (Hauptgebäude) 09.05.2017
Übung 06 Di, 16.00 - 18.00 Uhr Raum Lehrturm-VU104 (Prof.-Huber-Platz 2) 09.05.2017
Übung 07 Di, 18.00 - 20.00 Uhr Raum A 015 (Hauptgebäude) 09.05.2017
Übung 08 Do, 10.00 - 12.00 Uhr Raum 220 (Amalienstr. 73A) 11.05.2017
Übung 09 Do, 12.00 - 14.00 Uhr Raum 220 (Amalienstr. 73A) 11.05.2017
Übung 10 Fr, 12.00 - 14.00 Uhr Raum A U115 (Hauptgebäude) 12.05.2017
Übung 11 Fr, 10.00 - 12.00 Uhr Raum A U115 (Hauptgebäude) 12.05.2017
Übung 12 Mo, 14.00 - 16.00 Uhr Raum A 023 (Edmund-Rumpler-Str. 9) 08.05.2017
Übung 13 Mo, 18.00 - 20.00 Uhr Raum 020 (Amalienstr. 73A) 08.05.2017
Übung 14 Mi, 12.00 - 14.00 Uhr Raum A U115 (Hauptgebäude) 10.05.2017
Übung 15 Mi, 14.00 - 16.00 Uhr Raum A U115 (Hauptgebäude) 10.05.2017
Übung 16 Mi, 16.00 - 18.00 Uhr Raum A U115 (Hauptgebäude) 10.05.2017
Übung 17 Do, 18.00 - 20.00 Uhr Raum D Z005 (Hauptgebäude) 11.05.2017
Übung 18 Do, 12.00 - 14.00 Uhr Raum A 019 (Edmund-Rumpler-Str. 9) 10.05.2017
Übung 19 Do, 10.00 - 12.00 Uhr Raum A 019 (Edmund-Rumpler-Str. 9) 10.05.2017

Planung

Datum Vorlesung Aufgaben Datum Übung
25.04.2017 Kapitel 0: Organisatorisches
Kapitel 1: Grundlagen
Übung
entfällt
Anmeldung
nicht vergessen
!
02.05.2017 Kapitel 1: Grundlagen Blatt 01 28.04.-
08.05.
-
09.05.2017 Kapitel 1: Grundlagen Blatt 02

List.java Lösungsvorschlag List.java

08.05.-
15.05.
Besprechung Blatt 01
16.05.2017 Kapitel 1: Grundlagen
Kapitel 2: Sortieren
Blatt 03

CalcTree.zip Lösungsvorschlag CalcTree.zip

15.05.-
19.05.
Besprechung Blatt 02
23.05.2017 Kapitel 2: Sortieren Blatt 04 22.05.-
26.05.
Besprechung Blatt 03
30.05.2017 Kapitel 3: Suchen in Mengen Blatt 05 29.05.-
02.06.
Besprechung Blatt 04
06.06.2017 entfällt Blatt 06

Lsg. 6-1 Lsg. 6-2

05.06.-
09.06.
Besprechung Blatt 05
13.06.2017 Kapitel 3: Suchen in Mengen Blatt 07 12.06.-
16.06.
Besprechung Blatt 06
20.06.2017 Kapitel 3: Suchen in Mengen Blatt 08

Lsg. 8-1

19.06.-
23.06.
Besprechung Blatt 07
27.06.2017 Kapitel 4: Graphalgorithmen Blatt 09 26.06.-
30.06.
Besprechung Blatt 08
04.07.2017 Kapitel 4: Graphalgorithmen Blatt 10

distance.java
Dijkstra.java
Floyd.java

03.07.-
07.07.
Besprechung Blatt 09
11.07.2017 Kapitel 5: Paradigmen Blatt 11 10.07.-
14.07.
Besprechung Blatt 10
18.07.2017 Kapitel 5: Paradigmen Blatt 12 17.07.-
21.07.
Besprechung Blatt 11
25.07.2017 Kapitel 5: Paradigmen - 24.07.-
28.07.
Besprechung Blatt 12

Ü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)


Vorhergehende Semester

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

blank