Algorithmische Diskrete Mathematik (MA2501)

Vorlesung

Dozent: Prof. Dr. Peter Gritzmann
Übungsleitung: Dr. Michael Ritter, Dipl.-Math. Matthias Silbernagl
weitere Tutoren/Korrektoren: B.Sc. Paul Stursberg, Patricia Rachinger

Aktuelles Termine und Sprechstunden Übungsblätter Notenbonus Literatur FAQ

Aktuelles

  • 9. April 2013: Die nicht abgeholten Hausaufgaben bewahren wir noch bis zum Ende der ersten Vorlesungswoche, also bis Freitag, 19. April 2013 auf. Hausaufgaben, die bis dahin nicht abgeholt wurden, werden (inklusive Schnellhefter) vernichtet.
  • 9. April 2013: Die Klausureinsicht für die Wiederholungsklausur findet diesen Freitag, den 12.4.2013, um 10:00 Uhr im Raum MI 02.06.020 statt. Bitte beachten Sie die Hinweise zur Klausureinsicht weiter unten.
  • 26. März 2013: Die Musterlösung zur Klausur steht hier zum Download bereit.
  • 15. März 2013: Die Anmeldung für die Wiederholungsklausur in TUMOnline ist freigeschaltet. Die Anmeldefrist endet am 25. März 2013.
  • 8. März 2013: Die Klausureinsicht findet am kommenden Mittwoch, 13.3.2013, um 10:00 Uhr im Seminarraum MI 03.08.011 statt. Bitte beachten Sie die Hinweise zur Einsicht weiter unten.
  • 18. Februar 2013: Weiter unten auf dieser Seite finden Sie jetzt Hinweise zur Klausur und die Hörsaal-Aufteilung. Studierende mit den Anfangsbuchstaben A-L des Nachnamens schreiben die Klausur im Hörsaal MW0001, Studierende mit Anfangsbuchstaben M-Z im Hörsaal MW2001.
  • 18. Februar 2013: Die Lösung zur Aufgabe 5.4 wurde korrigiert und etwas ausführlicher dargestellt. Vielen Dank für die Hinweise.
  • 6. Februar 2013: Sollten Sie für die Klausur Anspruch auf einen Nachteilsausgleich haben (beispielsweise in Form einer Prüfungszeitverlängerung), teilen Sie uns das bitte möglichst bald mit, damit wir die Prüfungsaufsicht entsprechend planen können.
  • 03. Februar 2013: Übungsgruppe 2 am 04. Februar 2013 fällt aufgrund von Krankheit aus. Bitte besuchen Sie die zeitgleiche Übungsgruppe 9 in Raum 00.04.017.
  • 01. Februar 2013: Die Bearbeitungspunkte von Hausaufgabenblatt 7 zählen regulär zum Notenbonus.
  • 14. Januar 2013: Korrektur zu Blatt 6: Im Algorithmus in Aufgabe 6.5 muss es im inneren min-Ausdruck %$\xi^{k-1}(u)$% statt %$\xi^{k-1}(v)$% heißen.
  • 8. Januar 2013: Zur Erinnerung: Bitte denken Sie daran, sich für die Klausur auf TUMOnline anzumelden. Die Einschreibung endet in wenigen Tagen am 15. Januar 2013.
  • 12. Dezember 2012: Tutorgruppe 05 findet diesen Donnerstag, den 13.12.12, ausnahmsweise im Raum MW 2250 statt.
  • 9. Dezember 2012: In Aufgabe 4.5a) muss in der modifzierten Breitensuche das gewählte u auch aus U entfernt werden. Eine korrigierte Version des Blatts steht zum Download bereit.
  • 30. November 2012: Am Freitag, den 7.12.2012 findet die Vorlesung noch einmal im Physik-Hörsaal der LMU, Am Coulombwall 1 statt. Wir beginnen wieder um 14:15 Uhr.
  • 19. November 2012: Am Freitag, den 23.11.2012 findet die Vorlesung wegen einer Veranstaltung ausnahmsweise im Physik-Hörsaal der LMU, Am Coulombwall 1 statt. Der Hörsaal befindet sich auf dem Forschungsgelände Garching am nördlichen Ende der Boltzmannstraße. Wegen des langen Weges dorthin beginnt die Vorlesung an diesem Freitag erst um 14:15 Uhr.
  • 25. Oktober 2012: Hausaufgaben können ab jetzt bis um 14:00 Uhr statt bis um 10:00 Uhr abgegeben werden. Ihren Abgabetermin finden Sie unter Übungsblätter.
  • 24. Oktober 2012: Die Tutorübung 6 findet am Donnerstag, den 25.10.2012, ausnahmsweise im Raum MW 2250 statt.
  • 22. Oktober 2012: Aufgrund Ihrer Anmeldung zu den Tutorübungen haben wir ein Anpassung der Termine vorgenommen: Die beiden Gruppen 7 und 8 (Donnerstags, 8:30 - 10:00) Uhr wurden gestrichen, die TeilnehmerInnen dieser Gruppen wurden auf Gruppe 5 umgebucht. Dafür bieten wir Ihnen zwei neue Montagsgruppen an, eine von 8:30 Uhr bis 10:00 Uhr und eine von 10:15 - 11:45 Uhr. Die genauen Daten zu den Gruppen finden Sie unter Termine und Sprechstunden. Die Ummeldung in diese neuen Gruppen ist von Dienstag, 23.10.2012, 18:00 Uhr bis Mittwoch, 24.10.2012, 24:00 Uhr für alle eingeschriebenen TeilnehmerInnen über TUMOnline möglich (nur über Ummeldung von einer anderen Gruppe!).
  • 19. Oktober 2012: Ab kommenden Freitag, 26. Oktober 2012, beginnt die Vorlesung jeweils um 14:00 Uhr.
  • 18. Oktober 2012: Die Einschreibung zu den Tutorübungen beginnt am Freitag, 19.10.2012, um 17:30 Uhr in TUM-Online. Die Anmeldung endet am Sonntag, den 21. Oktober um Mitternacht. Erster Übungstermin ist Montag, der 22. Oktober, 8:30 Uhr, die genauen Daten für alle Übungsgruppen finden Sie auf dieser Seite weiter unten.
  • 10. Oktober 2012: Die erste Vorlesung findet am Freitag, den 19. Oktober 2012 statt, an diesem Tag von 14:15 bis 15:45 Uhr. Den genauen Startzeitpunkt für die folgenden Vorlesungen vereinbaren wir in der ersten Veranstaltung. Die Übungen beginnen in der zweiten Vorlesungswoche, also ab Montag, 22. Oktober 2012.

