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