Algorithmus: Unterschied zwischen den Versionen
Marius (Diskussion | Beiträge) (→Beispiele für die Eigenschaften von Algorithmen) |
Marius (Diskussion | Beiträge) |
||
| Zeile 2: | Zeile 2: | ||
aus: Grumm/Sommer: Einführung in die Informatik | aus: Grumm/Sommer: Einführung in die Informatik | ||
| + | |||
| + | |||
| + | Man kann einen Algorithmus mit einer Gebrauchsanleitung vergleichen: Es wird versucht, ein (mathematisches) Problem durch präzise Anweisungen theoretisch auf einem Computer zu lösen. Dabei wird Pseudocode, also eine vereinfachte und verkürzte Programmiersprache, verwendet. | ||
| Zeile 9: | Zeile 12: | ||
==Forderungen an einem Algorithmus== | ==Forderungen an einem Algorithmus== | ||
===A1: Relation=== | ===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. | + | ''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=== | ===A2: Elementaroperationen=== | ||
| − | Ein Algorithmus setzt sich aus '''wohldefinierten Elementaroperationen''' zusammen, die auf einer geeigneten Maschine ausführbar sind. | + | ''Ein Algorithmus setzt sich aus '''wohldefinierten Elementaroperationen''' zusammen, die auf einer geeigneten Maschine ausführbar sind.'' |
===A3: Abfolge=== | ===A3: Abfolge=== | ||
| − | Ein Algorithmus legt die '''Abfolge der Schritte''' fest, wobei jeder Schritt genau eine Elementaroperation umfasst. | + | ''Ein Algorithmus legt die '''Abfolge der Schritte''' fest, wobei jeder Schritt genau eine Elementaroperation umfasst.'' |
===A4: Beschreibung endlicher Länge=== | ===A4: Beschreibung endlicher Länge=== | ||
| − | Ein Algorithmus ist eine '''Beschreibung endlicher Länge'''. | + | ''Ein Algorithmus ist eine '''Beschreibung endlicher Länge'''.'' |
===A5: Speicherplatz=== | ===A5: Speicherplatz=== | ||
| − | Ein Algorithmus benutzt nur '''endlich viele Speicherplätze''' zur Ablage von Zwischenergebnissen. | + | ''Ein Algorithmus benutzt nur '''endlich viele Speicherplätze''' zur Ablage von Zwischenergebnissen.'' |
===A6: Terminierung=== | ===A6: Terminierung=== | ||
| − | Für jede (!) Eingabe endet die Ausführung des Algorithmus nach endlich vielen Schritten ('''Terminierung'''). | + | ''Für jede (!) Eingabe endet die Ausführung des Algorithmus nach endlich vielen Schritten ('''Terminierung''').'' |
===A7: Begrenzte Schrittanzahl=== | ===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'''). | + | ''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=== | ===A8: Determiniertheit=== | ||
| − | Die Eingabe-Ausgabe-Relation (siehe A1) ist rechtseindeutig. Dies bedeutet, dass jeder Eingabe genau eine Ausgabe zugeordnet wird ('''Determiniertheit'''). | + | ''Die Eingabe-Ausgabe-Relation (siehe A1) ist rechtseindeutig. Dies bedeutet, dass jeder Eingabe genau eine Ausgabe zugeordnet wird ('''Determiniertheit''').'' |
===A9: Determinismus=== | ===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'''). | + | ''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=== | ===A10: Allgemeinheit=== | ||
| − | Ein Algorithmus löst nicht nur ein einziges Problem, sondern eine Klasse von Problemen ('''Allgemeinheit'''). | + | ''Ein Algorithmus löst nicht nur ein einziges Problem, sondern eine Klasse von Problemen ('''Allgemeinheit''').'' |
===A11: Änderbarkeit=== | ===A11: Änderbarkeit=== | ||
| − | Ein Algorithmus soll sich leicht modifizieren lassen, um ihn an eine veränderte Aufgabenstellung anzupassen ('''Änderbarkeit'''). | + | ''Ein Algorithmus soll sich leicht modifizieren lassen, um ihn an eine veränderte Aufgabenstellung anzupassen ('''Änderbarkeit''').'' |
===A12: Effiezenz=== | ===A12: Effiezenz=== | ||
| − | Für eine gegebene Eingabe soll die Anzahl der benötigten Schritte möglichst gering sein ('''Effizienz'''). | + | ''Für eine gegebene Eingabe soll die Anzahl der benötigten Schritte möglichst gering sein ('''Effizienz''').'' |
===A13: Robustheit=== | ===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'''). | + | ''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''').'' |
| Zeile 80: | Zeile 85: | ||
System.out.println("Das Ergebnis ist:" + erg); | System.out.println("Das Ergebnis ist:" + erg); | ||
}</source> | }</source> | ||
| + | |||
| + | Beide Programme führen das gleiche aus. Beide berechnen das Produkt von ''a'' und ''b'' bzw. ''c'' und ''d'', ohne zu mutipliezieren. Sie addieren ''b'' bzw. ''d'' ''a''- bzw ''c''-mal auf eine Ergebnisvariablen auf, Genaueres s. Schleifen. Diese Variable wird zum Schluss ausgegeben. | ||
==Vom Algorithmus zum Programm== | ==Vom Algorithmus zum Programm== | ||
| Zeile 85: | Zeile 92: | ||
===Programm/Programmieren=== | ===Programm/Programmieren=== | ||
| + | Die Formulierung eines Algorithmus heißt Programm. | ||
| + | Das Entwerfen eines Programms programmieren. | ||
===Programmpardigmen=== | ===Programmpardigmen=== | ||
| + | Ein Programmparadigma ist ein Konzept zum Programmieren. | ||
==Die bekanntesten Programmparadigmen== | ==Die bekanntesten Programmparadigmen== | ||
| − | * Imperative (prozedurale) Programmierung | + | *Imperative (prozedurale) Programmierung |
*Funktionale Programmierung | *Funktionale Programmierung | ||
Version vom 10. Juli 2015, 13:39 Uhr
"Ein Algorithmus ist eine detaillierte und explizite Vorschrift zur schrittweisen Lösung eines Problems durch eine Abfolge bekannter Befehle/Operationen."
aus: Grumm/Sommer: Einführung in die Informatik
Man kann einen Algorithmus mit einer Gebrauchsanleitung vergleichen: Es wird versucht, ein (mathematisches) Problem durch präzise Anweisungen theoretisch auf einem Computer zu lösen. Dabei wird Pseudocode, also eine vereinfachte und verkürzte Programmiersprache, verwendet.
Inhaltsverzeichnis
- 1 Forderungen an einem Algorithmus
- 1.1 A1: Relation
- 1.2 A2: Elementaroperationen
- 1.3 A3: Abfolge
- 1.4 A4: Beschreibung endlicher Länge
- 1.5 A5: Speicherplatz
- 1.6 A6: Terminierung
- 1.7 A7: Begrenzte Schrittanzahl
- 1.8 A8: Determiniertheit
- 1.9 A9: Determinismus
- 1.10 A10: Allgemeinheit
- 1.11 A11: Änderbarkeit
- 1.12 A12: Effiezenz
- 1.13 A13: Robustheit
- 2 Verständlichkeit eines Algorithmus
- 3 Vom Algorithmus zum Programm
- 4 Die bekanntesten Programmparadigmen
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
Beispiel für ein unverständlichen Algorithmus:
public static void berechnen2(int c, int d){int erg=0;for(int i=0;i<c;i++){erg+=d;}System.out.println("Das Ergebnis ist: "+erg);}
Das gleiche Beispiel:
public static void berechnen(int a, int b)
{
int erg = 0;
for(int i = 0; i<a ; i++)
{
erg += b;
}
System.out.println("Das Ergebnis ist:" + erg);
}
Beide Programme führen das gleiche aus. Beide berechnen das Produkt von a und b bzw. c und d, ohne zu mutipliezieren. Sie addieren b bzw. d a- bzw c-mal auf eine Ergebnisvariablen auf, Genaueres s. Schleifen. Diese Variable wird zum Schluss ausgegeben.
Vom Algorithmus zum Programm
Programm/Programmieren
Die Formulierung eines Algorithmus heißt Programm. Das Entwerfen eines Programms programmieren.
Programmpardigmen
Ein Programmparadigma ist ein Konzept zum Programmieren.
Die bekanntesten Programmparadigmen
- Imperative (prozedurale) Programmierung
- Funktionale Programmierung
- Logische Programmierung
- Objektorientierte Programmierung
