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

  • 26.10.22: Abschnitt Informationen zur Belegung ergänzt.
  • 20.10.22: Unter Übungsaufgaben wurden die Abgabmodalitäten ergänzt.
  • 17.10.22: Anmeldung für die Übungsgruppen:
    Die konkrete Verteilung der Studierenden auf die Übungsgruppen wird von AGNES durchgeführt. Der erste Anmeldungszeitraum endete am 12.10.22.
    Die Übungsgruppen am Mittwoch und am Donnerstag sind bereits voll. Bisher sind in allen vier Freitags-Übungsgruppen noch recht viele Plätze verfügbar. Falls Sie von AGNES bisher noch keiner Übungsgruppe zugeteilt wurden, melden Sie sich in AGNES bitte für alle Übungstermine am Freitag an – dort sind noch genügend Plätze vorhanden.
    Bitte beachten Sie: Die Nachfrist zur Anmeldung endet schon am 20.10.22!
  • 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 Grundbegriffe und Beweistechniken
  • Kapitel 3: Graphen und Bäume
  • Kapitel 4: Kombinatorik
  • Kapitel 5: Diskrete Stochastik
  • Kapitel 6: Algebraische Strukturen

Das Vorlesungsskript wird nach und nach 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 i.d.R. alle zwei Wochen am Dienstag gegen 17:00 ein Übungsblatt veröffentlicht. Dieses besteht jeweils aus zwei verpflichtenden Aufgaben, sowie ggf. zusätzlichen Präsenzaufgaben.

  • Blatt 0 (ausgeteilt am 18.10, keine Abgabe)
  • Blatt 1 (ausgeteilt am 25.10, Abgabe bis 7.11)
  • Blatt 2 (ausgeteilt am 8.11, Abgabe bis 21.11)
  • Blatt 3 (ausgeteilt am 22.11, Abgabe bis 5.12)
  • Blatt 4 (ausgeteilt am 6.12, Abgabe bis 19.12)

Nachdem das Blatt veröffentlicht wurde, haben Sie bis zum Montag der übernächsten Woche Zeit, die verpflichtenden Aufgaben in Kleingruppen von 2 bis 3 Personen zu bearbeiten und Ihre Lösung gemeinsam als Gruppe über Moodle abzugeben. Die Präsenzaufgaben sollen Sie bearbeiten, deren Lösung jedoch nicht abgeben.

Abgabegruppen in Moodle

Sobald Sie eine Gruppe gebildet haben (nutzen Sie zur Gruppenbildung gerne das Diskussionsforum in Moodle), tragen Sie sich vor der Abgabe einer Lösung in eine der Abgabegruppen in Moodle ein.

Sie können ihre Gruppenzugehörigkeit jederzeit ändern, beachten Sie jedoch, dass Ihre hochgeladenen Lösungen an die Gruppe gekoppelt sind – das heißt, Sie haben nach dem Wechsel keinen Zugriff mehr auf Ihre bisher abgegebenen Lösungen. Führen Sie daher unbedingt selbstständig Buch über Ihre Punkte!

Abgabemodalitäten

Halten Sie sich bei Ihren Abgaben an die folgenden Vorgaben:

  1. Die Lösungen sind handschriftlich anzufertigen. Verwenden Sie kein MS Word, LaTeX o.Ä.
  2. Vermerken Sie auf der ersten Seite Ihrer Lösung ganz oben die Namen und Matrikelnummern sämtlicher an der Abgabe beteiligter Studierender (mindestens 2, höchstens 3). Es erhalten ausschließlich diejenigen Personen Punkte, deren Name vermerkt ist. So könnte der Kopf Ihrer Abgabe aussehen:
    Blatt Nr. X Max Mustermann Mat.Nr. 0101010
      Sabine Musterfrau Mat.Nr. 1001001
  3. Scannen Sie ihre Lösung anschließend ein und laden Sie sie als ein einzelnes PDF in Moodle hoch. Beachten Sie: Moodle akzeptiert höchstens eine Datei und kein anderes Format als PDF. Nach Ablauf der Frist ist in Moodle keine Abgabe mehr möglich. Es ist ausreichend, wenn ein Mitglied der Gruppe die Lösungen hochlädt. Anschließend sollten alle anderen Mitglieder die Lösung ebenfalls in Moodle einsehen können. Ist dies nicht der Fall, prüfen Sie unbedingt Ihre in Moodle hinterlegte Gruppenzugehörigkeit!

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.

 


Informationen zur Belegung dieser Veranstaltung (Höhere Fachsemester)

Wann muss ich Diskrete Sturkturen belegen:

  • Ich fange mein Informatikstudium in diesem Semester an (ich bin in der SPO 2022 immatrikuliert).
  • Ich wechsle in die SPO 2022 und habe das Modul Lineare Algebra oder das Modul Analysis noch nicht bestanden.

Wann muss ich Diskrete Strukturen nicht belegen:

  • Ich studiere in der SPO 2015.
  • Ich habe sowohl das Modul Lineare Algebra als auch das Modul Analysis I bestanden.

Wann kann ich Diskrete Strukturen belegen:

  • Ich studiere in der SPO 2015 und habe Lineare Algebra noch nicht bestanden (In diesem Fall kann ich statt dem Modul Lineare Algebra der SPO 2015 das Modul M1 der SPO 2022 belegen).

Für weitere Fragen dieser Art wenden Sie sich an die Studentische Studienberatung Frau Tessa Bertholdt.

 


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.