Horizonterweiterung

[Severin]

Hallo,

Ich beschäftige mich seit gut einem Jahr mit PHP und seit ein paar Monaten auch  nebenbei ein wenig mit Python. Ich würde sagen, dass ich mich realtiv gut in  den Syntaxen (mmmh was ist die Mehrzahl von Syntax?) beider Sprachen auskenne und auch meistens in der Lage bin ein Problem zu lösen (auch wenns ab und zu recht lange dauern kann ;)).  Da ich also die Oberfläche meiner beiden Sprachen mehr oder weniger beherrsche, würde ich jetzt aber auch mal gerne einen "Blick unter die Haube" machen, und mich mit Informatik beschäftigen.

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 (ja echt wahr, in der Schule haben wir es noch nicht gelernt...) und b) Algorithmen als "Schwirig" gelten.

Sollte ein Grundwissen in einer Programiersprache als Voraussetzung reichen,  würde mich interressieren, welche Bücher zu diesem Thema empfehlenswert sind.
Im Archiv habe ich dazu folgenden -kurzen- Thread gefunden </archiv/2002/6/14657/#m81447>.
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.
Zum zweiten genannten Buch (Algorithmen und Datenstrukturen v. Thomas Ottmann u. Peter Widmayer) würde ich ebenfalls gerne wissen ob es für Anfänger geeignet ist, und wie viel Sprachwissen die Beispiele in dem Buch verlangen.
Ein weiterer Vorschlag, über den ich bei oberflächlichem googeln gestolpert bin ist "Introduction to Algorithms" v. Thomas H. Cormen, das auch gut sein soll, aber halt englisch[1].

So jetzt möchte ich gerne fragen, ob jemand Erfahrungen mit diesen Büchern hat und ob es für mich überhaupt Sinn macht mich mit Algorithmen zu beschäftigen und ich nicht was anderes zuerst lernen soll. Über alternative Buchvorschläge bin ich natürlich auch glücklich, diese waren die ersten die so "auf die schnelle" finden konnte.

[1] ich habe keine Probleme (auch längere) Englische Texte zu lesen, aber wenn es vergleichbare Texte in Deutsch gibt bevorzuge ich die, da Englisch halt doch eine Fremdsprche ist...

gruß,
Severin

[Z.N.S.]

abend,

leicht verständlich sind einfache suchalgorithmen.
schau dir einfach mal http://www.sortieralgorithmen.de/
dazu an... dort wird speziell darauf eingegangen..
definitionen findest du dort auch.

mfg,
Z.N.S.

[Michael Schröpl]

Hi Z.N.S.,

schau dir einfach mal http://www.sortieralgorithmen.de/

yep - vieles davon wird auch im "Wirth" behandelt.

Viele Grüße
      Michael

[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

[Severin]

Hallo,

... zur "Abschreckung" ein Google-Treffer:
http://www.ifi.unizh.ch/groups/req/courses/fgi/folien/Berechenbarkeit.4.pdf

hehe wie nett ;) Naja aber zumindest hat es mein Interesse an dem Thema noch weiter verstärkt. Ich denke ich folge einfach einmal Dimitris Rat und schaue was es in diversen Bibliotheken so gibt, und wenn ich etwas gefunden habe, dass mich   anspricht kann ich es immer noch kaufen. Mein größtes "Handycap" wird wohl mein Defizit in der Mathematik sein, aber ich denke (oder besser hoffe) dass ich mir den nötigen Stoff erarbeiten (nachlesen) kann, da ich ja prinzipiell in Mathematik gar nicht so schlecht bin. Und wenn mir das nicht gelingt kann ich immer noch den Lehrer fragen - das macht immer Eindruck.
Jedenfalls danke für die Tipps, sie haben mein Interesse an dieser "neuen Welt" geweckt und ich bin schon gespannt wie leicht/schwer mir es fallen wird.

gruß,
Severin

[Dimitri Rettig]

Hallo,

Da ich also die Oberfläche meiner beiden Sprachen mehr oder weniger beherrsche, würde ich jetzt aber auch mal gerne einen "Blick unter die Haube" machen, und mich mit Informatik beschäftigen.

Das ist die richtige Einstellung!

und b) Algorithmen als "Schwirig" gelten.

Wer sagt denn so etwas?

Sollte ein Grundwissen in einer Programiersprache als Voraussetzung reichen,  würde mich interressieren, welche Bücher zu diesem Thema empfehlenswert sind.

