TUM – TUM – Menü

 

 
Algorithmische Diskrete Mathematik (MA2501)

Vorlesung

 

Dozent: Prof. Dr. Anusch Taraz
Übungsleitung: Andreas Würfl
Tutoren/Korrektoren: Christian Donner, Susanne Nieß, Berit Plumhoff, Wolfgang Ferdinand Riedl

Aktuelles Ferienkurs Termine und Sprechstunden Mitschrift Übungsblätter Klausur Literatur FAQ

%SBBANNER% Ca. 41% aller Hilfskräfte in der Mathematik im Wintersemester 2011/12 werden aus Studienbeiträgen finanziert.

Aktuelles

  • (16.04.2012) Die Klausurergebnisse wurden soeben auf TUMonline veröffentlicht. Die Klausureinsicht findet am Freitag, 20.04. 14:00 - 15:00 Uhr im Raum 02.06.020 statt.
  • (14.03.2012) Der Ferienkurs zur Veranstaltung findet am 02.04.-04.04. statt. Weitere Informationen
  • (08.03.2012) Die endgültigen Noten der Semestrale wurden soeben in TUMonline veröffentlicht.
  • (01.03.2012) Die Klausurergebnisse wurden soeben auf TUMonline veröffentlicht. Die Klausureinsicht findet am Montag, 05.03. 16:00 - 17:00 Uhr im Raum 02.04.011 statt.
  • (23.02.2012) Die Mitschrift des Wiederholungskurses finden Sie hier.
  • (21.02.2012) Die Liste der erreichten Hausaufgabenpunkte können Sie hier einsehen. Sollten Sie Ihrer Punktzahl in der Liste widersprechen wollen, so haben Sie bis zum 24.02.2012 die Gelegenheit. Anschließend werden wir die angegebenen Werte als endgültig betrachten.
  • (21.02.2012) Die Lösung der MC-Blätter sowie des Wiederholungsblatt werden morgen im Ferienkurs besprochen.
  • (07.02.2012) Das zweite MC-Blatt, ein Wiederholungsblatt sowie eine alte Klausur sind nun online.
  • (07.02.2012) Die Details zum Wiederholungskurs finden Sie hier.
  • (25.01.2012) Terminverwirrung: Einige Übungstermine sind in TUMonline fehlerhaft hinterlegt. Korrekt ist: Gruppe 8 am 26.01., Gruppe 5 und Gruppe 7 am 02.02., ...
  • (13.01.2012) Klausuranmeldung: Sollten Sie dies noch nicht getan haben, melden Sie sich bitte bis Sonntag, 15.01.2012 über TUMonline zur Klausur an.
  • (23.12.2011) Das Programmierblatt (zur freiwilligen Bearbeitung) steht online. Schöne Weihnachtsferien wünscht das Team der Algorithmischen Diskreten Mathematik.
  • (02.12.2011) Am kommenden Donnerstag findet der Dies Academicus statt. Deshalb entfallen alle Tutorübungen an diesem Tag. Gruppe 5 findet ersatzweise am Donnerstag, 15. Dezember statt.
  • (24.10.2011) Für alle Studierende des ersten Semesters oder 2in1-Teilnehmer: Die Algorithmische Diskrete Mathematik setzt zwingend die Inhalte der Vorlesung Propädeutikum Diskrete Mathematik voraus!
  • (24.10.2011) Auf Grund des Feiertags verschiebt sich der Abgabetermin nächste Woche auf Mittwoch, 02.11. 12:15 Uhr.
  • (24.10.2011) Zu den Übungsgruppen: Wir möchten nochmals darauf hinweisen, dass jede(r) ausschließlich die Gruppe besuchen kann, für die er oder sie angemeldet ist. Wer noch keinen Platz in einer Gruppe angenommen hat, kann sich nun für weitere freie Plätze in TUMonline registrieren.
  • (20.10.2011) Großer Ansturm auf Übungsgruppen: Leider konnten nicht alle Wünsche bzgl. der Übungsgruppeneinteilung erfüllt werden. Trotzdem bitten wir Sie, in die Gruppe zu gehen, für die Sie angemeldet sind. (Die Teilnehmerzahlen der jeweiligen Gruppen richten sich nach dem Fassungsvermögen des jeweiligen Übungsraums!)
  • (18.10.2011) Die Anmeldung zu den Übungen ist in TUMonline ab Donnerstag, 20.10.2011, 20:00 Uhr möglich.

