12.2. Komplexität, Mächtigkeit und Aufwandsbetrachtungen - Effizienz

Letztmalig dran rumgefummelt: 25.06.23 10:34:53

	Vor dem Herangehen an ein Problem steht für den Informatiker die Frage, ob es sich bei der vorliegenden Aufgabe überhaupt um ein lösbares Problem handelt. Fällt es dann grundsätzlich in die Klasse der lösbaren Aufgaben, muss eingeschätzt werden, mit welchem Aufwand ein sinnvolles, evtl. akzeptabel unvollständiges Ergebnis erreicht werden kann. So wird es in absehbarer Zeit definitiv kein perfektes Übersetzungsprogramm geben, was einfach daran liegt, das Sprachen im Kontext betrachtet werden müssen. Das aber können derzeitige Computer und Software nicht leisten. Anders gesagt: es gibt Probleme, welche man mit heute möglichem Aufwand lösen lassen, es existieren solche, die sich heute nicht, aber evtl. morgen schon lösen lassen und da ist die Restmenge der Probleme, welche sich generell nicht lösen lässt, weil es gar nicht geht!
	1. Komplexität 2. Mächtigkeit 3. Aufwandsbetrachtungen 4. Effektivität & Effizienz 5. Laufzeitproblematik 6. Verwandte Themen
	die Informatikseiten Logo für Komplexität, Mächtigkeit und Aufwand inhaltlich auf korrektem Stand - evtl. partiell unvollständig ;-) Informatik-Profi-Wissen
	Quellen: Lehr- und Übungsbuch Informatik Band 1 - 5 Seite ??? Technische und Theoretische Informatik  Seite ???
	„Die rohe Gewalt der computerisierten Zahlenfresserei allein kann das Unendliche nicht erreichen.“ Simon Singh in „Fermats letzter Satz“
	Problemlösungsstrategien sowie Lösungsalgorithmen gibt's in jedem Olsenbande-Film - nach Egon Olsen gehören dazu: "... Kühnheit, Tatkraft, Entschlossenheit sowie Mut und Beherrschtheit!"
	Riemannsche Vermutung letztes Fermatsches Theorem Goldbach-Vermutung Hilbert-Raum Ramanujan-Tau-Funktion Euklids Algorihmus Hardy-Littlewood-Kreismethode Fourier-Reihen Gödel-Nummerierung Siegel-Nullstellen Selbergsche Spurformel Sieb des Eratosthenes Mersenne-Primzahlen Euler-Produkt Gaußsche ganze Zahlen
	David Hillberts 23 wichtige mathematische Probleme des zwanzigsten Jahrhunderts
	... und hier sind sie!
	sieben aktuelle mathematische Probleme des 21. Jahrhunderts - Millenium-Probleme

1. Komplexität eines Problems

	Komplex ist ein Problem, wenn die Anzahl der zur betrachteten Lösung benötigten Operationen hoch - im Einzelfall extrem hoch ist (wird). Komplexe Probleme fallen schon bei geringer Mächtigkeit in die Klasse der nichtlösbaren Probleme.
	Komplexität ist nix weiter als die Anzahl der in Betracht kommenden Operationen, um zur jeweils aktuellen Lösungsstrategie des Problems zu kommen (diese muss damit noch lange nicht effizient sein)
	Komplexität ist schlicht die Anzahl der benötigten Operationen zum aktuellen Lösungsalgorithmus
	bei einer ganzen Reihe der nun folgenden Probleme stoßen wir auf die Klasse der NP-vollständige sowie NP-schwere Probleme - unbedingt vorab dazu informieren, was das ist und welche Aufgaben da auf uns zukommen Zeitkomplexität Algorithmentheorie Gretchen-Frage

2. Mächtigkeit eines Problems

	Mächtig ist ein Problem, wen die Anzahl der zur betrachteten Lösung benötigten Operanden hoch - im Einzelfall extrem hoch ist (wird). Mächtige Probleme fallen schon bei geringer Komplexität in die Klasse der nichtlösbaren Probleme.
	Mächtigkeit ist nix weiter als die Anzahl der in Betracht kommenden Elemente, um zur jeweils aktuellen Lösungsstrategie des Problems zu kommen (diese muss damit noch lange nicht minimal sein)
	Mächtigkeit ist schlicht die Anzahl der benötigten Operanden zum aktuellen Lösungsalgorithmus
	Mächtigkeit kann uns in drei verschiedenen Formen gegenüber treten: in der Anzahl der Argumente (Hauptparameter), für welche eine Lösung gesucht wird die Anzahl der Zwischenwerte (Unterparameter), die zur Lösung für ein Argument (Hauptparameter) benötigt werden die schlichte Größe des einen Ergebnisses zu einem Argument (Hauptparameter) bzw. bereits seiner Zwischenwerte (Unterparameter)

