Zeit- und Platzklassen - Versionsgeschichte

Css: /* Polynomielle Zeit */

2018-08-23T16:04:37Z

‎Polynomielle Zeit

2018-08-23T15:53:04Z

‎Polynomielle Zeit

2018-08-23T15:49:57Z

‎Polynomielle Zeit

2018-08-23T15:44:56Z

2018-08-17T13:24:54Z

‎Polynomielle Zeit

2018-08-16T12:41:22Z

2018-08-16T12:39:16Z

‎Polynomielle Zeit

2018-08-16T12:37:42Z

2018-08-16T12:30:19Z

2018-08-16T12:26:47Z

@@ Zeile 32: / Zeile 32: @@
 == Polynomielle Zeit ==
-Eine Sprache heiße '''polynomiell''', wenn es für ihr Entscheidungsproblem einen Algorithmus in ${\cal O}(p)$ für ein Polynom $p$ gibt. Die Klasse aller polynomiellen Sprachen wird mit $P$ bezeichnet. Es gilt $P = \bigcup\limits_{n\in\mathbb{N}} \operatorname{DSPACE}(x^n)$.
+Eine Sprache heiße '''polynomiell''', wenn es für ihr Entscheidungsproblem einen Algorithmus in ${\cal O}(p)$ für ein Polynom $p$ gibt. Die Klasse aller polynomiellen Sprachen wird mit $P$ bezeichnet. Es gilt $P = \bigcup\limits_{n\in\mathbb{N}} \operatorname{DTIME}(x^n)$.
 Während lineare Zeit zum Beispiel bei Einband- und Mehrbandturingmaschinen unterschiedlich ist, so gibt es doch zwischen allen Maschinenmodellen polynomielle Reduktionen, das heißt, $P$ ist dort invariant.
 [[Kategorie:TODO]]

← Nächstältere Version		Version vom 23. August 2018, 15:53 Uhr
Zeile 32:		Zeile 32:
	== Polynomielle Zeit ==		== Polynomielle Zeit ==

−	Eine Sprache heiße '''polynomiell''', wenn es für ihr Entscheidungsproblem einen Algorithmus in ${\cal O}(p)$ für ein Polynom $p$ gibt. Die Klasse aller polynomiellen Sprachen wird mit $P$ bezeichnet. Es gilt $P = \bigcup\limits_{n\in\mathbb{N}} \operatorname{DSPACE(~~x\mapsto~~ x^n)}$.	+	Eine Sprache heiße '''polynomiell''', wenn es für ihr Entscheidungsproblem einen Algorithmus in ${\cal O}(p)$ für ein Polynom $p$ gibt. Die Klasse aller polynomiellen Sprachen wird mit $P$ bezeichnet. Es gilt $P = \bigcup\limits_{n\in\mathbb{N}} \operatorname{DSPACE}(x^n)$.

@@ Zeile 32: / Zeile 32: @@
 == Polynomielle Zeit ==
-Eine Sprache heiße '''polynomiell''', wenn es für ihr Entscheidungsproblem einen Algorithmus in ${\cal O}(p)$ für ein Polynom $p$ gibt. Die Klasse aller polynomiellen Sprachen wird mit $P$ bezeichnet. Während lineare Zeit zum Beispiel bei Einband- und Mehrbandturingmaschinen unterschiedlich ist, so gibt es doch zwischen allen Maschinenmodellen polynomielle Reduktionen, das heißt, $P$ ist dort invariant.
+Eine Sprache heiße '''polynomiell''', wenn es für ihr Entscheidungsproblem einen Algorithmus in ${\cal O}(p)$ für ein Polynom $p$ gibt. Die Klasse aller polynomiellen Sprachen wird mit $P$ bezeichnet. Es gilt $P = \bigcup\limits_{n\in\mathbb{N}} \operatorname{DSPACE(x\mapsto x^n)}$.
 '''TODO'''
 [[Kategorie:TODO]]

← Nächstältere Version		Version vom 23. August 2018, 15:44 Uhr
Zeile 24:		Zeile 24:

	Umgekehrt kann man sich aber nun die interessantere Frage stellen, wie gut ein gegebenes Problem lösbar ist. Wir werden uns hier im Wesentlichen auf Entscheidungsprobleme beschränken. Eine '''Klasse''' von Problemen ist eine Menge von Sprachen; meistens betrachtet man Klassen, deren Probleme die gleiche Zeit- oder Platz-Komplexität haben.		Umgekehrt kann man sich aber nun die interessantere Frage stellen, wie gut ein gegebenes Problem lösbar ist. Wir werden uns hier im Wesentlichen auf Entscheidungsprobleme beschränken. Eine '''Klasse''' von Problemen ist eine Menge von Sprachen; meistens betrachtet man Klassen, deren Probleme die gleiche Zeit- oder Platz-Komplexität haben.
		+
		+	Mit $\operatorname{DTIME}(f)$ bezeichnet man die Menge der Probleme, die sich mit einer deterministischen Turingmaschine in ${\cal O}(f)$ schritten lösen lassen.
		+
		+	Mit $\operatorname{DSPACE}(f)$ bezeichnet man die Menge der Probleme, die sich mit einer deterministischen Turingmaschine unter Platzbedarf ${\cal O}(f)$ lösen lassen.
		+

	== Polynomielle Zeit ==		== Polynomielle Zeit ==

