Diskrete Strukturen - Winter 14: Difference between revisions

From Sccswiki
Jump to navigation Jump to search
No edit summary
 
(26 intermediate revisions by 2 users not shown)
Line 9: Line 9:
: * Mittwoch, 17:00 - 18:30 MW 0001
: * Mittwoch, 17:00 - 18:30 MW 0001
| credits = 6 SWS (4V + 2Ü) / 8 Credits
| credits = 6 SWS (4V + 2Ü) / 8 Credits
| audience = [https://campus.tum.de/tumonline/wbStpModHB.detailPage?&pKnotenNr=454051 Modul IN0015]
| audience = [https://campus.tum.de/tumonline/WBMODHB.wbShowMHBReadOnly?pKnotenNr=454051&pOrgNr=14189 Modul IN0015]
:Informatik (Bachelor): Pflichtfach
:Informatik (Bachelor): Pflichtfach
:Wirtschaftsinformatik (Bachelor): Pflichtfach
:Wirtschaftsinformatik (Bachelor): Pflichtfach
Line 17: Line 17:
: [http://www14.in.tum.de/lehre/2014WS/ds/uebung/ Übungswebseite]
: [http://www14.in.tum.de/lehre/2014WS/ds/uebung/ Übungswebseite]
| exam = 03. Februar 2015, Zeit: 15:30 Uhr bis 18:30 Uhr (Details siehe unter [[#Klausur | Klausur]]!)
| exam = 03. Februar 2015, Zeit: 15:30 Uhr bis 18:30 Uhr (Details siehe unter [[#Klausur | Klausur]]!)
: Wiederholungsklausur: t.b.a
: Wiederholungsklausur: 28. März 2015, Zeit: 10:00 Uhr bis 13:00 Uhr
| tumonline = https://campus.tum.de/tumonline/lv.detail?clvnr=950157189
| tumonline = https://campus.tum.de/tumonline/lv.detail?clvnr=950157189
}}
}}


= Aktuelle Informationen =
= 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 <strike>Donnerstag, 10:15 - 11:45 MW 0001</strike> ausnahmsweise statt am '''Freitag, 30.01.2015, 8:15 Uhr - 9:45 Uhr in MW 0001'''.
* In der letzten Vorlesungswoche (26.01.-30.01.2015) findet die Vorlesung statt <strike>Donnerstag, 10:15 - 11:45 MW 0001</strike> ausnahmsweise 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: Donnerstag, 27.11. zu den üblichen Zeiten'''
* 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 =
= Vorlesung =
Line 67: Line 68:
** Folie 21: Das "leere Wort" wurde eingeführt
** Folie 21: Das "leere Wort" wurde eingeführt
* Relationen und Abbildungen (Foliensatz 3)
* 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 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 37: Definition der ceiling-Funktion angepasst, "<=" zu ">=" geändert
Line 73: Line 75:
** Folie 39: zweiter Punkt, ß: V -> {0,1} eingefügt
** Folie 39: zweiter Punkt, ß: V -> {0,1} eingefügt
** Folie 54: letztes Beispiel gestrichen
** 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 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 =
= Übungen =
Line 80: Line 124:
= Klausur =
= Klausur =
Die Klausur findet am Dienstag, den 3. Februar 2015 von 15:30 Uhr bis 18:30 Uhr in folgenden Räumen statt:
Die Klausur findet am Dienstag, den 3. Februar 2015 von 15:30 Uhr bis 18:30 Uhr in folgenden Räumen statt:
* [https://portal.mytum.de/displayRoomMap?roomid=00.02.001@5602 MI HS1] (Informatik Hörsaal 1), Boltzmannstr. 3
* [https://portal.mytum.de/displayRoomMap?roomid=00.02.001@5602 MI HS1] (Friedrich L. Bauer Hörsaal)
* [https://portal.mytum.de/displayRoomMap?roomid=101@5620&disable_decoration=yes Interims 1]
* [https://portal.mytum.de/displayRoomMap?roomid=101@5620&disable_decoration=yes Interims 1]
* [https://portal.mytum.de/displayRoomMap?roomid=2001@5510 MW 2001] (Rudolf-Diesel-Hörsaal), Boltzmannstr. 15
* [https://portal.mytum.de/displayRoomMap?roomid=0001@5510&disable_decoration=yes MW 0001] (Gustav-Niemann-Hörsaal)
* [https://portal.mytum.de/displayRoomMap?roomid=2001@5510 MW 2001] (Rudolf-Diesel-Hörsaal)
* [https://portal.mytum.de/displayRoomMap?roomid=1801@5508&disable_decoration=yes MW 1801] (Ernst-Schmidt-Hörsaal)
* [https://portal.mytum.de/displayRoomMap?roomid=2501@5101&disable_decoration=yes Physik 1] (Rudolf-Mößbauer-Hörsaal)
* [https://portal.mytum.de/displayRoomMap?roomid=2502@5101&disable_decoration=yes Physik 2]
* [https://portal.mytum.de/displayRoomMap?roomid=21010@5401&disable_decoration=yes CH1] (Chemie Hörsaal 1)
* [https://portal.mytum.de/displayRoomMap?roomid=22210@5402&disable_decoration=yes 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.'''
 
* [http://wwwmayr.in.tum.de/lehre/2007WS/ds/uebung/ WS2007/08] (Dozent: Prof. Westermann, Übungsleitung: Dr. Meixner)
* [http://wwwmayr.in.tum.de/lehre/2008WS/ds/uebung/ WS2008/09] (Dozent: Prof. Esparza, Übungsleitung: Dr. Meixner)
* [http://wwwmayr.in.tum.de/lehre/2009WS/ds/uebung/ WS2009/10] (Dozent: Prof. Esparza, Übungsleitung: Dr. Meixner)
* [http://wwwmayr.in.tum.de/lehre/2010WS/ds/uebung/ WS2010/11] (Dozent: Prof. Mayr, Übungsleitung: Dr. Meixner)
* [http://wwwmayr.in.tum.de/lehre/2011WS/ds/uebung/ WS2011/12] (Dozent: Prof. Mayr, Übungsleitung: Dr. Meixner)
* [http://wwwmayr.in.tum.de/lehre/2012WS/ds/uebung/ WS2012/13] (Dozent: Prof. Mayr, Übungsleitung: Dr. Meixner)
* [http://www7.in.tum.de/um/courses/ds/ws1314/files/ds-20140228.pdf WS2013/14] (Dozent: Prof. Esparza, Übungsleitung: Luttenberger)
* [http://www7.in.tum.de/um/courses/ds/ws1314/files/ds-20140329.pdf WS2013/14 Wdh] (Dozent: Prof. Esparza, Übungsleitung: Luttenberger)


= Literatur =
= Literatur =

Latest revision as of 11:02, 14 July 2015

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



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 0001 ausnahmsweise 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

Ä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

Link zu den Übungen

Klausur

Die Klausur findet am Dienstag, den 3. Februar 2015 von 15:30 Uhr bis 18:30 Uhr in folgenden Räumen statt:

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
Retrieved from "https://www5.in.tum.de/wiki/index.php?title=Diskrete_Strukturen_-_Winter_14&oldid=18431"