12.1. Algorithmen sowie algorithmische Rätsel und Knobelaufgaben

Letztmalig dran rumgefummelt: 31.01.09 03:48:04

	Algorithmus - (algorithm) Auch Rechenanweisung. Eine endliche Menge von eindeutig festgelegten Regeln zur Lösung eines Problems durch eine endliche Menge von Einzelschritten. Ein Algorithmus ist demnach eine Beschreibung der Methode, ein Problem oder eine Aufgabe zu lösen. Er besteht aus einer Folge von Einzelschritten, deren richtige Abarbeitung die gegebene Aufgabe erfüllt. Diese Abarbeitung bezeichnet man als einen Prozess. In der Mathematik werden solche Algorithmen als Voraussetzung für die Lösung von berechenbaren, entscheidbaren und aufzählbaren Problemen verwendet. Jedoch ist der Begriff des Algorithmus übertragbar auf sämtliche anderen Bereiche, in denen ebenfalls nach gegebenen Regeln vorgegangen wird. Konstruiert man eine Apparatur, die einen Prozess nach einem Algorithmus durchführen kann, so spricht man von einem Prozessor. Typische Prozessoren sind Automaten, zu denen Computer zu rechnen sind. Computer erhalten ihre Algorithmen in Form von Programmen, die mit Hilfe von Programmiersprachen formuliert worden sind Programme sind also Algorithmen.
	1. Definitionsversuch 2. Arten und Grenzen von Algorithmen - Algorithmierbarkeit von Problemlösungen 3. Eigenschaften des Algorithmus 4. Erweiterung des Algorithmenbegriffes 5. Zusammenfassung 6. Grundalgorithmen und Problemstellungen 7. Algorithmierbare Rätsel & Knobelaufgaben 8. Gierige Algorithmen 9. Verwandte Themen
	die Informatikseiten Logo zur Algorithmentheorie inhaltlich auf korrektem Stand - evtl. partiell unvollständig ;-) Basiswissen der Informatik Wissen für Fortgeschrittene der Informatik
	Quellen: Lehr- und Übungsbuch Informatik Band 1 - 5 Seite ??? Technische und Theoretische Informatik  Seite ???
	In neuerer Zeit hat man entdeckt, dass es bei der Gestaltung von Computerprogrammen praktisch nur drei Grundformen von Algorithmen-Mustern gibt, die Reihung (Sequenz), die Auswahl (Selektion) und die Wiederholung (lteration). Das hat zu einer völligen Umstellung der Programmiertechnik (Programmierung, strukturierte) geführt, die erhebliche Verbesserungen hinsichtlich der Übersichtlichkeit, der Änderungsfreundlichkeit und der Benutzerfreundlichkeit bewirkte. Diese Erkenntnisse haben sich bis in die Konstruktion neuer Sprachen ausgewirkt (z. B. bei PASCAL). Besondere Probleme im Zusammenhang von Algorithmen bestehen in ihrer Berechenbarkeit, ihrer Komplexität und ihrer Korrektheit. Wichtige theoretische Vorarbeiten für die Entwicklung von Computern wurden bereits durch die Untersuchungen von Turing u. a. über A. geleistet. Der Name Algorithmus leitet sich von dem Namen des iranischen Mathematikers und Astronomen Mohammed ibn Musa al-Chwarismi ab, der um 820 u. a. Lehrbücher über Algebra schrieb. Diese Bücher wurden im Mittelalter auch ins Lateinische übersetzt und hatten große Verbreitung sowohl im arabischen Kulturkreis als auch in Europa. Lit.: Horowitz, e.: S. Sahni: Fundamentals of Computer Algorithms, Rockwell 1978. Hoßfehl, E: Parallele Algorithmen, Berlin, Heidelberg u. a. 1983. Goldschlagcr, L.; A. Lister: Informatik. Eine moderne Einführung. München/Wien 1984. Mehlkorn, K.: Datenstrukturen und effiziente Algorithmen, 2. Aufl. Stuttgart 1988.
	Rezept zur Zubereitung einer Elefanten-Crème Je nach Personenzahl einen bis zwei zarte Elefanten mit 3 Litern Vollmilch und 150 g Zucker kurz aufwellen lassen, unter ständigem Rühren 1 Eigelb beigeben, in gespülte Puddingform gießen, nach dem Erkalten stürzen und mit Mandeln servieren. Statt der Elefanten können auch Schokolade, Vanille oder Himbeeren verwendet werden. Loriot
	Beachte: Murphys Gesetze sowie deren Optimierung durch Computer, denn: wer Algorithmen entwickelt, macht Fehler

