BuK/IIm11/BuK-Übung02
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
== 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 Beispiele.
===== Unzugängliches (wenigstens) für Computer =====
* Durch fehlende Beschreibungssprache nicht maschinell verarbeitbar / formalisierbar.
* Viele Probleme vielschichtig und mit vielen (abhängigen) Parametern.
* Simulationen und KI ermöglichen ein Erschließen dieses Problembereichs und tragen somit zur Verkleinerung dieser Problemklasse bei.
* Beispiele: "Mag sie mich?", "Wer gewinnt am Samstag das Fussballspiel?"
===== Praktisch Unmögliches =====
* Probleme, die maschinell beschreibar jedoch nicht effizient lösbar sind (Grenzen vorhandener Ressourcen).
* Beispiele: Leistungsfähiges Schachprogramm, n-Queens-Problem und Rundreiseproblem in größeren Dimensionen und im letzteren Fall mit mehreren Parametern.
==== 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 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 <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.
'''Für''' $\Z$:
{| border="1" cellpadding="5" cellspacing="0"
|-
|| 0 || 1 || 2 || 3 || 4 || 5 || ...
|-
|| 0 || 1 || -1 || 2 || -2 || 3 || ...
|-
|}
'''Für''' $\Q$:
{| border="1" cellpadding="5" cellspacing="0"
!$\Z$\$\N$
!$1$
!$2$
!$3$
!$4$
!$5$
|-
|| 1 || 1/1 || 1/2 || 1/3 || 1/4 || 1/5
|-
|| 2 || 2/1 || 2/2 || 2/3 || 2/4 || 2/5
|-
|| 3 || 3/1 || 3/2 || 3/3 || 3/4 || 3/5
|-
|| 4|| 4/1 || 4/2 || 4/3 || 4/4 || 4/5
|-
|| 5 || 5/1 || 5/2 || 5/3 || 5/4 || 5/5
|-
|}
Es werden mit Hilfe des ersten Cantorschen Diagonalisierungsverfahren alle Zahlen erreicht.
'''Für die Menge der Primzahlen:'''
1. Die Menge der Primzahlen P ist unendlich (nach Satz von Euklid).
2. Die Menge der Primzahlen P ist abzählbar unendlich, da gilt: P $\subset \N$.
'''Für die Menge der geraden Zahlen:'''
1. Die geraden Zahlen G sind unendlich (per Definition) und abzählbar unendlich, da gilt: G $\subset \Z$.
==== Aufgabe 4 <tt>(Max Wielsch, Raik Bieniek)</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.
$m_{1}(i), m_{2}(i), m_{3}(i) …; i ∈ ℕ$ seien Indexfunktionen für $M_{1}, M_{2}, M_{3} …$
$n(i); i ∈ ℕ$ sei Indexfunktion für $\bigcup_{n=1}^\infty {M_{n}}$ (gesucht)
Cantorsches Diagonalisierungsverfahren 1. Art:
{| border="1" cellpadding="5" cellspacing="0"
|-
||$m_{1}(0) = n(0)$ || $m_{1}(1) = n(1)$ || $m_{1}(2) = n(5)$ || $m_{1}(3) = n(6)$ ||…
|-
||$m_{2}(0) = n(2)$ || $m_{2}(1) = n(4)$ || $m_{2}(2) = n(7)$ || $m_{2}(3) = n(13)$ || …
|-
||$m_{3}(0) = n(3)$ || $m_{3}(1) = n(8)$ || $m_{3}(2) = n(12)$ || $m_{3}(3) = n(17)$ || …
|-
||$m_{4}(0) = n(9)$ || $m_{4}(1) = n(11)$ || $m_{4}(2) = n(18)$ || $m_{4}(3) = n(24)$ || …
|-
||…|| … || … || … || …
|-
|}
<div align="right">$\square$</div>
Alternativ:
{| border="1" cellpadding="5" cellspacing="0"
|-
||$m_{0}(0) = n(0)$ || $m_{0}(1) = n(2)$ || $m_{0}(2) = n(5)$ || $m_{0}(3) = n(9)$ ||…
|-
||$m_{1}(0) = n(1)$ || $m_{1}(1) = n(4)$ || $m_{1}(2) = n(8)$ || $m_{1}(3) = n(13)$ || …
|-
||$m_{2}(0) = n(3)$ || $m_{2}(1) = n(7)$ || $m_{2}(2) = n(12)$ || $m_{2}(3) = n(18)$ || …
|-
||$m_{3}(0) = n(6)$ || $m_{3}(1) = n(11)$ || $m_{3}(2) = n(17)$ || $m_{3}(3) = n(24)$ || …
|-
||…|| … || … || … || …
|-
|}
<code id="4f71a91f0d21f">;Gibt die Abzählfunktion M_n zurück
(define m
(lambda (setIndex)
(lambda (elementIndex)
(string-append
"Menge "
(number->string setIndex)
" Element "
(number->string elementIndex)))))
; basiert auf
; http://de.wikipedia.org/w/index.php?title=Cantorsche_Paarungsfunktion&oldid=95121801#Pascal-Programm_zur_Berechnung_der_Umkehrung
; function F(Z : Integer) : Integer;
; begin
; F := Z * (Z + 1) div 2
; end;
(define f
(lambda (z)
(* z (/ (+ z 1) 2))))
; function Q(Z : Integer) : Integer;
; var
; V : Integer;
; begin
; V := 0;
; while F(V) <= Z do
; V := V + 1;
; Q := V - 1
; end;
(define tmp
(lambda (v z)
(cond
((<= (f v) z) (tmp (+ v 1) z))
(else (- v 1)))))
(define q
(lambda (z)
(tmp 0 z)))
; begin
; J := Q(I);
; Y := I - F(J);
; X := J - Y;
; end;
(define n
(lambda (i)
(let ((j (q i)))
(let ((y (- i (f j))))
(let ((x (- j y)))
((m x) y))))))</code>
<run id="4f71a91f0d2c4">(n 11)</run>
==== 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.
'''Lösung zu 1.:'''
<code id="4f69d94623146">
(define f
(lambda (n)
(if (= n 1)
1
(if (= (modulo n 2) 0)
(+ 1 (f (/ n 2)))
(/ 1 (f (- n 1)))
)
)
)
)
</code>
<run id="4f69d946231b0">(f 6)</run>
'''Lösung zu 2.:'''
$f(1) = 1$
$f(2) = 2$
$f(3) = 0,5$
$f(4) = 3$
$f(5) = \frac{1}{3}$
$f(6) = 1,5$
$f(7) = \frac{2}{3}$
'''Lösung zu 3.:'''
<code id="4f715b8c54891">
(import hashtable)
(define table (make-hashtable))
(define false (lambda () #f))
(define f-mem
(lambda (n)
(let ([resultat (hashtable/get table n false)])
(cond
[(= n 1) 1]
[(number? resultat) resultat]
[else
(let([res-berechnet
(if (= (modulo n 2) 0)
(+ 1 (f-mem (/ n 2)))
(/ 1 (f-mem (- n 1)))
)])
(hashtable/put! table n res-berechnet)
res-berechnet
)
]
)
)
)
)
</code>
<run id="4f715b8c54900">(f-mem 999)</run>
== 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.
'''Lösung:'''
Methode: Indirekter Beweis
Annahme: Die Menge der Reelen Zahlen ist abzählbar unendlich.
Daraus folgt: man kann sie nacheinander aufschreiben:
$n_{1} = 0,$ $n_{11}$ $n_{12}$ $n_{13}$ $n_{14} ... $
$n_{2} = 0,$ $n_{21}$ $n_{22}$ $n_{23}$ $n_{24} ... $
$n_{3} = 0,$ $n_{31}$ $n_{32}$ $n_{33}$ $n_{34} ... $
$.$
$.$
$.$
$n_{i} = 0,$ $n_{i1}$ $n_{i2}$ $n_{i3}$ $n_{i4} ... $
Konstruktion einer Zahl $x$ mit $x \in [0 ; 1]$, die nicht in der Menge vorkommen kann:
$x = 0,$ $x_{1}$ $x_{2}$ $x_{3}$ $x_{4} ...$
wobei $x_{i} = (n_{ii} +1)$ $mod 10$ sein soll. Durch diese Definition wird ersichtlich, dass man immer eine Zahl $x_{i}$ findet, die nicht innerhalb der Menge ist.
'''Quelle:'''
[http://www.mathepedia.de/Ueberabzaehlbar_unendlich.aspx]