Ich kann dir kein bestimmtes Buch empfehlen. Ich würde dir folgendes raten: Gehe in eine Bücherei (am besten Universitätsbücherei) und schau dir einfach mal alle Bücher, die es über Algorithmen und Datenstrukturen gibt, durch. Du wirst auf Bücher mit verschiedenen Schwerpunkten und von unterschiedlichsten Niveaus stoßen. Suche dir ein einfaches Buch, das dir gefällt, aus. Mit diesem Buch kannst du eine Zeit lang beschäftigen. Du brauchst nicht das ganze Buch durchzuarbeiten. Wenn es irgendwann zu einfach wird (weil du schon algorithmisch denken kannst), dann hole dir ein anderes, anspruchsvolleres.
Diese Vorgehensweise finde ich besser als sich ein mittelschweres Buch zu kaufen, nicht nur weil sie kostengünstiger ist, sondern weil einfache Bücher zumeist zu einfach sind, und weil ansprchsvolle Bücher einen zu schweren Einstieg bieten. Wenn du dich allerding in die Materie eingearbeitet hast, dann wirst du feststellen, dass eine Zuordnungvorschrift, oder das Wissen, dass eine gewisse Struktur eine Abelsche Gruppe darstellt, einfach mehr über die Eigenschaften dieser aussagt als zwei Seiten in "Algorithmen und Datenstrukturen für Dummies".
Wie du sicherlich feststellen wirst, sind deine Mathematikkenntnisse ausschlaggebend dafür, auf welchem Niveau du letztenendes bewegen wirst. Leider gehört vieles, was dir alltäglich in der Algorithmik begegnet, nicht zum Umfang der Schulmathematik. Der Stoff ist aber keineswegs komplizierter, manchmal nur etwas abstrakter und unanschaulich. Wenn du die ersten fünf Bücher über Algorithmen durchgearbeitet hast, und merkst, dass du nicht mehr weiter kommst, dann ist es Zeit für eine Runde Algebra. Allein mit den De Morganschen Regeln kannst du dir einiges an komplizierten if-else Anweisungen, die wohl in jeder Programmiersprache vorkommen, ersparen. Das Wichtigste ist, sich nicht vor mathematischen Symbolen abschrecken zu lassen.

Ich wünsche dir viel Erfolg, und vor allem Spaß am algorithmischen Lösen von mathematischen Problemen.

Mit freundlichen Grüßen
   Dimitri Rettig

[Tim Tepaße]

Hallo Dimitri,

"Algorithmen und Datenstrukturen für Dummies".

Glaub mir, im Studium haben wir schon nach solchen Büchern gesucht. So
etwas gibt es nicht. ;-)

• Tim

[Antje]

Hach wieder so ein, kann etwas Scripten Blondchen das jetz nach grösseren Sachen sucht als nur zu Scrippten.

Lern erst mal Kochen.

[JvM]

Hallo liebe Antje,

kann das sein das alle Posts die ich von dir entdeckt habe keinen Sinn haben, sondern lediglich darauf abzielen korrekt und freundlich gestellte Fragen möglichst blöd mit einem dummen Kommentar zu beantworten?

Gruß,
JvM

[Harry]

Holladiewaldfee,

kann das sein das alle Posts die ich von dir entdeckt habe keinen Sinn haben, sondern lediglich darauf abzielen korrekt und freundlich gestellte Fragen möglichst blöd mit einem dummen Kommentar zu beantworten?

Ja, wie gut, daß es sowas wie eine Ignore-Liste gibt.
[pref:t=53941&m=299382]

Ich bin der Meinung, daß sie (wer immer "sie" auch sein mögen) irgendwo irgendein Zeug ins Grundwasser gekippt haben, daß heute die Leute irgendwie komisch werden lässt ;) So 'ne Art Vertrollungspulver oder so.

Ciao,

Harry

[Severin]

Hallo Antje,

Ich bitte freundlichst um eine Erläuterung deines Postings und aus welches Indizien oder Buchstabenfolgen du in der Lage bist den Schluss zu ziehen, ich sei nicht mit der Fähigkeit ausgestattet, Bedienungsanleitungen in Form von Kochbüchern zu befolgen.
Doch um deine etwaige Sorge um mein leibliches Wohl zu mindern, sei dir gesagt, dass ich a) Einen Mikrowellenherd bedienen kann und b) Die Nummer der lokalen Pizza-Services auswendig kann :)

gruß,
Severin