1. Definistionsversuch

	Algorithmen sind Werkzeuge zum Problemlösen sie sind sehr starke Werkzeuge jedes Werkzeug hat seine Einsatzgrenzen - wo liegen die Grenzen des Algorithmus? öffentliche Meinung: Algorithmen und schnelle/viele Computer lösen jedes Problem Der Algorithmus ist eine direkte Folge von Zustandsinformationen, ist eine endliche, geordnete Menge von Aktivitäten, durch die der Zustand vom Datenobjekt verändert wird. Die Teilordnung dieser Aktivitäten bestimmt die Reihenfolge ihrer Ausführung, sie wird konstituiert durch die zwischen ihnen bestehende Datenabhängigkeit. Jede Lösung entspricht einem Algorithmus.
	um ein Problem zu lösen, muss Aufwand betrieben werden
	„Ist eine präzise, endliche Verarbeitungsvorschrift, deren Elementaroperationen so ausführlich formuliert sind, dass sie von einem Computer ausgeführt werden können. Dabei muss die Anzahl der möglichen Elementaroperationen beschränkt sein, was auch für die Ausführungszeit gilt. Aus der sprachlichen Darstellung des Algorithmus muss die Abfolge der einzelnen Schritte eindeutig hervorgehen. Wahlmöglichkeiten sind zugelassen, diese Auswahl muss aber eindeutig sein.“ nach „Scriptum der Inforamtik“
	Naiver Algorithmenbegriff: endlich lange Beschreibung endliche Ausführungzeit Klarheit in der Ausführung was ist zu tun? womit wird etwas getan? wie geht es weiter? gleiche Eingabe erzwingt gleiche Ausgabe Erfassen einer Klasse von Problemen konkretes Einsatzgebiet Darstellung der Aufgabe in einer Eingabesprache Darstellung des Resultates in einer Ausgabesprache
	mehr gibt's hier

