Bäume?!

Th69

Gerade bei Bäumen (in der Informatik) sollte auch der Begriff (Mono)Hierarchie gefallen sein, und daher ist klar, daß Bäume eine der fundamentalsten Datenstrukturen sind (um Eltern-Kind-Relationen (parent child relations) darzustellen, also unabhängig von einer konkreten Implementierung).

dot hat ja auch schon genug Beispiele beschrieben, die aufzeigen, daß es ohne Hierachie (Bäume) nicht geht (wie im echten Leben -)

berniebutt

@dot: Wird wohl so sein, dass man überall diesen ´Bäumen´ begegnet und diese benutzt ohne davon zu wissen. Solange man das nicht selbst realisieren und nur durch die eingesetzten Hilfsmittel benutzt kommt man damit nicht in Berührung. Ich frage auch nicht danach, was z.B. bei C hinter <math.h> alles verborgen ist. Aber der Fragesteller studiert wohl Informatik und da gehören solche und andere Dinge einfach dazu.

@Th69: Im echten Leben habe ich Bäume im Garten und weiss, dass ich zur rechten Zeit davon Kirschen, Äpfel oder sonstwas ernten kann!

dot

Also ich hab in sicher 70% all meiner Projekte der letzten 3 Jahre und 100% der gößeren davon an mindestens einer Stelle baumartige Strukturen selbst implementiert. Und selbst wenn man solche Datenstrukturen nur fertig verwendet und nicht selbst schreibt ist ein genaues Wissen über die theoretische Funktionsweise einfach unerlässlich, das gilt für die Funktionen in math.h genauso wie für alles andere.

asc

dot schrieb:

...Und selbst wenn man solche Datenstrukturen nur fertig verwendet und nicht selbst schreibt ist ein genaues Wissen über die theoretische Funktionsweise einfach unerlässlich, das gilt für die Funktionen in math.h genauso wie für alles andere...

Einfach nur Unsinn. Nach deiner Beschreibung müsste man auch bei einem DVD-Spieler den internen Aufbau verstehen, um ihn verwenden zu können. Theoretisches Wissen um die Funktionsweise von etwas ist zwar nicht schädlich, aber auch nicht notwendig, wenn man weiß was eine Schnittstelle grundsätzlich tut (damit meine ich keine Implementationskenntnisse, sondern das Wissen zur Anwendung).

Ich brauche auch keine WinAPI-Kenntnisse um z.B. die VCL zu verwenden, ebenso brauche ich keine DirectX-Kenntnisse um WPF zu verwenden.

Ein Theoretiker kann sich gerne mit der Optimierung von Algorithmen beschäftigen, doch die wenigsten Praktiker werden das theoretische Wissen benötigen um diesen zu verwenden.

berniebutt

@dot: Wir sind hier im Forum nicht alle Studenten der Informatik oder haben das nie gelernt und realisieren dennoch Software-Projekte. Fertig ausgebildete Informatiker müssen oft schnell das Handtuch schmeissen, weil sie einige fachspezifische Aufgaben nicht verstehen können. Es geht nicht alleín um Datenstrukturen und ähnliches. Manchmal geht es schlicht um einfache oder komplizierte Algorithmen.

dot

Nein das wollte ich damit nicht sagen. Du musst nicht wissen wie genau dein Baum implementiert ist, ob es jetzt ein Rot-Schwarz Baum oder ein 2-4 Baum oder sonstwas ist ist vielleicht meistens egal. Aber du musst wissen was ein Baum prinzipiell ist, du musst wissen und verstanden haben welche grundlegende Idee hinter einer solchen Datenstruktur steht und welche Konsequenzen aus der Verwendung einer solchen Datenstruktur erwachsen, welche Alternativen es vielleicht gibt usw. usw. Denn schließlich musst du dich im Kontext einer gewissen Problemstellung für eine bestimmte Datenstruktur entscheiden. Und um das zu können führt kein Weg daran vorbei die Grundprinzipien verstanden zu haben. Du musst vielleicht meistens nicht wissen wie ein DVD Player aufgebaut ist. Aber du solltest wissen was eine DVD ist und warum du dir eine DVD gekauft hast anstatt einer VHS oder SVCD oder Blu-Ray etc.

dot

berniebutt schrieb:

Es geht nicht alleín um Datenstrukturen und ähnliches. Manchmal geht es schlicht um einfache oder komplizierte Algorithmen.

Wenn es um Algorithmen geht dann geht es auch um Datenstrukturen. Und es ist egal ob studierter Informatiker oder nicht. Bäume sind fürs Programmieren ca. so grundlegend wie ein Schraubenzieher für einen Handwerker. Ich glaub kaum dass du mir einen professionellen Programmierer zeigen kannst der nicht weiß was ein Baum ist, da wär ich echt ziemlich verblüfft.

berniebutt

Lassen wir diese Diskussion besser sein. Die zunächst benötigten Datenstrukturen sind:
.. Die fundamentalen Datentypen wie int, char, float, etc..
.. struct und class
.. vielleicht auch Container-Klassen
Alles weitere ist bereits als anwendungsspezifisch zu betrachten. Aber niemand sei daran gehindert, auch die Internas der eingesetzten Hilfsmittel im Detail verstehen zu wollen.
daddeldu! :p

