Diskrete Mathematik I - WS 2007/2008

Diskrete Mathematik I

Wintersemester 2007/2008

Vorlesung
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
Übungen
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
Folien zur Vorlesung:
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