BuK/IIm14/Studenten/s3rozoek/Uebung3

Wiki-Quelltext dieser Seite.

<language>Javascript</language>
Vereinigung mit Streams

= Übung 3 =

== Entscheidbarkeit einfacher Mengen ==

Zu zeigen ist die Entscheidbarkeit der beiden Mengen $M1$ und $M2$. Dazu reicht es eine entsprechende Charaktersitische Funktion $\chi_{M_x}(w)$ zu finden.

=== Bsp1 ===
$A^*={a,b}^*$ und $M_1 \subset A^* = \{w | w \in A^* \text{ und }  |w| = 3\}$
$M_1$ ist die Menge aller Wörter aus $A^*$, die die Länge 3 beseitzen, d.h. $M_1 = \{aaa, aba, aab, baa, bab, abb, bba, bbb\}$

Da die Menge endlich ist, können einfach alle Elemente überprüft werden. Somit ergibt sich $\chi_{M_1}(w)$.

$$ 
\chi_{M_1}(w) = \begin{cases}
wahr, & \text{wenn } w==aaa || w==aba || w==aab || w==baa || w==bab || w==abb || w==bba || w==bbb;\\
falsch, & \text{sonst}
\end{cases}
$$

<code id="552e54cde090f">
function chiM1(wort){
if(wort=="aaa"||wort=="aba"||wort=="aab"||wort=="baa"||wort=="bab"||wort=="abb"||wort=="bbb"){return true;}
else{return false;}
}
</code>

<run id="552e54cde0985">
chiM1("aaa")
</run>


=== Bsp 2 ===
Abzählbar unendliche Menge.
$M_2$ ist die Menge aller Wörter, die aus beliebig vielen a's und b's bestehen und mit a beginnen. $A^* = {a, b}^*$ und $M1 \subset A^* = {w = aw' | w' \in A^*}$

Da es reicht das erste Element zu überprüfen, ist die Menge entscheidbar. Dazu sei $w \in M_1 = w_1 \circ w_2 \circ ... \circ w_n | w_1,...w_n \in A$

$$ 
\chi_{M_2}(w) = \begin{cases}
wahr, & \text{wenn } w_1 == a;\\
falsch, & \text{sonst}
\end{cases}
$$

<code id="552e554c46082">
function chiM2(wort){
if(wort.charAt(0)=="a"){return true;}
else{return false;}
}
</code>

<run id="552e554c460f9">
chiM2("abbbbabababababba")
</run>


== Anzahl berechenbarer charakteristischer Funktionen ==

Da die Potenzmenge von $A^*$ überabzählbar unendlich ist, gibt es überabzählbar unendlich viele charakteristische Funktionen (eine für jede Teilmenge). Davon sind nicht alle berechenbar (ein Gegenbeispiel reicht).

== Aufzählbarkeit ==

Eine Menge $M \subseteq A^*$ heißt aufzählbar, wenn es entweder eine total berechenbare surjektive Funktion $f : \N \rightarrow M$ gibt, oder es gilt $M=\emptyset$
Man nennt f eine Aufzählprozedur oder ein Aufzählverfahren von M.
Sehr vereinfacht : aufzählbar = abzählbar + berechenbar

Somit muss für den Beweis der Aufzählbarkeit eine entsprechende Funktion $f$ gefunden werden.


=== Menge der geraden Zahlen G ===

z.z. Die Menge $G = \{g | g=2n , n \in \N\}$ ist aufzählbar.

Das Aufzählverfahren ergibt sich bereits aus der Definition von $G$.

$f(n) = 2n$

=== Menge der Primzahlen ===


$ f(n) = \begin{cases}
n, & \text{wenn x eine Primzahl ist} ;\\
2, & \text{sonst}
\end{cases} $

=== $A^*$ ===
Aufbauschema:
[[Bild:Rzoeke_ASternAufbauschema.png]]

Aufbauprozedur:

