Informatik

• Deutsch-Jozsa Algorithm
• Negation der Pumpingeigenschaft
• Algorithmus
• Formelspiel
• Turingreduktion
• Satz Turingreduktion ist transitiv
• Satz Turingreduktion ist reflexiv
• Folgerungsbeziehungsproblem der Prädikatenlogik
• Erfüllbarkeitsproblem der Prädikatenlogik
• Formale Sprachen
• Erfüllbarkeitsproblem der Aussagenlogik
• Satz Halteproblem für Turingmaschinen ist unentscheidbar
• Beispiel KFG aus if-else Kellerautomat
• Universale Sprache
• nicht-triviale semantische Eigenschaft
• Satz von Friedberg und Muchnik
• Erkannte Sprache einer TM
• Polynomialzeitreduktion
• Log-Raum-Reduktion
• Satz Auf entscheidbare Sprache Turing-reduzierbare Sprache ist entscheidbar
• Reduktion
• Komplement einer Sprache
• Satz Jede Sprache ist Turing-reduzierbar zu ihrem Komplement
• Satz Jede Sprache ist einseitig Turing-reduzierbar zu ihrem Jump
• Jump
• Satz Allgemeine Wortproblem für Turingmaschinen ist unentscheidbar
• Allgemeines Wortproblem für Turingmaschinen
• Satz epsilon-Halteproblem für Turingmaschinen ist unentscheidbar
• epsilon-Halteproblem für Turingmaschinen
• Halteproblem für Turingmaschinen
• Halteproblem
• Satz von Rice
• Theorie der Programmiersprachen
• Satz von Kleene und Post
• Einseitige Turingreduktion
• Leere Sprache
• Anwendung Pumpinglemma für Kontextfreie Sprachen
• Pumpinglemma für Kontextfreie Sprachen
• Satz Größe eines Syntaxbaum
• Pumpingeigenschaft für Kontextfreie Sprachen
• Pumpinglemma für reguläre Sprachen
• Satz Jede reguläre Sprache wird von DKA erkannt
• Erweiterte Folgekonfiguration eines Kellerautomaten
• Durch leeren Keller erkannte Sprache eines NDKA
• Durch Endzustand erkannte Sprache eines NDKA
• Deterministischer Kellerautomat
• Satz Umwandlung NDKA in äquivalenter KFG
• Sprache IfElse
• Satz Umwandlung KFG in äquivalenter NDKA
• Nichtdeterministischer Kellerautomat
• Ableitung in Satzform
• Satz durch Endzustand und durch leeren Keller erkannt ist äquivalent
• Kontextfreie Sprache
• Automatentheorie
• Satz NDKA von Endzustand zu äquivalenten leeren Kelller
• Satz NDKA von leeren Keller zu äquivalenten Endzustand
• Satz NDKA erkennt w-w-reversed
• Berechnung eines NDKA
• Erkannte Sprache eines NDKA
• Satz ungelese Eingabe und unbenutzer Speicher beeinflusst Erweiterte Folgekonfiguration nicht
• Folgekonfiguration eines Kellerautomaten
• Konfiguration eines Kellerautomaten
• Sprache Palindrom
• Kellerspeicher
• Datenstruktur
• Kontextfreie Grammatik
• Ableitung mit Produktionsregeln
• Mehrdeutige Kontextfreie Grammatik
• Eindeutige Kontextfreie Grammatik
• Satz Syntaxbaum, erweiterte Ableitung und rekursive Inferenz sind äquivalent
• erweiterte Ableitung
• Syntaxbaum
• Ertrag eines Syntaxbaums
• Rekursive Inferenz
• Satz Jede reguläre Sprache ist auch kontextfrei
• WortKFG-Algorithmus
• Produzierte Sprache einer kontextfreien Grammatik
• Produkt einer kontextfreien Grammatik
• Minimaler DEA
• Satz NEA zu regulärer Ausdruck
• Zustand aus einem GNEA entfernen
• Urbilder regulärer Sprachen
• Berechnung eines GNEA
• Berechnung eines NEA
• Generalisierter nichtdeterministischer endlicher Automat
• Nichtdeterministischer endlicher Automat
• Regulärer Ausdruck
• Satz Kleene Hülle eines NEAs
• Satz Konkatenation zweier NEAs
• Satz Vereinigung zweier NEAs
• Universelle Turingmaschine
• Satz Komplement von Allgemeine Wortproblem ist nicht erkennbar
• Satz Allgemeine Wortproblem ist erkennbar
• Rucksackproblem
• Satz SUBSET-SUM is NP-vollständig
• Entscheidungsproblem
• Kodierung einer TM
• Abschlusseigenschaften der regulären Sprachen
• Satz Regulärer Ausdruck zu NEA
• Satz DEA zu NEA
• Satz Korrektheit Potenzmengenkonstruktion ohne epsilon-Kanten
• epsilon-Eliminierung
• epsilon-Pfad
• Epsilon-Kante
• Potenzmengenkonstruktion
• w-Pfad
• epsilon-Hülle
• Satz reverse ist nicht sequentiell
• Funktion reverse
• Abstand
• Sequenzielle Funktion
• Satz raise ist nicht sequentiell
• Funktion raise
• Berechenbare Funktion
• Pumpingeigenschaft
• Sprache
• Reguläre Sprache
• Erkannte Sprache eines DEA
• Berechnung eines DEA
• Berechnung
• Berechnung einer TM
• Satz TQBF ist PSPACE-vollständig
• Erfüllbarkeitsproblem für quantifizierte boolesche Formeln
• Informatik
• Satz Anzahl der Konfigurationen eines LBTM
• Satz EQ-ROBP in BPP
• Satz NL teil von P
• Komplexitätsklasse
• Komplexitätstheorie
• Satz FORMULA-GAME ist PSPACE-vollständig
• Problem E gewinnt Formelspiel
• Gewinnstrategie
• Spiele
• Satz 3SAT ist NP-vollständig
• Satz 3SAT is poly reduzierbar auf CLIQUE
• nichtdeterministisch polynomielle Zeit
• Satz Redundanz zusätzlicher Bänder
• Binäres Entscheidungsdiagramm
• LSPACE
• minimale Knotenüberdeckung
• deterministisch polynomielle Zeit mit Orakel-TM
• Orakel-Turingmaschine
• Orakel
• Problem der Äquivalenz zweier Regulärer Ausdrücke mit Potenzierung
• Reguläre Sprache mit Potenzierung
• Problem der Äquivalenz zweier Regulärer Ausdrücke
• EXPSPACE-Vollständigkeit
• PSPACE-Vollständigkeit
• PSPACE
• deterministisch polynomielle Zeit
• EXPTIME
• EXPSPACE
• Satz PSPACE Teilmenge von EXPTIME
• Raumhierarchiesatz
• Zeitkonstruierbare Funktion
• Hierarchiesätze
• Satz TQBF ist nicht NL
• Satz NL ist eine echte Teilmenge von PSPACE
• Raumkonstruierbare Funktion
• Satz coPATH is in NL
• Unerreichbarkeitsproblem in Graphen
• Erreichbarkeitsproblem in Graphen
• Satz PATH is NL-vollständig
• Satz PATH ist in P
• NLSPACE
• coNL
• coNP
• Nur-Lesen Eingabeband Turingmaschine
• Satz Falls B in L und A log-raum reduzierbar auf B dann A in L
• Satz NP-vollständig durch Reduktion von NP-vollständig
• NL-Vollständigkeit
• NP-Schwer
• NL-Schwere
• Logarithmische Platzkomplexität berechenbare Funktion
• log space transducer
• Satz Anzahl der Konfiguration einer ROITM
• Satz von Savitch
• Satz Anzahl der Konfiguration einer TM
• Satz 0^k1^k ist L
• Sprache 0^k1^k
• Satz von Cook und Levin
• Maximum flow problem
• Graphentheorie
• Problem der Äquivalenz zweier ROBP
• Problem der exakten Überdeckung
• Satz RELPRIME ist in P
• Hamiltonkreisproblem
• Verifizierer
• Satz Flusswert bei Quelle und Senke gleich
• Flusswert
• Flusserhalt
• s-t-Fluss
• Kapazitätskonformität
• Netzwerk
• Fluss
• Ausgangsgrad
• Eingangsgrad
• Ausgangskanten
• Eingangskanten
• Optimierung
• Lineare Optimierung
• Tutte-Berge Formel
• Alternierender Kantenzug
• Flower (Graphentheorie)
• Gewichtetes Matching-Problem
• Maximum Kardinalität Matching-Problem
• Maximal Matching
• Heiratssatz
• Satz von König (Graphentheorie)
• Maximum Matching
• Matching (Graphentheorie)
• R-Baum
• Sortierverfahren
• Quicksort
• Algorithmus Topo-Sortierung
• Breitensuche
• Tiefensuche
• Augmentierender Kantenzug
• Blossom algorithm
• Satz augmentierender Kantenzug unmatched weg bipartite
• Maximum matching no augmenting path theorem
• Knotenüberdeckung
• Inzidenz
• Big Data is dead
• Global distribution system
• Selectionsort
• Radixsort
• Bucketsort
• Mergesort
• Insertionsort
• Bubblesort
• Algorithmus von Prim
• Algorithmus von Kruskal
• Algorithmus von Dijkstra
• Algorithmus von Bellman und Ford
• Binäre Suche
• Algorithmus von Boruvka und Sollin
• Verstärkungslemma
• Rekursion
• Traveling Salesman Problem
• Quantencomputer
• Nichtdeterminismus
• Median-Algorithmus
• Güte von Approximationsalgorithm
• Grover-Algorithmus
• Algorithmus von Sahni
• Algorithmen und Datenstrukturen
• Qubit
• Zeitkomplexität
• Taxonomie der Lokalisationsprobleme
• Robotik
• Roboterlokalisation
• Markovlokalisation
• Rokos basilisk
• gamification
• Determinismus
• Divide-and-Conquer
• Verantwortung
• Value-based Engineering
• Ethisches Designdokument
• Ethischen Fallanalyse
• Das Prinzip Verantwortung
• k-adische Darstellung
• EKF Lokalisation
• Entropiefunktion
• Ganzzahlige lineare Optimierung
• Point-set registration
• Fraktal
• Boolesche Funktion
• Bipartition
• Big O
• Akkumulatortechnik
• Simons-Problem
• Shor-Algorithmus
• Simons-Algorithmus
• Qureg
• Quantum state transformation
• Quantum coin flip algorithm
• Periodische Funktion
• Hadamard transformation
• Oracle (Quantum)
• Topologische Sortierung
• Speicher
• Softwarelizenz
• Optimalitätsprinzip von Bellman
• Programm
• Gesellschaft für Informatik
• Ethik in der Informatik
• Maschinelles Lernen
• unique function
• Teilsummenproblem
• SPACE
• small o
• Satz PSPACE gleich NPSPACE
• Satz P Teilmenge von PSPACE
• 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
• RELPRIME
• Rekursionsgleichung
• Randomisierte polynomielle Zeit
• Probabilistische Entscheidbarkeit
• Polynomieller Verifizierer
• Primzahltest
• Polynomialzeit berechenbare Funktion
• Polynomialzeit
• Platzkomplexität
• Null-Fehler probabilistische polynomielle Zeit
• P versus NP
• NTIME
• NSPACE
• NPSPACE
• NP-Vollständigkeit
• nichtdeterministische Polynomialzeit
• Kürzeste Wegeproblem
• Landau-Symbole
• Färbungsproblem
• Faktorisierungsproblem
• coRP
• 3SAT
• beschränkte Fehlerwahrscheinlichkeit probabilistische polynomielle Zeit
• 3-dimensional matching
• supply paradox of AI
• Gefahr von KI
• Data Mining
• Apriori-Algorithmus
• Zyklus
• Zwischenzentralität
• Zusammenhang
• Wald
• Weg
• Vervollständigte Entfernungsmatrix
• Vollständiger Graph
• Transponierter Graph
• TIME
• Spannbaum
• Teilgraph
• Senke
• Quelle
• Perfekt Matching
• Multigraph
• Matching Augmentation Lemma
• Knotenüberdeckungszahl
• Knotengrad
• Knoten
• Kante
• Kantenzug
• k-Färbung
• Hamiltonzyklus
• Hamiltonwegproblem
• Hamiltonweg
• Graph
• Gerichteter Kantenzug
• Eulerkreis
• Einfacher Kantenzug
• Clique
• Bipartiter Graph
• Alternierender Wald 1
• Alternierender Wald
• Adjazenzmatrix
• Alternierender Baum
• Adjazenzliste
• Vereinigung von regulären Sprachen
• Äquivalenz DEA, NEA und Reg
• Datenbanksysteme
• Data Science
• Speicherverwaltung
• Prozess
• Betriebssysteme
• Adressabbildung
• Turingmaschine
• Mehrband-Turingmaschine
• Nichtdeterministische Turingmaschine
• Deterministische Turingmaschine
• Satz Redundanz von Nichtdeterminismus
• Probabilistische Turingmaschine
• Linear beschränkte Turingmaschine
• Äquivalente Automaten
• Voxelgitter
• Verlustfreie Kartenkompression
• Suchbaum
• Punktwolke
• Minimalen Spannbaum
• Lies-einmal Binäres Entscheidungsdiagramm
• Liste
• Dynamische Programmierung
• Bikette
• Binäre Baum
• Baum
• Balancierter Baum
• Backtracking
• B-Baum
• B+-Baum