uebung2
Aus ProgrammingWiki
Inhaltsverzeichnis |
Übungsaufgaben - Berechenbarkeitsbegriff
| Definition der Berechenbarkeit |
| Eine Funktion |
*Effektiv bedeutet, dass nicht zwingend ein entsprechendes Programm vorliegen muss.
Aufgabe 1
Unzulängliches (wenigstens) für Computer
- es fehlt eine Beschreibungssprache
nicht maschinell verarbeitbar
- Probleme/Aufgaben sind oft komplex und besitzen viele (abhängige) Parameter
- Beispiele: "Gefallen ihr die Blumen?", "Werden alle Ostereier dieses Jahr verkauft?"
- mögliche Verkleinerung dieser Probleme (Problemklasse): Einsatz von KI, Simulationen, Wahrscheinlichkeitsrechnung
Praktisch Unmöglich
- das sind Probleme die maschinell beschreibbar, jedoch aufgrund begrenzter Ressourcen nicht effizient lösbar sind.
- Beipsiele: n-Damen-Problem, Traveling-Salesman-Problem in großen Dimensionen und mit mehreren Parametern (z.B. Zeitpunkte), Stundenplan-Problem
Wdh. abzählbar unendliche Menge
Ist eine bijektive Abbildung der natürlichen Zahlen auf eine Menge (es reicht auch schon surjektiv)
Cantor 1. Art
Ist ein mathematisches Beweisverfahren, mit dem man zeigen kann, dass die Menge der rationalen Zahlen abzählbar unendlich ist.
Am Beispiel von :
Alphabet:
wird längen-lexikografisch geordnet:
Die Menge lässt sich in Gruppen unterteilen:
Gruppe 1:
Gruppe 2:
Gruppe 3:
Die Länge der Gruppen entspricht der Kardinalität von
So geordnet lässt sich jedem Element von Element der natürlichen Zahlen zuordnen.
Diese Zuordnung ist bijektiv ist abzählbar unendlich
Aufgabe 2 (Deutschmann, Horbach)
Zeigen Sie, dass die folgenden Mengen abzählbar unendlich sind: , die Menge der Primzahlen, die geraden Zahlen
Ganze Zahlen :
Mit der Funktion , mit
können alle ganzen Zahlen bijektiv auf die natürlichen Zahlen abgebildet werden.
ist abzählbar unendlich.
| 0 | 1 | 2 | 3 | 4 | 5 | ... | |
| 0 | 1 | -1 | 2 | -2 | 3 | ... |
Rationale Zahlen :
Beweisen mit Cantor 1. Art:
Zuerst betrachtet man die Menge der positiven rationalen Zahlen $\Q⁺$.
Die Brüche lassen sich in einem zweidimensionalen Schema anordnen, sodass folgende Tabelle entsteht:
| $\N$\$\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 | ... |
| ... | ... | ... | ... | ... | ... | ... |
Die Brüche lassen sich diagonal abzählen. Dabei blendet man die ungekürzten Brüche aus, da sie sich in den Äquivalenzklassen der entsprechenden gekürzten Brüche befinden.
Auf diese Weise erhält man eine Abzählung der positiven rationalen Zahlen:
| 1 | 2 | 3 | 4 | 5 | ... | |
| 1 | $\frac{1}{2}$ | 2 | 3 | $\frac{1}{3}$ | ... |
Durch das Beschränken auf den ungekürzten Repräsentanten der jeweiligen Äquivalenzklasse eines Bruches wird die bijektive Abbildung auf die natürlichen Zahlen erreicht.
Um nun auf auf den gesamten Bereich der rationalen Zahlen zu verallgemeinern, wird die Abzählung erweitert, indem vor die Eins die Null und hinter jede Zahl ihr Negatives ergänzt wird.
| 1 | 2 | 3 | 4 | 5 | ... | |
| 0 | 1 | -1 | $\frac{1}{2}$ | $-\frac{1}{2}$ | ... |
Primzahlen:
- Die Menge der Primzahlen ist nach Euklid unendlich.
- Die Menge der Primzahlen ist eine Teilmenge der natürlichen Zahlen
- Die Menge der natürlichen Zahlen ist abzählbar unendlich.
Also ist jede unendliche Teilmenge der nat. Zahlen auch abzählbar unendlich.
Gerade Zahlen:
Die geraden Zahlen sind eine Teilmenge der ganzen Zahlen und per Definition unendlich. Die ganzen Zahlen sind nachgewiesen abzählbar unendlich und somit gilt das auch für die geraden Zahlen.
Aufgabe 3
Beweisen Sie den folgenden Satz:
Wenn abzählbare Mengen sind, dann ist auch die Menge
abzählbar.
Das kann mit Cantor 1. Art bewiesen werden.
Die Mengen sind abzählbar und somit lassen sie sich in geordneter Reihenfolge aufschreiben.
| $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)$ | … |
| … | … | … | … | … |
Mit dem Verfahren kann man an jedes Element der Teilmengen gelangen und somit ist die Vereinigungsmenge abzählbar.
Aufgabe 4
Verizieren Sie, dass die folgende Funktion eine bijektive Funktion ist und implementieren Sie eine Prozedur, die die zugehörige Umkehrfunktion
berechnet.
- Schreiben Sie als erstes eine Scheme-Prozedur für
und führen Sie einige rekursive Berechnungen aus.
- Berechnen Sie
für
mit der Hand
- Verbessern Sie die Effizienz der Prozedur für
$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}$
Aufgabe 5
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:
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. Durch diese Definition wird ersichtlich, dass man immer eine Zahl $x$ findet, die nicht innerhalb $\mathbb{R}$ ist.
Wenn es immer eine Zahl $x$ gibt, die nicht in der Menge ist, dann ist $\mathbb{R}$ auch nicht abzählbar unendlich und damit überabzählbar unendlich.
