Diskrete Mathematik II

Sommersemester 2011

Vorlesungen
Dozent Zeit Raum Erstmals am
Prof. A. May montags 12.00-14.00 HZO 70 MO, 04.04.2011, 12.00-14.00 Uhr
Prof. A. May dienstags, 09.00-10.00 NA 6/99
Übungen
Dozent Zeit Raum Erstmals am
Gottfried Herold Dienstags 10.00 - 12:00 NA 5/99 DI, 05.04.2011 (Präsenzübung und Hausaufgaben)
Gottfried Herold Freitags 10:00 s.t. - 11:30 ID/03-463 Fr, 06.05.2011 (nur für Präsenzübungen, bitte bevorzugt zu diesem Termin kommen)

Klausur

Termin 13.09.2011
Uhrzeit 9:00-11:00 Uhr
Ort HIA und HID
Hilfsmittel 1 beidseitig handbeschriebener DIN A4 Zettel
Klausureinsicht Di. 11.10. um 15:00 in NA 5/24 (Ort und Termin geändert)

Die Wiederholungsklausur findet am 13.03.2012 um 12:30 in HID statt. Erlaubte Hilfsmittel und Bonuspunktregelung sind wie bei der ursprünglichen Klausur.

Die vorläufigen Ergebnisse der Nachholklausur vom 13.3. gibt's hier.

Die Klausureinsicht findet am Donnerstag 22.3. (wegen ÖPNV-Streiks doch nicht Mittwoch), 14:00 Uhr statt. Wer sich schon auf Mittwoch eingestellt hat und am Donnerstag nicht kann, soll bitte alternativ am Mittwoch 22.3., 16:30 Uhr vorbeikommen.

Fragestunden zur Klausur finden jeweils am Dienstag, 6.9. und Montag, 12.9. um 14:00 Uhr in NA5/74 statt. Sie können dort auch Übungsblatt 7 abholen und Ihre Gesamtübungspunkte einsehen.

Auf vielfachen Wunsch haben wir eine alte Klausur zur Übung Online gestellt. Der Stil der diesjährigen Klausur wird der selbe sein; insbesondere wird es eine Multiple-Choice-Aufgabe mit dem selben Benotungsschema geben. Beachten Sie jedoch, dass die damalige Vorlesung einen anderen Aufbau hatte, was sich in der alten Klausur wiederspiegelt (keine Frage zu Zahlentheorie, Schwerpunkt mehr auf Kodierungstheorie als auf Komplexitätstheorie). Als Übungsklausur ist die alte Klausur daher möglicherweise nur bedingt geeignet.

Skript zur Vorlesung

01 Mo. 04.04.11 PDF(05.04.) Turingmaschine, Rekursive Aufzählbarkeit, Entscheidbarkeit, Laufzeit, DTIME, P
02 Mo. 11.04.11 PDF(12.04.) Verifizierer, nicht-deterministische Turingmaschine, Klasse NP
03 Mo. 18.04.11 PDF(19.04.) KNF, 3SAT, polynomielle Reduktion
04 Mo. 25.04.11 PDF(26.04.) NP-Vollständigkeit, Satz von Cook-Levin
05 Mo. 02.05.11 PDF(03.05.) NP-Vollständigkeit von 3-SAT, Clique, Knotenüberdeckung, SubsetSum
06 Mo. 09.05.11 PDF(10.05.) Rucksack, Exakte Überdeckung, Hamiltonkreis, Diffie-Hellman, ElGamal
07 Mo. 16.05.11 PDF(17.05.) Sicherheit ElGamal, Quadratische Reste, Reziprozitätsgesetz
08 Mo. 23.05.11 PDF(24.05.) BBS Generator, Goldwasser-Micali Verschlüsselung, Bit Commitment, Elliptische Kurven
09 Mo. 30.05.11 PDF(31.05.) Motivation Kodierungstheorie, Entschlüsselbarkeit, Präfixcode
10 Mo. 06.06.11 PDF(07.06.) Suffix, Sätze von Kraft und McMillan, Huffman-Kodierung, Information
11 Mo. 20.06.11 PDF(21.06.) Entropie, Shannons Theorem, Quellerweiterung, Maximum Likelihood
12 Mo. 27.06.11 PDF(28.06.) Distanz, maximale und perfekte Codes, Singleton- und Plotkin-Schranke
13 Mo. 04.07.11 PDF(05.07.) Lineare Codes, Duale Codes, Parity Check Matrix
14 Mo. 11.07.11 PDF(12.07.) Syndromdekodierung, Hamming-Code, Reed-Muller Code, McEliece

Skript: komplette Vorlesung SS2011 (12.07.2011)

Übungsblätter

Blatt 1 PDF(05.04.2011) Abgabe bis 12.04.2011, 9:00 Uhr in den Briefkaesten in Ebene 02
Blatt 2 PDF(12.04.2011) Abgabe bis 26.04.2011, 9:00 Uhr in den Briefkaesten in Ebene 02
(Achtung: Korrigierte Version, insbesondere wurde in Aufg 1b NP zu P korrgiert.)
Blatt 3 PDF(26.04.2011) Abgabe bis 10.05.2011, 9:00 Uhr in den Briefkaesten in Ebene 02
Blatt 4 PDF(10.05.2011) Abgabe bis 24.05.2011, 9:00 Uhr in den Briefkaesten in Ebene 02
Blatt 5 PDF(24.05.2011) Abgabe bis 07.06.2011, 9:00 Uhr in den Briefkaesten in Ebene 02
Blatt 6 PDF(07.06.2011) Abgabe bis 28.06.2011, 9:00 Uhr in den Briefkaesten in Ebene 02
Blatt 7 PDF(21.06.2011) Abgabe bis 12.07.2011, 9:00 Uhr in den Briefkaesten in Ebene 02

Korrektor: Ilya Ozerov Helpdesk - Sprechstunde montags, 15 Uhr im NA 3/58

Anmeldung/Voraussetzungen

Diskrete Mathematik I

Anmeldung/Voraussetzungen