Inhaltsverzeichnis
14 Beziehungen: Clique (Graphentheorie), FP (Komplexitätsklasse), Ingo Wegener, Knotenüberdeckung, Monte-Carlo-Algorithmus, NP (Komplexitätsklasse), NP-Äquivalenz, NP-Vollständigkeit, Problem, Reduktion (theoretische Informatik), Schwere und Vollständigkeit (theoretische Informatik), Stabile Menge, Suchverfahren, Wortproblem (Berechenbarkeitstheorie).
Clique (Graphentheorie)
Eine Clique bezeichnet in der Graphentheorie eine Teilmenge von Knoten in einem ungerichteten Graphen, bei der jedes Knotenpaar durch eine Kante verbunden ist.
Sehen Suchproblem und Clique (Graphentheorie)
FP (Komplexitätsklasse)
In der theoretischen Informatik, speziell der Komplexitätstheorie, beschreibt die Klasse FP die Menge aller Suchprobleme, die von einer deterministischen Turingmaschine in polynomieller Zeit gelöst werden können (englisch function polynomial time, daher auch die Abkürzung).
Sehen Suchproblem und FP (Komplexitätsklasse)
Ingo Wegener
Ingo Wegener (vollständiger Name Ingo Werner Wegener; * 4. Dezember 1950 in Bremen; † 27. November 2008 in Bielefeld) war ein deutscher Informatiker, der auf dem Gebiet der theoretischen Informatik arbeitete.
Sehen Suchproblem und Ingo Wegener
Knotenüberdeckung
Eine Knotenüberdeckung bezeichnet in der Graphentheorie eine Teilmenge der Knotenmenge eines Graphen, die von jeder Kante mindestens einen Endknoten enthält.
Sehen Suchproblem und Knotenüberdeckung
Monte-Carlo-Algorithmus
Monte-Carlo-Algorithmen sind randomisierte Algorithmen, die mit einer nichttrivial nach oben beschränkten Wahrscheinlichkeit ein falsches Ergebnis liefern.
Sehen Suchproblem und Monte-Carlo-Algorithmus
NP (Komplexitätsklasse)
In der Informatik bezeichnet NP (für nichtdeterministisch polynomielle Zeit) eine fundamentale Komplexitätsklasse aus dem Bereich der Komplexitätstheorie.
Sehen Suchproblem und NP (Komplexitätsklasse)
NP-Äquivalenz
NP-Äquivalenz ist ein Begriff aus der Komplexitätstheorie innerhalb der Informatik.
Sehen Suchproblem und NP-Äquivalenz
NP-Vollständigkeit
NP-schweren und NP-vollständigen Probleme. In der Informatik bezeichnet man ein Problem als NP-vollständig (vollständig für die Klasse der Probleme, die sich nichtdeterministisch in Polynomialzeit lösen lassen), wenn es zu den schwierigsten Problemen in der Klasse NP gehört, also sowohl in NP liegt als auch NP-schwer ist.
Sehen Suchproblem und NP-Vollständigkeit
Problem
Ein Problem („Vorsprung, Klippe, Hindernis; das, was vorgelegt wurde“) entsteht in einer Situation, in der ein oder mehrere Ziele erreicht werden müssen, wobei nicht unmittelbar sicher ist, welche Maßnahmen ergriffen oder welche Mittel eingesetzt werden müssen, um diese Ziele zu erreichen.
Sehen Suchproblem und Problem
Reduktion (theoretische Informatik)
Die Reduktion ist eine Methode der theoretischen Informatik, bei der ein Problem auf ein anderes zurückgeführt wird.
Sehen Suchproblem und Reduktion (theoretische Informatik)
Schwere und Vollständigkeit (theoretische Informatik)
In der theoretischen Informatik – insbesondere in der Berechenbarkeits- und der Komplexitätstheorie – bezeichnet die Schwere (Übersetzung von engl. hardness dt. „Schwierigkeit“) eines Problems dessen Eigenschaft, mindestens so schwierig lösbar zu sein wie alle Probleme einer betrachteten Klasse.
Sehen Suchproblem und Schwere und Vollständigkeit (theoretische Informatik)
Stabile Menge
Eine stabile Menge, unabhängige Menge oder Co-Clique ist in der Graphentheorie eine Teilmenge von Knoten eines Graphen, die zueinander nicht adjazent sind.
Sehen Suchproblem und Stabile Menge
Suchverfahren
Die Informatik bezeichnet mit Suchverfahren oder Suchalgorithmus einen Algorithmus, der in einem Suchraum nach Mustern oder Objekten mit bestimmten Eigenschaften sucht.
Sehen Suchproblem und Suchverfahren
Wortproblem (Berechenbarkeitstheorie)
Als Wortproblem einer formalen Sprache bezeichnet man in der Theoretischen Informatik das Entscheidungsproblem, zu einem gegebenen Wort festzustellen, ob dieses zur Sprache gehört oder nicht.