Baum- und Netzstruktur
Worum geht es?
Baumstrukturen
In der Informatik werden häufig baumartige Datenstrukturen verwendet. Einerseits werden sie bei Daten mit einer hierarchische Struktur verwendet, wie zum Beispiel bei einem Stammbaum oder in der Informatik ein Dateisystem mit Verzeichnissen und Dateien. Auf der anderen Seite kann man sie aber auch verwenden, wenn man in einer geordneten Datenmenge Elemente schnell finden will: Mit einem binären Suchbaum.
Alle Baumstrukturen in der Informatik haben eine Wurzel, die immer zuoberst beginnt, die anderen Elemente können variieren.
Alle Baumstrukturen in der Informatik haben eine Wurzel, die immer zuoberst beginnt, die anderen Elemente können variieren.
Um den Baum für einen bestimmten Anwendungszweck zu beschränken, können Restriktionen festgelegt werden. Bäume können gerichtet oder ungerichtet sein.
Ein spezieller Baum ist der binäre Baum. Er hat die Ordnung 2, das heisst jeder Knoten darf maximal zwei Kind-Knoten haben. Die Suche in einem solchen Baum entspricht der binären Suche.
Auch Entscheidungsbäume trifft man in der Informatik an. Sie werden aber anders verwendet, wie die Bäume, die oben beschrieben wurden. Man kann sie zum Beispiel dazu brauchen, um Objekte nach bestimmten Kriterien zu klassifizieren. Dies wird beim maschinellen Lernen genutzt oder bei der Klassifizierung von Paketen beim Versenden durch ein Netzwerk.
Sobald man den Entscheidungsbaum verwendet, um etwas zu sortieren/klassifizieren, handelt es sich um einen Algorithmus.
Ein spezieller Baum ist der binäre Baum. Er hat die Ordnung 2, das heisst jeder Knoten darf maximal zwei Kind-Knoten haben. Die Suche in einem solchen Baum entspricht der binären Suche.
Auch Entscheidungsbäume trifft man in der Informatik an. Sie werden aber anders verwendet, wie die Bäume, die oben beschrieben wurden. Man kann sie zum Beispiel dazu brauchen, um Objekte nach bestimmten Kriterien zu klassifizieren. Dies wird beim maschinellen Lernen genutzt oder bei der Klassifizierung von Paketen beim Versenden durch ein Netzwerk.
Sobald man den Entscheidungsbaum verwendet, um etwas zu sortieren/klassifizieren, handelt es sich um einen Algorithmus.
Netzstrukturen
Netzstrukturen findet man in der Informatik bei Graphen oder Netzwerken. Bei jedem dieser Netze sind verschiedene Objekte miteinander verbunden.
Für die Graphen verwendet man die gleichen Bezeichnungen wie bei den Bäumen: Knoten sind mit Kanten verbunden, diese können gerichtet oder ungerichtet sein, sie sind im Gegensatz zu Bäumen oft zyklisch. Der Dijkstra-Algorithmus ist hier von Bedeutung, damit soll der kürzeste Weg zwischen zwei Knoten in einem Graphen gefunden werden. Ein bekanntes Problem aus der Graphentheorie, das die theoretische Informatik beschäftigt, ist das Problem des Handelsreisenden.
Rechnernetze bestehen aus Geräten, die untereinander mit verschiedenen Netzwerktopologien verbunden sein können, zum Beispiel sternförmig, als Bus oder vermascht.
Für die Graphen verwendet man die gleichen Bezeichnungen wie bei den Bäumen: Knoten sind mit Kanten verbunden, diese können gerichtet oder ungerichtet sein, sie sind im Gegensatz zu Bäumen oft zyklisch. Der Dijkstra-Algorithmus ist hier von Bedeutung, damit soll der kürzeste Weg zwischen zwei Knoten in einem Graphen gefunden werden. Ein bekanntes Problem aus der Graphentheorie, das die theoretische Informatik beschäftigt, ist das Problem des Handelsreisenden.
Rechnernetze bestehen aus Geräten, die untereinander mit verschiedenen Netzwerktopologien verbunden sein können, zum Beispiel sternförmig, als Bus oder vermascht.
Passende Inhalte Mathwelt und Zahlenbuch
Mathwelt 2
|
Zahlenbuch 6
|
Unterrichtsmaterialien
Lehrmittel
- Einfach Informatik 5/6: Lösungen finden - 1. Maschinen steuern
- Einfach Informatik 5/6: Lösungen finden - 4. Gute Entscheidungen treffen
- inform@21: Sich zu helfen wissen
Online
Weitere Ideen
- Eine Datei auf dem Laptop untersuchen: Kann dazu ein Verzeichnisbaum bis zur Datei erstellt werden?
- Aufbau einer einfachen Website untersuchen: Kann sie als Baumstruktur aufgezeichnet werden?
- Stammbaum der Familie zeichnen nur mit den nötigsten Informationen (>Young World 3)
- Entscheidungs-/Sortierbäume entwerfen
Lehrplan 21
MI.2.1
1 Die Schülerinnen und Schüler können Daten aus ihrer Umwelt darstellen, strukturieren und auswerten.
Die Schülerinnen und Schüler können...
1 Die Schülerinnen und Schüler können Daten aus ihrer Umwelt darstellen, strukturieren und auswerten.
Die Schülerinnen und Schüler können...
- f erkennen und verwenden Baum- und Netzstrukturen (z.B. Ordnerstruktur auf dem Computer, Stammbaum, Mindmap, Website).