Diskrete Mathematik (D-ITET)

Dozenten

Prof Dr. Angelika Steger, Dr. Uli Wagner

Übungsleitung

Torsten Mütze, Johannes Lengler

Zeit und Ort

Vorlesung: Montag 10.00-12.00 (CAB G11)

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

• 1. Gruppe (Dominik Lengacher): ETZ G91 
• 2. Gruppe (Felix Wermelinger): ETZ H91
• 3. Gruppe (Mathis Steichen): ETZ J91
  
• 4. Gruppe (Tobias Pröger): HG E22
• 5. Gruppe (Ognjen Maric): HG G26.1
• 6. Gruppe (Sandro Feuz): HG G26.5

Die Gruppeneinteilung erfolgt nach den Nachnamen: 1. Gruppe (Aeschbach-Clausen), 2. Gruppe (Cottier-Glaser), 3. Gruppe (Gross-Leuenberger), 4. Gruppe (Li-Odermatt), 5. Gruppe (Pauli-Selber), 6. Gruppe (Sgier-Zufferey)

Übungsblätter

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

Aufwärmübung: PDF, Lösung zu Aufgabe 6 der Aufwärmübung: PDF

Auf der Vorlesungshomepage von 2009 finden sich einige Übungsaufgaben, die sich für die Klausurvorbereitung eignen.

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

Zusatzserie:

Da die letzten Wochen der Vorlesung nicht mehr durch den Übungsbetrieb abgedeckt sind, gibt es hier eine Serie von Beispielaufgaben und eine ausführliche Musterlösung. Diese Serie dient ausschliesslich Ihrer Klausurvorbereitung; sie wird nicht abgegeben oder korrigiert.

Wir empfehlen Ihnen trotzdem, die Aufgaben erst selbst zu lösen (oder es zumindest zu versuchen), bevor Sie sich die Musterlösung anschauen. Gegebenenfalls erhalten Sie in der letzten Übung am 16.12. Hinweise zur Bearbeitung.

Challenge-Aufgabe:

Die Challenge-Aufgabe ist gelöst. Als Preis für weitere Lösungen winkt daher kein Buchpreis mehr, sondern nur noch Ruhm und Ehre.

In der Vorlesung wurde eine Challenge-Aufgabe vorgestellt. Die genaue Formulierung kann hier nachgeschaut werden. Dort gibt es auch die Möglichkeit, nach einer Registrierung (Online Judge ID: 00000) die Lösung als Programm (z.B. in Java oder C++) hochzuladen, das dann automatisch auf Korrektheit geprüft wird. Es ist Ehrensache, dass man eine Challenge-Aufgabe nur dann abgibt, wenn man sie ohne fremde Hilfe gelöst hat!

Die erste Person, die die Aufgabe löst, darf aus folgender Buchliste wählen:

• Peter Winkler: Mathematical Puzzles - A Connoisseur's Collection
• Simon Singh: Fermats letzter Satz
• Martin Aigner und Günter Ziegler: Das Buch der Beweise
• Walter Isaacson: Steve Jobs: A Biography
  
• Angelika Steger: Diskrete Strukturen 1: Kombinatorik, Graphentheorie, Algebra

Vorlesungsprotokoll

• 26.09. (Angelika Steger)
  Kapitel 1.1.1: Kombinatorik: Ziehen von Elementen aus einer Menge
  Kapitel 1.1.2: Teilmengen
• 03.10. (Angelika Steger)
  Kapitel 1.1.3: Permutationen
  Kapitel 1.2: Catalan-Zahlen
  Kapitel 1.3: Asymptotische Abschätzungen
• 10.10. (Angelika Steger)
  Kapitel 1.4: Untere Schranke für Sortieralgorithmen
  Kapitel 2.1: Graphen: Grundbegriffe und Beispiele
  Kapitel 2.2: Pfade, Wege, Kreise
• 17.10. (Angelika Steger)
  Kapitel 2.3: Zusammenhang, Satz von Menger
  
• 24.10. (Angelika Steger)
  Kapitel 2.4: Hamiltonkreise und Eulertouren
  Kapitel 2.5: Graphen und lineare Algebra
  
• 31.10. (Angelika Steger)
  Kapitel 2.5: Graphen und lineare Algebra (Fortsetzung), gerichtete Graphen
• 07.11. (Angelika Steger)
  Kapitel 2.6: Bäume
  
• 14.11. (Uli Wagner)
  Kapitel 2.7: Matchings, Heiratssatz
  Kapitel 2.8: Planare Graphen
  
• 21.11. (Uli Wagner)
  Kapitel 2.8: Planare Graphen (Fortsetzung)
  
• 28.11. (Uli Wagner)
  Kapitel 2.9: Flüsse in Netzwerken
  
• 05.12. (Uli Wagner)
  Kapitel 3.1: Modulare Arithmetik, Der Euklidische Algorithmus
  
• 12.11. (Uli Wagner)
  Kapitel 3.1: Chinesischer Restsatz, Der Satz von Fermat
  Kapitel 3.2: Gruppen
  
• 19.11. (Uli Wagner)
  Kapitel 3.2: Gruppen: Ordnung eines Elements, Sätze von Lagrange und Euler
  

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 Torsten Mütze (CAB G 39.1).

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:

• Beispielklausur - Musterlösung

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.