Austarierte Bäume history menue Letztmalig dran rumgefummelt: 22.06.20 07:15:48

... das Spiel theoretisch kennt jeder - und mit "Ausprobieren" geht das auch, aber "berechnen" im Vorhinein ist vor allem für unausgewogene Logische Bäume schon etwas komplexer - man muss diese berechnen. Die "Ungleichgewichte" müssen möglichst ausgeglichen werden, auch wenn dies mit den vorher gegebenen "Hebel-Verhältnissen" nicht unbedingt immer auch möglich ist. Sollte dies der Fall sein, sind von Dir "Ausgleichsberechnungen erwünscht!!!
Basis ist immer das Hebelgesetz!
1. Problembeschreibung
2. Hintergründe und Zusammenhänge - Einordnung in Klassen
3. Lösungsalgorithmen
4. Programmvorschläge
5. Zusammenfassung
6. Weiterführende Literatur
7. Linkliste zum Thema
8. Verwandte Themen

Probleme & Problemlösungsverfahren

Logo für den austarierten Baum

begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-)

Informatik-Profi-Wissen

Quellen:

LOG IN - Heft 146/147 (2007) Seite 47 ff.


1. Problembeschreibung history menue scroll up

Hier gibt es zwei mögliche Varianten: ausgewogene sowie unausgewogene austarierte Bäume - in Waage sind sie bei exakter Berechnung beide - die unausgewogenen sind jedoch wesentlich komplexer - erfordern ein Vielfaches an Rechenaufwand.
... ausgewogen austarierte Bäume ... unausgewogen austarierte Bäume

Beispiel für einen ausgewogen austarierten Baum

 


2. Hintergründe, Zusammenhänge - Einordnung in Klassen history menue scroll up

Für kleine Mengen M ist das Problem empirisch durch ausprobieren möglich! Für große Mengen existieren allerdings keine anderen Verfahren, als genau diese: ausprobieren jeden Elements mit jedem - das sind dann aber schon bei 10 Elementen 210 Möglichkeiten.
 


3. Lösungsalgorithmus history menue scroll up
Nimm die vorgegebene Zahl - fülle sie auf vier Stellen auf. Ergibt sich Gleichheit in allen vier möglichen Stellen, so verabschieden wir uns von der Zahl - sie ist keine Zahl innerhalb des Definitionsbereiches - was wir selbstverständlich softwartechnisch exakt wegfangen, wobei wir Oma und/oder Katze nutzen! Wir erhalten in jedem Fall der verbleibenden Restmenge vier Stellen (ungleich in mindest einer Position) und bilden daraus die jeweils kleinste und größte ziffernfolge als Zahl. Von der jeweils größeren subtrahieren wir die jeweils kleinere und verfahren damit, bis wir entweder 6174 oder eine Tiefe von 7 erreicht haben (was im Worst-Case gleichzeitig eintritt).
 
 


4. Programmvorschläge history menue scroll up

Hannes Uhlig hat unser Vorschläge konsequent aufgegriffen und einschließlich der Problematik Oma und Katze ein Programm des Kaprekar-Algorithmus notiert, in welchem schon einige Kerngedanken eines sauberen - eben noch nicht objektorientierten Programmieirstils zusammenlaufen.
 
 


5. Zusammenfassung history menue scroll up

 
 


6. Weiterführende Literatur history menue scroll up

 
 
 
 


7. Links zum Thema history menue scroll up

 
http://www.mathematische-basteleien.de/kaprekarzahl.htm
 


8. 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.

das 8-Dame-Problem

des Cliquen-Problem

Domino-Problem

das Entscheidbarkeitsproblem

das Erfüllbarkeitsproblem

die Fibonacci-Zahlen

das Flaggenproblem

das Halteproblem

das Hamilton-Problem

das K-Farben-Problem

der Kaprekar-Algorithmus

die Magischen Quadrate

das PASCAL'sche Dreiecksproblem

das Philosophenproblem

das Königsberger-Brückenproblem

das Post'schen Korrespondenzproblem

das Rundreiseproblem

das Springer-Problem

die Türme von Hanoi

das Wortproblem

das Wüstenfit-Problem

das 153-Problem

   

Worst-Case-Denken

Algorithmentheorie

Komplexität, Mächtigkeit und Aufwand

Praktische Elementaralgorithmen

Lösbarkeit und Problemlösungsstrategien

Klassische algorithmisch lösbare Probleme

Zufall und Computer

Graphentheorie

Petri-Netze

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 am 22. Juni 2020 um 9.21 Uhr

... 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 ;-)