Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algorithmen und Komplexitaet - Coggle Diagram
Algorithmen und Komplexitaet
Berechenbarkeitstheorie
Entscheidbarkeit
Unterschiedliche Formen der Entscheidbarkeit
Unentscheidbar
Unentscheidbare Probleme
Post'sche Korrespondenz Problem
Halteproblem
Auf leere Eingabe
Auf bestimmtes Wort
Rice's Theorem: non-trivial property
Entscheidbar
Semi-entscheidbar
Definitionen
Turing-Akzeptanz
Turing-Aequivalenz
Modelle
Turingmaschinen
Varianten
Mehrspur-TMs
Mehrband-TMs
Einseitig-begrenzte TM
Nicht-deterministische TM
Linear-begrenzte TM
Kodierung
Goedelnummer
Loop Computability
While Computability
Registermaschinen
Goto Computability
Lambda-Kalkuel
Rekursive Funktionen
Intuitive Berechenbarkeit
Reduktionen
Varianten
Many-to-one (Eingabewort)
Polynomiale Reduktion
Reduktionstheorem
L unentscheidbar bedeutet, dass L' ebenfalls unentscheidbar ist
Komplexitaetstheorie
O-Notation
Big-O
Small-O
Big-Omega
Small-Omega
Big-Theta
Komplexitaetsklassen
P
NP
TIME
PTIME
NTIME
EXPTIME
NEXPTIME
SPACE
PSPACE
NPSPACE
EXPSPACE
NEXPSPACE
DEC
RE
Zeitkomplexitaet
time-constructible function
Raumkomplexitaet
space-constructible function
Definitionen
NP-vollstaendig
NP-hart
NP-Vollstaendige Probleme
Boolean Satisfiability Problem
SAT
3SAT
Defintionen
Literal
Clause
CNF (Konjunktive Normalform)
CLIQUE
HAMILTON
BIN PACKING
Knapsack
SELECT
Traveling Salesman
PARTITION
Minimum Vertex Cover
MAX-CUT
Algorithmendesign
Probleme
Entscheidungsproblem
Optimisierungsproblem
Konzepte
Systematische Suche
Backtracking
Greedy Algorithms
Approximationsalgorithmen
Randomisierung
Specific Algorithms
BFS
IDDFS
DFS
Design techniques
Dynamic Programming
Branch and Bound
Local Search
Simulated Annealing