BuK/IIm12/Studenten/siclsche/Thema3

Wiki-Quelltext dieser Seite.

<language>Java</language>
== Aufgabe 1 ==
Wie viele berechenbare charakteristische Funktionen gibt es?

''Hinweis: Potenzmenge unendlicher Mengen''

Zu jeder Teilmenge der Menge $A^*$ existiert eine charakteristische Funktion. Daher gibt es so viele charakterisitsche Funktionen, wie es Teilmengen gibt. Sämtliche Teilmengen einer Menge $M$ sind in der Potenzmenge von $M$ enthalten. Da die Potenzmenge einer unendlichen Menge überabzählbar unendlich viele Elemente besitzt, gibt es demzufolge ebenfalls überabzählbar unendlich viele charakteristische Funktionen.

== Aufgabe 2 == 
'''Beispiel 1:'''

M ist die Menge aller Wörter aus $A^*$, die die Länge 3 besitzen, d.h.:

$A^* = \{a, b\}^* \text{ und } M \subset A^* = \{w \mid w \in A^*\text{ und } |w| = 3\}$

* bei diesem Beispiel handelt es sich um eine endliche Menge
** somit kann jedes Element der Menge mit dem gesuchten Element verglichen und eine Entscheidung getroffen werden
* die entsprechende charakteristische Funktion dazu ist: $
\chi_M(w) = \begin{cases}
wahr, & \text{wenn } w \in M;\\
falsch, & \text{sonst}
\end{cases}
$


'''Beispiel 2''' abzählbar unendliche Menge

$ M $ ist die Menge aller Wörter, die aus beliebeig vielen $ a $'s und $ b $'s bestehen und mit $ a $ beginnen: $ A^* = \{a,b\}^* $ und $ M \subset A^* = \{w = aw' | w' \in A^* \} $ .

Zeigen Sie, dass die beiden Mengen aus den Beispielen entscheidbar sind. Schreiben Sie je eine entsprechende Prozedur für die jeweilige charakteristische Funktion
<code id="516bb99f33ff3">
public enum SubsetEnum {
	ODD,EVEN,WORDLENGTH,EXPRESSION
}
</code>

<code id="516bb99f3405f">
public class Subset {
	private WordAmountStream stream;//alle n (< maxWordDisplay) Wörter aus A* 
	private int maxWordToDisplay; 
	private int wordlength = 3; // Wörter mit der Länge 3
	private String containExpression ="[a].*?";  // Wörte die mit a beginnen
	
	public Subset (int maxWordtoDisplay, ArrayList<String> alphabet){
		stream = new WordAmountStream(alphabet);
		this.maxWordToDisplay = maxWordtoDisplay;
	}
	
	public ArrayList<String> getSubset(SubsetEnum subset){
		if(subset.equals(SubsetEnum.WORDLENGTH)){
			return subsetWordlength();
		}
		if(subset.equals(SubsetEnum.EXPRESSION)){
			return subsetExpression();
		}
		
		if(subset.equals(SubsetEnum.EVEN)){
			return null;
		}
		if(subset.equals(SubsetEnum.ODD)){
			return null;
		}
		return null;
	}
	
	private ArrayList<String> subsetExpression(){
		ArrayList<String> result = new ArrayList<String>();
		ArrayList<String> words=stream.getWordAmount(maxWordToDisplay);
		for(String word :words){
			if(word.matches(containExpression)){
				result.add(word);
			}
		}
		return result;
	}

	private ArrayList<String> subsetWordlength(){
		ArrayList<String> result = new ArrayList<String>();
		ArrayList<String> words=stream.getWordAmount(maxWordToDisplay);
		for(String word :words){
			if(word.length() == wordlength){
				result.add(word);
			}
		}
		return result;
	}
	
}
</code>
[[BuK/IIm12/Studenten/siclsche/Thema3/wordAmount|WordAmount.java]], [[BuK/IIm12/Studenten/siclsche/Thema3/MyStack|MyStack.java]]

