Kreativaufgabe Zeitbeschränkte Prozesse (Kretschmer, Schumann)

Wiki-Quelltext dieser Seite.

;Autoren
:[mailto://s3toschu@stud.hszg.de Tom Schumann]<br/>
:[mailto://s3hakret@stud.hszg.de Hannes Kretschmer]

=Aufgabenstellung=

Implementieren Sie die im Beweis definierte Aufzählfunktion für $M \subseteq \text{ A*}$ unter Verwendung der Cantorschen Paarungsfunktion. Wählen Sie im Fallbeispiel $A = \{a,b,c\}, g: \N \mapsto A^*$ und M = $\{w |w \in A^* \text{ und } w \text{ enthält Fibonacci-zahlig viele } b's\}$.

Machen Sie bei der Konstruktion von $\chi^'_M$ nur von der Semi-Entscheidbarkeit der Menge der Fibonacci-Zahlen Gebrauch, obwohl doch deren Entscheidbarkeit durch Beschränkung des Suchraumes gegeben ist.

'''Hinweis:''' Sie benötigen keine ''engines''. Das einfache Timer-System reicht aus.

=Lösung=

==Abbildung der Natürlichen Zahlen==

<popup text="Vollständigen Code"><code rows="11">
class Naturals:
    def __init__(self):
        self.current = 0

    def __next__(self):
        result = self.current
        self.current += 1
        return result

    def __iter__(self):
        return self
</code>

==Generierung von $A^*$==

<popup text="Vollständigen Code"><code>
def generate_a_star(A, count):
    A_star = []
    for s in A:
        A_star.append(s)
    for i in range(0, count):
        A_star_temp = A_star.copy()
        for p in A_star_temp:
            for s in A:
                if (p + s) not in A_star:
                    A_star.append(p + s)
    A_star.append("")
    return A_star

</code></popup>

==Menge der Fibonacci-Wörter==

<popup text="Vollständigen Code"><code>
class FibWords:
    def __init__(self):
        self.current = 0

    def __next__(self):
        self.current += 1
        result = fib(self.current)
        return result

    def __iter__(self):
        return self


def fib(n):
    if n == 1:
        return "b"
    elif n == 0:
        return "b"
    else:
        return fib(n - 1) + fib(n - 2)

</code></popup>

==Cantorsche Paarungsfunktion==

<popup text="Vollständigen Code"><code>
def cantor(x, y):
    return int(((x + y) * (x + y + 1) / 2) + y)


def get_w_from_cantor(z):
    return int(math.floor(0.5 * ((math.sqrt(8 * z + 1)) - 1)))


def get_x_from_cantor(z):
    w = get_w_from_cantor(z)
    return w - get_y_from_cantor(z)


def get_y_from_cantor(z):
    w = get_w_from_cantor(z)
    t = int(w * (w + 1) * 0.5)
    return z - t



</code></popup>

==$g: \N \mapsto A^*$==

<popup text="Vollständigen Code"><code>

def g(x):
    j = 0
    for i in A_star:
        if j == x:
            return i
        j += 1

</code></popup>

==Aufzählfunktion==

<popup text="Vollständigen Code"><code>
def f(z):
    x = get_x_from_cantor(z)
    y = get_y_from_cantor(z)
    fib_word = g(x)
    chi_thread = ChiThread(fib_word)
    chi_thread.start()
    time.sleep(y)
    chi_thread.join(timeout=2)
    if chi_thread.return_result():
        return fib_word
    else:
        return "b"

</code></popup>

==Zeitbegrenzung==
<code>
class ChiThread(Thread):
    def __init__(self, w):
        super(ChiThread, self).__init__()
        self.word = w
        self.result = False
        self.stoprequest = threading.Event()

    def join(self, timeout=None):
        self.stoprequest.set()
        super(ChiThread, self).join(timeout)

    def run(self):
        self.result = chi_strich_m(self.word)

    def return_result(self):
        return self.result
</code>