Termine und Sprechstunden

Veranstaltung Tag Uhrzeit Raum
Vorlesung Freitag 14:00 - 15:30 Uhr MI HS 1

Veranstaltung Tag Uhrzeit Raum TutorIn Termine
Gruppe 01 Montag 8:30 - 10:00 Uhr MI 02.04.011 Matthias Silbernagl 22.Okt., 05.Nov., 19 Nov., 03.Dez., 17.Dez., 14.Jan, 28.Jan.
Gruppe 02 Montag 8:30 - 10:00 Uhr MI 02.04.011 Matthias Silbernagl 29.Okt., 12.Nov., 26 Nov., 10.Dez., 07.Jan, 21.Jan, 04.Feb.
Gruppe 09 Montag 8:30 - 10:00 Uhr MI 00.07.014 Michael Ritter 29.Okt., 12.Nov., 26 Nov., 10.Dez., 07.Jan, 21.Jan, 04.Feb.
Gruppe 03 Montag 10:15 - 11:45 Uhr MI 02.04.011 Patricia Rachinger 22.Okt., 05.Nov., 19.Nov., 03.Dez., 17.Dez., 14.Jan, 28.Jan.
Gruppe 04 Montag 10:15 - 11:45 Uhr MI 02.04.011 Patricia Rachinger 29.Okt., 12.Nov., 26.Nov., 10.Dez., 07.Jan., 21.Jan, 04.Feb.
Gruppe 10 Montag 10:15 - 11:45 Uhr MI 00.07.014 Michael Ritter 29.Okt., 12.Nov., 26.Nov., 10.Dez., 07.Jan, 21.Jan, 04.Feb.
Gruppe 05 Donnerstag 8:30 - 10:00 Uhr MI 03.10.011 Paul Stursberg 25.Okt., 08.Nov., 22.Nov., 13.Dez. (MW2250), 20.Dez., 17.Jan, 31.Jan.
Gruppe 06 Donnerstag 8:30 - 10:00 Uhr MI 03.10.011 Paul Stursberg 25.Okt. (MW 2250), 15.Nov., 29.Nov., 13.Dez., 10.Jan, 24.Jan, 07.Feb.

