Grundbegriffe der Informatik, Vorlesung, WS17/18

Grundbegriffe der Informatik, Vorlesung, WS17/18 episodes:

• February 13, 201826: 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

  ...more

  ---

• February 05, 201825: 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

  ...more

  ---

• February 05, 201824: 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

  ...more

  ---

• January 26, 201823: 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

  ...more

  ---

• January 25, 201822: 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

  ...more

  ---

• January 23, 201821: 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

  ...more

  ---

• January 18, 201820: 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

  ...more

  ---

• January 15, 201819: 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

  ...more

  ---

• December 22, 201718: 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

  ...more

  ---

• December 22, 201717: 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

  ...more

  ---