BuK/IIm20/Vorlesung 3 Thomas

Wiki-Quelltext dieser Seite.

<language>Python</language>
Seite 9

'''Beispiel 1: endliche Menge'''

$A^∗ = \{a, b\}^∗$ und $M \subset A^∗ = \{w | w \in A^∗$ und $|w| = 3\}$.

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

$M = \{aaa, aba, aab, baa, bab, abb, bba, bbb\}$.

<code id="606703bee3717">def chi(m):
    if len(m) == 3:
	return m in ['aaa', 'aba', 'aab', 'baa', 'bab', 'abb', 'bba', 'bbb']
    return False</code>
<run id="606703bee3801">
print(chi("aaa"))
print(chi("aa"))
print(chi("bab"))
print(chi("bcb"))</run>

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

<code id="606703bee3789">
def chi(m):
    if len(m) > 0:
        return m[0] == "a"
    return False</code>
<run id="606703bee3871">
print(chi("abaaba"))
print(chi("babbaa"))</run>


----
Seite 15

Ü1: Zeigen Sie, dass die Menge der geraden Zahlen G eine aufzählbare Menge ist.

Ü2: Zeigen Sie, dass die Menge der Primzahlen P aufzählbar ist.

<code id="607001132c229">
def is_prime_number(x):
    if x >= 2:
        for y in range(2,x):
            if not ( x % y ):
                return False
    else:
	return False
    return True</code>
<run id="607001132c2ae">for i in range(2,60):
    if is_prime_number(i) == True:
        print(i)</run>

Ü3: 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.

----
Seite 16

Zeigen Sie, dass jede endliche Menge aufzählbar ist.

*$M = \{x_0, ..., x_n\}$ ist Wertebereich von $f$ mit $f(n) = 
\begin{cases}
x_i & falls~i\geq n \\
x_0 & \, \text{sonst}
\end{cases}$
*$f$ ist primitiv rekursiv, also berechenbar

Die Menge $G$ der Gitterpunkte $(0, 0),(0, 1), ...$ einer x-y-Ebene ist aufzählbar.
<code id="60734e5d4581e">
def gitter(x):
    list = []
    startx = 0
    while len(list) <= x:
        list.append("(" + str(startx) + ", " + str(startx) + ")")
        if len(list) == x: break
        list.append("(" + str(startx) + ", " + str(startx+1) + ")")
        if len(list) == x: break
        list.append("(" + str(startx+1) + ", " + str(startx) + ")")
        startx+=1
    print(list)
</code>
<run id="60734e5d45ae2">
gitter(7)
gitter(20)
</run>

<code id="60734e5d458c3">
def find_gitter(y, x):
    list = []
    startx = 0
    while True:
        list.append("(" + str(startx) + ", " + str(startx) + ")")
        if startx == y and startx == x: break
        list.append("(" + str(startx) + ", " + str(startx+1) + ")")
        if startx == y and (startx+1) == x: break
        list.append("(" + str(startx+1) + ", " + str(startx) + ")")
        if (startx+1) == y and startx == x: break
        startx+=1
    print(len(list))
</code>
<run id="60734e5d45b5a">
find_gitter(1, 2)
find_gitter(2, 1)
find_gitter(7, 8)
find_gitter(10, 10)
</run>
----
Seite 20

Ü1: Das Halteproblem ist semi-entscheidbar. Beweisen Sie diese Aussage.

Ü2: Geben Sie für 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.
<code id="60734e5d45945">def FIBS(n):
    if n == 0:
        return 1
    if n == 1:
        return 1
    if n == 2:
        return 2
    return FIBS(n-1) + FIBS(n-2)</code>
<run id="60734e5d45bca">for i in range(5):
    print(FIBS(i))</run>
Ü3: Übertragen Sie die vorhergehende Übungsaufgabe sinngemäß auf die Menge der Quadratzahlen $QZ = \{n^2| n \in N\}$.
<code id="60734e5d459c0">
def q(x):
    return x*x
</code>
<run id="60734e5d45c46">print(q(10))
print(q(105))
print(q(1078))</run>
Ü4: Weisen Sie nach, dass die Menge $M$ aller Wörter aus ${a, b}^∗$, die mit $a$ beginnen, semi-entscheidbar ist

----
Seite 23

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="60734e5d45a3f">def even(n):
    return 2 * n

def odd(n):
    return 2 * n + 1

def unite(i, f, g):
    if i % 2 == 0:
        return f(i / 2)
    else:
        return g((i-1) / 2)</code>
<run id="60734e5d45cb8">for i in range(30):
    print(unite(i, even, odd))</run>