Die Einschreibung in die Tutorien ist beendet. Wenn Sie noch zwischen Gruppen wechseln möchten oder sich nachträglich einschreiben wollen, wenden Sie sich bitte direkt an Michael Ritter (michael.rittertum.de).

Achtung: Wegen die Donnerstagstermine am 1.11. (Allerheiligen) und am 6.12. (Nikolaus und Dies Academicus) ausfallen, finden in den Donnerstagsgruppen zwei Termine gemeinsam (statt zweiwöchentlich alternierend) statt, nämlich der 25. Oktober und der 13. Dezember. Die Daten der Donnerstagsgruppen werden dadurch leider etwas unregelmäßig. Im Zweifel beachten Sie bitte die Ankündigungen auf dieser Homepage oder fragen Sie Ihre Tutorin bzw. Ihren Tutor.

Skript und Mitschriften

Vorlesungsskript

Stand Datei
08.02.2013 vorlesung-ADM2012.pdf

Mitschriften aus der Vorlesung

Datum Datei
19.10.2012 ADM2012-01.pdf
26.10.2012 ADM2012-02.pdf
02.11.2012 ADM2012-03.pdf
09.11.2012 ADM2012-04.pdf
16.11.2012 ADM2012-05.pdf
30.11.2012 ADM2012-06.pdf
14.12.2012 ADM2012-14-12-12.pdf
21.12.2012 ADM2012-21-12-12.pdf
11.01.2013 ADM2012-11-1-13.pdf
18.01.2013 ADM2012-18-1-13.pdf
25.01.2013 ADM2012-25-1-13.pdf
01.02.2013 ADM2012-01-02-13.pdf
08.02.2013 ADM2012-08-02-13.pdf

Übungsblätter

  • Bitte verwenden Sie dieses Deckblatt für Ihre Abgaben: coversheet.pdf
  • Bitte geben Sie die Hausaufgaben jeweils bis spätestens 14:00 Uhr im entsprechend beschrifteten Briefkasten im Untergeschoss des MI-Gebäudes ab. Spätere Abgaben können wir nicht mehr berücksichtigen!

Übungsblatt Lösungsvorschlag Abgabedatum Abgabedatum Anmerkungen
Blatt 01 Lösungsvorschlag 01 29.10. für Gruppen 1,3,5,6 und "Dummy" 05.11. für Gruppen 2, 4, 9 und 10 jeweils um 14:00 Uhr
Blatt 02 Lösungsvorschlag 02 12.11. für ungerade Gruppen (außer 9) und "Dummy" 19.11. für gerade Gruppen und Gruppen 9 und 10  
Blatt 03 Lösungsvorschlag 03 26.11. für ungerade Gruppen (außer 9) und "Dummy" 03.12. für gerade Gruppen und Gruppen 9 und 10  
Blatt 04 Lösungsvorschlag 04 10.12. für Gruppen 1,3 und "Dummy" 17.12. für Gruppen 2,4,5,6,9 und 10  
Blatt 05 Lösungsvorschlag 05 07.01. für ungerade Gruppen (außer 9) und "Dummy" 14.01. für gerade Gruppen und Gruppen 9 und 10  
Blatt 06 Lösungsvorschlag 06 21.01. für ungerade Gruppen (außer 9) und "Dummy" 28.01. für gerade Gruppen und Gruppen 9 und 10  
Blatt 07 Lösungsvorschlag 07 04.02. für ungerade Gruppen (außer 9) und "Dummy" 11.02. für gerade Gruppen und Gruppen 9 und 10  

