Grundbegriffe der Informatik, Vorlesung, WS17/18 Karlsruher Institut für Technologie (KIT)

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