Was bringen mir Algorithmen und Datenstrukturen?

Bis jetzt habe ich mich immer nur mit einer Programmiersprache an sich beschäftigt, also ein wenig C und jetzt seit zwei Monaten C++ und davor auch Java. Jetzt bin ich auf das Thema Algorithmen und Datenstrukturen gestoßen, also so Listen, Bäume und so was. Lohnt es sich sich damit zu beschäftigen? Was würde ich damit anfangen können, oder was würde ich damit besser machen können als ohne dieses Wissen?

SeppJ

Du lernst dadurch viele Standardlösungen für häufig vorkommende Probleme kennen und auch die Strategien, wie man zu diesen Lösungen kommt, die du dann auch auf andere Probleme anwenden kannst. Außerdem lernst du, wie man die Qualität unterschiedlicher Lösungen beurteilen und vergleichen kann, was es dir erlaubt, die jeweils beste Lösung zu wählen, wenn mehrere zur Wahl stehen. Oder im schlimmsten Fall lernst du wenigstens, was hinter den vorgefertigten Lösungen in den Standardbibliotheken der Sprachen steckt, so dass du deren Leistungsfähigkeit einschätzen kannst. Alles sehr nützlich.

PS: Nicht zum Thema, aber zu deinem ersten Satz: Am Anfang ist es wahrscheinlich besser, wenn du nicht zu viele Sprachen auf einmal lernst.

Bashar

Wenn es dich nicht interessiert, lass es halt bleiben. Man kann sich auch 10 Jahre als Webentwickler durchschlagen, ohne von Algorithmen die leiseste Ahnung zu haben. [quelle: dieser Thread]

berniebutt

Es lohnt sich immer, sich mit etwas zu beschäftigen, was man noch nicht kennt.
Algorithmen sind Lösungswege für eine konkrete Aufgabe. Wie im täglichen Leben gibt es oft
mehrere solcher Lösungswege.

Beispiel Kartoffelnknödeln:
a. Kartoffeln schälen, in Stücke schneiden, zu Brei stampfen, Knödel formen
b. Kartoffelpulver kaufen, nach Vorschrift zu Knödeln machen
c. fertig geformte Kartoffelnknödeln verwenden

In der Programmierung ist das so ähnlich. Auch hier hat man oft verschiedene Möglichkeiten zur Wahl.
Selber machen oder auf (unterschiedliche) fertige Lösungen zugreifen.

Vorschlag: Stelle dir Aufgaben und versuche diese auf möglichst verschiedene Weise zu lösen. Viel mehr
lässt sich als Hilfestellung nicht sagen.

berniebutt schrieb:

a. Kartoffeln schälen, in Stücke schneiden, zu Brei stampfen, Knödel formen

Die Kartoffeln dazu werden gerieben, nicht geschnitten+gestampft. Und mit Kartoffelpulver schmeckt das gar nicht, da kann man sie auch bleiben lassen.

Mechanics

Logn schrieb:

also so Listen, Bäume und so was.

Es kommt auch drauf an, ob sich hinter "so was" tatsächlich noch mehr versteckt. Listen und Bäume sind ziemlich grundlegende Datenstrukturen, du kannst nicht sinnvoll programmieren, ohne sie zu verstehen. Gut, bei Bäumen schaut es vielleicht schon etwas anders aus, es gibt viele Arten von Bäumen und man sie nicht alle im Detail und auswendig kennen. Ganz grundlegende baumartige Strukturen hat man beim Programmieren aber ständig, schadet nicht, sich mal anzuschauen, was andere schon über das Thema rausgefunden haben.
Bei weitergehenden Algorithmen kann es aber schon wieder anders ausschauen. Wenn du erst anfängst zu programmieren, wirst du wahrscheinlich in der Tat nicht viel brauchen. Ich habe mit 14 angefangen zu programmieren und bin jahrelang wunderbar ohne komplexere Algorithmen ausgekommen, hab die dann erst im Studium kennengelernt.

Man kann ein Problem (halbwegs) effektiv lösen oder man verscuht sich zu behelfen. Doch je mehr "Werkzeuge" man hat um so besser kann man sich helfen, ist doch überall so. Schau es dir an und schau ob das interessant für dich sein könnte, wenn du es nicht wirklich brauchen kannst und es wirklich doof findest, lass es. Ansonsten wird es dich weiter bringen weil du weisst was noch so geht, was man noch machen kann und auch wie. Und nur weil andere das doof finden muss das ja nicht schlecht sein. Vielleicht findest du es ja auch interessant.

Danke für die Antworten. Ich werde mich mal mit dem Thema beschäftigen. Irgendwelche Büchertipps oder so?

supertux

Logn schrieb:

