uebung2
Inhaltsverzeichnis |
Aufgabe 1
- Unzugängliches (wenigstens) für Computer
- Praktisch Unmögliches
Kommentieren Sie. Nennen Sie Beispiele.
Lösung:
Aufgabe 2
Warum ist es so schwierig ein leistungsfähiges Schachprogramm zu entwerfen?
Lösung:
Aufgabe 3
Zeigen Sie, dass die folgenden Mengen abzählbar unendlich sind: \Z, \Q, die Menge der Primzahlen, die geraden Zahlen.
Lösung:
Aufgabe 4
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.
Lösung:
Aufgabe 5
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.
Lösung:
Aufgabe 6
Zeigen Sie, dass \mathbb{R} überabzählbar unendlich ist.
Hinweis: Es reicht schon aus zu zeigen, dass es im Intervall [0, 1] überabzählbar unendlich viele reelle Zahlen gibt.
Lösung: