Was bringen mir Algorithmen und Datenstrukturen?

[leiseahnung]

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.

[klappstuhl]

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.

[Gast]

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.

[Gast]

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.

[großbuchstaben]

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.

[Gast]

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.

[großbuchstaben]

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.

[Öhm nö]

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.

[Mechanics]

Logn schrieb:

Entwickelt man denn als Informatiker oft wirklich eigene Algorithmen, so wie einen neuen quicksort oder so?

Nicht unbedingt sowas wie Quicksort. Und es kommt drauf an, was du als "Informatiker" überhaupt machst. Admins sind auch Informatiker (bzw. viele Informatiker arbeiten als Admins), werden aber sicher nie irgendwelche Algos brauchen. Webentwickler werden wahrscheinlich auch nie großartige Algorithmen brauchen.
Ansonsten kann es aber schon mal vorkommen, dass man etwas komplexere Programme schreibt. Ein Algorithmus muss ja nicht unbedingt sowas allgemeines und wiederverwendbares wie Quicksort sein. Jedes Programm ist ein Algorithmus. Kann sein, dass du z.B. eine größere Datenmenge analysieren musst. Und du suchst dabei nach bestimmten Strategien, um das schneller machen zu können. z.B. divide and conquer, wie beim Quicksort. Oder du betrachtest die Abhängigkeiten zwischen den Daten als Graph und kannst dann z.B. durch die topologische Sortierung die Daten in eine optimale Reihenfolge bringen. Oder du erkennst, dass bestimmte Teilgraphen für deine Analyse überhaupt nicht relevant sind und kannst sie gleich überspringen. Solche Algorithmen schreibt man halt im Alltag.
Dafür muss man natürlich auch eine Komplexitätsanalyse machen können. Wenn die triviale Lösung O(n) wäre und für die raffiniertere Lösung erst in (n * log(n)) eine Sortierung durchgeführt werden müsste, dann ist die triviale Lösung besser. Aber solche Analysen kann meist relativ einfach machen, dafür muss man sich nicht besonders in die Komplexitätstheorie vertiefen.

[Gast]

Danke für den Einblick. Also nutzt man eher vorhandene Algos und Techniken und verbindet diese, als das man nun was komplett bahnbrechendes Neues erfindet, was aus einer bekannten Problemlösung mit O(N) Laufzeit eines mit O(log N) macht.

Sind denn Leute hier auch als Wissenschaftler tätig, also in der Forschung, so mit richtigem Doktor?

Öhm nö schrieb:

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.

Ähm, ich studiere nicht. Ich habe nicht mal ein Abi. Ich mache das nur aus Spaß und nicht um damit Geld zu verdienen, oder noch mal eine Lehre anzufangen. Das hier ist alles nur so nebenher, da ich vieeeeel Zeit derzeit habe.

[Mechanics]

Logn schrieb:

Danke für den Einblick. Also nutzt man eher vorhandene Algos und Techniken und verbindet diese, als das man nun was komplett bahnbrechendes Neues erfindet, was aus einer bekannten Problemlösung mit O(N) Laufzeit eines mit O(log N) macht.

Ja, als Softwareentwickler kombiniert man meist etwas vorhandenes. Die Herausforderung ist wohl nicht so sehr das Kombinieren, sondern das Erkennen, dass man etwas bekanntes auf sein Problem anwenden kann.
Es geht auch nicht immer unbedingt nur um Performance oder um etwas bahnbrechendes... Bei der Forschung geht es oft darum, irgendwelche Aspekte von bekannten oder weniger bekannten Problemen zu untersuchen. Sagt dir das Rucksackproblem etwas? Ich hatte vor paar Jahren so ein ähnliches Problem und hab da etwas rumgesucht und wahrscheinlich hunderte Publikationen zu dem Thema gefunden. Viele davon beziehen sich darauf, dass man die Bedingungen leicht verändert oder Zusatzbedingungen stellt. Das kann in der Praxis ja durchaus vorkommen, läuft ja meist nicht auf die Standardvariante von einem Problem hinaus, sondern man hat zusätzliche Bedingungen oder zusätzliche Kenntnisse. Das kann zu völlig anderen Lösungsansätzen führen. Es kann aber natürlich auch sein, dass man sowas eben "selber" macht und nicht darauf wartet, dass es eine Publikation zu dem Thema gibt. So entstehen wahrscheinlich auch viele dieser Publikationen.

[Gast]

Sehr interessant, solche Erzählungen wie deine hier liest man äußert selten. Es sollte viel mehr solche Praxisgeschichten geben, das motiviert unheimlich sich mit der Informatik näher zu beschäftigen. Kann man eigentlich sagen, dass die Wahl der richtigen Algorithmen viel wichtiger als die Performance der Programmiersprache ist?

Durch die Vorlesungsvideos werde ich wohl erst einmal mit Java weiter machen, das geht mir irgendwie um Längen schneller von der Hand. C++ verlieren ich nicht aus den Augen, aber ich will auch mal voran kommen mit den Algos.

Nutzt man eigentlich in der Praxis mehr Libs oder macht man da auch viel selbst? Wenn ja, was macht man selbst und was kommt aus Libs?