<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
== Aufgabe 3 ==
Zeigen Sie, dass die Menge der geraden Zahlen G eine aufzählbare Menge ist.

Um Aufzählbarkeit zu beweisen, muss gezeigt werden, dass die zu untersuchende Menge abzählbar und berechenbar ist.

Die Abzählbarkeit wird bewiesen, indem eine Funktion angegeben wird, welche die natürlichen Zahlen bijektiv auf die Menge der geraden Zahlen abbildet:

$$f(x) = 2x$$

Die Berechenbarkeit wird nachgewiesen, indem eine Prozedur angegeben wird, welche eine natürliche Zahl nimmt und ein Element der geraden Zahlen ausgibt:


<code id="51821013ce3e3">
(define gerade
  (lambda (x)
    (* 2 x)))
</code>

<run id="51821080f34ff">(gerade 13)</run>


Da sowohl die Abzählbarkeit, als auch die Berechnbarkeit nachgewiesen wurden, ist gezeigt, dass die Menge der geraden Zahlen aufzählbar ist.

<language>Scheme</language>
== Aufgabe 4 ==
Zeigen Sie, dass die Menge der Primzahlen P aufzählbar ist.

Nach Euklid ist die Menge der Primzahlen eine unendliche Menge. Da sie außerdem eine Teilmenge der natürlichen Zahlen ist, die abzählbar unendlich sind, ist sie ebenfalls abzählbar unendlich.

<code id="51821519461b2">
(define prim?
  (lambda (n)
    (letrec
        ((helfer
          (lambda (t)
            (cond
              ((> t (sqrt n)) #t)
              ((= (remainder n t) 0) #f)
              (else
               (helfer (+ t 2)))))))
    (cond
      ((= n 1) #f)
      ((= n 2) #t)
      ((= (remainder n 2) 0) #f)
      (else
       (helfer 3))))))

(define nat_zahlen (make-stream 0 (lambda (n) (+ n 1))))

(define generiere_aufzaehlbare_menge
  (lambda (f)
    (stream-map f nat_zahlen)))

(define primzahlen (generiere_aufzaehlbare_menge f))
</code>

<run id="518215194621e">(menge-bis primzahlen 18)</run>

== Aufgabe 5 ==
Wir wissen, dass A* eine abzählbar unendliche Menge ist. Zeigen Sie, dass A* auch aufzählbar ist. Hinweis: Hierzu ist es notwendig ein Aufbauschema für A* zu entwerfen und anschließend eine Prozedur dafür zu implementieren.

== Aufgabe 6 ==
Zeigen Sie, dass jede endliche Menge M aufzählbar ist.

== Aufgabe 7 ==
Die Menge G der Gitterpunkte (0, 0),(0, 1), ... einer x-y-Ebene ist aufzählbar.

1. Geben Sie eine Funktion f an, die $\N_0$ 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ählprozedur für G an und begründen Sie deren Berechenbarkeit.

== Aufgabe 8 ==
Das Halteproblem ist semi-entscheidbar. Beweisen Sie diese Aussage.

== Aufgabe 9 ==
Geben Sie fur die Menge FIBS der Fibonacci-Zahlwörter eine Aufzählfunktion an und begründen Sie deren Berechenbarkeit.
Weisen Sie nach, dass FIBS eine semi-entscheidbare Menge ist. Zeigen Sie, dass FIBS sogar entscheidbar ist.

== Aufgabe 10 ==
Übertragen Sie die vorhergehende Übungsaufgabe sinngemäß auf die Menge der Quadratzahlen $QZ = \{n^2 |n \in \N\}.$

== Aufgabe 11 ==
Weisen Sie nach, dass die Menge $M$ aller "Wörter" aus $\{a,b\}^*$, die mit a beginnen, semi-entscheidbar ist.

== Aufgabe 12 ==
Definieren Sie die Menge der geraden Zahlen (Zahlwörter) und die der ungeraden Zahlen (Zahlwörter) und veranlassen Sie das ProgrammingWiki die 30 ersten Elemente der Vereinigungsmenge (in aufsteigender Sortierung) auszugeben.