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

Aktuelles

• 19.10.2023: Überarbeitete Fassung des Vorlesungsskripts verfügbar.
• 07.10.2023: Weitere Hinweise zur Klausur ergänzt.
• 21.07.2023: Hinweise zur Klausur ergänzt.
• 30.05.2023: Anfang Juli bieten die Tutor*innen eine Fragestunde zur Prüfungsvorbereitung an. Nähere Informationen finden Sie im Moodle-Kurs unter "Ankündigungen".
• 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 fand 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)
• 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
• 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

Inhalt

• Kapitel 1: Einführung ins Thema
• Kapitel 2: Mathematische Grundbegriffe und Beweistechniken
• Kapitel 3: Graphen und Bäume
• Kapitel 4: Kombinatorik
• Kapitel 5: Stochastik
• Kapitel 6: Algebraische Strukturen

Komplettes Vorlesungsskript (Version vom 19.10.2023).

Eine in einzelne Kapitel aufgeteilte Vorab-Version wurde bereits im Laufe des WS 22/23 nach und nach an dieser Stelle veröffentlicht:

• Titelseite
• Kapitel 1
• Kapitel 2
• Kapitel 3
• Kapitel 4
• Kapitel 5
• Kapitel 6
• Literatur

Beachten Sie:
In den Vorlesungs- und Übungsstunden wird hauptsächlich an der Tafel gearbeitet. Alle behandelten Inhalte sind für die Veranstaltung wesentlich und daher auch dann prüfungsrelevant, wenn sie nicht in den auf den Webseiten oder in Moodle erhältlichen Materialien enthalten sind. Zur Vorbereitung auf eine Prüfung wird dringend empfohlen, das gesamte in den Vorlesungs- und Übungsstunden vermittelte Material durchzuarbeiten. Es ist daher wichtig, dass Sie sich während der Vorlesungs- und Übungsstunden Notizen machen.

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.

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

• Anke Bianchi
• Charlotte Lenz

Übungsgruppen

Ü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)
• Blatt 5 (ausgeteilt am 20.12, Abgabe bis 16.1)
• Blatt 6v2 (ausgeteilt am 17.1, Abgabe bis 30.1) Beachten Sie die kleinen Änderungen an Aufgabe 1.
• Blatt 7 (ausgeteilt am 31.1, Abgabe bis 13.2)

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.

Den vollständigen Prüfungsplan sowie Hinweise zur An- und Abmeldung finden Sie auf der Seite des Prüfungsbüros.

M1 (Prüfungsnummer 1579)

Die Klausur des Moduls M1 findet im ersten Prüfungszeitraum am 31.07.2023 um 12:00 Uhr in den Räumen RUD26 (ESZ) 0'115 (und ggf. 0'110, 0'306) statt; im zweiten Prüfungszeitraum findet die Klausur am 10.10.2023 um 9:00 Uhr in den Räumen RUD26 (ESZ) 0'115 (und ggf. 0'311) statt. Sie wird durch Frau Dr. Otwinowska (M1.2 im SoSe23) organisiert. Bei Fragen wenden Sie sich an Frau Dr. Otwinowska und ggf. an die Seite des Prüfungsbüros.

Diskrete Strukturen für Wechselnde (Prüfungsnummer 1578)

Die Klausur „Diskrete Strukturen für Wechselnde“ dauert 75 Minuten.

Sie findet im ersten Prüfungszeitraum am 31.07.2023 um 12:15 Uhr (Einlass ab 12:05 Uhr) in Präsenz in Raum RUD26 (ESZ) 0'310 statt. Die vorläufigen Ergebnisse werden Sie in Agnes spätestens am 04.08.23 um 10:00 Uhr in Ihrem Leistungsspiegel einsehen können. Die Einsicht findet am 04.08.23 von 11:00 bis 12:00 Uhr in Raum RUD25 (JvN-Haus) 3.408 statt.

Im zweiten Prüfungszeitraum findet die Klausur am 10.10.2023 um 9:15 Uhr (Einlass ab 9:10 Uhr) in Präsenz in Raum RUD26 (ESZ) 0'313 statt. Die vorläufigen Ergebnisse werden Sie in Agnes spätestens am 13.10.23 um 10:00 Uhr in Ihrem Leistungsspiegel einsehen können. Die Einsicht findet am 13.10.23 von 11:00 bis 12:00 Uhr in Raum RUD25 (JvN-Haus) 3.408 statt.

Auf der folgenden verlinkten Seite finden Sie weitere Hinweise zur Klausur „Diskrete Strukturen für Wechselnde“.

Literatur

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.