Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Logik in der Informatik

Vorlesung Diskrete Strukturen (WS 22/23)

Aktuelles  Einführung  Inhalt  Logbuch Vorlesungsbetrieb  Übungsbetrieb  Aufgaben   Prüfung    Literatur  


Aktuelles

  • Die Eröffnungsvorlesung findet am Montag, den 24.10.22 um 17:00 Uhr im Hörsaal 0.115 im Erwin-Schrödinger-Zentrum (Rudower Chaussee 26) statt.

  • Die Übungen beginnen für die Gruppen 5-8 in der Woche vom 24.10.22 und für die Gruppen 1-4 in der Woche vom 31.10.22. Für Einzelheiten siehe Abschnitt Übungsbetrieb.
  • Falls Sie an der Veranstaltung "Diskrete Strukturen" teilnehmen wollen, melden Sie sich bitte für eine Übungsgruppe bis zum 12.10.22 (Nachfrist: bis 20.10.22) in AGNES an.
  • Viele wichtige Informationen zur Veranstaltung finden Sie hier auf der Webseite, die regelmäßig aktualisiert wird. Ergänzend dazu werden manche Teile der Veranstaltung über die Moodle-Plattform durchgeführt; bitte schreiben Sie sich dort bis zum 25.10.2022 (Nachfrist 1.11.22) in den Moodle-Kurs ein. Der Einschreibeschlüssel wird an die über AGNES eingeschriebenen Studierenden verschickt (bis 17.10.22) und kann von Teilnehmer*innen, die noch nicht über AGNES eingeschrieben sind, danach auch per Mail an Benjamin Scheidt erfragt werden.
  • Im Logbuch finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden, Teile des Skripts und gelegentlich auch Korrekturen und sonstige ergänzende Bemerkungen.

 


Einführung

In dieser Veranstaltung erlernen Studierende die zum fundierten Verständnis der Informatik notwendigen Grundlagen der diskreten mathematischen Strukturen. Sie erwerben die Fähigkeit, mathematische Aussagen zu verstehen und Beweise selbst zu führen, sowie Probleme präzise zu formulieren und durch Methoden der diskreten Mathematik zu lösen.

Themen

  • Mathematische Grundbegriffe: Menge der natürlichen Zahlen; Unendlichkeit; (Über)Abzählbarkeit; Prinzip der Diagonalisierung; kartesische Produkte; Relationen; Funktionen; rekursive Definitionen; Klärung der Begriffe „Definition", „Satz", „Lemma", „Korollar"
  • Mathematische Beweise verstehen und selbst formulieren: Aussagen und ihre Verknüpfungen; Beweistechniken (direkter Beweis, Beweis durch Kontraposition, Beweis durch Widerspruch, vollständige Induktion)
  • Graphen und Bäume: Grundbegriffe (gerichtete und ungerichtete Variante; Wege; Kreise) und grundlegende Eigenschaften; Isomorphie; Zuordnungsprobleme und ihre Bedeutung für die Informatik (z.B. Modellierung von Problemen durch Matching- oder Färbungsprobleme); Grundbegriffe zu speziellen Graphen (z.B. vollständige Graphen; Binärbäume; bipartite Graphen; planare Graphen)
  • Algebraische Strukturen: modulare Arithmetik; Grundbegriffe zu Gruppen, Körpern und Ringen; endliche Körper und Polynomringe und ihre Bedeutung in der Informatik, z. B. in der Codierungstheorie
  • Kombinatorik: kombinatorische Abzählregeln; das Prinzip des doppelten Abzählens; Binomialkoeffizienten; Schubfachprinzip
  • Diskrete Stochastik: Ereignisse und ihre Wahrscheinlichkeiten; diskrete Wahrscheinlichkeitsräume; Zufallsvariablen; Erwartungswert und Varianz; Markov-Ungleichung; Tschebyscheff-Ungleichung; Ausblick auf randomisierte Algorithmen und deren erwartete Laufzeit bzw. Erfolgswahrscheinlichkeit

 


Inhalt

  • Kapitel 1: Einführung ins Thema
  • Kapitel 2: Mathematische Grundlagen
  • Folgt

Das Vorlesungsskript wird kapitelweise an dieser Stelle veröffentlicht.

 

Beachten Sie:
Zur Vorbereitung auf eine Prüfung wird dringend empfohlen, den gesamten in den Vorlesungs- und Übungsstunden vermittelten Stoff durchzuarbeiten.

 


Logbuch

Im Logbuch finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden, Teile des Vorlesungsskripts und gelegentlich auch Korrekturen und sonstige ergänzende Bemerkungen.

 


Informationen zum Vorlesungsbetrieb

Die Eröffnungsvorlesung findet am Montag, den 24.10.22 um 17:00 Uhr statt.

Mo 11:00 - 13:00 14-täglich Prof. Dr. Nicole Schweikardt RUD26 0.115 Beginn am 31.10.22
Mo 17:00 - 19:00 Wöchentlich Prof. Dr. Nicole Schweikardt RUD26 0.115 Beginn am 24.10.22

Informationen zum Übungsbetrieb