Jetzt bin ich auf das Thema Algorithmen und Datenstrukturen gestoßen, also so Listen, Bäume und so was. Lohnt es sich sich damit zu beschäftigen? Was würde ich damit anfangen können, oder was würde ich damit besser machen können als ohne dieses Wissen?

Für jemanden, der das längst verstanden hat und quasi täglich damit arbeitet, ist es manchmal schwer sich zu erinnern, wie man am Anfang sich gefühlt hat.

Ich kann mich an meine erste Info Vorlesung erinnern, als der Prof von Linked Lists und Trees gesprochen hat. Meine Reaktion war damals ähnlich wie deine: Lohnt es sich sich damit zu beschäftigen? Die Beispielse des Profs schienen mir zu künstlich zu sein, irgendwie alles unnötig.

Aber.... das zeigte nur, obwohl ich schon Jahre mit VisualBasic unterwegs war, wie wenig Anhnung ich von theoretischen Grundlagen hatte.

Der Name Datenstruktur kommt daher, dass du versuchst Daten strukturiert zu behandeln. Was sind die meisten Programme, die man so am Anfang so schreibt?

Gib eine Zahl ein: [user gibt 5 ein]
Gib eine andere Zahl ein: [user gibt 8 ein]
Die Addition von 5 und 8 ist 13

erst mit der Zeit und mit mehr Erfahrung wirst du anfangen andere Probleme zu lösen, wo du Daten hast und diese musst du bearbeiten. Komplizierte Daten (sagen wir mal Koordinaten) kannst du nicht mehr so einfach ein Int speichern, da brauchst du komplexe Datenstrukturen. Dann willst du sie anordnen, bewegen, löschen, vergleichen, verschieben, welche hinzufügen und dann merkst du, ein einfaches Array ist a) langsam und b) kompliziert für solche Aufgaben. Dann musst du dir bessere Alternativen ausdenken, wie man mit sowas umgeht. Dafür gibt es komplexere Datenzustrukturen wie Bäume, LinkedLists, Stacks, usw.

Nathan

Ich persönlich fand aber insbesondere die formelle Spezifikation von Algorithmen (so mit var, pre, post, reads und wie sie alle heißen), die einen viel zu hohen Bestandteil in der Vorlesung hatte, relativ unnötig.
Komplexitätstheorie war aber recht interessant, genau wie einige Bäume.

Ich habe jetzt eine Seite mit Videos von Vorlesungen zum Thema Algorithmen und Datenstrukturen gefunden. Ist zwar in Java, aber das kann ich sicher in C++ auch umsetzen.

Hier mal der Link, falls es noch jemanden interessiert:
http://www-lehre.inf.uos.de/~ainf/2013/index.html

Nach dem ich das alles durch habe, bin ich bestimmt etwas schlauer.

berniebutt schrieb:

In der Programmierung ist das so ähnlich. Auch hier hat man oft verschiedene Möglichkeiten zur Wahl.
Selber machen oder auf (unterschiedliche) fertige Lösungen zugreifen.

oder eben den Computer machen lassen. Gibt es ungefähr seit 1972, nennt sich Prolog.

Gregor

Nathan schrieb:

Komplexitätstheorie war aber recht interessant, genau wie einige Bäume.

Komplexitätstheorie ist in der Tat äußerst interessant. Aus meiner Sicht kommt sie im Informatikstudium wesentlich zu kurz, wenn man sich nicht explizit in diese Richtung spezialisiert. Natürlich ist Komplexitätstheorie aus Sicht der Programmierung relativ abstrakt, aber ich denke, dass Kenntnisse in Komplexitätstheorie eine Kernkompetenz jedes Informatikers sein sollten.

Mechanics

Gregor schrieb:

Komplexitätstheorie ist in der Tat äußerst interessant.

Find ich nicht, kenn ich auch sonst keinen einzigen, der so denkt Natürlich braucht man da paar Grundkenntnisse, aber sonst find ich es völlig uninteressant. Außer vielleicht für irgendwelche theoretischen Informatiker, die nur in der Forschung tätig sind.

Entwickelt man denn als Informatiker oft wirklich eigene Algorithmen, so wie einen neuen quicksort oder so? Ich denke mal, da braucht man dann schon die Komplexitätstheorie. Ich für meinen Teil habe mich da gestern mal eingelesen und haben jetzt meine Tabelle von O(1) bis O(N!) und kann so einschätzen welcher der Algorithmen( die es schon gibt) schneller oder langsamer sind, um so den richtigen wählen zu können. Aber wie man nun genau aus einem Algo die Komplexität ausrechnet ist mir noch zu kompliziert.

