BuK/IIm20/Vorlesung 11 Lemke

Wiki-Quelltext dieser Seite.

<language>Python</language>
== Übungsaufgabe S. 6 ==

=== Add-Funktion in Python ===

<code id="60c4e63cdf8a1">
def S(x):
	return x + 1

def add(x, n):
	if x == 0:
		return n
	else:
		return S(add(x-1, n))
		
def add_loop(x, n):
	for i in range(n):
		x = S(x)
	return x
</code>
<run id="60c4e63cdfa42">
print(add(130, 15))
print(add_loop(130, 15))
</run>

=== Multipikationsfunktion in Python ===
<code id="60c4e63cdf917">
def mult(x, n):
	if x == 0:
		return 0
	else:
		return add(mult(x-1, n), n)
		
def mult_loop(x, n):
	res = 0
	for i in range(n):
		res = add(res, x)
	return res
</code>
<run id="60c4e63cdfac2">
print(mult(3, 4))
print(mult_loop(3, 4))
</run>

=== Potenzfunktion in Python ===

<code id="60c4e63cdf982">
def pot(exp, base):
	if exp == 0:
		return 1
	else:
		return mult(pot(exp-1, base), base)
		
def pot_loop(exp, base):
	res = 1
	for i in range(exp):
		res = mult(res, base)
	return res
</code>
<run id="60c4e63cdfb1c">
print(pot(3, 4))	
print(pot_loop(3, 4))
</run>

== Übungsaufgabe S. 16 == 

=== Wiederholte Nachfolgerbildung - primitiv rekursiv? ===

[[Bild:WiederholteNachfolgerbildung.jpg]]

== Übungsaufgabe S. 32 ==

=== Memoizingtabelle der AP-Funktion ===

[[Bild:Memoizingtablette_APFunktion.jpg]]

== Übungsaufgabe S. 45 ==

=== Polynome mit natürlichen Koeffizienten primitiv rekursiv? ===

Polynome mit natürlichen Koeffizienten sind primitiv rekursiv, weil sie sich aus den bereits bekannten primitiv rekursiven Funktionen, Multiplikation, Addition, Potenz, Substraktion, zusammensetzen. Mithilfe der Aufbautechnik Substitution und den erwähnten Grundrechenarten kann man jedes dieser Polynome darstellen.