English website

Hörerkreis:

1. Semester aller Bachelor-Informatikstudiengänge (Inf, TInf, MInf, WInf, ECom)

Arbeitsaufwand: 7 ECTS-Punkte

Große Übung:
   zur Hauptvorlesung: Mi 11:00 Uhr - 12:15 Uhr, HS 5 
   zu den Teilen Logik und Verifikation: Do 17:00 Uhr - 18:15 Uhr, HS 6, ab 20.10. im Wechsel mit der Übung (siehe gesonderte Webseite)

Terminverschiebung:
21.12., 11 Uhr, HS 5: vorgeholte Vorlesung vom 10.01.
21.12., 17 Uhr, HS 3: Übung bei Helga Karafiat
10.01., 15:30 Uhr: Vorlesung fällt aus

Diese Vorlesung legt das mathematische Fundament für das gesamte weitere Informatikstudium. Es gibt in den Inhalten Querverbindungen zu vielen nachfolgenden oder gleichzeitig stattfindenden Veranstaltungen.

Das Gebiet der Diskreten Mathematik umfasst mehrere Teilgebiete der Mathematik, welche alle mit endlichen oder zumindest abzählbaren Strukturen zu tun haben (Strukturen, die nicht so dicht sind wie z.B. die Menge der reellen Zahlen; genau wird das in der Vorlesung erklärt): Lehre der endlichen und abzählbaren Mengen, Theorie der natürlichen und ganzen Zahlen (Teilbarkeit, Primzahlen, etc.), Algebra in endlichen Mengen, Kombinatorik, Graphentheorie (Theorie der Gebilde aus Knoten und Kanten). Details können der Gliederung unten entnommen werden.

Die Diskrete Mathematik ist für die Informatik so wesentlich wie die aus der Schule besser bekannte Analysis für Physik und Technik.

Die Vorlesung behandelt in den ersten 5 Wochen auch die für ein grundlegendes Verständnis aller mathematischen Überlegungen notwendigen Inhalte der Logik, allgemeinen Mengenlehre und Beweisführung. Vorausgesetzt wird lediglich Schulstoff bis zur 9. Klasse. Damit ermöglicht die Vorlesung auch ein tieferes Verständnis aller anderen Mathematikveranstaltungen an Hochschule und Schule. Die Teilnehmer dieser Vorlesung sollen damit nicht nur für ihr weitere Informatikstudium vorbereitet werden, sondern auch für eine systematische Analysefähigkeit in vielen Anwendungsbereichen des Lebens.

Die Teile Logik und Verifikation gehören ebenfalls zu dieser Vorlesung, werden aber organisatorisch gesondert behandelt: Beachten Sie die gesonderte Webseite.

Im Folgenden werden die nicht zu Logik und Verifikation gehörenden Teile dieser Vorlesung als Hauptvorlesung bezeichnet.

Studierende, welche die Vorlesung Diskrete Mathematik der Prüfungsordnungen eines 6-semestrigen Bachelorstudiengangs machen, müssen nur eine Prüfung in den Inhalten der hier beschriebenen Hauptvorlesung machen.

Studierende, welche die Vorlesung Diskrete Mathematik der Prüfungsordnungen eines 7-semestrigen Bachelorstudiengangs machen, müssen die Prüfung über die Inhalte der Hauptvorlesung und Logik und Verifikation machen.

Studierende, welche von einem 6-semestrigen Bachelorstudiengang in einen 7-semestrigen gewechselt haben und Diskrete Mathematik nach der alten Studienordnung bestanden haben, müssen nur noch die Prüfung in Logik und Verifikation machen (entspricht den Inhalten von GTI). Wer von diesen Studierenden bereits GTI bestanden hat, muss nur noch eine Prüfung über die Inhalte der Hauptvorlesung machen. Die Noten der einzelnen Prüfungsteile werden im Verhältnis 2:1 (DM:GTI) zu einer Gesamtnote mit 7 ECTS-Punkten verrechnet.