2. Arten und Grenzen von Algorithmen - Algorithmierbarkeit von Problemlösungen

	Das muss aber auch einfacher gehen ;-)
	Algorithmen kann man unterteilen in numerische Algorithmen Ausgabegrößen entstehen über numerische Funktionen und Operationen aus den Eingabegrößen lineare Algorithmen lineare Rekursion Polynome Matrixoperationen nichtlineare Algorithmen Differentialgleichungen Transformationen Korelationsgleichungen nichtnumerische Algorithmen keine Veränderung von Werten - nur eine Beziehung zur Umgebung mathematische Operationen Geometrie Graphenalgorithmen logische Operationen Suchen Mischen Testen Sortieren sonstige Algorithmen Medizin Biologie Technik
	Wohl schon alleine, um nicht in den Verdacht zu geraten, den technischen Fortschritt all zu sehr zu bejubeln, findet man in fast allen Richtlinien die Aufforderung, im Informatikunterricht auch Aussagen zu den „Grenzen“ der Computer zu machen. Meist wird dieser Aufgabe dadurch entsprochen, in einer Lerneinheit der theoretischen Informatik etwa beim Thema „Turingmaschinen“ Berechenbarkeits- und Entscheidbarkeitsprobleme zu behandeln. Abgesehen davon, dass solche Fragen nicht in allen Kursfolgen angesprochen werden können (und die meisten Schüler/innen damit keine Aussagen zu den „Grenzen“ im Informatikunterricht vorfinden werden), sind die heranzuziehenden Beispiele der theoretischen Informatik in diesem Bereich so abstrakt, dass bei den Schülern durchaus der Eindruck entstehen kann, für „praktische“ Fragen wären Computer „grenzenlos“ geeignet. Dem ist aber nicht so, denn Grenzen in der Anwendbarkeit von Rechnern zeigen sich auf sehr unterschiedlichen Gebieten: Numerische Grenzen zeigen sich bei der Zahlendarstellung. Größere Zahlenmengen können praktisch nur in festem Format, also mit eingeschränkter Genauigkeit dargestellt werden. Daraus resultieren Folgefehler, die etwa bei Rundungsproblemen in bekannter Weise leicht zu zeigen sind. Auch extreme Wechsel in den Größenordnungen der verarbeiteten Zahlen führen zu unsinnigen Ergebnissen. Ein Beispiel dafür sind Reihenentwicklungen mit sehr großen Summanden, die zu einem Ergebnis führen, das klein gegen diese Summanden ist. Selbst die Benutzung von „algebraischen“ Programmen löst dieses Problem nicht, denn die Genauigkeit der Rechner ist auch dann durch den vorhandenen Speicher begrenzt. Zeitliche Grenzen zeigen sich dann, wenn theoretisch lösbare Probleme praktisch nicht bearbeitet werden können, weil die zur Verfügung stehende Zeit nicht reicht. Beispiele dafür sind Programme, bei denen der Zeitbedarf exponentiell mit der Zahl der zu verarbeitenden Daten wächst. (Etwa beim Sortieren, beim Suchen im Baum, ...). Grenze der Algorithmierbarkeit zeigen sich bei den angesprochenen Themen der theoretischen Informatik Halteproblem’’, ...). Grenzen in den Abbildungsmöglichkeiten zeigen sich, wenn relevante Aspekte einer Problemstellung sucht in einem Modell beschrieben werden können, das sich auf von Computern verarbeitbare Strukturen abbilden lässt. („Schönheit“ ...) Grenzen der Zulässigkeit, Computer anzuwenden, zeigen sich bei Problemen, wo eine ethisch-moralische Bewertung erforderlich ist. (Was ist „richtig, wichtig, gut“?) Grenzen in der Zuverlässigkeit der Ergebnisse zeigen sich bei Fragestellungen, in denen etwa „chaotische“ Bereiche erreicht werden können, in denen die gelieferten Ergebnisse aus den Startwerten nicht mehr gefolgert werden können, weil schon kleinste Schwankungen zu völlig anderen Resultaten führen. (Beispiel: „Apfelmännchen“, ...) Schon im Anfangsunterricht können Fragestellungen behandelt werden, die „die Grenzen der Computer“ erfahrbar werden lassen. Insbesondere ist es meist nicht notwendig, zu diesem Zweck Programme zu schreiben, denn die interessanteren Fragestellungen ergeben sich, wenn anhand von Fallbeispielen allgemein erörtert wird, auf welchen Gebieten Computer vielleicht besser nicht eingesetzt werden sollten.

