Grundlagen und Diskrete Strukturen

Diese Vorlesung deckt Grundlagen aus der diskreten Mathematik für Informatiker ab.

Vorlesung: Dienstag 09:00-10:30 im LdV-Hs 1 und Freitag 11:00-12:30 im LdV-Hs 2
Dozent: Jens M. Schmidt
Übung: Dienstag 11:00-12:30 im Raum Sr H 1527 (Gruppe A) oder Mittwoch 11:00-12:30 im Raum Sr Oe 305 (Gruppe B)
Tutor: Jens Schreyer
SWS: 4V+2Ü
Zielgruppe: Informatik Bachelor 1. Semester, Lehramt Metalltechnik Bachelor 3. Semester
Voraussetzungen: keine
Prüfung:










Prüfungsvoraussetzungen sind die regelmäßige und aktive Mitarbeit in den Übungen, das Vorstellen mindestens einer Übungsaufgabe und das Erreichen von mindestens 50% der Gesamtpunktzahl der Hausaufgaben (die Übungsaufgaben zählen hier nicht zu). Bitte melden Sie sich rechtzeitig im Thoska-System für die Prüfungsvoraussetzung ("Studienleistung") an.

Die Prüfungsvoraussetzung berechtigt zur Teilnahme an der schriftlichen Prüfung, die am Ende des Semesters angeboten wird. Melden Sie sich hierfür gegen Vorlesungsende im Thoska-System an.
Einzig erlaubte Hilfmittel sind eine einseitig handschriftlich beschriebene DIN A4-Seite und eine Formelsammlung in Buchform. Insbesondere also keine eletronischen Hilfmittel, Taschenrechner, Handys, etc.! Bringen Sie zur Prüfung bitte Ihre Thoska-Karte mit.

Bei der Prüfungsbewertung erhalten Sie ein halbes Prozent Bonus für jedes Prozent, das Sie über die nötigen 50% der Prüfungsvoraussetzung hinaus kommen. Dieser Bonus verfällt nach einem Jahr. Die Möglichkeit einer Einsichtnahme ist zu Beginn des folgenden Semesters gegeben.
Klausureinsicht:Am 03.06.2015, 9:00 Uhr im Curiebau, Raum C113.
Literatur:









  • Klaus Kriegel: Logik und Diskrete Mathematik, Skript zur Vorlesung 2012/13, FU Berlin
    (viele Überschneidungen zur Vorlesung, zusätzlicher Fokus auf Rekursion und Logik)
  • Christoph Meinel, Martin Mundhenk: Mathematische Grundlagen der Informatik, Teubner; 5. Auflage 2011
    (deckt den Anfangsstoff weitgehend ab, behandelt aber keine Algebra)
  • Eric Lehman, Tom Leighton: Mathematics for Computer Science, Skript, 2004
    (unterhaltsam geschriebene englische Einführung mit vielen Beispielen)
  • Uwe Schöning: Logik für Informatiker, B.I.-Wissenschaftsverlag; 5. Auflage 2000
    (enthält einige Ergänzungen zur Logik, überdeckt aber auch nur dieses Teilthema)
  • Martin Aigner: Diskrete Mathematk, Vieweg, 5. Auflage 2004
    (über den Vorlesungsstoff hinausgehendes Buch mit Fokus Kombinatorik)


Datum Inhalt Übung Hausaufgaben
14.10.2014 Aussagenlogik Aussagen, Syntax: Operatoren, Boolesche Terme, Rang, Semantik: Boolesche Funktionen ueb01.pdf ha01.pdf
17.10.2014 Aussagenlogik Substitution, DNF, KNF, Signaturen, Funktionale Vollständigkeit, Prädikate, Quantoren ueb02.pdf
21.10.2014 Beweistechniken Negativnormalform, Beweistechniken
24.10.2014 Beweistechniken Induktion mit Peano-Axiomen, Arithmetik auf N, Summenformeln, Unvollständigkeit ueb03.pdf
28.10.2014 Mengenlehre Russelsche Antinomie, Naive Mengenlehre vs. Axiomatische Sicht (ZFC), Konstruktion von N nach Neumann, Mengenoperatoren
31.10.2014
Reformationstag ueb04.pdf ha02.pdf
04.11.2014 Mengenlehre Partitionen, geordnete Paare nach Kuratowski, Kartesisches Produkt, Relationen, Operationen auf Relationen
07.11.2014 Mengenlehre Äquivalenzrelationen und Darstellungen, Äquivalenzklassen, Abschluss, Kongruenzen ueb05.pdf ha03.pdf
11.11.2014 Mengenlehre Halbordnungen und Schranken, Totalordnungen, Lexikographische Ordnungen, Funktionen
14.11.2014 Mengenlehre Eigenschaften von Funktionen + Charakterisierungen, Inverse Funktionen, Endliche und unendliche Mengen, Unendlichkeit nach Dedekind ueb06.pdf
18.11.2014 Mengenlehre Mächtigkeit und Abzählbarkeit, Diagonalisierungsargumente, Reelle und Algebraische Zahlen, Satz von Cantor
21.11.2014 Kombinatorik Schubfachprinzip, Erdós-Szekeres, Ramsey(3,3), Weitere Beispiele zum Schubfachprinzip ueb07.pdf ha04.pdf
25.11.2014 Kombinatorik Summen- und Produktregel, Permutationen, Inklusion / Exklusion, Binomialkoeffizienten
28.11.2014 Kombinatorik Identitäten zu Binomialkoeffizienten, Monotone Gitterwege
ueb08.pdf ha05.pdf
02.12.2014 Kombinatorik
Mengenpartitionen, Anzahl Surjektiver Funktionen, Summendarstellungen
05.12.2014 Kombinatorik Geordnete und ungeordnete Zahlpartitionen, Doppeltes Abzählen ueb09.pdf ha06.pdf
09.12.2014 Kombinatorik Die 12 Arten des Abzählens, Kartentrick
12.12.2014 Wahrscheinlichkeits-
rechnung
Diskrete Wahrscheinlichkeitsräume, Beispiele, Bedingte Wahrscheinlichkeiten, Satz von Bayes ueb10.pdf ha07.pdf
16.12.2014 Wahrscheinlichkeits-
rechnung
Unabhängigkeit, Produkträume, Satz von der totalen Wahrscheinlichkeit, Zufallsvariablen, Erwartungswert
19.12.2014
Vorlesung fällt aus ueb11.pdf ha08.pdf
06.01.2015 Wahrscheinlichkeits-
rechnung
Markow-Ungleichung, Linearität des Erwartungswertes, Varianz, Diskrete Wahrscheinlichkeitsverteilungen, Coupon Collector-Problem
09.01.2015 Ganzzahlige Arithmetik Division mit Rest, ggT, Euklidischer Algorithmus, Lemma von Bezout ueb12.pdf ha09.pdf
13.01.2015 Ganzzahlige Arithmetik Laufzeit des eukl. Alg., Primzahlen, Eindeutigkeit der Primfaktorzerlegung, Unendlichkeit der Primzahlen
16.01.2015 Algebraische Strukturen Algebren, Halbgruppen, Monoide, Gruppen, Beispiele ueb13.pdf ha10.pdf
20.01.2015 Algebraische Strukturen Eindeutigkeit neutraler und inverser Elemente, Rechenregeln, Untergruppen, Symmetrische Gruppe, Zykeldarstellung
23.01.2015 Algebraische Strukturen Erzeugte Untergruppen, Ordnung, Diedergruppen ueb14.pdf
27.01.2015 Algebraische Strukturen Nebenklassen, Satz von Lagrange, Ringe, Körper
30.01.2015 Modulare Arithmetik Kongruenz modulo m, Restklassenringe, Quersummenbeispiel, Einheiten, Charakterisierungen von Einheiten (ohne Beweis), Chinesischer Restsatz ueb15.pdf
03.02.2015 Graphentheoretische Grundlagen Einführung Graphentheorie, Repräsentation von Graphen und Eingabelänge, Handschlaglemma, Zusammenhang, Existenz langer Pfade
06.02.2015 Graphentheoretische Grundlagen Bäume und Wälder, Bipartite Graphen + Algorithmus, Breiten- und Tiefensuche Probeklausur-
aufgaben.pdf