Thema3

Aus ProgrammingWiki

< BuK < IIm12 < Studenten < siclsche

Archivierte Version vom 2013-04-15T08:41:41+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Aufgabe 1
2 Aufgabe 2
3 Aufgabe 3
4 Aufgabe 4
5 Aufgabe 5
6 Aufgabe 6
7 Aufgabe 7
8 Aufgabe 8
9 Aufgabe 9
10 Aufgabe 10
11 Aufgabe 11
12 Aufgabe 12

Aufgabe 1

Wie viele berechenbare charakteristische Funktionen gibt es?

Hinweis: Potenzmenge unendlicher Mengen

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

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;
		}	
	}
}

import java.util.ArrayList;

import utility.SubsetEnum;

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;
	}
	
}

ArrayList<String> alpha = new ArrayList<String>();
  alpha.add("a");
  alpha.add("b");
  Subset subset = new Subset(50, alpha);
  System.out.println(subset.getSubset(SubsetEnum.EXPRESSION));

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.

Thema3

Inhaltsverzeichnis

Aufgabe 1

Aufgabe 2

Aufgabe 3

Aufgabe 4

Aufgabe 5

Aufgabe 6

Aufgabe 7

Aufgabe 8

Aufgabe 9

Aufgabe 10

Aufgabe 11

Aufgabe 12

Suche