18 Beziehungen: Determinismus (Algorithmus), Englische Sprache, Entscheidbar, Erreichbarkeitsproblem in Graphen, Komplexitätsklasse, Komplexitätstheorie, Logarithmisch platzbeschränkte Reduktion, Logarithmus, Mengenlehre, NC (Komplexitätsklasse), NL (Komplexitätsklasse), NP (Komplexitätsklasse), P (Komplexitätsklasse), Planarer Graph, Platzkomplexität, PSPACE, Turingmaschine, 2004.
Determinismus (Algorithmus)
Ein deterministischer Algorithmus ist ein Algorithmus, bei dem nur definierte und reproduzierbare Zustände auftreten.
Neu!!: L (Komplexitätsklasse) und Determinismus (Algorithmus) · Mehr sehen »
Englische Sprache
Die englische Sprache (Eigenbezeichnung: IPA) ist eine ursprünglich in England beheimatete germanische Sprache, die zum westgermanischen Zweig gehört.
Neu!!: L (Komplexitätsklasse) und Englische Sprache · Mehr sehen »
Entscheidbar
In der theoretischen Informatik heißt eine Eigenschaft auf einer Menge entscheidbar (auch rekursiv, rekursiv ableitbar), wenn es ein Entscheidungsverfahren für sie gibt.
Neu!!: L (Komplexitätsklasse) und Entscheidbar · Mehr sehen »
Erreichbarkeitsproblem in Graphen
Das Erreichbarkeitsproblem in Graphen (auch STCON bzw. USTCON, GAP, PATH oder REACH) behandelt die Frage, ob es in einem Graphen einen Weg von einem Knoten s zu einem Knoten t gibt.
Neu!!: L (Komplexitätsklasse) und Erreichbarkeitsproblem in Graphen · Mehr sehen »
Komplexitätsklasse
Komplexitätsklassen In der Komplexitätstheorie werden Probleme oder Algorithmen darauf untersucht, wie aufwendig sie zu berechnen sind bezüglich einer bestimmten Ressource, meist bezüglich des Zeitaufwands oder des (Speicher-)Platzaufwands.
Neu!!: L (Komplexitätsklasse) und Komplexitätsklasse · Mehr sehen »
Komplexitätstheorie
Die Komplexitätstheorie als Teilgebiet der theoretischen Informatik befasst sich mit der Komplexität algorithmisch behandelbarer Probleme auf verschiedenen formalen Rechnermodellen.
Neu!!: L (Komplexitätsklasse) und Komplexitätstheorie · Mehr sehen »
Logarithmisch platzbeschränkte Reduktion
Eine logarithmisch platzbeschränkte Reduktion (auch als logarithmische Reduktion bezeichnet) ist eine spezielle Form der Reduktion.
Neu!!: L (Komplexitätsklasse) und Logarithmisch platzbeschränkte Reduktion · Mehr sehen »
Logarithmus
Logarithmische Skaleneinteilung eines Rechenschiebers (Detail) e (rot) und 1/2 (blau) Logarithmus zur Basis 10. Als Logarithmus (Plural: Logarithmen; von, „Verständnis, Lehre, Verhältnis“, und ἀριθμός, arithmós, „Zahl“) einer Zahl bezeichnet man den Exponenten, mit dem eine vorher festgelegte Zahl, die Basis, potenziert werden muss, um die gegebene Zahl, den Numerus, zu erhalten.
Neu!!: L (Komplexitätsklasse) und Logarithmus · Mehr sehen »
Mengenlehre
Die Mengenlehre ist ein grundlegendes Teilgebiet der Mathematik, das sich mit der Untersuchung von Mengen, also von Zusammenfassungen von Objekten, beschäftigt.
Neu!!: L (Komplexitätsklasse) und Mengenlehre · Mehr sehen »
NC (Komplexitätsklasse)
NC steht in der Informatik als Abkürzung für Nick's Class (nach Nick Pippenger), die Komplexitätsklasse der parallel effizient lösbaren Entscheidungsprobleme.
Neu!!: L (Komplexitätsklasse) und NC (Komplexitätsklasse) · Mehr sehen »
NL (Komplexitätsklasse)
In der Komplexitätstheorie bezeichnet NL (für nichtdeterministisch logarithmischer Platz) die Klasse der Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine auf logarithmischem Platz gelöst werden können.
Neu!!: L (Komplexitätsklasse) und NL (Komplexitätsklasse) · Mehr sehen »
NP (Komplexitätsklasse)
In der Informatik bezeichnet NP (für nichtdeterministisch polynomielle Zeit) eine fundamentale Komplexitätsklasse aus dem Bereich der Komplexitätstheorie.
Neu!!: L (Komplexitätsklasse) und NP (Komplexitätsklasse) · Mehr sehen »
P (Komplexitätsklasse)
In der Komplexitätstheorie ist P (auch: PTIME) diejenige Komplexitätsklasse, die alle Entscheidungsprobleme enthält, die in Polynomialzeit für deterministische Turingmaschinen lösbar sind.
Neu!!: L (Komplexitätsklasse) und P (Komplexitätsklasse) · Mehr sehen »
Planarer Graph
Planare Zeichnung des K_4 Ein planarer oder plättbarer Graph ist in der Graphentheorie ein Graph, der auf einer Ebene, mit Punkten für die Knoten und Linien für die Kanten, dargestellt werden kann, sodass sich keine Kanten schneiden.
Neu!!: L (Komplexitätsklasse) und Planarer Graph · Mehr sehen »
Platzkomplexität
Unter der Platzkomplexität eines Problems versteht man den (minimalen) Bedarf an Speicherplatz eines Algorithmus zur Lösung dieses Problems, in Abhängigkeit von der Länge der Eingabe.
Neu!!: L (Komplexitätsklasse) und Platzkomplexität · Mehr sehen »
PSPACE
In der Komplexitätstheorie bezeichnet PSPACE die Klasse der Entscheidungsprobleme, die von deterministischen Turingmaschinen mit polynomiellem Platz entschieden werden können.
Neu!!: L (Komplexitätsklasse) und PSPACE · Mehr sehen »
Turingmaschine
Eine Turingmaschine ist ein mathematisches Modell der theoretischen Informatik, das eine abstrakte Maschine definiert.
Neu!!: L (Komplexitätsklasse) und Turingmaschine · Mehr sehen »
2004
Keine Beschreibung.
Neu!!: L (Komplexitätsklasse) und 2004 · Mehr sehen »