Loading
     

Modulbeschreibung - Detailansicht

Wichtigste Meldungen anzeigenMeldungsfenster schließen
Moduldetails
Diskrete Strukturen
Fakultät für Informatik
TUINFIN
8
1
6
IN0015
Zuordnungen zu SPO-Versionen
Lehrveranstaltungen und Prüfungsveranstaltungen
Beschreibungen
Export
Allgemeine Daten (Modulhandbuch)
Bachelor
Einsemestrig
Wintersemester
Deutsch
Arbeitsaufwand (Work Load)
240
90
150
Studien- und Prüfungsleistungen
Die Studierenden werden mittels einer schriftlichen Prüfung von 120 - 180 Minuten bewertet. Ein Teil der Prüfungsaufgaben überprüft, ob der Studierende die mathematischen Begriffe aus Mengentheorie, Relationen, Logik, Graphen und den weiteren, in der Vorlesung behandelten Bereichen korrekt anwenden kann. Ein weiterer Teil der Aufgaben überprüft, ob der Studierende dazu in der Lage ist, das richtige Verfahren aus den behandelten Themen zur Lösung eines konkreten Problems auszuwählen und korrekt anzuwenden.
N
J
Beschreibung
keine
Nach erfolgreichem Abschluss des Moduls
- beherrschen Teilnehmer die Grundbegriffe sowie die Grundlagen des Umgangs mit logischen, algebraischen und algorithmischen Kalkülen,
- können kombinatorische Problemstellungen lösen,
- können Probleme mit Methoden der Graphentheorie modellieren und lösen und
- sind zur quantitativen Betrachtung der Effizienz von Lösungsmethoden und Algorithmen in der Lage.
Die Vorlesung ist eine Einführung in die Begriffe und Bereiche der Diskreten Mathematik für Informatiker. Sie gliedert sich in fünf Teilen:

1) Grundbegriffe der Mengen, Relationen und Funktionen:
- Mengen: Grundoperationen, Äquivalenzgesetze, KV-Diagramme,
Abzählbarkeit, Satz von Cantor
- Relationen: Join, Transitive Hülle, Relationale Algebra
- Funktionen: Grundeigenschaften, Komposition, Inverse

2) Grundlagen der Aussagenlogik und Logik erster Stufe:
- Aussagenlogik:
- Syntax und Semantik
- Wahrheitstabellen und Bezug zu KV-Diagramme
- Äquivalenzgesetze
- KNF, DNF, Normalisierungsverfahren, Erfüllbarkeitsäquivalenz
- SAT-Verfahren: DPLL, Resolution. Korrektheitsnachweis
- Modellierung mit Aussagenlogik
- Prädikatenlogik
- Syntax und Semantik
- Äquivalenzgesetze
- Modellierung mit Prädikatenlogik

3) Grundlagen der Kombinatorik:
- Zählprinzipien
- Ziehung von Bällen aus Urnen: Variationen, Permutationen, Kombinationen.
- Binomialkoeffizienten: Symmetrie, Identitäten von Pascal und Vandermonde
- Verteilungsprobleme
- Stirling-Zahlen der ersten und zweiten Art
- Geordnete und ungeordnete Zahlpartitionen
- Anwendung Lastverteilung

4) Grundlagen der Graphentheorie:
- Grunddefinitionen
- Bäume
- Eulerkreise: Satz von Euler. Hamiltonkreise: Sätze von Dirac und Ore
- Planargraphen: Eulersche Polyederformel, Satz von Kuratowski
- Matchings: Heiratssatz, augmentierende Pfade
- Matchings mit Präferenzen: Satz von Gale-Shapley

5) Algebraische Grundlagen:
- Grunddefinitionen: Algebra, Gruppe, Ring, Körper
- Gruppen
- Ordnung: Satz von Lagrange, Erzeuger, Gruppenexponent
- Zyklische Gruppen
- Zahlentheoretische Grundlagen: Größter gemeinsamer Teiler,
Erweiterter euklidischer Algorithmus, Eulersche phi-Funktion
- Multiplikative Restklassengruppen
- RSA
Das Modul besteht aus einer Vorlesung und einer begleitenden Übung. Die Inhalte der Vorlesung werden im Vortrag und durch Präsentation vermittelt. Studierende werden durch kleine, im Laufe der Vorträge gestellte Aufgaben, sowie durch die Lösung von Übungsblättern zur inhaltlichen Auseinandersetzung mit den Themen angeregt. Die Lösung der Übungsaufgaben wird in der Übungsveranstaltung besprochen.
Folienpräsentation, Tafelanschrieb, Übungsblätter.
- A. Steger: Diskrete Strukturen, Band 1: Kombinatorik, Graphentheorie, Algebra, Springer, 2001
- K.H. Rosen: Discrete Mathematics And Its Applications, McGraw-Hill, 1995
M. Aigner: Diskrete Mathematik, Vieweg, 1999 (3rd Edition)
- 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
- D.L. Kreher, D.R. Stinson: Combinatorial Algorithms: Generation, Enumeration, and Search, CRC Press, 1999
- S. Pemmaraju, S. Skiena: Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Cambridge University Press, 2003
- Schöning, Uwe: Logik für Informatiker, Spektrum-Verlag, 2000 (5. Auflage)
Modulverantwortliche*r
Javier Esparza