Department of Computer Science | Institute of Theoretical Computer Science

CADMO - Center for Algorithms, Discrete Mathematics and Optimization

Diskrete Mathematik 2012 (D-ITET)

Dozenten

Prof Dr. Angelika Steger, Prof. Dr. Emo Welzl

Übungsleitung

Johannes Lengler

News:

Zeit und Ort

Vorlesung: Montag 10.00-12.00 (CAB G11)

Übung: Freitag 10.00 - 12.00 (14-tägig, 1. Termin am 21.09.12)

Die Gruppeneinteilung in fünf der Gruppen erfolgt nach dem Nachnamen:

Gruppe 1: A-Fer

Gruppe 2: Fes-Kas

Gruppe 3: Kat-Muj

Gruppe 4: Mul-Schm

Gruppe 5: Schn-Z

Ausserdem wird es eine Gruppe geben, die auf Englisch abgehalten wird. Der Wechsel in diese Gruppe ist freiwillig. Die Abgabe der Übungsserien kann in dieser Gruppe wahlweise auf Deutsch oder auf Englisch erfolgen. Wenn Sie gerne in diese Gruppe wechseln möchten, dann schreiben Sie bitte eine E-Mail an Marko Horvat, oder teilen Sie in der ersten Übungsgruppe Ihrem Assistenten mit, dass Sie gerne wechseln möchten. Beachten Sie, dass wir diesem Wunsch nur entsprechen können, solange die Gruppe nicht voll ist ("first come, first serve").

Übungsblätter

Es werden 6 Serien ausgegeben, die bearbeitet werden müssen (Testatpflicht). Die Abgabe der bearbeiteten Serien erfolgt zwei Wochen nach Ausgabe montags vor Beginn der Vorlesung.

In der ersten Übung am 21.09. wird eine Präsenzübung bearbeitet. Da die letzte Aufgabe nicht überall besprochen werden konnte, gibt es hier eine Musterlösung zu dieser Aufgabe.

Neu:
Zu den Themen Gruppen, Körper, Kryptographie und Polynome über endlichen Körpern gibt es ein Zusatzübungsblatt, das der Klausurvorbereitung dient. Es wird nicht abgegeben oder besprochen. Sie finden hier eine Musterlösung für dieses Blatt.

Vorlesung


24.09.

01.10.


08.10.

15.10.


22.10.

29.10.


05.11.

12.11.


19.11.

26.11.


03.12.

10.12.


17.12.

Übung

21.09.



05.10.



19.10.



02.11.



16.11.



30.11.



14.12.


Ausgabe Serie #

1 pdf


2 pdf



3 pdf



4 pdf



5 pdf



6 pdf






Vorbesprechung Serie #

1



2



3



4



5



6





Abgabe Serie #



1



2



3



4



5



6



<\p>

Weitere geeignete Übungsaufgaben (mit Lösungen) finden sich in dem Buch Diskrete Strukturen I von Angelika Steger, erschienen im Springer-Verlag.

Vorlesungsplanung

  • 24.09. (Angelika Steger)
    Kapitel 1.1.1: Kombinatorik: Ziehen von Elementen aus einer Menge
    Kapitel 1.1.2: Teilmengen
    Kapitel 1.1.3: Permutationen
  • 01.10. (Angelika Steger)
    Kapitel 1.2: Catalan-Zahlen
    Kapitel 1.3: Asymptotische Abschätzungen
    Kapitel 1.4: Untere Schranke für Sortieralgorithmen
  • 08.10. (Angelika Steger)
    Kapitel 2.1: Graphen: Grundbegriffe und Beispiele
    Kapitel 2.2: Pfade, Wege, Kreise
  • 15.10. (Angelika Steger)
    Kapitel 2.3: Zusammenhang, Satz von Menger
    Kapitel 2.4: Hamiltonkreise und Eulertouren
  • 22.10. (Emo Welzl)
    Kapitel 2.5: Graphen und lineare Algebra, gerichtete Graphen
  • 29.10. (Emo Welzl)
    Kapitel 2.6: Bäume
    Kapitel 2.7: Matchings, Heiratssatz
  • 05.11. (Emo Welzl)
    Kapitel 2.8: Planare Graphen
  • 12.11. (Emo Welzl)
    Kapitel 2.9: Flüsse in Netzwerken
  • 19.11. (Angelika Steger)
    Kapitel 2.9: Flüsse in Netzwerken: Bipartites Matching, Bildsegmentierung
    Kapitel 3.1: Modulare Arithmetik: Definitionen und Beispiele
  • 26.11. (Angelika Steger)
    Kapitel 3.1: Modulare Arithmetik: Der Euklidische Algorithmus
  • 03.12. (Emo Welzl)
    Kapitel 3.1: Modulare Arithmetik: Der Satz von Euler-Fermat
    Kapitel 3.2: Gruppen: Definitionen und Eigenschaften
  • 10.12. (Emo Welzl)
    Kapitel 3.2: Gruppen: Untergruppen und der Satz von Lagrange
    Kapitel 3.3: Körper
  • 17.12. (Angelika Steger)
    Kapitel 3.4: Kryptographie, Nachrichtenübertragung und Datenspeicherung

Inhalt der Vorlesung

  • Kombinatorik
    Elementare Zählprobleme
    Ein Zählproblem in vielen Gewändern: Die Catalan-Zahlen
    Asymptotische Abschätzungen
    Untere Schranke für Sortieralgorithmen

  • Graphen
    Grundbegriffe und Beispiele
    Pfade, Wege, Kreise
    Zusammenhang, Satz von Menger
    Hamiltonkreise und Eulertouren
    Graphen und lineare Algebra, gerichtete Graphen
    Bäume
    Matchings, Heiratssatz
    Planare Graphen
    Flüsse in Netzwerken

  • Algebra
    Modulare Arithmetik
    Gruppen
    Körper
    Kryptographie, Nachrichtenübertragung und Datenspeicherung

Skript

Wird in der ersten Vorlesung zum Preis von 10 CHF verkauft. Wer im Nachhinein ein Skript erwerben möchte, wende sich bitte direkt an Johannes Lengler (CAB G 36.2).

Testatpflicht

Ja. Es müssen 5 der 6 Übungsblätter sinnvoll bearbeitet werden, um ein Testat zu erhalten.

Prüfung

Prüfung: Sessionsprüfung

Vor der Prüfung wird es eine Fragestunde geben. Während der Fragestunde können Fragen zum behandelten Stoff der Vorlesung und zu den Übungen gestellt und diskutiert werden. Hinweise zum Inhalt der Klausur werden selbstverständlich nicht gegeben. Die Termine werden rechtzeitig auf der Webseite und allen eingeschriebenen Studenten auch noch einmal per E-Mail bekanntgegeben.

Hilfsmittel: 10 handbeschriebene DIN-A4 Blätter
Handbeschrieben bedeutet mit einem handelsüblichen Stift unter Einsatz der menschlichen Hand geschrieben. Anderweitig erstellte, z.B. am Computer oder Tablet-PC, oder kopierte Unterlagen, welcher Form auch immer, sind nicht zulässig. Die 10 Blätter können beidseitig beschrieben werden, dies ergibt 20 Seiten Platz.

Folgende Beispielklausur (inklusive Musterlösung) steht für die Prüfungsvorbereitung zur Verfügung:

Bitte beachten Sie, dass der Inhalt dieser Klausur weder als Hinweis noch als Garantie zu verstehen ist, welche Themen und Aufgabentypen in zukünftigen Klausuren behandelt werden.