Komplexität (Informatik)

Komplexität (Informatik)

Komplexität bezeichnet in der Informatik die „Kompliziertheit“ von Problemen, Algorithmen oder Daten. Die Komplexitätstheorie befasst sich dabei mit dem Ressourcenverbrauch von Algorithmen, die Informationstheorie dagegen verwendet den Begriff für den Informationsgehalt von Daten (siehe unten).

Inhaltsverzeichnis

Komplexität von Algorithmen

Unter der Komplexität (auch Aufwand oder Kosten) eines Algorithmus (nicht zu verwechseln mit der Algorithmischen Komplexität, siehe unten) versteht man in der Komplexitätstheorie seinen maximalen Ressourcenbedarf. Dieser wird oft in Abhängigkeit von der Länge n der Eingabe angegeben und für große n asymptotisch unter Verwendung eines Landau-Symbols abgeschätzt. Analog wird die Komplexität eines Problems definiert durch den Ressourcenverbrauch eines optimalen Algorithmus zur Lösung dieses Problems. Die Schwierigkeit liegt darin, dass man somit alle Algorithmen für ein Problem betrachten müsste, um die Komplexität desselben zu bestimmen.

Die betrachteten Ressourcen sind fast immer die Anzahl der benötigten Rechenschritte (Zeitkomplexität) oder der Speicherbedarf (Platzkomplexität). Die Komplexität kann aber auch bezüglich einer anderen Ressource bestimmt werden. Dabei interessiert nicht der Aufwand eines konkreten Programms auf einem bestimmten Computer, sondern viel mehr, wie der Ressourcenbedarf wächst, wenn mehr Daten zu verarbeiten sind, also z. B. ob sich der Aufwand für die doppelte Datenmenge verdoppelt oder quadriert (Skalierbarkeit).

Oft ist es sehr aufwändig oder ganz unmöglich, eine Funktion anzugeben, die allgemein zu jeder beliebigen Eingabe für ein Problem den zugehörigen Aufwand an Ressourcen angibt. Daher begnügt man sich in der Regel damit, statt jede Eingabe einzeln zu erfassen, sich lediglich mit der Eingabelänge n = | w | zu befassen. Es ist aber meist sogar zu schwierig, eine Funktion f_L: n \rightarrow f_L(n), n = |w| anzugeben. Daher beschränkt man sich häufig darauf, eine obere und untere Schranke für das asymptotische Verhalten anzugeben. Hierfür wurden die Landau-Symbole entwickelt.

Algorithmen und Probleme werden in der Komplexitätstheorie gemäß ihrer so bestimmten Komplexität in so genannte Komplexitätsklassen eingeteilt. Diese sind ein wichtiges Werkzeug, um bestimmen zu können, welche Probleme „gleich schwierig“, beziehungsweise welche Algorithmen „gleich mächtig“ sind. Dabei ist die Frage, ob zwei Komplexitätsklassen gleichwertig sind, oft nicht einfach zu entscheiden (zum Beispiel P-NP-Problem).

Die Komplexität eines Problems ist zum Beispiel entscheidend für die Kryptographie und insbesondere für die asymmetrische Verschlüsselung: So verlässt sich zum Beispiel das RSA-Verfahren auf die Vermutung, dass die Primfaktorzerlegung von großen Zahlen nur mit sehr viel Aufwand zu berechnen ist – anderenfalls ließe sich aus dem öffentlichen Schlüssel leicht der private Schlüssel errechnen.

Komplexität von Daten

In der Informationstheorie versteht man unter der Komplexität von Daten bzw. einer Nachricht ihren Informationsgehalt. Neben der klassischen Definition dieser Größe nach Claude Shannon gibt es verschiedene andere Ansätze, zu bestimmen, wie viel Information in einer Datenmenge enthalten ist:

Zum einen gibt es die so genannte Kolmogorow-Komplexität (auch Algorithmische Komplexität oder Beschreibungskomplexität), die den Informationsgehalt als die Größe des kleinsten Programms definiert, das in der Lage ist, die betrachteten Daten zu erzeugen. Sie beschreibt eine absolut optimale Komprimierung der Daten. Eine Präzisierung des Ansatzes Andrei Kolmogorows bezüglich des Maschinenmodells bietet die Algorithmische Informationstheorie von Gregory Chaitin.

Dagegen betrachtet Algorithmische Tiefe (auch Logische Tiefe) die Zeitkomplexität eines optimalen Algorithmus zur Erzeugung der Daten als Maß für den Informationsgehalt.

Komplexitätsmetriken

