uebung2

Aus ProgrammingWiki
< BuK < IIm12 < Studenten < sifedeut
Archivierte Version vom 2013-04-02T09:29:18+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


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^*: