Grundbegriffe der Informatik, Vorlesung, WS16/17

26 |

0:00:00 Starten

0:00:04 Kapitel 21: Relationen

0:00:59 Antisymmetrische Relationen

0:03:57 Halbordnungen

0:05:52 eine Halbordnung auf Wörtern - darauf bauen wir später noch auf

0:07:28 Wenn man weiß, dass es eine Halbordnung ist, enthält der gesamte Graph Redundantes

0:08:51 Wenn man weiß, dass es eine Halbordnung ist, genügt das Hassediagramm

0:10:31 Das Hassediagramm enthält <>

0:11:32 Minimale und maximale Elemente

0:12:56 Beispiele minimaler und maximaler Elemente

0:13:22 Kleinste und größte Elemente

0:14:14 Beispiele kleinster und größter Elemente

0:15:22 Das kleinste und das größte Element sind eindeutig

0:16:02 Untere und obere Schranken von T - unter Umständen auch außerhalb von T

0:16:52 Untere und obere Schranken: Beispiele

0:17:27 Untere und obere Schranken müssen nicht existieren

0:18:43 Supremum und Infimum

0:19:45 Supremum und Infimum: Beispiele

0:21:47 Aufsteigende Ketten

0:23:08 Vollständige Halbordnungen

0:24:34 Vollständige Halbordnungen: weitere (Nicht-)Beispiele

0:27:09 Monotone Abbildungen

0:28:20 Stetige Abbildungen

0:29:14 Stetige Abbildungen: Beispiel 1

0:31:15 Stetige Abbildungen: Beispiel 2

0:32:10 Fixpunktsatz

0:33:58 Fixpunktsatz: Beweis

0:37:13 Was ist wichtig

0:38:25 Totale Ordnung - keine unvergleichbaren Elemente

0:40:27 Totale Ordnungen auf A*

0:42:16 Lexikographische Ordnung (Wörterbuch)

0:45:37 Lexikographische Ordnung <> - die im Wörterbuch

0:46:07 Lexikographische Ordnung

0:48:12 Lexikographische Ordnung <>

0:49:31 Die lexikographischen Ordnungen sind total

0:51:00 Was ist wichtig (2)

0:51:42 Kapital 22: MIMA-X

0:51:55 MIMA-X - eine Erweiterung der MIMA

0:53:20 Erinnerung: die Ackermann-Funktion A

0:54:00 Ackermann-Funktion Beispielberechnung für A(2,2)

0:54:18 Ackermann-Funktion A(2,2) kompakt notiert

0:56:27 Stapel oder Keller - Zugriff nur auf das oberste Element

0:58:04 Stapel - eine mögliche ""Implementierung""

0:58:27 Stapel - bequeme Verallgemeinerung

0:58:54 Berechnung der Ackermann-Funktion mit einem Stapel

1:00:25 Jede k-stellige Operation auf V ist auf Stapel mit mindestens k Einträgen übertragbar

1:02:01 Stapel - Implementierung in einem Rechner

1:03:36 Mimax- drei zusätzliche Register für Adressen

1:05:53 Register RA speichert eine Rückkehradresse

1:06:42 CALL und RET - Wiederverwendung von Codestücken durch primitiven Unterprogrammaufruf

1:08:12 SP und FP

1:08:59 Speicherzugriffe mittels SP

1:09:49 Veränderungen des SP-Registers

1:10:34 Realisierung von push, top und pop

1:11:30 push und pop von RA - für ineinander geschachtelte CALL

1:13:09 Wir halten fest

27 |

0:00:00 Starten

0:00:04 Aufgabe 6.1

0:04:44 Aufgabe 6.2

0:11:12 Aufgabe 6.3

0:16:19 Aufgabe 6.4

0:22:26 Aufgabe 7.1

0:28:13 Aufgabe 7.2

0:36:24 Aufgabe 7.3

0:39:42 Aufgabe 7.4

25 |

0:00:00 Starten

0:00:04 Kapitel 20: Turingmaschinen

0:00:25 Wo sind wir?

0:01:45 Codierungen von Turingmaschinen

0:04:54 Beispielcodierung

0:09:44 Eigenschaften dieser und ähnlicher Codierungen

0:11:50 Das Halteproblem ist unentscheidbar

