Grundlagen der funktionsorientierten Programmierung mit SCHEME/Der Algorithmusbegriff
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
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 />
== Der intuitive Algorithmusbegriff ==
Es ist recht schwierig, eine formal exakte Definition für den Begriff ''Algorithmus'' anzugeben.<br />
Wir begnügen uns deshalb 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>
== Eigenschaften von Algorithmen ==
<ol>
<li>'''Endlichkeit:'''
* endliche Notation des Algorithmus,
* Nutzung endlicher Ressourcen (z.B. begrenzter Arbeitsspeicher / begrenzte Rechenzeit),
* endlich viele Abarbeitungsschritte (z.B. begrenzte Rekursionstiefe),
</li>
<li>'''Eindeutigkeit:'''
* nach jedem Abarbeitungsschritt besteht höchstens eine Möglichkeit der Fortsetzung,
* gleiche Eingabegrößen und Anfangsbedingungen liefern stets das gleiche Ergebnis (''Determiniertheit''),
</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>
== Beispiele ==
=== Der Euklidische Algorithmus ===
Mit diesem Algorithmus, der nach dem griechischen Mathematiker '''Euklid von Alexandria''' (* um 360 v. Chr.; † um 280 v. Chr.) benannt ist, lässt sich der ''größte gemeinsame Teiler (ggT)'' zweier natürlicher Zahlen bestimmen.<br />
'''Beschreibung:'''<br />
* Der größte gemeinsame Teiler der Zahlen <math>m</math> und <math>n</math> ist <math>m</math>, falls <math>n=0</math> ist.
* Anderenfalls berechnet er sich aus dem größten gemeinsamen Teiler von <math>n</math> und dem Rest der ganzzahligen Division <math>\tfrac{m}{n}</math>.
'''Implementation:'''
<code id="4bd3f5a7f35e8">
(define ggT
(lambda (m n)
...))
</code>
<check>
(and (= (ggT 123 69) 3) (= (ggT 9797 303) 101))
</check>
<eval id="4bd3f5a800334">
(ggT 123 69)
</run>
=== Das Sieb des Eratosthenes ===
Der griechische Mathematiker, Geograph, Philosoph, Philologe und Dichter '''Eratosthenes von Kyrene''' (* zwischen 276 und 273 v. Chr.; † um 194 v. Chr.) war der erste Gelehrte der Antike, der durch eine wissenschaftlich fundierte Messung den Umfang der Erde mit erstaunlicher Genauigkeit bestimmt hat.<br />
Auf ihn geht aber auch ein interessanter Algorithmus zur Bestimmung aller ''Primzahlen'' zurück.<br />
'''Beschreibung:'''<br />
* Notiere die natürlichen Zahlen, beginne mit <math>2</math>.
<blockquote>
<math>2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...</math>
</blockquote>
* Unterstreiche die <math>2</math> und streiche alle Vielfachen von <math>2</math>.
<blockquote>
<math>\usepackage{ulem} \uline{2}, 3, \xout{4}, 5, \xout{6}, 7, \xout{8}, 9, \xout{10}, 11, \xout{12}, 13, \xout{14}, 15, \xout{16}, 17, \xout{18}, 19, \xout{20}, ...</math>
</blockquote>
* Unterstreiche die erste freie Zahl (in diesem Falle die Zahl <math>3</math>) und streiche deren Vielfachen.
<blockquote>
<math>\usepackage{ulem} \uline{2}, \uline{3}, \xout{4}, 5, \xout{6}, 7, \xout{8}, \xout{9}, \xout{10}, 11, \xout{12}, 13, \xout{14}, \xout{15}, \xout{16}, 17, \xout{18}, 19, \xout{20}, ...</math>
</blockquote>
* Verfahre mit allen weiteren freien Zahlen ebenso.
<blockquote>
<math>\usepackage{ulem} \uline{2}, \uline{3}, \xout{4}, \uline{5}, \xout{6}, \uline{7}, \xout{8}, \xout{9}, \xout{10}, \uline{11}, \xout{12}, \uline{13}, \xout{14}, \xout{15}, \xout{16}, \uline{17}, \xout{18}, \uline{19}, \xout{20}, ...</math>
</blockquote>
* Alle unterstrichenen Zahlen sind Primzahlen.
'''Implementation:'''<br />
Zunächst scheint diese Beschreibung gegen die Forderung der Endlichkeit zu verstoßen: Bereits das Notieren der natürlichen Zahlen, beginnend mit <math>2</math>, wäre endlos.<br />
Wir benutzen deshalb das Konzept der ''verzögerten Evaluation'' und repräsentieren die natürlichen Zahlen als [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Streams|Stream]].<br />
Das Streichen erfolgt mit der bekannten Prozedur <tt>stream-filter</tt>:
<code id="4bbba01cbbadd" hidden>
(define stream-car car)
(define stream-cdr
(lambda (stm)
(force (cdr stm))))
(define-syntax stream-cons
(syntax-rules ()
((_ head tail) (cons head (delay tail)))))
(define stream?
(lambda (stm)
(and (pair? stm) (promise? (cdr stm)))))
(define stream-map
(lambda (proz stm)
(stream-cons (proz (stream-car stm)) (stream-map proz (stream-cdr stm)))))
(define stream-filter
(lambda (proz stm)
(if (proz (stream-car stm))
(stream-cons (stream-car stm) (stream-filter proz (stream-cdr stm)))
(stream-filter proz (stream-cdr stm)))))
(define show-stream
(lambda (stm n)
(if (= n 0)
(begin
(display "...") (newline)
'ok)
(begin
(display (stream-car stm)) (display ", ")
(show-stream (stream-cdr stm) (- n 1))))))
</code>
<code id="4bbba9a450b38">
(define natstream
(lambda (n)
(stream-cons n (natstream (+ n 1)))))
(define teilbar?
(lambda (n teiler)
(= (modulo n teiler) 0)))
(define primzahlstream
(letrec
([sieb
(lambda (stm)
(stream-cons (stream-car stm)
(sieb (stream-filter
(lambda (n) (not (teilbar? n (stream-car stm))))
(stream-cdr stm)))))])
(sieb (natstream 2))))
</code>
<eval id="4bbba9a451ac0">
(show-stream primzahlstream 25)
</run>
Man beachte, dass <tt>primzahlstream</tt> <u>keine</u> Prozedur ist. Vielmehr werden an diesen Namen <u>alle</u>, d.h. unendlich viele Primzahlen gebunden!
== Aufgaben ==
<ol>
<li>
Geben Sie typische Algorithmen aus dem Alltag an.
</li>
<li>
Beschreiben Sie Vorgänge oder Abläufe, auf die sich offensichtlich der intuitive Algorithmusbegriff <u>nicht</u> anwenden lässt. Begründen Sie.
</li>
<li>
Begründen Sie, warum auch das Sieb des Eratosthenes als Algorithmus bezeichnet werden kann.
</li>
</ol>
== Zum Weiterarbeiten ==
Erstellen Sie für einen der nachfolgenden Algorithmen die entsprechende Seite im ProgrammingWiki.
* <h5>[[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Lösen quadratischer Gleichungen|Lösen quadratischer Gleichungen]]</h5>
* <h5>[[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Das Heron-Verfahren|Das Heron-Verfahren]]</h5>
* <h5>[[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Das NIM-Spiel|Das NIM-Spiel]]</h5>