26 |

0:00:00 Start

0:00:30 Halbordnungen

0:09:59 Minimale und maximale Elemente/ Beispiel

0:18:32 Untere und obere Schranken/-Beispiel

0:23:29 Supremum und Infimum/-Beispiele

0:36:03 Monotone Abbildungen

0:38:54 Stetige Abbildungen/-Beispiele

0:43:57 Fixpunktsatz/-Beweis

0:52:57 Was ist wichtig ?

0:54:44 Ordungen

0:55:28 Totale Ordung

1:00:06 Totale Ordung auf A*

1:02:30 Milchstraße-Milch-Milchreis-- Beispiel

1:04:08 Lexikographische Ordung (Wörterbuch)

1:14:07 Was ist wichtig

1:15:25 Kapietel 22: MIMA-X

1:17:08 Ackermann-Funktion

1:20:13 Stapel oder Keller

25 |

0:00:00 Start

0:00:22 Äquivalenzrelationen

0:01:41 Kongruenz ganzer Zahlen modulo n

0:04:05 Bild einer Äquivalnzrelation

0:12:15 Was ist wichtig

0:13:40 Äquivalenzrelationen auf mengen mit Struktur

0:18:23 Kongruenzrelationen

0:20:52 Verträglichkeit erlaubt die Übertragung einer Abbildung auf die Faktormenge

0:24:33 Rückblick auf endliche Akzeptoren

0:28:38 Verträglichkeit: Beispiel Nerode-Äquivalenzen

0:37:32 Antisymmetrische Relationen

0:39:52 Halbordnungen

0:41:49 eine Halbordnung auf Wörtern – darauf bauen wir später noch auf

0:43:37 Übung

0:44:44 Reguläre Ausdrücke

0:49:29 Ein regulärer Ausdruck für epsilon

0:54:44 Distributivgesetz

0:56:14 Kantorowitsch-Bäume

1:01:53 Kantorowitsch-Bäume und reguläre Ausdrücke

1:04:51 Beispiel: Zahlen spezifizieren

1:07:14 Ein Wiederbesuch: Wörter umkehren

1:11:32 Rechtslineare Grammatiken

1:15:16 Charakterisierung regulärer Sprachen

1:18:47 Linkslineare Grammatiken

1:23:40 Äquivalenz RL und LL Grammatiken

24 |

0:00:00 Start

0:00:39 Wiederholung(Turingmaschinen)

0:02:42 Endliche Automaten

0:03:56 Reguläre Ausdrücke

0:07:50 Klammereinsparungsregeln

0:12:41 Durch R Beschriebene formale Sprachen / Beispiel

0:14:49 Beispiele für R

0:27:56 Charakterisierungen regulärer Sprachen

0:34:39 Rechtslineare Grammatiken (Typ 3)

0:39:02 Rechtslineare Grammatiken: Beispiele

0:44:42 Sprechweisen

0:47:29 Vorteile rechtslinearer Grammatiken

0:49:49 Kantorowitsch-Bäume und strukturelle Induktion

0:52:31 Mit Kantorowitsch-Bäumen kann man z.B. reguläre Ausdrücke repräsentieren

0:56:25 Regex-Bäume -- etwas genauer

1:00:06 Vollständige Induktion über die Baumhöhe

1:04:44 Skizze des Induktionsschritts

1:12:15 Zusammenfassung

1:14:29 Äquivalenzrelationen

1:15:48 Kongruenz ganzer Zahlen modulo n

1:16:59 Beispiel: asymtptotisches gleiches Wachstum

1:17:33 Urbilder von Fuktionswerten

23 |

0:00:00 Start

0:00:05 Turingmaschinen

0:04:32 Unentscheidbare Probleme

0:04:59 Beispielcodierung

0:16:51 Das Halteproblem

0:19:24 Beweis mit Diagonalisierung

0:30:28 Weitere unentscheidbare Probleme

0:34:48 Erinnerung: BB3

0:36:22 Fleißige Biber und die Busy-Beaver-Funktion

0:43:20 Steam-Powered Turing Machine ;-)

0:44:04 Zusammenfassung

0:44:25 Beginn der Übung

0:44:56 Endlicher Akzeptor

0:48:28 Beispiele regulärer Sprachen

0:52:19 Akzeptoren: Komplement

0:54:53 Akzeptoren: Schnitt

0:59:54 Akzeptoren: Vereinigung

1:03:32 Reguläre Sprachen und kontextfreie Grammatiken

1:07:38 Turing-Maschinen (TMs)

1:17:10 Analyse: Zeit- und Platzbedarf

1:18:56 TM: Akzeptor, Entscheider

1:25:34 TMs und endliche Akzeptoren

1:27:35 Church-Turing-These

22 |

0:00:00 Start

0:00:40 Endliche Automaten

0:02:22 Beispiel einer nicht erkennbaren Sprache

0:13:53 Zusammenfassung / Was ist wichtig ?

0:16:19 Turingmaschinen

0:19:33 Eine Turingmaschine im Bild

0:25:27 Turingmaschine: graphische Darstellung/ tabellarische Darstellung

0:28:42 Beispielberechnung

0:35:53 Längere Beispielberechnung von BB3

0:37:56 Berechnung und Endkonfigurationen

0:48:04 Beispiel: Palindromerkennung

0:56:10 Entscheidbare und aufzählbare Sprachen

1:01:54 Zeitkomplexität - der Rechenzeitbedarf einer TM

1:06:30 Raumkomplexität

1:07:49 Zeitkomplexität versus Raumkomplexität

1:09:48 Eine Komplexitätsklasse ist eine Menge von Problemen

1:11:35 P und PSPACE- Zwei wichtige Komplexitätsklassen

