12.3. Praktische Elementaralgorithmen history menue Letztmalig dran rumgefummelt: 01.06.18 08:08:25

Recherchiert man die bis heute in der Informatikangewandten Programme, so lässt sich deren grundsätzliche Struktur in ca. 20 Grundalgorithmen splitten, welche jeweils in den verschieden Strukturen und Verschachtelungstiefen sowie Datentypen einschließlich Rekursion "verpackt" sind. Die Oberbegriffe der Grundalgorithmen lauten: Tausche, Verschieben, Suchen und Sortieren.

1. Grundalgorithmen
2. Sortieralgorithmen
3. Suchalgorithmen
4. Aufgaben und Lösungsverfahren
5. Verwandte Themen

die Informatikseiten

Algorithmen-Logo

inhaltlich auf korrektem Stand - evtl. partiell unvollständig ;-)

Wissen für Fortgeschrittene der Informatik

Quellen:
hier kommen sofort die Datentypen ins Spiel - oft betrachten wir bei einer hinreichenden Mächtigkeit Arrays als Grundstruktur
Rekursion hat sich mit all seinen Problemen in der Praxis ihrer Entwicklung sowie der Spezifik ihrer Denkweise als ein mächtiges Werkzeug zur Lösung gemausert
„Talente finden Lösungen, Genies entdecken Probleme.“

Krailsheimer

das alles hat ganz viel mit Algorithmen, Programmen und Programmieren sowie mit Computern zu tun und wird in Anwendersoftware unbemerkt eingesetzt
Und wie löse ich meine eigenen Probleme? Mit Psychologie - heißt eigentlich nix anderes, als: ich erkenne und bekämpfe meinen eigenen inneren Schweinehund. Den hat übrigens jeder - tritt' einer vor Dir erfolgreich in Sachen XY auf, war er nur erfolgreich in der Bekämpfung eben seines ... ;-)
... und wie hat er das gemacht? - Na zum Beispiel so:
  1. Salami-Taktik: Unterteilen Sie große Aufgaben in kleine Häppchen. Die können Sie leichter und angenehmer  peu à peu  abarbeiten.
  2. 5-Minuten-Taktik: Erledigen Sie eine unangenehme Aufgabe nur 5 Minuten lang. So verliert sie ihren Schrecken und oft bleiben Sie länger am Ball!
  3. Druck-Taktik: Setzen Sie sich selbst unter Zeitdruck. Sagen Sie sich (oder jemand anderem): "Bis zum ... (Termin) ist die Sache erledigt!"
  4. Erster-Schritt-Taktik: Suchen Sie nicht länger nach Ausflüchten, sondern tun Sie einfach den ersten Schritt und fangen Sie an  ohne weiteres Grübeln.
  5. Abwäge-Taktik: Wägen Sie Vor- und Nachteile eines sofortigen Erledigens ab. Sie werden sehen: Die Vorteile überwiegen ganz klar!
  6. Das-Schlimmste-zuerst-Taktik: Erledigen Sie das Schlimmste zuerst. Dann ist das weg und der Tag kann nur noch schöner werden.
  7. Jeden-Tag-Taktik: Erledigen Sie jeden Tag etwas Schreckliches. Danach geht es Ihnen schlagartig besser. Das könnte Ihr tägliches Erfolgserlebnis sein!

Sekretärinnen News vom 27.4.05


1. Grundalgorithmen history menue scroll up

