{"id":9591,"date":"2019-05-06T09:05:28","date_gmt":"2019-05-06T09:05:28","guid":{"rendered":"http:\/\/blog.bachi.net\/?p=9591"},"modified":"2019-06-24T19:46:34","modified_gmt":"2019-06-24T19:46:34","slug":"ftp_theocomp","status":"publish","type":"post","link":"https:\/\/blog.bachi.net\/?p=9591","title":{"rendered":"FTP_TheoComp"},"content":{"rendered":"

Komplexit\u00e4tstheorie<\/a>
\nVolker Strassen<\/a>
\nStrassen-Algorithmus<\/a>
\nSolovay-Strassen-Test<\/a>
\nAdditionskette<\/a>
\nBin\u00e4re Exponentiation<\/a>
\nRussische Bauernmultiplikation<\/a>
\nDeterminante<\/a>
\nPermanente<\/a>
\nPermutation<\/a>
\nPermutationsmatrix<\/a>
\nZyklische Permutation -> Vertauschung oder Transposition<\/a>
\nVorzeichen (Permutation)<\/a><\/p>\n

Woche 10<\/h2>\n

Wikipedia<\/h4>\n

Komplexit\u00e4tstheorie<\/a>
\nAutomat (Informatik)<\/a>
\nLandau-Symbole<\/a>
\nKonjunktive Normalform<\/a><\/p>\n

Woche 13<\/h2>\n

Tutorial<\/h4>\n

Aussagen und Logik<\/a> (dann folgt)<\/p>\n

Wikipedia<\/h4>\n

Karps 21 NP-vollst\u00e4ndige Probleme<\/a>
\nDisjunktionsterm \/ Klausel<\/a>
\nLiteral<\/a>, (Wahrheitswerte: true, false)
\nClique (Graphentheorie)<\/a>
\nCliquenproblem<\/a>
\nKnoten\u00fcberdeckung<\/a>
\nKnoten\u00fcberdeckungsproblem<\/a>
\nErf\u00fcllbarkeitsproblem der Aussagenlogik (SAT)<\/a>
\n3-SAT<\/a>
\nTeilsummenproblem (subset sum problem)<\/a><\/p>\n

YouTube<\/h4>\n

Komplexit\u00e4t #05 – Polyzeit-Reduktionen<\/a>
\n16. Complexity: P, NP, NP-completeness, Reductions<\/a>
\nReductions – Intro to Theoretical Computer Science<\/a>
\nPolynomialzeit-Reduktion<\/a>
\nVertex Cover (Knoten\u00fcberdeckung)<\/a>
\nCSC 333 Reductions from Ham Cycle to TSP and from Vertex Cover to Dominating Set<\/a>
\nNP Completeness for Dummies: Reduction of NP Complete Problems<\/a>
\nReductions and NP-Complete Proofs (CS)<\/a> (Karp Reduction)<\/p>\n

YouTube<\/h3>\n

Leibnizformel f\u00fcr Determinanten<\/a>
\nZyklendarstellung von Permutationen<\/a><\/p>\n

Die Chomsky-Hierarchie<\/a>
\nTheoretische Informatik<\/a>, Karsten Morisse (Playlist)
\nTI_6_6 TM: akzeptieren und entscheiden<\/a>, Karsten Morisse
\nTheoretische Informatik – Kontextsensitive Sprachen<\/a>
\nGraphen, Grammatiken und Automaten<\/a>, The Morpheus Tutorials (Playlist)
\nTheoretische Informatik (Wintersemester 2013\/2014)<\/a>, Weitz \/ HAW Hamburg
\nTim Roughgarden on Theoretical Computer Science<\/a> (Playlist)
\nAlgorithms Live!<\/a>
\nWilliamFiset Algorithms<\/a><\/p>\n

B\u00fccher \/ Books<\/h1>\n

Diskrete Mathematik erleben, Stephan Hu\u00dfmann, Brigitte Lutz-Westphal, 2015
\nFundamentals of Discrete Math for Computer Science, Tom Jenkyns, Ben Stephenson, 2018
\nKonkrete Mathematik (nicht nur) f\u00fcr Informatiker, Edmund Weitz, 2018
\nKonkrete Mathematik (nicht nur) f\u00fcr Informatiker<\/a> (Playlist)<\/p>\n

NLogSpace<\/h1>\n

Formale Sprachen<\/a>
\nBerechenbarkeit<\/a>
\nKomplexit\u00e4t<\/a>
\nEntscheidbar, unentscheidbar, semi-entscheidbar?<\/a><\/p>\n

Mathematik-Vorkurs \u2013 Universit\u00e4t des Saarlandes<\/h1>\n

Kapitel 1 – Sprachen<\/a>
\nKapitel 2.1 – Aussagenlogik<\/a>
\nKapitel 2.2 – Pr\u00e4dikatenlogik<\/a>
\nKapitel 3 – Schlie\u00dfen und Beweisen<\/a>
\nKapitel 4 – Mengen<\/a>
\nKapitel 5 – Relationen<\/a>
\nKapitel 6 – Induktion<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

Komplexit\u00e4tstheorie Volker Strassen Strassen-Algorithmus Solovay-Strassen-Test Additionskette Bin\u00e4re Exponentiation Russische Bauernmultiplikation Determinante Permanente Permutation Permutationsmatrix Zyklische Permutation -> Vertauschung oder Transposition Vorzeichen (Permutation) Woche 10 Wikipedia Komplexit\u00e4tstheorie Automat (Informatik) Landau-Symbole Konjunktive Normalform Woche 13 Tutorial Aussagen und Logik (dann folgt) Wikipedia Karps 21 NP-vollst\u00e4ndige Probleme Disjunktionsterm \/ Klausel Literal, (Wahrheitswerte: true, false) Clique (Graphentheorie) Cliquenproblem Knoten\u00fcberdeckung […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-9591","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/blog.bachi.net\/index.php?rest_route=\/wp\/v2\/posts\/9591","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.bachi.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.bachi.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.bachi.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.bachi.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=9591"}],"version-history":[{"count":27,"href":"https:\/\/blog.bachi.net\/index.php?rest_route=\/wp\/v2\/posts\/9591\/revisions"}],"predecessor-version":[{"id":9737,"href":"https:\/\/blog.bachi.net\/index.php?rest_route=\/wp\/v2\/posts\/9591\/revisions\/9737"}],"wp:attachment":[{"href":"https:\/\/blog.bachi.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=9591"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.bachi.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=9591"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.bachi.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=9591"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}