Notenbonus für Hausaufgaben

Für die kontinuierliche Teilnahme am Übungsbetrieb können Sie einen Notenbonus für die Klausur erhalten. Die genauen Modalitäten sind wie folgt:
  • Um an der Bonusregelung überhaupt teilnehmen zu können, müssen Sie über TUMOnline korrekt zu einer Übung zu dieser Veranstaltung angemeldet sein. (Eintragen in eine Warteliste genügt nicht.)
    Wenn Sie an keiner Übung teilnehmen möchten, melden Sie sich bitte bei der Dummy-Übung an.
  • Wenn Sie 80% der Bearbeitungspunkte in den Blättern 1-7 erreicht haben, erhalten Sie bei der Klausur einen Bonus von einer Notenstufe auf eine bestandene Klausur. (D.h. 1.7 wird zu 1.3, 2.3 wird zu 2.0, 3.0 wird zu 2.7 usw.). "Bearbeitungspunkte" erhalten Sie, wenn Sie eine Aufgabe sinnvoll bearbeitet haben - Sie müssen dazu nicht unbedingt die richtige Lösung haben, es sollte aber erkennbar sein, dass Sie sich mit der Aufgabe beschäftigt haben. Im Zweifel bringen Sie Ihre Ansätze zu Papier und erläutern Sie, was Sie sich dabei gedacht haben und (wenn Sie soweit gekommen sind) warum die Ideen vielleicht doch nicht funktionieren.
  • Die Note von nicht-bestandenen Klausuren (4.3, 4.7, 5.0) kann nicht verbessert werden.
  • Die Note 1.0 kann nicht weiter verbessert werden.
  • Die Bonusregelung gilt für beide Klausuren (Erst- und Zweitversuch) in diesem Semester. Sie gilt nicht für Klausuren zur Algorithmischen Diskreten Mathematik in späteren Semestern. Ebenso können Punkte und/oder Boni aus früheren Semestern nicht angerechnet werden.

Klausur

  • Die Veranstaltung endet mit einer 60-minütigen, schriftlichen Prüfung.
  • Inhalt der Prüfung ist der gesamte Stoff von Vorlesung und Übungen.
  • Es sind keinerlei Hilfsmittel (außer Schreibzeug) zugelassen.
  • Für die Teilnahme an der Klausur ist eine vorherige Anmeldung über TUMOnline notwendig. Die Anmeldefrist beginnt am 15.11.12 und endet am 15.01.13.
  • Die Prüfungsdaten finden Sie ebenfalls in TUMOnline und (unverbindlich) weiter unten auf dieser Seite.
  • Die genaue Aufteilung auf die einzelnen Hörsäle geben wir rechtzeitig vor der Klausur bekannt.

Datum Uhrzeit Hörsäle Anmeldung Hinweise
Fr 22.2.2013 11:00 - 12:00 Uhr MW 0001, MW 2001 15.11.12 - 15.01.13 über TUMOnline Klausurangabe zum Download: exam1.pdf
Musterlösung: exam1-lsg.pdf
Di 09.04.2013 9:00 - 10:00 Uhr MW 2001 bis 25.03.13 über TUMOnline Wiederholungstermin

