Grundbegriffe der Informatik, Vorlesung, WS17/18

By Karlsruher Institut für Technologie (KIT)Education

Grundbegriffe der Informatik, Vorlesung, WS17/18 episodes

February 13, 2018 26: Grundbegriffe der Informatik, Vorlesung, WS 2017/18, 09.02.2018
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
1 hr 5 min
February 05, 2018 25: Grundbegriffe der Informatik, Übung, WS 2017/18, 02.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
1 hr 7 min
February 05, 2018 24: Grundbegriffe der Informatik, Vorlesung, WS 2017/18, 31.01.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
1 hr 27 min
January 26, 2018 23: Grundbegriffe der Informatik, Vorlesung, WS 2017/18, 26.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
1 hr 24 min
January 25, 2018 22: Grundbegriffe der Informatik, Vorlesung, WS 2017/18, 24.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
1 hr 8 min
January 23, 2018 21: Grundbegriffe der Informatik, Übung, WS 2017/18, 19.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
52 min
January 18, 2018 20: Grundbegriffe der Informatik, Vorlesung, WS 2017/18, 17.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
1 hr 22 min
January 15, 2018 19: Grundbegriffe der Informatik, Vorlesung, WS 2017/18, 12.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
1 hr 6 min
December 22, 2017 18: Grundbegriffe der Informatik, Übung, WS 2017/18, 22.12.2017
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
1 hr 32 min
December 22, 2017 17: Grundbegriffe der Informatik, Vorlesung, WS 2017/18, 20.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
1 hr 27 min