Studierende, welche von einem 6-semestrigen Bachelorstudiengang in einen 7-semestrigen gewechselt haben und sowohl Diskrete Mathematik als auch GTI bestanden haben, müssen diese Vorlesung überhaupt nicht mehr belegen: Ihre Prüfungsleistungen werden im Verhältnis 2:1 (DM:GTI) zu einer Gesamtnote mit 7 ECTS-Punkten verrechnet.

Die Übungen zur Hauptvorlesung werden von Helga Karafiat betreut. Frau Karafiat stellt in Absprache mit mir in jeder Woche die Übungsaufgaben und führt die Lösungen eine Woche später in der großen Übung vor. Die Übungsaufgaben stehen auf der Webseite von Frau Karafiat.

Zusätzlich stehen für die Aufarbeitung des Lernstoffs in Kleingruppen studentische Tutoren zur Verfügung. Diese bieten jeweils einmal pro Woche einen Übungstermin an, der freiwillig ist und bei Verständnisschwierigkeiten besucht werden kann (sozusagen "Nachhilfe"). Die Tutorien starten ab dem 15.04. Die Tutoren korrigieren auch die Übungsaufgaben. Jeder Übungsteilnehmer muss sich aus diesem Grund in genau einem Tutorium eintragen, auch wenn er nicht an den Übungsstunden teilnimmt. Die Anmeldung erfolgt im On-line-Studentensekretariat ab dem 08.04. und sollte bis 14.04. abgeschlossen sein. Details dazu werden noch bekanntgegeben. Aktuelle Informationen zu den Tutorengruppen stehen auf der Webseite von Frau Karafiat.

Die Übungsaufgaben sollen selbständig bearbeitet und in der großen Übung in der Woche nach dem Ausgabetermin abgegeben werden (mit Angabe des Übungstermins/Tutors). Der Tutor / die Tutorin streicht die Fehler an und bespricht die wichtigsten Schwierigkeiten im darauf folgenden Tutorium. Außerdem werden Fragen zum laufenden Vorlesungsstoff beantwortet.

Für einen erfolgreichen Studienverlauf gebe ich folgende Empfehlung:

Der Besuch der Vorlesung ist freiwillig, d.h. es wird keine Anwesenheitskontrolle durchgeführt. Dennoch rate ich, an allen Vorlesungen teilzunehmen, da in der Vorlesung viel geübt wird und interaktiv auf Ihre Fragen eingegangen wird. Das Lesen des Skripts ersetzt nicht den Besuch der Vorlesung, sondern ergänzt ihn nur. Ohne einen regelmäßigen Besuch der Vorlesung wird die selbständige Lösung der Übungsaufgaben sehr schwierig sein.

Die Teilnahme an den Übungen ist freiwillig, ebenso die Abgabe und Lösung der Übungszettel. Wer die Übungsaufgaben nicht kontinuierlich bearbeitet, hat nach den Erfahrungen der letzten Semester keine Chance, die Klausur zu bestehen: Die Klausuraufgaben sind von derselben Art wie Übungsaufgaben!

Mathematik wird nicht gelernt, sondern verstanden. Dafür muss geübt werden.

Da viele Studienanfänger die Qualität ihrer Arbeit noch nicht gut einschätzen können, ist eine Abgabe und Kontrolle durch die Tutoren sehr zu empfehlen. Sollte sich dann herausstellen, dass Ihre Lösung nicht den Anforderungen entsprach, dann ist der Besuch von Großer Übung und Tutorenstunde genau das richtige Forum, um das zu verbessern.

Es gibt zur Hauptvorlesung ein Skript, das genau den Lehrstoff dieser Vorlesung widerspiegelt. Dieses Skript erhalten Sie in SkriptDM auf dem Handout-Server (nur für Hochschulangehörige zugänglich). Es ist geplant, das Skript bald als Buch zu veröffentlichen. Aus diesem Grund ist es untersagt, Teile daraus irgendwo zu veröffentlichen. Bitte teilen Sie mir Korrekturbedarf mit. Jeder, der einen Fehler zum ersten Mal findet, wird in der Hitliste unten veröffentlicht (auf Wunsch anonym). In unregelmäßigen Abständen wird das Skript aktualisiert: Der Hinweis erfolgt auf meiner Webseite unter "Aktuelles".

