thema2

Aufgabe 1

Kommentieren Sie. Nennen Sie Beispiele.

1. . Unzugängliches (wenigstens) für Computer
2. . Praktisch Unmöglich

zu 1:

• benötigte Beschreibungssprachen fehlen, dadurch nicht maschinell verarbeitbar bzw. formalisierbar
• es sind umfassende Probleme, mit vielen abhängigen Parametern vorhanden
• durch den Einsatz von künstlicher Intelligenz, Data Mining und Computersimulation wird die Klasse der unzugänglichen Probleme immer mehr verkleinert
• Beispiel: Wird alles gut werden? , Gefällen ihr die Schuhe oder nicht?

zu 2:

• vorhandene Probleme können maschinell beschrieben werden, aber nicht effizient gelöst werden
• Beispiel: Travelling Salesman Problem, Job Shop Scheduling Problem

Aufgabe 2

Wiederholen Sie die Definition von abzählbar unendlichen Mengen

abzählbar unendliche Mengen

Eine Menge ist abzählbar unendlich, wenn es möglich ist eine bijektive Abbildung zwischen der Menge der natürlichen Zahlen und der Menge X zu finden ist.

überabzählbar unendliche Mengen

Wird eine solche Funktion nicht gefunden, ist die zu untersuchenden Menge überabzählbar unendlich.

Aufgabe 3

Cantorisches Diagonalisierungsverfahren 1.Art: Idee und am Beispiel der Wortmenge A*

Motivation dieses Verfahrens ist es, eine sichere Aussage über die Überabzählbarkeit von Mengen zu treffen.

Cantorsches Diagonalisierungsverfahren 1. Art

Diese Art ist konstruktiver Natur und läuft auf das abzählen der Elemente hinaus. Hierbei versucht man die Mengen nach einem bestimmten Prinzip zu ordnen und bildet sie anschließend auf die Menge der natürlichen Zahlen ab.

Beispiel: Wortmenge A*

• Alphabet: A={a,b,c} \rightarrow die Wortmenge wird längen-lexikografisch (nach Länge und Alphabet) geordnet
• Wortmenge: A* = {\epsilon, a,b,c, aa, ab, ac, ba, bc, ca, cb, abc, .....} \rightarrow durch die Verkettung entstehen neue Wörter
• außerdem lassen sich die einzelnen Wörter in Bereiche unterteilen \rightarrow die Länge der einzelnen Bereich entspricht einer Kardinalität von |A|^{\text{Ordnungsrelation des Bereiches}}
  • 1.Bereich: \epsilon
  • 2.Bereich: a,b,c
  • usw.
• somit ist es Möglich jedes Element der Wortmenge auf die natürlichen Zahlen (\mathbb{N}\rightarrow A*) bijektiv abzubilden
• und es kann gesagt werden, dass die Wortmenge A* eine abzählbar unendliche Menge ist

Aufgabe 4

Zeigen Sie, dass die folgenden Mengen abzählbar unendliche Mengen sind \mathbb{Z \quad Q \quad}, die Menge der Primzahlen und die geraden Zahlen.

'''Die Menge der \mathbb{Z} (ganze Zahlen)

• die Elemente der Menge der ganzen Zahlen können auf eine Zahlenstrahl dargestellt werden und somit Indexiert werden
  • 0,-1,1,-2,2,-3,3,......

• f(i)=\begin{cases}-\frac{i}{2} & \text{, wenn }i(i \in \mathbb{N})\text{ gerade}\\\frac{i+1}{2} & \text{, sonst}\end{cases} \rightarrow mit dieser Funktion wird die bijektive Abbildung der natürlichen Zahlen auf die ganzen Zahlen noch einmal verdeutlicht
• somit kann gesagt werden, das die Menge der ganzen Zahlen eine abzählbar unendliche Menge ist

Die Menge der \mathbb{Q} (rationalen Zahlen)

• um zu Beweisen, dass die Menge der rationalen Zahlen abzählbar unendlich ist, kommt das 1.Cantorsche Diagonalverfahren zum Einsatz

• dadurch kann bewiesen werden das die Menge der rationalen Zahlen ein abzählbar unendliche ist

Die Menge der Primzahlen

• Die Menge der natürlichen Zahlen ist eine abzählbar unendliche Menge und die Menge der Primzahlen ist eine Teilmenge der natürlichen Zahlen
  • P \subseteq \mathbb{N}
• Die Menge der ganzen Zahlen ist eine abzählbar unendliche Menge und die Menge der Primzahlen ist eine Teilmenge der genzen Zahlen
• Nach dem Satz von Euklid sind die Primzahlen unendlich

Aufgabe 5

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.