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.
| Nachname beginnt mit ... | Hörsaal |
|---|---|
| A - H | HMA-10 |
| I - R | HNB |
| S - Z | HNC-10 |
| 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
| 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 |
| 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.