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?

=== 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.