BuK/IIm11/BuK-Übung02

Wiki-Quelltext dieser Seite.

== Intuitiver Algorithmusbegriff ==

=== Prinzipell Unlösbares ===

# Unzugängliches (wenigstens) für Computer
# Praktisch Unmögliches

==== Aufgabe 1 <tt>(Robert Rosenberger, Stefan Scheumann)</tt> ====

Kommentieren Sie. Nennen Sie Beispiel.

==== Aufgabe 2 <tt>(Tobias Salzmann, Ronald Krause)</tt> ====

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  40 Züge, also 80 Halbzüge folgendes berechnen:
$$20^{2}+10^1+10^2+10^3+10^4+10^5+...+10^{78} = 1,11111111 × 10^{78} \approx 10^{78}$$
Möglichkeiten.

=== Absolute Unlösbarkeit ===

==== Aufgabe 3 <tt>(Ingo Körner, Christof Ochmann)</tt> ====

Zeigen Sie, dass die folgenden Mengen abzählbar unendlich sind: $\Z, \Q$, die Menge der Primzahlen, die geraden Zahlen.

==== Aufgabe 4 <tt>(Max Wielsch, Raik Bieneck)</tt> ====

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 <tt>(Jens Heider, Daniel Tasche)</tt> ====

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 <tt>(Felix Nitsche, Stefan Lüttke)</tt> ====

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.