Grundbegriffe der Informatik, Vorlesung, WS17/18

26 | 0:00:00 Starten 0:00:10 Turingmaschinen 0:00:34 Platzkomplexität oder Raumkomplexität einer TM 0:01:32 Raumkomplexität der TM für Palindromerkennung 0:02:23 Zeitkomplexität versus Raumkomplexität 0:04:00 Eine Komplexitätsklasse ist eine Menge von Problemen 0:05:48 P und PSPACE - zwei wichtige Komplexitätsklassen 0:07:15 Beziehung zwischen P und PSPACE - unklar 0:09:49 Was ist wichtig 0:10:48 Achtung 0:11:09 Codierungen von Turingmaschinen 0:14:37 Beispielcodierung - Zustände 0:15:41 Beispielcodierung - Symbole 0:16:17 Beispielcodierung - Kopfbewegen 0:16:34 Beispielcodierung - Kopfbewegen 0:18:00 Beispielcodierung - eine ganze Turingmaschine 0:19:31 Eigenschaften dieser und ähnlicher Codierungen 0:21:30 Das Halteproblem 0:30:02 Gibt es Probleme die nicht algorithmisch gelöst werden können? 0:31:46 Diagonalisierung 0:37:27 Beweis der Unentscheidbarkeit des Halteproblems 0:41:35 Weitere unentscheidbare Probleme 0:42:40 Erinnerung: BB3 0:44:01 Bibermaschinen 0:44:50 Fleißige Biber und die Busy-Beaver-Funktion 0:50:26 Was ist wichtig? 0:51:39 Steam-Powered Turing Machine 0:53:04 Zusammenfassung 1 0:53:28 Video: Turing Machine in Microsoft Powerpoint 1:01:17 Zusammenfassung 2

25 | 0:00:00 Starten 0:00:37 Aufgabe 6.1 0:06:56 Aufgabe 6.2 0:17:33 Aufgabe 6.3 0:34:45 Aufgabe 6.4

24 | 0:00:00 Starten 0:01:39 Mealy-Automaten 0:05:23 Verallgemeinerte Zustandsübergangsfunktionen 0:20:24 Moore-Automat 0:25:59 Verallgemeinerte Ausgabefunktionen g* und g** 0:30:51 Endliche Akzeptoren 0:36:55 Erkannte formale Sprache 0:54:47 Beispiel einer nicht erkennbaren Sprache 1:07:39 Regulärer Ausdruck 1:18:21 Durch R beschriebene formale Sprache 1:23:28 Ãquivalenz regulärer Ausdrücke

23 | 0:00:00 Starten 0:00:10 Einheit 17: Quantitative Aspekte von Algorithmen 0:01:53 Einfache Beobachtungen 0:05:08 Für die Lektüre leider unverzichtbar 0:07:01 Eine nützliche Rechenregel 0:08:26 Komplexoperationen 0:15:51 Weitere Regeln 0:17:09 Was ist wichtig 0:18:23 Multiplikation von 2 X 2-Matrizen 0:20:25 Multiplikation von n X n Matrizen mit Blockaufteilung 0:27:44 Die Idee von Volker Strassen 0:31:00 Aufwandsabschätzung für den Algorithmus von Strassen 0:34:37 Matrizenmultiplikation - geht es noch schneller? 0:35:37 Teile und herrsche 0:37:43 Was ist wichtig 0:38:54 Laufzeit von Teile-und-Herrsche-Algorithmen 0:41:30 Mastertheorem 0:51:58 Hier ist das Mastertheorem nicht anwendbar 0:53:05 Einfache for-Schleifen 0:53:59 Geschachtelte for-Schleifen 0:56:06 Rechenzeiten 1:07:24 Ein primitiver Getränkeautomat

22 | 0:00:00 Starten 0:00:13 kapitel 16: Erste Algorithmen in Graphen 0:00:15 Wiederverwendung 0:11:20 Was ist wichtig 0:12:29 Algorithmus von Warshall 0:20:07 Zum Aufwand des Algorithmus von Warshall 0:21:01 Einheit 17: Quantitative Aspekte von Algorithmen 0:21:21 Überblick 0:23:25 Ressourcenverbrauch bei Berechnungen 0:23:26 Zählen arithmetischer Operationen 0:24:49 Ressourcen für Rechnungen 0:26:49 Insertionsort 0:32:46 Ressourcenverbrauch 0:35:05 Was ist wichtig 0:35:12 Wo sind wir ? 0:35:21 Warum keine exakten Angaben? 0:37:45 Wie ungenau wollen wir über Funktionen reden? 0:38:05 Zu Notation und Redeweise 0:43:36 Beispiel 0:55:44 Obere und untere Schranken

