Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / SS 2016 / Algorithmen und Datenstrukturen


Inhaltsbereich

Algorithmen und Datenstrukturen

Vorlesung, 3-std., Di 8-10 Uhr, Mi 16-18 Uhr, Hofmann, Barth; Übungen, 2-std., Jost, Kaltenthaler

Aktuelles


Inhalt

Die Vorlesung führt in grundlegende Algorithmen und Datenstrukturen ein, welche in fast allen Gebieten der Informatik und verwandten Disziplinen Anwendung finden. Wir lehnen uns eng an das Lehrbuch von Cormen et al. an, das mit mehreren Exemplaren in der Bibliothek vorhanden ist.

Gliederung (vorläufig)

  • Einführung
    • Sortieren durch Einfügen
    • Sortieren durch Mischen
    • O-Notation
    • Lösen asymptotischer Rekurrenzen
  • Sortier- und Suchverfahren
    • HeapSort
    • QuickSort
    • Sortieren in Linearzeit
    • Selektion
  • Datenstrukturen
    • Hashtabellen
    • Binäre Suchbäume
    • Disjunkte Mengen
  • Entwurfsprinzipien
    • Dynamische Programmierung
    • Greedy Algorithmen
    • Amortisierungs-Analyse
  • Graphalgorithmen
    • Minimale Spannbäume
    • Kürzeste Wege
    • Flüsse in Netzwerken

Organisation

  • Umfang: 3+2 Semesterwochenstunden
  • Vorlesung: Prof. Martin Hofmann, Stephan Barth
  • Übung: Dr. Steffen Jost, Daniel Kaltenthaler
     

    Hinweise zum Übungsbetrieb

    Das neue Übungsblatt wird wöchentlich per UniWorX herausgegeben. Die Abgabe zur Korrektur erfolgt ebenfalls per UniWorX. Die Bearbeitungszeit der Hausaufgaben beträgt in der Regel eine Woche. 

    Für die Teilnahme an einem der 10 Übungsgruppentermine ist ab Semesterbeginn, eine gesonderte Anmeldung über UniWorX notwendig. Dies soll sicherstellen, dass alle Termine gleichmässig ausgelastet werden und alle die gleiche Chance haben, Ihren Wunschtermin zu bekommen. Zur reinen Abgabe von Hausübungen ist eine Anmeldung zu einem der Übungsgruppentermine nicht notwendig.

    Die Übungen werden nach dem Kleingruppenkonzept abgehalten, d.h. die neuen Übungsblätter müssen nicht vorbereitet werden - als Vorbereitung reicht es aus, vorausgegangenen Vorlesungen aufmerksam gefolgt zu sein. Zu Beginn der Übung werden die Hausaufgaben des letzten Übungsblattes besprochen, falls trotz per UniWorX zur Verfügung gestellter Musterlösung noch Fragen vorhanden sind. Danach werden die mit A nummerierten Aufgaben in Gruppen zu 2-5 Studenten in eigenem Tempo bearbeitet. Der Tutor beantwortet lediglich individuell dabei aufkommende Fragen.

    Die mit H nummerierten Hausaufgaben sollten möglichst einen Tag später dann von jedem Studenten alleine bearbeitet werden. Die Hausaufgaben sind meist vereinfachte Varianten der A-Aufgaben. Wegen dem Klausurbonus müssen die Hausaufgaben ausschliesslich alleine bearbeitet werden. Abschreiben führt zum Ausschluß.


Zeit und Ort

Veranstaltung Zeit OrtBeginn
Vorlesung Di, 8–10 c.t. Geschw.-Scholl-Pl. 1 (B), B 201 12.04.2016
Vorlesung Mi, 16–18 c.t. Geschw.-Scholl-Pl. 1 (B), B 201 13.04.2016
Übung Mo 14-16 c.t. Amalienstr. 73A, 112 18.04.2016
Übung Mo 16-18 c.t. Amalienstr. 73A, 112
Übung Mo 16-18 c.t. Theresienstr. 39, B004
Übung Mo 18-20 c.t. Amalienstr. 73A, 220
Übung Di 14-16 c.t. Amalienstr. 73A, 220 19.04.2016
Übung Di 16-18 c.t. Amalienstr. 73A, 020
Übung Di 18-20 c.t. Amalienstr. 73A, 220
Übung Do 10-12 c.t. Amalienstr. 73A, 220 21.04.2016
Übung Do 12-14 c.t. Amalienstr. 73A, 220
Übung Fr 12-14 c.t. Amalienstr. 73A, 220 22.04.2016

