Übungsaufgaben - Berechenbarkeitsbegriff

^*Effektiv bedeutet, dass nicht zwingend ein entsprechendes Programm vorliegen muss.

Aufgabe 1

Unzulängliches (wenigstens) für Computer

• es fehlt eine Beschreibungssprache \Rightarrow 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 M (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 A^*:

Alphabet: A=\{a,b,c\}

A^* wird längen-lexikografisch geordnet:

Die Menge A^* lässt sich in Gruppen unterteilen:

Gruppe 1: \epsilon

Gruppe 2: a,b,c

Gruppe 3: aa,ab,ac,ba,bb,ba,ca,cb,cc

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

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

Diese Zuordnung ist bijektiv \Rightarrow A^* ist abzählbar unendlich

Aufgabe 2 (Deutschmann, Horbach)

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

Ganze Zahlen \mathbb{Z}:

Mit der Funktion f(i)=\begin{cases}-\frac{i}{2} & \text{, wenn }i\text{ gerade}\\\frac{i+1}{2} & \text{, sonst}\end{cases}, mit i \in \mathbb{N} können alle ganzen Zahlen bijektiv auf die natürlichen Zahlen abgebildet werden. \Rightarrow \mathbb{N} ist abzählbar unendlich.

Rationale Zahlen \mathbb{Q}:

Aufgabe 3

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 4

Verizieren Sie, dass die folgende Funktion f : \mathbb{N}^+ \to \mathbb{Q}^+ eine bijektive Funktion ist und implementieren Sie eine Prozedur, die die zugehörige Umkehrfunktion f^{-1} berechnet.

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