21 | 0:00:00 Starten 0:01:19 Aufgabe 5.1 0:11:02 Aufgabe 5.2 0:25:26 Aufgabe 5.3 0:35:19 Aufgabe 5.4 0:46:17 Aufgabe 5.5

20 | 0:00:00 Starten 0:00:18 ARMAR-6 0:06:11 Königsberg, 1652 0:06:28 Eine Anmerkung zu Relationen 0:08:14 Symmetrische Relationen 0:09:41 Äquivanelnzrelationen 0:13:08 Graphen mit knoten- oder Kantenmarkierungen 0:13:52 Graphen mit Beschriftungen 0:15:21 Beispiel 0:19:01 Färbungen von Graphen - formal 0:20:16 Gewichtete Graphen 0:21:40 Eine Grenze de üblichen Formalisierung von Graphen 0:28:00 Zusammenfassung 0:28:15 Kapitel 16 0:28:44 Überblick 0:32:04 Objekte im Rechner 0:34:02 Adjaztezlisten 0:35:06 Inzidenzlisten 0:36:02 Variante von Adjanzenlisten 0:37:59 Adjanzenmatrix 0:41:22 Repräsentation von Relationen durch Matrizen 0:41:57 Wegematrix eines Graph 0:45:08 Beispiel 0:45:37 2-Erreichbarkeit 0:47:34 Systematische Suche 0:49:59 Zählen der Pfade 0:51:15 Matrizenmultiplikation 0:52:53 Algorithmus für Matrizenmultiplikation 0:53:47 Einheitsmatrizen 0:54:44 Potenzen quadratischer Matrizen 0:55:24 Quadrierte Adjanzenmatrix 0:57:01 Matrizenaddition 0:58:05 Berechnung von E* 1:00:13 Beseitigung der unendlichen Vereinigung 1:03:55 Potenzen der Adjazenmatrix 1:04:24 Signum- Funktion 1:05:44 Matrizendarstellung für Ek 1:06:40 Vereinigung von Relationen 1:08:22 Eine erste Formel für die Wegematrix 1:09:09 Beweis 1:10:19 Einfacher Algorithmus 1:18:49 Wiederverwendung

19 | 0:00:00 Starten 0:00:28 Algorithmus zur Multiplikation nichtnegativer ganzer Zahlen 0:04:55 Schleifenvariante für Multiplikationsalgorithmus 0:10:53 Was ist wichtig 0:12:52 Kapitel 15: Graphen 0:14:05 Darstellung von Zusammenhängen 0:18:29 Überblick 0:20:45 Gerichteter Graph 0:24:04 Bäume kamen schon mehrfach vor 0:25:41 de Bruijn-Graphen 0:28:13 Teilgraph 0:29:54 Pfade können über mehrere Kanten führen 0:32:44 Zyklen führen zum Ausgangspunkt zurück 0:34:57 Beispiele für Pfade 0:37:04 Strenger Zusammenhang 0:39:43 Eindeutigkeit der Wurzel 0:41:54 Knotengrad bei gerichteten Graphen 0:43:06 Bäume: Blätter und innere Knoten 0:47:02 Welche Bedeutung hat das Relationsprodukt 0:48:33 Erreichbarkeit 0:54:27 Ungerichtete Graphen - Formal definiert 0:56:32 Teilgraph eines ungerichteten Graphen 0:59:13 Ungerichtete Kanten und Relationen 1:01:24 Zusammenhang in ungerichteten Graphen 1:04:09 Knotengrad in ungerichteten Graphen - ein heikles Thema

18 | 0:00:00 Starten 0:00:10 Aufgabe 4.1 0:12:08 Aufgabe 4.2 0:26:13 Aufgabe 4.3 0:35:11 Aufgabe 4.4 0:45:22 Aufgabe 4.5

