Vorlesung2

Intuitiver Algorithmusbegriff

Prinzipell Unlösbares

1. Unzugängliches (wenigstens) für Computer
2. Praktisch Unmögliches

Aufgabe 1

Kommentieren Sie. Nennen Sie Beispiele.

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?

Abzählbarkeit unendlicher Mengen

Absolute Unlösbarkeit

Aufgabe 3

Zeigen Sie, dass die folgenden Mengen abzählbar unendlich sind: \Z, \Q, die Menge der Primzahlen, die geraden Zahlen.

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.