Informatik Vorbereitung KA

Inhalt:
1. Funktionen und Prozeduren inc. Parameter
2. iterative und rekursive Algorithmen
3. Werteverlaufstabelle


Quelle: http://www.th.schule.de/th/lfk-informatik/material/

Algorithmen

 

Unter der Spezifikation eines Algorithmus versteht man eine Aussage, die möglichst genau beschreibt, was der Algorithmus leistet.
Zwei Algorithmen heißen wirkungsgleich (äquivalent), wenn sie der gleichen Spezifikation genügen.

Algorithmus:

Beschreibung zur Lösung eines Problemes, die so formuliert ist, das sie von einer Maschine abgearbeitet werden kann

Eigenschaften von Algorithmen:

  1. Jeder Algorithmus löst eine Klasse von Problemen.
  2. endliche Beschreibung
  3. endliche Abarbeitung
  4. Determiniertheit (gleiche Eingabe –> gleiche Ausgabe)
  5. Arten:
    • deterministische
      (Zu jedem Zeitpunkt seiner Ausführung besteht höchstens eine Möglichkeit der Fortsetzung.)
    • nichtdeterministische,
      (An gewissen Stellen gibt es bei der Ausführung mehrere Möglichkeiten der Fortsetzung, von denen man nach Belieben eine auswählen kann.)
    • stochastische
    • (An gewissen Stellen gibt es bei der Ausführung mehrere Möglichkeiten der Fortsetzung, für deren Auswahl man Wahrscheinlichkeiten zuordnen kann.)

Formulierung von Algorithmen:

  1. verbale
  2. Struktogramm
  3. Programm (Quelltext)
formale Parameter aktuelle Parameter
In der Kopfzeile der Deklaration eines Unterprogrammes sind die formalen Parameter zu finden. Sie wirken innerhalb des Unterprogrammes wie lokale Variablen. Beim Aufruf eines Unterprogrammes verwendet man aktuelle Parameter.
Die aktuellen und formalen Parameter müssen in Anzahl, Typ und Reihenfolge übereinstimmen.
Wertparameter Referenzparameter
Beim Aufruf des Unterprogrammes werden neue Speicherplätze reserviert und die Werte der aktuellen Parameter dort eingetragen.
(Die Werte der aktuellen Parameter werden in neue Speicherzellen kopiert.)
Beim Aufruf werden keine neuen Speicherplätze reserviert.
(Die formalen und aktuellen Parameter verweisen auf dieselben Speicherzellen.)
Innerhalb des Unterprogrammes wird nur mit diesen Kopien gearbeitet. Die Operationen mit den formalen Parametern werden mit den Speicherplätzen der aktuellen Parameter ausgeführt.
Nach Abschluss des Unterprogramms werden die lokalen Parmeterspeicherzellen wieder freigegeben. Ihre Inhalte sind dann verloren. Nach Abschluss des Unterprogramms bleiben die Inhalte der formalen Parameter in den aktuellen Parametern erhalten.
Aktuelle Parameter können Konstanten, Variablen oder Ausdrücke, die vor der übertragung ausgewertet werden, sein. Aktuelle Parameter können nur Variablen sein.
Sie eignen sich nur zur Eingabe von Werten in ein Unterprogramm. Sie eignen sich zur Eingabe und Ausgabe von Werten in ein (aus einem) Unterprogramm.
Beispiel:

  • PROCEDURE eins(x,y:INTEGER);
Beispiel:

  • PROCEDURE zwei(VAR x,y:INTEGER);

Autor: H. Heerdegen