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.'''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: <math>\mathbb{Z}</math>, <math>\mathbb{Q}</math>, 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 <math>\mathbb{Z}</math>'''

Mit der bijektiven Funktion 

<math>f(i)=\begin{cases}-\frac{i}{2} & \text{, wenn }i\text{ gerade}\\\frac{i+1}{2} & \text{, sonst}\end{cases}</math>, mit <math>i \in \mathbb{N}</math> 

können die ganzen Zahlen <math>\mathbb{Z}</math> auf die natürlichen Zahlen abgebildet werden.

{| border="1" cellpadding="5" cellspacing="0"
|-
||<math>\mathbb{N}</math>|| 0 || 1 || 2 || 3 || 4 || 5 || ...
|-
||<math>\mathbb{Z}</math>|| 0 || 1 || -1 || 2 || -2 || 3 || ...
|-
|}

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

'''Für Rationalen Zahlen <math>\mathbb{Q}</math>'''


'''Für die Menge der Primzahlen'''
* Primzahlen sind nach dem Satz von Euklid unendlich
* Primzahlen sind eine Teilmenge der natürlichen Zahlen <math>\mathbb{N}</math> 
* 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 <math>\mathbb{Z}</math>. 

Mit der bijektiven Funktion 

<math>f(i)=\begin{cases}-\frac{i}{2} & \text{, wenn }i\text{ gerade}\\\frac{i+1}{2} & \text{, sonst}\end{cases}</math>, mit <math>i \in \mathbb{N}</math> 

können die ganzen Zahlen <math>\mathbb{Z}</math> auf die natürlichen Zahlen abgebildet werden, was zeigt, dass diese abzählbar unendlich sind.

{| border="1" cellpadding="5" cellspacing="0"
|-
||<math>\mathbb{N}</math>|| 0 || 1 || 2 || 3 || 4 || 5 || ...
|-
||<math>\mathbb{Z}</math>|| 0 || 2 || -2 || 4 || -4 || 6 || ...
|-
|}

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

==== Aufgabe 4  ====
Beweisen Sie den folgenden Satz: Wenn <math>M_{1}, M_{2}, M_{3} ...</math> abzählbare Mengen sind, dann ist auch die Menge <math>\bigcup_{n=1}^\infty {M_{n}}</math> abzählbar.

<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
==== Aufgabe 5 ====
Verifizieren Sie, dass die folgende Funktion <math>f:\N^+ \rightarrow \Q^+</math> eine bijektive Funktion ist und implementieren Sie eine Prozedur, die die zugehörige Umkehrfunktion <math>f^{-1}</math> berechnet.


<math>f(n)=\begin{cases}1 & \text{, wenn n=1}\\f(\frac{n}{2})+1 & \text{, wenn }n\text{ gerade}}\\\frac{1}{f(n-1)} & \text{, wenn }n\text{ ungerade.}\end{cases}</math>


# Schreiben Sie als erstes eine Scheme-Prozedur für <math>f</math> und führen Sie einige rekursive Berechnungen aus.
# Berechnen Sie <math>f(n)</math> für <math>n=1,2,...,7</math> mit der Hand
# Verbessern Sie die Effizienz der Prozedur für <math>f</math> mittels memoizing



<code id="5c9545713f9bb">
(define f 
    (lambda (x) 
        (if (= x 1)
            (1)
            (if (= (modulo x 2) 0)
                (+ 1 (f (/ x 2)))
                (/ 1 (f (- x 1)))))))
</code>
<run id="5c9545713fa30">(f 1)</run>

==== Aufgabe 6 ====

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