PMG/Kurs 11/Wdhlg Alg Prog I

Wiki-Quelltext dieser Seite.

<language>Pascal</language>
== Algorithmen ==

=== Einführung ===
Auch heute kann man noch <u>nicht</u> 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 <u>genau eine</u> Bedeutung zulassen, während der Sinngehalt mancher Worte der Umgangssprache erst aus dem Kontext heraus deutlich werden kann. <br>
Ein Rechner benötigt aber <u>stets eindeutig</u> 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 ===
<span style="color:#006400;"><blockquote>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.<br>
Stelle für folgende Beispiele Vermutungen an, ob diese Handlungen Algorithmen darstellen.:
* "''Koffer packen''"
* "''Flughafen - einchecken''"
* "''Castingshow''" 
* "''Fußballregeln''".

Überprüfe die Vermutungen anhand der unten aufgeführten Eigenschaften von Algorithmen.
</blockquote></span>


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.<br /><br />

Es existiert eine Vielzahl von Versuchen einer Definition für den Begriff ''Algorithmus''.<br />
zum Beispiel:
<ol>
<li>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)
</li>
<li>”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)
</li>
<li>”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)
</li>
</ol>

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

<b>''Ein Algorithmus ist eine endliche Folge von eindeutigen und ausführbaren Anweisungen zur Lösung eines allgemeinen Problems.''</b><br>

=== Eigenschaften von Algorithmen ===

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




== Arbeit mit den Eingabefeldern im PWiki==

PWiki steht für ProgrammingWiki - also für ein Wiki, in dem programmiert werden kann. Dies erfolgt in Boxen (Eingabefeldern).<br>
Um uns etwas mit der Schreibweise im PWiki vertraut zu machen, wenden wir einfache Grundrechenoperatoren auf ganze und reelle Zahlen an. Es folgt ein interaktives Feld zum Experimentieren. <br>
Im oberen Feld bitte den angegebenen Term (3*5-5*3) beliebig verändern. Mit einem Klick auf ''speichern & ausführen'' wird diese vom Pascal-Interpreter verarbeitet. Im zweiten Kästchen erscheint das Berechnungsergebnis.<br>
<span style="color:#CD661D">Probiere und interpretiere mögliche Fehlermeldungen!</span>


<run id="4f5c9ba917e1d">
writeln(inttostr(3*5-5*3))
</run>



Offensichtlich funktioniert die Ausgabe bei reellen Zahlen nicht. <br>
''inttostr'' bedeutet Konvertierung (Umwandlung) von <u>ganzen</u> Zahlen in eine Zeichenkette.<br>
''floattostr'' wird für die Konvertierung von <u>reellen</u> Zahlen in eine Zeichenkette verwendet.
[[Bild:Thomas_Kreuz.JPG|right|thumb|100px|rotes Kreuz]] 


''Zu beachten ist, dass reelle Zahlen mit Punkt (also 12.5 nicht 12,5) notiert werden.'' <br><br>
'''<span style="color:#cd661d;"> Hinweis: </span>''' <br>
<span style="background-color:#CD661D;"> Wenn Du den Quelltext änderst, siehst Du dies an dem roten Kreuz an dem Eingabefeld. <br>Durch einen Klick darauf lässt sich der ursprüngliche Quelltext wieder herstellen. </span>

<br>