Sammlung alt

"Sortieren" - Vergleich zweier Zahlen

(Ein Beispiel aus der Wissenschaftlichen Arbeit im Fach Informatik "Bildungsstandards Informatik - Aufgaben für den Unterricht zum Thema "Algorithmen" von Stefan Renz, TU Dresden, 2010)

Am Kölner Dom wurde über 600 Jahre gebaut, als er 1880 fertig wurde, war er allerdings nur für vier Jahre das höchste Gebäude der Welt. Hier eine Auswahl sehr hoher Gebäude:

1. Überlege Dir einen Algorithmus, der zwei Zahlen als Eingabe verarbeitet und die größere von beiden als Ergebnis ausgibt. Halte diesen Algorithmus als Struktogramm fest.
2. Was passiert bei Deinem Algorithmus, wenn die beiden Zahlen gleich groß sind?
3. Setze den Algorithmus in der vorbereiteten Box um.

<eval id="4cc726df709fc"></eval>

Potenz und Betrag/Abstand

Gegeben ist folgendes Struktogramm. Struktogramm(v2).JPG

Teste den dargestellten Algorithmus mit den Werten x = 5, y = 8 und z = 3 sowie anderen, selbst gewählten Werten. Erläutere die Bedeutung der Variablen.
Schreibe Deine Antwort in die Box hinter write:

<eval id="4cc728e2c48fd"> begin write(' '); end. </eval>

Implementiere den dargestellten Algorithmus in der nachfolgenden Box als function xyz1 (Teilalgorithmus Potenz)

<eval id="4cc728e2c4a12"> begin writeln(inttostr(xyz1(...))); end. </eval>

Implementiere den zweiten Teil des Algorithmus in der nachfolgenden Box als function xyz2 (Teilalgorithmus Betrag/Abstand)

Zufallszahlen und Würfelspiele

In den nächsten (letzten) Übungen mit dem PWiki werden wir noch ein paar "Spiele" mit Zufallszahlen erstellen. Anschließend werden wir mit einer Anwendersoftware (Fischer-Technik) Modelle bauen und steuern!

Doch zunächst:

Erzeugen von Zufallszahlen

<eval id="4cec1965a9ae3"> begin writeln(inttostr(zufall(100))); end.</eval>

Würfeln

Nun sollen nur Ergebnisse zufällig erzeugt werden, wie sie an einem idealen Würfel eintreten können.
Ergänze die Boxen analog dem obigen Beispiel und teste das Ergebnis.

<eval id="4cec1965a9bf2"> begin // dein Text end.</eval>

Simuliere nun ein Würfelspiel mit einem idealen Würfel. Für eine Anzahl n von Würfen soll die Anzahl aller geworfenen Augenzahlen ausgegeben werden.

Hinweis: Es soll also für jede mögliche Augenzahl eine Variable vereinbart werden, eine beliebige Anzahl von (simulierten)
Versuchen durchgeführt werden und die Anzahl der gewürfelten Einsen, Zweien, ..., Sechsen ausgegeben werden.

Stelle den notwendigen Algorithmus in einem Struktogramm dar.
Benutze dazu das Tool structorizer.

• Erstelle mit dem Programm das Struktogramm
• Speichere das Struktogramm als Bild (Format .jpg)
• füge dein Bild im PWiki ein

<eval id="4cec1965a9d02"></eval>

Wir stellen fest, dass eine function nur einen Wert (ein Resultat) zurückliefern kann.
Daher brauchen wir eine weitere Möglichkeit, die mehrere Ergebnisse liefert.
Dies geschieht unter Verwendung einer procedure, wobei die Rückgabewerte (Ergebnisvariablen) mit var angefügt werden (vergleiche Box).

<eval id="4d243865b40ec"></eval>

Formuliere anhand der Simulation eine Aussage über die Wahrscheinlichkeit der einzelnen Ergebnisse beim Würfeln.

zum Weiterarbeiten: Zeige durch eine analoge Simulation, dass die Zufallsgröße "Augensumme beim Würfeln mit zwei idealen Würfeln" nicht gleichverteilt ist.

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.

Der Algorithmusbegriff

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

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

Syntax von Funktionen

Beispiel für eine Funktion in einer imperativen Programmierumgebung

Function.JPG

Aufruf der Funktion im Hauptprogramm

Function_2.JPG

hier nun Beispiele für die Syntax im PWIKI

einfache Addition

<eval id="4bc596ef084eb"> begin writeln(inttostr(addi(3,4))); end. </eval>

Ergänze die ähnliche Funktion addi3 zur Bildung der Summe dreier reeller Zahlen!

<eval id="4bccb71f48edc"> begin writeln(floattostr(addi33(3,4,5))); end. </eval>

Quadrat einer Zahl

<eval id="4bc4611f3a5f1"> begin writeln(inttostr(quadrat(2))); end. </eval>

Beispiel 3

Untersuche diese Funktion.
Gib Deine Lösung in der zweiten Zeile zwischen den Anführungszeichen '' an.

<eval id="4bc596ef0a437"> begin writeln(inttostr(was(2,4,6))); writeln(''); end. </eval>

Gute Wünsche für den Tag

Ergänze die Anweisungen so, dass in der Ausgabe Wünsche für die Tage 1 bis 5 ausgegeben werden.
Worin unterscheidet sich der Quelltext von den obigen Beispielen?

<eval id="4bc596ef0b3cb"></eval>

Grundlagen der Unterprogrammarbeit (Modularisierung)

function

Beispiel für eine Funktion in einer imperativen Programmierumgebung

Function.JPG

Aufruf der Funktion im Hauptprogramm

Function_2.JPG

hier ein Beispiel für die Syntax im WIKI

<eval id="4b96b9dd51145"> begin writeln(inttostr(addi(3,4))); end. </eval>

Ergänze die ähnliche Funktion addi3 zur Bildung der Summe dreier reller Zahlen!

<eval id="4b96b9dd520e6"> begin writeln(floattostr(addi3(3,4,5))); end. </eval>

procedure

Beispiel für eine Prozedure in einer imperativen Programmierumgebung

Prozeduren.JPG

Aufruf der Prozedur im Hauptprogramm

Prozeduren_2.JPG

hier ein Beispiel für die Syntax im WIKI

<eval id="4b96b9dd53085"> var erg: string; begin dreieck(4,3,5.2,erg); writeln(erg); end. </eval>

Neujahrswünsche in Pascal:

<eval id="4b96b9dd54025"></eval>

Die folgenden Übungsaufgaben dienen der Festigung des Umgangs mit den algorithmischen Grundstrukturen.

1. Entwickle einen Algorithmus für die Berechnung der Summe der ersten n natürlichen Zahlen.

Setze diesen in Pascal um.

<eval id="4bcecd8d1833c"> begin writeln(inttostr(summe_erste_n(5))); end. </eval>

2. Übertrage diesen Algorithmus auf die Berechnung einer Fakultät!

<eval id="4bced86216bbc"> begin writeln(inttostr(fak_n(5))); end. </eval>

3. Gegeben ist folgendes Struktogramm. Implementiere den damit dargestellten Algorithmus in der nachfolgenden Box als function xyz und

teste ihn mit den Werten x = 5, y = 8 und z = 3. Erläutere die Bedeutung der Variablen.
] Struktogramm(v2).JPG

<eval id="4bd7d28b3972d"> begin writeln(inttostr(xyz(...))); end. </eval>

Eine Funktion gibt nur einen Wert (a oder b) zurück.

Daher nun diesen Algorithmus als procedure schreiben.

<eval id="4bd80bd03eb3a"> begin writeln(...); end. </eval>

4. Abschließend soll ein Programm geschrieben werden, das entscheidet, ob eine quadratische Funktion keine, genau eine oder genau zwei Nullstellen besitzt. Die Werte dieser Nullstellen sind auszugeben.
vorher Algorithmus formulieren und z.B. Struktogramm entwerfen!

<eval id="4bd8132f813eb"> begin writeln(...); end. </eval>