Diskrete Mathematik I

Wintersemester 2008/2009

Vorlesung
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
Übungen
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.