imported>Redonebird: Abschnittlink korrigiert

2023-11-22T05:14:41Z

Abschnittlink korrigiert

Neue Seite

Der Begriff '''Komplexität''' wird in der [[Informatik]] in verschiedenen Teilbereichen verwendet. Die [[Komplexitätstheorie]] befasst sich dabei mit dem Ressourcenverbrauch von [[Algorithmus|Algorithmen]], die [[Informationstheorie]] dagegen verwendet den Begriff für den [[Informationsgehalt]] von [[Daten]], die [[Praktische Informatik]] wiederum bewertet damit Software oder Softwareteile hinsichtlich der Anzahl von Interaktionen.

== Komplexitätstheorie ==
{{Hauptartikel|Komplexitätstheorie}}
Unter der Komplexität (auch ''Aufwand'' oder ''Kosten'') eines Algorithmus versteht man in der [[Komplexitätstheorie]] seinen Ressourcenbedarf. Dieser wird oft in Abhängigkeit von der Länge <math>n</math> der Eingabe angegeben und für große <math>n</math> [[asymptotisch]] unter Verwendung von [[Landau-Symbole]]n abgeschätzt. Analog wird die Komplexität eines [[Problem#Wissenschaften|Problems]] definiert durch den Ressourcenverbrauch eines optimalen [[Algorithmus]] zur Lösung dieses Problems. Die Schwierigkeit liegt darin, dass man alle Algorithmen für ein Problem betrachten muss, um die Komplexität desselben zu bestimmen.

Die betrachteten [[Betriebsmittel (Informatik)|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 [[Computerprogramm|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 schwierig, 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, [[Konstante Funktion|konstante]] [[Faktor (Mathematik)|Faktoren]] und [[Summand]]en auszulassen und sich lediglich mit dem Verhalten in Abhängigkeit der ''Eingabelänge'' <math>n = |w|</math> zu befassen. Die Eingabelänge wird hierbei in der Anzahl an [[Bit]]s gemessen, die benötigt werden, um die Information darzustellen.

Eine weitere Vereinfachung ist die Annahme, dass alle elementaren Operationen dieselbe Zeit benötigen, sodass z. B. die [[Addition]] zweier Zahlen und die [[Multiplikation]] zweier Zahlen genau eine Zeiteinheit kostet.

Algorithmen und Probleme werden in der Komplexitätstheorie gemäß ihrer so bestimmten Komplexität in so genannte [[Komplexitätsklasse]]n 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-Kryptosystem|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 [[Öffentlicher Schlüssel|öffentlichen Schlüssel]] leicht der [[Privater Schlüssel|private Schlüssel]] errechnen.

Ein Problem, das selbst für einen Computer von der Größe der Erde nicht lösbar ist, wird als [[transcomputationales Problem]] bezeichnet.

== 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 [[Datenkompression|Komprimierung]] der Daten. Eine Präzisierung des Ansatzes [[Andrei Nikolajewitsch Kolmogorow|Andrei Kolmogorows]] bezüglich des [[Maschinenmodell]]s 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.

== Softwarekomplexität ==
Programm- oder Softwarekomplexität umfasst viele Eigenschaften einer Software, die einen Einfluss auf interne Interaktionen haben. Meist wird zwischen den Begriffen ''Komplex'' und ''Kompliziert'' unterschieden. Kompliziert bedeutet in diesem Zusammenhang ''für Programmierer schwer zu verstehen'', also eine interne Eigenschaft des Codes, der Algorithmen, des technischen Designs oder der Architektur der Software. Komplexität wiederum beschreibt die Eigenschaften der Interaktionen zwischen Teilen der Software. Mit der Anzahl der Abhängigkeiten zwischen Teilen der Software steigt die Anzahl der Interaktionen und somit die Komplexität der Software. Das Verständnis der Abhängigkeiten und Interaktionen hat einen großen Einfluss auf das gesamte Verständnis der Software, darum wird Software, wenn sie komplexer wird, auch schwerer zu verstehen, also komplizierter. Die Komplexität einer Software kann einen Grad erreichen, wo es für Menschen unmöglich ist, die Software vollumfänglich zu verstehen.

Ähnlich dazu erhöht eine hohe Komplexität das Risiko, dass Änderungen an einer Stelle ungewollte Auswirkungen an einer anderen Stelle bewirken. Das führt zu einer höheren Wahrscheinlichkeit, Fehler in die Software einzubauen, und zu größeren Aufwänden, die Ursache dieser Fehler zu finden bzw. diese zu beheben. Im schlechtesten Fall kann die Komplexität dazu führen, dass die Software de facto unwartbar wird, da die Risiken von Änderungen deren Nutzen übersteigen. Die Abhängigkeit zwischen Komplexität und [[Softwarewartung#Wartungsaufwand|Wartungsaufwand]] wurden durch [[Meir Manny Lehman]] untersucht und in seinen Gesetzen der Softwareevolution 1980 zusammengefasst.<ref>{{Literatur |Autor=M.M. Lehman |Titel=Programs, Life Cycles, and Laws of Software Evolution |Sammelwerk=Proceedings of the IEEE 68 |Datum=1980 |Seiten=1060-1076 |Sprache=en}}</ref>

Meir Manny Lehman und [[Laszlo Belady]] untersuchten auch eine Reihe von [[Softwaremetrik]]en zur Messung des Zustandes einer Software.<ref>{{Literatur |Autor=Meir Manny Lehman, Les A. Belady |Titel=Program Evolution |TitelErg=Processes of Software Change |Hrsg=Academic Press Inc |Datum=1985-12-01 |Sprache=en |Umfang=538 |ISBN=978-0124424418}}</ref> Die folgenden Softwaremetriken messen die Komplexität von Daten und Algorithmen in der Informatik auf unterschiedliche Art und Weise:
; Chapins Data-Metrik: Misst den Anteil der Bedingungs- und Ergebnisdaten an allen verwendeten Daten.
; Elshofs Data-Flow-Metrik: Misst die Anzahl der Datenverwendungen relativ zur Anzahl der Daten. Sie ist verwandt mit hoher [[Kohäsion (Informatik)|Kohäsion]]. Hohe Kohäsion entspricht einer häufigen Verwendung von möglichst wenig Variablen.
; Cards Data-Access-Metrik: Misst das Verhältnis der Anzahl der 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.<ref>{{Literatur |Autor=S. Henry, D. Kafura |Titel=Software Structure Metrics Based on Information Flow |Hrsg=IEEE |Sammelwerk=IEEE Transactions on Software Engineering |Band=SE-7 |Nummer=5 |Datum=1981-09 |Sprache=en |Seiten=510 - 518 |ISSN=1939-3520 |DOI=10.1109/TSE.1981.231113 |Zitat="the procedure length multiplied by the square of fan-in multiplied by fan-out"}}</ref>
; [[McCabe-Metrik]] bzw. Eulers Maß bzw. Zyklomatische Komplexität: Misst die Komplexität des Ablaufgraphen als Verhältnis der Kantenanzahl zur Knotenanzahl.
; McClures Decision-Metrik: Misst den Anteil der Entscheidungen an allen Anweisungen.
; [[Harry Sneed|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.
; NPATH: Zählt die azyklischen Pfade durch Funktionen<ref>{{Literatur |Autor=Brian A. Nejmeh |Titel=NPATH: a measure of execution path complexity and its applications |Sammelwerk=Communications of the ACM |Band=31 |Nummer=2 |Datum=1988-02 |Seiten= |DOI=10.1145/42372.42379}}</ref>
; Cognitive Complexity: Wird von [[SonarQube]] zur Messung der Komplexität von Programmen und Programmteilen gegenüber anderen Komplexitätsmetriken empfohlen.<ref>{{Literatur |Autor=G. Ann Campbell |Titel=Cognitive Complexity |TitelErg=A new way of measuring understandability |Hrsg=SonarSource |Datum=2016 |Sprache=en |Umfang=20 |Online=https://www.sonarsource.com/docs/CognitiveComplexity.pdf |Format=PDF |KBytes=214 |Abruf=2020-03-10}}</ref>

Sechs Komplexitätsmetriken für [[Objektorientierte Analyse und Design|objektorientiertes Design]] wurden von S.R. Chidamber und C.F. Kemerer 1994 vorgestellt:<ref>{{Literatur |Autor=S.R. Chidamber, C.F. Kemerer |Titel=A Metrics Suite for Object-Oriented Design |Hrsg=IEEE |Sammelwerk=IEEE Transactions on Software Engineering |Band=20 |Nummer=6 |Datum=1994-06 |Sprache=en |Seiten=476 - 493 |ISSN=1939-3520 |DOI=10.1109/32.295895}}</ref> Gewichtete Methoden pro Klasse, Kopplung zwischen Objektklassen, Antworten pro Klasse, Anzahl an Subklassen, Tiefe des Vererbungsbaumes und ungenügende [[Kohäsion (Informatik)|Kohäsion]] von Methoden.

== Siehe auch ==
* [[Effizienz (Informatik)|Effizienz]]

== Einzelnachweise ==
<references />

{{SORTIERUNG:Komplexitat #Informatik}}
[[Kategorie:Komplexitätstheorie]]

Komplexität (Informatik) - Versionsgeschichte

imported>Redonebird: Abschnittlink korrigiert