Die meisten Teile des Vorlesungsinhalts werden ferner durch die Bücher von Dean, Meinel et al. und Beutelspacher et al. (s.u.) abgedeckt (in dieser chronologischen Reihenfolge). Unten sind weitere Bücher für Spezialthemen bzw. Vertiefungen angegeben. Sie finden alle angegebenen Bücher in der Hochschulbibliothek.

Die unter den Kapitelüberschriften bereitgestellten Übersichtsfolien dienen als Wegweiser und Inhaltsangabe für die einzelnen Vorlesungseinheiten. Sie dienen nicht als Skriptersatz, d.h. sie sind weder vollständig noch selbst erklärend. Diese Folien könnten noch kurzfristig vor oder auch nach der jeweiligen Vorlesungseinheit aktualisiert werden. In einem solchen Fall wird das letzte Aktualisierungsdatum in rot hinter dem Kapitel angegeben.

In den Vorlesungseinheiten werden die auf den Folien angegebenen Inhalte hauptsächlich an der Tafel präsentiert und mit Beispielen erläutert. Die Lehrinhalte und weitere Beispiele können im Skript und in den zu jedem Kapitel angegebenen Literaturstellen zur Vertiefung nachgelesen werden.

Zur Übung mit endlichen Körpern (Kap. 5.2) gibt es mehrere Programme, die im Rahmen eines Softwareprojekts entstanden sind und hier heruntergeladen werden können.

Die im Folgenden angegebenen Vorlesungswochen sind ein Richtwert, von dem der tatsächliche Vorlesungsablauf um maximal eine Woche abweichen kann.

1. Grundlagen der Mathematik (1. Woche)

    1.1 Einführung

    1.2 Aussagenlogik

    1.3 Prädikatenlogik

2. Mengenlehre (2.-4. Woche)

    2.1 Grundlagen

    2.2 Relationen (Notenbeispiel)

    2.3 Funktionen

    2.4 Boolesche Algebren

3. Beweisführung (4.-6. Woche)

    3.1 Strukturen der mathematischen Beweisführung

    3.2 Vollständige Induktion (3-Teilbarkeit, Bienenaufgabe)

    3.3 Beweisstrategien

4. Zahlentheorie (6.-8. Woche)

    4.1 Teilbarkeit

    4.2 Teilen mit Rest

    4.3 Primzahlen (Beispielrechnungen für ggT und kgV)

    4.4 Modulare Arithmetik

5. Algebraische Strukturen (8.-9. Woche)

    5.1 Gruppen

    5.2 Körper 

6. Kombinatorik (10. Woche)

    6.1 Zählformeln für Mengen

    6.2 Permutationen

7. Graphentheorie (11.-12.Woche)

    7.1 Terminologie und Repräsentation

    7.2 Wege in Graphen (Beispiele, Algorithmenbeispiel zu Dijkstra, Dijkstra für Rechnernetze)

    7.3 Bäume

    7.4 Planare Graphen

    7.5 Färbungen

Vorlesungsskript

Bücher mit engem Bezug zur Vorlesung:

Albrecht Beutelspacher / Marc-Alexander Zschiegner: Diskrete Mathematik für Einsteiger, Vieweg 2004 (2. Auflage), ISBN 3-528-16989-3

Neville Dean: Diskrete Mathematik, Pearson Studium, Reihe "im Klartext" 2003, ISBN  3-8273-7069-8

Christoph Meinel / Martin Mundhenk: Mathematische Grundlagen der Informatik, Teubner 2002 (2. Auflage), ISBN 3-519-12949-3

Weitere Literatur zum Thema Diskrete Mathematik als Alternative oder zur Vertiefung:

Martin Aigner: Diskrete Mathematik, Vieweg 2001 (4. Auflage), ISBN 3-528-37268-0

Norman L. Biggs: Discrete Mathematics, Oxford University Press 2002, ISBN 0-19-850717-8 

Benjamin Klopsch: Endliche Körper - Eine kurze Wiederholung, Seminarunterlagen 2001 (Download mit freundlicher Genehmigung des Autors)