Ferienkurs %SBICON%

  • Der Ferienkurs findet am Mittwoch, 22.02. von 11:00 - 12:45 Uhr bzw. 14:15 - 16:00 Uhr in HS 1 statt.
  • Um an den Kurs teilnehmen zu dürfen, müssen Sie sich über die Ferienkurs-Webseite anmelden. Dieser Kurs ist ein Zusatzangebot - Sie sind nicht verpflichtet, ihn zu besuchen.
  • Im Rahmen dieses Wiederholungskurses werden wir wichtige Inhalte der Vorlesung wiederholen und eine Auswahl der Aufgaben des Blattes zur Klausurvorbereitung besprechen.
  • Bei dieser Gelegenheit können Sie auch Ihre korrigierten Hausaufgaben zu Blatt 6 sowie bis jetzt nicht abgeholte Hausaufgaben abholen. Des weiteren werden wir eine Liste der erreichten Bearbeitungspunkte mitbringen.

Klausur

  • Die Klausur findet am Freitag, den 24.02.2012 von 15:00 bis 16:00 Uhr statt. Bitte bringen Sie Ihren Studentenausweis mit und erscheinen Sie rechtzeitig.
  • Die Klausur findet in den Hörsälen MW 0001 (Familiennamen A-M) und MW 1801 (Familiennamen N-Z) statt.
  • Sie müssen sich bei TUMOnline zur Klausur anmelden. (Eine Anleitung dazu gibt es hier.)
  • Die Veröffentlichung der Ergebnisse erfolgt ebenfalls über TUMOnline.
  • Die Wiederholungsklausur findet am 11.04.2012 von 8:00 bis 09:00 Uhr im Hörsaal MI HS 1 statt.

Termine und Sprechstunden

Veranstaltung Tag Uhrzeit Raum Dozent/TutorIn erster Termin 2011
Vorlesung Donnerstag 16:00-17:30 Uhr MI HS 1 Anusch Taraz 20.10.
           
Gruppe 01 Montag 08:30 - 10:00 Uhr MI 02.04.011 Susanne Nieß %SBBANNER% 24.10.
Gruppe 02 Montag 08:30 - 10:00 Uhr MI 02.04.011 Susanne Nieß %SBBANNER% 31.10.
Gruppe 03 Montag 10:15 - 11:45 Uhr MI 02.04.011 Wolfgang Ferdinand Riedl 24.10.
Gruppe 04 Montag 10:15 - 11:45 Uhr MI 02.04.011 Wolfgang Ferdinand Riedl 31.10.
Gruppe 05 Donnerstag 08:30 - 10:00 Uhr MI 03.10.011 Andeas Würfl 27.10.
Gruppe 07 Donnerstag 10:15 - 11:45 Uhr MI 02.06.011 Andeas Würfl 27.10.
Gruppe 08 Donnerstag 10:15 - 11:45 Uhr MI 02.06.011 Andeas Würfl 03.11.

Die Übungen finden 14-tägig statt. Die ungerade Gruppen ab der zweiten Semesterwoche, die geraden Gruppen ab der dritten.

  • Gruppe 5: Die andere Übung: Diese Übung richtet sich an besonders motivierte Studenten. In dieser Übung werden wir die Aufgaben gemeinsam an der Tafel diskutieren, immer auf der Suche nach der elegantesten Lösung. Wir erwarten, dass die Teilnehmer dieser Übung sich bereits vor dem Termin mit den Aufgaben beschäftigt haben.

Person Sprechstunde (im Semester)
Anusch Taraz nach Vereinbarung
Andreas Würfl nach Vereinbarung
Wolfgang Ferdinand Riedl nach Vereinbarung

Mitschriften und Folien aus der Vorlesung