Planung

Da die Vorlesung trotz der zwei wöchentlichen Vorlesungstermine insgesamt nur den Umfang von 3 SWS hat, findet die Vorlesung nicht an allen Terminen statt. Die Übungen finden durchgehend wöchentlich statt. Die momentane Planung ist wie folgt, kann jedoch jederzeit geändert werden (RSS-Feed beachten):

Nr.DatumThemaKapitelDozent
1. 12.4. Sortieren durch Einfügen 2.1 MH
2. 13.4. Sortieren durch Mischen, O-Notation 2.3.1, 3.1 MH
3. 19.4 Master-Methode, Heapsort 4.3, 6.1-6.4 MH
4. 20.4. Prioritätsschlange, Quicksort  6.5, 7.1-7.3 MH
26.4.
27.4.
3.5.
4.5.
5. 10.5. Vergleichskomplexität, Max/Min, Selektion 8.1, 9.1-3 MH
6. 11.5. Binäre Suchbäume, AVL-Bäume, B-Bäume 12.1-3, 18.1-3 MH
17.5. (Pfingstdienstag)
7. 18.5. Rot-Schwarz-Bäume als spezielle B-Bäume 13.1-3 SB
24.5.
25.5.
8. 31.5. Hashtabellen: Kollisionsauflösung, Divisions- und Multiplikationsmethode 11 MH
9. 1.6. Hashtabellen: offene Adressierung, Lineares- und quadratisches Sondieren 11 MH
10. 7.6. Allgemeine Entwurfs- und Optimierungsmethoden 16.1-3 MH
11. 8.6. Dynamische Programmierung, Längste gemeinsame Teilfolge 15 MH
12. 14.6. Amortisierte Komplexität, Union-Find 22.1 SB
13. 15.6. Amortisierte Komplexität von Union-Find 22.1 SB
14. 21.6. Breitensuche, Tiefensuche, Zerlegung in Zusammenhangskomponenten 22.2-5 MH
15. 22.6. Minimale Spannbäume, Algorithmen von Kruskal und Prim 22.5., 23 SB
16. 28.6. Algorithmus von Dijkstra MH
17. 29.6. Algorithmen von Bellman-Fort und Floyd-Warshall MH
18. 5.7. Flüsse in Netzwerken MH
19. 6.7. Ford-Fulkerson Algorithmus, Bipartite Matchings MH
20. 12.7. Edmonds-Karp Algorithmus MH
21. 13.7. Wiederholung & Fragestunde MH

Materialien

  • Vorlesungsfolien und Dateivorlagen finden Sie auf der Material Unterseite, welche auch einen RSS-Feed anbietet.
  • Übungsblätter und Lösungen erhalten Sie per UniWorX.
  • Für Fragen zum Stoff gibt es ein Forum zu dieser Veranstaltung auf die-informatiker.net.

Literatur

  1. Vorlesungslehrbuch: Cormen, Stein, Leiserson, Rivest. Introduction to Algorithms. 2nd edition, MIT Press, 2001. (Deutsche Version bei Oldenbourg 2004.)
  2. Ottmann. Algorithmen und Datenstrukturen. Spektrum, 2012.

 


Prüfung

Klausur

  • Termin: Freitag 29.07.2016, 9 bis 12 Uhr (Bearbeitungszeit 120min)
  • Anmeldezeitraum: bis 14.07.2016 
  • Ort & Raumeinteilung: Die Klausur fand im Hauptgebäude der LMU statt.
  • Klausureinsicht: siehe Termineintrag
     

Nachklausur

  • Termin: 19.10.2016 18:00-21:00
  • Anmeldezeitraum: 1.9.2016 bis 30.9.2016
  • Ort & Raumeinteilung: Die Klausur findet im Hauptgebäude der LMU statt. Die Raumeinteilung erfolgt nach dem Anfangsbuchstaben Ihres Nachnamens. Es gilt der für Sie bei UniworX eingetragene Nachname, auch wenn dort ein Fehler vorliegen sollte, z.B. Vor- und Nachname in UniworX vertauscht sind.
    WerWo
    Teilnehmer mit Nachteilsausgleich B 101
    A - J B 101
    K - Ng M 018
    Nh - Z B 201
  • Klausureinsicht: (steht noch nicht fest)
     

