Algorithmusbegriff

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Algorithmen 1.1 Einführung 1.2 Der Algorithmusbegriff 1.3 Eigenschaften von Algorithmen 2 Beispiele für Algorithmen / keine Algorithmen

Algorithmen

Einführung

Auch heute kann man noch nicht in natürlicher Sprache mit einem dem Computer kommunizieren, deshalb wurden im Laufe der Jahre verschiedene Programmiersprachen entwickelt. Die Entwicklung einer Programmiersprache gehört zur theoretischen Informatik. In Abgrenzung zur natürlichen Sprache und auch zu den Programmiersprachen befassen sich formale Sprachen mit deren „Aufbau“ – Satzbau. Der Unterschied zwischen gesprochenen Sprachen und Programmiersprachen liegt darin, dass die Worte einer Programmiersprache nur genau eine Bedeutung zulassen, während der Sinngehalt mancher Worte der Umgangssprache erst aus dem Kontext heraus deutlich werden kann.
Ein Rechner benötigt aber stets eindeutig formulierte Anweisungen zur Bearbeitung - Algorithmus:

Im Gegensatz zur theoretischen Informatik befasst sich die praktische Informatik mit der Formulierung von Algorithmen als Programm – diese müssen in Maschinensprache übersetzt werden.

Möglichkeiten der Übersetzung von Quelltexten einer Programmierumgebung in Maschinensprache:

Interpreter:

• Programm wird zeilenweise abgearbeitet
• Bei Neustart ist immer neue zeilenweise Übersetzung notwendig
• Programme laufen langsamer, z.B. Javascript, Basic, Robot Karol

Compiler:

• Programm wird komplett übersetzt - es entsteht eine startbare EXE-Datei
• Nur bei Änderungen im Quelltext muss das Programm neu in Maschinensprache übersetzt werden
• compilierte Programme laufen 10 bis 20 schneller als interpretierte Programme, z.B. Delphi, C++

Der Algorithmusbegriff

Der Algorithmusbegriff ist ein zentaler Begriff in der Informatik. Ein Algorithmus bildet die Grundlage für die Implementierung (Umsetzung) einer Problemlösung mit Hilfe einer Programmiersprache.

Die Bezeichnung Algorithmus geht auf den Namen Muhammad ibn Musa, Abu Dscha'far al-Chwarizmi (* um 780; † um 850), einem persischen Mathematiker, Astronomen und Geographen, zurück. Diesem Universalgelehrten verdanken wir nicht nur die Einführung der Null aus dem indischen in das arabische Zahlensystem, sondern auch das Wort "Algebra", das der lateinischen Übersetzung seines Buches Kitāb al-muchtasar fi hisab al-dschabr wa-l-muqabala ("Rechnen durch Ergänzung und Ausgleich") entnommen ist.

Es existiert eine Vielzahl von Versuchen einer Definition für den Begriff Algorithmus.
zum Beispiel:

1. Als ”Algorithmus [..] bezeichnet [man] heute in der Arithmetik einen Rechenvorgang (bzw. die ihn beschreibenden Regeln) der nach einem bestimmten sich wiederholenden Schema abläuft" (Meyers Enzyklopädie, 1971)
2. ”Ein Algorithmus [..] ist eine vollständige, präzise und in einer Notation oder Sprache mit exakter Definition abgefasste, endliche Beschreibung eines schritt- weisen Problemlösungsverfahrens zur Ermittlung gesuchter Datenobjekte (ihrer Werte) aus gegebenen Werten von Datenobjekten, in dem jeder Schritt aus einer Anzahl ausführbarer, eindeutiger Aktionen und einer Angabe über den nächsten Schritt besteht.”(Pomberger, Gustav; Dobler, Heinz: Algorithmen und Datenstrukturen - Eine systematische Einführung in die Programmierung. München : Pearson Education Deutschland GmbH, 2008)
3. ”Ein Algorithmus ist eine detaillierte und explizite Vorschrift zur schrittweisen Lösung eines Problems.”(Gumm, Heinz P.; Sommer, Manfred: Einführung in die Informatik. München : Oldenbourg Wissenschaftsverlag, 2006)

Wir begnügen uns mit einer anschaulichen (intuitiven) Erklärung:

Ein Algorithmus ist eine endliche Folge von eindeutigen und ausführbaren Anweisungen zur Lösung eines allgemeinen Problems.

Eigenschaften von Algorithmen

1. Endlichkeit: (Finitheit)
   • endliche Notation des Algorithmus, (statische Endlichkeit)
   • Nutzung endlicher Ressourcen (z.B. begrenzter Arbeitsspeicher / begrenzte Rechenzeit) - dynamische Endlichkeit
2. Terminiertheit
   • endlich viele Abarbeitungsschritte - Endlichkeit im Ablauf (z.B. begrenzte Rekursionstiefe), der Algorithmus liefert also bei jeder Anwendung nach endlich vielen Verarbeitungsschritten ein Resultat
     
   • Bei Nichterfüllung: Endlosschleife (Ausnahmen: OS; interaktive Programme)
3. Deterministisch
   • nach jedem Abarbeitungsschritt besteht höchstens eine Möglichkeit der Fortsetzung
4. Eindeutigkeit: (Determiniertheit)
   • gleiche Eingabegrößen und Anfangsbedingungen liefern stets das gleiche Ergebnis
5. Ausführbarkeit:
   • jede Anweisung ist (z.B. für einen Prozessor) verständlich und ausführbar
6. Allgemeingültigkeit:
   • Anwendbarkeit auf gleiche Probleme einer Problemklasse.

Beispiele für Algorithmen / keine Algorithmen

• Finde unter Beachtung der Eigenschaften zwei Beispiele für einen Algorithmus.
• Nenne zwei Gegenbeispiele und begründe.