BuK/IIm18/Vorlesung2

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
== Intuitiver Algorithmusbegriff ==

=== Prinzipell Unlösbares ===

# Unzugängliches (wenigstens) für Computer
# Praktisch Unmögliches

==== 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?



== 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.