
26 Folgen

Grundbegriffe der Informatik, Vorlesung, WS17/18 Karlsruher Institut für Technologie (KIT)
-
- Bildung
Inhalt der Vorlesung:
- Algorithmen informell, Grundlagen des Nachweises ihrer Korrektheit, Berechnungskomplexität, 'schwere' Probleme, O-Notation, Mastertheorem
- Alphabete, Wörter, formale Sprachen, endliche Akzeptoren, kontextfreie Grammatiken
- induktive/rekursive Definitionen, vollständige und strukturelle Induktion, Hüllenbildung
- Relationen und Funktionen
- Graphen
- Syntax und Semantik für Aussagenlogik
Weiterführende Literatur
- Goos: Vorlesungen über Informatik, Band 1, Springer, 2005
- Abeck: Kursbuch Informatik I, Universitätsverlag Karlsruhe, 2005
Ziel:
Der/die Studierende soll
- grundlegende Definitionsmethoden erlernen und in die Lage versetzt werden, entsprechende Definitionen zu lesen und zu verstehen.
- den Unterschied zwischen Syntax und Semantik kennen.
- die grundlegenden Begriffe aus diskreter Mathematik und Informatik kennen und die Fähigkeit haben, sie im Zusammenhang mit der Beschreibung von Problemen und Beweisen anzuwenden.
Dozent: Dr. Sebastian Stüker | Karlsruher Institut für Technologie (KIT), Institut für Anthropomatik und Robotik |
Vorlesungsaufzeichnung: http://webcast.kit.edu
-
- video
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 -
- video
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 -
- video
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 -
- video
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 -
- video
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 -
- video
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