Theoretische Grundlagen Der Informatik, Vorlesung, WS16/17 podcast

Theoretische Grundlagen der Informatik, Vorlesung, WS16/17

Player FM - Internet Radio Done Right

0-10 subscribers

Lagt til seven år siden

Innhold levert av Karlsruher Institut für Technologie (KIT). Alt podcastinnhold, inkludert episoder, grafikk og podcastbeskrivelser, lastes opp og leveres direkte av Karlsruher Institut für Technologie (KIT) eller deres podcastplattformpartner. Hvis du tror at noen bruker det opphavsrettsbeskyttede verket ditt uten din tillatelse, kan du følge prosessen skissert her https://no.player.fm/legal.

Mind The Business: Small Business Success Stories

1
Understanding Taxes as a Newly Formed Small Business - Part 2 of the Small Business Starter Kit 28:24

for 19 dager siden28:24

Spill senere

Lister

Lik

Likt

28:24

In our second installment of the Small Business Starter Kit series - we’re tackling a topic that’s sometimes tricky, sometimes confusing, but ever-present: taxes. Hosts Austin and Jannese have an insightful conversation with entrepreneur Isabella Rosal who started 7th Sky Ventures , an exporter and distributor of craft spirits, beer, and wine. Having lived and worked in two different countries and started a company in a heavily-regulated field, Isabella is no stranger to navigating the paperwork-laden and jargon-infused maze of properly understanding taxes for a newly formed small business. Join us as she shares her story and provides valuable insight into how to tackle your business’ taxes - so they don’t tackle you. Learn more about how QuickBooks can help you grow your business: QuickBooks.com See omnystudio.com/listener for privacy information.…

Theoretische Grundlagen der Informatik, Vorlesung, WS16/17

Del

Serier hjem•Feed

Theoretische Grundlagen der Informatik, Vorlesung, WS16/17

18 episoder

#Hochschulbildung #Bildung #Vorlesung #Informatik #Berechnungsmodelle #Determinismus #Nichtdeterminismus #Berechenbarkeit #Komplexitätstheorie #Grammatiken #Karlsruher Instituts Für Technologie KIT #Video #KIT #Theorie

Theoretische Grundlagen der Informatik, Vorlesung, WS16/17

0-10 subscribers

updated for 8 år siden

Del

Serier hjem•Feed

Theoretische Grundlagen der Informatik, Vorlesung, WS16/17

18 episoder

Alle episoder

Theoretische Grundlagen der Informatik, Vorlesung, WS16/17

1
Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 07.02.2017, 18 47:15

for 8 years siden47:15

47:15

18 | 0:00:00 Starten 0:00:07 Fortsetzung Informationstheorie 0:01:06 Wiederholung Quellkodierung 0:01:46 Kanalkodierung 0:02:24 Codierung zum Schutz gegen Übertragungsfehler 0:04:17 Paritätscodes - Einfach Binär 0:07:27 Kreuzsicherung 0:12:20 Paritätscodes 0:13:33 Beweis 0:15:09 Paritätscodes gegen Vertauschungsfehler 0:18:42 Bsp: ISBN-10 0:18:56 ISBN 0:19:59 Block-Codes 0:20:31 Hamming-Distanz und Fehlerkorrektur 0:21:58 Maximum-Likelihood-Decoding 0:23:08 Shannon's Theorem 0:23:52 Block-Codes 0:25:13 Beweisskizze 0:26:37 Werbung 0:28:18 Vorlesung Planare Graphen 0:36:07 Proseminar Theoretical Computer Science Classics 0:39:53 ICPC Praktikum 0:42:04 PSE Energieinformatik…

Theoretische Grundlagen der Informatik, Vorlesung, WS16/17

1
Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 02.02.2017, 17 1:07:17

for 8 years siden1:07:17

1:07:17

