spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Ganz ehrlich, es ist recht simpel:
Code lesen. Ganz viel Code lesen. Habe keine Sorge, dass du als Azubi vielleicht noch nicht alles sofort verstehst (insbesondere wenn Andere meinen, das sei einfach). Ich verstehe heute noch, nach einigen Jahren als Entwickler in der Industrie, nicht sofort jeden Algorithmus oder Code. Das muss man auch gar nicht immer. Man entwickelt über die Jahre ein Gespür und wenn du hartnäckig bleibst wirst du das auch irgendwann. Mein Tipp an dich: Hör einfach nie auf zu lernen, gib dich nie zufrieden mit deinem Wissensstand, sei hungrig auf mehr, hab Spaß neue Dinge zu lernen und sei offen für neue Technologien. Gerade letzteres macht meiner Meinung nach einen guten Programmierer aus, denn unsere Branche hört nie auf sich zu entwickeln und das solltest du auch nicht. Wie man so schön sagt: "Spezialisierung ist etwas für Insekten!"

PS: wirklich wichtige Bücher sind folgende:
Clean Code von Robert C. Martin
Design Patterns von der Gang of Four

...und alles was Bob Nystrom schreibt

Viel lesen und lernen hilft schon mal, das stimmt. Und der Rest ist einfach Praxis. Je mehr du entwickelst und dabei halt Probleme löst desto besser wirst du darin mit der Zeit. Rekursion ist eigentlich keine schwere Sache. Es ist aber überhaupt nicht ungewöhnlich wenn dir das am Anfang Kopfschmerzen bereitet. Es ist eben erst mal ungewöhnlich weil man mit so etwas vorher oft nicht in Kontakt kommt. Versuch keine Angst vor Rekursion zu haben sondern lass dich einfach darauf ein. Türme von Hanoi ist kein riesig schweres Problem, es gibt aber auch viel viel einfachere Probleme um sich in das Thema einzuarbeiten. Hier mal ein paar Beispiele von mir:
Fakultät berechnen,
Fibonaccireihe berechnen
Durchlaufen einer Liste,
Durchlaufen eines Baumes in inorder, präorder oder postorder ( Ein Binärbaum zb ist schnell geschrieben )
Paints Füllwerkzeug, wobei du an sich einfach ein 2D Array vom Typ Bool nehmen kannst, wobei du eben eine Fläche mit Werten füllen möchtest.
Alternativ und da wir hier in einem Spieleprogrammierer Forum sind, kannst du ja Minesweeper programmieren. Dort müssen teilweise viele Flächen gleichzeitig aufgedeckt werden was dem selben Problem entspricht. Wenn du es geschafft hast kannst du deinen Algorithmus ja mal mit Flood Fill vergleichen.
Ansonsten kannst du auch einfach mal im Internet nach rekursiven Algorithmen suchen und versuchen welche davon umzusetzen. Mergesort und Quicksort sind da Beispiele.

Es wird nicht von dir erwartet, dass du diese Probleme sofort verstehst. Andere Leute studieren oder arbeiten viele Jahre lang, um das zu können.

Du musst nicht einmal Rekursion verwenden, sondern kannnst alle Probleme iterativ lösen, ggf. mit einer Queue statt rekursiven Aufrufen. Es ist bei Fakultät und vor allem Fibonacci-Zahlen auch sinnvoller, das iterativ zu lösen. Bei letzterem brauchst du iterativ nur lineare Zeit in n (O(n)), wenn du die n-te Fibonacci-Zahl suchst, während du rekursiv exponentielle Zeit (O(2^n)) brauchst. Es ist also oft nicht nur wichtig, dass du ein Problem löst, sondern auch wie.

Eine effiziente Lösung ist aber auch bei einfachen Problemen nicht unbedingt trivial, z.B. bei Travelling Salesperson, wo der kürzeste Weg durch n Städte und zurück zum Start gesucht wird. Obwohl das Problem NP-schwer ist, wurde hier zum Beispiel eine optimale Lösung mit 85.900 Städten gefunden [Quelle]. Die Laufzeit wäre hier im schlimmsten Falle bzw. mit einem unoptimierten Algorithmus so lang gewesen, dass alle Sterne im Universum erloschen wären, bevor die Lösung gefunden worden wäre. Allerdings wurde dieser Algorithmus auch jahrelang oder gar jahrzehntelang optimiert.

