[linux-l] Graphen und Didaktik (war: graphs of media-handling components)

Volker Grabsch vog at notjusthosting.com
Sa Jan 6 15:56:14 CET 2007


On Sat, Jan 06, 2007 at 07:49:53AM +0100, Detlef Lechner wrote:
> Am Freitag, den 05.01.2007, 23:49 +0100 schrieb Volker Grabsch:
> 
> > Eigentlich genügt es, zu sagen, ein Graph ist eine Menge mit einer
> > Relation. Und Umgangsspachlich nennt man die Elemente dann Knoten,
> > Man sagt, eine Kante führt von A nach B, wenn die Relation zwischen
> > A und B besteht.
> > 
> > Mögliche Realisierungen der Knoten Menge:
> 
> Ganz herzlichen Dank dafür, daß Du das so gründlich und klar
> zusammenhängend erläutert hast - einge große Hilfe, wenn man das nicht
> in einer Vorlesung gehört hat!

Nunja, ich habe das auch nicht in einer Vorlesung gehört, sondern all
das zusammgenfasst, was ich in der Schule und in verschiedenen Mathe-
und Info-Vorlesungen darüber gehört habe. Eine extra Vorlesung über
Graphentheorie gibt es nicht, das würde sich auch nicht lohnen.

Es gibt aber eine Vorlesung "Graphen und Algorithmen", in denen es
allgemein um Algorithmen, Datenstrukturen, deren Effizienz u.s.w.
geht. Etwas mehr über Graphen, und was das mit menschlichem Denken
zu tun hat, erfährt in einer Vorlesung über "Künstliche Intelligenz".
Geht es mehr um die Organisation, also Abstraktion und Komposition,
also die Beherrschung von Komplexität durch Etabliernug geeigneter
Strukturen, empielt sich: "Structure and Interpretation of Computer
Programs". Das ist eine Vorlesung am MIT, von der es im Netz Video-
Mitschnitte (CC-Lizenz) gibt, und auch ein Buch (unfrei, aber lesens-
wert, und es kursieren verschiedene semi-legale[1] PDFs). Eine damit
vergleichbare Vorlesung habe ich an meiner Uni noch nicht gefunden.
Nicht einmal die Vorlesung über Compilerbau geht auch nur annähernd
in diese Richtung.

> > (Weil unser Gehirn zwischen räumlichen und zeitlichen Dimensionen
> > unterscheidet, bedingt durch diese komische 3:1-Aufteilung in unserem
> > konkreten Universum. 3:1, das ist auch der tiefere Sinn dahinter, warum
> > unsere räumliche Vorstellungskraft besser geschult ist, und warum wir
> > zeitliche Ablkäufe uns immer irgendwie räumlich vorstellen, durch einen
> > Zeitstrahl, Kalender, u.Ä., obwohl ich es viel cooler fände, wenn wir
> > 4-dimensionale Geometrie im Kopf beherrschen würden. ;-))
> 
> Meinst Du mit "3:1-Aufteilung" 3 räumliche und 1 zeitliche Dimension in
> der menschlichen Vorstellung?

Jain, ich meine die 3 räumlichen und die 1 zeitliche Dimension in der
von uns wahrgenommenen Umwelt. Dass unsere Vorstellung mehr oder
weniger gut darauf geeicht ist, ist eher eine Folge-Erscheinung.

(Genauso, wie wir an Schwerkraft etc. gewöhnt sind ... merkt man
besonders, wenn man 3D-Space-Shooter spielt, dass man sehr daran
gewöhnt ist, sich jederzeit an ein gewisses "oben" und "unten" zu
orientieren zu können, das man bei diesen Spielen plötzlich nicht
mehr hat)

> > Die Konzepte von Bäumen und Graphen sind also sehr allgemein und ihre
> > Verwendung ist stark von der Art und Weise geprägt, wie unser Geist
> > arbeitet, und wie wir Komplexität beherrschen können.
> 
> Daher rührt wohl auch die große Menge von unterschiedlichen Definitionen
> von 'Graph' im Internet.

Nein, diese unterschiedlichen Definitionen rühren daher, dass man
je nach Anwendungsfall verschiedene Varianten von Graphen haben will.

Manchmal will man Schlaufen zulassen (d.h. eine Kante darf von einem
Knoten zu sich selbst führen). Manchmal ist es sinnvoller, dies von
vornherein auszuschließen. Manchmal sollten die Kanten eine Richtung
haben, manchmal lieber nicht. Manchmal will man den Knoten oder Kanten
Gewichte (also Zahlen) zuordnen, man spricht auch davon, den Graph zu
"färben" (ist ja egal, ob man die Zahl als Gewicht oder als Farbe
interpretiert). Manchmal will man das nicht. Manchmal ist es sinnvoll,
das "Gewicht 0" als "keine Kante" zu interpretieren, manchmal nicht.
Und so weiter.

