uebung2
Inhaltsverzeichnis |
Übungsaufgaben - Berechenbarkeitsbegriff
| Definition der Berechenbarkeit |
| Eine Funktion f ist berechenbar, wenn es einen Algorithmus gibt, der für jedes x \in D(f) den zugehörigen Funktionswert f(x) effektiv* ermittelt. |
*Effektiv bedeutet, dass nicht zwingend ein entsprechendes Programm vorliegen muss.
Aufgabe 1
Unzulängliches (wenigstens) für Computer
- es fehlt eine Beschreibungssprache \Rightarrow nicht maschinell verarbeitbar
- Probleme/Aufgaben sind oft komplex und besitzen viele (abhängige) Parameter
- Beispiele: "Gefallen ihr die Blumen?", "Werden alle Ostereier dieses Jahr verkauft?"
- mögliche Verkleinerung dieser Probleme (Problemklasse): Einsatz von KI, Simulationen, Wahrscheinlichkeitsrechnung
Praktisch Unmöglich
- das sind Probleme die maschinell beschreibbar, jedoch aufgrund begrenzter Ressourcen nicht effizient lösbar sind.
- Beipsiele: n-Damen-Problem, Traveling-Salesman-Problem in großen Dimensionen und mit mehreren Parametern (z.B. Zeitpunkte), Stundenplan-Problem
Wdh. abzählbar unendliche Menge Ist eine bijektive Abbildung der natürlichen Zahlen auf eine Menge M (es reicht auch schon surjektiv)
Cantor 1. Art
Ist ein mathematisches Beweisverfahren, mit dem man zeigen kann, dass die Menge der rationalen Zahlen abzählbar unendlich ist.
Am Beispiel von A^*:
Alphabet: A=\{a,b,c\}
A^* wird längen-lexikografisch geordnet:
A^*=\{\epsilon,a,b,c,aa,ab,ac,ba,bb,ba,ca,cb,cc,...\}Die Menge A^* lässt sich in Gruppen unterteilen:
Gruppe 1: \epsilon
Gruppe 2: a,b,c
Gruppe 3: aa,ab,ac,ba,bb,ba,ca,cb,cc
Die Länge der Gruppen entspricht der Kardinalität von A\text{: }|A|^{\text{Ordnungsnummer der Gruppe}}
So geordnet lässt sich jedem Element von A^* Element der natürlichen Zahlen zuordnen.
Diese Zuordnung ist bijektiv \Rightarrow A^* ist abzählbar unendlich