Diskrete Mathematik

Vorschlag Jantzen

Umfang: 4 SWS Vorlesung + 2 SWS Übung

Vorausetzungen: keine

Präambel:

Der zu behandelnde Stoff entspricht etwa der bisherigen Vorlesung M1 nach Prof. Andreae: Keine ausführliche Logik (die soll im Modul Grundlagen der Theoretischen Informatik behandelt werden). Der Begriff der booleschen Algebra soll wie die anderen wichtigen Strukturen natürlich nicht fehlen. Ordnungs- und ander Relationen, ungerichtete, gerichtete und kantenbewertete Graphen bzw. Digraphen gehören natürlich zum Inhalt. Eine algorithmische Orientierung (vergl. Steeger, Ihringer!) ist einer ausschließlich abstrakten Sichtweise vorzuziehen!

Lernziele:

• Definitionsprinzipien und Beweistechniken kennen zu lernen und diese in unterschiedlichen Bereichen anwenden zu können,
• Methoden der (strukturellen) Diskreten Mathematik für informatische Probleme anwenden zu können,
• Formale Konzepte der Modellierung kennen- und einsetzen zu lernen,

Lehrinhalte

• Mengen, cartesisches Produkt Abbildungen (injektive, surjektive, Homomorphismus, Isomorphismus), Funktionen (partielle und totale), Relationen, Äquivalenz- und Kongruenzrelationen, Partition, Äquivalenzklassen
• ungerichteter und gerichteter Graph, Multigraph, gewichteter Digraph, Zusammenhangskomponente, Eulersche Linie und Hamiltonscher Kreis, Adjazenz- und Inzidenzmatrix, Gerüst, spannender Baum, planarer Graph, maximale Flüsse und minimale Schnitte
• Strukturen (algebraische, relationale), Halbgruppe, Monoid, Gruppe, zyklische Gruppe, Ringe, Polynomringe, Polynomdivision, euklidischer Algorithmus für Polynome, Körper, Algebra, boolesche Algebra, Venndiagramm
• Ordnungsrelationen, partielle Ordnung (d.h. Halbordnung), strikte (irreflexive) partielle Ordnung, Präzedenzrelation, Hasse-Diagramm, totale Ordnung, lineare Ordnung, Minimum, Maximum, Infimum, Supremum, Wohlordnung, Hüllenbildung, Transitiver Abschluss
• natürliche Zahlen, ganze Zahlen, rationale Zahlen, komplexe Zahlen, reelle Zahlen, Teilbarkeit, Primzahlen, Euler-Funktion, ggT und kgV, euklidischer Algorithmus, modulare Arithmetik
• Beweistechniken (vollständige Induktion, strukturelle Induktion, Noethersche Induktion, Beweis durch Gegenbeispiel, Widerspruchsbeweis, Inklusion, Exklusion), Abzählbarkeit und Überabzählbarkeit, Schubfachprinzip
• Binomialkoeffizienten, binomische Formel, Multinnomialkoeffizient, Pascalsches Dreieck, Permutationen, Permutationsgruppe, homogene lineare Rekurrenzen, Erzeugenden Funkionen
• Matrizennotation und Matrizenprodukt (Beispiel: Komposition von Relationen, keine Lineare Algebra!),

Literatur:

A. Steeger: Diskrete Strukturen, Springer (2001) [anwendungsorientiert, für Studierende der Informatik konzipiert]

M. Aigner: Diskrete Mathematik, vieweg (2001)

N.L. Biggs: Discrete Mathematics, Oxford Science Publ. (1998)

T. Ihringer: Diskrete Mathematik, Teubner (1999) [algorithmenorientiert, viel zu Graphen]

-- WolfgangMenzel -- 24 Sep 2003