Information Security and Cryptography Research Group

Diskrete Mathematik 2020

Dozent: Prof. Ueli Maurer
Chefassistent: David Lanzenberger

Termine

  • 15.09.2020: erste Vorlesung
  • 21.09.2020: erste Montag-Übung
  • 22.09.2020: erste Dienstag-Übung
  • 23.09.2020: erste Fragestunde
  • 27.10.2020: erste Zoom-Vorlesung

Prüfung

Es gelten die Informationen im VVZ.

Als Hilfsmittel zugelassen sind selbstverfasste, handgeschriebene Notizen auf 6 A4-Seiten (respektive 3 Blätter doppelseitig). Handgeschrieben bedeutet, dass die Notizen (inkl. Abbildungen und Diagramme) in der eigenen Handschrift verfasst sein müssen. Die Notizen dürfen unter dieser Bedingung auch auf einem Tablet (per Stift) verfasst werden, müssen aber zwingend in ausgedruckter Form an die Prüfung gebracht werden. Tablet-Notizen müssen so skaliert sein, dass sie auch ohne weitere Hilfsmittel von Hand hätten erstellt werden können. Falls die Notizen nicht auf einem Tablet erstellt wurden, muss an der Prüfung das Original verwendet werden. Kopien sind unabhängig von der Skalierung nicht erlaubt. Das Verwenden einer Lupe oder ähnlicher Hilfsmittel an der Prüfung ist nicht gestattet.

Vorlesung

Die Vorlesungen finden dienstags und mittwochs jeweils 12-14 in Zoom-Meeting 998 3243 1597 statt. Anschliessend sind die Aufzeichnungen unten in der Vorlesungsliste abrufbar. Die Notizen der Zoom-Vorlesung werden (anders als ursprünglich bekannt gegeben) nicht separat veröffentlicht.

Bitte beachten Sie, dass sowohl für die Live-Vorlesung als auch das Abrufen der Aufzeichnung nur eingeloggte Zoom-User mit ethz.ch-Account zugelassen sind (Account-Name muss auf ethz.ch enden, z.B. @ethz.ch oder @student.ethz.ch). Stellen Sie deshalb früh genug sicher, dass Sie einen entsprechenden Account haben und dann auch mit diesem zum Vorlesungsbeginn eingeloggt sind. Falls Sie keinen Account haben, erstellen Sie einen mit E-Mail-Addresse nethzuser@ethz.ch.

Vorlesungen

DatumInhalt
15.09.2020Kap. 1
16.09.2020Kap. 2.1., Kap. 2.2. (teilweise), Kap. 2.3. (1.Teil)
22.09.2020Kap. 2.2. fertig, Kap. 2.3. fertig, Kap. 2.4.1.-3.
23.09.2020Kap. 2.4. fertig
29.09.2020Kap. 2.5., 2.6.1-2.6.8
30.09.2020Kap. 2.6. fertig, Kap. 3.1. (1. Teil)
06.10.2020Kap. 3.1. (2. Teil)
07.10.2020Kap. 3.2.
13.10.2020Kap. 3.3., Kap. 3.4. (1. Teil)
14.10.2020Kap. 3.4. (2. Teil), Kap. 3.5., Kap. 3.6. (1. Teil)
20.10.2020Kap. 3.6. (2. Teil), Kap. 4.1.
21.10.2020Kap. 4.2., Kap. 4.5. (1. Teil)
27.10.2020Kap. 4 fertig, ausser 4.5.4.
28.10.2020Kap. 4.5.4, Kap. 5.1., Kap. 5.2. (1. Teil)
3.11.2020Kap. 5.2. fertig, Kap. 5.3. (1. Teil)
4.11.2020Kap. 5.3. fertig, Kap 5.4.
10.11.2020Kap. 5.5.
11.11.2020Kap. 5.5. fertig, Kap. 5.6.
17.11.2020Kap. 5.7., Kap. 5.8. 1. Teil
18.11.2020Kap. 5.8. 2. Teil, Kap. 5.9.
24.11.2020Kap. 6.1., Kap. 6.2., Kap. 6.3.1.-2.
25.11.2020Kap. 6.3.3.-6., Kap. 6.5.1.-3.
01.12.2020Kap. 6.5.4., Kap. 6.6.1-3.
02.12.2020Kap. 6.6.3.-6.
Das Skript wird in der ersten Übungsstunde zum Selbstkostenpreis (10 CHF) verkauft. Solange Vorrat kann das Skript auch beim Chefassistenten erworben werden.

Innerhalb des ETH-Netzes (nur via VPN, einloggen per WLAN reicht nicht) kann an dieser Stelle das Skript zur Vorlesung heruntergeladen werden.

