CITS » Lehre » Sommersemester 2018

Diskrete Mathematik II

(MEd05 Mod3: Modul 3; MEd13 Mod3: Modul 3; MSc Mod 1: Modul1(G2), Modul1(G3); MSc Mod 2: Modul2(G2), Modul2(G3); MSc Mod 3: Modul3(G2), Modul3(G3); MSc Mod 5: Modul 5 (6 CP))




Bitte melden Sie sich hier für den Kurs an. Das Passwort wird in der ersten Vorlesung bekanntgegeben.

Vorlesung und Übung
Dozent Zeit Raum Erstmals am
Prof. Dr. Alexander May (Vorlesung) Fr. 09:00 - 12:00 HID 13.04.
Dr. Felix Heuer (Übung) Mo. 10:00 - 11:30 NB 3/99 16.04.
Dr. Felix Heuer (Übung) Mo. 12:30 - 14:00 NA 3/99 16.04.
Alexander Helm (Übung) Di. 12:00 - 14:00 ND 3/99 17.04.
Alexander Helm (Vorrechenübung) Di. 14:00 - 16:00 NB 02/99 08.05.

Skript

Kompletter Foliensatz

01 Turingmaschine, Rekursive Aufzählbarkeit, Entscheidbarkeit, Laufzeit, DTIME, P
02 Verifizierer, nicht-deterministische Turingmaschine, Klasse NP
03 KNF, 3SAT, polynomielle Reduktion
04 NP-Vollständigkeit, Satz von Cook-Levin
05 NP-Vollständigkeit von 3-SAT, Clique, Knotenüberdeckung, SubsetSum
06 Rucksack, Exakte Überdeckung, Hamiltonkreis, Diffie-Hellman, ElGamal
07 Sicherheit ElGamal, Quadratische Reste, Reziprozitätsgesetz
08 BBS Generator, Goldwasser-Micali Verschlüsselung, Bit Commitment, Elliptische Kurven
09 Motivation Kodierungstheorie, Entschlüsselbarkeit, Präfixcode
10 Suffix, Sätze von Kraft und McMillan, Huffman-Kodierung, Information
11 Entropie, Shannons Theorem, Quellerweiterung, Maximum Likelihood
12 Distanz, maximale und perfekte Codes, Singleton- und Plotkin-Schranke
13 Lineare Codes, Duale Codes, Parity Check Matrix
14 Syndromdekodierung, Hamming-Code, Reed-Muller Code, McEliece



Termine
Termin Veranstaltung Hausübungen
13.04. Vorlesung 1 Ausgabe Blatt 1
{16,17}.04. Präsenzübungen 0
20.04. Vorlesung 2
{23,24}.04. Präsenzübungen 1
27.04. Vorlesung 3 Abgabe Blatt 1, Ausgabe Blatt 2
04.05. Vorlesung 4
07.05. Präsenzübung 2
08.05. Präsenzübung 2, danach Vorrechenübung Blatt 1
11.05. Vorlesung 5 Abgabe Blatt 2, Ausgabe Blatt 3
15.05. Vorrechenübung Blatt 2
18.05. Vorlesung 6
{28,29}.05. Präsenzübungen 3
01.06. Vorlesung 7 Abgabe Blatt 3, Ausgabe Blatt 4
05.06. Vorrechenübung Blatt 3
08.06. Vorlesung 8
{11,12}.06. Präsenzübungen 4
15.06. Vorlesung 9 Abgabe Blatt 4, Ausgabe Blatt 5
19.06. Vorrechenübung Blatt 4
22.06. Vorlesung 10
{25,26}.06. Präsenzübungen 5
29.06. Vorlesung 11 Abgabe Blatt 5, Ausgabe Blatt 6
03.07. Vorrechenübung Blatt 5
06.07. Vorlesung 12
{09,10}.07. Präsenzübungen 6
13.07. Vorlesung 13 Abgabe Blatt 6
16.07. Fragestunde
17.07. Vorrechenübung Blatt 6
20.07. Vorlesung 14

Kommentar:

Im Studiengang ITS läuft die Vorlesung unter dem Titel "Einführung in die theoretische Informatik".
Die Vorlesung gibt eine Einführung in die Codierungstheorie und in die Theorie der Berechenbarkeit.

Themenübersicht:
- Eindeutig entschlüsselbare Codes
- Kompakte und optimale Codes
- Lineare und duale Codes
- Turingmaschine
- Komplexitätsklassen P und NP
- Polynomielle Reduktion
- Quadratische Reste

Zum Erreichen von 9 CP muss der Inhalt der Vorlesung in der mündlichen Prüfung durch Literatur in Absprache mit dem Dozenten ergänzt werden.