3. Aufwandsbetrachtungen eines Problems

	Aufwand ist das Produkt von Komplexität und Mächtigkeit (wobei die Mächtigkeit die Anzahl der Ausgangsfaktoren darstellt), wenn wir die Komplexität (was sie meist auch ist) als Wiederholung eine Blockes identischer Anweisungen auffassen.
	das Aufwands-Logo
	Beide Übel für sich allein genommen (Komplexität oder Mächtigkeit) sind schon gewaltige Schranken zur Lösung von Problemen - oft aber finden sie auch noch zueinander und machen so Aufgabenstellungen praktisch unmöglich - dies zumindest in einem sinnvollen Zeitraum. Um auf dem Computer Algorithmen abarbeiten zu können, muss Aufwand betrieben werden. Klar ist auch, dass der Aufwand mit steigender Kompliziertheit aber auch mit größerer Menge von Daten und/oder mathematischer Operationen wächst (der Algorithmus wird komplexer!). Schnell wird der Ruf nach größeren und schnelleren Computern laut, vergessen wird vom Laien, dass die Verringerung des Aufwandes - evtl. noch gekoppelt mit leistungsfähigeren Maschinen die Lösung u. U. bringen kann.
	Der Aufwand ist ein Ausdruck für die Komplexität (Kompliziertheit) von Algorithmen. Algorithmische Lösung von Problemen wird auf Computern durch Zeit und Speicherbelastung bestimmt. Durch zwei Maße kann der Aufwand charakterisiert werden: die Größe des Problems n Zeitaufwand für die typischen Elementaroperationen A Relation von Problemgröße und zu betreibenden Aufwand bei der Problemlösung
	Was ist Aufwand im Sinne der Informatik? Aufwand zur Lösung von Problemen durch Algorithmen auf Computern: Anzahl der Steueroperationen Anzahl von Vergleichsoperationen Anzahl der Tauschoperationen Anzahl von Suchvorgängen Beanspruchung von Hauptspeicher Auslagerung von Daten und Zugriff auf ausgelagerte Daten Mächtigkeit des Problems Problemklasse Zufall Aufwand muss messbar gemacht werden - also benötigen wir messbare Kriterien! In der Informatik: Zeit Speicherbedarf Auslagerungsdateien und andere Ressourcen Anzahl von Prozessoren und/oder Computern bei komplexen Problemen Bestimmung von echten Zufallsgrößen Zeitbestimmende Maße beim Computer sind: die Problemgröße n (die Mächtigkeit des Problems) Arbeit an typischen Operationen A (Additionen, Schleifensteuerungen, Vergleichen, Austauschen, Suchen) Anzahl der Bestimmung von echten Zufallsgrößen Aufwandsbezüge auf die Zeiteinheiten Vergleichen 1 ZE Lesen einer Variablen 1 ZE Speichern einer Variablen 1 ZE Lesen einer k-fach indizierten Variablen (k+1) ZE Addition 5 ZE Multiplikation 10 ZE Zyklussteuerung 5 ZE Bestimmung einer echten Zufallsgröße: 450 ZE
	Aufwandsanalyse Wie oben erwähnt wurde, besitzen die meisten Algorithmen einen Hauptparameter N, (gewöhnlich die Anzahl der zu verarbeitenden Datenelemente) der die Laufzeit am stärksten beeinflusst. Der Parameter N könnte der Grad eines Polynoms sein, die Größe einer zu sortierenden oder zu durchsuchenden Datei, die Anzahl der Knoten in einem Graph usw. Bei praktisch allen Algorithmen in diesem Buch ist die Laufzeit zu einer der folgenden Funktionen proportional: Aufwand direkt: ein Argument mehr, ein Schritt mehr - wir sprechen vom Aufwand 1 Die meisten Anweisungen in der Mehrzahl der Programme werden einmal oder höchstens einige Male ausgeführt. Falls alle Anweisungen eines Programms diese Eigenschaft haben, sagen wir, dass seine Laufzeit konstant ist. Offensichtlich ist das die Situation, die bei der Entwicklung von Algorithmen angestrebt werden sollte. log N Wenn die Laufzeit eines Programms logarithmisch ist, wird das Programm mit wachsendem N allmählich langsamer. Diese Laufzeit tritt gewöhnlich bei Programmen auf, die ein umfangreiches Problem lösen, indem sie es in ein kleineres Problem umwandeln, wobei sie den Umfang auf einen gewissen konstanten Anteil verringern. Für unsere Belange kann angenommen werden, dass die Laufzeit kleiner ist als eine »große« Konstante. Die Basis des Logarithmus beeinflusst die Konstante, jedoch nicht sehr: Hat N den Wert eintausend, so hat log N zur Basis 10 den Wert 3, zur Basis 2 den Wert 10; beträgt N eine Million, so ist log N jeweils doppelt so groß. Bei jeder Verdopplung von N wächst log N um einen gewissen konstanten Wert; eine Verdopplung des Wertes findet jedoch erst statt, wenn N auf N2 angewachsen ist. Aufwand N: ein Argument mehr, N Schritte mehr - wir sprechen vom Aufwand N Wenn die Laufzeit eines Programms linear ist, entfällt im allgemeinen ein kleiner Anteil der Verarbeitung auf jedes Element der Eingabedaten. Wenn N eine Million beträgt, dann ist die Laufzeit ebenso groß. Jedes mal, wenn N sich verdoppelt, trifft das auch für die Laufzeit zu. Dies ist die optimale Situation für einen Algorithmus, der N Eingabedaten verarbeiten muss (oder N Ausgabewerte erzeugen muss). N log N Diese Laufzeit tritt bei Algorithmen auf, die ein Problem lösen, indem sie es in kleinere Teilprobleme aufteilen, diese unabhängig voneinander lösen und dann die Lösungen kombinieren. Mangels eines passenderen Adjektivs (linearithmisch?) werden wir sagen, dass die Laufzeit eines solchen Algorithmus »N log N« beträgt. Wenn N eine Million ist, beträgt N log N vielleicht zwanzig Millionen. Wenn sich N verdoppelt, wird die Laufzeit mehr als doppelt so groß (aber nicht wesentlich mehr). N2  quadratischer Aufwand Wenn die Laufzeit eines Algorithmus quadratisch ist, lässt er sich praktisch nur für relativ kleine Probleme anwenden. Quadratische Laufzeiten sind typisch für Algorithmen, die alle paarweisen Kombinationen von Datenelementen verarbeiten (eventuell in einer doppelt verschachtelten Schleife). N3 kubischer Aufwand Wenn N eintausend beträgt, ist die Laufzeit eine Million. Wenn N sich verdoppelt, vervierfacht sich die Laufzeit. Analog gilt, dass ein Algorithmus, der Tripel von Datenelementen verarbeitet (zum Beispiel in einer dreifach verschachtelten Schleife), eine kubische Laufzeit hat und praktisch nur für kleine Probleme verwendbar ist. Wenn N einhundert beträgt, ist die Laufzeit eine Million. Wenn sich N verdoppelt, erhöht sich die Laufzeit auf das Achtfache. Bei wenigen Algorithmen mit exponentieller Laufzeit kann man erwarten, dass sie für praktische Zwecke geeignet sind, obwohl solche Algorithmen in natürlicher Weise als »gewaltsame« Lösungen von Problemen auftreten. Wenn N zwanzig beträgt, ist die Laufzeit eine Million. Bei jeder Verdopplung von N, wird die Laufzeit quadriert! Die Laufzeit eines speziellen Programms ist meist ein konstantes Vielfaches eines dieser Terme (des Führenden Terms) plus einiger kleinerer Terme. Die Werte des konstanten Faktors und der zusätzlichen Terme hängen von den Ergebnissen der Analyse und von Einzelheiten der Implementation ab. Grob gesagt hat der Koeffizient des führenden Terms etwas mit der Anzahl der Anweisungen in der inneren Schleife zu tun: Bei jedem Schritt der Entwicklung eines Algorithmus tut man gut daran, die Zahl solcher Anweisungen zu begrenzen. Für große N überwiegt der Einfluss des führenden Terms; für kleine N oder für sorgfältig gestaltete Algorithmen können mehrere Terme die Laufzeit spürbar beeinflussen und Vergleiche von Algorithmen komplizieren. In den meisten Fällen werden wir die Laufzeit von Programmen einfach als »linear«", N log N« »kubisch« usw. bezeichnen, wobei - auch wenn dies nicht ausdrücklich gesagt wird - klar ist, dass in Fällen, in denen die Effizienz sehr wichtig ist, eine eingehendere Analyse oder empirische Untersuchungen vorgenommen werden müssen. Literatur: Schülerduden "Die Informatik - Ein Sachlexikon für die Schule", Bibliografisches Institut & F. A. Brockhaus AG, 2. Auflage; 1991
	Algorithmen unterscheiden sich bei ihren Lösungsverfahren, ihrer Mächtigkeit und ihrer Komplexität ...
	... kurz: sie unterscheiden sich durch den zu betreibenden Aufwand
	überproportionaler Aufwand