Hinweise zur Wiederholungsklausur

  • Die Wiederholungsklausur findet im Hörsaal MW2001 in Garching (Forschungszentrum, Maschinenwesen) statt.

  • Seien Sie rechtzeitig vor Beginn der Klausur um 09:00 Uhr im Hörsaal. Eventuelle Verspätungen gehen zu Ihren Lasten.
  • An den Türen und im Hörsaal finden Sie einen Aushang, dem Sie Ihren Sitzplatz entnehmen können. Die Listen sind nach Matrikelnummer sortiert.
  • Bitte denken Sie daran, einen Lichtbildausweis und Ihren Studentenausweis mitzubringen. Wir werden während der Klausur die Ausweise kontrollieren.
  • Für die Klausur sind bis auf Schreibzeug keinerlei Hilfsmittel erlaubt. Sollten Sie Schmierpapier benötigen, erhalten Sie gerne welches von der Aufsicht, eigenes Schmierpapier können wir nicht gestatten.
  • Bitte denken Sie daran, keinen roten oder grünen Stift und auch keinen Bleistift für die Klausur zu verwenden.
  • Die Notenbekanntgabe erfolgt ausschließlich über TUMOnline.
  • Ein Einsichtstermin wird zeitnah nach der Klausur festgelegt, Sie erfahren den Termin hier und mit der Notenbekanntgabe über TUMOnline.

Klausureinsicht

  • Die Klausureinsicht zur Wiederholungsklausur findet am Freitag, den 12.04.2013, von 10:00-11:00 Uhr im Seminarraum MI 02.06.020 statt.
  • Bitte bringen Sie einen Lichtbildausweis zur Klausureinsicht mit.
  • Sie dürfen während der Einsicht Ihre (und nur Ihre eigene!) Klausur abfotografieren, die Nutzung eines Kopierers ist aber leider nicht möglich.
  • Falls Sie den Termin nicht selbst wahrnehmen können, besteht die Möglichkeit, eine Freundin/einen Freund mit einer Vollmacht zur Einsicht Ihrer Klausur zu schicken. In diesem Fall stellen Sie bitte eine schriftliche Vollmacht auf den Namen des Bevollmächtigten (und natürlich unter Nennung Ihres Namens) aus und unterschreiben Sie diese. Mit dieser Vollmacht und einem Lichtbildausweis des Bevollmächtigten kann dieser dann Ihre Klausur einsehen, abfotografieren und ggf. auch in Ihrem Namen einen Antrag auf Zweitkorrektur stellen. Beispieltext: "Hiermit erteile ich, Anne Musterfrau, Herrn Bernhard Mustermann eine Vollmacht zur Einsichtnahme in meine Klausur im Fach Algorithmische Diskrete Mathematik. Herr Mustermann ist berechtigt, meine Klausur abzufotografieren und in meinem Namen einen Antrag auf Zweitkorrektur zu stellen."
  • Anträge auf Zweitkorrektur sind nur während der Einsicht möglich. Falls Sie sich durch einen Bevollmächtigten vertreten lassen, können Sie ausnahmsweise einen Antrag auf Zweitkorrektur auch noch bis 17.04.2013 stellen. Spätere Anträge können wir wegen des Notenschluss-Termins leider nicht mehr berücksichtigen.
  • Falls Sie (aus gutem Grund) einen Ersatztermin benötigen, schreiben Sie bitte vor der Einsicht eine E-Mail an die Übungsleitung, bei Bedarf bieten wir dann einen weiteren Termin an.

alte Klausuren

Zur Vorbereitung stellen wir Ihnen ein paar alte Klausuren zur Verfügung. Bitte beachten Sie, dass der Stoff der Vorlesung je nach Dozent ein wenig variiert. Sie werden also einerseits Aufgaben finden, die Sie mit dem Wissen aus dieser Veranstaltung nicht lösen können, andererseits decken die Aufgaben auch nicht den kompletten Stoff dieser Veranstaltung ab!

Literatur

  • P. Gritzmann: Grundlagen der Mathematischen Optimierung , Springer 2013
  • A. Taraz: Diskrete Mathematik, 1. Auflage, Birkhäuser / Springer 2012
  • Cook, Cunningham, Pulleyblank, Schrijver, Combinatorial Optimization, Wiley 1998
  • Korte, Vygen, Combinatorial Optimization: Theory and Algorithms, Springer 2002
  • Jungnickel, Graphen, Netzwerke und Algorithmen, BI Wissenschaftsverlag 1994
  • Papadimitriou, Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover 1998

