FTP_TheoComp

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

Leave a Reply

Your email address will not be published. Required fields are marked *