3. Eigenschaften des Algorithmus

	Bisher haben wir uns mit einer vorläufigen Umschreibung des Begriffs „Algorithmus“ begnügt; nunmehr ist es an der Zeit, ihn geeignet zu präzisieren. Aus einer Analyse des Algorithmenbegriffes versprechen wir uns Aufschluss hinsichtlich der Frage, bei welcher Art von Problemen überhaupt Informatiksysteme eingesetzt werden können. Wir waren bis zu der vorläufigen Antwort vorgedrungen, dass sich das Lösungsverfahren „algorithmisieren“ lassen müsse. Was heißt das aber? Zuvor jedoch noch einige Bemerkungen zur Herkunft des Wortes. In dem Wort „Algorithmus“ lebt der Name des Universalgelehrten ABU JAFAR MUHAMMAD IBN MUSA AL-HWARIZMI (783 - 850) aus der in Mittelasien (Usbekistan) gelegenen Landschaft Choresmien fort, welcher etwa seit dem Jahr 800 an der Akademie der Wissenschaften („Haus der Weisheit“) zu Bagdad - zusammen mit anderen Gelehrten - indische und griechische wissenschaftliche Schriften ins arabische übersetzte und auf dieser Grundlage selbst weiter forschte. Er schrieb mathematische und astronomische Lehrbücher, unter anderem ein weit verbreitetes und einflussreiches Mathematikwerk mit dem Titel KITAB AL_JABR WAL_MUQABALA, d. h., „Buch für die Rechnung durch Vergleich und Reduktion“, welches im 13. Jhd. ins lateinische übersetzt wurde. In der Übersetzung beginnen die Kapitel jeweils mit DIXIT ALGORITHMI, d.h. „Also sprach Al-Khwarizmi!“. Diese Bücher wurden im Mittelalter auch ins Lateinische übersetzt und hatten große Verbreitung sowohl im arabischen Kulturkreis als auch in Europa.
	Endlichkeit der Beschreibung (Finitheit) Ebenso wie die Daten muss auch ein Algorithmus dargestellt, d. h. beschrieben werden. Diese Beschreibung besteht aus einem Text endlicher Länge, welcher sich auf einzelne Verarbeitungsschritte bezieht. Die Bedingungen der Endlichkeit scheint zunächst überflüssig, da niemand unendlich lange Texte aufschreiben oder lesen kann. Gemeint ist damit, dass Notationen wie z. B. 1+1/2 +1 1/3+ .... nicht zulässig sein sollen.
	Präzise und eindeutige Beschreibung Ein Algorithmus steuert eine Folge von Verarbeitungsschritten. Die einzelnen Schritte und ihre Abfolge müssen unmissverständlich beschrieben sein. Diese unmissverständliche Beschreibung hat u. a. zur Konsequenz, das jeder, auch wenn er die Bedeutung des Algorithmus überhaupt nicht verstanden hat, ihn korrekt ausführen kann, wenn er nur der Vorschrift genau folgt. Dies ist notwendige Voraussetzung dafür, das eine Maschine, welche ja keinen Zugang zur Bedeutung hat, den Algorithmus ausführen kann.
	Effektivität Jeder einzelne Verarbeitungsschritt eines Algorithmus muss durch die Verarbeitungskomponente des Informatiksystems tatsächlich ausführbar sein. Um dies zu erreichen, werden Anweisungen so in elementare Schritte zerlegt, dass sie von der Verarbeitungskomponente ausgeführt werden können. Mit der Forderung nach Effektivität sollen auch Operationen wie z. B. die Division durch Null oder Anweisungen wie zum Beispiel „Falls die Dezimalbruchentwicklung von p die Ziffer sieben endlich oft enthält, setze x:=x+5“ ausgeschlossen werden. Der Begriff der Effektivität ist nicht mit dem der Effizienz Wirksamkeit (im Verhältnis zu den aufgewandten Mitteln) zu verwechseln.
	Allgemeinheit (Abstraktheit) Interpretiert man die Eingabedaten als Beschreibung der Anfangssituation eines realen Systems oder eines Problems und die Ausgabedaten als Endsituation, so soll ein Algorithmus in dem Sinne allgemein sein, dass er nicht einen Einzelfall, sondern stets eine ganze Klasse von Problembeschreibungen verarbeitet. Es wäre ja auch sinnlos, einen „Algorithmus“ zur Berechnung von 7 mal 13 (beispielsweise) zu entwickeln. Diesen könnte man einfach in die Worte „sieben mal dreizehn ist gleich einundneunzig“ kleiden. Neben diesen - für den Algorithmusbegriff kennzeichnenden - gibt es weitere Eigenschaften, die Algorithmen haben können, aber nicht müssen.
	ein Algorithmus heißt terminierend (abbrechend), wenn er bei jeder Anwendung nach endlich vielen Verarbeitungsschritten zum Ende kommt und die Ausgabedaten als Ergebnis liefert. Es gibt Algorithmen, die - mindestens potentiell - nicht abbrechen (etwa im Betriebssystem eines Computers oder zur Steuerung eines chemischen Prozesses).
	ein Algorithmus heißt deterministisch, wenn in der Verarbeitungsfolge jeder Schritt eindeutig festgelegt ist, andernfalls nicht deterministisch. Ein nicht deterministischer Algorithmus kann mehrere verschiedene Schritte als mögliche Fortsetzungen eines Arbeitsschrittes festlegen und dabei offenlassen, welcher tatsächlich zu wählen ist.

