Diskrete Mathematik I
Wintersemester 2007/2008
| Dozent | Zeit | Raum | Erstmals am |
|---|---|---|---|
| Prof. A. May | dienstags 10.00 - 12.00 | HNC 30 | 16.10.2007 |
| Prof. A. May | mittwochs 12.00 - 14.00 | HZO 50 |
| Dozent | Zeit | Raum | Erstmals am |
|---|---|---|---|
| N. List | dienstags, 08.00 - 10.00 | HZO 60 | 23.10.2007 |
| N. List | mittwochs, 8.00-10.00 | NA 02/99 |
Aktuelles
| Erste Klausur: | Klausur vom 28.02.08 |
| Klausurtermin: | 28. August, 9:00-12:00 Uhr |
| Klausurort: | HZO-10 |
| Zulässige Hilfsmittel: | Diskrete Sturukturen I+II (Steger), Vorlesungsskript, zweisprachiges Wörterbuch für nicht Muttersprachler |
| Bonuspunkte: | Erworbene Bonuspunkte aus dem WS07/08 werden angerechnet |
| Klausureinsicht: | Di. 09. September, 15:00-16:00 Uhr, NA 5/64 |
| Klausurergebnisse : | Ergebnisse vom 28.02.08 (mit korrigierter Bonusberechnung) |
| Ergebnisse vom 28.08.08 (Bonuspunkte sind eingerechnet) |
Umrechnung der Prozentpunkte in eine Note.
Beantragte Scheine können in NA 5/74 abgeholt werden.
Inhalt
Die Vorlesung richtet sich an Studierende der Mathematik, der Angewandten Informatik und der IT-Sicherheit. Diskrete Mathematik beschäftigt sich überwiegend mit endlichen Strukturen. Die Vorlesung gliedert sich in 5 Abschnitte. Abschnitt 1 ist der Kombinatorik gewidmet. Insbesondere werden grundlegende Techniken vermittelt, um sogenannte Zählprobleme zu lösen. In Abschnitt 2 beschäftigen wir uns mit der Graphentheorie. Graphen werden zur Modellierung von Anwendungsproblemen benutzt. Wir behandeln Techniken zur Graphexploration und weitere ausgesuchte Graphprobleme. Abschnitt 3 vermittelt Grundkenntnisse in elementarer Zahlentheorie und endet mit einem Ausblick auf kryptographische Anwendungen. Grundlegende Designtechniken für effiziente Algorithmen bilden das zentrale Thema von Abschnitt 4. Daneben geht es auch um das Aufstellen und Lösen von Rekursionsgleichungen, wobei sogenannte erzeugende Funktionen zum Einsatz kommen. Abschnitt 5 der Vorlesung liefert eine Einführung in elementare Wahrscheinlichkeitstheorie.
Literatur:
Der Stoff der Vorlesung überschneidet sich stark mit dem Inhalt der Bücher:
- [1] Angelika Steger, "Diskrete Strukturen", Band 1,
- [2] Thomas Schickinger und Angelika Steger, "Diskrete Strukturen", Band 2,
welche beide im Springer-Verlag 2001 erschienen sind.
Im Netz finden sich auch Errata zu diesen beiden Bänden.
Weitere Literatur:
- [3] Ihringer, "Diskrete Mathematik", Teubner Verlag, 2. Auflage (1999)
- [4] Cormen, Leiserson, Rivest, Stein, "Introduction to Algorithms", MIT Press, 2. Auflage (2001)
- [5] Graham, Knuth, Patashnik, "Concrete Mathematics", 2. Auflage, Addison-Wesley, 1994
- [6] Aigner, "Diskrete Mathematik", 6. Auflage, Vieweg Studium, 2006
| 01 Di. 16.10.07 PDF, PPT | Grundlagen |
| 02 Mi. 17.10.07 PDF, PPT | Ziehen von Elementen [6] |
| 03 Di. 23.10.07 PDF, PPT | Permutationen, Teilmengen, Zahlpartitionen [6] |
| 04 Mi. 24.10.07 PDF, PPT | Partielle Ordnungen [3] |
| 05 Di. 30.10.07 PDF, PPT | Distributiver Verband, ungerichteter Graph [3,4] |
| 06 Mi. 31.10.07 PDF, PPT | Zusammenhangskomponente, Baum [4] |
| 07 Di. 06.11.07 PDF, PPT | Spannbaum, Prüferkode [4] |
| 08 Mi. 07.11.07 PDF, PPT | BFS, DFS, Hamiltonkreis [4] |
| 09 Di. 13.11.07 PDF, PPT | Eulertour, planare Graphen [3] |
| 10 Mi. 14.11.07 PDF, PPT | Färbung, Matching [3] |
| 11 Di. 20.11.07 PDF, PPT | Topologische Sortierung, Transitive Hülle [4] |
| 12 Mi. 21.11.07 PDF, PPT | Satz von Bezout, Euklidischer Algorithmus [4] |
| 13 Di. 27.11.07 PDF, PPT | Erweiterter Euklidischer Algorithmus, Gruppen |
| 14 Mi. 28.11.07 PDF, PPT | Satz von Euler, Satz von Lagrange, Nebenklassen |
| 15 Di. 04.12.07 PDF, PPT | Modulare Arithmetik, Fermat-Primzahltest |
| 16 Mi. 05.12.07 PDF, PPT | Chinesischer Restsatz, RSA |
| 17 Di. 11.12.07 PDF, PPT | Arithmetik auf Polynomen, Point-value Form [4] |
| 18 Mi. 12.12.07 PDF, PPT | Einheitswurzeln, DFT, Schnelle Fouriertransformation [4] |
| 19 Di. 18.12.07 PDF, PPT | Endliche Körper mit p Elementen |
| 20 Mi. 19.12.07 PDF, PPT | Zyklizität der Einheitengruppe, Galoiskörper |
| 21 Di. 08.01.08 PDF, PPT | Divide & Conquer, Sortieren [4] |
| 22 Mi. 09.01.08 PDF, PPT | Dynamische Programmierung [4] |
| 23 Di. 15.01.08 PDF, PPT | Greedy, Scheduling-Problem [4] |
| 24 Mi. 16.01.08 PDF, PPT | Matroid, Minimale Spannbäume [4] |
| 25 Di. 22.01.08 PDF, PPT | Rekursionsgleichungen, Master Theorem [4] |
| 26 Mi. 23.01.08 PDF, PPT | Formale Potenzreihen, Erzeugende Funktionen [5,6] |
| 27 Di. 29.01.08 PDF, PPT | Partialbruchzerlegung, Lineare Rekursion 2.Ordnung [5,6] |
| 28 Mi. 30.01.08 PDF, PPT | Wahrscheinlichkeitsraum, bedingte Wahrscheinlichkeit [2] |
| 29 Di. 05.02.08 PDF, PPT | Satz von Bayes, Unabhängigkeit von Ereignisse [2] |
| 30 Mi. 06.02.08 PDF, PPT | Zufallsvariable, Erwartungswert, Varianz [2] |
Prüfungsmodalitäten:
Am Ende des Semesters wird eine Abschlussklausur geschrieben. Der Termin wird zu Ende des Semesters bekannt gegeben.
Einzige zugelassene Hilfsmittel sind dabei die Bücher Diskrete Strukturen I/II von Steger/Schickinger und die Ausdrucke der Präsentation aus der Vorlesung. Nicht zugelassen sind somit insbesondere andere Bücher (mit der Ausnahme von Wörterbüchern) oder Mitschriften aus der Vorlesung, sowie Taschenrechner und Ähnliches.
Es werden wöchentlich 4 Übungsaufgaben auf dieser Seite zum Download bereitgestellt. Zwei zufällig gewählte Aufgaben werden korrigiert und bewertet. Durch die Bewertung kann ein Bonus für die Klausur erarbeitet werden. Wurden 50% der möglichen Punkte bei der Korrektur erreicht, wird die Klausur eine Notenstufe verbessert, wenn 75% oder mehr erreicht wurden, verbessert sich die Abschlussnote um zwei Notenstufen.
Vorraussetzung dafür ist, dass die Klausur auch ohne Bonuspunkte mit mindestens 50 Prozentpunkten (4,0) bewertet wird. Die Abgabe der Übungsblätter kann in Gruppen bis zu 4 Personen erfolgen. Abgabetermin ist jeweils Montag 18:00 Uhr in den Kästen auf NA 02.
Hinweis: Die Bonuspunkte werden nur für Studierende erfasst, die sich über VSPL zur Vorlesung angemeldet haben. Der Meldetermin wurde bis Freitag 9.11. um 12h verlängert.
Übungsaufgaben:
Probeaufgaben zur Klausur PDF, PS
Übungsblatt 1 PDF, PS
Übungsblatt 2 PDF, PS
Übungsblatt 3 PDF, PS
Übungsblatt 4 PDF, PS
Übungsblatt 5 PDF, PS
Übungsblatt 6 PDF, PS In Aufgabe 6.4 muss es heissen: 1234*x = 110 (mod 654321)
Übungsblatt 7 PDF, PS
Übungsblatt 8 PDF, PS In Aufgabe 8.1 muss es heissen: x^2 - 4x + 3 = 0
Übungsblatt 9 PDF, PS
Übungsblatt 10 PDF, PS
Übungsblatt 11 PDF, PS
Übungsblatt 12 PDF, PS
Übungsblatt 13 PDF, PS