Diskrete Mathematik II SS2008

Diskrete Mathematik II

Sommersemester 2008

Vorlesung
Dozent Zeit Raum Erstmals am
Prof. A. May montags, 12.00 - 14.00 HIA 07.04.2008
Prof. A. May dienstags, 10.00 - 11.00 ND 2/99
Übungen
Dozent Zeit Raum Erstmals am
Mathias Herrmann Dienstag, 11:00-13:00 ND 2/99 15.04.2008

Klausur

Wiederholungsklausur

Diskrete Mathematik II: 25. Februar 2009, 14.00Uhr HNB

Klausurergebnisse
Klausureinsicht:
  • Fr. 06.03.2009, 14:00, NA 5/64
  • Diskrete Mathematik II: Fr., 26. September, 10:00 - 11:30 Uhr, NA 5/64
  • Wurde wegen einer Überschneidung um eine halbe Stunde verlängert.
  • Diskrete Mathematik II: 27. August 2008, 9.00Uhr HZO-20
  • Hier finden Sie Informationen zur 2. Klausur Diskrete Mathematik I

Hilfsmittel

  • Diskrete Mathematik II: Nur die Folien!

Fragestunde

  • Diskrete Mathematik II: Mo, 25.08, 14 - 16 Uhr, NB 6/99

Inhalt

Die Vorlesung behandelt diskrete Strukturen, deren Anwendungsgebiete in der algorithmischen Zahlentheorie, der Kryptographie und der Kodierungstheorie liegen.

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. 07.04.08 PDF(08.04.) Grundlagen, Motivation Kodierungstheorie, Codes, Präfixcodes, Kompakte Codes
02 Mo. 14.04.08 PDF(15.04.) Eindeutig entschüsselbare Codes, Sätze von Kraft und McMillan, Huffman-Kodierung
03 Mo. 21.04.08 PDF(22.04.) Information, Entropie, Kodierungstheorem von Shannon, Perfekte Sicherheit
04 Mo. 28.04.08 PDF(29.04.) Maximum Likelihood, Parameter eines Codes, Perfekte Codes
05 Mo. 05.05.08 PDF(05.05.) Optimale Codes, A(n,d), Singleton-Schranke, Plotkin-Schranke, Lineare Codes
06 Mo. 19.05.08 PDF(20.05.) Duale Codes, Parity Check Matrix, Gilbert-Varshamov Schranke, Syndrome
07 Mo. 26.05.08 PDF(27.05.) Äquivalenz linearer Codes, Hamming Code, Simplex Code, Golay Code, Reed-Muller Code
08 Mo. 02.06.08 PDF(03.06.) McEliece, Stern Identifikation, Turingmaschine, Entscheidbarkeit
09 Mo. 09.06.08 PDF(10.06.) DTIME, P, Polynomielle Verifizierer, NP, Nichtdeterminismus, NTIME
10 Mo. 16.06.08 PDF(17.06.) Boolesche Formeln, SAT, 3SAT, Polynomielle Reduktion, NP-Vollständigkeit
11 Mo. 23.06.08 PDF(24.06.) Satz von Cook-Levin, NP-Vollständigkeit von SAT und 3SAT, Knotenüberdeckung
12 Mo. 30.06.08 PDF(01.07.) Reduktionen: SubsetSum, Rucksack, exakte Überdeckung, Hamiltonkreis
13 Mo. 07.07.08 PDF(08.07.) Diffie Hellman, ElGamal, Quadratische Reste, Reziprozität, Legendre/Jacobi Symbol
14 Mo. 14.07.08 PDF(15.07.) Blum-Blum-Shub Zufallsgenerator, GM Kryptosytem, GM Commitment, BG Kryptosytem

Vorlesungsfolien (vollständiger Satz)