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

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

1. Cantorisches Diagonalisierungsverfahren 1.Art: Idee und am Beispiel der Wortmenge A*
2. Zeigen Sie, dass die folgenden Mengen abzählbar unendliche Mengen sind \mathbb{Z \quad Q \quad}, die Menge der Primzahlen und die geraden Zahlen.
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.