27 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, WS16/1‪7‬ Karlsruher Institut für Technologie

    • Kurse
    • 3.3 • 4 Bewertungen

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
    Grundbegriffe der Informatik, Vorlesung, WS 2016/17, 08.02.2017, 26

    Grundbegriffe der Informatik, Vorlesung, WS 2016/17, 08.02.2017, 26

    26 |
    0:00:00 Starten
    0:00:04 Kapitel 21: Relationen
    0:00:59 Antisymmetrische Relationen
    0:03:57 Halbordnungen
    0:05:52 eine Halbordnung auf Wörtern - darauf bauen wir später noch auf
    0:07:28 Wenn man weiß, dass es eine Halbordnung ist, enthält der gesamte Graph Redundantes
    0:08:51 Wenn man weiß, dass es eine Halbordnung ist, genügt das Hassediagramm
    0:10:31 Das Hassediagramm enthält >
    0:11:32 Minimale und maximale Elemente
    0:12:56 Beispiele minimaler und maximaler Elemente
    0:13:22 Kleinste und größte Elemente
    0:14:14 Beispiele kleinster und größter Elemente
    0:15:22 Das kleinste und das größte Element sind eindeutig
    0:16:02 Untere und obere Schranken von T - unter Umständen auch außerhalb von T
    0:16:52 Untere und obere Schranken: Beispiele
    0:17:27 Untere und obere Schranken müssen nicht existieren
    0:18:43 Supremum und Infimum
    0:19:45 Supremum und Infimum: Beispiele
    0:21:47 Aufsteigende Ketten
    0:23:08 Vollständige Halbordnungen
    0:24:34 Vollständige Halbordnungen: weitere (Nicht-)Beispiele
    0:27:09 Monotone Abbildungen
    0:28:20 Stetige Abbildungen
    0:29:14 Stetige Abbildungen: Beispiel 1
    0:31:15 Stetige Abbildungen: Beispiel 2
    0:32:10 Fixpunktsatz
    0:33:58 Fixpunktsatz: Beweis
    0:37:13 Was ist wichtig
    0:38:25 Totale Ordnung - keine unvergleichbaren Elemente
    0:40:27 Totale Ordnungen auf A*
    0:42:16 Lexikographische Ordnung (Wörterbuch)
    0:45:37 Lexikographische Ordnung > - die im Wörterbuch
    0:46:07 Lexikographische Ordnung
    0:48:12 Lexikographische Ordnung >
    0:49:31 Die lexikographischen Ordnungen sind total
    0:51:00 Was ist wichtig (2)
    0:51:42 Kapital 22: MIMA-X
    0:51:55 MIMA-X - eine Erweiterung der MIMA
    0:53:20 Erinnerung: die Ackermann-Funktion A
    0:54:00 Ackermann-Funktion Beispielberechnung für A(2,2)
    0:54:18 Ackermann-Funktion A(2,2) kompakt notiert
    0:56:27 Stapel oder Keller - Zugriff nur auf das oberste Element
    0:58:04 Stapel - eine mögliche ""Implementierung""
    0:58:27 Stapel - bequeme Verallgemeinerung
    0:58:54 Berechnung der Ackermann-Funktion mit einem Stapel
    1:00:25 Jede k-stellige Operation auf V ist auf Stapel mit mindestens k Einträgen übertragbar
    1:02:01 Stapel - Implementierung in einem Rechner
    1:03:36 Mimax- drei zusätzliche Register für Adressen
    1:05:53 Register RA speichert eine Rückkehradresse
    1:06:42 CALL und RET - Wiederverwendung von Codestücken durch primitiven Unterprogrammaufruf
    1:08:12 SP und FP
    1:08:59 Speicherzugriffe mittels SP
    1:09:49 Veränderungen des SP-Registers
    1:10:34 Realisierung von push, top und pop
    1:11:30 push und pop von RA - für ineinander geschachtelte CALL
    1:13:09 Wir halten fest

    • 1 Std. 15 Min.
    • video
    Grundbegriffe der Informatik, Übung, WS 2016/17, 10.02.2017, 27

    Grundbegriffe der Informatik, Übung, WS 2016/17, 10.02.2017, 27

    27 |
    0:00:00 Starten
    0:00:04 Aufgabe 6.1
    0:04:44 Aufgabe 6.2
    0:11:12 Aufgabe 6.3
    0:16:19 Aufgabe 6.4
    0:22:26 Aufgabe 7.1
    0:28:13 Aufgabe 7.2
    0:36:24 Aufgabe 7.3
    0:39:42 Aufgabe 7.4

    • 44 Min.
    • video
    Grundbegriffe der Informatik, Vorlesung, WS 2016/17, 03.02.2017, 25

    Grundbegriffe der Informatik, Vorlesung, WS 2016/17, 03.02.2017, 25

    25 |
    0:00:00 Starten
    0:00:04 Kapitel 20: Turingmaschinen
    0:00:25 Wo sind wir?
    0:01:45 Codierungen von Turingmaschinen
    0:04:54 Beispielcodierung
    0:09:44 Eigenschaften dieser und ähnlicher Codierungen
    0:11:50 Das Halteproblem ist unentscheidbar
    0:18:37 Diagonalisierung
    0:24:07 Das Halteproblem
    0:24:22 Beweis der Unentscheidbarkeit des Halteproblems
    0:28:37 Weitere unentscheidbare Probleme
    0:36:10 Erinnerung: BB3
    0:37:03 Bibermaschinen
    0:38:26 Busy-Beaver-Funktion
    0:42:51 Was ist wichtig
    0:43:53 Steam-Powered Turing Machine
    0:47:48 Zusammenfassung
    0:51:51 Kapitel 21: Relationen
    0:52:28 Überblick
    0:52:51 Äquivalenzrelationen
    0:53:41 Identität
    0:54:18 Kongruenz ganzer Zahlen modulo n
    0:55:12 Beispiel: asymptotisch gleiches Wachstum
    0:55:24 Urbilder von Funktionswerten
    0:57:50 Bild einer Äquivalenzrelation
    0:59:27 Äquivalenzklassen und Faktormengen
    1:00:40 Beispiel: Äquivalenzklassen und Kogruenz modulo 2
    1:02:21 Was ist wichtig
    1:02:49 Äquivalenzrelationen auf Mengen mit ""Struktur""
    1:03:27 Verträglichkeit von Äquivalenzrelationen mit Abbildungen
    1:05:49 Kongruenzrelation
    1:06:28 Eine Operation für Äquivalenzklassen modulo n?
    1:08:20 Verträglichkeit erlaubt die Übertragung einer Abbildung auf der Faktormenge
    1:09:14 eine Operation für Äquivalenzklassen modulo n?
    1:10:10 Was ist wichtig
    1:10:54 Wo sind wir?
    1:11:02 Motivation
    1:13:02 Äquivalenzrelationen von Nerode einer Sprache
    1:14:30 Beispiel
    1:18:35 Die Nerode-Relation is immer eine Äquivalenzrelationen
    1:19:09 Verträglichkeit: Beisoiel Nerode-Äquivalenzen
    1:20:44 Eine Abbildung für Nerode-Äquivalenzklassen
    1:21:22 Nerode-Äquivalenzen: Ausblick

    • 1 Std. 24 Min.
    • video
    Grundbegriffe der Informatik, Vorlesung, WS 2016/17, 01.02.2017, 24

    Grundbegriffe der Informatik, Vorlesung, WS 2016/17, 01.02.2017, 24

    24 |
    0:00:00 Starten
    0:00:59 Algorithmusbegriss informell
    0:03:47 Erinnerung: partielle Funktion von A nach B
    0:05:39 Turingmaschinen: Ursprung
    0:08:33 Eine Turingmaschine im Bild
    0:13:48 Turingmaschine formalisiert
    0:15:28 Turingmaschine: graphische Darstellung
    0:19:23 Turingmaschine: tabellarische Darstellung
    0:20:26 Beispielberechnung
    0:23:01 Turingmaschine: Konfigurationen
    0:25:48 Turingmaschine: "" überschaubare"" Bandbeschriftungen
    0:27:48 Ein Schritt einer Turingmaschine
    0:30:31 Längere Beispielberechnung von BB3
    0:33:13 Berechnungen und Endkonfigurationen
    0:36:18 Rechnen bir zur Endkonfiguration
    0:37:14 zwei Arten von Turingmaschinen
    0:38:15 Eingaben und Anfangskonfigurationen
    0:40:53 Ergebnisse von Turingmaschinenberechnungen
    0:44:19 Beispiel: Palindromerkennung
    0:58:27 Entscheidbare und aufzählbare Sprachen
    1:01:36 Was ist wichtig
    1:06:22 Berechungskomplexität
    1:07:59 Zeitkomplexität - der Rechenzeitbedarf einer TM
    1:12:43 Zeitkomplexität der TM für Palindromerkennung
    1:14:39 Platzkomplexität oder Raumkomplexität einer TM
    1:15:54 Raumkomplexität der TM für Palindromerkennung
    1:17:18 Zeitkomplexität versus Raumkomplexität
    1:20:03 Eine Komplexitätsklasse ist eine Menge von Problemen
    1:22:29 P und PSPACE - zwei wichtige Komplexitätsklassen
    1:25:02 Beziehung zwischen P und PSPACE - unklar
    1:27:55 Was ist wichtig

    • 1 Std. 29 Min.
    • video
    Grundbegriffe der Informatik, Vorlesung, WS 2016/17, 27.01.2017, 23

    Grundbegriffe der Informatik, Vorlesung, WS 2016/17, 27.01.2017, 23

    23 |
    0:00:00 Starten
    0:00:05 Beispiel einer nicht erkennbaren Sprache
    0:03:01 Beispiel einer nicht erkennbaren Sprache (2)
    0:06:44 Beispiel einer nicht erkennbaren Sprache (3)
    0:12:49 Was ist wichtig
    0:14:26 Zusammenfassung
    0:15:48 Was können endliche Akzeptoren
    0:16:20 Überblick
    0:18:46 Der Begriff regulärer Ausdruck hat heute verschiedene Bedeutungen
    0:19:49 Definition regulärer Ausdrücke (1)
    0:22:58 Beispiele
    0:23:44 Klammereinsparungsregeln
    0:25:01 Beispiele für Klammereinsparungsregeln
    0:26:05 Nichtbeispiele
    0:27:31 Definition der Syntax regulärer Ausdrücke
    0:29:03 Ableitungsbaum eines regulären Ausdrucks
    0:29:44 Durch R beschriebene formale Sprache
    0:30:55 Beispiele für
    0:32:44 Bestimmung von entlang des Ableitungsbaums von R
    0:34:08 Wie ist das denn eigentlich?
    0:35:24 Äquivalenz regulärer Ausdrücke
    0:37:40 Weitere Beispiele für
    0:40:26 RFC 5322: Internet Message Format
    0:43:01 RFC 5322, Abschnitt 3.3: Date and Time Specification, fast wörtlich:
    0:45:39 Datums- und Zeitangaben in Emails (2)
    0:46:28 Datums- und Zeitangaben in Emails (3)
    0:48:07 Charakterisierungen regulärer Sprachen
    0:50:46 Zum Beweis des Satzes
    0:53:39 Was ist wichtig
    1:00:13 Rechtslineare Grammatiken: Definition
    1:01:58 Rechtslineare Grammatiken: Beispiele
    1:04:06 Rechtslineare Grammatiken: Nichtbeispiel
    1:04:52 Sprechweisen
    1:06:53 Vorteil rechtslinearer Grammatiken
    1:07:54 Ziel dieses Abschnittes
    1:09:18 Mit Kantorowitsch-Bäumen kann man z.B. reguläre Ausdrücke repräsentieren
    1:10:53 Regex-Bäume - etwas genauer
    1:12:17 Vollständige Induktion über die Baumhöhe
    1:13:33 Vollständige Induktion über die Baumhöhe - ein Problem
    1:15:08 Erinnerung: Verallgemeinerung vollständiger Induktion
    1:15:49 Induktion über die Höhe der Regex-Bäume
    1:17:49 Skizze des Induktionsschritts (1)
    1:18:45 Skizze des Induktionsschritts (2)
    1:21:07 Strukturelle Induktion
    1:22:25 Zusammenfassung

    • 1 Std. 23 Min.
    • video
    Grundbegriffe der Informatik, Vorlesung, WS 2016/17, 25.01.2017, 22

    Grundbegriffe der Informatik, Vorlesung, WS 2016/17, 25.01.2017, 22

    22 |
    0:00:00 Starten
    0:00:04 Einheit 17: Quantitative Aspekte von Algorithmen
    0:01:45 Rechenzeiten
    0:13:35 Was ist wichtig
    0:14:07 Zusammenfassung
    0:14:55 Kapitel 18: Endliche Automaten
    0:15:46 Ein primitiver Getränkeautomat
    0:16:47 Getränkeautomat: Zustände
    0:19:27 Getränkeautomat: Eingaben
    0:21:18 Getränkeautomat: Zustandsübergänge
    0:29:52 Getränkeautomat: Aufgaben
    0:35:07 Maely-Automaten
    0:37:33 Verallgemeinerte Zustandsübergangsfunktionen
    0:45:08 Verallgemeinerte Ausgabenfunktion
    0:49:09 Moore-Automaten
    0:50:47 Moore-Automat: Beispiel aus tikz-Dokumentation
    0:52:32 Verallgemeinerte Zustandsübergangsfunktionen
    0:53:20 Verallgemeinerte Ausgabenfunktionen g* und g**
    0:56:20 Endliche Akzeptoren - ein wichtiger Sonderfall von Moore-Automaten
    0:58:29 Endlicher Akzeptor: Beispiel
    0:59:41 Akzeptierte und abgelehnte Wörter
    1:01:18 Erkannte formale Sprache
    1:04:06 Beispiel 2 einer erkennbaren Sprache
    1:11:14 Beispiel 3 einer erkennbaren Sprache
    1:15:32 Beispiel 3 - Entwicklung einer Lösung
    1:18:42 Beispiel einer nicht erkennbaren Sprache

    • 1 Std. 21 Min.

Kundenrezensionen

3.3 von 5
4 Bewertungen

4 Bewertungen

shannon0010 ,

Top Prof

Sehr gut erklärt, jedoch teilweise unterirdische Klangqualität.

Top‑Podcasts in Kurse

Zuhörer haben auch Folgendes abonniert:

Mehr von Karlsruher Institut für Technologie