BuK-Übung02
Inhaltsverzeichnis |
Intuitiver Algorithmusbegriff
Prinzipell Unlösbares
- Unzugängliches (wenigstens) für Computer
- Praktisch Unmögliches
Aufgabe 1 (Robert Rosenberger, Stefan Scheumann)
Kommentieren Sie. Nennen Sie Beispiel.
Aufgabe 2 (Tobias Salzmann, Ronald Krause)
Warum ist es so schwierig ein leistungsfähiges Schachprogramm zu entwerfen?
Es ist praktisch unmöglich, wenn man davon ausgeht das ein Spieler beim ersten Zug 20 verschiedene Möglichkeiten besitzt und bei jedem weiteren mindestens 10, könnte man für 10 Züge, also 20 Halbzüge folgendes berechnen:
20^{2}+10^1+10^2+10^3+10^4+10^5+...+10^{18} = 1,11111111 × 10^{18} \approx 10^{18}Möglichkeiten.
Dafür benötigt der schnellste Rechner der Welt, mit 10 510 TFLOPS, ca. 1 000 000 Sekunden \approx 11 \frac{1}{2} Tage.
Erhöht sich die Anzahl der Züge auf 15, also 30 Halbzüge, so ergeben sich
20^{2}+10^1+10^2+10^3+10^4+10^5+...+10^{28} = 1,11111111 × 10^{28} \approx 10^{128}Möglichkeiten.
Hierfür benötigt dieser Rechner ca. 10^{16} Sekunden \approx 316 887 646 Jahre.
Hinweis: Durchschnittlich werden 40 Züge für eine Schachpartie benötigt.
Absolute Unlösbarkeit
Aufgabe 3 (Ingo Körner, Christof Ochmann)
Zeigen Sie, dass die folgenden Mengen abzählbar unendlich sind: \Z, \Q, die Menge der Primzahlen, die geraden Zahlen.
Aufgabe 4 (Max Wielsch, Raik Bieneck)
Beweisen Sie den folgenden Satz: Wenn M_{1}, M_{2}, M_{3} ... abzählbare Mengen sind, dann ist auch die Menge \bigcup_{n=1}^\infty {M_{n}} abzählbar.
Aufgabe 5 (Jens Heider, Daniel Tasche)
Verifizieren Sie, dass die folgende Funktion f:\N^+ \rightarrow \Q^+ eine bijektive Funktion ist und implementieren Sie eine Prozedur, die die zugehörige Umkehrfunktion f^{-1} berechnet.
f(n) = \begin{cases} 1, & \text{wenn } n=1;\\ f(\frac{n}{2})+1, & \text{wenn } n \text{ gerade};\\ \frac{1}{f(n-1)}, & \text{wenn } n \text{ ungerade}. \end{cases}- Schreiben Sie als erstes eine Scheme-Prozedur für f und führen Sie einige rekursive Berechnungen aus.
- Berechnen Sie f(n) für n = 1,2,....,7 mit Hand.
- Verbessern Sie die Effizienz der Prozedur für f mittels memoizing.
Cantorsches Diagonalisierungsverfahren 2. Art
Aufgabe 6 (Felix Nitsche, Stefan Lüttke)
Zeigen Sie, dass die Menge der reellen Zahlen überabzählbar unendlich ist.
Hinweis: Es reicht schon aus zu zeigen, dass es im Intervall [0, 1] überabzählbar unendlich viele reelle Zahlen gibt.