Datum Datei Themen
20.10.2011 Vorlesung 1 1. Grundlagen der algorithmischen Graphentheorie
27.10.2011 Vorlesung 2 1. Grundlagen der algorithmischen Graphentheorie (Forts.)
2. Kürzeste Wege
03.11.2011 Vorlesung 3 2. Kürzeste Wege (Forts.)
10.11.2011 Vorlesung 4 2. Kürzeste Wege (Forts.)
3. Minimal aufspannende Bäume und Matroide
17.11.2011 Vorlesung 5 3. Minimal aufspannende Bäume und Matroide (Forts.)
24.11.2011 Vorlesung 6 3. Minimal aufspannende Bäume und Matroide (Forts.)
01.12.2011 Vorlesung 7 3. Minimal aufspannende Bäume und Matroide (Forts.)
4. Flüsse
15.12.2011 Vorlesung 8 4. Flüsse (Forts.)
22.12.2011 Vorlesung 9 4. Flüsse (Forts.)
12.01.2012 Vorlesung 10 5. Komplexitätstheorie
19.01.2012 Vorlesung 11 5. Komplexitätstheorie (Forts.)
26.01.2012 Vorlesung 12 5. Komplexitätstheorie (Forts.)
02.02.2012 Vorlesung 13 5. Komplexitätstheorie (Forts.)
09.02.2012 Vorlesung 14 6. Ausblicke: Matchings und TSP-Approximation

Übungsblätter

Übungsblatt Lösungsvorschlag Abgabedatum Abgabedatum Anmerkungen
    ungerade Gruppen gerade Gruppen  
Blatt 01 Lösung 01 01.11. 08.11.  
Blatt 02 Lösung 02 15.11. 22.11.  
Blatt 03 Lösung 03 29.11. 06.12.  
Blatt 04 Lösung 04 13.12. 20.12.  
Blatt 05 Lösung 05 10.01. 17.01. Zusatzmaterial zu 5.4
Programmierblatt   - - graphen.zip
Blatt 06 Lösung 06 24.01. 31.01.  
Blatt 07 Lösung 07 - -  
Wiederholungsblatt Lösung Wdh. - -  

Eine alte Klausur zur Veranstaltung finden Sie hier.

Hinweis: Die Musterlösungen sind passwortgeschützt. Den Zugang erhalten Sie in Ihren Tutorgruppen.

Multiple Choice Online Aufgaben %SBICON%

Übungsblatt Lösungsvorschlag Veröffentlichung Hinweise
MC-Blatt 1 Lösung MC 1 20.12. Update
MC-Blatt 2 Lösung MC 2 07.02.

Notenbonus für Hausaufgaben

Für die kontinuierliche Teilnahme am Übungsbetrieb können Sie einen Notenbonus für die Klausr 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 50% der Hausaufgabenpunkte in den Blättern 1-6 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.)
  • Die Multiple-Choice-Aufgaben sowie das Programmierblatt sind von dieser Regelung ausgenommen, d.h. für die 50% zählen nur die regulären Aufgaben auf den Übungsblättern.
  • 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.
  • Die Liste der erreichten Hausaufgabenpunkte können Sie hier einsehen.

Literatur

  • 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 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.
  • Die Abgabe ist bis 14:15 Uhr an dem Dienstag, 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.
  • Wenn Sie mehr als 50% der Hausaufgabenpunkte erreichen, können Sie einen Notenbonus für die Klausur erhalten. Genaues unter dem Punkt Klausur.

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 bei Bedarf zu ausgewählten 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.

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 Bin ich automatisch zur Wiederholungsklausur angemeldet?
info Nein. Die Anmeldung zur Wiederholungsprüfung erfolgt getrennt, d.h zu nicht bestandenen Prüfungen muss man sich noch einmal anmelden. Man darf sich aber auch nur zur Wiederholungsprüfung anmelden. Die Anmeldung zu den Prüfungen läuft vom 12. - 26. März. Eine Abmeldung ist bis eine Woche vor Klausurtermin möglich.

question Wo finde ich die Modulbeschreibung zum Propädeutikum Diskrete Mathematik?
info Klicken Sie in der Kopfzeile dieser Seite auf den Link mit der Modulnummer dieser Veranstaltung. Das ganze Modulhandbuch gibt es unter www.ma.tum.de/Studium/Modulhandbuch.

Research Unit M9


Department of Mathematics
Boltzmannstraße 3
85748 Garching b. München
Germany
phone:+49 89 289-16858
fax:+49 089 289-16859
sekretariat-m9ma.tum.de

Professors

Prof. Dr. Peter Gritzmann
Applied Geometry and Discrete Mathematics

Prof. Dr. Andreas S. Schulz
Mathematics of Operations Research
(affiliated member of M9)

Prof. Dr. Stefan Weltge
Discrete Mathematics

News

April 2018
Case Studies 2018: Save the date: Case Studies poster presentation on May 25th, 2018, final workshop on July 7th, 2018.