Diskrete Mathematik I
Wintersemester 2008/2009
Dozent | Zeit | Raum | Erstmals am |
---|---|---|---|
Prof. A. May | dienstags, 10.00 - 12.00 | HIC | Di. 14.10.2008 |
Prof. A. May | mittwoch 12.00 - 14.00 | HZO 50 | Di. 14.10.2008 |
Dozent | Zeit | Raum | Erstmals am |
---|---|---|---|
M. Ritzenhofen | dienstags, 08.00 - 10.00 | HZO | Di. 21.10.2008 |
M. Ritzenhofen | Mittwochs, 08.00 - 10.00 | NA 02/99 | Di. 21.10.2008 |
Wiederholungsklausur im Sommersemester 2009:
Aktuell: Die Klausurergebnisse liegen nun vor. Insgesamt haben 50% der Teilnehmer die Klausur bestanden (Statistik).
Die Klausureinsicht findet am 10. September 2009 um 10 Uhr in NA 5/64 statt.
Die Wiederholungsklausur zur Diskreten Mathematik I findet am 27. August 2009 um 14 Uhr in HZO 10 statt.
Bitte melden Sie sich, falls Ihre Studienordnung dies erfordert, bis zum 12. August 2009 im VSPL zur Klausur an.
Die Anmeldung erfolgt unter der Veranstaltung Diskrete Mathematik I, Veranstaltungsnummer 150310 im WS08/09, zur Prüfung im SS09 an. Hierbei wird nicht zwischen Mathematik- und ITS-Studierenden unterschieden. Bitte nicht zur Wiederholungsklausur mit der Veranstaltungsnummer 150310w anmelden.
Erlaubte Hilfsmittel bleiben wie bei der letzten Klausur: Vorlesungsfolien mit Vorlesungsnotizen, zusätzlich ein beidseitig handbeschriebenes DIN A 4 Blatt. Die Lösungsvorschläge zu den Übungsaufgaben dürfen nicht mitgenommen werden. Ebenso sind außer den Vorlesungsfolien keine gedruckten oder kopierten Zettel zugelassen.
Bücher, abgesehen von Wörterbüchern für ausländische Studierende, sowie Taschenrechner oder sonstige Hilfsmittel sind nicht zugelassen.
Klausurergebnisse:
Die Klausurergebnisse liegen nun vor. Insgesamt haben 41% der Teilnehmer die Klausur bestanden (Statistik).
Klausureinsicht:
Freitag, den 06.03. 2009, von 15.00 - 16.00Uhr in NA 5/64
Klausur:
Termin: 26.02.2008, 14.00Uhr in HZO 10 (Nachnamen A-Ne) und HZO 20 (Nachnamen Ng-Z)
Erlaubte Hilfsmittel: Vorlesungsfolien mit Vorlesungsnotizen, zusätzlich ein beidseitig handbeschriebenes DIN A 4 Blatt. Die Lösungsvorschläge zu den Übungsaufgaben dürfen nicht mitgenommen werden. Ebenso sind außer den Vorlesungsfolien keine gedruckten oder kopierten Zettel zugelassen.
Bücher, abgesehen von Wörterbüchern für ausländische Studierende, sowie Taschenrechner oder sonstige Hilfsmittel sind nicht zugelassen.
Klausuranmeldung: Bitte melden Sie sich bis zum 12.2.2009 via VSPL zur Klausur an (dies betrifft einige ITS-Studierende (je nach Studienordnung) und alle Mathematikstudierenden). Die Veranstaltungsnummer der Klausur ist 150310a, eingetragen als Vorlesung im WS08/09 Diskrete Mathematik 1 Klausur.
Um die Veranstaltung als Modulprüfung zu nutzen, ist für Studierende des Bachelor of Arts die Teilnahme an der Klausur erforderlich.
Klausurvorbereitung:
Alexander Meurer bietet im Rahmen des Helpdesk Hilfe bei Fragen zur Diskreten Mathematik I an. Seine Sprechzeiten sind immer Dienstags von 13.00Uhr bis 16.00Uhr im Helpdesk (NA3/51 oder NA3/58).
Übungen:
Die korrigierten Übungen liegen vor und können Donnerstags zwischen 14.00Uhr und 15.00Uhr in NA 5/74 abgeholt werden.
Bitte kontrollieren Sie die Punktzahlen in der Liste der Übungspunkte und wenden Sie sich bei Fehlern an Maike Ritzenhofen.
Übungsscheine:
Um einen Übungsschein zu erhalten, müssen 50% der Übungspunkte in den gestellten Übungen erreicht werden.
Zusätzlich ist eine Anmeldung erforderlich. Bitte melden Sie sich bis zum 31.1.2009 via VSPL zur Klausur an (dies betrifft vor allem Lehramts-Studierende). Die Veranstaltungsnummer für die Übungsscheine ist 150310b.
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. 14.10.08 PDF, PPT, PDF(14.10.) | Mengen, Relationen, Funktionen, Indirekter Beweis |
02 Mi. 15.10.08 PDF, PPT, PDF(15.10.) | Induktion, Widerspruch, Landau-Notation, Ziehen von k aus n Elementen |
03 Di. 21.10.08 PDF, PPT, PDF(21.10.) | Kombinatorisches Beweisen, Schubfachprinzip, Inklusion-Exklusion |
04 Mi. 22.10.08 PDF, PPT, PDF(22.10.) | Permutation, Fixpunkt, 1.Stirlingzahl, Rekursive Berechnung |
05 Di. 28.10.08 PDF, PPT, PDF(28.10.) | Binomialkoeffizienten, Stirlingzahl zweiter Art, Zahlpartitionen |
06 Mi. 29.10.08 PDF, PPT, PDF(29.10.) | Bälle in Urnen, ungerichtete Graphen, isomorphe Graphen |
07 Di. 04.11.08 PDF, PPT, PDF(04.11.) | Handschlaglemma, Zusammenhangskomponente, Bäume und Wälder |
08 Mi. 05.11.08 PDF, PPT, PDF(05.11.) | Spannbaum, markierte Bäume, Satz von Cayley, Prüfercode, Queue, Stack |
09 Di. 11.11.08 PDF, PPT, PDF(11.11.) | Breitensuche, Kürzeste u-v Pfade, Tiefensuche, Hamiltonkreis |
10 Mi. 12.11.08 PDF, PPT, PDF(12.11.) | Eulertour, Planare Graphen, Nicht-Planarität |
11 Di. 18.11.08 PDF, PPT, PDF(18.11.) | Satz von Kuratowski, Vierfarbensatz, Knoten- und Kantenfärbung |
12 Mi. 19.11.08 PDF, PPT, PDF(19.11.) | Matching, Heiratssatz, gerichtete Graphen, topologische Sortierung |
13 Di. 25.11.08 PDF, PPT, PDF(25.11.) | Algorithmus von Warschall, Dynamische Programmierung, Binärbäume |
14 Mi. 26.11.08 PDF, PPT, PDF(26.11.) | Lemma von Bezout, Primzahlzerlegung, Euklidischer Algorithmus |
15 Di. 02.12.08 PDF, PPT, PDF(02.12.) | EEA, Abelsche Gruppe, Gruppen- und Elementordnung |
16 Mi. 03.12.08 PDF, PPT, PDF(03.12.) | Satz von Euler, Nebenklassen, Satz von Lagrange, Faktorgruppe |
17 Di. 09.12.08 PDF, PPT, PDF(09.12.) | Gruppenisomorphie, Modulare Arithmetik, Kleiner Satz von Fermat |
18 Mi. 10.12.08 PDF, PPT, PDF(10.12.) | Primzahltest, Chinesischer Restsatz, Nullstellen quadratischer Gleichungen |
19 Di. 16.12.08 PDF, PPT, PDF(16.12.) | RSA, Polynome, Polynomarithmetik |
20 Mi. 17.12.08 PDF, PPT, PDF(17.12.) | Point-value Form, Interpolation, Einheitswurzel, DFT und FFT |
21 Di. 06.01.09 PDF, PPT, PDF(06.01.) | Inverse DFT, Körper und Ringe, Fundamentalsatz der Algebra |
22 Mi. 07.01.09 PDF, PPT, PDF(07.01.) | Generatoren von Körpern, Polynomringe, Irreduzibilität, Galoiskörper |
23 Di. 13.01.09 PDF, PPT, PDF(13.01.) | Divide and Conquer, Binäre Suche, Mergesort, Quicksort |
24 Mi. 14.01.09 PDF, PPT, PDF(14.01.) | Entscheidungsbaum, Dynamische Programmierung, Optimierungsproblem |
25 Di. 20.01.09 PDF, PPT, PDF(20.01.) | Greedy, Scheduling-Problem, Kruskal's Algorithmus, Master-Theorem |
26 Mi. 21.01.09 PDF, PPT, PDF(21.01.) | Beweis Master-Theorem, Lineare Rekursion, Erzeugende Funktion |
27 Di. 27.01.09 PDF, PPT, PDF(27.01.) | Potenzreihen, Partialbruchzerlegung, geschlossene Form |
28 Mi. 28.01.09 PDF, PPT, PDF(28.01.) | Fibonacci-Zahlen, Wahrscheinlichkeitsraum, Bedingte Wahrscheinlichkeit |
29 Di. 03.02.09 PDF, PPT, PDF(03.02.) | Multiplikationssatz, Satz von der totalen Ws, Satz von Bayes, Unabhängigkeit |
30 Mi. 04.02.09 PDF, PPT, PDF(04.02.) | Unabhängigkeit, Zufallsvariable, Erwartungswert, Varianz |
Es werden wöchentlich 4 Übungsaufgaben auf dieser Seite zum Download bereitgestellt. 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.
Voraussetzung 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 Dienstag 8:00 Uhr
in den Kästen auf NA 02. Bitte schreiben Sie die Lösungen zu den Aufgaben 1 und 2 auf einen Zettel und die Lösungen zu den Aufgaben 3 und 4 auf einen anderen Zettel. Die entsprechenden Lösungen sind in unterschiedliche Kästen zu werfen.
Bei Fragen zur Korrektur können Sie sich auch an Alexander Meurer wenden. Seine Sprechzeit ist Do 13:00Uhr bis 14:00Uhr im Helpdesk in Na 3/51.
Hinweis: Die Bonuspunkte werden nur für Studierende erfasst, die sich über VSPL zur Vorlesung angemeldet haben. Bitte melden Sie sich bis Mittwoch, den 29.10.2008 an.