FAQ

question Woher weiß ich, in welche Übungsgruppe ich gehen soll?
info Wählen Sie eine Übung, die am besten in Ihren persönlichen Stundenplan passt. Melden Sie sich (sobald möglich) für diese Übung an und besuchen Sie diese Gruppe dann zu den angegebenen Terminen (ca. alle 14 Tage).

question Wie funktioniert das mit den Übungsaufgaben und Abgaben?
info Das geht so:
  • In Ihrer Tutorübung erhalten Sie alle zwei Wochen ein Übungsblatt. Zudem wird dieses jeweils am Freitag der ungeraden Semesterwochen auf dieser Homepage veröffentlicht. Sie erhalten die Übungsblätter auch jeweils in Ihren Tutorübungen.
  • Die Abgabe ist bis 14:00 Uhr an dem Montag, der Ihrer Übung folgt, möglich.
  • Sie geben Ihre schriftlichen Lösungen in maximal Dreierteams ab, d.h. Sie werfen Ihre Bearbeitung in den entsprechend beschrifteten Briefkasten im Untergeschoß des MI-Gebäudes.
  • Vermerken Sie bitte auf der ersten Seite der Abgabe Ihre Namen, Matrikelnummern und Übungsgruppe(n).
  • Die korrigierten Übungsaufgaben erhalten Sie in den Tutorübungen zurück.
  • Wenn Sie mehr als 80% der Bearbeitungspunkte erreichen, können Sie einen Notenbonus für die Klausur erhalten. Genaues unter dem Punkt Notenbonus.

question Gibt es Musterlösungen für die Aufgaben?
info Ausgewählte Aufgaben werden in den Übungen präsentiert werden. Nach Abschluss aller Übungen zu einem Blatt stellen wir zu allen Aufgaben Lösungsvorschläge auf der Homepage bereit.

question Was passiert mit nicht abgeholten Abgaben?
info Nicht abgeholte Abgaben werden noch eine Weile am Lehrstuhl M9 (Finger 02.04, direkt nach der Glastür links) verwahrt und können dort abgeholt werden. Sie finden Ihre Hausaufgaben im Schrank direkt links hinter der ersten Glastür im Lehrstuhl-Gang. Hausaufgaben, die bis zur Wiederholungs-Klausur nicht abgeholt wurden, werden wir anschließend entsorgen.

question Was muss ich tun, um zur Klausur zugelassen zu werden?
info Sie müssen sich zur Vorlesung registrieren und sich für die Klausur anmelden. Siehe dazu: BSc Regelungen

question Wie wird die Klausur aussehen?
info Es wird zum Semesterende eine Aufgabensammlung mit alten Klausuraufgaben geben, die Sie zu Ihrer eigenen Einschätzung und zur Übung bearbeiten können. Die tatsächliche Klausur wird eine vergleichbare Schwierigkeit haben.

question Welche Hilfsmittel sind zur Klausur zugelassen?
info Keine, außer Schreibzeug (insbesondere keinerlei Taschenrechner).

question Enthält die Klausur Multiple-Choice-Aufgaben?
info Es wird keine reinen Multiple-Choice-Aufgaben in der Klausur geben. Allerdings könnte es Fragen geben, die jeweils mit einer kurzen Begründung zu beantworten sind, beispielsweise Ist die folgende Aussage richtig oder falsch? Geben Sie eine kurze Begründung Ihrer Antwort an! "Die Distanzmatrix eines Digraphen ist immer eine quadratische Matrix."

question Wo finde ich die Algorithmische Diskrete Mathematik bei TUMOnline?
info Die folgenden beiden Links führen zur Seite der Vorlesung und der Übungen bei TUMOnline.