Wer diese Algorithmen studiert (studieren heißt, sich bemühen - und Mühe ist's ja wohl), entdeckt ganz schnell, dass dahinter die Anforderungen von Datenbanken sowie deren Abfragen stecken ;-)

NP-vollständige sowie NP-schwere Probleme

Tauschalgorithmus

Tauschen von zwei Elementen - Worst-Case: gibt es überhaupt mindestens zwei Elemente? - Typisches Beispiel: "... tauschen wir unsere Schichten im Schichtplan!" - oder aber: (Worst-Case) können wir unsere Schichten überhaupt tauschen?

... als dowloadbare Datei hier verfügbar

 

Radix-Sort

das Gesamtprogramm im ZIP-Format

 
Füllen eines Feldes der Mächtigkeit n mit Elementen eines bestimmten Datentyps - optionaler Worst-Case: vielen verschiedenen Datentypen sowie der dazu erforderlichen Steuerlogik und frei wählbare Dimension der Elemente
Füllen eines Feldes der Mächtigkeit n mit Buchstaben - optionaler Worst-Case: vielen verschiedenen Datentypen sowie der dazu erforderlichen Steuerlogik und frei wählbare Dimension der Elemente
Tauschen von zwei Elementen eines Feldes der Mächtigkeit n
Suchalgorithmen mit der Besonderheit: Wie suchen, wenn der Wertevorrat "mächtig" ist?
... ist ein Element innerhalb der Menge n vorhanden? (Rückgabewert ist eine JA/NEN-Entscheidung) - Typisches Beispiel: "... haben wir einen Schüler namens 'Rumpelstilzchen'?"
... gibt es ein Element mit mehreren bestimmten, genau definierten Eigenschaften oder nicht? (Rückgabewert ist eine JA/NEN-Entscheidung) - Typisches Beispiel: "... ist der rosa Rollkragenpullover in Größe 38 noch auf Lager?"
... wie viel male gibt es ein Element mit mehreren bestimmten, genau definierten Eigenschaften? (im Worst-Case Anzahl einschließlich 0 bzw. alle) - Typisches Beispiel: "... wie viele Male ist der rosa Rollkragenpullover in Größe 38 noch auf Lager?"
... gibt es ein Element mit mehreren bestimmten, genau definierten Eigenschaften mehrfach? (im Worst-Case Anzahl einschließlich 0 bzw. alle) - Typisches Beispiel: "... gibt es den rosa Rollkragenpullover in Größe 38 mehrfach?" (Rückgabewert ist eine JA/NEN-Entscheidung)
... wie groß ist der Abstand mehrerer bestimmter, genau definierten Elemente, was natürlich nur für unsortierte Mengen von Elementen gilt - (aber "AMAZON" macht das so!!!)? (im Worst-Case Anzahl einschließlich 0 bzw. alle) - Typisches Beispiel: "... wie viele Male ist der rosa Rollkragenpullover in Größe 38 noch auf Lager?"
... bestimme das am häufigsten in der Menge vorkommende Element (oder: Worst-Case: die Plätze - respektive die Anzahl) - im Worst-Case auf allen Plätzen oder alle Elemente sind voneinander verschieden - Typisches Beispiel: "... was ist die größte Anzahl von Pullovern einer Größe und wo befinden sich diese im Lager?"
... wo ist der Platz i (oder: Worst-Case: die Plätze) des Elements n innerhalb der Menge - im Worst-Case auf allen Plätzen - Typisches Beispiel: "...wo  ist der rosa Rollkragenpullover in Größe 38 im Lager?"
... bestimmen wir doch mal die Anzahl des Vorkommens eines Elements innerhalb der Menge - dies schließt die Lösung des Problems: ist ein Element innerhalb der Menge n vorhanden - Worst-Case: alle bzw. keines! - Typisches Beispiel: "... wie viele Male ist der Name Müller in der Startliste vorhanden?" (Rückgabewert ist die Anzahl des Vorkommens), (Menge der untersuchten Objekte: ALLE!!!)
... bestimme das kleinste (respektive das größte) Elements innerhalb der Menge - schlimm: mehrere sind das Kleinste -  Worst-Case: alle Elemente sind gleich! - Typisches Beispiel: "... wie hoch ist das größte Punktekonto beim Sportfest?" - wir nennen das MINIMUM- bzw. MAXIMUM-Suche
... bestimme den Platz des kleinsten (respektive das größten) Elements innerhalb der Menge - schlimm: mehrere sind das Kleinste oder Größte -  Worst-Case: alle Elemente sind gleich! - Typisches Beispiel: "... welche Nummer hat das Konto mit dem höchsten (oder niedrigsten) Sparbetrag?" - wir nennen das MINIMUM- bzw. MAXIMUM-Platzsuche
... bestimme die Anzahl aller Elemente innerhalb der Menge - schlimm: jedes Element genau einmal -  Worst-Case: leere Menge!
Verschieben, Rotieren und Spiegeln mit der Besonderheit: Mächtigkeit der Elementemenge, ungerade Anzahl, verschiedene Datentypen
Verschiebe die gesamte Menge um jeweils genau einen Platz - Problem: was wird als neues Element eingefügt? - Typisches Beispiel: "... die Klasse 13 (in einigen Bundesländern die Klasse 14) verlässt die Schule - die neuen Klassen 5 werden eingeschult, alle anderen rücken (theoretisch) eine Klasse nach oben!"
Verschiebe die Menge ab Position n um genau m Plätze - Worst-Case: ist das überhaupt möglich und was wird als neues Element eingefügt?
Rotiere die Feldelemente um genau eine Position nach rechts bzw. links - es gibt mal keinen Worst-Case - Typisches Beispiel: "... Lauflicht - es läuft immer um!"
Spiegeln eines Feldes der Mächtigkeit n - Worst-Case: die Anzahl der Elemente ungerade!

 

Palindrome

PALINDROM-Tester

 
Vertausche zwei Element innerhalb eines Feldes mit bekannter Position
Verschiebe die Elemente eines Feldes um genau einen Platz nach einer gewählten Richtung
Rotiere die Elemente eines Feldes um genau einen Platz nach einer gewählten Richtung
ein gegebenes Feld von Elementen eines beliebigen Datentyps ist zu spiegeln (finde den Datentyp) - Worst-Case: ist die Anzahl der Elemente ungerade?
Einfügen und Löschen sowie Ersetzen von Elementen innerhalb einer Menge mit der Besonderheit: Wenn sich nichts mehr Anfügen (oder Einfügen lässt z. B. wegen der Dimension des Feldes)
Füge ein Element an seinen entsprechenden Platz in einer sortierten Menge ein - es gibt mal keinen Worst-Case selbst wenn die Menge leer ist - Typisches Beispiel: "... ein neuer Schüler kommt in eine Klasse!"
Bestimmen der Häufigkeit des Vorkommens von Elementen in einem Feld
Bestimmen der Anzahl des Vorkommens jedes Elements im Feld und Ausgabe in einer Rangliste - es gibt keinen Worst-Case selbst wenn die Menge leer ist - Typisches Beispiel: "... die Häufigkeitsverteilung von Zeichen in einem Text"


2. Sortieralgorithmen history menue scroll up

Unter Sortieren versteht man das Anordnen einer Folge von Elementen gemäß einer vorgegebenen Ordnung. Jedes Element hat einen für den Sortiervorgang ausschlaggebenden Ordnungsbegriff oder Schlüssel, auf den Vergleichsoperatoren <, <=, =, <>, >= und > anwendbar sind. Teile  bzw. alle der nachfolgend genannten Grundoperationen nutzen alle Sortieralgorithmen: Zuweisen, Vergleichen, Vertauchen. Sortieralgorithmen sind typische Beispiele für lösbare, jedoch in Abhängigkeit der Anzahl der Elemente recht mächtige Probleme.

Logo der Sortieralgorithmen

Gliederung der Sortierverfahren an der Uni Halle

Bubble-Sort

Shaker-Sort

MINIMUM- bzw. MAXIMUM-SORT - auch als Selection-Sort bekannt

Merge-Sort

Bucket-Sort

Index-Sort

Shell-Sort

Distribution Sort (Einführung in die Informatik)

Quick-Sort

Simple-Sort Field-Sort Heap-Sort

Radix-Sort

     


3. Suchalgorithmen history menue scroll up

Unter Suchen versteht man im informationstechnischen Sinne das Registrieren eines oder einer Gruppe von Elementen als Bestandteil einer wohldefinierten Gesamtmenge. In der Realität des Programmierens ist dies dann auch noch abhängig von Datentypen und vor allem von der Datenorganistation.
Ein Suchraum kann sein:
  • eine Datenstrukturinstanz
  • eine Menge bzw. Ansammlung von vernetzten Daten
  • ein Datennetz
  • ein Graph

Der Suchraum besteht aus Knoten (Datenobjekte), die untereinander in Beziehung stehen. Die Suche arbeit sich über vernetzte Knoten – wenn es sein muss – durch das gesamte Knotennetz wie beispielsweise über Nachbarschaftsbeziehungen zwischen den Knoten oder über Vater−Sohn−Beziehungen. Knoten des Suchraums stellen die Argumente/Objekte für das Suchkriterium dar

Suchalgorithmen

Binäre Bäume

Baumstrukturen

Umfahren des Suchbaumes

Breitensuche

Tiefensuche

 

Hash-Verfahren

Umfahren des Suchbaumes

   

 

Lineare Listen

Lineare Suche auf unsortierten Listen

Lineare Suche auf sortierten Listen

Binäre Suche auf sortierten Listen

 

Dijkstra-Suche

Lineare Suche auf unsortierten Listen

Lineare Suche auf sortierten Listen

Binäre Suche auf sortierten Listen

 

Greedy-Suche

Lineare Suche auf unsortierten Listen

Lineare Suche auf sortierten Listen

Binäre Suche auf sortierten Listen

 


4. Aufgaben und Lösungsverfahren history menue scroll up

Hierhinter steckt kein konkreter Algorithmus - und damit schon gar nicht ein Grundalgorithmus. Was wir hier besprechen, ist eine grundsätzliche Art, bestimmte Probleme, die zu einer Klasse gehören mit den gleichen Methoden zu lösen. Ich bin ja der Meinung, schöner kann man objektorientiertes Programmieren nicht formulieren (Rost am 16.10.04 um 23.35 Uhr - komme gerade aus dem Kino: "Der Untergang").
Klassische Prinzipien und Ideen der antiken Mathematik und Problemlösungsstrategie

Euklid von Alexandria

Eratosthenes von Kyene

   
Klassische Verfahren der antiken Mathematik und Problemlösungsstrategien

die Zahlenteiler

GGT

KGV

 

die Primzahlsuche - zumindest die ersten Beschreibungen sind trivial ;-)

die Pseudoprimzahlen

Quersummenermittlung

Primzahlfaktorisierung

 
Interessante (oder uninteressante - je nach Einstellung) Mathematik

die Sache mit der Hamsterbeute

die Wirtshausterteilerei

die Maleraufgabe

 
Lösungsstrategien für derartige Probleme:

Worst-Case-Denken

Brute-Force-Angriffe

das Backtracking-Verfahren

 


5. Verwandte Themen history menue scroll up

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

Algorithmentheorie

Komplexität, Mächtigkeit und Aufwand

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 März 1995

... dieser Text wurde nach den Regeln irgendeiner Rechtschreibreform verfasst - ich hab' irgendwann einmal beschlossen, an diesem Zirkus nicht mehr teilzunehmen ;-)

„Dieses Land braucht eine Steuerreform, dieses Land braucht eine Rentenreform - wir schreiben Schiffahrt mit drei „f“!“

Diddi Hallervorden, dt. Komiker und Kabarettist

Diese Seite wurde ohne Zusatz irgendwelcher Konversationsstoffe erstellt ;-)