Algorithmen sollen die klugen Menschen erfinden, ich als DAU will die nur anwenden.

Jetzt lerne ich erst mal ein paar Algos durch die Vorlesungen kennen und spiele damit rum. Ist ja alles auch nur zum Spaß an der Freud. Dann kann ich auch ein wenig mit den echten Akademikern mitreden, oder zumindest annähernd verstehen was die so reden.

Mechanics schrieb:

Gregor schrieb:

Komplexitätstheorie ist in der Tat äußerst interessant.

Find ich nicht, kenn ich auch sonst keinen einzigen, der so denkt

jetzt schon.

Mechanics schrieb:

Natürlich braucht man da paar Grundkenntnisse, aber sonst find ich es völlig uninteressant. Außer vielleicht für irgendwelche theoretischen Informatiker, die nur in der Forschung tätig sind.

um seine Forschung zu finanzieren, muß so mancher Theoretiker das theoretische Wissen in praktisch nutzbare Form gießen können, sprich: Software herstellen.

Jester

Gregor schrieb:

Nathan schrieb:

Komplexitätstheorie war aber recht interessant, genau wie einige Bäume.

Komplexitätstheorie ist in der Tat äußerst interessant. Aus meiner Sicht kommt sie im Informatikstudium wesentlich zu kurz, wenn man sich nicht explizit in diese Richtung spezialisiert. Natürlich ist Komplexitätstheorie aus Sicht der Programmierung relativ abstrakt, aber ich denke, dass Kenntnisse in Komplexitätstheorie eine Kernkompetenz jedes Informatikers sein sollten.

Ich finde Komplexitätstheorie auch sehr interessant. Aber mir ist nicht ganz klar was Du Dir davon genau versprichst. Welche Kenntnisse in dem Bereich hältst Du für besonders relevant und warum? (Ich gehe mal davon aus, dass Komplexitätstheorie bei dir mehr heißt als O-Kalkül benutzen können)

Gregor

Logn schrieb:

Entwickelt man denn als Informatiker oft wirklich eigene Algorithmen, so wie einen neuen quicksort oder so? Ich denke mal, da braucht man dann schon die Komplexitätstheorie. Ich für meinen Teil habe mich da gestern mal eingelesen und haben jetzt meine Tabelle von O(1) bis O(N!) und kann so einschätzen welcher der Algorithmen( die es schon gibt) schneller oder langsamer sind, um so den richtigen wählen zu können. Aber wie man nun genau aus einem Algo die Komplexität ausrechnet ist mir noch zu kompliziert.

Wenn es um die Zeitkomplexität konkreter Algorithmen geht, würde ich von Komplexitätsanalyse reden und nicht von Komplexitätstheorie. Wobei man das natürlich als Teilgebiet der Komplexitätstheorie ansehen könnte.

Aus meiner Sicht geht es in der Komplexitätstheorie um die prinzipielle Komplexität von Problemstellungen, also darum, wie effizient ein Algorithmus für eine Problemstellung überhaupt sein kann. Ich denke, dass das für Informatiker relevant sein sollte, weil ein Verständnis von Problemstellungen natürlich ein Ausgangspunkt beim Design von Algorithmen ist. Vor allem sollte man hier Kompetenz haben, um entscheiden zu können, welchen Problemstellungen man sich überhaupt stellt bzw. wie man sich die Probleme designt.

Gregor

@Jester: Ok, Komplexitätstheorie insgesamt ist vielleicht zu weit gegriffen. Für die Praxis wird es vermutlich recht wenig bringen, das PCP Theorem oder so im Detail zu kennen. Aber Du kennst doch das Buch "Computers and Intractibility", oder? So etwas, was da gebracht wird, ist glaube ich sehr nützlich. ...nicht nur der hintere Teil.

Logn schrieb:

Entwickelt man denn als Informatiker oft wirklich eigene Algorithmen, so wie einen neuen quicksort oder so? Ich denke mal, da braucht man dann schon die Komplexitätstheorie. Ich für meinen Teil habe mich da gestern mal eingelesen und haben jetzt meine Tabelle von O(1) bis O(N!) und kann so einschätzen welcher der Algorithmen( die es schon gibt) schneller oder langsamer sind, um so den richtigen wählen zu können. Aber wie man nun genau aus einem Algo die Komplexität ausrechnet ist mir noch zu kompliziert.

Algorithmen sollen die klugen Menschen erfinden, ich als DAU will die nur anwenden.

Dann hättest du Fachinformatiker als Lehre machen sollen und nicht Informatik studieren sollen.

Jetzt lerne ich erst mal ein paar Algos durch die Vorlesungen kennen und spiele damit rum.

Naja, vielleicht wird sich deine Sichtweise noch ändern.