BuK/IIm20/Vorlesung 3 Seidl

Wiki-Quelltext dieser Seite.

<language>Python</language>
<language>Python</language>
=== S. 9 ===

<code id="607075c26e3a5">
menge = ["aaa", "aba", "aab", "baa", "bab", "abb", "bba", "bbb"]

def ist_in(wort):        
        if wort in menge:
                return True
        else:
                return False

print(ist_in("a"))
</code>

<code id="60707494b88b0">
def ist_in(wort):
        if wort[0] == "a":
                return True
        else:
                return False
</code>
<run id="60707494b8b64">
print(ist_in("hallo"))
</run>

=== S. 15 ===
Zahlen G, aufzählbare Menge:
<code id="60707494b8910">
def generator(n):
        if n % 2 != 0:
                print(n + " ist keine gerade Zahl")
                return
        
        while True:
                n += 2
                yield n
</code>
<run id="60707494b8bdf">
for n in generator(2):
        print(n)
</run>

Primzahl-Generator:
<code id="60707494b8976">
def generator(n):
    while True:
        if ist_primzahl(n):
            yield n
        n += 1
 
def ist_primzahl(n):
    if n == 2:
        return True

    for i in range(2, n):
        if n % i == 0:
            return False 
    
    return True
</code>
<run id="60707494b8c5b">
for i in generator(2):
    print(i)
</run>

=== S. 16 ===
Jede endliche Menge aufzählbar:
<run id="60707494b8cbc">
def aufzaehler(menge):
        for element in menge:
                print(element)
</run>

Gitterpunkte (TODO: Als Generator umbauen?):
<code id="60707494b89ce">
gp_list = {}
def diagonalisierung(gpm, max_n=100):
    # X + 1
    gp[0] = gp[0] + 1
    gp_list[len(gp_list) + 1] = (gp[0], gp[1])

    for x_next in range(gp[0] - 1, 0, -1):
        gp[1] = gp[1] + 1
        gp[0] = x_next
        gp_list[len(gp_list) + 1] = (gp[0], gp[1])
        
    gp[1] = gp[1] + 1
    gp_list[len(gp_list) + 1] = (gp[0], gp[1])

    for x_next in range(gp[0] + 1, gp[1] + 1):
        gp[1] = gp[1] - 1
        gp[0] = x_next
        gp_list[len(gp_list) + 1] = (gp[0], gp[1])

    if len(gp_list) >= max_n:
        return

    diagonalisierung(gp)
</code>
<run id="60707494b8d15">
# gp = [x, y]
gp = [0, 0]

diagonalisierung(gp)
print(gp_list)
</run>

=== S. 20 ===
Direkter Beweis: Der Beweis dafür, ob das Halteproblem semi-entscheidbar ist, leitet sich aus den Definitionen des Halteproblems und der semi-entscheidbarkeit ab. Beim Halteproblem handelt es sich um ein Entscheidungsproblem, ob eine Funktion einen Rückgabewert gibt (da die zu prüfende Bedingung erfüllt ist) oder endlos weiter läuft. Man kann die Laufzeit nicht vorhersagen, von daher kann auch nicht gesagt werden, ob es nur sehr lange dauert bis die Bedingung erfüllt ist oder ob die Bedingung niemals erfüllt sein wird. Die semi-Entscheidbarkeit gibt genau diesen SV wieder.

FIBS:
<code id="60707494b8a25">
def fib():
        i = 0
        j = 1
        while True:
                yield i
                i = j
                j = i + j


def ist_fib(n):
        count = 1
        for f in fib():
                if n == f:
                        return True
</code>
<run id="60707494b8d6e">
print(ist_fib(1))
</run>

Nachweis semi-entscheidbare Menge: Die Funktion gibt nur Wahr zurück, wenn der zu prüfende Wert Teil der Fibonacci Folge ist. Ist dies nicht der Fall, so läuft die Funktion unendlich weiter.<br/>
Ist sogar entscheidbar:
<code id="60707494b8a7c">
def ist_fib(n):
        count = 1
        for f in fib():
                if n == f:
                        return True
                if f > n:
                        return False
</code>
<run id="60707494b8dc8">
print(ist_fib(1))
</run>

TODO: ÜA 4

=== S. 23 ===
TODO