CITS » Lehre » Sommersemester 2018

Klausureinsicht

Die Klausureinsicht findet am Freitag (14.09.) von 13 - 14 Uhr in der Wasserstraßre 221 (Etage 4) statt. (Nicht am Campus.)

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.

Klausur 15.08.18

Die Klausur findet um 14:30 - 16:30 in drei Hörsälen statt.
Seid bitte frühzeitig da. Die Klausur beginnt pünktlich um 14:30 Uhr.
Als Hilfsmittel ist nur ein beidseitig handschriftlich beschriebener DinA4-Zettel erlaubt.
Die Aufteilung der Studenten auf die Hörsäle erfolgt nach Anfangsbuchstaben des Nachnamens.


Klausur - Aufteilung auf die Hörsäle
Nachname beginnt mit ... Hörsaal
A - H HMA-10
I - R HNB
S - Z HNC-10
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.