Zur Haupt­na­vi­ga­ti­on sprin­gen [Alt]+[0] Zum Sei­ten­in­halt sprin­gen [Alt]+[1]

Frosch­per­spek­ti­ve vs. Ad­ler­per­spek­ti­ve

Nach­dem die Aus­gangs­si­tua­ti­on als Graph mo­del­liert wurde, muss nun der Al­go­rith­mus er­ar­bei­tet wer­den. Men­schen er­fas­sen den Gra­phen als Ge­samt­heit ("Ad­ler­per­spek­ti­ve"), beim Pro­gram­mie­ren kann man aber immer nur einen ein­zi­gen Kno­ten be­ar­bei­ten. Über be­reit­ge­stell­te Me­tho­den des Gra­phen kann man auch auf an­gren­zen­de Kan­ten oder ver­bun­de­ne Kno­ten zu­grei­fen.

Un­plug­ged

Daher ist es wich­tig, dass die Schü­ler den Gra­phen in "Frosch­per­spek­ti­ve" be­trach­ten, d.h. immer nur einen klei­nen Aus­schnitt des Gra­phen im Blick haben. Diese Frosch­per­spek­ti­ve kann man bei pla­na­ren Gra­phen mit nicht zu vie­len Kan­ten un­plug­ged er­rei­chen, indem man die Kno­ten he­xa­go­nal an­ord­net. Jeder Kno­ten kann da­durch Kan­ten zu höchs­tens sechs Nach­barn haben. Dar­über legt man ein vor­ge­fer­tig­tes Mas­ken­blatt mit Loch, das den Blick nur auf einen ein­zi­gen Kno­ten mit sei­nen Nach­barn frei­gibt. Even­tu­ell soll­te der Graph mit dar­über lie­gen­der Scha­blo­ne von einem an­de­ren Schü­ler oder der Lehr­kraft vor­be­rei­tet wer­den, damit of­fen­sicht­li­che Ei­gen­schaf­ten nicht so­fort er­fasst wer­den (z. B. ob der Graph zu­sam­men­hän­gend ist). Auch eine An­ord­nung auf einem qua­dra­ti­schen Git­ter (bis zu 4 bzw. 8 Nach­barn) wäre mög­lich. Je nach Al­go­rith­mus ist es sinn­voll, die Kno­ten durch­zu­num­me­rie­ren, um eine Liste mit noch zu be­ar­bei­ten­den Kno­ten füh­ren zu kön­nen.

Sol­len die noch zu be­ar­bei­ten­den Kno­ten in einer Schlan­ge ge­spei­chert wer­den (Brei­ten­su­che), dann kann man die Liste der zu be­ar­bei­ten­den Kno­ten ein­fach hin­ter­ein­an­der schrei­ben und die be­ar­bei­te­ten Kno­ten ab­strei­chen:

Breitensuche

Bild­quel­le: Brei­ten­su­che von ZPG In­for­ma­tik [CC BY-NC-SA 3.0 DE], aus 2_­un­ter­richts­ver­lauf.odt, be­ar­bei­tet

Hier ist K3 der ak­tu­el­le Kno­ten, K2 und K1 wur­den schon be­ar­bei­tet, K6 und K7 war­ten auf die Be­ar­bei­tung. Sol­len die noch zu be­ar­bei­ten­den Kno­ten in einem Sta­pel ge­spei­chert wer­den (Tie­fen­su­che), muss der Ver­lauf des Sta­pels pro­to­kol­liert wer­den. Dazu ist in jedem Schritt eine Über­tra­gung des Sta­pels not­wen­dig:
Tiefensuche

Bild­quel­le: Tie­fen­su­che von ZPG In­for­ma­tik [CC BY-NC-SA 3.0 DE], aus 2_­un­ter­richts­ver­lauf.odt, be­ar­bei­tet

Der Start­kno­ten war hier K2. Bei der Aus­wer­tung die­ses Kno­tens wur­den die Kno­ten K1 und K3 hin­zu­ge­fügt. K3 ist der nächs­te zu be­ar­bei­ten­de Kno­ten, die­ser wird vom Sta­pel ent­fernt und bei der Be­ar­bei­tung K6 und K7 hin­zu­ge­fügt. Die Be­ar­bei­tung von K7 fügt keine wei­te­ren Kno­ten hinzu. Daher ist K6 der nächs­te Kno­ten. Dabei wird K4 und K8 hin­zu­ge­fügt. K8 ist der ak­tu­ell zu be­ar­bei­ten­de Kno­ten.

Vor­tei­le: In der Maske be­kommt man „un­plug­ged“ den di­dak­tisch wün­schens­wer­ten Tun­nel­blick, d.h. man sieht nur die nächs­te Nach­bar­schaft des fo­kus­sier­ten Kno­tens; das Me­di­um zwingt wie ein Schreib­tisch­test zum Mit­den­ken, und die hän­di­sche („en­ak­ti­ve“) Aus­füh­rung ist für man­che Schü­ler ein­fa­cher zu er­ler­nen als die Be­die­nung des Gra­phen­tes­ters.