Dirk Hachenberger: Mathematik für Informatiker, Pearson Studium 2005, ISBN 3-8273-7109-0

Hans Kurzweil: Endliche Körper, Springer 2007, ISBN 978-3-540-49081-4

Steffen Lohrke: Endliche Körper, Seminararbeit 2005 bei Prof. Dr. Lang, Vortrag und Ausarbeitung

Jiri Matousek / Jaroslav Nesetril: Diskrete Mathematik - Eine Entdeckungsreise, Springer-Verlag 2001, ISBN 3-540-42386-9

Gerald Teschl / Susanne Teschl: Mathematik für Informatiker, Band 1: Diskrete Mathematik und Lineare Algebra, Springer 2008 (3. Auflage), ISBN 978-3-540-77431-0

Literatur zur allgemeinen mathematischen Horizonterweiterung:

Martin Aigner: Graphentheorie - Eine Entwicklung aus dem 4-Farben-Problem, Teubner 1984, ISBN 3-519-02068-8

Martin Aigner / Ehrhard Behrends: Alles Mathematik - Von Pythagoras zum CD-Player, Vieweg 2002 (2. Auflage), ISBN 3-528-13131-4

Martin Aigner / Günter Ziegler: Proofs from THE BOOK, Springer-Verlag 2010 (4. Aufl.), ISBN 978-3-642-00855-9
in der Bibliothek auch auf Deutsch erhältlich:
Das Buch der Beweise, Springer-Verlag 2004 (2. Aufl.), ISBN 978-3-540-40185-8

Benjamin Klopsch: Audio-CDs und Reed-Salomon-Codes, Seminarunterlagen 2001 (Download mit freundlicher Genehmigung des Autors)

 

Ich bedanke mich bei allen aufmerksamen Lesern meines Skripts seit WS 2008/2009, die mir zahlreiche Hinweise zu Druckfehlern oder missverständlichen Darstellungen geschickt haben.

Im Folgenden gebe ich eine Hitliste bekannt, wer wie viele Fehler gefunden hat, die in regelmäßigen Abständen aktualisiert wird. Es werden nur diejenigen gezählt, die mir einen Fehler erstmals gemeldet haben.

Wer nicht namentlich genannt werden möchte, teile mir das bitte per e-mail mit.

1. Jan Seifert (13 Treffer)

2. Maksim Khazanov (7 Treffer)

3. Janik Lipke (6 Treffer)

4. Alexander Kirtzel (5 Treffer)
4. Nadja Peters (5 Treffer)
4. Anonym (5 Treffer)

7. Simon Monecke (4 Treffer)
7. Samuel David Nazari (4 Treffer)
7. Patrick Satters (4 Treffer)

10. Lars Knickrehm (3 Treffer)

11. Ulrik Jensen (2 Treffer)
11. Christoph Kröger (2 Treffer)
11. Nils Littmann (2 Treffer)
11. Janina Pätzel (2 Treffer)
11. Marcus Riemer (2 Treffer)
11. Timo Schmidt (2 Treffer)
11. Karolina Wochnik (2 Treffer)

18. Ivonne Bieber (1 Treffer)
18. Lennart Bublies (1 Treffer)
18. Patrick Delfs (1 Treffer)
18. Michael Gaida (1 Treffer)
18. Timo Gröger (1 Treffer)
18. Timm Hoffmann (1 Treffer)
18. Carl Jonas Jöhnk (1 Treffer)
18. Nils van Kan (1 Treffer)
18. Christopher Kapusta (1 Treffer)
18. Philipp Kewisch (1 Treffer)
18. Philipp Kneuer (1 Treffer)
18. Christoph Langhein (1 Treffer)
18. Florian Meister (1 Treffer)
18. Henrik Schulz (1 Treffer)
18. Alexander Schwank (1 Treffer)
18. Christopher Sorgenfrei (1 Treffer)
18. Lennart Steffin (1 Treffer)
18. Florian Thiemann (1 Treffer)
18. Lara Vols (1 Treffer)
18. Michael Warnke (1 Treffer)
18. Sören Wrede (1 Treffer)