26 Folgen

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

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

    • Kurse

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: 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 Std. 4 Min.
    • video
    25: Grundbegriffe der Informatik, Übung, WS 2017/18, 02.02.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 Std. 6 Min.
    • video
    24: Grundbegriffe der Informatik, Vorlesung, WS 2017/18, 31.01.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 Std. 26 Min.
    • video
    23: Grundbegriffe der Informatik, Vorlesung, WS 2017/18, 26.01.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 Std. 23 Min.
    • video
    22: Grundbegriffe der Informatik, Vorlesung, WS 2017/18, 24.01.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 Std. 7 Min.
    • video
    21: Grundbegriffe der Informatik, Übung, WS 2017/18, 19.01.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

    • 51 Min.

Top‑Podcasts in Kurse

Zuhörer haben auch Folgendes abonniert:

Mehr von Karlsruher Institut für Technologie