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.
Vorlesungsaufzeichnung: http://webcast.kit.edu

Grundbegriffe der Informatik, Vorlesung, WS18/19 Karlsruher Institut für Technologie

    • Kurse
    • 5.0, 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.
Vorlesungsaufzeichnung: http://webcast.kit.edu

    • video
    26: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 06.02.2019

    26: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 06.02.2019

    26 |
    0:00:00 Start
    0:00:30 Halbordnungen
    0:09:59 Minimale und maximale Elemente/ Beispiel
    0:18:32 Untere und obere Schranken/-Beispiel
    0:23:29 Supremum und Infimum/-Beispiele
    0:36:03 Monotone Abbildungen
    0:38:54 Stetige Abbildungen/-Beispiele
    0:43:57 Fixpunktsatz/-Beweis
    0:52:57 Was ist wichtig ?
    0:54:44 Ordungen
    0:55:28 Totale Ordung
    1:00:06 Totale Ordung auf A*
    1:02:30 Milchstraße-Milch-Milchreis-- Beispiel
    1:04:08 Lexikographische Ordung (Wörterbuch)
    1:14:07 Was ist wichtig
    1:15:25 Kapietel 22: MIMA-X
    1:17:08 Ackermann-Funktion
    1:20:13 Stapel oder Keller

    • 1 Std. 26 Min.
    • video
    25: Grundbegriffe der Informatik, Vorlesung und Übung, WS 2018/19, 01.02.2019

    25: Grundbegriffe der Informatik, Vorlesung und Übung, WS 2018/19, 01.02.2019

    25 |
    0:00:00 Start
    0:00:22 Äquivalenzrelationen
    0:01:41 Kongruenz ganzer Zahlen modulo n
    0:04:05 Bild einer Äquivalnzrelation
    0:12:15 Was ist wichtig
    0:13:40 Äquivalenzrelationen auf mengen mit Struktur
    0:18:23 Kongruenzrelationen
    0:20:52 Verträglichkeit erlaubt die Übertragung einer Abbildung auf die Faktormenge
    0:24:33 Rückblick auf endliche Akzeptoren
    0:28:38 Verträglichkeit: Beispiel Nerode-Äquivalenzen
    0:37:32 Antisymmetrische Relationen
    0:39:52 Halbordnungen
    0:41:49 eine Halbordnung auf Wörtern – darauf bauen wir später noch auf
    0:43:37 Übung
    0:44:44 Reguläre Ausdrücke
    0:49:29 Ein regulärer Ausdruck für epsilon
    0:54:44 Distributivgesetz
    0:56:14 Kantorowitsch-Bäume
    1:01:53 Kantorowitsch-Bäume und reguläre Ausdrücke
    1:04:51 Beispiel: Zahlen spezifizieren
    1:07:14 Ein Wiederbesuch: Wörter umkehren
    1:11:32 Rechtslineare Grammatiken
    1:15:16 Charakterisierung regulärer Sprachen
    1:18:47 Linkslineare Grammatiken
    1:23:40 Äquivalenz RL und LL Grammatiken

    • 1 Std. 26 Min.
    • video
    24: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 30.01.2019

    24: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 30.01.2019

    24 |
    0:00:00 Start
    0:00:39 Wiederholung(Turingmaschinen)
    0:02:42 Endliche Automaten
    0:03:56 Reguläre Ausdrücke
    0:07:50 Klammereinsparungsregeln
    0:12:41 Durch R Beschriebene formale Sprachen / Beispiel
    0:14:49 Beispiele für R
    0:27:56 Charakterisierungen regulärer Sprachen
    0:34:39 Rechtslineare Grammatiken (Typ 3)
    0:39:02 Rechtslineare Grammatiken: Beispiele
    0:44:42 Sprechweisen
    0:47:29 Vorteile rechtslinearer Grammatiken
    0:49:49 Kantorowitsch-Bäume und strukturelle Induktion
    0:52:31 Mit Kantorowitsch-Bäumen kann man z.B. reguläre Ausdrücke repräsentieren
    0:56:25 Regex-Bäume -- etwas genauer
    1:00:06 Vollständige Induktion über die Baumhöhe
    1:04:44 Skizze des Induktionsschritts
    1:12:15 Zusammenfassung
    1:14:29 Äquivalenzrelationen
    1:15:48 Kongruenz ganzer Zahlen modulo n
    1:16:59 Beispiel: asymtptotisches gleiches Wachstum
    1:17:33 Urbilder von Fuktionswerten

    • 1 Std. 19 Min.
    • video
    23: Grundbegriffe der Informatik, Vorlesung und Übung, WS 2018/19, 25.01.2019

    23: Grundbegriffe der Informatik, Vorlesung und Übung, WS 2018/19, 25.01.2019

    23 |
    0:00:00 Start
    0:00:05 Turingmaschinen
    0:04:32 Unentscheidbare Probleme
    0:04:59 Beispielcodierung
    0:16:51 Das Halteproblem
    0:19:24 Beweis mit Diagonalisierung
    0:30:28 Weitere unentscheidbare Probleme
    0:34:48 Erinnerung: BB3
    0:36:22 Fleißige Biber und die Busy-Beaver-Funktion
    0:43:20 Steam-Powered Turing Machine ;-)
    0:44:04 Zusammenfassung
    0:44:25 Beginn der Übung
    0:44:56 Endlicher Akzeptor
    0:48:28 Beispiele regulärer Sprachen
    0:52:19 Akzeptoren: Komplement
    0:54:53 Akzeptoren: Schnitt
    0:59:54 Akzeptoren: Vereinigung
    1:03:32 Reguläre Sprachen und kontextfreie Grammatiken
    1:07:38 Turing-Maschinen (TMs)
    1:17:10 Analyse: Zeit- und Platzbedarf
    1:18:56 TM: Akzeptor, Entscheider
    1:25:34 TMs und endliche Akzeptoren
    1:27:35 Church-Turing-These

    • 1 Std. 29 Min.
    • video
    22: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 23.01.2019

    22: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 23.01.2019

    22 |
    0:00:00 Start
    0:00:40 Endliche Automaten
    0:02:22 Beispiel einer nicht erkennbaren Sprache
    0:13:53 Zusammenfassung / Was ist wichtig ?
    0:16:19 Turingmaschinen
    0:19:33 Eine Turingmaschine im Bild
    0:25:27 Turingmaschine: graphische Darstellung/ tabellarische Darstellung
    0:28:42 Beispielberechnung
    0:35:53 Längere Beispielberechnung von BB3
    0:37:56 Berechnung und Endkonfigurationen
    0:48:04 Beispiel: Palindromerkennung
    0:56:10 Entscheidbare und aufzählbare Sprachen
    1:01:54 Zeitkomplexität - der Rechenzeitbedarf einer TM
    1:06:30 Raumkomplexität
    1:07:49 Zeitkomplexität versus Raumkomplexität
    1:09:48 Eine Komplexitätsklasse ist eine Menge von Problemen
    1:11:35 P und PSPACE- Zwei wichtige Komplexitätsklassen
    1:17:40 Unentscheidbare Probleme
    1:19:46 Codierung von Turingmaschinen

    • 1 Std. 24 Min.
    • video
    21: Grundbegriffe der Informatik, Vorlesung und Übung, WS 2018/19, 18.01.2019

    21: Grundbegriffe der Informatik, Vorlesung und Übung, WS 2018/19, 18.01.2019

    21 |
    0:00:00 Start
    0:00:30 mMealy-Automaten
    0:04:21 Verallgemeinerte Zusatndsübergangsfunktionen
    0:06:09 Verallgemeinerte Ausgabefunktionen
    0:07:47 Was ist wichtig
    0:10:21 Moore-Automat
    0:12:43 Verallgemeinerte Zusatndsübergangsfunktionen
    0:13:44 Verallgemeinerte Ausgabefunktionen
    0:20:06 Endliche Akzeptoren
    0:22:59 Akzeptierte und abgelehnte Wörter
    0:25:13 Erkannte formale Sprache
    0:43:00 Übung 12: asymptotische Analyse und endliche Automaten
    0:43:57 Operationen auf Abbildungen
    0:50:56 Noch etwas O-Kalkül: unvergleichbare Abbildungen
    0:54:40 Master-Theorem
    1:04:22 Über Asymptotik hinaus: Schleifendurchläufe zählen
    1:07:55 Endliche Automaten
    1:09:54 Mealy-Automaten und Zahlendarstellung
    1:12:20 Moore-Automat: Beispiel aus der realen Welt
    1:14:20 Zustandsfolge, Ausgabe
    1:17:01 Umwandlung von Mealy- in Moore-Automaten

    • 1 Std. 24 Min.

Kundenrezensionen

5.0 von 5
4 Bewertungen

4 Bewertungen

Top‑Podcasts in Kurse

Zuhörer haben auch Folgendes abonniert:

Mehr von Karlsruher Institut für Technologie