BuK-Übung02
Aus ProgrammingWiki
Inhaltsverzeichnis |
Intuitiver Algorithmusbegriff
Prinzipell Unlösbares
- Unzugängliches (wenigstens) für Computer
- Praktisch Unmögliches
Aufgabe 1 (Robert Rosenberger, Stefan Scheumann)
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 (Tobias Salzmann, Ronald Krause)
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[1] der Welt, mit 10 510 TFLOPS, ca. 1 000 000 Sekunden $\approx 11 \frac{1}{2}$ Tage. Nicht nur die Leistung spielt hierbei eine entscheidende Rolle, sondern auch der Verbrauch des Speichers. Geht man bei der Speicherung davon aus, dass ein Zug, also ein Zustand, 1 Byte Speicher benötigt so würde der Speicherverbrauch $\approx 10^{18}$ Bytes benötigen.
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. Geht man wie oben davon aus, dass 1 Byte pro Zug benötigt werden, so beträgt der notwendige Speicher $\approx 10^{128}$ Bytes.
Hinweis: Durchschnittlich werden 40 Züge für eine Schachpartie benötigt.
Abzählbarkeit unendlicher Mengen
Absolute Unlösbarkeit
Aufgabe 3 (Ingo Körner, Christof Ochmann)
Zeigen Sie, dass die folgenden Mengen abzählbar unendlich sind: $\Z, \Q$, die Menge der Primzahlen, die geraden Zahlen.
Für $\Z$:
| 0 | 1 | 2 | 3 | 4 | 5 | ... |
| 0 | 1 | -1 | 2 | -2 | 3 | ... |
$$f(n) = \begin{cases}
-\frac{n}{2}, & \text{wenn n gerade};\\
\lceil \frac{n}{2} \rceil, & \text{sonst }.\\
\end{cases}$$
Für $\Q$:
| $\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 (Max Wielsch, Raik Bieniek)
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.
Gegeben: $m_{i}: ℕ → M_{i}; sujektiv$ existiert nach Definition von „abzählbare Mengen“
Gesucht: $n: ℕ → \bigcup_{n=1}^\infty {M_{n}}; sujektiv$
Cantorsches Diagonalisierungsverfahren 1. Art:
| Abzählfunktion \ Element der Menge | 1 | 2 | 3 | 4 | … |
| $m_1$ | $m_{1}(1) = n(1)$ | $m_{1}(2) = n(2)$ | $m_{1}(3) = n(6)$ | $m_{1}(4) = n(7)$ | … |
| $m_2$ | $m_{2}(1) = n(3)$ | $m_{2}(2) = n(5)$ | $m_{2}(3) = n(8)$ | $m_{2}(4) = n(14)$ | … |
| $m_3$ | $m_{3}(1) = n(4)$ | $m_{3}(2) = n(9)$ | $m_{3}(3) = n(13)$ | $m_{3}(4) = n(18)$ | … |
| $m_4$ | $m_{4}(1) = n(10)$ | $m_{4}(2) = n(12)$ | $m_{4}(3) = n(19)$ | $m_{4}(4) = n(25)$ | … |
| $m_n$ | … | … | … | … | … |
Alternativ:
| Abzählfunktion \ Element der Menge | 1 | 2 | 3 | 4 | … |
| $m_1$ | $m_{0}(0) = n(0)$ | $m_{0}(1) = n(2)$ | $m_{0}(2) = n(5)$ | $m_{0}(3) = n(9)$ | … |
| $m_2$ | $m_{1}(0) = n(1)$ | $m_{1}(1) = n(4)$ | $m_{1}(2) = n(8)$ | $m_{1}(3) = n(13)$ | … |
| $m_3$ | $m_{2}(0) = n(3)$ | $m_{2}(1) = n(7)$ | $m_{2}(2) = n(12)$ | $m_{2}(3) = n(18)$ | … |
| $m_4$ | $m_{3}(0) = n(6)$ | $m_{3}(1) = n(11)$ | $m_{3}(2) = n(17)$ | $m_{3}(3) = n(24)$ | … |
| $m_n$ | … | … | … | … | … |
Aufgabe 5 (Jens Heider, Daniel Tasche)
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}$$
Umkehrfunktion:
$$ f^{-1}(n) = \begin{cases}1, & n = 1 \\ f^{-1}(n-1) * 2, & n > 1 \\ f^{-1}(\frac{1}{n}) + 1, & sonst\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.:
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.:
Cantorsches Diagonalisierungsverfahren 2. Art
Aufgabe 6 (Felix Nitsche, Stefan Lüttke)
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:
Methode: Indirekter Beweis
Annahme: $\mathbb{R}$ ist abzählbar unendlich.
Wenn dem so ist,
dann kann man die reelen Zahlen nacheinander auflisten.
$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} ...$
| $n_{1}$ | $\bf n_{11}$ | $n_{12}$ | $n_{13}$ | $n_{14}$ | $...$ | $...$ |
| $n_{2}$ | $n_{21}$ | $\bf n_{22}$ | $n_{23}$ | $n_{24}$ | $...$ | $...$ |
| $n_{3}$ | $n_{31}$ | $n_{32}$ | $\bf n_{33}$ | $n_{34}$ | $...$ | $...$ |
| $n_{4}$ | $n_{41}$ | $n_{42}$ | $n_{43}$ | $\bf n_{44}$ | $...$ | $...$ |
| $...$ | $...$ | $...$ | $...$ | $...$ | $...$ | $...$ |
| $x$ | $x_{1} $ | $x_{2}$ | $x_{3} $ | $x_{4}$ | $\bf x_{5}$ | $...$ |
wobei $x_{i} = (n_{ii} +1)$ $mod 10$ sein soll. Die Veränderung der Ziffern an der Diagonalen der Tabelle bewirkt, dass sich das konstruierte $x$
immer an der jeweiligen Stelle vom veränderten $n_i$ unterscheidet. Daraus folgt, dass sich die konstruierte Zahl $x$ von allen Elementen der Menge
unterscheidet und somit ein Element konstruiert werden kann, das noch nicht aufgelistet wurde. Dies widerspricht allerdings der Definition der
Abzählbarkeit, woraus folgt, dass $\mathbb{R}$ überabzählbar unendlich ist.
Quelle: [2]
Warum gilt $0,\bar{9} = 1$?
(a) Es Gilt: $\frac{1}{3}$ wird als $0,\bar{3}$ in Dezimalschreibweise dargestellt.
(b) Desweiteren gilt: $0,\bar{9} = 0,\bar{3}*3$.
Wenn (a) und (b) gelten, so gilt auch: $0,\bar{9} = \frac{1}{3} * 3 = 1$