1:17:40 Unentscheidbare Probleme

1:19:46 Codierung von Turingmaschinen

21 |

0:00:00 Start

0:00:30 mMealy-Automaten

0:04:21 Verallgemeinerte Zusatndsübergangsfunktionen

0:06:09 Verallgemeinerte Ausgabefunktionen

0:07:47 Was ist wichtig

0:10:21 Moore-Automat

0:12:43 Verallgemeinerte Zusatndsübergangsfunktionen

0:13:44 Verallgemeinerte Ausgabefunktionen

0:20:06 Endliche Akzeptoren

0:22:59 Akzeptierte und abgelehnte Wörter

0:25:13 Erkannte formale Sprache

0:43:00 Übung 12: asymptotische Analyse und endliche Automaten

0:43:57 Operationen auf Abbildungen

0:50:56 Noch etwas O-Kalkül: unvergleichbare Abbildungen

0:54:40 Master-Theorem

1:04:22 Über Asymptotik hinaus: Schleifendurchläufe zählen

1:07:55 Endliche Automaten

1:09:54 Mealy-Automaten und Zahlendarstellung

1:12:20 Moore-Automat: Beispiel aus der realen Welt

1:14:20 Zustandsfolge, Ausgabe

1:17:01 Umwandlung von Mealy- in Moore-Automaten

20 |

0:00:00 Start

0:00:15 Überblick

0:01:58 2x2 Matrizenmultiplikation

0:06:47 Die Idee von Volker Strassen

0:09:23 Aufwandsabschätzung für den Algorithmus von Strassen

0:13:22 Matrizenmultiplikation- geht es noch schneller? / Teile und herrsche(divide and conquer)

0:16:56 Laufzeit von Teile-und-Herrsche-Algorithmen

0:20:54 Mastertheorem-bescheidener hätte auch gereicht

0:32:48 Rechenzeiten

0:38:58 Zusammenfassung

0:41:51 Endliche Automaten

0:43:33 Ein primitiver Getränkeautomat

0:44:51 Getränkeautomat: Zustände

0:46:39 Getränkeautomat: Eingaben

0:47:40 Getränkeautomat: Zustandsübergänge

0:54:04 Getränkeautomat: Ausgaben

0:58:08 Mealy-Automaten

0:59:45 Verallgemeinerte Zustandsübergangsfunktionen

1:08:34 Was ist wichtig

Lernziele:

Der/die Studierende soll grundlegende Definitionsmethoden erlernen und in die Lage versetzt werden, entsprechende Definitionen zu lesen und zu verstehen.

den Unterschied zwischen Syntax und Semantik kennen.

die grundlegenden Begriffe aus diskreter Mathematik und Informatik kennen und die Fähigkeit haben, sie im Zusammenhang mit der Beschreibung von Problemen und Beweisen anzuwenden.

Lehrinhalt:

Algorithmen informell, Grundlagen des Nachweises ihrer Korrektheit

Berechnungskomplexität, "schwere" Probleme

O-Notation, Mastertheorem

Alphabete, Wörter, formale Sprachen

endliche Akzeptoren, kontextfreie Grammatiken

induktive/rekursive Definitionen, vollständige und strukturelle Induktion

Hüllenbildung

Relationen und Funktionen

Graphen

19 |

0:00:00 Start

0:00:25 Groß-O-Notation

0:15:24 Groß-O-Notation: Notation für obere und untere Schranken des Wachstums

0:25:37 Groß-O-Notation: Eine grauenhafte Schreibweise

0:35:40 Groß-O-Notation: Was ist wichtig

0:37:41 Matrizenmultiplikation: 2x2 Matrizen

0:40:07 nxn Matrizen

0:42:04 Übung

0:43:09 Erinnerung: Matrixmultiplikation

0:46:06 Adjazenzmatrizen

0:48:50 Erreichbarkeitsmatrizen

0:53:02 Wegematrix

0:55:02 Adjazenz- und Wegematrix: Eindeutigkeit

0:57:54 Zusammenhang Matrizen und Relationen in Graphen

1:06:59 O-Kalkül

1:10:53 O-Kalkül: Logarithmen

1:13:13 O-Kalkül: Exponentialfunktionen

1:20:18 O-Kalkül: Fakultät

18 |

0:00:00 Start

0:00:05 Einfachster Algorithmus für die Wegmatrix

0:12:27 Es geht noch besser – erst mehr denken dann weniger rechnen

0:21:11 Algorithmus von Warshall

0:27:56 Quantitative Aspekte von Algorithmen

0:29:38 Ressourcen für Rechnungen

0:37:01 Warum keine exakten Angaben

0:39:46 Zu Notation und Redeweise

0:44:15 Übung 10: Graphen

0:48:34 Graphen: Darstellung von Relationen

0:52:35 Graphen: Maximale Anzahl Kanten

0:58:43 Pfad

1:03:16 (Streng) zusammenhängend

1:06:43 Zusammenhangskomponenten

1:09:13 Ein Paar (gerichtete) Standard-Graphen

1:13:24 Vollständiger Graph (ungerichtet)

1:17:28 Adjazenzmatrix

17 |

0:00:00 Start

0:00:41 Gerichtete Graphen

0:14:08 Ungerichtete Graphen

0:25:12 Ungerichtete Bäume

0:30:42 Symmetrische Relationen

0:32:12 Äquivalenzrelationen

0:36:15 Erste Algorithmen in Graphen

0:41:25 Adjazenzlisten

0:47:18 Repräsentation von Relationen durch Matrizen

0:48:35 Wegematrix eins Graphen

0:55:40 2-Erreichbarkeit an einem Bespiel

0:56:35 Systematische Suche nach Pfaden im Beispiel

1:07:00 Berechnung von E*