4. Erweiterung des Algorithmenbegriffs

	Mit dem bisherigen festen Algorithmenverständnis sind wir nicht in der Lage, die Welt sowie ihr innewohnende Problemstellung hinreichend zu beschreiben - wir müssen für das klassische Algorithmenverständnis allgemein gültige Erweiterungen zulassen.
	Die mathematische Grundlagenforschung vollzog im Laufe dieses Jahrhunderts eine Präzisierung des Algorithmus-Begriffs. Es wurden unabhängig voneinander mehrere solcher Präzisierungen entwickelt, die sich später als gleichwertig erwiesen. Die bekanntesten Mathematiker, die auf diesem Gebiet Marksteine setzten, waren K. GÖDEL, A. CHURCH und A. M. TURING. Wir greifen im folgenden den Ansatz des Engländers Turing (1912-1954) auf, der 1936 die nach ihm benannten Turingmaschinen als Modelle von Berechnungsverfahren entwickelte.
	nichtdeterministische Algorithmen sind zugelassen (Zufallszahlen sorgen mindestens einmal für die zufällige Wahl des Operanden, der Operation oder der Fortsetzung) gleiche Eingabedaten bewirken nicht mehr gleiche Ausgabedaten
	Kopplung eines Algorithmus an einen Datenbestand - lernender Algorithmus
	Algorithmen können theoretisch endlos werden - Betriebssysteme

5. Zusammenfassung

	Ergänzt um diese Positionen und Akzeptiert die praktischen Forderungen, ergibt sich hier ein derzeit vollständig funktionierender Algorithmenbegriff. Er erweitert den klassischen Begriff um die Komponente Zufall (gleicher Input generiert nun nicht mehr zwingend gleichen Output) sowie das schmälern der Forderung nach einem Ende - Algorithmen müssen nicht mehr notwendigerweise terminieren.
	Ein Algorithmus endet „irgendwann“!
	Ein Algorithmus ist „eindeutig (genau)“ in seiner Beschreibung!
	Ein Algorithmus bricht nur nutzerdefiniert ab und „nicht irgendwie“!
	Ein Algorithmus beschreibt kein Problem, sondern eine „Problemklasse“!
	Determinierende Algorithmen „enden“! - Es gibt jedoch praktisch nicht determinierende Algorithmen - siehe dazu Betriebssysteme
	Nach einem Schritt ist der nächste Schritt genau bekannt!

6. Grundalgorithmen und Problemstellungen

	Analysiert man die Aufgabenbereiche der Anwendersoftware, dann stellt man schnell fest, dass sich alle Aufgabenstellungen an ca. 20 Grundalgorithmen auf Basis von Arrays und Dynamischen Variablen zurückführen. Diese werden dann lediglich den drei Grundstrukturen folgend miteinander kombiniert und/oder geschachtelt.
	... einfache, aber auch schon komplexe Grundalgorithemen der informatik ... einfache, aber auch schon komplexe Probleme der Informatik Grundalgorithmen Probleme der Informatik

7. Algorithmische Rätsel und  Knobelaufgaben

	Die Aufgaben sind nicht mit Formeln und irgendwelcher allgemein aufstellbaren Logik abzuwickeln - hier muss schrittweise vorgegangen und das Teilresultat auf seine weitere Verwendbarkeit im Sinne des Algorithmus - also des Gesamtzusammenhangs überprüft werden.
	Rätsel-Seiten
	die Magischen Quadrate von Stefan Hecker

8. Gierige Algorithmen - Greedy-Algorithmen

9. Verwandte Themen

	Das Vorangestellte hilft wirtschaften, löst jedoch kein einziges Problem (allerdings ohne Beachtung der Worst-Case-Strategien wird man auch nicht erfolgreich Software entwickeln und/oder informatische Projekte realisieren können). Deshalb nunmehr das, was wirklich Arbeiten hilft.
	Worst-Case-Denken Komplexität, Mächtigkeit und Aufwand Praktische Elementaralgorithmen Lösbarkeit und Problemlösungsstrategien Klassische algorithmisch lösbare Probleme Zufall und Computer Graphentheorie Petri-Netze Traversierungs-Probleme Baumstrukturen Turingmaschine
	Informationsbegriff Logo für die Signale Nachrichten Wissen Systembegriff Modellbegriff Simulation Denken und Sprache Zahlen, Daten und Datentypen Gegenläufigkeit und Verklemmung Pattern-Matching

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost im August 2003