FU Logo
Institute of Computer Science

Inhaltlich und zeitlich wird sich die Vorlesung in etwa in diesem Rahmen bewegen.

Hinweis: Das Vorlesungsskript ist handgeschrieben und ist nur aus dem Universitätsnetz erreichbar, die obige Übersicht ist dagegen von überall abrufbar.

 

Nr.DatumThemaSkript

1

18.10.05

Grundbegriffe der Aussagenlogik

  • Was sind Aussagen?
  • Logische Operatoren
  • Induktive Definition der Syntax der Aussagenlogik
  • Boolesche Formeln (Terme)
  • Rechnen mit Wahrheitswerten (Boolesche Algebra)

VL1

2

20.10.05

Vom Booleschen Term zur Booleschen Funktion

  • Baumdarstellung eines Terms, Klammerstruktur
  • Rang einer Formel
  • bottom-up-Auswertung bei gegebener Variablenbelegung, zugeordnete Boolesche Funktion
  • Semantische Äquivalenz von Termen
  • Bindungsstärke der logischen Operatoren
  • Boolesche Gesetze beim Umformen von Termen
  • das Substitutionsprinzip

VL2

3

25.10.05

Von der Booleschen Funktion zum Booleschen Term

  • Anzahl n-stelliger Boolescher Funktionen
  • Aufgabe: Finde zur Funktion einen Term, der sie repräsentiert
  • Terme in DNF, KNF
  • die kanonische dnf(f), knf(f)
  • Interpretation im Hyperwürfel
  • vollständige Mengen Boolescher Operatoren

VL3

4

27.10.05

Minimierung von DNF-Formeln, Prädikate und Quantoren

  • vollständige Minterme
  • Überdeckungen mit Unterwürfeln
  • geometrische Interpretation
  • Aussageformen
  • Quantifizierte Aussagen
  • Rechnen mit Quantoren

VL4

5

01.11.05

Mengen und Operationen auf Mengen

  • Mengen Begriff
  • Darstellung von Mengen
  • Operationen auf Mengen, Identitäten
  • Mengen Familien, Potenzmenge und ihre Mächtigkeit
  • Kartesisches Produkt

VL5

6

03.11.05

Binäre Relationen und Operationen auf Relationen

  • Binäre Relationen
  • Darstellungen
  • Operationen auf Relationen, Verknüpfung
  • Eigenschaften von Relationen
  • Abschluss bezüglich einer Eigenschaft
  • Äquivalenzrelation, Äquivalenzklassen

VL6

7

08.11.05

Äquivalenzrelationen

  • Partition einer Menge
  • Äquivalenzrelation definiert Partition
  • Partition definiert Äquivalenzrelation
  • Operationen auf Äquivalenzrelationen

VL7

8

10.11.05

Halbordnungsrelationen

  • Vollständiges Repräsentantensystem einer Äquivalenzrelation
  • Halbordnungsrelation, Ordnungsrelation
  • Hasse-Diagramm
  • Lexikografische Ordnung
  • untere/obere Schranken

VL8

9

15.11.05

Lineare Erweiterungen von Posets; Funktionen

  • totale Ordnung, lineare Erweiterung eines Posets
  • Satz: Jedes endliche Poset hat lineare Erweiterung (totpologisches Sortieren)
  • Grundlegende Begriffe zu Funktionen
  • Charakteresierung surjektiver, injektiver, bijektiver Funktionen

VL9

10

17.11.05

Abzählbare und überabzählbare Mengen

  • Mächtigkeit, Gleichmächtigkeit
  • endliche, abzählbar unendliche Mengen
  • Rationale Zahlen sind abzählbat
  • Überabzählbarkeit, Diagonalisierungsbeweise
  • Bsp.: Reele Zahlen sind überabzählbar, Potenzmenge von N ist überabzählbar

VL10

11

22.11.05

Beweistechniken

  • direkter Beweis, Kontraposition, Widerspruchsbeweis, Fallunterscheidung
  • Taubenschlagprinzip, Satz von Erdös-Szekeres

VL11

12

24.11.05

Beweis mittels vollständiger Induktion

  • Peanoschen Axiome
  • Beispiele

VL12

13

29.11.05

Strukturelle Induktion, Grundlegende Zählprinzipien

  • Strukturelle Induktion
  • Grundlegende Zählprinzipien: Summenregel, Produktregel, Inklusion-Exklusion Prinzip
  • Permutationen
  • k-elementige Untermengen

VL13

14

01.12.05

Rechnen mit Binomialkoeffizienten, Gitterwege

  • Binomialkoeffizienten
  • Pascalsches Dreieck, Vandermondsche Gleichung, Binomischer Satz
  • Gitterwege

VL14

15

06.12.05

Mengenpartitionen, Zahlpartitionen

  • Partitionen von n-elementigen Mengen, Stirling Zahlen 2. Art
  • Zahlpartitionen, geordnet und ungeordnet

VL15

16

08.12.05

Abzählen, die Übersicht

VL16

17

13.12.05

Diskrete Wahrscheinlichkeitsrechnung, die Grundlagen

  • endlicher Wahrscheinlichkeitsraum, Ereignis
  • elementare Eigenschaften eines Wahrscheinlichkeitsraums
  • bedingte Wahrscheinlichkeit, unabhängige Ereignisse

VL17

18

15.12.05

Diskrete Wahrscheinlichkeit, Beispiele, Zufallsvariable, Erwartungswert

  • Satz von Bayes
  • Rechnen mit bedingten Wahrscheinlichkeiten
  • Zufallsvariable, Erwartungswert

VL18

19

03.01.06

Erwartungswert

VL19

20

05.01.06

Varianz, Ungleichungen von Markov und Tschebyschev, spezielle Verteilungen

VL20

21

10.01.06

Geometrische Verteilung, das Coupon-Collector-Problem
Einführung in die Graphentheorie und algorithmische Fragen

VL21(1) VL21(2) [ps] VL21(2) [pdf]

22

12.01.06

Grundlegende graphentheoretische Begriffe, Bipartite Graphen

VL22 [ps] VL22 [pdf]

23

17.01.06

Bäume und ihre Charakterisierung, Breitensuche

VL23

24

19.01.06

Korrektheit BFS, Tiefensuche und Topologisches Sortieren

VL24

25

24.01.06

Minimum Spanning Tree, Algorithmen von Prim und Kruskal

VL25

26

26.01.06

Flüsse in Netzwerken

VL26 Ford-Fulkerson-Beispiel

27

31.01.06

Resolution I

VL27

28

02.02.06

Resolution II

VL28

29

07.02.06

30

09.02.06

31

14.02.06

32

16.02.06

Mathematik für Informatiker I
Literatur
Scheine/Klausur
Übungsaufgaben
Vorlesungen
Impressum