Grundbegriffe der Informatik, Vorlesung, WS16/17

Karlsruher Institut für Technologie (KIT)
  • 0,0 (0)
  • KURSE
Grundbegriffe der Informatik, Vorlesung, WS16/17

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

  1. 16.02.2017 · VIDEO

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

  2. 16.02.2017 · VIDEO

    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

    45 Min.

  3. 16.02.2017 · VIDEO

    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.

  4. 09.02.2017 · VIDEO

    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.

  5. 03.02.2017 · VIDEO

    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.

  6. 30.01.2017 · VIDEO

    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.

  7. 25.01.2017 · VIDEO

    Grundbegriffe der Informatik, Übung, WS 2016/17, 20.01.2017, 21

    21 | 0:00:00 Starten 0:00:05 Aufgabe 5.1 0:06:10 Aufgabe 5.2 0:10:56 Aufgabe 5.3 0:16:29 Aufgabe 5.5 0:21:42 Aufgabe 5.4 0:24:40 Aufgabe 5.6 0:31:26 Aufgabe 5.7 0:32:52 Catalan-Zahl 0:33:38 Eigenschaften 0:41:01 Aufgabe 5.8 0:49:49 Aufgabe 5.1 0:55:42 Aufgabe 5.7

    57 Min.

  8. 24.01.2017 · VIDEO

    Grundbegriffe der Informatik, Übung, WS 2016/17, 09.12.2016, 15

    15 | 0:00:00 Starten 0:01:12 Aufgabe 3.6 0:23:38 Aufgabe 3.5 0:45:35 Aufgabe 3.3 1:14:43 Aufgabe 3.2 - 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.

    1 Std. 32 Min.
Alle anzeigen (27)

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. Dozent: Dr. Sebastian Stüker |  Karlsruher Institut für Technologie (KIT), Institut für Anthropomatik und Robotik | Vorlesungsaufzeichnung: http://webcast.kit.edu

Informationen

Mehr von Karlsruher Institut für Technologie

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