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

'''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.

# 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.