17 | 0:00:00 Starten 0:14:00 Wo sind wir? 0:18:18 Zwei wichtige Schriften von al-Kharizmi 0:21:43 Lösen einer Sorte quadratischer Gleichung nach al-Kharazmi 0:24:11 Algorithmusbegriff informal 0:26:20 Diskussion des informellen Algorithmusbegriffs 0:35:21 Korrektheit eines Algorithmus 0:35:50 Beweis von al-Khwaraizmi 0:40:51 Beweis durch Nachrechnen 0:43:36 Eine einfache ,,Programmiersprache'' 0:46:12 Hoare-Tripel 0:47:47 mZusicherungen in Hoare-Tripeln 0:50:50 Bedeutung von Programmen 0:51:59 Gültigkeit von Hoare-Tripeln 0:56:20 Axiome für Hoare-Kalkül 0:59:59 Ableitungsregeln 1:03:35 Beispiel 1:15:27 Regel H T-I 1:17:17 Beispiel für H T-I 1:23:46 Erinnerung 1:25:06 Algorithmus für die Multiplikation

16 | 0:00:00 Starten 0:00:10 Kap13: Prädikatenlogik erster Stufe 0:11:37 Vorkommen von Variablensymbolen in Formeln 0:13:24 freie und gebundene Vorkommen von Variablensymbolen 0:21:02 Substitutionen 0:36:51 Kollisionsfreie Substitutionen für Formeln 0:39:06 Logisch äquivalente Formeln 0:49:36 Weitere allgemeingültige Formeln 0:53:25 Kapitel 14: Der Begriff des Algorithmus (einige grundlegende Aspekte) 0:53:34 Kalkül 0:55:53 Aussagenkalkül 0:56:42 Hilbert-Kalkül 0:59:54 Axiome für Hilbert-Kalkül 1:03:12 Schlussregeln für den Hilbert-Kalkül 1:05:06 Ableitungen - formal gefasst 1:09:30 Beweis - formal gefasst 1:09:55 Hilbert-Kalkül - korrekt und vollständig 1:12:39 Deduktionstheorem - aber nur mit Einschränkungen 1:14:47 Skizze eines Beispiels 1:28:22 Großzügige Benutzung von Prädikatenlogik 1:29:26 Zusammenfassung

15 | 0:00:00 Starten 0:01:46 Aufgabe 3.1 0:26:54 Aufgabe 3.2 0:43:54 Aufgabe 3.3

14 | 0:00:00 Starten 0:03:00 Prädikatenlogische Formeln 0:09:54 Terme 0:22:17 Atomare Formeln 0:33:04 Prädikatenlogische Formeln 0:39:37 Was ist wichtig 0:40:40 Interpretationen 0:45:55 Val 1:03:16 Allgemeingültige Formeln 1:13:29 Modelle 1:19:09 Was ist wichtig 1:19:53 Vorkommen 1:21:45 freie und gebundene Vorkommen

13 | 0:00:00 Starten 0:00:24 Was ist wichtig? 0:04:26 Wo sind wir? 0:04:59 Kontextfreie Grammatik 0:07:50 Ableitungsschritt 0:10:14 Anmerkungen 0:13:16 Ableitungsfolgen 0:16:01 Jede Grammatik erzeugt eine formale Sprache 0:16:57 Beispiel einer kontextfreien Grammatik/Sprache 0:19:20 Kompaktere Notation bei vielen Produktionen 0:20:14 Java-Syntax 0:22:22 Kontextfreie Grammatiken versus Syntax von Programmiersprachen 0:23:49 Ableitungsbäume 0:28:19 Wohlgeformte/korrekte Klammerausdrücke 0:29:48 Arithmetische Ausdrücke 0:34:29 Syntax aussagenlogischer Formeln 0:39:09 Produkt von Relationen 0:42:29 Reflexiv-transitive Hülle 0:45:43 Eigenschaften der reflexiv-transitiven Hülle 0:50:17 Eine Grenze kontextfreier Grammatiken 0:52:01 L-Beispielwörter 0:54:15 L ist nicht kontextfrei 1:16:53 Zusammenfassung