← Nächstältere Version		Version vom 17. August 2018, 13:24 Uhr
Zeile 28:		Zeile 28:

	Eine Sprache heiße '''polynomiell''', wenn es für ihr Entscheidungsproblem einen Algorithmus in ${\cal O}(p)$ für ein Polynom $p$ gibt. Die Klasse aller polynomiellen Sprachen wird mit $P$ bezeichnet. Während lineare Zeit zum Beispiel bei Einband- und Mehrbandturingmaschinen unterschiedlich ist, so gibt es doch zwischen allen Maschinenmodellen polynomielle Reduktionen, das heißt, $P$ ist dort invariant.		Eine Sprache heiße '''polynomiell''', wenn es für ihr Entscheidungsproblem einen Algorithmus in ${\cal O}(p)$ für ein Polynom $p$ gibt. Die Klasse aller polynomiellen Sprachen wird mit $P$ bezeichnet. Während lineare Zeit zum Beispiel bei Einband- und Mehrbandturingmaschinen unterschiedlich ist, so gibt es doch zwischen allen Maschinenmodellen polynomielle Reduktionen, das heißt, $P$ ist dort invariant.
		+
		+	'''TODO'''

	[[Kategorie:TODO]]		[[Kategorie:TODO]]

@@ Zeile 16: / Zeile 16: @@
 Wir wollen uns ein praktisches Beispiel anschauen: Das Sortieren von Listen.
 == Klassen ==
-Vielen Algorithmen sieht man ihre Komplexität direkt an, oder man kommt durch ein wenig Nachdenken darauf. Andererseits kann es zum selben Problem viele verschiedene Algorithmen mit unterschiedlichem Laufzeitverhalten geben.
+Vielen Algorithmen sieht man ihre Komplexität direkt an, oder man kommt durch ein wenig Nachdenken darauf. Andererseits kann es zum selben Problem viele verschiedene Algorithmen mit unterschiedlichem Laufzeitverhalten geben, wie wir beim Sortieren von Listen gesehen haben.
 == Polynomielle Zeit ==

@@ Zeile 2: / Zeile 2: @@
 Weiterhin betrachtet man üblicherweise nicht die absolute Zeit bzw. den absoluten Platz, den ein Algorithmus braucht, sondern dessen '''Asymptotik''', die man üblicherweise in Landau-Notation angibt. Der Grund ist, dass es verschiedene Maschinenmodelle gibt, aber die Asymptotik in den meisten realisierbaren Maschinenmodellen gleich ist (wir lassen an der Stelle mal Quantencomputer außen vor).
 Wir sagen, ein Algorithmus $A(x)$ hat die (Zeit-)Komplexität ${\cal O}(f)$, oder meistens einfach "ist ${\cal O}(f)$", wenn es eine Funktion $g$ gibt, sodass die Zeit, die $A(x)$ braucht, höchstens $g(|x|)$ Schritte sind, wobei $|x|$ die Länge von $x$ ist, sodass $g\in{\cal O}(f)$.
@@ Zeile 10: / Zeile 12: @@
 Es ist auf jeden Fall bei solchen Angaben immer wichtig, zu wissen, was genau gemeint ist, sonst kann es schnell zu Missverständnissen kommen.
 == Polynomielle Zeit ==

← Nächstältere Version		Version vom 16. August 2018, 12:26 Uhr
Zeile 4:		Zeile 4:

	Wir sagen, ein Algorithmus $A(x)$ hat die (Zeit-)Komplexität ${\cal O}(f)$, oder meistens einfach "ist ${\cal O}(f)$", wenn es eine Funktion $g$ gibt, sodass die Zeit, die $A(x)$ braucht, höchstens $g(\|x\|)$ Schritte sind, wobei $\|x\|$ die Länge von $x$ ist, sodass $g\in{\cal O}(f)$.		Wir sagen, ein Algorithmus $A(x)$ hat die (Zeit-)Komplexität ${\cal O}(f)$, oder meistens einfach "ist ${\cal O}(f)$", wenn es eine Funktion $g$ gibt, sodass die Zeit, die $A(x)$ braucht, höchstens $g(\|x\|)$ Schritte sind, wobei $\|x\|$ die Länge von $x$ ist, sodass $g\in{\cal O}(f)$.
		+
		+	Oft schreibt man auch explizit hin, in Abhängigkeit von was genau die Klasse ist, also in unserem Fall ${\cal O}(f(\|x\|))$. Meistens redet man aber über Probleme mit nur einer Eingabe, und dann ist üblicherweise die Länge der Eingabe gemeint.
		+
		+	Ist die Eingabe eine Zahl, dann meint man normalerweise deren Länge in einem Stellenwertsystem, zum Beispiel dem Dezimalsystem.
		+
		+	Es ist auf jeden Fall bei solchen Angaben immer wichtig, zu wissen, was genau gemeint ist, sonst kann es schnell zu Missverständnissen kommen.

	== Polynomielle Zeit ==		== Polynomielle Zeit ==