Nach­tei­le: Ge­ne­rell sind nur pla­na­re Gra­phen mit ent­spre­chend re­gel­mä­ßi­ger An­ord­nung mög­lich. Manch­mal sind auch nicht ver­bun­de­ne Kno­ten mit im Blick (z.B. bei Fokus auf Kno­ten links unten). Nach der Be­ar­bei­tung eines Kno­tens muss ein neuer Kno­ten fo­kus­siert wer­den. Für die Aus­wahl die­ses Kno­tens ist ein Blick auf den ge­sam­ten Gra­phen not­wen­dig. Die Ver­wal­tung eines Sta­pels ist recht auf­wän­dig.

Frosch­per­spek­ti­ve im Gra­phen­tes­ter

Graphentester

Bild­quel­le: Gra­phen­tes­ter von ZPG In­for­ma­tik [CC BY-NC-SA 3.0 DE], aus 2_­un­ter­richts­ver­lauf.odt

Der Gra­phen­tes­ter un­ter­stützt das Er­pro­ben eines Al­go­rith­mus in der Frosch­per­spek­ti­ve im "Ex­pe­ri­men­tier­mo­dus". Dar­ge­stellt wer­den dabei immer ein Kno­ten bzw. eine Kante und die da­zu­ge­hö­ri­gen Nach­barn (A). Wird das Hin­ter­grund­bild aus­ge­blen­det (Stan­dard­ein­stel­lung), dann er­kennt man nicht mehr, an wel­cher Stel­le im Gra­phen man sich be­fin­det.

Die dar­ge­stell­ten Kno­ten und Kan­ten kön­nen mit der Maus aus­ge­wählt wer­den und ent­we­der über die Ei­gen­schaf­ten auf der rech­ten Seite oder mit einem Kon­text­me­nü be­ar­bei­tet wer­den. Dabei ist es nicht mög­lich, die Struk­tur des Gra­phen zu ver­än­dern.

Kno­ten kön­nen als "be­sucht" und als "mar­kiert" ge­kenn­zeich­net wer­den, Kan­ten als "mar­kiert" und als "ge­löscht" (B). Die Farbe eines Kno­tens er­gibt sich ent­we­der au­to­ma­tisch aus die­sen Ein­stel­lun­gen (Op­ti­on "au­to­ma­tisch") oder kann über eine Farbaus­wahl be­stimmt wer­den.

Dar­über hin­aus kann der Wert eines Kno­tens ge­än­dert wer­den (C).

Eine "ToDo-Liste" (D) ent­hält die noch zu be­ar­bei­ten­den Kno­ten / Kan­ten. Über das Kon­text­me­nü (rech­te Maus­tas­te) kön­nen Kno­ten / Kan­ten der ToDo-Liste hin­zu­ge­fügt oder aus ihr ge­löscht wer­den. Da­durch dass das Ein­fü­gen am An­fang oder am Ende der Liste er­fol­gen kann, kann die ToDo-Liste als Sta­pel oder als Schlan­ge ver­wen­det wer­den und damit Tie­fen- oder Brei­ten­su­che rea­li­siert wer­den. Ist über die An­sicht "Kno­ten­wer­te an­zei­gen" aus­ge­wählt, ist es au­ßer­dem mög­lich, die ToDo-Liste zu sor­tie­ren und damit eine Prio­ri­täts­war­te­schlan­ge zu rea­li­sie­ren (z.B. für Di­jk­s­tra- oder Krus­kal-Al­go­rith­mus).

Mit der Op­ti­on "Gehe zu ..." des Kon­text­me­nüs kann man die­ses Ele­ment in einem neuen Tab öff­nen, aber spä­ter wie­der zum vor­he­ri­gen Kno­ten zu­rück­keh­ren. Damit ist es mög­lich, einen re­kur­si­ven Auf­ruf durch­zu­füh­ren. Zu­sam­men mit der Op­ti­on "Zu­stand si­chern" (D), die den ak­tu­el­len Zu­stand des Gra­phen si­chert und eine Wie­der­her­stel­lung zu einem spä­te­ren Zeit­punkt er­mög­licht, kann ein Back­tracking-Al­go­rith­mus rea­li­siert wer­den.

Durch diese Mög­lich­keit kann der Auf­rufs­tack eines re­kur­si­ven Al­go­rith­mus schön ver­an­schau­licht wer­den, al­ler­dings ist es deut­lich schwe­rer, den Über­blick bei der Durch­füh­rung eines Al­go­rith­mus zu be­hal­ten.

Vor­teil: Die Frosch­per­spek­ti­ve wird zu kei­nem Zeit­punkt ver­las­sen. Erst am Ende kehrt man zur Ge­samt­an­sicht des Gra­phen zu­rück und sieht das Er­geb­nis. Die dabei durch­ge­führ­ten Ak­tio­nen las­sen sich sehr leicht auch in einen Al­go­rith­mus über­set­zen. Die Ver­wen­dung einer ToDo-Liste ist eine prak­ti­ka­ble Um­set­zung vie­ler Al­go­rith­men.

Nach­teil: Das Er­ler­nen der Be­nut­zung des Tools darf nicht der Un­ter­richts­in­halt sein. Die kon­se­quen­te Be­schrän­kung auf die Frosch­per­spek­ti­ve er­schwert den Über­blick und könn­te da­durch man­chen Schü­le­rin­nen oder Schü­lern den Zu­gang zum Al­go­rith­mus er­schwe­ren.

 

Un­ter­richts­ver­lauf: Her­un­ter­la­den [odt][298 KB]

 

Wei­ter zu Er­ar­bei­tung des Al­go­rith­mus