BuK/IIm12/Studenten/siclsche/thema2

Wiki-Quelltext dieser Seite.

== Aufgabe 1 ==
Kommentieren Sie. Nennen Sie Beispiele.

#. Unzugängliches (wenigstens) für Computer
#. 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
# Cantorisches Diagonalisierungsverfahren 1.Art: Idee und am Beispiel der Wortmenge A*
# Zeigen Sie, dass die folgenden Mengen abzählbar unendliche Mengen sind  $\mathbb{Z \quad Q \quad}$, die Menge der Primzahlen und die geraden Zahlen. 
# 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.

'''zu 1:'''
 
'''abzählbar unendliche Mengen'''

Eine Menge ist abzählbar unendlich, wenn es möglich ist eine bijektive Abbildung zwischen der Menge der $\mathbb{N \quad}$ 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.

'''zu 2:'''

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 $\mathbb{N \quad}$ 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|^{Ordnungsrelation des Bereiches}$
** 1.Bereich: $\epsilon$
** 2.Bereich: a,b,c 
** usw.