Theoretischen_informatik
- Graphentheorie
- Selectionsort
- Radixsort
- Quicksort
- Bucketsort
- Mergesort
- Insertionsort
- Bubblesort
- Algorithmus von Dijkstra
- Algorithmus von Bellman und Ford
- Algorithmus Topo-Sortierung
- Binäre Suche
- Verstärkungslemma
- Traveling Salesman Problem
- Quantencomputer
- Polynomialzeitreduktion
- Median-Algorithmus
- Güte von Approximationsalgorithm
- Junktor
- Boolesche Funktion
- Strukturelle Induktion
- Aussagenlogischen Formel
- Erfüllbarkeitsproblem für quantifizierte boolesche Formeln
- Boolescher Wert
- aussagenlogische Variable
- Big O
- Simons-Problem
- Simons-Algorithmus
- Optimalitätsprinzip von Bellman
- Verifizierer
- Teilsummenproblem
- SPACE
- small o
- Satz von Cook und Levin
- Satz von Savitch
- Satz SUBSET-SUM is NP-vollständig
- Satz STCON is NL-vollständig
- Satz STCON ist in P
- Satz RELPRIME ist in P
- Satz PSPACE Teilmenge von EXPTIME
- Satz PSPACE gleich NPSPACE
- Satz P Teilmenge von PSPACE
- Satz NP-vollständig durch Reduktion von NP-vollständig
- Satz NP gdw. NDTM
- Satz Laufzeit zusätzlicher Bänder
- Satz Hamiltonwegproblem ist in NP
- Satz Laufzeit Determinisierung von Nichtdeterminismus
- Satz Hamiltonwegproblem ist in EXPTIME
- Satz Falls B NP-vollständig und B in P dann P gleich NP
- Satz Falls SAT in P dann P gleich NP
- Satz CLIQUE is NP-vollständig
- Satz EQ-ROBP in BPP
- Satz 3SAT ist NP-vollständig
- Satz 3SAT is poly reduzierbar auf CLIQUE
- RELPRIME
- Reduktion
- Rekursionsgleichung
- Randomisierte polynomielle Zeit
- PSPACE
- PSPACE-Vollständigkeit
- Problem der exakten Überdeckung
- Problem der Äquivalenz zweier ROBP
- Probabilistische Entscheidbarkeit
- Polynomieller Verifizierer
- Primzahltest
- Polynomialzeit berechenbare Funktion
- Polynomialzeit
- Platzkomplexität
- Null-Fehler probabilistische polynomielle Zeit
- P versus NP
- NTIME
- NSPACE
- NPSPACE
- NP-Schwer
- NP-Vollständigkeit
- nichtdeterministische Polynomialzeit
- NL-Vollständigkeit
- nichtdeterministisch polynomielle Zeit
- Landau-Symbole
- Komplexitätsklasse
- Färbungsproblem
- Faktorisierungsproblem
- Erfüllbarkeitsproblem der Aussagenlogik
- Entscheidungsproblem
- coRP
- deterministisch polynomielle Zeit
- coNP
- beschränkte Fehlerwahrscheinlichkeit probabilistische polynomielle Zeit
- Vervollständigte Entfernungsmatrix
- TIME
- Multigraph
- k-Färbung
- Hamiltonwegproblem
- Hamiltonkreisproblem
- Eulerkreis
- Sprache
- Vereinigung von regulären Sprachen
- Regulärer Ausdruck
- Reguläre Sprache
- Buchstaben
- Äquivalenz DEA, NEA und Reg
- Alphabet
- Abschlusseigenschaften der regulären Sprachen
- Turingmaschine
- Reguläre Urbildmengen
- Mehrband-Turingmaschine
- Nichtdeterministische Turingmaschine
- Lemma des linear beschränkten Längenwachstum
- Deterministische Turingmaschine
- Lemma des linear beschränkten Abstandswachstum
- Berechnung
- Berechenbare Funktion
- Satz Redundanz zusätzlicher Bänder
- Satz Redundanz von Nichtdeterminismus
- Satz Anzahl der Konfigurationen eines LBTM
- Probabilistische Turingmaschine
- Potenzmengenkonstruktion
- Linear beschränkte Turingmaschine
- Konfiguration einer TM
- epsilon-Hülle
- Endlicher Automat
- Deterministischer endlicher Automat
- Elimination von epsilon-Kanten
- Automatentheorie
- Äquivalente Automaten
- Sortierverfahren
- Datenstruktur
- Dynamische Programmierung
- Baum