0:18:37 Diagonalisierung

0:24:07 Das Halteproblem

0:24:22 Beweis der Unentscheidbarkeit des Halteproblems

0:28:37 Weitere unentscheidbare Probleme

0:36:10 Erinnerung: BB3

0:37:03 Bibermaschinen

0:38:26 Busy-Beaver-Funktion

0:42:51 Was ist wichtig

0:43:53 Steam-Powered Turing Machine

0:47:48 Zusammenfassung

0:51:51 Kapitel 21: Relationen

0:52:28 Überblick

0:52:51 Äquivalenzrelationen

0:53:41 Identität

0:54:18 Kongruenz ganzer Zahlen modulo n

0:55:12 Beispiel: asymptotisch gleiches Wachstum

0:55:24 Urbilder von Funktionswerten

0:57:50 Bild einer Äquivalenzrelation

0:59:27 Äquivalenzklassen und Faktormengen

1:00:40 Beispiel: Äquivalenzklassen und Kogruenz modulo 2

1:02:21 Was ist wichtig

1:02:49 Äquivalenzrelationen auf Mengen mit ""Struktur""

1:03:27 Verträglichkeit von Äquivalenzrelationen mit Abbildungen

1:05:49 Kongruenzrelation

1:06:28 Eine Operation für Äquivalenzklassen modulo n?

1:08:20 Verträglichkeit erlaubt die Übertragung einer Abbildung auf der Faktormenge

1:09:14 eine Operation für Äquivalenzklassen modulo n?

1:10:10 Was ist wichtig

1:10:54 Wo sind wir?

1:11:02 Motivation

1:13:02 Äquivalenzrelationen von Nerode einer Sprache

1:14:30 Beispiel

1:18:35 Die Nerode-Relation is immer eine Äquivalenzrelationen

1:19:09 Verträglichkeit: Beisoiel Nerode-Äquivalenzen

1:20:44 Eine Abbildung für Nerode-Äquivalenzklassen

1:21:22 Nerode-Äquivalenzen: Ausblick

24 |

0:00:00 Starten

0:00:59 Algorithmusbegriss informell

0:03:47 Erinnerung: partielle Funktion von A nach B

0:05:39 Turingmaschinen: Ursprung

0:08:33 Eine Turingmaschine im Bild

0:13:48 Turingmaschine formalisiert

0:15:28 Turingmaschine: graphische Darstellung

0:19:23 Turingmaschine: tabellarische Darstellung

0:20:26 Beispielberechnung

0:23:01 Turingmaschine: Konfigurationen

0:25:48 Turingmaschine: "" überschaubare"" Bandbeschriftungen

0:27:48 Ein Schritt einer Turingmaschine

0:30:31 Längere Beispielberechnung von BB3

0:33:13 Berechnungen und Endkonfigurationen

0:36:18 Rechnen bir zur Endkonfiguration

0:37:14 zwei Arten von Turingmaschinen

0:38:15 Eingaben und Anfangskonfigurationen

0:40:53 Ergebnisse von Turingmaschinenberechnungen

0:44:19 Beispiel: Palindromerkennung

0:58:27 Entscheidbare und aufzählbare Sprachen

1:01:36 Was ist wichtig

1:06:22 Berechungskomplexität

1:07:59 Zeitkomplexität - der Rechenzeitbedarf einer TM

1:12:43 Zeitkomplexität der TM für Palindromerkennung

1:14:39 Platzkomplexität oder Raumkomplexität einer TM

1:15:54 Raumkomplexität der TM für Palindromerkennung

1:17:18 Zeitkomplexität versus Raumkomplexität

1:20:03 Eine Komplexitätsklasse ist eine Menge von Problemen

1:22:29 P und PSPACE - zwei wichtige Komplexitätsklassen

1:25:02 Beziehung zwischen P und PSPACE - unklar

1:27:55 Was ist wichtig

23 |

0:00:00 Starten

0:00:05 Beispiel einer nicht erkennbaren Sprache

0:03:01 Beispiel einer nicht erkennbaren Sprache (2)

0:06:44 Beispiel einer nicht erkennbaren Sprache (3)

0:12:49 Was ist wichtig

0:14:26 Zusammenfassung

0:15:48 Was können endliche Akzeptoren

