uebung2

Aus ProgrammingWiki
< BuK < IIm12 < Studenten < sifedeut
Archivierte Version vom 2013-04-02T09:18:22+00:00. Aktuelle Version

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