DiscoverGrundbegriffe der Informatik, Vorlesung, WS16/17
Claim Ownership
Grundbegriffe der Informatik, Vorlesung, WS16/17
Author: Karlsruher Institut für Technologie (KIT)
Subscribed: 46Played: 321Subscribe
Share
Description
Inhalt der Vorlesung:
- 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.
Dozent: Dr. Sebastian Stüker | Karlsruher Institut für Technologie (KIT), Institut für Anthropomatik und Robotik |
Vorlesungsaufzeichnung: http://webcast.kit.edu
- 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.
Dozent: Dr. Sebastian Stüker | Karlsruher Institut für Technologie (KIT), Institut für Anthropomatik und Robotik |
Vorlesungsaufzeichnung: http://webcast.kit.edu
27 Episodes
Reverse
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 <<alles Wesentliche>>
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 <<erster Art>> - die im Wörterbuch
0:46:07 Lexikographische Ordnung
0:48:12 Lexikographische Ordnung <<zweiter Art>>
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 <R>
0:30:55 Beispiele für <R>
0:32:44 Bestimmung von <R> 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 <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?
18 |
0:00:00 Starten
0:00:04 Aufgabe 4.1
0:13:31 Aufgabe 4.2
0:30:12 Aufgabe 4.3
17 |
0:00:00 Starten
0:00:04 Kapitel 15: Graphen
0:00:16 Wo sind wir? Ungerichtete Graphen
0:12:44 Ungerichtete Bäume
0:17:24 Knotengrad in ungerichteten Graphen
0:19:28 Symmetrische Relationen
0:21:14 Äquivalenzrelationen
0:23:40 Beschriftete Graphen
0:28:51 Färbungen von Graphen
0:30:54 Gewichtete Graphen
0:40:09 Erste Algorithmen in Graphen
0:42:24 Repräsentation von Graphen im Rechner
0:42:43 Objekte im Rechner
0:47:51 Adjazenzlisten
0:48:35 Inzidenzisten
0:49:12 Variante von Adjazenzlisten
0:51:34 Adjazenzmatrix
0:52:44 Repräsentation von Relationen durch Matrizen
0:54:00 Wegematrix eines Graphen
1:00:26 2-Erreichbarkeit
1:02:39 Systematische Suche nach Pfade
1:05:26 Zählen der Pfade
1:07:20 Matrizenmultiplikation
1:08:37 Algorithmus für Matrizenmultiplikation
1:14:43 Einheitsmatrizen
1:15:45 Quadrierte Adjazezmatrix
1:17:15 Matrizenaddition
16 |
0:00:00 Starten
0:00:52 Logisch äquivalente Formeln
0:07:01 Weitere allgemeingültige Formeln
0:10:02 Deduktionstheorem
0:13:22 Skizze eines Beispiels
0:24:55 Großzügige Benutzung von Prädikatenlogik
0:27:04 Zusammenfassung
0:27:58 Kapitel 14
0:29:57 Eine Zeitreise...wohin?...
0:30:29 ...da wären wir...
0:32:35 Zwei wichtige Schriften von al-Kharizmi
0:40:00 Algorithmusbegriff informell
0:48:49 Korrektheit eines Algorithmus
0:50:02 Beweis von al_Khwarizmi
0:53:51 Beweis durch Nachrechnen
0:55:31 Eine einfache ""Programmiersprache""
0:59:31 Hoare-Tripel
1:04:59 Hoare-Kalkül
14 |
0:00:00 Starten
0:04:48 Neutrale Elemente
0:14:29 Prädikatenlogische Formeln – Beispiele
0:17:15 Interpretationen
0:23:47 val (D,I,ß) - ein Wert für jeden Term und ein Wahrheitswert für jede Formel
0:40:58 Allgemeingültige Formeln
0:46:57 Modelle
0:52:34 Was ist wichtig
0:54:45 Vorkommen von Variablensymbolen in Formeln
1:02:17 Substitutionen
1:14:20 Weitere allgemeingültige Formeln
1:15:42 Kalküle
1:17:43 Axiome
1:21:12 Schlussregeln
1:22:30 Ableitungen – formal gefasst
1:24:49 Beweis – formal gefasst
13 |
0:00:00 Starten
0:00:05 Kapitel 12: kontextfreie Grammatiken
0:00:58 Kontextfreie Grammatik
0:01:41 Ableitungsbaum
0:02:24 Arithmetische Ausdrücke
0:08:35 Syntax aussagenlogischer Formeln
0:10:57 Was ist wichtig
0:11:30 Wo sind wir?: Relationen (Teil 2)
0:12:20 Produkt von Relationen
0:15:56 Reflexiv-transitive Hülle einer Relation - Vereinigung aller Potenzen
0:17:05 Reflexiv-transitive Hülle einer Relation - ein Beispiel
0:19:11 Eigenschaften der reflexiv-transitiven Hülle
0:19:57 Eigenschaften der reflexiv-transitiven Hülle - Erläuterungen
0:21:56 Was ist wichtig
0:23:33 Eine Grenze kontextfreier Grammatiken
0:25:34 Lvv - Beispielwörter
0:26:35 Lvv ist nicht kontextfrei
0:28:47 Lvv ist nicht kontextfrei (2)
0:31:58 Lvv ist nicht kontextfrei (2) - Beweisskizze des Lemmas
0:35:18 Lvv ist nicht kontextfrei (3)
0:37:32 Lvv ist nicht kontextfrei (4)
0:40:10 Lvv ist nicht kontextfrei (5)
0:42:22 Lvv ist nicht kontextfrei (6)
0:46:53 Zusammenfassung
0:47:54 Kapitel 13: Prädikatenlogik erster Stufe
0:58:44 Überblick
1:00:12 Prädikatenlogische Formeln
1:04:26 Prädikatenlogische Formeln - der Aufwand lohnt sich
1:06:38 Terme - benötigte Alphabete
1:10:49 Terme - Syntax
1:13:44 Terme - Beispiel
1:15:18 Atomare Formeln - Syntax
1:20:33 Atomare Formeln - Beispiele
1:24:08 Prädikatenlogische Formeln - Syntax
1:25:55 Prädikatenlogische Formeln - Beispiele
12 |
0:00:00 Starten
0:00:04 Wo sind wir?
0:01:15 Auszug aus der DTD für Tabellen in XHTML
0:03:04 Interpretation der DTD für Tabellen in XHTML
0:05:15 Beispiel für Tabelle in XHTML
0:06:56 Latex (1)
0:11:44 Latex (2)
0:13:30 Grobstruktur von Latex-Dokumenten
0:15:21 Listen mit Latex
0:16:56 Formale Sprachen kommen ins Spiel
0:20:29 Eine Grenze unserer bisherigen Vorgehensweise
0:23:59 Was ist wichtig (1)
0:25:07 Kapitel 12: kontextfreie Grammatiken
0:26:08 Spezifikation von formalen Sprachen
0:26:34 Abschnitt der Definition der Syntax von Java
0:30:35 Rekursion
0:32:01 Vereinfachung
0:35:07 Versuch einer formalen Sprache
0:39:19 Lösbarkeit von L
0:40:51 Beweis des Lemmas – Teil 1
0:43:36 Beweis des Lemmas – Teil 2
0:48:41 Was kann man an Li sehen?
0:52:02 Die Erklärung für L3 graphisch dargestellt
0:54:49 Vereinfachte Darstellung für L3
0:56:36 Was ist wichtig (2)
0:57:30 Kontextfreie Grammatik G
1:01:08 Ableitungsschritt mittels einer Produktion
1:03:24 Anmerkungen (1)
1:04:03 Anmerkungen (2)
1:05:54 Ableitungsfolgen
1:07:36 jede Grammatik erzeugt eine formale Sprache
1:08:39 Beispiel einer kontextfreien Grammatik/Sprache
1:11:01 Kompaktere Notation bei vielen Produktionen
1:11:50 Java-Syntax – Interpretation der Definition
1:13:20 kontextfreie Grammatiken versus Syntax von Programmiersprachen
1:15:29 Ableitungsbäume sind übersichtlicher als schrittweise Ableitung
1:17:26 Ableitungsbaum
1:19:12 Wohlgeformte/korrekte Klammerausdrücke
1:20:49 Arithmetische Ausdrücke
11 |
0:00:00 Starten
0:00:08 Aufgabe 2.1
0:06:26 Aufgabe 2.2
0:19:43 Aufgabe 2.3
0:21:33 Aufgabe 2.4
0:34:48 Aufgabe 2.5
0:47:37 Aufgabe 2.6
0:55:14 Aufgabe 2.7
10 |
0:00:00 Starten
0:00:06 Kapitel 10: Prozessor
0:00:47 MIMA – die Minimalmaschine ist ein idealisierter Prozessor
0:02:18 Überblick
0:02:55 Drähte verbinden »Erzeuger« und »Verbraucher«
0:06:46 »Erzeuger« für ein Bit
0:09:24 Drähte können mehrere Erzeugerausgänge mit Verbrauchern verbinden
0:11:29 Einfaches »Speicher-Element« für ein Bit
0:12:45 Arbeitsweise des Speicher-Elements
0:13:53 Wo sind wir? Grobstruktur der MIMA
0:14:48 Von-Neumann-Architektur vs. Harvard-Architektur
0:20:01 John von Neumann
0:21:27 Grobstruktur der MIMA
0:23:18 Hauptspeicher für die MIMA
0:27:22 Prozessor – Aufbau allgmein
0:31:05 die MIMA – ein idealisierter Prozessor
0:32:05 Maschinenbefehle werden aus dem Speicher geladen und ausgeführt
0:33:35 MIMA-Befehle (1a) – Datentransport Akku - Speicher
0:36:04 Laden und Speichern – Beispiel-»Programm«
0:39:16 MIMA-Befehle (1b) – Datentransport mit indirekter Adressierung
0:42:31 Laden mit indirekter Adressierung – Beispiel-»Programm«
0:43:59 MIMA-Befehle (2a) – für die ALU
0:45:29 Arithmetik – Beispiel-»Programm«
0:46:13 MIMA-Befehle (2b) – mehr für die ALU
0:48:34 Programmabarbeitung – normalerweise ganz einfach
0:50:07 Sprünge ändern die normale Reihenfolge der Programmabarbeitung
0:51:15 Rückwärtsgänge gehen natürlich auch ...
0:53:43 Bedingte Sprünge – Ausführung hängen vom Inhalt des Akku ab
0:54:52 Bedingter Sprung – Beispiel-»Programm«
0:55:59 Arbeitsweise der MIMA – für jeden Maschinenbefehl ein Mikroprogramm
0:57:19 MIMA – die Minimalmaschine ist ein idealisierter Prozessor
0:59:23 MIMA-Befehlsholphase
0:59:42 MIMA-Befehlsholphase (A1)
0:59:52 MIMA-Befehlsholphase (A2)
0:59:55 MIMA-Befehlsholphase (A3)
0:59:58 MIMA-Befehlsholphase (A4)
1:00:04 MIMA-Befehlsholphase (A5)
1:01:00 MIMA-Befehlsholphase (B1)
1:01:23 MIMA-Befehlsholphase (B2)
1:01:29 MIMA-Befehlsholphase (B3)
1:01:38 MIMA-Befehlsholphase (B4)
1:01:56 MIMA-Befehlsholphase (1)
1:02:01 MIMA-Befehlsholphase (2)
1:02:03 MIMA-Befehlsholphase (3)
1:02:07 MIMA-Befehlsholphase (4)
1:02:11 MIMA-Befehlsholphase (5)
1:02:13 Kapitel 48
1:02:23 MIMA-Befehlsdecodierungsphase
1:03:07 MIMA-Befehlsausführungsphase
1:03:22 MIMA-Befehlsausführungsphase für LDV adr (1)
1:03:29 MIMA-Befehlsausführungsphase für LDV adr (2)
1:03:32 MIMA-Befehlsausführungsphase für LDV adr (3)
1:03:33 MIMA-Befehlsausführungsphase für LDV adr (4)
1:03:34 MIMA-Befehlsausführungsphase für LDV adr (5)
1:03:36 MIMA-Befehlsausführungsphase für JMP adr
1:04:00 Wo sind wir? Ein Beispielprogramm
1:04:16 Aufsummieren einer Liste von Zahlen
1:06:24 Aufsummieren – Initialisierungen
1:08:27 Aufsummieren – Iteration über die Elemente
1:12:27 Wir halten fest
1:13:34 Dokumente haben Inhalt, Struktur und Form
1:14:46 Inhalt, Struktur und Form
1:15:50 Wozu Inhalt, Struktur und Form?
1:20:08 Struktur von Dokumenten
1:21:22 Wo sind wir? Dokumente XHTML
1:21:33 XHTML
1:23:12 Auszug aus der DTD für Tabellen in XHTML
09 |
0:00:00 Starten
0:00:05 Einheit 8: Codierungen
0:00:20 Übersetzungen – bedeutungserhaltende Abbildungen
0:00:30 Homomorphismen – mit Konkatenation verträgliche Abbildungen
0:01:15 Homomorphismen lassen das leere Wort unverändert
0:01:37 Homomorphismen – die Bilder einzelner Symbole legen alles fest
0:04:01 Homomorphismen – die Bilder einzelner Symbole legen alles fest (2)
0:07:17 Präfixfreie Codes
0:09:09 Präfixfreie Codes: Decodierung
0:14:23 Präfixfreie Codes: Decodierung (2)
0:15:35 Präfixfreie Codes: Decodierung (3)
0:16:23 Präfixfreie Codes: Decodierung (4)
0:17:51 Wo sind wir?
0:18:11 UTF-8 Coderung von Unicode – ein Homomorphismus
0:19:59 UTF-8 – Auszug aus RFC 3629
0:23:02 Beispiel: UTF-8 Codierung des Integralzeichens
0:24:49 Das ist wichtig
0:25:37 Huffmann-Codierung
0:26:43 Huffmann-Codierung – ein Überblick
0:28:03 Voraussetzungen
0:30:01 Algorithmus für Huffmann-Codes
0:32:22 Konstruktion des Huffmann-Baumes (1)
0:33:14 Konstruktion des Huffmann-Baumes (2)
0:34:00 Konstruktion des Huffmann-Baumes (3)
0:35:08 Konstruktion des Huffmann-Baumes (4)
0:37:44 Konstruktion des Huffmann-Baumes (5)
0:37:59 Konstruktion des Huffmann-Baumes (6)
0:38:12 Konstruktion des Huffmann-Baumes (8)
0:38:28 Beschriftung der Kanten
0:39:47 Eigenschaften von Huffmann-Codes
0:40:39 Block-Codierungen
0:41:52 Das ist wichtig
0:44:02 Einheit 9: Speicher
0:44:49 Überblick
0:47:20 Bit und Byte
0:47:39 Wo sind wir?
0:47:59 Kleiner und großer Speicher
0:49:49 Dezimale Größenpräfixe
0:52:41 Binäre Größenpräfixe
0:54:31 Wir halten fest
0:54:48 Formalisierungen sind Spezifikationen – auch im Zusammenhang mit Speicher...
0:57:08 Gesamtzustand eines Speichers
0:59:07 Formalisierung von Speicher
1:01:26 Lesen aus dem Speicher – Formalisierung als Abbildung
1:02:45 Bemerkunbg zu memread
1:04:09 Schreiben in den Speicher – ein wenig komplizierter
1:09:11 Eigenschaften von Speicher
1:09:45 Wozu diese Formalisierungen?
1:10:04 Was ist wichtig
07 |
0:00:00 Starten
0:00:05 Aufgabe 1.1
0:01:51 Aufgabe 1.2
0:04:44 Aufgabe 1.3
0:09:05 Aufgabe 1.4
0:16:40 Aufgabe 1.5
0:25:32 Aufgabe 1.6
0:58:29 Aufgabe 1.7