Vorlesung 2 Lemke

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Übungsaufgabe 1 (S. 5) 1.1 Unzugängliche Probleme 1.2 Praktisch unmöglich zu lösende Probleme 1.3 Warum ist es so schwierig, ein leistungsfähiges Schachprogramm zu entwerfen? 2 Übungsaufgabe 2 (S. 6) 2.1 Beweise & Zeigen von abzählbarer und unabzählbarer Unendlichkeit von Mengen 3 Übungsaufgabe 3 (S. 7) 3.1 Rekursive Funktion und ihre Umkehrfunktion, mit Memoizing 4 Übungsaufgabe 4 (S. 11) 5 Übungsaufgabe 5 (S. 15) 5.1 Primzahlzwillinge

Übungsaufgabe 1 (S. 5)

Unzugängliche Probleme

• soziale Konstrukte wie z.B. Dynamiken in einer Gesellschaft oder in einer Marktwirtschaft, aufgrund der Komplexität, Schwierigkeit der abstrakten Darstellung und Mangel an Information

Praktisch unmöglich zu lösende Probleme

• Primfaktorzerlegung (Quantencomputer mit einer gewissen Anzahl an QBits könnten das Problem in Zukunft aber praktisch lösbar machen, allerdings sind wir noch lange nicht bei der Größenordnung an QBits angekommen, weshalb das Problem praktisch immer noch unmöglich zu lösen ist)

Warum ist es so schwierig, ein leistungsfähiges Schachprogramm zu entwerfen?

Einfach aufgrund der immenns vielen Möglichkeiten, die es in jedem Spielzustand gibt. Man kann aber, wenn man nicht die perfekte Lösung haben will, eine hinreichend gute Lösung in akzeptabler Zeit erhalten, z.B. mit QLearning

Übungsaufgabe 2 (S. 6)

Beweise & Zeigen von abzählbarer und unabzählbarer Unendlichkeit von Mengen

Übungsaufgabe 3 (S. 7)

Rekursive Funktion und ihre Umkehrfunktion, mit Memoizing

$f(n)=\begin{cases}1 \\ f(\frac{n}{2})+1 \\ \frac{1}{f(n-1)}\end{cases}$

def memoize(function): lookup_table = {} def helper(x): if x not in lookup_table: lookup_table[x] = function(x) return lookup_table[x] return helper @memoize def recursive(n): if n == 1: return 1 elif n % 2 == 0: return recursive((n/2)) + 1 else: return 1 / recursive(n-1) # Disclaimer: Does not seem to work for 4/3. Unsure, if bug in code or something to do with how Python handles floating point numbers. @memoize def inverse(n): if n == 1: return 1 elif n < 1: return inverse(1/n) + 1 else: return inverse(n-1) * 2

print(recursive(8))

ausführen

print(inverse(4))

ausführen

Übungsaufgabe 4 (S. 11)

Übungsaufgabe 5 (S. 15)

Primzahlzwillinge

Funktion: Finde für eine natürliche Zahl n die nächsten Primzahlzwillinge

Naive Gedanken dazu:

Wenn es unendlich viele Primzahlen gibt und ich zeigen kann, dass es für jede Primzahl p eine nachfolgende Primzahl q gibt, warum sollte es dann nicht auch unendlich viele Primzahlzwillinge geben? Was spricht denn dagegen, dass es sich dort genauso verhält wie mit den Primzahlen? Gibt es einen Grund, anzunehmen, dass es irgendwann keine Primzahlzwillinge mehr gibt? Und wenn wir davon ausgehen, dass die Menge der Primzahlzwillinge nicht unendlich ist, warum ist dann die Menge der Primzahlen unendlich?

Selbst wenn der Beweis für die Unendlichkeit der Menge der Primzahlenzwillinge bisher noch fehlt, halte ich es für sehr plausibel, dass diese Menge unendlich ist und somit die obige Funktion total und nicht nur partiell ist. Ich denke, dass die Funktion effektiv berechenbar ist, d.h., wir haben noch keinen Algorithmus, noch keinen Beweis gefunden, aber das liegt nicht daran, dass es ihn nicht gibt, sondern es fehlen die mathematischen Werkzeuge.