Informatik ist die Wissenschaft, Probleme mit Hilfe von Maschinen effizient zu lösen. Dabei bedient sie sich eines strengen mathematischen Formalismus, um Probleme und deren Lösung zu beschreiben und zu klassifizieren. Zugrunde gelegt werden theoretische Rechenmodelle, die einen realen Computer in allen Belangen übertreffen. Zwei grundlegende Fragen beschäftigen den Informatiker:
ad 1)
Interessanterweise gibt es (unendlich) viele Probleme, die sich beweisbar mit den heutigen Rechenmodellen nicht lösen lassen,
d.h. es kann kein Programm dafür geschrieben werden. Ein berühmtes Beispiel ist das sogenannte Halteproblem:
In der Praxis bedeutet das, daß ein gegebenes Programm nicht mittels einer Maschine auf Korrektheit geprüft werden kann.
ad 2)
Lösbare Probleme werden, wenn möglich, Klassen zugeteilt. Diese Klassen repräsentieren die Eigenschaften Laufzeitverhalten und Speicherplatzbedarf.
Ein kleines Beispiel: Sortieren sie die folgende Zahlenfolge aufsteigend.
100, 45, 33, 80, 75, 11, 46, 99
Instinktiv werden Sie wahrscheinlich so vorgehen:
Er würde sich weiterhin fragen, ob es nicht ein besseres, effizienteres Verfahren exististiert, das Ihre Zahlenfolge sortiert. In der Tat existieren mehrere effizientere Verfahren für dieses Problem, die proportional nur n*log(n) Schritte durchführen.
^ topSchon bei einer Eingabegröße von 1000 Zahlen sind hier enorme Lauftzeitunterschiede zu vermerken:
Bei n =1000 ist n²=1000000 und n*log(n) cr. 10000, das entspricht 1% von 1000000 ! Das n*log(n) Verfahren spart hier also schon 99% Laufzeit bei n=1000. Ob Sie nun 100 Stunden oder nur eine Stunde auf die Lösung eines Problems warten sollen, zahlt sich für Sie aus.
Noch praktischer und dramatischer ausgedrückt:
Bei n=10000 Zahlen würde ein betagter Computer, der 15 Jahre
alt ist, mit dem n*log(n) Verfahren einen brandneuen Computer mit dem quadratischen Verfahren um Längen schlagen.
Sie denken, diese Problematiken treten in der Praxis nicht auf? Leider allzu häufig. Ein gutes Beispiel ist mangelhaftes Datenbankdesign, das sehr schnell zu den obig geschilderten Phänomenen führen kann.
^ topEin wichtiges Feld für die Klassifizerung von Verfahren ist die Kombinatorik, die die Zusammenhänge der Eingabeanzahl und der Größe der Lösungen beschreibt.
Sie glauben, das ist ein akademisches, weit hergeholtes Beispiel? Leider nicht, denn viele Probleme im täglichen Leben haben oft eine enorme Anzahl von Lösungen, von der nur ein paar oder sogar nur eine einzige interessant ist.
Soweit zur akademischen Natur dieses Problems. Ein guter Informatiker kann Ihnen hier in den meisten Fällen trotzdem weiterhelfen, indem er die Natur des Problems erkannt hat und gar nicht erst nach der besten Lösung sucht, sondern nach einer Lösung, die vielleicht maximal 10% von der besten Lösung abweicht.
^ topViele Probleme in der Praxis erscheinen einfach, sind in Wahrheit aber komplex. Andererseits existieren Probleme, die komplex erscheinen, aber eine einfache Lösung haben. Ein letztes Beispiel: Den kürzesten Weg zwischen zwei Löchern auf der Platine zu berechnen, ist sehr effizient lösbar. Die Bedingung, das alle Löcher in dem Weg enthalten sein müssen, macht die Lösung nahezu unmöglich.
Lassen Sie sich deshalb von uns beraten !