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/17 Karlsruher Institut für Technologie (KIT)

    • Bildung
    • 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 Bildung

Deutschlandfunk Nova
Greator – GEDANKENtanken
Maxim Mankevich
Ralf Senftleben
Ron Perduss / Audio Alliance
Christian Bischoff - Persönlichkeits- und Mentaltrainer

Mehr von Karlsruher Institut für Technologie

Karlsruher Institut für Technologie (KIT)
Karlsruher Institut für Technologie (KIT)
Karlsruher Institut für Technologie (KIT)
Karlsruher Institut für Technologie (KIT)
Karlsruher Institut für Technologie (KIT)
Karlsruher Institut für Technologie (KIT)