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

Grundbegriffe der Informatik, Vorlesung, WS17/18

26: Grundbegriffe der Informatik, Vorlesung, WS 2017/18, 09.02.2018

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

25: Grundbegriffe der Informatik, Übung, WS 2017/18, 02.02.2018

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

24: Grundbegriffe der Informatik, Vorlesung, WS 2017/18, 31.01.2018

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

23: Grundbegriffe der Informatik, Vorlesung, WS 2017/18, 26.01.2018

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

22: Grundbegriffe der Informatik, Vorlesung, WS 2017/18, 24.01.2018

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

21: Grundbegriffe der Informatik, Übung, WS 2017/18, 19.01.2018

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

20: Grundbegriffe der Informatik, Vorlesung, WS 2017/18, 17.01.2018

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

19: Grundbegriffe der Informatik, Vorlesung, WS 2017/18, 12.01.2018

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

18: Grundbegriffe der Informatik, Übung, WS 2017/18, 22.12.2017

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

17: Grundbegriffe der Informatik, Vorlesung, WS 2017/18, 20.12.2017

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

16: Grundbegriffe der Informatik, Vorlesung, WS 2017/18, 13.12.2017

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

15: Grundbegriffe der Informatik, Übung, WS 2017/18, 08.12.2017

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

14: Grundbegriffe der Informatik, Vorlesung, WS 2017/18, 06.12.2017

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

13: Grundbegriffe der Informatik, Vorlesung, WS 2017/18, 01.12.2017

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

hubhopper

Grundbegriffe der Informatik, Vorlesung, WS17/18

hubhopper