Vorlesung 3 Seidl

Aus ProgrammingWiki

Inhaltsverzeichnis 1 S. 9 2 S. 15 3 S. 16 4 S. 20 5 S. 23

S. 9

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"))

ausführen

def ist_in(wort): if wort[0] == "a": return True else: return False

print(ist_in("hallo"))

ausführen

S. 15

Zahlen G, aufzählbare Menge:

def generator(n): if n % 2 != 0: print(n + " ist keine gerade Zahl") return while True: n += 2 yield n

for n in generator(2): print(n)

ausführen

Primzahl-Generator:

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

for i in generator(2): print(i)

ausführen

S. 16

Jede endliche Menge aufzählbar:

def aufzaehler(menge): for element in menge: print(element)

aufzaehler(["a", "b", "c", "abc"])

ausführen

Gitterpunkte (TODO: Als Generator umbauen?):

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)

# gp = [x, y] gp = [0, 0] diagonalisierung(gp) print(gp_list)

ausführen

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:

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

print(ist_fib(1))

ausführen

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.
Ist sogar entscheidbar:

def ist_fib(n): count = 1 for f in fib(): if n == f: return True if f > n: return False

print(ist_fib(1))

ausführen

TODO: ÜA 4

S. 23

TODO