12.2. Komplexität, Mächtigkeit und Aufwandsbetrachtungen - Effizienz history menue Letztmalig dran rumgefummelt: 12.12.16 18:19:21

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:

„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!"


1. Komplexität eines Problems history menue scroll up

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 history menue scroll up

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 history menue scroll up

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 history menue scroll up

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 history menue scroll up

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

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

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