Diskrete Mathematik II



Vorlesung
Dozent Zeit Raum Erstmals am
Prof. A. May montags, 12.00 - 14.00 Uhr HIA Dienstag. 14.04.2009
Prof. A. May dienstags, 09.00 - 10.00 Uhr NA 3/99 Dienstag, 21.04.2009

Klausur

Anmeldung/Voraussetzungen: Diskrete Mathematik I

Aktuell: Wiederholungsklausur

Die Klausurergebnisse liegen nun vor.

Die Klausureinsicht findet am Montag, den 15. März, um 11 Uhr in NA 5/64 statt.


Die Wiederholungsklausur zur Diskreten Mathematik II findet am 24. Februar 2010 um 14 Uhr in HZO 50 statt.

Als Hilfsmittel für die Klausur sind zwei beidseitig handbeschriebene DIN A 4 Blätter zugelassen und für Studierende, deren Muttersprache nicht Deutsch ist, zusätzlich ein Wörterbuch. Weitere Hilfsmittel sind nicht erlaubt.

Die Klausur zur Diskreten Mathematik II findet am 26. August 2009 um 14 Uhr in HZO 10 statt.


Bitte melden Sie sich, falls Ihre Studienordnung dies erfordert, bis zum 11. August 2009 im VSPL zur Klausur an.

Die Anmeldung für Mathematiker erfolgt unter der Veranstaltungsnummer 150310a, alle anderen melden sich bitte unter der Veranstaltungsnummer 150310 an.

Als Hilfsmittel für die Klausur sind zwei beidseitig handbeschriebene DIN A 4 Blätter zugelassen und für Studierende, deren Muttersprache nicht Deutsch ist, zusätzlich ein Wörterbuch. Weitere Hilfsmittel sind nicht erlaubt.

Zur Nachklausur Diskrete Mathematik I am 27. August 2009 um 14Uhr in HZO 10 melden Sie sich bitte 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.

Klausurergebnisse und -einsicht:


Die Klausurergebnisse liegen nun vor. Insgesamt haben 56% der Teilnehmer die Klausur bestanden (Statistik).



Die Klausureinsicht findet am Donnerstag, den 10. September, um 11 Uhr in NA 5/64 statt.


Die Klausureinsicht zur Diskreten Mathematik I findet am 10. September um 10 Uhr in NA 5/64 statt.

Kommentar

Die Vorlesung behandelt diskrete Strukturen mit den Schwerpunkten Kodierungstheorie und Berechenbarkeitstheorie.

Bitte melden Sie sich bis zum 15.Mai 2009 unter der Veranstaltungsnummer 150311 im VSPL zu den Übungen zur Vorlesung an.

Literatur


  • Steven Roman, "Introduction to Coding and Information Theory", Springer Verlag, 1996
  • Michael R. Garey, David S. Johnson, "Computers and Intractability", Freeman, 2000
  • J. Blömer, "Einführung in Algorithmen und Komplexität", Vorlesungsskript Universität Paderborn, 2002
  • N. Koblitz, "A Course in Number Theory and Cryptography", Springer Verlag, 1994

Folien zur Vorlesung

01 Mo. 20.04.09 PDF(21.04.) Grundlagen, Motivation Kodierungstheorie, Codes, Präfixcodes
02 Mo. 27.04.09 PDF(28.04.) Sätze von Kraft und McMillan, Kompakte Codes, Huffman-Kodierung
03 Mo. 04.05.09 PDF(05.05.) Information, Entropie, Kodierungstheorem von Shannon, Perfekte Sicherheit
04 Mo. 11.05.09 PDF(12.05.) Maximum Likelihood, Hamming-Distanz, Minimaldistanz, Maximale Codes
05 Mo. 18.05.09 PDF(19.05.) Optimale Code, A(n,d), Sphere-Packing/-Covering, Singleton-/Plotkinschranke
06 Mo. 25.05.09 PDF(26.05.) Lineare Codes, Duale Codes, Parity Check Matrix, Gilbert-Varshamov
07 Mo. 08.06.09 PDF(09.06.) Syndrom, Hamming Code, Simplex Code, Golay Code
08 Mo. 15.06.09 PDF(16.06.) Reed-Muller Codes, McEliece Kryptosystem, Stern Identifikation
09 Mo. 22.06.09 PDF(23.06.) Turingmaschine, Rekursive Aufzählbarkeit, Entscheidbarkeit, Laufzeit, DTIME, P
10 Mo. 29.06.09 PDF(30.06.) Verifizierer, nicht-deterministische Turingmaschine, Klasse NP
11 Mo. 06.07.09 PDF(07.07.) KNF, 3SAT, polynomielle Reduktion, Clique, NP-Vollständigkeit
12 Mo. 13.07.09 PDF(14.07.) Satz von Cook-Levin, Reduktionen: Knotenüberdeckung, SubsetSum
13 Mo. 20.07.09 PDF(21.07.) SubsetSum, Cover, Hamiltonkreis, Diffie-Hellman, ElGamal

Folien: komplette Vorlesung SS2009

Übungen und Prüfungsmodalitäten

Die Übungen sind korrigiert und können in NA 5/74 abgeholt werden, allerdings nicht in der Woche vom 10. bis zum 14. August. In dieser Woche können die Übungen Vormittags in NA 5/72 abgeholt werden.

Zur Kontrolle der Punktzahlen gibt es hier eine Punkteliste. Alle zwei Wochen findet eine Präsenzübung statt. Dazu gibt es zwei Übungsgruppen in wöchentlichem Wechsel.

Außerdem werden alle zwei Wochen 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 3 Personen erfolgen. Abgabetermin ist jeweils Dienstag 09:00 Uhr in den Kasten auf NA 02.