Grundbegriffe der Informatik, Vorlesung, WS18/19

Karlsruher Institut für Technologie (KIT)
  • 4,6 (11)
  • KURSE
Grundbegriffe der Informatik, Vorlesung, WS18/19

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

  1. 07.02.2019 · VIDEO

    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.

  2. 04.02.2019 · VIDEO

    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. 27 Min.

  3. 31.01.2019 · VIDEO

    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. 20 Min.

  4. 29.01.2019 · VIDEO

    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.

  5. 24.01.2019 · VIDEO

    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. 25 Min.

  6. 21.01.2019 · VIDEO

    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. 25 Min.

  7. 17.01.2019 · VIDEO

    20: Grundbegriffe der Informatik, Vorlesung, WS 2018/19, 16.01.2019

    20 | 0:00:00 Start 0:00:15 Überblick 0:01:58 2x2 Matrizenmultiplikation 0:06:47 Die Idee von Volker Strassen 0:09:23 Aufwandsabschätzung für den Algorithmus von Strassen 0:13:22 Matrizenmultiplikation- geht es noch schneller? / Teile und herrsche(divide and conquer) 0:16:56 Laufzeit von Teile-und-Herrsche-Algorithmen 0:20:54 Mastertheorem-bescheidener hätte auch gereicht 0:32:48 Rechenzeiten 0:38:58 Zusammenfassung 0:41:51 Endliche Automaten 0:43:33 Ein primitiver Getränkeautomat 0:44:51 Getränkeautomat: Zustände 0:46:39 Getränkeautomat: Eingaben 0:47:40 Getränkeautomat: Zustandsübergänge 0:54:04 Getränkeautomat: Ausgaben 0:58:08 Mealy-Automaten 0:59:45 Verallgemeinerte Zustandsübergangsfunktionen 1:08:34 Was ist wichtig Lernziele: 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. Lehrinhalt: 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

    1 Std. 10 Min.

  8. 10.01.2019 · VIDEO

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

    19 | 0:00:00 Start 0:00:25 Groß-O-Notation 0:15:24 Groß-O-Notation: Notation für obere und untere Schranken des Wachstums 0:25:37 Groß-O-Notation: Eine grauenhafte Schreibweise 0:35:40 Groß-O-Notation: Was ist wichtig 0:37:41 Matrizenmultiplikation: 2x2 Matrizen 0:40:07 nxn Matrizen 0:42:04 Übung 0:43:09 Erinnerung: Matrixmultiplikation 0:46:06 Adjazenzmatrizen 0:48:50 Erreichbarkeitsmatrizen 0:53:02 Wegematrix 0:55:02 Adjazenz- und Wegematrix: Eindeutigkeit 0:57:54 Zusammenhang Matrizen und Relationen in Graphen 1:06:59 O-Kalkül 1:10:53 O-Kalkül: Logarithmen 1:13:13 O-Kalkül: Exponentialfunktionen 1:20:18 O-Kalkül: Fakultät

    1 Std. 26 Min.
Alle anzeigen (26)

    Bewertungen und Rezensionen

    4,6
    von 5
    11 Bewertungen

    Info

    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

    Informationen

    Mehr von Karlsruher Institut für Technologie

    Eingeschränkter Inhalt

    Diese Folge kann in deinem Land oder deiner Region nicht im Internet wiedergegeben werden.

    Melde dich an, um anstößige Folgen anzuhören.

    Bleib auf dem Laufenden mit dieser Sendung

    Melde dich an oder registriere dich, um Sendungen zu folgen, Folgen zu sichern und die neusten Updates zu erhalten.
    Wähle ein Land oder eine Region aus

    Afrika, Naher Osten und Indien

    Asien/Pazifik

    Europa

    Lateinamerika und Karibik

    USA und Kanada