KIT | KIT-Bibliothek | Impressum | Datenschutz

Grundbegriffe der Informatik, Vorlesung, WS 2016/17, 11.01.2017, 19

Stüker, Sebastian; KIT | Webcast [Hrsg.]

  • 0:00:00 Starten
  • 0:00:04 Überblick - Einheit 16
  • 0:00:11 Adjazenzmatrix eines gerichteten Graphen
  • 0:00:54 Wegematrix eines Graphen
  • 0:02:44 Matrizenmultiplikation
  • 0:02:56 Algorithmus für Matrizenmultiplikation
  • 0:03:10 Quadrierte Adjazenzmatrix
  • 0:03:33 Matrizenaddition
  • 0:03:59 Berechnung von E* - die naheliegende Idee
  • 0:06:13 Beseitigung der unendlichen Vereinigung
  • 0:10:27 Potenzen der Adjazenzmatrix haben eine Bedeutung
  • 0:11:27 Signum-Funktion
  • 0:13:10 Matrizendarstellung für E^k - sgn(A^k) tut es
  • 0:14:11 Erste Möglichkeit für die Berechnung der Wegematrix
  • 0:15:32 Vereinigung von Relationen
  • 0:17:13 Eine erste Formel für die Wegematrix - es gibt auch noch andere...
  • 0:18:43 Beweis
  • 0:19:33 Einfachster Algorithmus für die Wegematrix
  • 0:22:37 Was ist der ""Aufwand"" eines Algorithmus?
  • 0:26:52 Wieviele elementare Operationen für Matrizenaddition?
  • 0:27:28 Wieviele elementare Operationen für Multiplikation?
  • 0:29:10 Wieviele elementare Operationen für Wegematrix?
  • 0:31:00 Wiederverwendung - auch bei Zwischenergebnissen eine gute Sache
  • 0:34:17 Es geht noch besser - erst mehr denken und dann weniger rechnen
  • 0:45:03 Was ist wichtig
  • 0:47:02 Algorithmus von Warshall
  • 0:59:37 Zum Aufwand des Algorithmus von Warshall
  • 1:02:10 Einheit 17: Quantitative Aspekte von Algorithmen
  • 1:02:53 Überblick - Einheit 17
  • 1:07:18 Zählen arithmetischer Operationen - in Abhängigkeit von der Größe der Objekte
  • 1:09:00 Ressourcen für Rechnungen
  • 1:10:40 ΟΘΩ - zur Notation asymptotischen Wachstums
  • 1:11:31 Insertionsort - Wieviele Vertauschungen sind nötig?
  • 1:15:10 Insertionsort - Laufzeitabschätzung?
  • 1:16:42 Ressourcenverbrauch - wie detailliert?
  • 1:19:09 Was ist wichtig
  • 1:20:50 Warum keine exakten Angaben?
Open Access Logo


Zugehörige Institution(en) am KIT Institut für Anthropomatik und Robotik (IAR)
Publikationstyp Audio & Video
Publikationsdatum 19.01.2017
Erstellungsdatum 11.01.2017
DOI 10.5445/DIVA/2017-43
Identifikator KITopen-ID: 1000114457
Lizenz KITopen-Lizenz
Serie Grundbegriffe der Informatik, Vorlesung, WS 2016/17
Folge 19
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page