Man kann diese Defintionen natürlich vereinheitlichen zum allgemeinsten
Fall (gewichteter Graph, in dem Schlaufen und Mehrfachkanten zulässig
sind), und alles andere als Spezialfälle davon definieren. Aber das ist
normalerweise viel umständlicher, als sich gleich auf das zu
beschränken, was man braucht. Zumal in der Anwendung meist völlig klar
ist, welche Art von Graph gemeint ist.

1) Das heißt, es gibt unterschiedliche *abstrakte* Definitionen.

Jenachdem ist es dann sinnvoller, die Kanten als 2-Mengen (ungeordnet)
oder als Paare (geordnet) zu modellieren. Oder als Funktion. Man weist
z.B. jedem Knotenpaar eine Zahl zu ... "0" steht dann für "keine Kante".
Selbst die Knoten müssen keine Menge sein. Manchmal realisiert man sie
auch als Liste oder Array. Oder man nummeriert sie einfach durch, d.h.
die Kantenmenge ist keine beliebige Menge, sondern eine der Form
{1,2,3,...,n}. In diesem Fall kann man die Knoten als Adjazenzliste
oder als Adjazenzmatrix realisieren.

2) Das heißt, es gibt zu jeder abstrakten Definition unterschiedliche
   *Realisierungen* in Form von Datenstrukturen.

Außerdem kann man Graphen auch anschaulich erklären, z.B. als Bäume
mit Querverbindungen, oder als Personen und Freundschaftsbeziehungen,
oder oder oder. Solche Dinge müssen manchmal ebenfalls als Definition
herhalten, obwohl es streng genommen keine sind. Sie sind für den
Formalismus völlig unwichtig, haben aber großen didaktischen Wert. Aber
das ist normalerweise von viel größerer Bedeutung als der Formalismus.
Ein guter Mathematiker/Informatiker kann eine verstandene Idee auch
selbst in einen Formalismus bringen. Aber die versteckte Idee aus
einem reinen Formalimus zu erkennen, das ist verdammt hart.

3) Das heißt, es gibt zu jeder abstrakten Definition auch noch
   unterschiedliche Veranschaulichungen.

Diese 3 Faktoren sorgen dafür, dass man im Netz so eine große Flut
von vermeintlich verschiedenen Definitionen findet.



Vielleicht noch was zur Didaktik:

Diesen Fehler erlebe ich übrigens recht häufig in der Mathematik und
Informatik, dass man sich zu viel Mühe mit einer formalen Definition
gibt, statt erstmal an Beispielen klar zu machen, worum es eigentlich
geht. Während die Profs und Übungsgruppenleiter da nicht so schlimm
sind, tendieren Studenten sehr dazu, wenn sie diese Dinge anderen
erklären sollen. Sie erklären es dann formal korrekt (manchmal nichtmal
das ;-)), statt es didaktisch gut zu erklären. In früheren Semestern
war ich manchmal aber genauso, muss ich zugeben.

Man kann z.B. erklären, was ein Körper ist, indem man von einer Menge
mit zwei Gruppenstrukturen redet, die durch ein Distributivgesetz
miteinander gekoppelt sind. Und das dann nochmal in Formeln
hinschreiben. Man kann aber auch einfach sagen, ein Körper ist ein
Gebilde, in dem die 4 Grundrechenarten funktionieren. :-)

(Danach kommen Beispiele wie Q, R, C und Gegenbeispiele wie Z, N,
und *dann* erst kann man überlegen, das Zeug formal hinzuschreiben.)


Noch schnell ein OnTBfH: [2]

Das ist auch in einer Mailingliste wichtig bzw. in einem Verein wie
der BeLUG, weil dort viel Wissen an Neulinge vermittelt werden muss.
Auch in der Programmierung freier und proprietärer Software ist das
wichtig. Die Qualität der Doku steigt enorm, wenn der Code zusammen-
hängend erklärt wird, und wenn zu jeder Klasse oder Funktion auch
etwas Beispiel-Code dasteht. Genauere, akkurate Beschreibungen sind
auch wichtig, aber erst für später zum Nachschlagen. Vorallem Randfälle
lassen akkurat mit viel weniger Worten beschreiben, wenn sie durch
Beispielcode vorgeführt werden. Denn dann stellt der Beispielcode den
Formalismus dar, den man sonst mühselig in Fließtext beschreiben müsste.



Viele Grüße,

    Volker

[1] semi-legal: eigentlich illegal, aber weder der Verlag noch die
                Autoren gehen dagegen vor.

[2] OnTBfH: OnT-Bezug für Holger :-)

-- 
Volker Grabsch
---<<(())>>---
Administrator
NotJustHosting GbR



Mehr Informationen über die Mailingliste linux-l