<code id="552e6ccc7c06e">
function aStern(n,alphabet){
if(n==0){
return "";
}
var array = [];
while(array.length<n){
array=createNextSet(array,alphabet);
}
return array[n-1];
}

function createNextSet(array,alphabet){
var result = [];
if(array.length==0){
result = ["a","b","c"];
return result;
}
for(i=0;i<array.length;i++){
 for(j=0;j<alphabet.length;j++){
 result.push(array[i].concat(alphabet[j]));
 }
}
return array.concat(result);
}
</code>

<run id="552e6ccc7c1a3">
aStern(12,["a","b","c"])
</run>

=== jede endliche Menge ===

Per Definition ist jede endliche Menge abzählbar. Weiterhin gibt es für jede endliche Menge M eine surjektive total berechenbare Funktion f, mit f : N -> M.

=== Menge G der Gitterpunkte ===
????
(0,0),(0,1),...

Geben Sie eine Funktion f an, die N bijektiv auf G abbildet.
2 Definieren Sie eine Ordnungsrelation p < in G .
3 Geben Sie eine Funktion k zur Berechnung der Platznummer
k(x, y ) des betrachteten Gitterpunktes (x, y ) an.
4 Geben Sie eine Aufz ̈ahlprozedur f ̈
ur G an und begr ̈
unden Sie
deren Berechenbarkeit.

== Semi Entscheidbarkeit ==

=== Halteproblem ===

Sei $A$ die Menge aller Algorithmen, dann gibt es eine Funktion $\chi'_A$ die wahr zurückgibt, wenn ein Algorithmus terminiert.

$$ 
\chi'_{A}(a) = \begin{cases}
wahr, & \text{wenn a terminiert};\\
\bot, & \text{sonst}
\end{cases}
$$

=== FIBS ===

Aufzählfunktion $\fib(n) = \begin{cases}
1, & \text{wenn n==1 oder n==0};\\
 fib(n-1)*fib(n-2), & \text{sonst}
\end{cases}
$

FIBS Entscheidbar?
$$ 
\chi'_{FIBS}(f) = \begin{cases}
wahr, & \text{wenn f in FIBS};\\
falsch, & \text{sonst}
\end{cases}
$$

Die Menge ist entscheidbar, da die Charakteristische Funktion berechenbar ist.

<code id="552e62e47c4bd">
function fib(n){
if(n==0||n==1){return 1;}
else{return fib(n-1)+fib(n-2);}
}

function chiFIBS(zahl){
var count = 0;
var running = true;
while(running){
 if(fib(count)==zahl){return true;}
 if(fib(count)>zahl){return false;} //Abbruchbedingung. zahl kann in diesem Fall nicht mehr gefunden werden.
 count = count +1;
}

}
</code>

<run id="552e62e47c55b">
//ACHTUNG rekursive quick&dirty Implementierung von fib. Keine großen Zahlen nehmen!
chiFIBS(10)
</run>

Aus der Entscheidbarkeit folgt die semi Entscheidbarkeit.

=== Quadratzahlen ===

Aufzählfunktion

$f(n)=n^2$

$
\chi_{QZ}(n) = \begin{cases}
wahr, & \text{wenn } sqrt(n) \in \N;\\
falsch, & \text{sonst}
\end{cases}
$

=== Wörter, die mit a beginnen ===

Aus Entscheidbarkeit folgt die Semi Entscheidbarkeit.

== Vereinigung ==

Definieren Sie die Menge der geraden Zahlen (Zahlwörter) und die der ungeraden Zahlen (Zahlwörter) und veranlassen Sie das ProgrammingWiki 30 Elemente der Vereinigungsmenge auszugeben.

<code id="552e6ccc7c0e0">
function even(n){
return 2*n;
}

function unEven(n){
return 3*n;
}

function printSet(numberOfItems,buildFunction){
var result = [];
for (i = 0; i < numberOfItems; i++){ 
  result.push(buildFunction(i));
 }
return result;
}
</code>

<run id="552e6ccc7c237">
printSet(15,even);
printSet(15,unEven);
</run>