asc

dot schrieb:

Denn schließlich musst du dich im Kontext einer gewissen Problemstellung für eine bestimmte Datenstruktur entscheiden.

Wobei es reicht eine Entscheidungstabelle zu haben (Welche Operation ist mit welchen Container schnell bzw. sinnvoll).

dot schrieb:

Ich glaub kaum dass du mir einen professionellen Programmierer zeigen kannst der nicht weiß was ein Baum ist, da wär ich echt ziemlich verblüfft.

Ich weiß zwar das ein Baum aus Ästen zusammengesetzt ist, aber die Details sind mir nicht (mehr) geläufig - da ich das Wissen nie in der Praxis benötigt hatte. Mir haben in der Praxis jedenfalls tabellarische Zusammenfassungen der Container mit ihren Stärken und Schwächen weit mehr in der Praxis geholfen.

Und ich gehe sogar davon aus das viele professionelle Anwendungsentwickler die nicht studiert haben, noch nichts von Bäumen gehört haben (und selbst ein Teil der studierten wenn es nicht gerade um reine Informatiker geht).

knivil

Baeume sind Container. Und ich glaube kaum, dass sich viele den internen Aufbau einer Klasse in C++ angesehen haben.

Alles weitere ist bereits als anwendungsspezifisch zu betrachten.

Jaja, genau wie Primzahlen vor 100 Jahren oder so ...

asc schrieb:

Und ich gehe sogar davon aus das viele professionelle Anwendungsentwickler die nicht studiert haben, noch nichts von Bäumen gehört haben (und selbst ein Teil der studierten wenn es nicht gerade um reine Informatiker geht).

Gibts jetzt schon nen Excel Studiengang?

hustbaer

berniebutt schrieb:

Die zunächst benötigten Datenstrukturen sind:
.. Die fundamentalen Datentypen wie int, char, float, etc..
.. struct und class
.. vielleicht auch Container-Klassen

Das sind alles keine Datenstrukturen.

Alles weitere ist bereits als anwendungsspezifisch zu betrachten.

Ne.

Sqwan

Hääelooo schrieb:

asc schrieb:

Und ich gehe sogar davon aus das viele professionelle Anwendungsentwickler die nicht studiert haben, noch nichts von Bäumen gehört haben (und selbst ein Teil der studierten wenn es nicht gerade um reine Informatiker geht).

Gibts jetzt schon nen Excel Studiengang?

Nein gibts nicht. Bevor du dich an einem solchen versuchst, solltest du auch mal die Grundschule versuchen. Die bringen dir einiges bei, was du scheinbar verpasst hast

rasfdfgge schrieb:

gastantwort schrieb:

Wenn du Programmierer werden willst studierst du eben nicht Informatik, so einfach ist das

Immer das gleiche, saudumme Gerede hier...

Ist jetzt nicht für alle. Die richtigen fühlen sich schon angesprochen.

EDIT:
@hustbaer
was sind denn neben bäumen noch datenstrukturen?
von listen mal abgesehen, da die irgendwo ja auch unter bäume fallen...

dot

Sqwan schrieb:

was sind denn neben bäumen noch datenstrukturen?
von listen mal abgesehen, da die irgendwo ja auch unter bäume fallen...

oO ist die Frage wirklich ernst gemeint?
Arrays, Stacks, (Priority)Queues, Heaps, Hastables, Graphen (Bäume, Listen, DAGs, etc. sind Spezialfälle von Graphen), nur um mal die paar ganz grundlegenden Konzepte zu nennen die man wirklich ständig braucht. Ausgehend davon gibts dann alle möglichen konkreteren Datenstrukturen, siehe auch hier: http://en.wikipedia.org/wiki/List_of_data_structures

Sqwan

ist eine Queue nicht eine liste? Genau wie der stack?
Heaps sind doch irgendwo auch bäume? Da sich Arrays am Heap orientieren auch irgendwo ein Baum?

Wobei mir grade auffällt, ob ein stack oder eine Queue eine Liste ist, könnte von der Implementierung abhängen :S Bin ein bischen verwirrt ^^

Irgendwie ist meine Frage nicht so richtig beantwortet. Ich wollte ja eigentlich eine Liste an Datenstruckturen die NICHTS mit Bäumen zu tun haben. Auch nicht im entfernten Sinne ...

wie viele Trees es gibt xD 90% der liste sind ja irgendwie geartete Trees

dot

Sqwan schrieb:

ist eine Queue nicht eine liste? Genau wie der stack?

Datenstruktur hat nicht nur damit zu tun wie Elemente im Speicher abgelegt sind sondern vor allem auch damit wie sie organisiert sind und welche Operationen darauf definiert sind. Und da gibt es ganz wesentliche Unterschiede zwischen Stacks, Queues, Listen, etc. Es gibt weiß Gott wieviele Arten um Stacks, Queues, Listen, Bäume, Graphen, etc. im Speicher zu organisieren. Nur weil manche Implementierungen einer Queue intern vielleicht eine verlinkte Liste verwenden bedeutet das noch lange nicht dass eine Queue eine verlinkte Liste ist.

