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