Diskrete Mathematik (D-ITET)

Dozenten

Dr. Uli Wagner, Prof. Dr. Emo Welzl

Übungsleitung

Torsten Mütze, Luca Gugelmann

Zeit und Ort

Vorlesung: Montag 10.00-12.00 (CAB G11)

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

• 1. Gruppe (Viktor Galliard): ETZ G91 
• 2. Gruppe (Esther Hänggi): ETZ H91
• 3. Gruppe (Jens Maue): ETZ J91
• 4. Gruppe (Luca Gugelmann): HG E22
• 5. Gruppe (Torsten Mütze): HG G26.1
• 6. Gruppe (Stephanie Werren): HG G26.5

Die Gruppeneinteilung erfolgt nach den Nachnamen: 1. Gruppe (Adamczyk-Bunjaku), 2. Gruppe (Bürli-Fankhauser), 3. Gruppe (Fischer-Jaggi), 4. Gruppe (Jain-Müri), 5. Gruppe (Nikitovic-Schrittwieser), 6. Gruppe (Schürch-Zellweger).

Übungsblätter

Die Abgabe der bearbeiteten Serien erfolgt vor Beginn der Vorlesung am jeweiligen Montag vor der nächsten Übung.

Serie zur Klausurvorbereitung: PDF

Musterlösung: PDF

Die Aufgaben auf dieser Serie dienen zur Klausurvorbereitung, sie sind nicht abzugeben und werden von den Assistenten nicht korrigiert. Sie haben insbesondere auch keine Relevanz für das Testat. Die Auswahl der Aufgaben ist weder als Hinweis noch als Garantie zu verstehen, welche Themen und Aufgabentypen in der Klausur tatsächlich vorkommen werden. Etwas anspruchsvollere Aufgaben sind mit einem Stern markiert.

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

Vorlesungsprotokoll

• 21.09. (Emo Welzl)
  Kapitel 1.1.1: Kombinatorik: Ziehen von Elementen aus einer Menge
• 28.09. (Emo Welzl)
  Kapitel 1.1.2: Teilmengen
  Kapitel 1.1.3: Permutationen
  Kapitel 1.1.4: Zahlpartitionen
  Kapitel 1.2: Catalan-Zahlen
• 05.10. (Emo Welzl)
  Kapitel 1.3: Asymptotische Abschätzungen
  Kapitel 1.4: Untere Schranke für Sortieralgorithmen
  Kapitel 2.1: Graphen: Grundbegriffe und Beispiele
• 12.10. (Emo Welzl)
  Kapitel 2.1: Grundbegriffe und Beispiele
  Kapitel 2.2: Pfade, Wege, Kreise
  Kapitel 2.3: Zusammenhang, Satz von Menger
• 19.10. (Emo Welzl)
  Kapitel 2.3: Satz von Menger (Beweis)
  Kapitel 2.4: Hamiltonkreise und Eulertouren
  Kapitel 2.5: Graphen und lineare Algebra, gerichtete Graphen
• 26.10. (Emo Welzl)
  Kapitel 2.5: Gerichtete Graphen (starker/schwacher Zusammenhang nur kurz)
  Kapitel 2.6: Bäume
• 02.11. (Emo Welzl)
  Kapitel 2.6: Prüferkode
  Kapitel 2.7: Matchings, Heiratssatz
• 09.11. (Emo Welzl)
  Kapitel 2.8: Planare Graphen
  Kapitel 2.9: Flüsse in Netzwerken
• 16.11. (Uli Wagner)
  Kapitel 3.1.1: Modulare Arithmetik: Definitionen und Beispiele
  Kapitel 3.1.2: Der euklidische Algorithmus
• 23.11. (Uli Wagner)
  Kapitel 3.1.2: Chinesischer Restsatz
  Kapitel 3.1.3: Satz von Euler-Fermat
  Kapitel 3.2: Gruppen: Definition und Beispiele
• 30.11. (Uli Wagner)
  Kapitel 3.2.2: Eigenschaften und Beispiele von Gruppen
  Kapitel 3.2.3: Ordnung eines Elements
• 07.12. (Uli Wagner)
  Kapitel 3.2.4: Untergruppen
  Kapitel 3.2.5: Nebenklassen und Satz von Lagrange, Beweis des Satzes von Euler-Fermat
  Kapitel 3.3: Körper: Definition
• 14.12. (Uli Wagner)
  Kapitel 3.3: Körper: Eigenschaften und Beispiele
  Kapitel 3.4.1: Kyprotgraphische Protokolle: RSA

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 Luca Gugelmann (CAB H17).

Testatpflicht

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

Prüfung

Prüfung: Sessionsprüfung

Es wird eine Fragestunde vor der Klausur geben. Während dieser 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 allen eingeschriebenen Studenten 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.