17 | 0:00:00 Starten 0:01:45 Thema dieses Kapitels 0:04:52 Material für Informationstheorie 0:05:32 Information 0:12:45 Wiederholung: Rechenregeln Logarithmus 0:13:53 Definition Information 0:14:52 Entropie 0:19:16 Bemerkung zur Entropie 0:19:31 Entropie einer Münze mit Wkt p für Zahl 0:20:44 (Platzsparende) Codierungen 0:22:12 Codierungsbäume 0:26:49 Präfix-Codes 0:29:08 Beispiel: Morse-Alphabet 0:30:15 Quellencodierungstheorem 0:31:47 Beispiel: Shannon-Fano Codierung 0:38:01 Codierungsbaum Shannon-Fano 0:38:59 Beispel: Huffman-Codierung 0:44:36 Optimalität der Huffman-Codierung 0:45:13 Vorbereitendes Lemma 0:47:00 VorbereitendesLemma: Beweis 0:51:10 Beweis - Induktionsschluss 0:57:00 Nachteile der Huffman-Codierung 0:59:05 Lauflängenkodierung…

Theoretische Grundlagen der Informatik, Vorlesung, WS16/17

1
Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 26.01.2017, 16 1:11:18

for 8 years siden1:11:18

1:11:18

16 | 0:00:00 Starten 0:00:37 Kellerautomaten 0:03:49 Satz 0:05:15 Satz (2) 0:06:09 Beweis 0:30:19 Korollar 0:30:41 Übersicht Chomsky-2 0:32:46 Exkurs 0:34:16 Zwischenfazit zu kontextfreien Grammatiken 0:36:10 Satz (3) 0:38:18 Das Post'sche Korrespondenzproblem 0:39:47 Beweis (2) 0:43:33 Beweisskizze 0:44:07 Beweis (3) 0:45:50 Sprache der korrekten Rechenwege 0:51:59 Lemma 0:52:28 Beweis (4) 1:01:26 Bemerkung 1:02:03 Lemma (2) 1:02:27 Beweis (5)…

Theoretische Grundlagen der Informatik, Vorlesung, WS16/17

1
Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 24.01.2017, 15 47:17

for 8 years siden47:17

47:17

15 | 0:00:00 Starten 0:00:07 Beweis 0:03:26 Kellerautomaten 0:09:17 Kellerautomaten - Visualisierung 0:10:09 Kellerautomaten - Arbeitsweise 0:18:33 Kellerautomaten - Beispiel 0:27:20 Kellerautomaten - Beispiel 2 0:31:02 Satz (1) 0:35:44 Satz (2) 0:39:19 Satz (3)

Theoretische Grundlagen der Informatik, Vorlesung, WS16/17

1
Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 12.01.2017, 14 1:06:23

for 8 years siden1:06:23

1:06:23

14 | 0:00:00 Starten 0:00:07 Wiederholung 0:12:03 Ogden´s Lemma für kontextfreie Sprachen 0:14:31 Beweis 0:29:20 Beweis - Teil 1 0:30:23 Beweis - Teil 2 0:39:23 Beweis - Teil 3 0:41:58 Nutzlose Variablen 0:43:38 Schritt 1 0:47:24 Beispiel: Schritt 1 0:51:28 Schritt 2 0:53:16 Beispiel: Schritt 2 0:56:45 Korollar 0:59:27 Beispielgraph…

Theoretische Grundlagen der Informatik, Vorlesung, WS16/17

1
Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 10.01.2017, 13 1:23:54

for 8 years siden1:23:54

1:23:54

13 | 0:00:00 Starten 0:00:31 Wiederholung 0:02:13 Die Chmosky Hierarchie 0:08:16 Syntaxbäume 0:10:28 Syntaxbäume - Beispiel 0:15:54 Links/Rechtsabteilung, Eindeutigkeit 0:17:31 Beispiel 0:19:37 Chomsky-Normalform 0:20:56 Die Chomsky Hierarchie 0:21:21 Chomsky-Normalform 0:31:01 Schritt 1 0:34:21 Schritt 2 0:38:20 Schritt 3 0:49:34 Schritt 4 0:53:36 Abhängigkeitsgraph 0:54:42 Schritt 4 – Phase 1 0:56:47 Schritt 4 – Phase 2 1:02:02 Der CYK-Algorithmus 1:05:15 Beweis - Beschreibung des CYK-Algorithmus 1:08:33 CYK-Algorithmus – Beispiel 1:12:31 CYK-Algorithmus – Vorgehen 1:14:50 Beweis - Beschreibung des CYK-Algorithmus 1:15:39 CYK-Algorithmus – Vorgehen 1:16:10 CYK-Algorithmus – Beispiel 1:22:11 CYK-Algorithmus – Vorgehen 1:22:48 Ergebnisse zum Wortproblem…