Errata zum Skript

  • Seite 8: Anstelle von 'The fourth proposition is false. The fifth proposition is not known to be true (or false).' sollte es korrekt heissen: 'The fourth proposition is not known to be true (or false). The fifth proposition is false. The sixth proposition is not known to be true (or false)'.
  • Seite 10: Es fehlt ein Faktor (2^a - 1) vor der Summe (2^{(b-1)a}+2^{(b-2)a} + ... + 2^a + 1).
  • Seite 51,52: In den Definitionen 3.16, 3.17, und 3.18 sollte es jeweils b ∈ A und c ∈ A statt b ∈ B und c ∈ C heissen.
  • Seite 65: Im Beweis von Theorem 3.20 steht fälschlicherweise 'A^{n+1} = A^n x A'. Stattdessen sollte 'A^{n+1} ~ A^n x A' verwendet werden (es gibt eine triviale Bijektion).
  • Seite 66: Im Beweis von Theorem 3.20 (iii) sollte es anstelle von '(f(a_1, ... , f(a_n))' heissen: '(f(a_1), ... , f(a_n))'.
  • Seite 66: In Example 3.66 sollte es anstelle von '({0,1}*)* -> {0,1}^8' heissen: '({0,1}*)* -> {0,1}*'.
  • Seite 73: Anstelle von 'replace the pair (m,n) by the pair (R_n(m),m)' sollte es heissen 'replace the pair (m,n) by the pair (R_m(n),m)'.
  • Seite 108: Anstelle von 'The sum of a(x) and b(x) is a polynomial of degree max(d, d')' sollte es korrekt heissen: 'The sum of a(x) and b(x) is a polynomial of degree at most max(d, d')'
  • Seite 114: In Theorem 5.25 sollte es anstelle von 'there exist a unique monic q(x)' heissen: 'there exist a unique q(x)'.

Fragestunde

Mittwochs um 16:30 findet jeweils eine Online-Fragestunde im Zoom-Meeting 927 3045 0751 statt (zum Beitreten wird ein Zoom-User mit ethz.ch-Account benötigt). Ziel ist es, zusätzliche Fragen zur Vorlesung, zum Skript, und zu den Übungen zu adressieren. Wir empfehlen, Fragen bis eine Stunde vor Beginn der Fragestunde per E-Mail an den Chefassistenten zu senden. Im Voraus gestellte Fragen müssen dann nochmal (zumindest per kurzem Verweis) explizit in der Fragestunde gestellt werden.

Die Struktur der Fragestunde ist wie folgt geplant: In einem ersten Teil werden Fragen im Plenum beantwortet. Dann wird in einen Modus gewechselt, indem Studierende via Zoom Waiting Room einzeln an die Reihe kommen und die Gelegenheit haben, individuelle Verständnisfragen zu stellen. Die Erwartung ist, dass Fragen via Mikrofon gestellt werden; eine aktivierte Kamera ist nicht notwendig (auch nicht im Einzelmodus).

Übung

Die Übungsstunden finden montags und dienstags statt. Typischerweise erscheint ein neues Übungsblatt am Freitag, wird in der nächsten Übungsstunde (Montag oder Dienstag) vorbesprochen, und ist dann am Dienstag der darauffolgenden Woche abzugeben. Die Aufgaben sind in vier Schwierigkeitsstufen von (★) bis (★ ★ ★ ★) eingeteilt. Aufgaben mit einem Stern sollten problemlos gelöst werden können, während Aufgaben mit vier Sternen als Herausforderung gedacht sind. Grundsätzlich sollten alle Aufgaben bearbeitet werden. Auf der Vorlesungswebseite werden alle Aufgaben sowie Lösungsvorschläge zur Verfügung gestellt.

Bonuspunkte

Ab der zweiten Woche, bis zur 13. Woche, wird es Bonusaufgaben geben. Welches die Bonusaufgaben sind, ist auf dem entsprechenden Übungsblatt vermerkt. Die beiden schlechtesten Wochen werden nicht gewertet. Die erworbenen Punkte verbessern das Ergebnis der schriftlichen Prüfung um maximal 0.25 Notenpunkte.

Die Bonuspunkte dienen als Anreiz, um sich regelmässig mit dem Übungsblatt zu befassen. Das regelmässige Arbeiten ist eine der Grundlagen, um das Material gut und effizient zu lernen. Zur Beherrschung des Stoffes ist es nicht ausreichend sich nur mit den Bonusaufgaben zu befassen.

Abgabe der Übung

Eine Abgabe per E-Mail an den Assistenten sollte folgendem Format entsprechen (Beispiel für Übung 4):

  • Betreff: [DM20] Übung 04
  • Anhang: ein einziges PDF (A4-Format, gut lesbare Qualität) mit Dateiname '04_nethzuser.pdf' (nethzuser entsprechend durch das persönliche nethz-Kürzel ersetzen). Auf der ersten Seite des PDFs muss oben der volle Name (Vorname und Nachname) stehen.

Unehrliches Verhalten

Unehrliches Verhalten ist kein Kavaliersdelikt und wird an der ETH ernsthaft bestraft. Insbesondere was die Bonusaufgaben angeht:

  • Das Kopieren von Lösungen von jedweder Quelle (Kommilitonen, Web, etc.) ist nicht erlaubt.
  • Umgekehrt: Lösungen sollten Kommilitonen in keiner Form gezeigt werden.
  • Es ist in Ordnung, in Gruppen zu lernen, aber am Ende müssen die Aufgaben selbständig gelöst werden.

Übungsblätter

AusgabeAbgabeAufgabenLösungen
114.09.2020--Übung 1Lösung 1
218.09.202029.09.2020Übung 2Lösung 2
325.09.202006.10.2020Übung 3Lösung 3
402.10.202013.10.2020Übung 4Lösung 4
509.10.202020.10.2020Übung 5Lösung 5
616.10.202027.10.2020Übung 6Lösung 6
723.10.202003.11.2020Übung 7Lösung 7
830.10.202010.11.2020Übung 8Lösung 8
906.11.202017.11.2020Übung 9Lösung 9
1013.11.202024.11.2020Übung 10Lösung 10
1120.11.202001.12.2020Übung 11Lösung 11
1227.11.202008.12.2020Übung 12

Punkteverteilung Bonuspunkte (bis Übung 8).

Übungsgruppen

Die Einschreibung in die Übungsgruppen erfolgt via myStudies. Bei Problemen oder Unklarheiten bezüglich der Einschreibung wenden Sie sich bitte an den Chefassistenten.

AssistentInSpracheZeitRaum
INFK-01Ferdinand NussbaumDeutschMo 12-14CAB G 52
INFK-02David LanzenbergerDeutschMo 12-14CHN G 46
INFK-03Joel AndréDeutschMo 12-14ETZ E 7
INFK-04Philip JordanDeutschMo 12-14ETZ E 8
INFK-05Marc HimmelbergerDeutschMo 12-14ETZ E 9
INFK-06Olivier FischerDeutschMo 12-14HG E 33.1
INFK-07Marta MularczykEnglischMo 12-14HG E 33.3
INFK-08Fabio BanfiEnglischMo 12-14HG E 33.5
INFK-09Michael HartmannDeutschMo 12-14LEE D 101
INFK-10Igors StepanovsEnglischMo 12-14HG G 26.3
INFK-11Jiamin ZhuEnglischDi 16-18LFW C 1
INFK-12Lukas WalkerDeutschDi 16-18CAB G 52
INFK-13Natalie SuterDeutschDi 16-18HG G 26.5
INFK-14Tristan GirardDeutschDi 16-18CHN D 46
INFK-15Fabio BanfiEnglischDi 16-18HG D 1.2
INFK-16Guilherme RitoEnglischDi 16-18HG D 1.2
INFK-17Leonardo GalliDeutschDi 16-18ETZ E 7
INFK-18Nicolas El MaaloulyEnglischDi 16-18ETZ E 9
INFK-19Blaise MorelDeutschDi 16-18ETZ F 91
INFK-20Robin HänniDeutschDi 16-18ETZ H 91
INFK-21Marta MularczykEnglischDi 16-18ETZ J 91
INFK-22Nicolas EmmeneggerDeutschDi 16-18LFW E 13
INFK-Rest 01Nicolas GrelierEnglischDi 16-18ETZ E 6
RW-01Robin StaabDeutschMo 14-16CHN G 46
RW-02Guilherme RitoEnglischMo 14-16LFW C 1
RW-03Georgijs VilumsDeutschMo 14-16LEE D 105
INFK-ON/RW-ON 01Jiamin ZhuEnglischMo 14-16Zoom-Meeting 968 0366 7976

Zum Beitreten der Online-Übungsstunde wird ein Zoom-User mit ethz.ch-Account benötigt.

Aufzeichnungen Online-Übungsstunde

Zum Abrufen der Aufzeichnungen wird ein Zoom-User mit ethz.ch-Account benötigt.
Datum
21.09.2020
28.09.2020
05.10.2020
12.10.2020
19.10.2020
26.10.2020
02.11.2020
09.11.2020
16.11.2020
23.11.2020
30.11.2020