Algorithmus

• wichtige Aspekte eine Algorithmus
  • Korrektheit
    • Macht der Algorithmus was er tun soll
  • Effizient
    • funktioniert der Algorithmus immer effizient
    • egal mit welchen und wieviel Daten
  • Terminierung
    • hat der Algorithmus ein Ende
      • wenn nicht läuft das Programm unbegrenzt weiter, was zu folge hat, dass es eine Endlosschleife gibt

Begriff

• Herkunft des Begriffs des Algorithmus
  • 780 - 850 Abu Dscha'far Muhammad ibn Musa al-Chwarizmi
  • “Dixit Algorizmi” = “also sprach al-Chwarizmi”
  • als Gütezeichen einer Rechnung (ab ca. 1200)

Algorithmus vs. Programm

• Algorithmen beschreiben in prinzipiellen Elementen, was ein Computer ausführen soll
• Programmiersprachen stellen eine Schnittstelle dar, um Algorithmen auf einem Computer definieren und ausführen zu können
• Algorithmen fokussieren auf Korrektheit, Vollständigkeit, und Komplexität
• Programmiersprachen müssen zusätzlich alle Details des Computers berücksichtigen

Beispiel Algorhitmus

Zweierpotenzen in natürlicher Sprache

Berechne die Zweierpotenzen bis n (also solange “2 m < n” gilt):

Sei m gleich 0
Sei p gleich 1
Solange p kleiner n ist, mache:
Gib „2 hoch m ist p“ auf der Konsole aus
Addiere zu m den Wert 1
Multipliziere p mit dem Wert 2

Zweierpotenzen in Pseudocode

m = 0
p = 1
while ( p < n)
Ausgabe "2^m ist p";
m = m +1;
p = p * 2;

Erklärung Zweierpotenz

• m und p sind Variablen, denen ein Wert zugewiesen wird (Zeile 1 & 2)
• while sagt aus, dass der Block wiederholt wird solange die Bedingung p < n erfüllt ist
• In Zeile 5 und 6 werden die Variablen neu zugewiesen. Dafür findet auf der rechten Seite eine Berechnung statt

Zweierpotenz in C

#include <stdio.c>

int main() {
	int m = 0;
	int p = 1;
	int n = 10; //nur Beispiel
	while (p < n) {
		printf("2^%d ist %d", m, p);
		m = m + 1;
		p = p * 2;
	}
}