Vorlesung2

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: https://de.wikipedia.org/wiki/Nenad_Petrovi%C4%87 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: \mathbb{Z}, \mathbb{Q}, 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 \mathbb{Z}

Mit der bijektiven Funktion f(i)=\begin{cases}-\frac{i}{2} & \text{, wenn }i\text{ gerade}\\\frac{i+1}{2} & \text{, sonst}\end{cases}, mit i \in \mathbb{N} können die ganzen Zahlen \mathbb{Z} auf die natürlichen Zahlen abgebildet werden.

Das zeigt, dass die ganzen Zahlen abzählbar unendlich sind.

Für Rationalen Zahlen \mathbb{Q}

Für die Menge der Primzahlen

• Primzahlen sind nach dem Satz von Euklid unendlich
• Primzahlen sind eine Teilmenge der natürlichen Zahlen \mathbb{N}
• 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 \mathbb{Z}.

Mit der bijektiven Funktion f(i)=\begin{cases}-\frac{i}{2} & \text{, wenn }i\text{ gerade}\\\frac{i+1}{2} & \text{, sonst}\end{cases}, mit i \in \mathbb{N} können die ganzen Zahlen \mathbb{Z} auf die natürlichen Zahlen abgebildet werden, was zeigt, dass diese abzählbar unendlich sind.

Die geraden Zahlen, als Teilmenge der ganzen Zahlen sind somit ebenfalls abzählbar unendlich.

Aufgabe 4

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

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.

Aufgabe 6

Zeigen Sie, dass \mathbb{R} überabzählbar unendlich ist.