Was bringen mir Algorithmen und Datenstrukturen?

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.

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.

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.

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?

Gregor

Logn schrieb:

Kann man eigentlich sagen, dass die Wahl der richtigen Algorithmen viel wichtiger als die Performance der Programmiersprache ist?

Im Prinzip ja, aber...

Letztendlich sind das zwei Aspekte bei der Realisierung einer Lösung für eine Problemstellung, die relativ unabhängig von einander sind. Eigentlich solltest Du immer den "besten Algorithmus" in der "am Besten geeigneten Programmiersprache" realisieren. Wobei es natürlich immer etwas subjektiv und kontextabhängig ist, was das Beste ist. Es spielen meistens verschiedene Kriterien eine Rolle.

Na, ich will Java und C++ lernen, obwohl Java irgendwie ziemlich schnell zu lernen ging. Programmieren will ich allerdings auch mal für Mikrocontroller, weswegen ich mir auch C kurz angeschaut habe. Am meisten habe ich aber vor auch für mobile Geräte was zu machen und da ist Java ja wohl der Platzhirsch.

Wenn man das so sieht brauche ich C++ eigentlich überhaupt nicht. Warum ich damit angefangen habe? Nun, es gilt es die schwierigste und komplizierteste Sprache und das wollte ich mal verifizieren. Im Vergleich zu Java komme ich mit C++ unglaublich langsam zum Ziel, was wahrscheinlich aber auch an meiner C++-Unkenntnis liegt.

Mir wurde ja schon gesagt, dass man nicht viele Sprache nebeneinander lernen soll. Ja mag sein, aber ich will und wollte halt vergleichen. Im Moment denke ich, dass ich mit C und Java schon eine optimale Wahl getroffen habe.

Mechanics

Logn schrieb:

Kann man eigentlich sagen, dass die Wahl der richtigen Algorithmen viel wichtiger als die Performance der Programmiersprache ist?

Grundsätzlich ja. Aber wenn man irgendwann bei ähnlich optimalen Algorithmen angekommen ist, lohnen sich Mikrooptimierungen wieder, da kann man immer noch Faktor 2-3 rausholen. Also, wenn du mit einer naiven Lösung 5 Stunden brauchst, dann braucht man nicht weiterreden. Aber wenn du einen besseren Algo gefunden hast und bei 15 Minuten Laufzeit bist, kann man die 15 Minuten mit C++ vielleicht auf 5 runterdrücken. Und das kann man dann auch dem Kunden gegenüber argumentieren. Was, die Konkurrenten brauchen 15 Minuten? Das müssen ja komplette Vollidioten sein, wir schaffen das in 5. Der Punkt ist vielleicht gar nicht so sehr, dass es auf die 10 Minuten Unterschied ankommen würde, sondern dass die Konkurrenten Idioten sind und man mit denen nicht zusammenarbeiten sollte
Oder es geht irgendwann darum, ob man irgendwas in Echtzeit machen kann, oder ob man dann nach jeder Mausbewegung 2 Sekunden wartet.

Logn schrieb:

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?

Standardsachen wie Quicksort wird wohl kaum jemand selber programmieren, außer als Übung. Für Numerik gibts auch recht gute Bibliotheken. Was wir aber z.B. selber implementiert haben, sind Clustering Algorithmen, viele Algos im 3D Bereich, auch einen eigenen 3D Kernel. Das sind Bereiche, wo es viele neue Ideen in Form von Papers gibt. Aber so ein Paper ist erstmal nichts, was man direkt verwenden könnte. Das sind oft Sachen, die die Autoren auch nur so ein bisschen in Form eines Prototyps ausprobiert haben. Da muss man oft noch viel weiterforschen und rumprobieren, bis man sagen kann, ob man das überhaupt verwenden kann.

Logn schrieb:

Wenn man das so sieht brauche ich C++ eigentlich überhaupt nicht. Warum ich damit angefangen habe? Nun, es gilt es die schwierigste und komplizierteste Sprache und das wollte ich mal verifizieren.

und - stimmt es? Oder sind APL und Forth doch schwieriger? oder TeX?

Logn schrieb:

Ja mag sein, aber ich will und wollte halt vergleichen. Im Moment denke ich, dass ich mit C und Java schon eine optimale Wahl getroffen habe.

mag sein. Erwarte aber vielleicht keinen grenzenlosen Beifall für die Wahl in einem C++ Forum