Übung

18.09.

02.10.

16.10.

30.10.

13.11.

27.11.

11.12.

Vorbesprechung Serie #

1

2

3

4

5

6

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.