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
- Es gibt eine Vielzahl unterschiedlicher Computer. Gibt es trotzdem etwas Gemeinsames, was allen Computern zu Grunde liegt?
-> Algorithmentheorie, Theorie endlicher Automaten - Gibt es für jedes Problem, dass sich in der Informatik oder Mathematik beschreiben lässt, einen Algorithmus zur Lösung des Problems? Oder gibt es Probleme, die auch mit noch so leistungsstarker Rechentechnik auch in Zukunft, also prinzipiell, nicht berechenbar sind?
-> Theorie der Berechenbarkeit - Wie kann man Algorithmen hinsichtlich ihrer Laufzeit und des zur Lösung benötigten Rechenaufwandes vergleichen, obwohl sie auf unterschiedlichen Rechnern laufen?
-> Komplexitätstheorie - Wie sind künstliche für eine Maschine verständliche Sprachen strukturell aufgebaut?
-> Theorie der formalen Sprachen und ihrer Grammatik - Kann man Programme als mathematische Gebilde ansehen und ihre Korrektheit dementsprechend wie einen mathematischen Satz beweisen?
-> Verifikation
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
Eine Seite von Mirko Hans