BuK/IIm12/Studenten/sifedeut/uebung2

Wiki-Quelltext dieser Seite.

= Übungsaufgaben - Berechenbarkeitsbegriff =

{| class="wikitable"
| '''Definition der Berechenbarkeit'''
|-
| Eine Funktion <math>f</math> ist berechenbar, wenn es einen Algorithmus gibt, der für jedes <math>x \in D(f)</math> den zugehörigen Funktionswert <math>f(x)</math> effektiv<sup>*</sup> ermittelt.
|}
<sup>*</sup>''Effektiv bedeutet, dass nicht zwingend ein entsprechendes Programm vorliegen muss.''

== Aufgabe 1 ==

=== Unzulängliches (wenigstens) für Computer ===
* es fehlt eine Beschreibungssprache <math>\Rightarrow</math> 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 <math>M</math> (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 <math>A^*</math>:

Alphabet: <math>A=\{a,b,c\}</math>

<math>A^*</math> wird längen-lexikografisch geordnet:

<math>A^*=\{\epsilon,a,b,c,aa,ab,ac,ba,bb,ba,ca,cb,cc,...\}</math>

Die Menge <math>A^*</math> lässt sich in Gruppen unterteilen:

Gruppe 1: <math>\epsilon</math>

Gruppe 2: <math>a,b,c</math>

Gruppe 3: <math>aa,ab,ac,ba,bb,ba,ca,cb,cc</math>

Die Länge der Gruppen entspricht der Kardinalität von <math>A\text{: }|A|^{\text{Ordnungsnummer der Gruppe}}</math>

So geordnet lässt sich jedem Element von <math>A^*</math> Element der natürlichen Zahlen zuordnen. 

Diese Zuordnung ist bijektiv <math>\Rightarrow A^*</math> ist abzählbar unendlich