Analyse von Algorithmen (Komplexität und Berechenbarkeit)


Bei der Beschäftigung mit Sortierverfahren haben wir festgestellt, dass es eine Vielzahl von verschiedenen Sortieralgorithmen gibt. Im praktischen Fall muss sich der Programmierer für einen Sortieralgorithmus entscheiden. Aber für welchen? Wir haben schon einmal kurz einige Gütekriterien für Sortierverfahren wie Schnelligkeit des Sortierens und Verhalten bei Sonderfällen angesprochen. Es stellt sich jedoch die Frage, wie man die Güte bzw. die Effizienz eines Algorithmus beurteilt. Und dies ganz allgemein und nicht nur für Sortieralgorithmen. Wie also kann man die Arbeitsweise und das Verhalten von Algorithmen analysieren? Dies ist eine Frage, der sich die theoretische Informatik widmet.

Hier zur Erinnerung noch einmal der Überblick über die verschiedenen Teilgebiete der Informatik: TeilgebieteInformatik.pdf.

Bevor wir uns weiter mit der Analyse von Algorithmen befassen bietet sich an dieser Stelle ein kleiner Exkurs an. Womit beschäftigt sich die theoretische Informatik überhaupt?

Der Gegenstand der theoretischen Informatik

Allgemein ist die theoretische Informatik die mathematische Basis der Informatik und der Mathematik sehr nah verwandt. Für unsere Problematik der Algorithmenanalyse sind die Punkte zwei (Berechenbarkeit) und drei (Komplexität) der obigen Aufstellung von Interesse.

Analyse von Algorithmen - Komplexität und Berechenbarkeit

Script zur Problematik Komplexität und Berechenbarkeit: Komplexitaet_Berechenbarkeit.pdf


zuletzt geändert am:
Eine Seite von Mirko Hans