Hinweise zu den Klausuren

  • Eine rechtzeitige Klausuranmeldung per UniWorX ist zur Teilnahme zwingend erforderlich; eine Abmeldung ist bis 1 Woche vor der Klausur ebenfalls per UniWorX möglich.
  • Man darf sich auch zur Nachklausur anmelden, ohne zuvor an der Erstklausur teilgenommen zu haben. Wer dies tut, verzichtet damit aber automatisch auf die Möglichkeit zur zügigen Klausurwiederholung, d.h. es wird von uns keine dritte Klausur mehr angeboten. Wer bei der Nachklausur durchfällt, kann diese Prüfung also erst wieder nach der nächsten regulären Wiederholung dieser Veranstaltung versuchen.
    Hinweis: Es kann natürlich sein, dass die für Sie gültige Prüfungsordnung die Wiederholunsgsversuche einschränkt. Dies wird durch Ihr Prüfungsamt kontrolliert, nicht durch uns. Wir melden die Noten lediglich ans Prüfungsamt weiter. Wenden Sie sich bei Fragen zur Ihrer Studienordnung an den für Sie zuständigen Studiengangskoordinator.
  • Jeder Teilnehmer muss einen gültigen Lichtbildausweis und seinen Studentenausweis mitbringen.
  • Gehen Sie rechtzeitig vor Beginn in den Ihnen zugewiesenen Raum! Die Raumeinteilung wird 1-2 Tage vor der Klausur oben angegeben.
  • Es sind keine Hilfsmittel zugelassen. Am Platz darf sich nur Schreibzeug und eventuell ein paar Nahrungsmittel befinden. Papier wird von uns gestellt und darf nicht mitgebracht werden. Taschen und Jacken müssen vorne an der Tafel abgelegt werden. Sollte jemand ein Telefon, mp3-Player, oder Ähnliches am Platz haben, ist das ein Täuschungsversuch, der dem Prüfungsausschuss gemeldet wird. Sollte ein Telefon klingeln, ist das eine Störung des Prüfungsablaufs und hat den Ausschluss von der weiteren Teilnahme zur Folge.
  • Teilnehmer mit Nachteilsausgleichbescheinigungen müssen uns vor Ablauf der Anmeldefrist formlos per eMail darüber informieren, so dass wir die entsprechenden Anforderungen gewähren können.
  • Alle behandelten Themen dieser Veranstaltung können in den Klausuren abgefragt werden.
     

Hausaufgabenbonus

      • Einige Hausaufgaben sind mit Punkten gekennzeichnet, welche durch sinnvolle Bearbeitung und Abgabe per UniWorX gesammelt werden können. Mit diesen Punkten kann ein Bonus auf die Klausurnote erzielt werden: Wer die Klausur bestanden, aber noch nicht die volle Punktzahl erzielt hat, kann die Klausurnote durch diesen Bonus verbessern. Der Bonus beeinflusst also nicht, ob man bestanden hat oder durchgefallen ist. Wer x% der Summe aller Hausaufgabenpunkte erzielt hat, erhält x% der maximalen Klausurbonuspunktzahl. Die Klausurbonuspunktzahl erlaubt eine Verbesserung um ca. zwei Notenstufen.
      • Da die Klausur eine Einzelleistung sein muss, und der Hausaufgabenbonus zur Klausur zählt, sind die Hausaufgaben ausschließlich alleine zu bearbeiten! Falls unser System ein Abschreiben entdeckt, kann Ihnen bereits im ersten Fall der gesamte Klausurbonus gestrichen werden, in schweren Fällen kann es auch zum Nichtbestehen des gesamten Moduls kommen. Weitere Details finden Sie unter www.medien.ifi.lmu.de/lehre/Plagiate-IfI.pdf
      • Der Klausurbonus gilt für jede unserer beiden Klausuren im aktuellen Semester (unabhängig von der Teilnahme an der jeweils anderen Klausur). Der Bonus verfällt für alle späteren Wiederholungen in anderen Semestern. Der Klausurbonus errechnet sich selbstverständlich aus allen Übungsblättern, die Hausaufgaben mit Punkten enthalten, ggf. auch dem letzten Übungsblatt.

 

 

Artikelaktionen


Funktionsleiste