Algorithmen

Algorithmische Probleme treten in allen Bereichen der Informatik auf. Exemplarisch sollen die folgenden Fragestellungen genannt werden: Verteilung beschränkter Ressourcen auf verschiedene Anforderungen, z.B. Stundenplanprobleme, Entwurf von Datenbanksystemen, Verifikation von Hardware und Software, Layout beim Entwurf digitaler Systeme, Computer-Aided Design, Flussmaximierung in Netzwerken, Berechnung kürzester Wege auch unter Nebenbedingungen wie im Traveling Salesman Problem, Klassifikationsprobleme, z.B. in der Mustererkennung, Verwaltung großer Datenbestände, z.B. von Geodaten, Datenschutz, kryptographische Systeme, Entwurf von Schachprogrammen, künstliche Intelligenz. Hierunter sind Entscheidungsprobleme wie die Hardwareverifikation (stimmt das Eingabe-Ausgabe-Verhalten von Spezifikation und Realisierung überein?) und Optimierungsprobleme (finde ein Layout, das z.B. bezüglich des Platzbedarfs optimal ist). Probleme wie die Hardwareverifikation und das Layoutproblem sind rekursiv, d.h. mit Rechnerhilfe lösbar, sie gehören aber auch zu den NP- harten Problemen[3.5], [3.14], [3.16]. Dies impliziert, dass es vermutlich keinen Algorithmus gibt, der für alle Eingaben effizient arbeitet. Unter den praktisch wichtigen Problemen haben viele diese Eigenschaft und nur wenige Probleme, unter ihnen die Flussmaximierung in Netzwerken, lassen sich mittels polynomieller Algorithmen lösen.