BuK/IIm12/Studenten/sifedeut/uebung2

Wiki-Quelltext dieser Seite.

= Übungsaufgaben - Berechenbarkeitsbegriff =

{| class="wikitable"
| '''Definition der Berechenbarkeit'''
|-
| Eine Funktion <math>f</math> ist berechenbar, wenn es einen Algorithmus gibt, der für jedes <math>x \in D(f)</math> den zugehörigen Funktionswert <math>f(x)</math> effektiv<sup>*</sup> ermittelt.
|}
<sup>*</sup>''Effektiv bedeutet, dass nicht zwingend ein entsprechendes Programm vorliegen muss.''

== Aufgabe 1 ==

=== Unzulängliches (wenigstens) für Computer ===
* es fehlt eine Beschreibungssprache <math>\Rightarrow</math> nicht maschinell verarbeitbar
* Probleme/Aufgaben sind oft komplex und besitzen viele (abhängige) Parameter
* Beispiele: "Gefallen ihr die Blumen?", "Werden alle Ostereier dieses Jahr verkauft?"
* mögliche Verkleinerung dieser Probleme (Problemklasse): Einsatz von KI, Simulationen, Wahrscheinlichkeitsrechnung

=== Praktisch Unmöglich ===
* das sind Probleme die maschinell beschreibbar, jedoch aufgrund begrenzter Ressourcen nicht effizient lösbar sind.
* Beipsiele: n-Damen-Problem, Traveling-Salesman-Problem in großen Dimensionen und mit mehreren Parametern (z.B. Zeitpunkte), Stundenplan-Problem


----

Wdh. abzählbar unendliche Menge
Ist eine bijektive Abbildung der natürlichen Zahlen auf eine Menge <math>M</math> (es reicht auch schon surjektiv)

== Cantor 1. Art ==
Ist ein mathematisches Beweisverfahren, mit dem man zeigen kann, dass die Menge der rationalen Zahlen abzählbar unendlich ist.

Am Beispiel von <math>A^*</math>:

Alphabet: <math>A=\{a,b,c\}</math>

<math>A^*</math> wird längen-lexikografisch geordnet:

<math>A^*=\{\epsilon,a,b,c,aa,ab,ac,ba,bb,ba,ca,cb,cc,...\}</math>

Die Menge <math>A^*</math> lässt sich in Gruppen unterteilen:

Gruppe 1: <math>\epsilon</math>

Gruppe 2: <math>a,b,c</math>

Gruppe 3: <math>aa,ab,ac,ba,bb,ba,ca,cb,cc</math>

Die Länge der Gruppen entspricht der Kardinalität von <math>A\text{: }|A|^{\text{Ordnungsnummer der Gruppe}}</math>

So geordnet lässt sich jedem Element von <math>A^*</math> Element der natürlichen Zahlen zuordnen. 

Diese Zuordnung ist bijektiv <math>\Rightarrow A^*</math> ist abzählbar unendlich

== Aufgabe 2 (Deutschmann, Horbach) ==
Zeigen Sie, dass die folgenden Mengen abzählbar unendlich sind: <math>\mathbb{Z}, \mathbb{Q}</math>, die Menge der Primzahlen, die geraden Zahlen

Ganze Zahlen <math>\mathbb{Z}</math>:

Mit der 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 alle ganzen Zahlen bijektiv auf die natürlichen Zahlen abgebildet werden. <math>\Rightarrow \mathbb{N}</math> ist abzählbar unendlich.

{| 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 || ...
|-
|}

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

== Aufgabe 4 ==
Verizieren Sie, dass die folgende Funktion <math>f : \mathbb{N}^+ \to \mathbb{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