BuK/IIm12/Studenten/siclsche/Thema3
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
== Aufgabe 1 ==
Wie viele berechenbare charakteristische Funktionen gibt es?
''Hinweis: Potenzmenge unendlicher Mengen''
<language>Java</language>
<language>Java</language>
<language>Java</language>
== 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\}$
'''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="516bb99f33eed" hidden>
import java.util.ArrayList;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class MyStack <T> implements Iterable<T>{
private ArrayList<T> stack = new ArrayList<T> ();
public MyStack(){
stack = new ArrayList<T> ();
}
public MyStack(ArrayList<T> stack){
this.stack = stack;
}
public void add(T element){
stack.add(element);
}
public void push(T element){
stack.add(0, element);
}
public T pop( ){
if(!stack.isEmpty()){
T element = stack.get(0);
stack.remove(0);
return element;
}
return null;
}
public T getFirstElement(){
return stack.get(0);
}
public int getSize(){
return stack.size();
}
public boolean removeAt(int index) {
if(index < stack.size()){
stack.remove(index);
return true;
}
return false;
}
public void overrideStack(ArrayList<T> element){
stack = new ArrayList<T>();
}
public boolean isEmpty(){
return stack.isEmpty();
}
public T getElementAt(int index){
return stack.get(index);
}
public Iterator<T> iterator() {
return new StackIterator();
}
public String toString(){
String value = "";
for(T stackElement : stack){
value+=stackElement.toString()+";";
}
return value;
}
// an iterator, doesn't implement remove() since it's optional
private class StackIterator implements Iterator<T> {
private int count=0;
public boolean hasNext(){
if(count < stack.size()){
return true;
}
return false;
}
public void remove() {
throw new UnsupportedOperationException();
}
public T next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
T element = stack.get(count);
count++;
return element;
}
}
}</code>
<code id="516bb99f33f71" hidden>public class WordAmountStream {
private Alphabet alpha;
int upperWordBorder = 100;//Anzahl der ersten Element einer Menge M die ausgegeben werden
public WordAmountStream(ArrayList<String> alphabet){
this.alpha = new Alphabet(alphabet);
}
/**
* Berechnet die Potenzmenge einer Menge M.
* @return Potenzmenge
*/
public ArrayList<ArrayList<String>> getPotency(){
ArrayList<ArrayList<String>> potencyAmount = new ArrayList<ArrayList<String>>();
countPotency(alpha.getAlphabet(),potencyAmount);
ArrayList<String> emptyAmount = new ArrayList<String>();
emptyAmount.add(0, " ");
potencyAmount.add(0, emptyAmount);
return potencyAmount;
}
private void countPotency(ArrayList<String> alphabet,ArrayList<ArrayList<String>> potencyAmount){
MyStack<ArrayList<String>> stack = new MyStack<ArrayList<String>>();
if(alphabet.isEmpty()){
return;
}
// fülle den Stack
for(String letter : alphabet){
ArrayList<String> tempAmount = new ArrayList<String>();
tempAmount.add(letter);
stack.add(tempAmount);
}
//Trage die erste Teilmenge ein
potencyAmount.add(stack.getElementAt(0));
while (!stack.isEmpty()){
//Hole die erste nicht leere Menge aus dem Stack und füge ist in die Potenzmenge
ArrayList<String> firstAmount = stack.pop();
//potencyAmount.add(firstAmount);
ArrayList<String> nextSubsetToPush = new ArrayList<String>();
for(int i = 0;i < stack.getSize();i++){
//kombiniere alle Restmengen mit der ersten Menge
ArrayList <String> tmpSubset = new ArrayList<String>(firstAmount);
tmpSubset.add(stack.getElementAt(i).get(0));
if(i == 0){
nextSubsetToPush = new ArrayList<String>(tmpSubset);
}
potencyAmount.add(tmpSubset);
}
//ersetze das nächste Element mit der ersten Kompination
stack.pop();
if(!stack.isEmpty()){
stack.push(nextSubsetToPush);
}
}
//lösche das erste zeichen aus dem Alphabet und rufe erneut die Funktion auf
if(stack.isEmpty()){
alphabet.remove(0);
countPotency(alphabet,potencyAmount);
}
}
/**
* Gibt alle Wörter aus A* über dem Alphabet A, bis zur upperBorder, zurück.
* Bemerkung: eingegebene Menge A muss geordnet sein
* @return Liste der ersten n Elemente
*/
public ArrayList<String> getWordAmount(int upperBorder){
ArrayList<String> amount = new ArrayList<String>();
amount.add(" ");
int count = 0;
for (int i = 0; i < alpha.getAlphabet().size(); i++){
String currentLetter = alpha.getLetter(i);
amount.add(currentLetter);
count++;
}
for (int i = 1; i < amount.size(); i++){
for (int j = 0; j < alpha.getAlphabet().size(); j++){
String currentLetter = amount.get(i) + alpha.getLetter(j);
amount.add(currentLetter);
count++;
}
if(count >= upperWordBorder){
break;
}
}
return amount;
}
private class Alphabet{
private ArrayList <String> alpha;
public Alphabet (ArrayList <String> alpha){
this.alpha = new ArrayList<String>(alpha);
}
public String getLetter(int index){
if( index < alpha.size() ){
return alpha.get(index);
}
return null;
}
public ArrayList<String> getAlphabet(){
return alpha;
}
}
}
</code>
<code id="516bb99f33ff3" hidden>
public enum SubsetEnum {
ODD,EVEN,WORDLENGTH,EXPRESSION
}
}</code>
<code id="516bb99f3405f">
public class Subset {
private WordAmountStream stream;
private int maxWordToDisplay;
private int wordlength = 3;
private String containExpression ="[a].*?";
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>
== Aufgabe 3 ==
Zeigen Sie, dass die Menge der geraden Zahlen G eine aufzählbare Menge ist.
== Aufgabe 4 ==
Zeigen Sie, dass die Menge der Primzahlen P aufzählbar ist.
== 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.