Premium Partner

Berechenbarkeit und Komplexität

Berechenbarkeit und Komplexität für Informatiker

Berechenbarkeit und Komplexität für Informatiker


Set of flashcards Details

Flashcards 76
Language Deutsch
Category Computer Science
Level University
Created / Updated 07.02.2015 / 18.01.2022
Licencing Attribution (CC BY)    (Okko)
Weblink
https://card2brain.ch/box/berechenbarkeit_und_komplexitaet_
Embed
<iframe src="https://card2brain.ch/box/berechenbarkeit_und_komplexitaet_/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>

Was sind Platzschranken?

Eine nichtdeterministische Maschine mit Platzschranke  \(f: \mathbb{N} \rightarrow \mathbb{N}\) besitzt keinen Algorithmus, die auf Eingabe der Länge \(n \geq 0\) mehr als \(f(n)\) Felder des Bandes benutzt. Für alle Platzschranken gilt \(f \in \Omega(log(n))\)

 

 

Was sind Zeitschranken?

Eine nichtdeterministische Maschine mit Zeitschranke \(f: \mathbb{N} \rightarrow \mathbb{N}\) besitzt keinen Algorithmus, die auf Eingabe der Länge \(n \geq 0\)mehr als \(f(n)\) Rechenschritte machen kann, bevor das Band hält. Es sind auch \(n+1\) Zeitschritte erlaubt, um zu erkennen, wann das Band endet

Welche Platzklassen gibt es?

\(\textbf{DSPACE}(f)\) und \(\textbf{NSPACE}(f)\) für \(f \in \Omega(log(n))\)

Welche Zeitklassen gibt es?

\(\textbf{DTIME}(f) \) und \(\textbf{NTIME}(f) \) für \(f(n) \geq n \ ; \forall n\)

\(\underline{\textbf{DTIME(t)}}\)

\(L \subseteq \Sigma^*\)| es existiert eine determenistische Turingmaschine \(M\) mit \(L=L(M)\), die auf allen Eingaben der Länge \(n\) nach höchstens \(max \{ t(n),n+1 \}\)Schritten hält. 

\(\underline{\textbf{NTIME(t)}}\)

 

\(L \subseteq \Sigma^*\)| es existiert eine determenistische Turingmaschine \(M\) mit \(L=L(M)\), die auf allen Eingaben der Länge \(n\) und bei allen Rechnungen nach höchstens \(max \{ t(n),n+1 \}\)Schritten hält. 

\(\underline{\textbf{DSPACE(s)}}\)

\(L \subseteq \Sigma^*\)| es existiert eine determenistische Turingmaschine \(M \)mit \(L=L(M)\), die auf allen Eingaben der Länge \(n\) höchstens \(s(n)\) Arbeitsbandfelder benötigt.

\(\underline{\textbf{NSPACE(s)}}\)

 

\(L \subseteq \Sigma^*\)| es existiert eine determenistische Turingmaschine \(M \)mit \(L=L(M)\), die auf allen Eingaben der Länge \(n\) bei allen Rechnungen höchstens \(s(n)\) Arbeitsbandfelder benötigt.