12 | 0:00:00 Starten 0:00:10 Laden mit indirekter Adressierung - Beispiel. Programm 0:00:59 MIMA-Befehle(1a) - Datentransport akku 0:02:17 MIMA-Befehle (1b) - Datentransport mit indirekter Adressierung 0:03:19 MiMa- Befehle (2a) - für die ALU 0:05:06 Arithmetik - Beispiel- Programm 0:05:48 MIMA-Befehle (2b) - mehr für die ALU 0:08:47 Programmabarbeitung - normalerweise ganz einfach 0:09:46 Sprünge ändern die normale Reihenfolge der Programmabarbeitung 0:10:44 Rückwertssprünge gehen natürlich auch... 0:12:20 Bedingte Sprünge 0:15:20 Arbeitsweise der MIMA 0:16:39 MIMA - die Minimalmaschine ist ein idealisierter Prozessor 0:18:15 MIMA- Befehlsholphase 0:18:40 MIMA Befehlsholphase (A1) 0:18:58 MIMA Befehlsholphase (A2) 0:19:21 MIMA Befehlsholphase (A3) 0:19:23 MIMA Befehlsholphase (A4) 0:20:42 MIMA Befehlsholphase (A5) 0:20:54 MIMA Befehlsholphase (B1) 0:21:20 MIMA Befehlsholphase (B2) 0:21:48 MIMA Befehlsholphase (B3) 0:21:53 MIMA Befehlsholphase (B4) 0:22:04 MIMA Befehlsholphase (1) 0:22:25 MIMA Befehlsholphase (2) 0:22:38 MIMA Befehlsholphase (3) 0:22:51 MIMA- Befehlsdecodierungsphase 0:23:39 MIMA Befehlsausführungsphase für LDV adr (1) 0:24:34 Aufsummieren einer Liste von Zahlen 0:26:24 Aufsummieren - Initialisierungen 0:27:49 Aufsummieren - Iteration über die Elemente 0:30:46 Wir halten fest 0:31:52 Kapitel 11 0:33:03 Dokumente 0:35:52 Inhalt, Struktur, Form 0:39:46 Struktur von Dokumenten 0:41:28 XHTML 0:45:58 Auszug aus der DTD für Tabellen in XHTML 0:46:56 Interpretation der DTD für Tabellen in XHTML 0:50:50 Beispiele für Tabelle in XHTML 0:51:16 LATEX 0:55:32 Grobstruktur 0:56:36 Listen mit LATEX 0:57:47 Formale Sprache kommen ins Spiel 0:59:57 Eine Grenze unserer bisherigen Vorgehensweise 1:03:03 Kapitel 12 1:03:07 Spezifikation formaler Sprache 1:03:27 Ausschnitt der Definition der Syntax von Java 1:05:16 Vereinfachung 1:07:35 Versuch einer formalen Sprache 1:11:34 Beweis des Lemmas 1:18:01 Was kann man sehen? 1:24:40 Kontextfreie Grammatik

0:00:00 Starten 0:00:53 Aufgabe 2.1: Aussagenlogische Formeln 0:07:42 Aufgabe 2.2 0:19:17 Aufgabe 2.3 0:41:12 Aufgabe 2.4 0:51:28 Aufgabe 2.5 0:54:47 Aufgabe 2.6 1:09:13 Aufgabe 2.7 1:15:55 Aufgabe 2.8

10 | 0:00:00 Starten 0:03:36 Überblick 0:04:31 Wo sind wir? 0:04:39 Bit und Byte 0:09:16 Kleiner ung großer Speicher 0:15:30 Dezimale Größenpräfixe 0:18:43 Binäre Größenpräfixe 0:22:58 Wir halten fest 0:23:35 Formalisierungen sind Spezifikationen - auch im Zusammenfassung mit Speicher 0:25:46 Gesamtzustand eines Speichers 0:28:13 Formalisierung von Speicher 0:30:58 Lesen aus dem Speicher - Formalisierung als Abbildung 0:33:10 Bemerkungen zu memread 0:35:12 Schreiben in den Speicher - ein weing komplizierter 0:42:19 Eigenschaften von Speicher 0:43:59 Wozu diese Formalisierungen? 0:44:48 Was ist wichtig 0:45:57 Kapitel 10: Prozessor 0:46:12 MIMA - die Minimalmaschine ist ein idealisierter Prozessor 0:47:27 Überblick 0:47:36 Drahte verbinden ,,Erzeuger'' und ,,Verbracher'' 0:50:00 ,,Erzeuger'' für ein Bit 0:52:18 Drähte können mehrere Erzeugerausgänge mit Verbrauchern verbinden 0:55:18 Einfaches ,,Speicher-Elemn'' für ein Bit 0:57:26 Arbeitsweise des Speicher-Elements 0:57:43 Von-Neumann-Architektur vs. Harvard-Architektur 1:01:37 John von Neumann 1:02:23 Grobstruktur der MIMA 1:06:09 Hauptspeicher für die MAMA 1:10:31 Prozessor - Aufbau allgemein 1:11:00 die MAMA - ein idealisierter Prozessor 1:12:39 Maschinenbefehle werden 1:15:45 MIMa- Befehle (1a) - Datentransport Akku - Speicher 1:18:55 Laden und Speichern - Beispiel - <<Program>> 1:21:01 MIMA- Befehle (1b)- Datentransport mit indirekter Adressierung