Türme von Hanoi kann man allerdings nicht schneller lösen. Da ist es auch nicht wichtig, jeden Schritt nachzuvollziehen, sondern zu verstehen, dass du das Problem für n Scheiben löst, indem du n-1 Scheiben vom Stapel 1 nach 2 verschiebst, dann die unterste auf Stapel 3 und dann die n-1 Scheiben von 2 auf 3. Die n-1 Scheiben kannst du wiederum auf die selbe Art verschieben, indem du die n-2 Scheiben auf einen anderen Stapel packst, die unterste auf den Zielstapel verschiebst und die n-2 Schreiben dann auf den Zielstapel verschiebst. Wenn du dann irgendwann nur noch eine Scheibe bewegen musst, kannst du das Problem trivial lösen.

Allerdings lernst du das Lösen von schwierigeren Problemen eher im Informatik-Studium. Wenn dich das interessiert und du besser werden willst, empfehle ich, ein Algorithmen-Buch zu lesen. Die guten sind leider meist auf Englisch und recht teuer.

Hallo,

ich kann leider kein bestimmtes Buch empfehlen, da ich die Dinge alle in Vorlesungen im Studium gelernt habe und dafür quasi nie ein Buch gebraucht habe. Ein Mathematik-Buch zu lesen ist nicht unbedingt nötig, sinnvoll wäre vielleicht ein Buch zu Graphtheorie, das aber eher die für die Informatik relevanten Aspekte behandelt. Für den Anfang reicht wohl ein Buch über Algorithmen und Datenstrukturen, da sollten die wichtigsten mathematischen Grundlagen auch erklärt sein. Für fortgeschrittene Anwendungen empfiehlt sich auch ein Buch über Berechenbarkeit und Komplexität, damit du Laufzeit eines Algorithmus abschätzen kannst.

Wenn du etwas über Grafikprogrammierung lernen möchtest, brauchst du lineare Algebra, vor allem Vektoren und Matrizen. Da sollten aber Tutorials im Internet ausreichen.

Wenn du dich im Allgemeinen für die Theorie interessierst, solltest du vielleicht über ein Informatik-Studium nachdenken. Da lernt man auch, etwas abstrakter zu denken und so auch schwierigere Probleme wie zum Beispiel Maximum Flow (Wie viel kann man maximal von A nach B transportieren pro Zeiteinheit, z.B. Wasser von der Quelle zu allen Haushalten in einer Stadt?) zu modellieren und zu lösen. Abgesehen davon gibt es auch noch eher praxisorientierte Bereiche wie z.B. Netzwerksicherheit oder Hardwareentwicklung.

Zitat von »Magogan«

Für fortgeschrittene Anwendungen empfiehlt sich auch ein Buch über Berechenbarkeit und Komplexität, damit du Laufzeit eines Algorithmus abschätzen kannst.

In vielen Büchern über Algorithmen sind Kapitel zur Laufzeitanalyse enthalten.
Bei uns haben sie damals meine ich dieses Buch empfohlen.

Es lohnt sich aber auch, Probleme etwas genauer einschätzen zu können. So dürfte in den Büchern zu Algorithmen sowas wie Parameterized Complexity nicht vorkommen, obwohl es durchaus relevant ist, denn damit können viele Laufzeiten besser abgeschätzt werden, z.B. durch den Maximalgrad in einem Graphen, der zum Beispiel bei sozialen Netzwerken relativ klein ist (ca. 100 bis 1.000) im Vergleich zur Ordnung des Graphen (n = 1.000.000.000 Knoten). So lässt sich z.B. eine Clique (kompletter Teilgraph; hier Gruppe, in der jeder jeden kennt) mit k Knoten in O(n^O(1)*2^x) Zeit (Komplexitätsklasse FPT) für x := Maximalgrad finden - sofern eine existiert -, also polynomielle Zeit für feste x, was viel besser ist als O(n^k) Zeit (Komplexitätsklasse XP) für große k.

Eine Funktion f(n) ist in O(g(n)), wenn es ein n0 und ein c gibt, sodass f(n) <= c*g(n) für alle n >= n0, also f(n) wächst höchstens so schnell wie g(n) abgesehen von konstanten Faktoren.