Algo_brains

Ein deterministischer Algorithmus ist ein Algorithmus, bei dem
- nur definierte und reproduzierbare Zustände auftreten.

Für die gleiche Eingabe folgt auch immer die gleiche Ausgabe und zusätzlich wird die gleiche Folge an Zuständen durchlaufen.

Bildfehler bzw. Artefakte bei Farbreduktion

Glättungsfaktor bzw. Rechnerisches Verfahren zur "Kantenglättung" bei Rastergrafiken und Schriften

Bsp: Treppenartige Kanten werden entschärft

- wenn Algo zielführend laut Aufgabenstellung ist

- kurze Laufzeit und geringer Speicherverbrauch

- durch simulierten evolutionären Zyklus entsteht die Motivation Probleme durch Operationen (Mutation und Selektion) neu zu lösen,

- meist nicht terminiert

- statisches 2Dimensionales Problem in ein dynamisches 1Dimensionales Problem umwandeln

- durch simultanes Masking wird Frequenz durch Kompression weggefiltert, bei temporalem Masking wird ein leiserer Ton weggefiltert,

- Simultanes Masking: Unvermögen, 2 gleichzeitig auftretende ähnliche Frequenzen auseinander zu halten,

- Temporäres Masking: bei 2 kurz aufeinander folgende Töne wird nur der Lautere von beiden wahr genommen

wird geliefert, wenn
- bei vorgegebener Eingabe
- ein eindeutiges Ergebnis
geliefert wird

auch bei mehrfacher Durchführung des Algorithmus (natuürlich mit den selben Eingabeparametern)

1: erlaubt 5 Zuständen:
bedingter Sprung,
unbedingter Sprung,
Verminderung durch Konstante,
Vermehrung durch Konstante,
Stop-Anweisung

2: schwer durchschaubar, daher schlechter Programmierstyle

Ausführbar, endlicher Länge beschreibbar sein, endlich viel Speicherplatz, endlich viele Schritte.

Effizient, Erweiterbarkeit, Portabilität, Stabilität

... beschrieben durch einen Namen und eine Bearbeitungsvorschrift.

Anwendung desselben Prinzips auf immer kleinere Teilprobleme, bis diese Teilprobleme so klein sind, dass sie mit einer Abbruchbedingung direkt gelöst werden können.

Der Folge f1 werden sukzessive Elemente entnommen und an die korrekte Stelle in f2 eingefügt, also sortieren durch Einfügen.

Benötigt mehr Speicher (2 * die Länge f1 + 1 Speicherstelle) Zerstört aber die f1 Liste nicht.

Komplexität bleibt gleich.

Insertionsort beginnt von links nach rechts, sortiert aber von rechts nach links.

Vorteil:
spart Speicher, weil benötigt nur Speicher für die Anzahl der Listen + 1 Zwischenspeicherstelle.

Nachteil: Verändert die Liste f1. Komplexität ist gleich.

- beginnt links

der größte Wert blubber von links nach rechts soweit, wie es die definierte partitielle Ordnung vor sieht.

Optimierung:
1. beim i-ten Durchlauf nur den Bereich 1 .. N-i betrachten, da der Rest bereits zuvor geordnet wurde.
2. Lokalität der Zugriffe im Cache

- bei fast sortierten und kleinen Folgen, und bei Flaschenhalsszenarien

- 2 bereits sortierte Folgen werden durch einmaligen Durchlauf paarweise miteinander vertauscht.

- Aufwand des Mischens ist linear in der Anzahl der Elemente.

- eine vorhandene Folge wird halbiert, die halben Folgen werden gemerget und rekursiv weiter verfahren bis einelementige Liste vorhanden ist.

ist eine pra_zise (d.h. in einer festgelegten Sprache abgefasste) endliche Beschreibung eines allgemeinen Verfahrens unter Verwendung ausfu_hrbarer elementarer (Verarbeitungs-) Schritte

- ausführbar sein,

- in endlicher Länge beschreibbar,

- während Ausführung nur endlichen Speicherplatz benötigen,

- terminiert sein

- Effizient, Portabilität, Stabilität, Erweiterbarkeit

Großes Problem durch selbes Vorgehen in immer kleinere (durch Abbruchbedingungendirekt lösbare) Probleme aufteilen

- 6 Tupel

(Eingabealphabet I, Ausgabealphabet O, Zustandsmengen Q, Zustandsübergangsfunktionen d, Anfangszustand q0, Endzustand F)

Wenn die Mengen I, O, Q endlich sind und es nur einen Anfangszustand gibt.