Ü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}:

Beweisen mit Cantor 1. Art:

Zuerst betrachtet man die Menge der positiven rationalen Zahlen \Q⁺.

Die Brüche lassen sich in einem zweidimensionalen Schema anordnen, sodass folgende Tabelle entsteht:

Die Brüche lassen sich diagonal abzählen. Dabei blendet man die ungekürzten Brüche aus, da sie sich in den Äquivalenzklassen der entsprechenden gekürzten Brüche befinden.

Auf diese Weise erhält man eine Abzählung der positiven rationalen Zahlen:

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