Vorlesung2
Aus ProgrammingWiki
Inhaltsverzeichnis |
Intuitiver Algorithmusbegriff
Prinzipell Unlösbares
Aufgabe 1
Kommentieren Sie. Nennen Sie Beispiele.
- grundätzlich Probleme mit vielen Abhängigkeiten und verschiedenen Parametern
- durch KI wird die Anzahl der potentiell unlösbaren Probleme verkleinert
Unzugängliches (wenigstens) für Computer
- Probleme, die in keiner Sprache ausreichend beschrieben werden können
Beispiele:
- Gefühlsentscheidungen,
- politische Entscheidungen (zum Beispiel Konflikt Israel Palästina),
- Probleme, die in der Zukunft liegen (Lottozahlen)
Praktisch Unmögliches
- Probleme, deren Lösung aus Mangel an Zeit und/oder Ressourcen nicht möglich ist
Beispiele:
- n-Damen-Problem, Graph Coloring-Problem mit hoher Komplexität
Aufgabe 2
Warum ist es so schwierig ein leistungsfähiges Schachprogramm zu entwerfen?
Das Schachfeld besitzt eine Größe von 8x8 Feldern. Jeder Spieler hat 8 Bauern, 2 Türme, 2 Läufer, 2 Springern, eine Königin und einen König. Jeder dieser Gruppen kann sich unterschiedlich auf dem Spielfeld fortbewegen.
Nach den ersten beiden Zügen ist es möglich 400 verschiedene Stellungen zu bilden. Laut Petrović ist es möglich mit den 32 Spielfiguren 10^32 legale Stellungen aufzubauen.Quelle: [1] Mit der heutigen Technik ist noch nicht möglich aus jeden Zug, den Zweig für alle nachfolgenden Züge und die Auswahl des daraus besten Zuges anhand aller Möglichen, zu berechnen.
Abzählbarkeit unendlicher Mengen
Absolute Unlösbarkeit
Aufgabe 3
Zeigen Sie, dass die folgenden Mengen abzählbar unendlich sind: ,
, die Menge der Primzahlen, die geraden Zahlen.
Wiederholung: Mengen sind abzählbar unendlich, wenn es eine bijektive Funktion gibt, die die natürlichen Zahlen auf die besagte Menge abbildet.
Für Ganze Zahlen
Mit der bijektiven Funktion $f:\mathbb{N}\mapsto\mathbb{Z}$ mit
können die ganzen Zahlen auf die natürlichen Zahlen abgebildet werden.
| 0 | 1 | 2 | 3 | 4 | 5 | ... | |
| 0 | 1 | -1 | 2 | -2 | 3 | ... |
Das zeigt, dass die ganzen Zahlen abzählbar unendlich sind.
Für Rationalen Zahlen
Für den Beweis, wird das Cantorsche Diagonalisierungsverfahren 1. Art benutzt.
Als erstes wird gezeigt, dass es eine bijektive Abbildung von gibt.
Dazu werden die Brüche mittels p und q dargestellt, wobei p und q natürliche Zahlen sind.
Damit ergibt sich folgende Zuordnung:
| $\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 | ... |
| ... | ... | ... | ... | ... | ... | ... |
Nun ist es möglich die Brüche diagonal abzuzählen, dabei werden die ungekürzten Brüche ausgelassen, 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}$ | ... |
Um eine Abbildung auf die gesamten rationalen Zahlen zu erhalten, müssen noch die Null, sowie die negativen rationalen Zahlen betrachtet werden. Die Null wird als erstes Element der ersten natürlichen Zahl zugeordnet. Anschließend wird nach jeder positiv rationalen Zahl, die zugehörige negative rationale Zahl einer natürlichen Zahl zugeordnet. Als Ergbnis besitzt man eine Abbildung mit der man jeder rationalen Zahl eine natürliche Zahl zuordnen kann.
| 1 | 2 | 3 | 4 | 5 | ... | |
| 0 | 1 | -1 | $\frac{1}{2}$ | $-\frac{1}{2}$ | ... |
Die mathematische Funktion dafür lautet:
mit
und
Für die Menge der Primzahlen
- Primzahlen sind nach dem Satz von Euklid unendlich
- Primzahlen sind eine Teilmenge der natürlichen Zahlen
- Die natürlichen Zahlen sind abzählbar unendlich.
Daraus folgt: Primzahlen sind abzählbar unendlich.
Für die geraden Zahlen
Die geraden Zahlen sind eine Teilmenge der ganzen Zahlen , welche nachgewiesenermaßen abzählbar unendlich sind.
Die geraden Zahlen sind somit ebenfalls abzählbar unendlich.
Aufgabe 4
Beweisen Sie den folgenden Satz: Wenn abzählbare Mengen sind, dann ist auch die Menge
abzählbar.
Um diesen Sachverhalt zu beweisen, wird das Cantorsche Diagonalverfahren 1. Art angewandt. Die einzelnen Mengen werden aufgezählt und deren Elemente werden nun durchnummeriert mit den natürlichen Zahlen. Damit ist sichergestellt, dass jedem Element eine natürliche Zahl zuordnet. Damit ist eine Abbildung gefunden, die die Vereinigung von abzählbaren Mengen auf die natürlichen Zahlen ist.
| 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$ | … | … | … | … | … |
Aufgabe 5
Verifizieren Sie, dass die folgende Funktion eine bijektive Funktion ist und implementieren Sie eine Prozedur, die die zugehörige Umkehrfunktion
berechnet.
Umkehrfunktion:
- 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
Lösung 1:
Lösung 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 3:
Aufgabe 6
Zeigen Sie, dass überabzählbar unendlich ist.
Methode: indirekter Beweis
Folgende Annahme wird getroffen: die Menge ist abzählbar unendlich.
$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} ... $
$.$
$.$
$.$
Dabei sind $n_{ij}$ die Dezimalstellen der reellen Zahlen.
Aus den Diagonalelementen wird eine neue Zahl $x$ mit $x \in [0 ; 1]$ konstruiert, die nicht in der Menge enthalten ist. Die Diagonalelemente sind hier fett hervorgehoben.
$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}$ | $...$ |
Für die Bildungsvorschrift der Zahl $x$ wird festgelegt, das $x_{i} $ = 3 ist, wenn $n_{ii}$ 3 ansonsten ist $x_{i} $ =4.
Mittels dieser Regel kann man eine Zahl erstellen, die sich von allen Zahlen in der Folge in mindestens einer Dezimalstelle unterscheidet.
Daraus ergibt sich ein Widerspruch der Annahme, dass die Menge der reellen Zahlen abzählbar unendlich ist. Somit ist die Menge
überabzählbar unendlich.
