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