1_grundlagen.md

1.1. Grundlagen

Definition und Eigenschaften von Algorithmen

Ein Algorithmus ist ein schrittweises Problemlösungsverfahren mit den folgenden Eigenschaften:

1.1.1. Vollständigkeit

Ein Algorithmus ist eine Beschreibung eines Lösungsverfahrens darf keinen Schritt auslassen und muss alle relevanten Vor- und Rahmenbedingungen berücksichtigen. 1.1.2. Eindeutigkeit

Jede Aktion muss eindeutig interpretierbar sein. Es darf keinen Interpretationsspielraum geben. 1.1.3. Ausführbarkeit

Jede Aktion muss ausführbar sein. Die Art und Weise der Ausführung muss klar sein. 1.1.4. Statische Endlichkeit

Der Umfang der Beschreibung eines Algorithmus muss endlich sein, unabhängig von der Notation. 1.1.5. Dynamische Endlichkeit

Ein Algorithmus heisst abbrechend oder terminierend wenn seine Ausführung nach endlich vielen Schritten anhält. Sonnst heisst der Algorithmus nicht nicht abbrechend oder nicht terminierend 1.1.6. Korrektheit

Ein Algorithmus ist korrekt wenn er für jede Eingabeinstanz mit der richtigen Ausgabe hält. Ein inkorrekter Algorithmus terminiert nicht oder terminiert mit einer falschen Ausgabe. 1.1.7. Effizienz

Ein Algorithmus soll seinen Zweck unter bestmöglicher Ausnutzung aller beteiligten Ressourcen erfüllen.

1.2. Bestandteile von Algorithmen

In der imperativen oder prozeduralen Programmierung bestehen Algorithmen aus einer Folge von Anweisungen / Aktionen / Befehlen / Kommandos, welche auf Datenobjekte angewandt werden.

1.2.1. Datenobjekte und Datentypen

Datenobjekte können während der Ausführung eines Algorithmus veränderbar (Variabeln) oder unveränderbar (Konstanten) sein und besitzen je einen Datentyp, welcher ihre Wertemenge und die auf sie anwendbaren Operationen beschreibt.

Ein Datenobjekt heisst elementar (atomar) wenn es im logischen Sinne nicht weiter in einzelne Bestandteile zerlegt werden kann. Ein Datenobjekt heisst strukturiert, wenn es eine Struktur aufweist und sich logisch aus kleineren Bestandteilen zusammensetzt.

1.2.2. Anweisungen

if condition then
     statement sequence 1
else
    statement sequence 2
end

1.3. Schnittstellen von Algorithmen

CalculateFactorial(↓x:int ↑ xf:int)
BinominalCoefficient(↓n:int ↓k:int) :int

1.4. Darstellungsformen für Algorithmen

• Grafische Darstellungsformen für Algorithmen
  • Ablaufdiagramme
  • Struktogramme / Nassi-Schneiderman-Diagramme
• (UML)
• Text-basierte Darstellungsformen für Algorithmen
  • Stilisierte Prosa
  • Pseudocode

1.5 Algorithmen und Programme

• Ein Algorithmus kann in verschiedenen Darstellungsformen beschrieben sein. Ein Programm hingegen muss immer in der Sprache des Rechners formuliert sein.
• Ein Programm kann eine Beschreibung eines Algorithmus sein. Es kann sich aber ebenso um eine sinnlose Aneinanderreihung von Operationen handeln.
• Ein Programm kann (unfreiwillig) fehlerhaft sein, auch wenn der zugrundeliegende Algorithmus korrekt ist.
• Von einem Algorithmus spricht man nur im Zusammenhang mit einem Problem.

1.6 Programmbibliotheken

• Verwenden Sie für Standard-Algorithmen und -Datenstrukturen immer bewährte Programmbibliotheken.
• Überlegen Sie sich die Umsetzung "besserer" Ideen oder Neuimplementierungen strets sehr gut.