09 | 0:00:00 Starten 0:00:10 Darstellung auch negativer Zahlen 0:02:24 Zweierkomplement-Darstellung - für negative und nichtnegative Zahlen 0:05:10 Das ist wichtig 0:07:43 Von Hexadezimal- zu Binärdarstellung 0:09:49 Übersetzungen - bedeutungserhaltende Abbildungen von Wörtern auf Wörter 0:13:49 Trans2,16 - eine Übersetzung 0:15:28 Wozu Übersetzungen 0:21:08 Codierungen - injektive Übersetzungen 0:23:52 Wie spezifiziert man eine Übersetzung? 0:24:40 Homomorphismen - mit Konkatenation verträgliche Abbildungen 0:26:37 Homomorphismen lassen das leere Wort unverändert 0:27:57 Homomorphismen - die Bilder einelner Symbole legen alles fest 0:30:35 Homomorphismen - die Bilder einzelner Symbole legen alles fest (2) 0:32:02 Homomorphismen - so legen die Bilder einzelner Symbole alles fest 0:34:08 Präfixfreie Codes 0:36:05 Präfixfreie Codes: Decodierung 0:40:02 Präfixfreie Codes: Decodierung (2) 0:41:51 Präfixfreie Codes: Decodierung (3) 0:42:03 Präfixfreie Codes: Decodierung (4) 0:44:58 UTF-8 Codierung von Unicode - ein Homomorphismus 0:46:42 UTF-8 - Auszug aus RFC 3629 0:49:52 Beispiel: UTF-8 Codierung des Integralzeichens 0:53:11 Huffman-Codierung - ein Überblick 0:55:07 Voraussetzungen 0:57:08 Algorithmus für Huffman-Codes 0:59:07 Konstruktion des Huffman-Baumes (1) 1:00:53 Konstruktion des Huffman-Baumes (2) 1:00:59 Konstruktion des Huffman-Baumes (3) 1:02:29 Konstruktion des Huffman-Baumes (4) 1:03:35 Konstruktion des Huffman-Baumes (5) 1:03:49 Konstruktion des Huffman-Baumes (6) 1:03:57 Konstruktion des Huffman-Baumes (7) 1:04:05 Konstruktion des Huffman-Baumes (8) 1:04:18 Beschriftung der Kanten 1:05:57 Eigenschaften von Huffman-Codes 1:07:15 Block-Codierungen

08 | 0:00:00 Starten 0:04:25 Von Wörten zu zahlen und zurück 0:05:49 Wo sind wir? 0:06:53 Dezimaldarstellung von Zahlen 0:24:13 Induktive Definitionen - ,,über die Wortlänge'' 0:26:24 Gottfried Wilhelm Leibniz: zwei Ziffern reichen aus! 0:33:21 Binäardarstellung von Zahlen 0:35:59 Hexadezimaldarstellung oder Sedezimaldarstellung 0:37:59 Ein kleines Problem 0:40:36 Ist jede Zahl darstellbar? 0:41:50 k-äre Darstellung von Zahlen 0:48:16 Operation div und mod 0:52:48 Die Definition von Reprk ist sinnvoll 0:57:44 Numk ist linksinvers zu Reprk 1:05:11 Unübliche Methode für negative Zahlen 1:09:55 Rechnen in Zk 1:18:41 Zahldarstellungen mit beschränkter fester Länge 1:21:11 Negative Zahlen - Pfeile in die entgegengesetzte Richtung 1:23:20 Darstellung auch negativer Zahlen

07 | 0:00:00 Starten 0:00:45 Aufgabe 1.1 0:12:53 Aufgabe 1.2 0:19:24 Aufgabe 1.3 0:28:12 Aufgabe 1.5 0:41:30 Aufgabe 1.6 0:55:47 Aufgabe 1.4