BuK-Übung02
Inhaltsverzeichnis |
Intuitiver Algorithmusbegriff
Prinzipell Unlösbares
- Unzugängliches (wenigstens) für Computer
- Praktisch Unmögliches
Aufgabe 1
Kommentieren Sie. Nennen Sie Beispiel.
Aufgabe 2
Warum ist es so schwierig ein leistungsfähiges Schachprogramm zu entwerfen?
Absolute Unlösbarkeit
Aufgabe 3
Zeigen Sie, dass die folgenden Mengen abzählbar unendlich sind: \Z, \Q, die Menge der Primzahlen, die geraden Zahlen.
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.
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.
Cantorsches Diagonalisierungsverfahren 2. Art
Aufgabe 6
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.