Diskrete Strukturen - Winter 14
Jump to navigation
Jump to search
- Term
- Winter 14/15
- Lecturer
- Univ.-Prof. Dr. Hans-Joachim Bungartz
- Time and Place
- Vorlesung:
- * Dienstag, 13:45 - 15:15 MI HS 1 (zusätzlich Videoübertragung Interimshörsaal 1)
- * Donnerstag, 10:15 - 11:45 MW 0001
- Zentralübung:
- * Mittwoch, 17:00 - 18:30 MW 0001
- Audience
- Modul IN0015
- Informatik (Bachelor): Pflichtfach
- Wirtschaftsinformatik (Bachelor): Pflichtfach
- Bioinformatics (Bachelor): Pflichtfach
- Informatik: Games Engineering (Bachelor): Pflichtfach
- Tutorials
- Dr. Werner Meixner
- Übungswebseite
- Exam
- 03. Februar 2015, Zeit: 15:30 Uhr bis 18:30 Uhr (Details siehe unter Klausur!)
- Wiederholungsklausur: 28. März 2015, Zeit: 10:00 Uhr bis 13:00 Uhr
- Semesterwochenstunden / ECTS Credits
- 6 SWS (4V + 2Ü) / 8 Credits
- TUMonline
- https://campus.tum.de/tumonline/lv.detail?clvnr=950157189
Contents
Aktuelle Informationen
- Die Wiederholungsklausur wurde vom 31. März auf den 28. März verschoben.
- In der letzten Vorlesungswoche (26.01.-30.01.2015) findet die Vorlesung statt
Donnerstag, 10:15 - 11:45 MW 0001ausnahmsweise statt am Freitag, 30.01.2015, 8:15 Uhr - 9:45 Uhr in MW 0001. - In der 8. Vorlesungswoche (24.11.-28.11.2014) wird Vorlesung und Zentralübung getauscht: Vorlesung: Mittwoch, 26.11., Zentralübung: Dienstag, 25.11. zu den üblichen Zeiten
Vorlesung
Organisatorisches
Inhalt
- Einleitung
- Mathematische und notationelle Grundlagen
- Mengen
- Relationen und Abbildungen
- Aussagen- und Prädikatenlogik
- Beweismethoden
- Wachstum von Funktionen
- Kombinatorik
- Graphentheorie
- Zahlentheorie und Algebraische Kalküle
Änderungen an den Folien
(chronologisch sortiert)
- Reihenfolge von "RSA (Foliensatz 20)" und "Endliche Körper (Foliensatz 21)" getauscht nach "Endliche Körper (Foliensatz 20)" und "RSA (Foliensatz 21)".
- Einleitung (Foliensatz 1), Folie 2: "Zwischen zwei beliebigen..." geändert in "Jeder erdenkliche Wert in Raum und Zeit kann angenommen werden.".
- Mengen (Foliensatz 2)
- Folie 9: "Restklasse" geändert in "Menge der Reste".
- Folie 20: Nicht-Kommutativität des kartesischen Produkts berichtigt.
- Folie 25: "Die beiden Mengen A und B sind disjunkt" geändert in "Dabei seien beide Mengen disjunkt".
- Folie 21: Das "leere Wort" wurde eingeführt
- Relationen und Abbildungen (Foliensatz 3)
- Folie 13: "von b nach c" ersetzt durch "von c nach b"
- Folie 27: "f(a) o f(b)" geändert in "f(a) o g(a)"
- Folie 37: Definition der ceiling-Funktion angepasst, "<=" zu ">=" geändert
- Folie 38: in letzter Zeile "ungleich" zu "gleich" geändert
- Aussagenlogik I (Foliensatz 4)
- Folie 39: zweiter Punkt, ß: V -> {0,1} eingefügt
- Folie 54: letztes Beispiel gestrichen
- Folie 59: F_1 ∧ F_2 ∧ ... ∧ F_n |= F ersetzt durch F_1 ∧ F_2 ∧ ... ∧ F_n |= G
- Folie 59: F_1, ... F_n |= F ersetzt durch F_1, ... F_n |= G
- Folie 63: F->false ersetzt durch F|=false
- Folie 65: "in dem" ersetzt durch "indem"
- Folie 68: "Äquivalenzschemen" ersetzt durch "Äquivalenzschemata"
- Aussagenlogik II (Foliensatz 5)
- Folie 12: Zweimal F[ß]=1 ersetzt durch [F](ß') = 1
- Prädikatenlogik (Foliensatz 6)
- Folie 4: sterblich ersetzt durch ist sterblich
- Folie 8: Wahrheitskonstanten hinzugefügt, 0-stellige Funktionen und Prädikate zugelassen
- Folie 15: "folgendes" ersetzt durch "Folgendes"
- Folie 18: "vielfaches" ersetzt durch "Vielfaches"
- Folie 21: "k-stelliges" ersetzt durch "k-stelligen" (zwei Mal)
- Folie 24: fehlende Klammer am Ende der Formel ergänzt
- Folie 26: "genauso so viele" ersetzt durch "gleich viele"
- Folie 31: Unterer Index: "x:=d" ersetzt durch "x:=b"
- Folie 36: "als sich" ersetzt durch "als sie"
- Folie 38: Letzter Spiegelstrich: "F folgt aus G" ersetzt durch "G folgt aus F"
- Folie 41: ganz unten: "∃x F ∧ ∃x G" statt "∃x F v ∃x G" (ist in den Folien oben nicht angepasst worden)
- Folie 43: "∃x" ersetzt durch "∃y"
- Folie 47: Fehlende Klammer am Ende der Formel ergänzt
- Folie 48: Fehlende Klammer am Ende der Formel ergänzt
- Folie 51: "∀u" ersetzt durch "∃u", Formel neu formatiert
- Folie 54: "∃u" ergänzt, Formel neu formatiert
- Folie 56: "beliebiges" ersetzt durch "beliebiges aber festes"
- Grundlagen: Beweise (Foliensatz 7)
- Folie 7: Klammern in den Formeln (Mitte und unten) korrigiert
- Folie 17: "einen Widerspruch" ersetzt durch "ein Widerspruch"
- Folie 21: Im Induktionsschritt: "n>0" ersetzt durch "n>=1" und "P(0)" ersetzt durch "P(1)"
- Folie 25: In den Mengen MIT und OHNE: L ∈ M ersetzt durch L ⊆ M
- Folie 28: R^n ∈ R^+ ersetzt durch R^n ⊆ R^+
- Folie 32: Teil 3. des Beweises ergänzt
- Kombinatorik (2) (Foliensatz 10)
- Folie 6: 0 aus S_1 entfernt und Berechnung korrigiert
- Folie 26: "in Durchschnitt" ersetzt durch "im Durchschnitt"
- Kombinatorik (3) (Foliensatz 11)
- Folie 18: links, dritte Zeile, {2} durch {3} ersetzt
- Folie 30: Zyklus-Definition neu formuliert, Kommentar zur fehlenden Eindeutigkeit eines Zyklus eingefügt
- Folie 39: Erster Punkt: m<=k angefügt
- Bäume (Foliensatz 14)
- Folie 15: Definition der Gradfolge entfernt
- Planarität und Färbung (Foliensatz 16)
- Folie 4: K3 zu K4 geändert
Übungen
Klausur
Die Klausur findet am Dienstag, den 3. Februar 2015 von 15:30 Uhr bis 18:30 Uhr in folgenden Räumen statt:
- MI HS1 (Friedrich L. Bauer Hörsaal)
- Interims 1
- MW 0001 (Gustav-Niemann-Hörsaal)
- MW 2001 (Rudolf-Diesel-Hörsaal)
- MW 1801 (Ernst-Schmidt-Hörsaal)
- Physik 1 (Rudolf-Mößbauer-Hörsaal)
- Physik 2
- CH1 (Chemie Hörsaal 1)
- CH2 (Ivar-Ugi-Hörsaal)
Die Wiederholungsklausur findet am Samstag, den 28. März 2015 von 10:00 Uhr bis 13:00 Uhr statt.
Bei den Klausuren sind keine Hilfsmittel außer einem beidseitig handbeschriebenen DIN-A4-Blatt zugelassen.
Alte Klausuren
Die folgenden Klausuren sind unter wechselnden Dozenten und Übungsleitungen entstanden.
Die alten Klausuren sind hier verlinkt um einen Eindruck zu vermitteln, wie eine DS-Klausur aussehen kann. Man kann sich die eine oder andere Aufgabe vornehmen, ein komplettes Durchrechnen früherer Klausuren ist aber allein nicht zielführend.
- WS2007/08 (Dozent: Prof. Westermann, Übungsleitung: Dr. Meixner)
- WS2008/09 (Dozent: Prof. Esparza, Übungsleitung: Dr. Meixner)
- WS2009/10 (Dozent: Prof. Esparza, Übungsleitung: Dr. Meixner)
- WS2010/11 (Dozent: Prof. Mayr, Übungsleitung: Dr. Meixner)
- WS2011/12 (Dozent: Prof. Mayr, Übungsleitung: Dr. Meixner)
- WS2012/13 (Dozent: Prof. Mayr, Übungsleitung: Dr. Meixner)
- WS2013/14 (Dozent: Prof. Esparza, Übungsleitung: Luttenberger)
- WS2013/14 Wdh (Dozent: Prof. Esparza, Übungsleitung: Luttenberger)
Literatur
- A. Steger: Diskrete Strukturen, Band 1: Kombinatorik, Graphentheorie, Algebra, (Zweite Auflage) Springer, 2007
- M. Aigner: Diskrete Mathematik, Vieweg+Teubner, 2004 (5. Auflage)
- U. Schöning: Logik für Informatiker . 5. Auflage, Spektrum, 2000.
- K.H. Rosen: Discrete Mathematics And Its Applications, (Several Editions) http://www.mhhe.com/math/advmath/rosen/
- R.L. Graham, D.E. Knuth, O. Patashnik: Concrete Mathematics: a Foundation for Computer Science, Addison-Wesley, 1994
- D. Gries, F.B. Schneider: A Logical Approach to Discrete Math, Springer, 1993
- S. Pemmaraju, S. Skiena: Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Cambridge University Press, 2003
- http://en.wikibooks.org/wiki/Discrete_Mathematics
- http://en.wikipedia.org/wiki/Portal:Discrete_mathematics