Ergänzend zu den Vorlesungen finden 2-stündige Übungen in kleinen Gruppen statt, in denen Fragen zur Vorlesung diskutiert und die Übungsaufgaben besprochen werden.

Melden Sie sich bitte für eine Übungsgruppe bis zum 12.10.22 (Nachfrist: bis 20.10.22) in AGNES an.

Bitte schreiben Sie sich außerdem zusätzlich bis zum 20.10.22 in den Moodle-Kurs ein. Der Einschreibeschlüssel wird an die über AGNES eingeschriebenen Studierenden verschickt (bis 17.10.22) und kann von Teilnehmer*innen, die noch nicht über AGNES eingeschrieben sind, danach auch per Mail an Benjamin Scheidt erfragt werden.

Tutor*innen

Übungsgruppen

Gruppe 1 Mi 09:00 - 11:00 14tgl./1 Prof. Dr. Nicole Schweikardt RUD26 1.305 Beginn am 02.11.22
Gruppe 2 Do 13:00 - 15:00 14tgl./1 Benjamin Scheidt RUD26 1.305 Beginn am 03.11.22
Gruppe 3 Fr 11:00 - 13:00 14tg.l/1 Benjamin Scheidt RUD26 1.303 Beginn am 04.11.22
Gruppe 4 Fr 13:00 - 15:00 14tgl./1 Benjamin Scheidt RUD26 1.303 Beginn am 04.11.22
Gruppe 5 Mi 09:00 - 11:00 14tgl./2 Prof. Dr. Nicole Schweikardt RUD26 1.305 Beginn am 26.10.22
Gruppe 6 Do 13:00 - 15:00 14tgl./2 Benjamin Scheidt RUD26 1.305 Beginn am 27.10.22
Gruppe 7 Fr 11:00 - 13:00 14tgl./2 Benjamin Scheidt RUD26 1.303 Beginn am 28.10.22
Gruppe 8 Fr 13:00 - 15:00 14tgl./2 Benjamin Scheidt RUD26 1.303 Beginn am 28.10.22

Übungsaufgaben

An dieser Stelle wird alle zwei Wochen ein Übungsblatt ausgegeben.

  • Blatt 0 (wird am 18.10 veröffentlicht, keine Abgabe)

 

Die Lösungen der Aufgaben müssen dann bis zur übernächsten Woche montags um 13:00 Uhr als PDF über Moodle eingereicht werden. Detailregelungen dazu, in welcher Form die Lösungen eingereicht werden sollen, werden in Kürze hier bekannt gegeben. Eine verspätete Abgabe ist nicht möglich.

Die von Ihnen abgegebenen Lösungen werden ab der Woche der Abgabe in den Übungsstunden besprochen und von unseren Tutor*innen korrigiert.

 

Voraussetzung für den Erhalt des Übungsscheins:

Um den Übungsschein zu erhalten, müssen Sie insgesamt mindestens 40% der erreichbaren Punkte bekommen. Wichtig ist hierbei, dass sie lediglich 40% aller Punkte erreichen müssen, nicht 40% der Punkte jedes Blattes. Wir raten Ihnen trotzdem ausdrücklich dazu, sämtliche Übungsblätter zu bearbeiten und einzureichen.

 


Modulabschlussprüfung

Da diese Veranstaltung gemeinsam mit „Lineare Algebra und ihre Bezüge zur Informatik" das Modul M1 bildet, wird die gemeinsame Modulabschlussprüfung am Ende des Sommersemesters 2023 stattfinden. Nähere Informationen werden wir Ihnen rechtzeitig zur Verfügung stellen.

 


Literatur

[S]   N. Schweikardt. Skript zur Vorlesung "Diskrete Strukturen". Humboldt-Universität zu Berlin, 2022-2023.
[J]

 

S. Jukna. Crashkurs Mathematik für Informatiker. Vieweg+Teubner, 2008. Link

[ST]

 

A. Steger. Diskrete Strukturen. Springer, 2007 (2. Auflage). Link

[MM]   C. Meinel und M. Mundhenk. Mathematische Grundlagen der Informatik. Mathematisches Denken und Beweisen. Springer Vieweg, 2015 (6. Auflage). Link
[B]
  A. Beutelspacher. "Das ist o.B.d.A. trivial!" Tipps und Tricks zur Formulierung mathematischer Gedanken. Vieweg, 2002 (6. Auflage). Link
[D]
  R. Diestel. Graphentheorie. Springer, 2017 (5. Auflage). Informationen zum Buch sind hier erhältlich.
[LPV]
  L. Lovasz, J. Pelikan und K. Vesztergombi. Discrete Mathematics. Elementary and Beyond. Springer, 2003. Link

Online-Zugang über VPN

Einige der Bücher sind für Angehörige der HU Berlin online erhältlich (siehe Verlinkung). Loggen Sie Sich dazu auf der Seite via Shibboleth mit ihrem CMS-Account ein (über Log In, Access via your institution, Find your institution: Humboldt Universität zu Berlin). Alternativ können Sie ggf. über eine VPN-Verbindung über das HU-Netz direkt darauf zugreifen. Zur Einrichtung eines VPN-Zugangs siehe die Anleitung des CMS.