Komplexitätstheorie
Volker Strassen
Strassen-Algorithmus
Solovay-Strassen-Test
Additionskette
Binäre Exponentiation
Russische Bauernmultiplikation
Determinante
Permanente
Permutation
Permutationsmatrix
Zyklische Permutation -> Vertauschung oder Transposition
Vorzeichen (Permutation)
Woche 10
Wikipedia
Komplexitätstheorie
Automat (Informatik)
Landau-Symbole
Konjunktive Normalform
Woche 13
Tutorial
Aussagen und Logik (dann folgt)
Wikipedia
Karps 21 NP-vollständige Probleme
Disjunktionsterm / Klausel
Literal, (Wahrheitswerte: true, false)
Clique (Graphentheorie)
Cliquenproblem
Knotenüberdeckung
Knotenüberdeckungsproblem
Erfüllbarkeitsproblem der Aussagenlogik (SAT)
3-SAT
Teilsummenproblem (subset sum problem)
YouTube
Komplexität #05 – Polyzeit-Reduktionen
16. Complexity: P, NP, NP-completeness, Reductions
Reductions – Intro to Theoretical Computer Science
Polynomialzeit-Reduktion
Vertex Cover (Knotenüberdeckung)
CSC 333 Reductions from Ham Cycle to TSP and from Vertex Cover to Dominating Set
NP Completeness for Dummies: Reduction of NP Complete Problems
Reductions and NP-Complete Proofs (CS) (Karp Reduction)
YouTube
Leibnizformel für Determinanten
Zyklendarstellung von Permutationen
Die Chomsky-Hierarchie
Theoretische Informatik, Karsten Morisse (Playlist)
TI_6_6 TM: akzeptieren und entscheiden, Karsten Morisse
Theoretische Informatik – Kontextsensitive Sprachen
Graphen, Grammatiken und Automaten, The Morpheus Tutorials (Playlist)
Theoretische Informatik (Wintersemester 2013/2014), Weitz / HAW Hamburg
Tim Roughgarden on Theoretical Computer Science (Playlist)
Algorithms Live!
WilliamFiset Algorithms
Bücher / Books
Diskrete Mathematik erleben, Stephan Hußmann, Brigitte Lutz-Westphal, 2015
Fundamentals of Discrete Math for Computer Science, Tom Jenkyns, Ben Stephenson, 2018
Konkrete Mathematik (nicht nur) für Informatiker, Edmund Weitz, 2018
Konkrete Mathematik (nicht nur) für Informatiker (Playlist)
NLogSpace
Formale Sprachen
Berechenbarkeit
Komplexität
Entscheidbar, unentscheidbar, semi-entscheidbar?
Mathematik-Vorkurs – Universität des Saarlandes
Kapitel 1 – Sprachen
Kapitel 2.1 – Aussagenlogik
Kapitel 2.2 – Prädikatenlogik
Kapitel 3 – Schließen und Beweisen
Kapitel 4 – Mengen
Kapitel 5 – Relationen
Kapitel 6 – Induktion