4. Effektivität & Effizienz

	Effizienz ist eine Art Wirkungsgrad eines Algorithmus. Nicht nur der Aufwand, sondern auch die Eleganz der Ausführungsroutine wird hier betrachtet. Daneben werden auch Speicherplatzbedarf, Anzahl benötigter Hilfsvariablen und Felder registriert. Einfach die Menge der benötigten Ressourcen, welche benötigt werden, um zu einem sinnvollen Ergebnis zu kommen, wird mit betrachtet.
	Betrachtungen zur Effektivität Logo der Effiektivität Autoproduktion am Fließband bei Henry Ford 1910 - das war ungeheuer effektiv Effektivität am Beispiel des  Bubble-Sort-Algorithmus sieben Wege zur Effektivität
	effektive Algorithmen lösen Probleme in minimal möglicher Zeit mit beliebigem Aufwand sowie hinreichender Sicherheit unter  Nichtbeachtung des "ökonomischem Einsatzes" von Ressourcen
	Algorithmen unterscheiden sich bei ihren Lösungsverfahren in dem benötigtem Aufwand an Ressourcen und Intelligenz (... oder Raffinesse)
	Betrachtungen zur Effizienz Logo der Effizienz Effizienz am Beispiel des  Bubble-Sort-Algorithmus
	effiziente Algorithmen lösen Probleme in minimal möglicher Zeit mit minimalem Aufwand sowie maximaler Sicherheit unter "ökonomischem Einsatz" von Ressourcen. Und der Informatiker erkennt wie der Mathematiker in richtigen Lösungen, dass die verfahren anfangen, "schön" auszusehen.
	Komplexität ist nix weiter als die Anzahl der in Betracht kommenden Operationen, um zur jeweils aktuellen Lösungsstrategie des Problems zu kommen (diese muss damit noch lange nicht effizient sein) - Effizienz minimiert den Aufwand im Durchschnitt der Fälle
	Komplexität ist schlicht die Anzahl der benötigten Operationen
	Algorithmen unterscheiden sich bei ihren Lösungsverfahren in dem benötigtem Aufwand an Ressourcen und Intelligenz (... oder Raffinesse)

5. Laufzeitproblematik

	Laufzeitproblematisch oder -kritisch sind Algorithmen genau dann, wenn nach dem Start des Programms bis zur endgültigen Lösung ein vertretbarer Zeitaufwand nicht oder nicht unbedingt gegeben ist. Leider gehören in diese Gruppe eine ganze Reihe recht sinnvoller und praktisch auch benötigter Lösungen. Gemein ist ihnen allen, dass der Aufwand zu ihrer Lösung überproportional
	Logo der Laufzeitproblematik
	die Perfect Numbers die befreundeten Zahlen das 153-Problem - Narziß-Zahlen

6. 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 Algorithmentheorie Praktische Elementaralgorithmen Lösbarkeit und Problemlösungsstrategien Klassische algorithmisch lösbare Probleme Zufall und Computer Graphentheorie Petri-Netze Traversierungs-Probleme Baumstrukturen Turingmaschine Sortieralgorithmen
	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 November 2002