Horizonterweiterung

[Michael Schröpl]

Hi Severin,

Ich würde mich eigendlich für Algorithmen interessieren, weiß aber nicht, ob ich nicht vielleicht einen Zwischenschritt machen sollte, da ich a) keine Ahnung habe was ein Algorithmus eigendlich ist

eine Arbeitsvorschrift, üblicherweise in Form einzelner Schritte. Bestimmte Elementar-Operationen wie Tests und Verzweigungen erlauben, signifikant komplexere als rein lineare Vorgänge zu beschreiben. (Alles, was darüber hinaus geht, ist IMHO schon implementierungsspezifisch ...)

Ein bißchen über grundlegende Recherarchitekturen solltest Du auch gleich am Anfang lernen.
Mit Deinem jetzigen Stand dürfte es aber nicht schwer sein, zu verstehen, was eine "von-Neumann-Maschine" ist und welche Konsequenzen deren Verwendung in den real existierenden Rechnern hat.

b) Algorithmen als "Schwierig" gelten.

"Komplexitätstheorie" lautet hier Dein Thema. (Informatik-Studium, ca. 3.-4. Semester)

Die Schwierigkeit eines Problems (bzw. eines zu dessen Lösung eingesetzten Algorithmus - beides ist von Interesse) wird üblicherweise dadurch gemessen, daß bestimmte Ressourcen (meistens die Anzahl der Rechenschritte, manchmal auch der Speicherbedarf etc.) in Abhängigkeit vom "Volumen" der Eingabewerte beschrieben werden, üblicherweise durch mathematische Funktionen (häufig Polynome).

Ein Algorithmus, der <n> Zahlen dadurch sortiert, daß er jede mit jeder anderen vergleicht, hat eine Komplexität O(n^2) (lies: "in der Ordnung von", wobei Vorfaktoren wie hier "1/2" üblicherweise abgespalten werden, weil sie bei großen Werten für <n> keine Rolle mehr spielen).
Ein Algorithmus, der Sortieren durch Einfügen in einen (binären) Baum realisiert, kommt mit sehr viel weniger Vergleichen aus, etwa mit O (n * log2(n)) - Du siehst, konkrete Programmiersprachen verwende ich bei solchen Überlegungen gar nicht.

"Schwierig" sind Algorithmen üblicherweise dann, wenn ein Polynom zur Beschreibung von deren Komplexität nicht mehr ausreicht, sondern ein Ausdruck erforderlich ist, in welchem die Eingabegröße selbst als Exponent auftritt oder ähnliches - das sind dann Fälle, wo der Aufwand schon bei einer Erhöhung der Eingabemenge um 1 auf ein Vielfaches steigen kann!
Das Knapsack-Problem ist das klassische Literatur-Beispiel, das in allgemeiner Form einen Aufwand erfordert, der O(n!) für <n> Teile beträgt ... aua.
Auch "NP-vollständig" ist ein Begriff, der Dir dabei öfters über den Weg laufen wird - und der am Anfang für Verwirrung sorgt, weil man sich nur schwer vorstellen kann, wie eine Komplexitätsabschätzung Sinn machen kann, die darauf beruht, daß man pausenlos richtig rät ... (Oder gar seine Steigerung: http://www.jargon.net/jargonfile/a/AI-complete.html ;-)

Sollte ein Grundwissen in einer Programmiersprache als Voraussetzung reichen,

Das ist gar nicht notwenig. Elementare Mathematik-Kenntnisse reichen aus; Programmierkenntnisse nützen insofern, als daß Du Dir die konkrete Umsetzung der Algorithmen besser vorstellen kannst.
Aber Komplexitätstheorie basiert auf Algorithmen, nicht auf deren Umsetzung in Programme.

Zum ersten genannten Buch (Algorithmen und Datenstrukturen v. Niklaus Wirth) würde ich gerne wissen, wie "schwer" ist es Pascal Code zu lesen (und zu verstehen), wenn man keine Ahnung von Pascal hat und ob es für Anfänger im Bereich theoretischer Informatik geeignet ist.

PASCAL ist auf Lesbarkeit optimiert. Überall, wo Du in anderen Sprachen kryptische Operatoren oder Klammern findest, verwendet PASCAL englische Worte wie "begin", "end", "and", "or", "not", "if", "then" oder "else".
Du wirst keine Schwierigkeiten haben, PASCAL zu lesen (schreiben ist natürlich schwieriger).

Der "Wirth" war unser Informatik-Lehrbuch im 3. Semester (1981), wobei er Komplexitätstheorie nicht wirklich vertieft, sondern sich eher auf praktische Algorithmen und deren Einsatzzwecke konzentriert. Vorher hatten wir ein Semester über Algorithmen (und PASCAL ohne Pointer) und ein Semester über Rechner-Architekturen (und Assembler), wobei letzteres keine direkte Voraussetzung für das 3. Semester war.
Man lernt von Wirth vor allem, was man tun sollte und was nicht (und auch, warum), eher als etwa die theoretischen Grundlagen, wie schwer Probleme allgemein sind (oder sein können). Sein Thema ist letzten Endes "Suchen und Sortieren" - und davon gibt es enorm viele interessante Varianten.

Informatik läßt sich neben der praktischen Anwendbarkeit auch wunderbar als "reine Wissenschaft" betreiben ... etwa, wenn es um Entscheidbarkeit geht (um den Beweis, daß bestimmte Probleme algorithmisch überhaupt nicht lösbar sind etc.), was in der Realität allerdings kaum von praktischem Nutzen sein wird ... zur "Abschreckung" ein Google-Treffer:
http://www.ifi.unizh.ch/groups/req/courses/fgi/folien/Berechenbarkeit.4.pdf

Viele Grüße
      Michael