Theoretische Grundlagen der Informatik, Vorlesung, WS16/17

1
Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 22.12.2016, 12 1:03:41

for 8 years siden1:03:41

1:03:41

12 | 0:00:00 Starten 0:00:28 Grammatiken 0:01:26 Beispiele 0:05:33 Grammatiken 0:07:12 Bemerkungen 0:08:32 Beispiel 0:09:22 Die Chomsky Hierarchie 0:20:09 Chomsky-0 Grammatiken und Semientscheidbarkeit 0:24:58 Beweis - Beschreibung der Grammatik G 0:28:28 Beweis - Zusammenfassung 0:29:42 Chomsky-0 Grammatiken und Semientscheidbarkeit 0:32:04 Zwischenfazit 0:34:01 Chomsky-3-Grammatiken und reguläre Sprachen 0:35:27 Beweis 0:42:00 Bemerkung 0:43:05 Chomsky-1-Grammatiken bzw. kontextsensitive Sprachen 0:48:01 Satz 0:48:59 Bemerkung 0:49:17 Wiederholung: Das Problem CLIQUE 0:50:02 Satz 0:54:02 Bemerkung 1 0:54:53 Bemerkung 2 0:56:12 Notation 0:57:15 Typ-2 / Kontextfreie Grammatiken 0:57:40 Typ-2 Grammatiken: Beispiel 1 0:58:51 Typ-2 Grammatiken: Beispiel 2 1:00:44 Typ-2 Grammatiken: Beispiel 3…

Theoretische Grundlagen der Informatik, Vorlesung, WS16/17

1
Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 15.12.2016, 11 1:00:16

for 8 years siden1:00:16

1:00:16

11 | 0:00:00 Starten 0:02:50 Approximation mit relativer Gütegarantie 0:03:31 Definition 0:04:49 Approximierbarkeit von COLOR 0:18:45 Approximierbarkeit von TSP 0:28:12 Approximationsschemata 0:38:45 Ein FPAS für KNAPSACK (1) 0:40:02 Ein pseudopolynomialer, optimaler Algorithmus für KNAPSACK 0:43:49 Ein FPAS für KNAPSACK (2) 0:58:51 Ein allgemeineres Resultat…

Theoretische Grundlagen der Informatik, Vorlesung, WS16/17

1
Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 13.12.2016, 10 1:11:07

for 8 years siden1:11:07

1:11:07

10 | 0:00:00 Starten 0:03:37 VerallgemeinerteNP-Schwere 0:07:17 Das Problem INTEGER PROGRAMMING 0:26:15 Pseudopolynomiale Algorithmen 0:29:56 Beispiel: Problem KNAPSACK 0:40:20 Starke NP-Vollständigkeit 0:44:14 Absolute Approximationsalgorithmen 0:46:31 Das allgemeine KNAPSACK-Suchproblem 0:57:09 Approximation mit relativer Gütegarantie 0:59:53 Beispiel: Greedy-Algorithmus für KNAPSACK…

Theoretische Grundlagen der Informatik, Vorlesung, WS16/17

1
Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 06.12.2016, 09 1:23:35

for 8 years siden1:23:35

1:23:35

09 | 0:00:00 Starten 0:06:41 Das Problem SUBSET SUM 0:07:46 NP-Vollständigkeit von SUBSET SUM 0:24:03 Das Problem PARTITION 0:31:06 Das Problem KNAPSACK 0:37:32 Auswirkungen auf die Frage P=NP 0:45:42 Zusammenfassung 0:47:57 Die Klassen NPI, co-P und co-NP 0:54:22 Das TSP-Komplement-Problem 0:57:40 Lemma 1:00:00 Bemerkung 1:01:25 Das Problem Subgraphisomorphie 1:03:14 Das Problem Graphismorphie 1:09:06 Suchprobleme 1:10:21 Beispiel: TSP-Suchproblem 1:11:03 Beispiel: Hamilton–Kreis Suchproblem 1:12:04 Aufzählungsprobleme 1:12:44 Reduzierbarkeit für Suchprobleme 1:15:36 Orakel-Turing-Machine 1:19:40 NP-schwer 1:20:39 Beweisskizze…

