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 Mus
sterlö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 MengeKapitel 1.1.2: Teilmengen
- 03.10. (Angelika Steger)Kapitel 1.1.3: PermutationenKapitel 1.2:
Catalan-ZahlenKapitel 1.3: Asymptotische Abschätzungen
- 10.10.
(Angelika Steger)Kapitel 1.4: Untere Schranke für Sortieralgorithmen
Kapitel 2.1: Graphen: Grundbegriffe und BeispieleKapitel 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 EulertourenKapitel 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, HeiratssatzKapitel 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 FermatKapitel 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ählproblemeEin Zählproblem in vielen Gewändern: Die Catalan-Zahlen
Asymptotische AbschätzungenUntere Schranke für Sortieralgorithmen
-
Graphen
Grundbegriffe und BeispielePfade, Wege, Kreise
Zusammenhang, Satz von MengerHamiltonkreise und EulertourenGraphen
und lineare Algebra, gerichtete GraphenBäumeMatchings,
HeiratssatzPlanare GraphenFlüsse in Netzwerken
-
Algebra
Modulare ArithmetikGruppenKö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:
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.