Es gibt eine Reihe von Softwaremetriken, welche die Komplexität von Daten und Algorithmen in der Informatik auf unterschiedliche Art und Weise messen. Diese sind:

  • Chapins-Data-Metrik – misst den Anteil der Bedingungs- und Ergebnisdaten von allen verwendeten Daten.
  • Elshofs-Data-Flow-Metrik – misst die Anzahl der Datenverwendungen relativ zur Anzahl der Daten. Sie ist verwandt mit hoher Kohesion. Hohe Kohesion entspricht einer hohen Verwendung von möglichst wenig Variablen.
  • Cards-Data-Access-Metrik – misst das Verhältnis der Anzahl Zugriffe auf externe Dateien und Datenbanken relativ zur Anzahl derselben.
  • Henrys-Interface-Metrik – misst die Anzahl der Zugriffe von fremden Funktionen/Methoden in ein Modul (englisch fan-in) beziehungsweise Anzahl der Aufrufe fremder Funktionen/Methoden aus einem Modul (englisch fan-out) relativ zu allen Funktionen/Methoden des Moduls.
  • McCabe-Metrik bzw. Eulers Maß bzw. Zyklomatische Komplexität – misst die Komplexität des Ablaufgraphen als Verhältnis Kanten zu Knoten.
  • McClures-Decision-Metrik – misst den Anteil Entscheidungen von allen Anweisungen.
  • Sneeds-Branching-Metrik – misst das Verhältnis der Anzahl Verzweigungen jeglicher Art zur Summe aller Anweisungen.
  • Halstead-Metrik – misst die Anzahl der verschiedenen Wörter (hier Anweisungstypen) relativ zur Anzahl verwendeter Wörter (hier Anweisungen). Sie behauptet, je weniger verschiedene Anweisungstypen man verwendet, desto einfacher ist der Code, was sehr umstritten ist.

Siehe auch


Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Komplexität — (v. lat.: complectere = umarmen, umfassen; Partizip Perfekt: complexum) bezeichnet allgemein die Eigenschaft eines Systems oder Modells, dass man sein Gesamtverhalten selbst dann nicht beschreiben kann, wenn man vollständige Informationen über… …   Deutsch Wikipedia

  • Informatik — ist die „Wissenschaft von der systematischen Verarbeitung von Informationen, besonders der automatischen Verarbeitung mit Hilfe von Digitalrechnern“ [1]. Historisch hat sich die Informatik einerseits aus der Mathematik entwickelt, andererseits… …   Deutsch Wikipedia

  • Komplexität — Kompliziertheit; Schwierigkeit; Varianz; Vielschichtigkeit * * * Kom|ple|xi|tät 〈f.; ; unz.〉 komplexe Beschaffenheit, vielfältige Gesamtheit * * * Kom|ple|xi|tät, die; (bildungsspr.): Vielschichtigkeit; das Ineinander vieler Merkmale: die K. der… …   Universal-Lexikon

  • Informatik — Informationstechnik; Computerwissenschaft * * * In|for|ma|tik [ɪnfɔr ma:tɪk], die; : Wissenschaft von der systematischen Verarbeitung von Informationen mithilfe von Computern: Informatik studieren. * * * In|for|ma|tik 〈f. 20; unz.〉 Wissenschaft… …   Universal-Lexikon

  • Informatik — I. Begriff:Wissenschaft von der systematischen Verarbeitung von Informationen, bes. der automatischen Verarbeitung mithilfe von Computern; im angelsächsischen Raum als Computer Science bezeichnet. Die I. untersucht grundsätzliche Verfahrensweisen …   Lexikon der Economics

  • Algorithmische Komplexität — Die Kolmogorow Komplexität (nach Andrei Nikolajewitsch Kolmogorow) ist ein Maß für die Strukturiertheit einer Zeichenkette und ist durch die Länge des kürzesten Programms gegeben, das diese Zeichenkette erzeugt. Dieses kürzeste Programm gibt… …   Deutsch Wikipedia

  • Kolmogoroff-Komplexität — Die Kolmogorow Komplexität (nach Andrei Nikolajewitsch Kolmogorow) ist ein Maß für die Strukturiertheit einer Zeichenkette und ist durch die Länge des kürzesten Programms gegeben, das diese Zeichenkette erzeugt. Dieses kürzeste Programm gibt… …   Deutsch Wikipedia

  • Kolmogorov-Komplexität — Die Kolmogorow Komplexität (nach Andrei Nikolajewitsch Kolmogorow) ist ein Maß für die Strukturiertheit einer Zeichenkette und ist durch die Länge des kürzesten Programms gegeben, das diese Zeichenkette erzeugt. Dieses kürzeste Programm gibt… …   Deutsch Wikipedia

  • Kolmogorow-Komplexität — Die Kolmogorow Komplexität (nach Andrei Nikolajewitsch Kolmogorow) ist ein Maß für die Strukturiertheit einer Zeichenkette und ist durch die Länge des kürzesten Programms gegeben, das diese Zeichenkette erzeugt. Dieses kürzeste Programm gibt… …   Deutsch Wikipedia

  • MPI Informatik — Max Planck Institut für Informatik Sitz in Saarbrücken Kategorie: Forschungseinrichtung Träger: Max Planck Gesellschaft Rechtsform des Trägers: Eingetragener Verein …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”