Theoretische Grundlagen der Informatik, Vorlesung, WS16/17

1
Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 01.12.2016, 08 1:27:34

for 8 years siden1:27:34

1:27:34

08 | 0:00:00 Starten 0:00:37 Wiederholung: NP-Vollständigkeit 0:06:10 Wiederholung: Transitivität der poly. Transformation 0:06:40 Wiederholung: Korollar 0:07:37 Wiederholung: Das Problem SAT (satisfiability) 0:12:17 Das Problem 3-SAT 0:13:13 Beweis: NP-Vollständigkeit von 3-SAT 0:30:07 Das Problem 2SAT 0:34:40 Das Problem MAX2SAT 0:38:02 Das Problem CLIQUE 0:39:32 Beweis: NP-Vollständigkeit von CLIQUE 0:51:19 Das Problem COLOR 0:54:56 Beweis: NP-Vollständigkeit von 3COLOR 0:57:29 Konstruktion von 3COLOR-Instanz G 1:01:05 Beispielgraph zur Reduktion 1:04:20 Polynomialität der Reduktion 1:04:56 Instanz I erfüllbar => Instanz G erfüllbar 1:07:12 Instanz I erfüllbar <= Instanz G erfüllbar 1:08:02 Das Problem EXACT COVER 1:13:06 Beweis: NP-Vollständigkeit von EXACT COVER 1:14:28 Konstruktion von (X,S) 1:24:05 G dreifärbbar => (X,S) hat exakte Überdeckung 1:25:47 G dreifärbbar <= (X,S) hat exakte Überdeckung…

Theoretische Grundlagen der Informatik, Vorlesung, WS16/17

1
Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 24.11.2016, 07 1:25:14

for 8 years siden1:25:14

1:25:14

07 | 0:00:00 Starten 0:01:06 Die Klasse P 0:03:19 Die Klasse NP 0:04:47 Die Nichtdeterministische Turingmaschine 0:05:17 Zeitkomplexität für NTM 0:08:55 Große Frage der Theoretischen Informatik 0:11:38 NP-Vollständigkeit 0:24:35 Transitivität der poly. Transformation 0:25:46 Korollar 0:28:28 Das Problem SAT (satisfiability) 0:31:05 Weitere Beispiele für SAT-Instanzen 0:33:44 Der Satz von Cook (Steven Cook, 1971) 0:36:00 Beweis 0:42:53 Beweis: Konstruktion der Variablen 0:49:48 Beweis 0:53:35 Beweis: Konstruktion der Klauseln - Übersicht 0:56:09 Klauselgruppe 1: 0:59:10 Klauselgruppe 2: 1:00:15 Klauselgruppe 3: 1:01:50 Klauselgruppe 4: 1:03:23 Klauselgruppe 5: 1:04:36 Klauselgruppe 6: 1:06:51 Klauselgruppe 6, 1: 1:09:51 Klauselgruppe 6,2: 1:13:35 Konstruktion der Klauseln - Zwischenergebnis 1:15:11 Polynomialität der Transformation 1:15:45 Polynomialität - Klauselgruppe 1: 1:16:20 Polynomialität - Klauselgruppe 2: 1:17:25 Polynomialität - Klauselgruppe 3: 1:17:56 Polynomialität - Klauselgruppe 4: 1:18:38 Polynomialität - Klauselgruppe 5:…

Theoretische Grundlagen der Informatik, Vorlesung, WS16/17

1
Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 22.11.2016, 06 1:31:49

for 8 years siden1:31:49

1:31:49

