Algorithmen

• Ein Algorithmus ist eine eindeutige Handlungsvorschrift zur Lösung eines Problems.

• Algorithmen bestehen aus endlich vielen, wohldefinierten Einzelschritten.

• Geschwindigkeit

• Speicher

• Präzision

• Prozess: Abarbeitung eines Algorithmus.

• Prozessor: Einheit die Prozesse ausführt, die einen Algorithmus abarbeitet

• Algorithmenschritt: Ein Schritt in der Abarbeitung des Algorithmuses

• präzise: in einer eindeutigen Sprache abgefasst

• endlich: in einer endlichen Form beschrieben

• effektiv: die Arbeitsschritte sind tatsächlich ausführbar

• effizient: problem mit möglichst wenig Aufwand lösen

• Aufwand: Zeit, Speicher, sonstige Ressourcen

  • Optimaler Algotirhmus: minimaler und maximaler Aufwand sind gleich

Fakultät:

Fibonacci:

• Ein Algorithmus, der nach Ausführung einer endlichen Zahl von Schritten anhält und dann das Ergebnis bestimmt hat, heißt terminierender Algorithmus

• ein Algorithmus muss nicht terminieren!

Deterministischer Algorithmus:

• ist zu jedem Zeitpunkt eindeutig, was als nächses zu tun ist

Nicht-deterministischer Algorithmus:

• sind zu einem Zeitpunkt mehrere Folgereaktionen erlaubt, wobei nicht festgelegt ist, welche ausgeführt werden soll

• gleiche Eingabe unterschiedliche Ergebnisse

Determiniert:

• immer gleiches Ergebnis

• auch deterministische Algorithmen (date)

• bezeichnet eine Offenbarung, die der Beantwortung von Zukunfts- oder Eintscheidungsfragen dient

• weiß immer eine Antwort

• Antwort ist immer korrekt

• Aufwand immer konstant

verwendet Zufallsbits, um seinen Ablauf zu steuern

• findet nicht immer effizient eine Lösung

Las-Vegas-Algorthmen: (Random-Quick-Sort)

• nie ein falsches Ergebnis

Monte-Carlo-Algorithmen: (bestimmung π)

• liefern auch falsche Ergebnisse

• Qualität durch obere Schranke für die Fehlerwahrscheinlichkeit bestimmt

P: hochstens polynomialen Aufwand (Suchalgorithmen)

EXPTime: höchstens exponentieller Aufwand (Türme von Hanoi)

NP: Nichtdeterministisch polynomial exponentieller Aufwand (Handlungsreisender, N!)

Problemlösungsmethode innerhalb der Algorithmik.

• “trial and error” Prinzip

• erreichte Teillösung zu einer Gesamtlösung auszubauen

• letzten Schritte zurückgenommen, wenn absehbar, dass es nicht klappt -> neue Wege