0:16:20 Überblick

0:18:46 Der Begriff regulärer Ausdruck hat heute verschiedene Bedeutungen

0:19:49 Definition regulärer Ausdrücke (1)

0:22:58 Beispiele

0:23:44 Klammereinsparungsregeln

0:25:01 Beispiele für Klammereinsparungsregeln

0:26:05 Nichtbeispiele

0:27:31 Definition der Syntax regulärer Ausdrücke

0:29:03 Ableitungsbaum eines regulären Ausdrucks

0:29:44 Durch R beschriebene formale Sprache

0:30:55 Beispiele für

0:32:44 Bestimmung von entlang des Ableitungsbaums von R

0:34:08 Wie ist das denn eigentlich?

0:35:24 Äquivalenz regulärer Ausdrücke

0:37:40 Weitere Beispiele für

0:40:26 RFC 5322: Internet Message Format

0:43:01 RFC 5322, Abschnitt 3.3: Date and Time Specification, fast wörtlich:

0:45:39 Datums- und Zeitangaben in Emails (2)

0:46:28 Datums- und Zeitangaben in Emails (3)

0:48:07 Charakterisierungen regulärer Sprachen

0:50:46 Zum Beweis des Satzes

0:53:39 Was ist wichtig

1:00:13 Rechtslineare Grammatiken: Definition

1:01:58 Rechtslineare Grammatiken: Beispiele

1:04:06 Rechtslineare Grammatiken: Nichtbeispiel

1:04:52 Sprechweisen

1:06:53 Vorteil rechtslinearer Grammatiken

1:07:54 Ziel dieses Abschnittes

1:09:18 Mit Kantorowitsch-Bäumen kann man z.B. reguläre Ausdrücke repräsentieren

1:10:53 Regex-Bäume - etwas genauer

1:12:17 Vollständige Induktion über die Baumhöhe

1:13:33 Vollständige Induktion über die Baumhöhe - ein Problem

1:15:08 Erinnerung: Verallgemeinerung vollständiger Induktion

1:15:49 Induktion über die Höhe der Regex-Bäume

1:17:49 Skizze des Induktionsschritts (1)

1:18:45 Skizze des Induktionsschritts (2)

1:21:07 Strukturelle Induktion

1:22:25 Zusammenfassung

22 |

0:00:00 Starten

0:00:04 Einheit 17: Quantitative Aspekte von Algorithmen

0:01:45 Rechenzeiten

0:13:35 Was ist wichtig

0:14:07 Zusammenfassung

0:14:55 Kapitel 18: Endliche Automaten

0:15:46 Ein primitiver Getränkeautomat

0:16:47 Getränkeautomat: Zustände

0:19:27 Getränkeautomat: Eingaben

0:21:18 Getränkeautomat: Zustandsübergänge

0:29:52 Getränkeautomat: Aufgaben

0:35:07 Maely-Automaten

0:37:33 Verallgemeinerte Zustandsübergangsfunktionen

0:45:08 Verallgemeinerte Ausgabenfunktion

0:49:09 Moore-Automaten

0:50:47 Moore-Automat: Beispiel aus tikz-Dokumentation

0:52:32 Verallgemeinerte Zustandsübergangsfunktionen

0:53:20 Verallgemeinerte Ausgabenfunktionen g* und g**

0:56:20 Endliche Akzeptoren - ein wichtiger Sonderfall von Moore-Automaten

0:58:29 Endlicher Akzeptor: Beispiel

0:59:41 Akzeptierte und abgelehnte Wörter

1:01:18 Erkannte formale Sprache

1:04:06 Beispiel 2 einer erkennbaren Sprache

1:11:14 Beispiel 3 einer erkennbaren Sprache

1:15:32 Beispiel 3 - Entwicklung einer Lösung

1:18:42 Beispiel einer nicht erkennbaren Sprache

21 |

0:00:00 Starten

0:00:05 Aufgabe 5.1

0:06:10 Aufgabe 5.2

0:10:56 Aufgabe 5.3

0:16:29 Aufgabe 5.5

0:21:42 Aufgabe 5.4

0:24:40 Aufgabe 5.6

0:31:26 Aufgabe 5.7

0:32:52 Catalan-Zahl

0:33:38 Eigenschaften