06 | 0:00:00 Starten 0:00:54 Definitionen zur TM 0:05:21 Notation: Konfiguration 0:07:49 Beispiel: Konfiguration 0:20:00 Definition: berechenbar / totalrekursiv 0:22:30 Beispiel 0:26:57 Entscheidbarkeit und Berechenbarkeit 0:30:18 Korollar 0:33:13 Die Church´sche These 0:36:20 Erweiterungen der Turing-Maschine 0:39:17 Die universelle Turing-Maschine 0:45:24 Die Gödelnummer 0:50:45 Die Gödelnummer - Bemerkungen 0:54:43 Die Gödelnummer - Beispiel 0:58:54 Definition 1:00:08 Die Diagonalsprache 1:05:42 Die Diagonalsprache - Veranschaulichung 1:07:03 Unentscheidbarkeit der Die Diagonalsprache 1:09:24 Korollar 1:14:01 Paradoxien und Selbstbezüglichkeit 1:17:13 Das Halteproblem 1:24:15 Halteproblem nicht entscheidbar…

Theoretische Grundlagen der Informatik, Vorlesung, WS16/17

1
Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 17.11.2016, 05 1:25:26

for 8 years siden1:25:26

1:25:26

05 | 0:00:00 Starten 0:00:54 Definitionen zur TM 0:05:56 Notation: Konfiguration 0:07:50 Beispiel: Konfiguration 0:20:37 Definition: berechenbar / totalrekursiv 0:23:01 Beispiel 0:27:27 Entscheidbarkeit und Berechenbarkeit 0:30:19 Korollar 0:33:21 Die Church´sche These 0:36:38 Ertweiterungen der Turing-Maschine 0:39:39 Die universelle Turing-Maschine 0:44:35 Die Gödelnummer 0:50:58 Die Gödelnummer - Bemerkungen 0:53:35 Die Gödelnummer - Beispiel 0:59:14 Definition 1:01:05 Die Diagonalsprache 1:05:35 Die Diagonalsprache - Veranschaulichung 1:07:32 Unentscheidbarkeit der Diagonalsprache 1:10:06 Korollar 1:11:03 Paradoxien und Selbstbezüglichkeit 1:14:47 Das Halteproblem 1:21:00 Grenzen der Berechenbarkeit 1:22:05 Halteproblem nicht entscheidbar…

Theoretische Grundlagen der Informatik, Vorlesung, WS16/17

1
Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 10.11.2016, 04 1:21:16

for 8 years siden1:21:16

1:21:16

04 | 0:00:00 Starten 0:00:12 Endliche Automaten, reguläre Sprachen 0:00:57 Frage 0:01:40 Äquivalenz 0:04:24 Der Äquivalenzklassenautomat 0:06:29 Vorgehensweise 0:08:44 Frage 0:10:29 Antwort 0:13:49 Definitionen: Rechtsinvarianz und Index 0:17:08 Nerode-Relation 0:20:55 Satz von Nerode 0:24:06 Beweis zu Satz von Nerode: (1) – (2) 0:28:54 Beweis zu Satz von Nerode: (2) – (3) 0:31:43 Beweis zu Satz von Nerode: (3) – (1) 0:37:00 Satz von Nerode 0:37:38 Korollar 0:40:52 Minimalität des Äquivalenzklassenautomats 0:44:19 Zusammenfassung 0:48:45 Kapitel: Turing-Maschinen und Berechenbarkeit 0:52:00 Die Registermaschine (RAM) 0:53:23 Befehle der Registermaschine (RAM) 0:53:52 Kostenmodell der Registermaschine (RAM) 0:54:56 Die Turingmaschine (TM) 0:57:54 Die Turingmaschine (TM) 0:58:20 Formale Definition der Turingmaschine 1:01:51 Bermerkungen zur TM 1:05:09 Beispiel-Turingmaschine 1:15:15 Bemerkungen zur TM 1:16:48 Definitionen zur TM…

Velkommen til Player FM!

Player FM scanner netter for høykvalitets podcaster som du kan nyte nå. Det er den beste podcastappen og fungerer på Android, iPhone og internett. Registrer deg for å synkronisere abonnement på flere enheter.