BuK/IIm18/Vorlesung2

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
== 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. <ref>[https://de.wikipedia.org/wiki/Nenad_Petrovi%C4%87] . Abgerufen am 22. März 2019.</ref>

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