0:41:01 Aufgabe 5.8

0:49:49 Aufgabe 5.1

0:55:42 Aufgabe 5.7

15 |

0:00:00 Starten

0:01:12 Aufgabe 3.6

0:23:38 Aufgabe 3.5

0:45:35 Aufgabe 3.3

1:14:43 Aufgabe 3.2

- 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

- Syntax und Semantik für Aussagenlogik

Weiterführende Literatur

- Goos: Vorlesungen über Informatik, Band 1, Springer, 2005

- Abeck: Kursbuch Informatik I, Universitätsverlag Karlsruhe, 2005

Ziel:

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.

20 |

0:00:00 Starten

0:09:28 Warum keine exakten Angaben?

0:11:05 Wie ungenau wollen wir über Funktionen reden?

0:12:15 Zu Notation und Redeweise

0:15:53 Erläuterungen zur Definition von f=g

0:20:14 Beispiel

0:25:02 Nichtbeispiele

0:28:58 Äquivalenzrelation

0:29:18 Relation ist refleixiv und symmetrisch

0:30:57 Relation ist transitiv

0:32:42 Groß

0:33:41 einfache Rechenregel

0:34:39 Obere und untere Schranken

0:38:05 Beispiel

0:45:45 Einfache Beobachtungen

0:46:47 Für die Lektüre leider unverzichtbar

0:48:11 Eine nützliche Rechenregel

0:49:22 Komplexoperationen

0:50:56 Beweis

0:53:45 Weitere Regeln

0:54:39 Was ist wichtig

0:56:15 Multiplikation von Matrizen

1:05:09 Die Idee von Volker Strassen

1:08:26 Aufwandsabschätzung für den Algorithmus von Strassen

1:10:52 Matrizenmultiplikation - geht es noch schneller?

1:12:11 Teile und herrsche - engl. divide and conquer

1:15:48 Mastertheorem

1:23:52 Geschachtelte for-Schleifen

19 |

0:00:00 Starten

0:00:04 Überblick - Einheit 16

0:00:11 Adjazenzmatrix eines gerichteten Graphen

0:00:54 Wegematrix eines Graphen

0:02:44 Matrizenmultiplikation

0:02:56 Algorithmus für Matrizenmultiplikation

0:03:10 Quadrierte Adjazenzmatrix

0:03:33 Matrizenaddition

0:03:59 Berechnung von E* - die naheliegende Idee

0:06:13 Beseitigung der unendlichen Vereinigung

0:10:27 Potenzen der Adjazenzmatrix haben eine Bedeutung

0:11:27 Signum-Funktion

0:13:10 Matrizendarstellung für E^k - sgn(A^k) tut es

0:14:11 Erste Möglichkeit für die Berechnung der Wegematrix

0:15:32 Vereinigung von Relationen

0:17:13 Eine erste Formel für die Wegematrix - es gibt auch noch andere...

0:18:43 Beweis

0:19:33 Einfachster Algorithmus für die Wegematrix

0:22:37 Was ist der ""Aufwand"" eines Algorithmus?

0:26:52 Wieviele elementare Operationen für Matrizenaddition?

0:27:28 Wieviele elementare Operationen für Multiplikation?

0:29:10 Wieviele elementare Operationen für Wegematrix?

0:31:00 Wiederverwendung - auch bei Zwischenergebnissen eine gute Sache

0:34:17 Es geht noch besser - erst mehr denken und dann weniger rechnen

0:45:03 Was ist wichtig

0:47:02 Algorithmus von Warshall

0:59:37 Zum Aufwand des Algorithmus von Warshall

1:02:10 Einheit 17: Quantitative Aspekte von Algorithmen

1:02:53 Überblick - Einheit 17

1:07:18 Zählen arithmetischer Operationen - in Abhängigkeit von der Größe der Objekte

1:09:00 Ressourcen für Rechnungen

1:10:40 ΟΘΩ - zur Notation asymptotischen Wachstums

1:11:31 Insertionsort - Wieviele Vertauschungen sind nötig?

1:15:10 Insertionsort - Laufzeitabschätzung?

1:16:42 Ressourcenverbrauch - wie detailliert?

1:19:09 Was ist wichtig

1:20:50 Warum keine exakten Angaben?