Sqwan schrieb:

Heaps sind doch irgendwo auch bäume? Da sich Arrays am Heap orientieren auch irgendwo ein Baum?

Wobei mir grade auffällt, ob ein stack oder eine Queue eine Liste ist, könnte von der Implementierung abhängen :S Bin ein bischen verwirrt ^^

Irgendwie ist meine Frage nicht so richtig beantwortet. Ich wollte ja eigentlich eine Liste an Datenstruckturen die NICHTS mit Bäumen zu tun haben. Auch nicht im entfernten Sinne ...

wie viele Trees es gibt xD 90% der liste sind ja irgendwie geartete Trees

Da siehst du mal wie wichtig Bäume sind. Abgesehen davon beantworten alle Datenstrukturen der Liste bis auf die unter Punkt 3 deine Frage nach Datenstrukturen die nichts mit Bäumen zu tun haben, du kannst von mir aus noch einfach verlinkte Listen als entarteten Baum auffassen aber das wars dann auch schon.

Sqwan

dot schrieb:

Sqwan schrieb:

ist eine Queue nicht eine liste? Genau wie der stack?

Datenstruktur hat nicht nur damit zu tun wie Elemente im Speicher abgelegt sind sondern vor allem auch damit wie sie organisiert sind und welche Operationen darauf definiert sind. Und da gibt es ganz wesentliche Unterschiede zwischen Stacks, Queues, Listen, etc.

Sowas fänd ich z.B. sehr wissenswert in einem Studium...

Sqwan schrieb:

Heaps sind doch irgendwo auch bäume? Da sich Arrays am Heap orientieren auch irgendwo ein Baum?

Wobei mir grade auffällt, ob ein stack oder eine Queue eine Liste ist, könnte von der Implementierung abhängen :S Bin ein bischen verwirrt ^^

Irgendwie ist meine Frage nicht so richtig beantwortet. Ich wollte ja eigentlich eine Liste an Datenstruckturen die NICHTS mit Bäumen zu tun haben. Auch nicht im entfernten Sinne ...

wie viele Trees es gibt xD 90% der liste sind ja irgendwie geartete Trees

Da siehst du mal wie wichtig Bäume sind. Abgesehen davon beantworten alle Datenstrukturen der Liste bis auf die unter Punkt 3 deine Frage nach Datenstrukturen die nichts mit Bäumen zu tun haben, du kannst von mir aus noch einfach verlinkte Listen als entarteten Baum auffassen aber das wars dann auch schon.

Ich hab ja mittlerweile mitbekommen wie wichtig Bäume sind. Schade nur das ich das hier lernen muss, und nicht im Studium. Wie dem auch sei. Ich hab das gefühl, wir drehen uns im Kreis. Oder treten auf der Stelle.

Eine Frage noch zum Heap. Ein Heap ist doch ein echter baum oder nicht? So hatten wir das jedenfalls in der Vorlesung...

EDIT: Heaps sind ja auch unter Trees aufgeführt ^^ Also alles klar

dot

Sqwan schrieb:

Eine Frage noch zum Heap. Ein Heap ist doch ein echter baum oder nicht? So hatten wir das jedenfalls in der Vorlesung...

Ein Heap ist eine baumartige Datenstruktur deren Elemente die Heapbedingung erfüllen, also ja.

Sqwan schrieb:

Hääelooo schrieb:

asc schrieb:

Und ich gehe sogar davon aus das viele professionelle Anwendungsentwickler die nicht studiert haben, noch nichts von Bäumen gehört haben (und selbst ein Teil der studierten wenn es nicht gerade um reine Informatiker geht).

Gibts jetzt schon nen Excel Studiengang?

Nein gibts nicht. Bevor du dich an einem solchen versuchst, solltest du auch mal die Grundschule versuchen. Die bringen dir einiges bei, was du scheinbar verpasst hast

Warum bist du so aggressiv, bei nem Witz?
Ach so

Sqwan schrieb:

Ich hab ja mittlerweile mitbekommen wie wichtig Bäume sind. Schade nur das ich das hier lernen muss, und nicht im Studium. Wie dem auch sei. Ich hab das gefühl, wir drehen uns im Kreis. Oder treten auf der Stelle.

du bist der der keine Ahnung hat und willst mich für dumm hinstellen, um von deiner Unfähigkeit abzulenken.

hustbaer

Da sich Arrays am Heap orientieren auch irgendwo ein Baum?

Die Aussage ist so wie sie dasteht nicht richtig.

Binäre Heaps werden oft als Array abgelegt, wobei die Position im Baum sich aus der Position im Array berechnen lässt und umgekehrt (worudch die Zeiger auf die Nodes entfallen).

Umgekehrt hat ein Array aber nichts mit einem Heap zu tun, und auch nichts mit Bäumen im Allgemeinen.