Algorithmus: Unterschied zwischen den Versionen
Marius (Diskussion | Beiträge) |
Marius (Diskussion | Beiträge) |
||
| Zeile 2: | Zeile 2: | ||
| − | + | "Ein Algorithmus ist eine detaillierte und explizite Vorschrift zur schrittweisen Lösung eines Problems durch eine Abfolge bekannter Befehle/Operationen." | |
| − | + | Gumm/Sommer: Einführung in die Informatik | |
| − | zur schrittweisen Lösung eines Problems durch eine Abfolge | + | |
| − | bekannter Befehle/Operationen. | + | |
| − | + | ||
| − | + | ||
| − | + | ||
| + | ==Forderungen an einem Algorithmus== | ||
| + | ===A1: Relation=== | ||
| + | Ein Algorithmus beschreibt eine '''Relation''' über dem '''Kreuzprodukt einer Eingabe- und einer Ausgabemenge'''. Dadurch werden für jede Eingabe die zulässigen Ausgaben festgelegt. | ||
| + | |||
| + | |||
| + | ===A2: Elementaroperationen=== | ||
| + | Ein Algorithmus setzt sich aus '''wohldefinierten Elementaroperationen''' zusammen, die auf einer geeigneten Maschine ausführbar sind. | ||
| + | |||
| + | |||
| + | ===A3: Abfolge=== | ||
| + | Ein Algorithmus legt die '''Abfolge der Schritte''' fest, wobei jeder Schritt genau eine Elementaroperation umfasst. | ||
| + | |||
| + | |||
| + | ===A4: Beschreibung endlicher Länge=== | ||
| + | Ein Algorithmus ist eine '''Beschreibung endlicher Länge'''. | ||
| + | |||
| + | |||
| + | ===A5: Speicherplatz=== | ||
| + | Ein Algorithmus benutzt nur '''endlich viele Speicherplätze''' zur Ablage von Zwischenergebnissen. | ||
| + | |||
| + | |||
| + | ===A6: Terminierung=== | ||
| + | Für jede (!) Eingabe endet die Ausführung des Algorithmus nach endlich vielen Schritten ('''Terminierung'''). | ||
| + | |||
| + | |||
| + | ===A7: Begrenzte Schrittanzahl=== | ||
| + | Für jede (!) Eingabe wird die zugehörige Ausgabe spätestens nach Ausführung einer vorgegebenen Schrittanzahl n geliefert. Wenn ein Rechensystem für jeden Schritt höchstens die Zeit s benötigt, dann wird die Ausgabe spätestens nach Verstreichen der begrenzten Antwortzeit t = s * n geliefert ('''Begrenzte Schrittanzahl'''). | ||
| + | |||
| + | |||
| + | ===A8: Determiniertheit=== | ||
| + | Die Eingabe-Ausgabe-Relation (siehe A1) ist rechtseindeutig. Dies bedeutet, dass jeder Eingabe genau eine Ausgabe zugeordnet wird ('''Determiniertheit'''). | ||
| + | |||
| + | |||
| + | ===A9: Determinismus=== | ||
| + | In jedem Zustand, der bei Ausführung des Algorithmus erreicht wird, ist jeweils nur ein einziger Folgeschritt als nächster ausführbar ('''Determinismus'''). | ||
| + | |||
| + | |||
| + | ===A10: Allgemeinheit=== | ||
| + | Ein Algorithmus löst nicht nur ein einziges Problem, sondern eine Klasse von Problemen ('''Allgemeinheit'''). | ||
| + | |||
| + | |||
| + | ===A11: Änderbarkeit=== | ||
| + | Ein Algorithmus soll sich leicht modifizieren lassen, um ihn an eine veränderte Aufgabenstellung anzupassen ('''Änderbarkeit'''). | ||
| + | |||
| + | |||
| + | ===A12: Effiezenz=== | ||
| + | Für eine gegebene Eingabe soll die Anzahl der benötigten Schritte möglichst gering sein ('''Effizienz'''). | ||
| + | |||
| + | |||
| + | ===A13: Robustheit=== | ||
| + | Der Algorithmus soll sich möglichst auch dann wohldefiniert verhalten, wenn eine unzulässige Eingabe (die nicht Element der Eingabemenge ist) vorliegt oder eine sonstige unvorhergesehene Situation auftritt ('''Robustheit'''). | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | ==Verständlichkeit eines Algorithmus== | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | ==Beispiele für die Eigenschaften von Algorithmen== | ||
| + | * '''Einfache Grundoperation''' | ||
| + | |||
| + | * '''Sequenzieller Algorithmus''' | ||
| + | |||
| + | * '''Nebenläufiger Algorithmus''' | ||
| + | |||
| + | * '''Parallele Ausführung''' | ||
| + | |||
| + | * '''Nichtdeterministischer Algorithmus''' | ||
| + | |||
| + | |||
| + | ==Vom Algorithmus zum Programm== | ||
| + | |||
| + | |||
| + | ===Programm/Programmieren=== | ||
| + | |||
| + | |||
| + | ===Programmpardigmen=== | ||
| + | |||
| + | ==Die bekanntesten Programmparadigmen== | ||
| + | * Imperative (prozedurale) Programmierung | ||
| + | |||
| + | *Funktionale Programmierung | ||
| + | |||
| + | *Logische Programmierung | ||
| + | |||
| + | *Objektorientierte Programmierung | ||
Version vom 3. Juli 2015, 16:07 Uhr
Inhaltsverzeichnis
- 1 Was ist ein Algorithmus?
- 2 Forderungen an einem Algorithmus
- 2.1 A1: Relation
- 2.2 A2: Elementaroperationen
- 2.3 A3: Abfolge
- 2.4 A4: Beschreibung endlicher Länge
- 2.5 A5: Speicherplatz
- 2.6 A6: Terminierung
- 2.7 A7: Begrenzte Schrittanzahl
- 2.8 A8: Determiniertheit
- 2.9 A9: Determinismus
- 2.10 A10: Allgemeinheit
- 2.11 A11: Änderbarkeit
- 2.12 A12: Effiezenz
- 2.13 A13: Robustheit
- 3 Verständlichkeit eines Algorithmus
- 4 Beispiele für die Eigenschaften von Algorithmen
- 5 Vom Algorithmus zum Programm
- 6 Die bekanntesten Programmparadigmen
Was ist ein Algorithmus?
"Ein Algorithmus ist eine detaillierte und explizite Vorschrift zur schrittweisen Lösung eines Problems durch eine Abfolge bekannter Befehle/Operationen." Gumm/Sommer: Einführung in die Informatik
Forderungen an einem Algorithmus
A1: Relation
Ein Algorithmus beschreibt eine Relation über dem Kreuzprodukt einer Eingabe- und einer Ausgabemenge. Dadurch werden für jede Eingabe die zulässigen Ausgaben festgelegt.
A2: Elementaroperationen
Ein Algorithmus setzt sich aus wohldefinierten Elementaroperationen zusammen, die auf einer geeigneten Maschine ausführbar sind.
A3: Abfolge
Ein Algorithmus legt die Abfolge der Schritte fest, wobei jeder Schritt genau eine Elementaroperation umfasst.
A4: Beschreibung endlicher Länge
Ein Algorithmus ist eine Beschreibung endlicher Länge.
A5: Speicherplatz
Ein Algorithmus benutzt nur endlich viele Speicherplätze zur Ablage von Zwischenergebnissen.
A6: Terminierung
Für jede (!) Eingabe endet die Ausführung des Algorithmus nach endlich vielen Schritten (Terminierung).
A7: Begrenzte Schrittanzahl
Für jede (!) Eingabe wird die zugehörige Ausgabe spätestens nach Ausführung einer vorgegebenen Schrittanzahl n geliefert. Wenn ein Rechensystem für jeden Schritt höchstens die Zeit s benötigt, dann wird die Ausgabe spätestens nach Verstreichen der begrenzten Antwortzeit t = s * n geliefert (Begrenzte Schrittanzahl).
A8: Determiniertheit
Die Eingabe-Ausgabe-Relation (siehe A1) ist rechtseindeutig. Dies bedeutet, dass jeder Eingabe genau eine Ausgabe zugeordnet wird (Determiniertheit).
A9: Determinismus
In jedem Zustand, der bei Ausführung des Algorithmus erreicht wird, ist jeweils nur ein einziger Folgeschritt als nächster ausführbar (Determinismus).
A10: Allgemeinheit
Ein Algorithmus löst nicht nur ein einziges Problem, sondern eine Klasse von Problemen (Allgemeinheit).
A11: Änderbarkeit
Ein Algorithmus soll sich leicht modifizieren lassen, um ihn an eine veränderte Aufgabenstellung anzupassen (Änderbarkeit).
A12: Effiezenz
Für eine gegebene Eingabe soll die Anzahl der benötigten Schritte möglichst gering sein (Effizienz).
A13: Robustheit
Der Algorithmus soll sich möglichst auch dann wohldefiniert verhalten, wenn eine unzulässige Eingabe (die nicht Element der Eingabemenge ist) vorliegt oder eine sonstige unvorhergesehene Situation auftritt (Robustheit).
Verständlichkeit eines Algorithmus
Beispiele für die Eigenschaften von Algorithmen
- Einfache Grundoperation
- Sequenzieller Algorithmus
- Nebenläufiger Algorithmus
- Parallele Ausführung
- Nichtdeterministischer Algorithmus
Vom Algorithmus zum Programm
Programm/Programmieren
Programmpardigmen
Die bekanntesten Programmparadigmen
- Imperative (prozedurale) Programmierung
- Funktionale Programmierung
- Logische Programmierung
- Objektorientierte Programmierung
