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
All content for Grundbegriffe der Informatik, Vorlesung, WS16/17 is the property of Karlsruher Institut für Technologie (KIT) and is served directly from their servers
with no modification, redirects, or rehosting. The podcast is not affiliated with or endorsed by Podjoint in any way.
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, WS 2016/17, 01.02.2017, 24
Grundbegriffe der Informatik, Vorlesung, WS16/17
1 hour 29 minutes 8 seconds
8 years ago
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
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
