Berechenbarkeit und Komplexität
Berechenbarkeit und Komplexität für Informatiker
Berechenbarkeit und Komplexität für Informatiker
Fichier Détails
| Cartes-fiches | 76 |
|---|---|
| Langue | Deutsch |
| Catégorie | Informatique |
| Niveau | Université |
| Crée / Actualisé | 07.02.2015 / 18.01.2022 |
| Lien de web |
https://card2brain.ch/box/berechenbarkeit_und_komplexitaet_
|
| Intégrer |
<iframe src="https://card2brain.ch/box/berechenbarkeit_und_komplexitaet_/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
\(\underline{\textit{Satz von Rice}}\)
Sei \(R\) die Klasse aller Turing-berechenbaren Sprachen. Sei \(\emptyset \neq S \subsetneq R\) eine beliebige echte Teilmenge. Dann ist die Sprache \(C(S)=\{ w \ \vert \ L(M_w) \in S \} \) unentscheidbar.
Praktisch: die Frage nach einer nicht-trivialen Eigenschaft einer Turingmaschine ist unentscheidbar. Eine nicht-trivial Eigenschaft ist hierbei eine Eigenschaft die für alle Turingmaschinen, unabhängig von ihrer Implementierung, gelten muss. Also eine Eigenschaft der Sprache und nicht der Turingmaschine selbst.
\(\underline{\textit{Gödelsches Prädikat}}\)
Für jede Zahlen \((n_0, ...,n_k)\)gibt es \(a\) und \(b\), so dass für \(i=0...k\) gilt:
\(n_i=a \ MOD \ (1+(i+1) \cdot b)\)
Gleichwertig zu \(\beta(a,b,i,n_i)\)ist wahr.
\(\underline{\textit{Entscheidbare und semientscheidbare Sprachen}}\)
Eine NTM \(M\) hält bei einer Eingabe \(x\), falls alle Rechnungen von \(M(x)\) eine endliche Länge haben.
Eine NTM \(M\) entscheidet eine Eingabe \(x\) falls \(M(x)\) hält oder eine Konfiguration mit einem Endzustand erreichen kann.
Eine Sprache \(L \subseteq \Sigma^*\) heißt entscheidbar, falls eine DTM \(M\) mit \(L(M)=L\) existiert, die jede Eingabe \(x \in \Sigma^*\) entscheidet.
Jede von einer DTM \(M\) erkannte Sprache heißt semientscheidbar.
Die von \(M\) akzeptierte Sprache \(L(M)\) heißt semientscheidbar, da \(M\) zwar alle Eingabe \(x \in L\) entscheidet, aber eventuell nicht alle \(x \in \bar{L}\)(Komplement von L).
Alle Typ-0 Sprachen sind semientscheidbar.
\(\underline{\textit{Charakteristische Funktion und Entscheidbarkeit}}\)
Eine Sprache \(A \subseteq \Sigma^*\) ist genau dann entscheidbar, wenn ihre charakteristische Funktion \(\chi _A :\Sigma^* \rightarrow \{ 0,1 \}\) berechenbar ist:
\(\chi_A(x) = \begin{cases} 1, & \text{für } x \in A \\ 0, & \text{für } x \notin A \end{cases}\)
Eine Sprache ist semientscheidbar, wenn ihre partielle charakteristische Funktion berechenbar ist.
\(\underline{\textit{WHILE-Programme}}\)
Eine Funktion \(f: \mathbb{N}^k \rightarrow \mathbb{N} \) nennt man WHILE-berechenbar, wenn es ein WHILE-Programm \(P\) gibt, das \(f\) wie folgt berechnet: \(P\) mit \(n_1...n_k\)in den Variablen \(x_1...x_k\) hält nach endlich vielen Schritten (wenn \(f(n_1...n_k)\) definiert ist) und dann befindet sich in der Variable \(x_0\) der Wert \(f(n_1...n_k)\). Falls nicht definiert, hält \(P\) nicht.
\(\underline{\textit{Welche Funktionen sind primitiv rekursiv?}}\)
- Konstante Funktionen
- Projektionen
- Nachfolgerfunktion \(s:\mathbb{N} \rightarrow \mathbb{N}\) mit \(s(n)=n+1\)
- Funktione die durch Einsetzen aus primtiv-rekursiven Funktionen entstehen
- Funktionen, die durch primitive Rekursion von primitiv rekursiven Funktionen enstehen
- Addition und Multiplikation
- Modifizierte Differenz
- Identifikation von Variablen
- Fiktive Variablen
- Vertauschte Variablen
- Einsetzen mit verschiedenen Variablen
\(\underline{\textit{Spezielle Regeln für Rekursion}}\)
- Eine Funktion ist genau dann primitiv rekursiv , wenn sie LOOP berechenbar ist. (primtiv rekursiv = LOOP-berechenbar)
- \(\mu\)-rekursiv = WHILE-berechenbar
\(\underline{\textit{Satz von Kleene}}\)
Sei \(f: \mathbb{N}^n \rightarrow \mathbb{N}\) eine \(\mu\)-rekursive Funktion. Dann existieren zwei \((n+1)\) stellige primitiv rekursive Funktionen \(p\) und \(q\) mit
\(f(x_1,...,x_n)=p(x_1,...,x_n,\mu q(x_1,...,x_n)) \).
\(\underline{\textit{Entscheidbar vs. Semientscheidbar}}\)
Eine Sprache \(A \subseteq \Sigma^*\)heißt entscheidbar genau dann, wenn \(A\) und \(\bar{A}\) semientscheidbar sind.
\(\underline{\textit{Rekursiv aufzählbare Sprachen}}\)
\(A \subseteq \mathbb{N}\) ist genau dann rekursiv aufzählbar, wenn sie die leere Menge ist (\(A = \emptyset\)) oder es eine totale und berechenbare Funktion \(f: \mathbb{N} \rightarrow \Sigma^*\) gibt, so dass gilt:
\(A=\{ f(n) \vert n \in \mathbb{N} \}\)
\(A\) ist genau rekursiv aufzählbar, wenn \(A\) semientscheidbar ist.
\(\underline{\textit{Äquivalente Charakterisierung einer rekursiv aufzählbaren Sprache}}\)
A ist rekursiv aufzählbar \(\Leftrightarrow\) A ist semientscheidbar \(\Leftrightarrow\) A ist von Typ 0 \(\Leftrightarrow\) A=T(M) für eine Turingmaschine M \(\Leftrightarrow\) \(\chi'_A\)ist berechenbar \(\Leftrightarrow\) A ist Definitionsbereich einer berechenbaren Funktion \(\Leftrightarrow\) A ist Wertebereich einer berechenbaren Funktion
\(\underline{\textit{Unentscheidbare Grammatik-Probleme}}\)
- Leehrheit des Schnitts: \(L_1 \cap L_2 = \emptyset \ ?\)
- Endlichkeit des Schnitts: \(\vert L_1 \cap L_2 \vert = \infty \ ?\)
- Kontextfreiheit des Schnitts: \(\exists G \ (Typ2) \ mit \ L(G)= L_1 \cap L_2 \ ?\)
- Inklusion: \(L_1 \subseteq L_2 \ ?\)
- Äquivalenz: \(L_1 = L_2 \ ?\)
\(\underline{\textit{Arithmetische Repräsentierbarkeit}}\)
\(f:\mathbb{N}^k \rightarrow \mathbb{N}\) ist arithmetisch repräsentierbar, wenn eine \((k+1)\)stellige arithmetische Formel \(F\) existiert, so dass
\(F(n_1,...,n_k,m) \Leftrightarrow f(n_1,...,n_k)=m\)
Jede WHILE-berechenbare Funktion ist arithmetisch repräsentierbar.
\(\underline{\textit{Satz von COOK}}\)
SAT ist NP-vollständig.
\(\underline{\textit{Sprachen, die weder Semi- noch CoSemi-entscheidbar sind}}\)
- \(U=\{ w:L(M_w) = \Sigma^* \}\)
- \(I=\{ w : \vert L(M_w) \vert = \infty \}\)
- \(Q= \{ (w_1, w_2) : L(M_{w_1}=L_{w_2} \}\)
\(\underline{\textit{Sprachen, die unentscheidbar sind}}\)
- \(E= \{ w: L(M_w) = \emptyset \}\)
- \(PCP\) Postsches Korrespondenzproblem
- Halteproblem \(H\), Halteproblem auf leerem Band \(H_0\)
Welche der folgenden Aussagen gilt nicht?
\(Welche\ der\ folgenden \ Aussagen \ lässt \ sich \ nach \ heutigem \ Wissenstand \ \textit{nicht} \ beantworten? \\\\ a) \ DSPACE(n^3) \subseteq NSPACE(n^5) .\\ b) \ 3-F\ddot{A}RBBARKEIT \in P.\\ c) \ 2-F\ddot{A}RBBARKEIT \in NP .\\ d) \ SAT \in PSPACE \)
c
\( Welche \ der\ folgenden\ Aussagen\ gilt\ \textit{nicht}? \\\\ a) \bigcup_{k \geq 0} NSPACE(n^k) \subseteq \bigcup_{k \geq 0} DSPACE(n^k) .\\ b) Das\ Halteproblem\ für\ Turingmaschinen\ lässt\ sich\ auf\ SAT\ reduzieren. \\ c) Jede\ Sprache\ in\ DTIME(n) \ lässt\ sich\ auf \ SAT\ reduzieren.\\ d) SAT \in PSPACE . \)
b
Sei HALBSAT das Problem, auf Eingabe einer aussagenlogischen Formel F zu entscheiden, ob eine erfüllende Belegung für F existiert, die genau die Hälfte der Variablen in F mit wahr belegt.
Sei INDEPENDENTSET das Problem, auf Eingabe eines ungerichteten Graphen und einer natürlichen Zahl k zu entscheiden, ob es eine unbhängige Menge dieses Graphen der Größe mindestens k gibt. (Eine unabhängige Menge ist eine Knotenmenge M , so dass je zwei Knoten aus M nicht durch eine Kante verbunden sind.) Welche der folgenden Aussagen gilt?
Was besagt der Gödelsche Unvollständigkeitssatz?
Sei L die Sprache aller \(w \in \{ 0,1 \}^*\) , so dass \(T(M_w) \) regulär ist.
Sei L die Sprache aller \(w \in \{ 0,1 \}^*\) , so dass \(M_w \)auf Eingabe 11 auf allen Berechnungspfaden und auf jedem Band höchstens 42 Zellen besucht.
Welche der folgenden Einschränkungen an die äußere Form von Turingmaschinen (mit mehreren Bändern) stellt eine Einschränkung der durch solche Turingmaschinen akzeptierten Sprachen dar?
Sei f eine beliebige LOOP-berechenbare Funktion. Welche der folgenden Aussagen gilt nicht?
Seien A und B beliebige Sprachen. Welche der folgenden Aussagen gilt nicht?
Sei L die Sprache aller \(w \in \{ 0,1 \}^*\) mit \(T(M_w) \neq \emptyset\) .
Sei a die Ackermann-Funktion
Welche Aussage gilt nicht?
\(\underline{\textit{Bekannte NP-vollständige Problem}}\)
- \(SAT\)
- \(3KNF-SAT\)
- \(CLIQUE\)
- \(Gerichteter\ Hamilton\ Kreis\)
- \(Mengenüberdeckung\)
- \(Färbbarkeit\)
- \(Knotenüberdeckung\)
- \(Partition\)
- \(Traveling \ Salesman\)
- \(Bin \ Packing\)
\(\underline{\textit{3KNF-SAT}}\)
gegeben: Eine Boolesche Formel \(F\) in konjunktiver Normalform (Klauselform) mit höchstens 3 Literalen pro Klausel
gefragt: Ist \(F\) erfüllbar?
\(\underline{\textit{Mengenüberdeckung}}\)
gegeben: Ein Mengensystem über einer endlichen Grundmenge \(M\), also \(T_1,...T_k \subseteq M\), sowie eine Zahl \(n \leq k\).
gefragt: Gibt es eine Auswahl aus \(n\) Mengen \(T_{i_1},...,T_{i_n}\), bei der bereits alle Elemente aus \(M\) vorkommen?
\(\underline{\textit{CLIQUE}}\)
gegebe: Ein ungerichteter Graph \(G=(V,E)\)und eine Zahl \(k \in \mathbb{N}\)
gefragt: Besitzt \(G\) eine "Clique" der Größe mindestens \(k\)? (Dies ist eine Teilmenge \(V'\) der Knotenmenge mit \(\vert V' \vert \geq k\) und für alle \(u,v \in V'\) mit \(u \neq v\) gilt: \(\{ u,v \} \in E\)).
\(\underline{\textit{Knotenüberdeckung}}\)
gegeben: Ein ungerichteter Graph \(G=(V,E)\)und eine Zahl \(k \in \mathbb{N}\).
gefragt: Besitzt \(G\) eine "überdeckende Knotenmenge" der Größe höchstens \(k\)? (Dies ist eine Teilmenge \(V' \subseteq V \) mit \(\vert V' \vert \leq k\), so dass für alle Kanten \(\{ u,v \} \in E\) gilt: \(u \in V'\) oder \(v \in V'\)).
\(\underline{\textit{Rucksack (oder SUBSET SUM)}}\)
gegeben: Natürliche Zahlen \(a_1, a_2, ..., a_k \in \mathbb{N}\) und \(b \in \mathbb{N}\).
gefragt: Gibt es eine Teilmenge \(I \subseteq \{ 1,2,..., k\}\) mit \(\sum _{i \in I} a_i = b\)?
\(\underline{\textit{Partition}}\)
gegeben: Natürliche Zahlen \(a_1, a_2,...a_k \in \mathbb{N}\)
gefragt: Gibt es eine Teilmenge \(J \subseteq \{ 1,2,...,k \}\) mit \(\sum_{i \in J} a_i = \sum _{i \notin J} a_i\)?
