Vorlesung 1 - 19.10. 10:15

Organisatorisches:

Aktive Teilnahme:

• 60% aller Punkte auf den Übungszetteln
• auf (n-2) Zetteln mehr als 20% der Punkte
• 2x Vorstellen einer Lösung im Tutorium

Regelmäßige Teilnahme:

• (n-2) mal anwesend im Tutorium

Note

• Klausur (120 Minuten) am Ende des Semesters

Inhaltliches:

• Was ist Mathematik?
• Warum brauchen Informatiker:innen Mathematik?
• Definition + Beispiel zu Aussagen

Ausgefallen

Syntax der Aussagenlogik:

• Junktoren
• Induktive Definition eines Terms
• Synataxbaum

Semantik der Aussagenlogik

• Interpretation eines Terms
• Definition Erfüllbarkeit, Tautologie, Kontradiktion, logische Äquivalenz

• Boolsche Gesetze
• Prädikate
• Quantoren

• Beweiser-Gegenspieler Prinzip
• Grundlegendes zu Beweisen
• Direkte Beweise

• direkter Beweis
• indirekte Beweise
  • Kontraposition
  • Widerspruch
  • Fallunterscheidung
• Peano-Axiome

Entspricht Abschnitt 4.2 und 4.3 im Skript

Beweis durch vollständige Induktion

(entspricht Abschnitt 4.3 im Skript)

• Definition von Mengen
• Identitäten auf Mengen
• Mengenfamilien und Partitionen

(entspricht Abschnitt 2 im Skript)

• Kartesisches Produkt
• Relationen
• Äquivalenzrelationen
• Äquivalenzklassen und Repräsentatensysteme

entspricht Abschnitten 3.1 und 3.2 im Skript

Halbordnungsrelationen

• Definition
• Hasse-Diagramm
• Schranken
• totale Ordnung
• lineare Erweiterung

entspricht Abschnitt 3.3 im Skript

(geplant)

Funktionen

• Definition
• Eigenschaften
• Komposition
• Folgerungen aus den Definitionen

Entspricht 3.3 im Skript

• Schubfachprinzip
• Boolsche Funktionen
• Von der Boolschen Funktion zum Boolschen Term I

Abschnitt 4.1 und 1.2

• Kanonische DNF + KNF
• Boolsche Signaturen
• vollständige Boolsche Signaturen

(entspricht 1.2 im Skript)

(geplant)

Resolutionskalkül

entspricht Abschnitt 7.2 im Skript

(geplant)

• Resolutionssatz
• Algorithmus zum Resolutionskalkül
• Abzählbarkeit

(7.2 und 3.5 im Skript)

Abzählbarkeit

Enspricht Abschnitt 3.5 im Skript

Kombinatorik I

-allgemeine Begriffsdefinitionen, Mengensysteme und Kardinalität

-Regeln, Inklusion-Exklusion

-Permutationen

Kombinatorik II

-Abzählen von Teilmengen fester Größe

-Binomialkoeffizienten und Regeln, Pascalsches Dreieck

-Binomischer Satz

Kombinatorik III

-Vandermonde-Indentität, Gitterwege

-Abzählung von Mengenpartitionen, Rekursionsgleichung

Kombinatorik IIII

-Definition k-Zerlegungen und k-Zahlenpartitionen

-Bespiele und Beweise zur Kardinalität

Kombinatorik V

-Beispiele und Beweis: Ungeordnete k-Zahlenpartitionen, Hinweis auf entsprechende k-Zerlegungen

-Prinzip und Beweis vom 'Dopplelten Abzählen', Beispiel Anzahl der Teiler einer Zahl

-Zusammenfassung aller Methoden, Illustration (unterscheidbarer Bälle in unterscheidbare Fächer)

Wahrscheinlichkeitsrechnung I

-Definition Wahrscheinlichkeitsräume und Konstruktion erster Beispiele

-Grundlegende Eigenschaften

-Bedingte Wahrscheinlichkeit und Beispiele

Ausgefallen

-Wahrscheinlichkeitsräume Beispiele

-Satz von Bayes, Ziegenproblem

-Erwartungswert

- Zufallsvariablen und Erwartungswert

- Spezielle Verteilungen

-Binomialverteilung

-Geometrische Verteilung

• Definition von Graphen
• Darstellungen von Graphen
• Grundlegende Begriffe auf Graphen
• Handschlaglemma
• Vereinigung, Schnitt, Komplement von Graphen
• Definition bipartite Graphen

(enstpricht 6.1 im Skript)

• Wichtige Graphen
• Definitionen zum Zusammenhang
• Charakterisierung von bipartiten Graphen

(entspricht 6.1.2 - 6.3 im Skript)

geplant:

• Definition von Bäumen
• Charakterisierung von Bäumen
• Graphtraversierung: Ideen
• Graphtraversierung: Breitensuche

(entspricht 6.4 und 6.5.1(Anfang) im Skript)

• BFS gibt kürzeste Wege
• DFS
• DAGs

(entspricht 6.5.1 bis 6.5.2 im Skript)

• topoplogische Sortierung
• Satz von Euler

(entspricht 6.5.2 und 6.6.1 im Skript)

• planare Graphen
• Vierfarbensatz
• Eulerkreise, Eulerpfade
• Hamiltonkreise, Hamiltonpfade

(enstspricht 6.61 im Skript (+ weitere Quellen))