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 13

Wikipedia

Disjunktionsterm / Klausel
Literal, (Wahrheitswerte: true, false)
Cliquenproblem

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)
Theoretische Informatik – Kontextsensitive Sprachen
Graphen, Grammatiken und Automaten, The Morpheus Tutorials (Playlist)

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 *