Was sind Probleme |:

anchored to [[111.00_anchor]]

Übersicht:

Problem sind etwa das Leben und die damit verbundenen Schwierigkeiten, die den Alltag bedrücken und schwer machen.

Angenommen wir haben eine abstrakte Frage, die wir lösen wollen. Dabei ist die Menge der Eingaben und die gewünschte Ausgabe gefordert. Es gibt dabei verschiedene Probleme, die wir ferner betrachten und bearbeiten möchten:

• Entscheidungsproblem -> also welche Entscheidungen getroffen werden können und wie wir dies mit gegebenen Abhängigkeiten tun können.
• Optimierungsproblemw -> wir haben ein Problem und müssen aus einer großen Grundmenge dann eine optimale Lösung bestimmen
• Suchprobleme

Problem-Definitionen und Instanzen dieser:

[!Definition] Probleme beschreiben ein Problem auf formaler Ebene, heißt sie beschreiben, was existieren / auftreten kann / muss.

Es wird also eine formale Beschreibung und Definition eines Problemes vorgenommen.

[!Definition] Instanz eines Problemes Eine Instanz hingegen zielt darauf ab einn konkreten Fall eines Problemes betrachten zu können.

Das heißt etwa, das wir ein explizites Array sortieren möchten.

Abstrakt können wir dann für das Problem sagen: -> Wie ist die Laufzeit des Problems? -> was sind Worst-Case / Best-Case? Diese Betrachtungen lassen sich nicht auf eine Instanz beziehen, da hier die Laufzeit von weiteren Aspekten abhängt. Jedoch können wir sagen, was Best / Worst-Case Situationen sein können.

etwa Sortieren einer Liste mit Bubblesort und der Array ist genau andersherum sortiert –> Worst case

Aus dieser Betrachtung heraus können dann ferner die Themen betrachtet werden:

• [[111.06_algo_runtimeanalysis]] –> Wir können Best / Worst-Case Szenarien dieser Probleme betrachten
• [[111.99_algo_ProblemComplexity]] –> Die Schwierigkeit eines abstrakten Problems wird sich auch auf dessen Ausführung / Instanzen dessen ausüben