Drumuri minime n graf Manualul profesorului Clasa a XI-a

- 1 -

Drumuri minime n graf Manualul profesorului Clasa a XI-a

- 2 -

Cuprins 1. Terminologie 2. Structur general

2.1. Obiective didactice 2.2. Coninut 2.3. Recomandri de structurare i predare

3. Obiecte de coninut - detaliere

3.1. M1.1 Algoritmul lui Dijkstra Prezentarea problemei 3.2. M1.2 Algoritmul lui Dijkstra Reprezentarea informaiilor 3.3. M1.3 Algoritmul lui Dijkstra Implementare 3.4. M1.4 Algoritmul lui Dijkstra Evaluare 3.5. M2.1 Algoritmul Roy-Floyd Prezentarea problemei 3.6. M2.2 Algoritmul Roy-Floyd Reprezentarea informaiilor 3.7. M2.3 Algoritmul Roy-Floyd Implementare 3.8. M2.4 Algoritmul Roy-Floyd Evaluare 3.9. M3.1 Algoritmul Belman-Ford Prezentarea problemei 3.10. M3.2 Algoritmul Belman-Ford Reprezentarea informaiilor 3.11. M3.3 Algoritmul Belman-Ford Implementare 3.12. M3.4 Algoritmul Belman-Ford Evaluare

4. Elemente de implementare a aplicaiei 5. Bibliografie

Drumuri minime n graf Manualul profesorului Clasa a XI-a

- 3 -

1. Terminologie Butoane definiie sunt amplasate totdeauna n partea din dreapta jos a ecranului i, atunci cnd sunt accesate, prezint ntr-o fereastr de detaliu, definiiile termenilor necesari momentului respectiv. Butoane care indic obiectivele leciei respective - - sunt amplasate totdeauna n partea din dreapta jos a ecranului. Prin apsarea lor, ntr-o fereastr detaliu se prezint obiectivele leciei. Butoane de control a animaiei - - prin apsarea butoanelor corespunztoare:

se execut animaia pas cu pas nainte

se execut animaia pas cu pas napoi

se ruleaz animaia n mod continuu

se face pauz n executarea animaiei

se oprete animaia

Buton care permite deschiderea/nchiderea barei de unelte atunci cnd este accesat deschide/nchide bara de unelte. Buton care permite deschiderea/nchiderea ferestrei de control a hrilor

atunci cnd este accesat deschide/nchide fereastra de control a hrilor.

Butoane cuprinse n bara de unelte care indic anumite aciuni care trebuie executate asupra hrii atunci cnd sunt accesate realizeaz operaia indicat. Butoane selectare item atunci cnd sunt accesate se realizeaz operaia de selectare i afiare a item-ului corespunztor din test. Butoane de indicare a corectitudinii rspunsului

rspuns corect

rspuns eronat

Ferestre detaliu sunt ferestre care ofer informaii suplimentare despre o anumit noiune. Asupra unei ferestre detaliu se poate face "drag_and_drop" acionnd asupra barei de titlu a ferestrei. Exemplu :

Drumuri minime n graf Manualul profesorului Clasa a XI-a

- 4 -

Ferestre de animaie sunt ferestre n care se prezint o animaie ce indic n mod sugestiv modul n care se desfoar algoritmul Exemplu :

Ferestre afiare graf asociat sunt ferestre n care la acionarea butonului corespunztor din bara de unelte este afiat graful asociat hrii respective. Exemplu :

Drumuri minime n graf Manualul profesorului Clasa a XI-a

- 5 -

Ferestre de control a hrilor fereastr care conine butoane care permit ncrcri de hri predefinite, respectiv salvri/ncrcri de hri construite on-line.

Butoane de selectare a modului de afiare al algoritmului atunci cnd sunt accesate realizeaz afiarea algoritmului n pseudocod sau n limbajul de programare indicat. Butoane pentru nchis ferestre detaliu sunt amplasate n colul dreapta sus a ferestrelor de detaliu iar acionarea lor duce la nchiderea ferestrei. Ferestre eroare sunt ferestre care ofer informaii despre ncercri de ncrcare a unor hri cu un numr de noduri nepermis.

Buton de informaii la acionarea lui se deschide o fereastr detaliu care conine informaii despre modul de utilizare a barei de unelte, precum i diferite avertismente sau atenionri. Buton legend la acionarea lui se deschide o fereastr detaliu care conine descrierea elementelor grafice utilizate la momentul respectiv i semnificaia lor.

Drumuri minime n graf Manualul profesorului Clasa a XI-a

- 6 -

Ferestre legend sunt ferestre care ofer informaii despre elementele grafice utilizate la momentul respectiv i semnificaia lor:

Drumuri minime n graf Manualul profesorului Clasa a XI-a

- 7 -

2. Structura general

n acest capitol sunt prezentate obiectivele didactice care pot fi atinse utiliznd acest material. n finalul prezentrii sunt incluse cteva recomandri privind unele moduri n care ar putea fi combinate aceste momente pentru a obine o lecie.

2.1. Obiective didactice

Obiectiv Detaliere Obiective de referin

R1 Analizarea modului de determinare a drumurilor minime n graf R2 Realizarea aplicaiilor utiliznd algoritmi specifici R3 Urmrirea etapelor de realizare a unei aplicaii

Obiective operaionale

OP1 Definirea corect a noiunilor de graf neorientat, noduri, muchii, OP2 Definirea corect a noiunilor de graf orientat, arce, drum, cost minim OP3 Descrierea unor situaii practice care s necesite determinarea unui

drum minim de la un punct fixat la alte puncte OP4 Identificarea semnificaiei sgeilor (verzi/roii) i rolul acestora pe

parcursul determinrii drumului e cost minim OP5 Modelarea cu ajutorul teoriei grafurilor a situaiei practice prezentate OP6 Alegerea reprezentrii adecvate a grafului n memoria calculatorului OP7 Descrierea structurilor de date necesare implementrii algoritmului OP8 Descrierea algoritmului Dijkstra OP9 Implementarea algoritmului lui Dijkstra ntr-un limbaj de programare OP10 Urmrirea execuiei pas cu pas a algoritmui lui Dijkstra OP11 Urmrirea valorilor variabilelor care intervin n desfurarea algoritmului

lui Dijkstra pe un exemplu OP12 Determinarea drumului de cost minim folosind vectorul tata OP13 Descrierea algoritmului Roy-Floyd OP14 Implementarea algoritmului lui Roy-Floyd ntr-un limbaj de programare OP15 Urmrirea execuiei pas cu pas a algoritmui lui Roy-Floyd OP16 Urmrirea valorilor variabilelor care intervin n desfurarea algoritmului

lui Roy-Floyd pe un exemplu OP17 Descrierea algoritmului Bellman-Ford OP18 Implementarea algoritmului lui Bellman-Ford ntr-un limbaj de

programare OP19 Urmrirea execuiei pas cu pas a algoritmui lui Bellman-Ford OP20 Urmrirea valorilor variabilelor care intervin n desfurarea algoritmului

lui Bellman-Ford pe un exemplu OP21 Determinarea complexitii timp a unui algoritm OP22 Dezvoltarea gndirii algoritmice, logice, flexibile, creatoare OP23 Dezvoltarea ateniei concentrate i spiritului de observaie

Drumuri minime n graf Manualul profesorului Clasa a XI-a

- 8 -

2.2 Coninut Se prezint lista obiectelor de coninut (notate cu M) i caracteristicile lor generale.

M1.1 Algoritmul Dijsktra prezentarea problemei Obiective didactice OP1, OP2, OP3, OP4, OP22, OP23 Timp de predare 20 min Tip de interaciune cu elevii

metode de comunicare oral: expunere, conversaie, algoritmizare, studiu de caz

metode de aciune: exerciiul, nvarea prin descoperire

procedee de instruire: explicaia n etapa de comunicare; nvarea prin descoperire dirijat, inductiv, experimental, exerciiul de consolidare

Descriere prezentarea problemei exemplificarea problemei pe o hart predefinit sau

construit pe loc construcia unor hri utiliznd bara de unelte urmrirea determinrii drumului minim de la punctul

de start la toate celelalte puncte de pe hart Cuvinte cheie hart

graf asociat graf neorientat, graf orientat muchie, arc cost, cost minim

M1.2 Algoritmul Dijsktra reprezentarea informaiilor Obiective didactice OP1, OP2, OP3, OP4, OP5, OP6, OP7, OP22, OP23 Timp de predare 30 min Tip de interaciune cu elevii

metode de comunicare oral: expunere, conversaie, studiu de caz

metode de aciune: exerciiul, nvarea prin descoperire

procedee de instruire: explicaia n etapa de comunicare; nvarea prin descoperire dirijat, inductiv, experimental, exerciiul de consolidare

Descriere prezentarea noiunii de graf asociat prezentarea noiunii de matrice a costurilor prezentarea grafului asociat unei hri prezentarea structurilor de date necesare

Cuvinte cheie graf asociat matricea costurilor

Drumuri minime n graf Manualul profesorului Clasa a XI-a

- 9 -

M1.3 Algoritmul Dijsktra implementare Obiective didactice OP1, OP2, OP3, OP4, OP7, OP8, OP9, OP10, OP11,

OP22, OP23 Timp de predare 50 min + 20 min Tip de interaciune cu elevii

metode de comunicare oral: expunere, conversaie, studiu de caz

metode de aciune: exerciiul, nvarea prin descoperire

procedee de instruire: explicaia n etapa de comunicare; nvarea prin descoperire dirijat, inductiv, experimental, exerciiul de consolidare

Descriere prezentarea algoritmului n limbaj natural prezentarea algoritmului n pseudocod/C/Pascal prezentarea evoluiei variabilelor de memorie prezentarea n paralel a execuiei programului i a

determinrii drumurilor de cost minim pe harta selectat sau pe graful asociat

determinarea complexitii algoritmului descrierea metodei de reconstituire a drumului

utiliznd vectorul tata Cuvinte cheie pseudocod

complexitate M1.4 Algoritmul Dijsktra evaluare Obiective didactice OP12, OP21, OP22, OP23 Timp de lucru 30 min Tip de interaciune cu elevii

evaluare n form scris prin intermediul calculatorului

Descriere test gril Cuvinte cheie hart

cost minim drum de cost minim matricea costurilor

Drumuri minime n graf Manualul profesorului Clasa a XI-a

- 10 -

M2.1 Algoritmul Roy Floyd prezentarea problemei Obiective didactice OP1, OP2, OP3, OP4, OP22, OP23 Timp de predare 20 min Tip de interaciune cu elevii

metode de comunicare oral: expunere, conversaie, algoritmizare, studiu de caz

metode de aciune: exerciiul, nvarea prin descoperire

procedee de instruire: explicaia n etapa de comunicare; nvarea prin descoperire dirijat, inductiv, experimental, exerciiul de consolidare

Descriere prezentarea problemei exemplificarea problemei pe o hart predefinit sau

construit pe loc construcia unor hri utiliznd bara de unelte urmrirea determinrii drumului minim de la punctul

de start la toate celelalte puncte de pe hart Cuvinte cheie hart

graf asociat graf neorientat graf orientat muchie arc cost cost minim

M2.2 Algoritmul Roy Floyd reprezentarea informaiilor Obiective didactice OP1, OP2, OP3, OP4, OP5, OP6, OP7, OP22, OP23 Timp de predare 30 min Tip de interaciune cu elevii

metode de comunicare oral: expunere, conversaie, studiu de caz

metode de aciune: exerciiul, nvarea prin descoperire

procedee de instruire: explicaia n etapa de comunicare; nvarea prin descoperire dirijat, inductiv, experimental, exerciiul de consolidare

Descriere prezentarea noiunii de graf asociat prezentarea noiunii de matrice a costurilor prezentarea grafului asociat unei hri prezentarea structurilor de date necesare

Cuvinte cheie graf asociat matricea costurilor

Drumuri minime n graf Manualul profesorului Clasa a XI-a

- 11 -

M2.3 Algoritmul Roy Floyd implementare Obiective didactice OP1, OP2, OP3, OP4, OP7, OP13, OP14, OP15, OP16,

OP22, OP23 Timp de predare 30 min Tip de interaciune cu elevii

metode de comunicare oral: expunere, conversaie, studiu de caz

metode de aciune: exerciiul, nvarea prin descoperire

procedee de instruire: explicaia n etapa de comunicare; nvarea prin descoperire dirijat, inductiv, experimental, exerciiul de consolidare

Descriere prezentarea algoritmului n limbaj natural prezentarea algoritmului n pseudocod/C/Pascal prezentarea evoluiei variabilelor de memorie prezentarea n paralel a execuiei programului i a

determinrii drumurilor de cost minim pe harta selectat sau pe graful asociat

determinarea complexitii algoritmului descrierea metodei de reconstituire a drumului

utiliznd vectorul tata Cuvinte cheie pseudocod

complexitate M2.4 Algoritmul Roy Floyd evaluare Obiective didactice OP12, OP21, OP22, OP23 Timp de lucru 20 min Tip de interaciune cu elevii

evaluare n form scris prin intermediul calculatorului

Descriere test gril Cuvinte cheie hart

cost minim drum de cost minim matricea costurilor

Drumuri minime n graf Manualul profesorului Clasa a XI-a

- 12 -

M3.1 Algoritmul Belmann Ford prezentarea problemei Obiective didactice OP1, OP2, OP3, OP4, OP22, OP23 Timp de predare 20 min Tip de interaciune cu elevii

metode de comunicare oral: expunere, conversaie, algoritmizare, studiu de caz

metode de aciune: exerciiul, nvarea prin descoperire

procedee de instruire: explicaia n etapa de comunicare; nvarea prin descoperire dirijat, inductiv, experimental, exerciiul de consolidare

Descriere prezentarea problemei exemplificarea problemei pe o hart predefinit sau

construit pe loc construcia unor hri utiliznd bara de unelte urmrirea determinrii drumului minim de la punctul

de start la toate celelalte puncte de pe hart Cuvinte cheie hart

graf asociat graf neorientat graf orientat muchie arc cost cost minim

M3.2 Algoritmul Belmann Ford reprezentarea informaiilor Obiective didactice OP1, OP2, OP3, OP4, OP5, OP6, OP7, OP22, OP23 Timp de predare 30 min Tip de interaciune cu elevii

metode de comunicare oral: expunere, conversaie, studiu de caz

metode de aciune: exerciiul, nvarea prin descoperire

procedee de instruire: explicaia n etapa de comunicare; nvarea prin descoperire dirijat, inductiv, experimental, exerciiul de consolidare

Descriere prezentarea noiunii de graf asociat prezentarea noiunii de matrice a costurilor prezentarea grafului asociat unei hri prezentarea structurilor de date necesare

Cuvinte cheie graf asociat matricea costurilor

Drumuri minime n graf Manualul profesorului Clasa a XI-a

- 13 -

M3.3 Algoritmul Belmann Ford implementare Obiective didactice OP1, OP2, OP3, OP4, OP7, OP17, OP18, OP19, OP20,

OP22, OP23 Timp de predare 30 min Tip de interaciune cu elevii

metode de comunicare oral: expunere, conversaie, studiu de caz

metode de aciune: exerciiul, nvarea prin descoperire

procedee de instruire: explicaia n etapa de comunicare; nvarea prin descoperire dirijat, inductiv, experimental, exerciiul de consolidare

Descriere prezentarea algoritmului n limbaj natural prezentarea algoritmului n pseudocod/C/Pascal prezentarea evoluiei variabilelor de memorie prezentarea n paralel a execuiei programului i a

determinrii drumurilor de cost minim pe harta selectat sau pe graful asociat

determinarea complexitii algoritmului descrierea metodei de reconstituire a drumului

utiliznd vectorul tata Cuvinte cheie pseudocod

complexitate M3.4 Algoritmul Belmann Ford evaluare Obiective didactice OP12, OP21, OP22, OP23 Timp de lucru 20 min Tip de interaciune cu elevii

evaluare n form scris prin intermediul calculatorului

Descriere test gril Cuvinte cheie hart

cost minim drum de cost minim matricea costurilor

Drumuri minime n graf Manualul profesorului Clasa a XI-a

- 14 -

2.3. Recomandri de structurare i predare

Planul unitii de nvare 1 Timp: 1 or

Obiect de coninut Timp (min) M1,1 M1,2

20 30

Planul unitii de nvare 2 Timp: 1 or

Obiect de coninut Timp (min) M1,3 50

Planul unitii de nvare 3 Timp: 1 or

Obiect de coninut Timp (min) M1,3 M1,4

20 30

Planul unitii de nvare 4 Timp: 1 or

Obiect de coninut Timp (min) M2,1 M2,2

20 30

Planul unitii de nvare 5 Timp: 1 or

Obiect de coninut Timp (min) M2,3 M2,4

30 20

Planul unitii de nvare 6 Timp: 1 or

Obiect de coninut Timp (min) M3,1 M3,2

20 30

Planul unitii de nvare 7 Timp: 1 or

Obiect de coninut Timp (min) M3,3 M3,4

30 20

Drumuri minime n graf Manualul profesorului Clasa a XI-a

- 15 -

3. Obiecte de coninut - detaliere n continuare vom prezenta n detaliu modul de utilizare a elementelor din ferestrele leciei (navigare, elemente specifice, funcionarea aplicaiilor, etc.). Subliniem c navigarea elementar se face cu ajutorul butoanelor descrise n Capitolul 1 Terminologie, al acestui manual. Nu ne vom referi la acestea dect spicuitiv. 3.1. Algoritmul Dijsktra prezentarea problemei n acest obiect de coninut este prezentat o problem practic care necesit utilizarea unui algoritm de determinare a drumurilor de cost minim. Tot aici este posibil descrierea acestei situaii pe o hart i determinarea drumurilor de cost minim de la un aeroport la toate celelalte.

Ecranul este mprit n cinci zone :

n stnga sus zona unde se construiete/ncarc o hart n dreapta sus zona unde este descris situaia practic ntre cele dou zone se gsete bara de unelte prin intermediul creia

poate fi editat orice hart numrul maxim permis de aeroporturi este 10

Drumuri minime n graf Manualul profesorului Clasa a XI-a

- 16 -

n stnga jos se gsete fereastra n care sunt afiate mesaje cu privire la aciunile care au fost executate prin intermediul barei de unelte

n dreapta jos se gsete fereastra care conine sarcinile de lucru Pe lng aceste zone n fereastr mai apar cteva butoane i controale:

Obiectul de coninut cuprinde descrierea problemei practice n limbaj natural, precum i sarcinile de lucru. Tot aici sunt date informaii despre modalitile de utilizare a editorului de hri. Aceste informaii se obin acionnd butonul . La acionarea lui (din oricare din poziiile unde apare) se deschide o fereastr detaliu care conine help-ul corespunztor:

Pentru a crea o hart proprie, operaiile indicate trebuie executate ntr-o anumit ordine i trebuie finalizate. Astfel, prima operaie care se face este operaia de adugare de aeroporturi (maxim 10) pe hart. Dup ce aeroporturile au fost adugate se pot aduga drumuri ntre diferite aeroporturi. Pentru aceasta se

controlul animaiei cele cinci butoane au respectiv efectul: execuie, pauz, oprire, nainte un pas, napoi un pas

care acionat deschide o fereastr detaliu care conine informai cu privire la utilizarea editorului de hri

la acionarea acestui buton se deschide fereastra care permite accesul la bibliotecile de hri

la acionarea acestui buton se deschide fereastra detaliu pentru descrierea obiectivelor

Drumuri minime n graf Manualul profesorului Clasa a XI-a

- 17 -

selecteaz din bara de unelte operaia corespunztoare apoi, pe hart, se selecteaz (click) cele dou aeroporturi ntre care se dorete adugarea unui drum primul aeroport selectat este aeroportul de plecare (sursa). n momentul n care a fost selectat i al doilea aeroport (de sosire, destinaia), ntre cele dou aeroporturi apare o sgeat (de la surs la destinaie) care poate fi modificat executnd operaia drag&drop cu mouse-ul fr nici un buton apsat. n momentul n care se execut un nou click, lng sgeat apare o caset text n care se introduce distana dintre cele dou aeroporturi (0

Drumuri minime n graf Manualul profesorului Clasa a XI-a

- 18 -

Butonul permite executarea operaiilor de gestiune a hrilor: ncrcarea unei hri dintr-o bibliotec de hri predefinite oferite de soft salvarea unei hri construite de utilizator ncrcarea unei hri construite ntr-un moment anterior eliminarea unei hri din memorie

Dup salvarea unei hri n memorie aceasta devine accesibil n orice moment al derulrii aplicaiei. Acionarea butonului permite apariia unei ferestre detaliu n care sunt indicate obiectivele pe care trebuie s le ating elevul dup parcurgerea acestui obiect de coninut.

Drumuri minime n graf Manualul profesorului Clasa a XI-a

- 19 -

3.2. Algoritmul Dijsktra reprezentarea informaiilor n acest obiect de coninut sunt prezentate noiunile necesare implementrii algoritmului: datele implicate, organizarea lor, semnificaia notaiilor folosite. Fereastra principal este organizat astfel:

n stnga sus zona unde se construiete/ncarc o hart i unde apare

graful asociat hrii respective n dreapta sus zona unde sunt descrise noiunile teoretice necesare

asocierii unui graf precum i modalitatea n care se realizeaz aceasta; tot aici, la acionarea butonului se vor afia datele nece-sare i modalitile de organizare a lor

n stnga jos se gsete fereastra n care sunt afiate mesaje cu privire la aciunile care au fost executate prin intermediul barei de unelte

n cadrul acestui obiect de coninut bara de unelte nu mai este prezent pe ecran tot timpul; ea poate fi adus aici prin acionarea butonului . Pentru derularea fireasc a obiectului de coninut, n primul rnd se ncarc una dintre hrile din bibliotec sau dintre cele salvate la momentul anterior. Aceasta se realizeaz utiliznd butonul . Evident, i n cadrul acestui obiect de coninut poate fi construit o hart utiliznd facilitile oferite de bara de unelte. Dup ncrcarea/construirea hrii, prin acionarea butonului n fereas-

Drumuri minime n graf Manualul profesorului Clasa a XI-a

- 20 -

tra din dreapta apar noiunile teoretice cu privire la modalitatea de a asocia hrii respective un graf. Acionarea butonului produce apariia n aceai fereastr a descrierii datelor i organizrii lor n vederea prelucrrii:

Acionarea butonului produce apariia unei ferestre detaliu n care este descris modul n care sunt iniializate elementele matricii costurilor precum i matricea costurilor ataat grafului asociat hrii resective.

Deoarece n acest obiect de coninut apar noiuni utilizate n teoria grafurilor, am considerat util ca anumite elemente utilizate s fie reamintite elevilor. Acest lucru este realizat prin intermediul noului buton care apare . Acionarea lui produce apariia unei ferestre detaliu n care sunt reamintite noiunile necesare:

graf neorientat, vrfuri, munchii graf orientat, arce drum n graf, drum elementar n graf

Drumuri minime n graf Manualul profesorului Clasa a XI-a

- 21 -

Ca la fiecare moment de coninut i aici exist butonul la acionarea cruia, ntr-o fereastr detaliu, sunt afiate obiectivele pe care trebuie s le ating elevul dup parcurgerea acestui obiect de coninut.

Buton de informaii care conine informaii despre modul de utilizare a barei de unelte, precum i diferite avertismente sau atenionri, este n continuare disponibil.

Drumuri minime n graf Manualul profesorului Clasa a XI-a

- 22 -

3.3. Algoritmul Dijsktra implementare n acest obiect de coninut este prezentat implementarea algoritmului lui Dijkstra n pseudocol, C i Pascal. Fereastra principal este organizat astfel:

n stnga sus zona unde se construiete/ncarc o hart i unde apare, la

cerere, graful asociat hrii respective n dreapta sus zona unde este descris implementarea algoritmului n C,

pseudocod sau Pascal sub aceast zon se gsesc trei butoane

care permit selectarea modalitii de afiare a implementrii algoritmului n dreapta jos se gsete fereastra n care sunt afiate mesaje cu privire la

aciunile care au fost executate prin intermediul barei de unelte n partea din stnga jos a ferestrei principale se afl fereastra n care vor fi

afiate valorile tuturor variabilelor care apar n implementarea algoritmului sub zona care conine harta se gsesc butoanele pentru controlul animaiei

descrise la nceput lng controul animaiei apare butonul care permite activarea /

dezactivarea barei de unelte Butonul permite, aa cum am artat activarea ferestrei pentru lucrul cu hri.

Drumuri minime n graf Manualul profesorului Clasa a XI-a

- 23 -

Pe lng aceste elemente fereastra mai conine trei butoane care permit deschiderea unor ferestre detaliu care conin:

Dup construirea/ncrcarea unei hri i stabilirea aeroportului de plecare (start), operaii permise fie cu ajutorul barei de unelte, fie prin intermediul ferestrei de control a hrilor, se poate trece la vizualizarea algoritmului n una dintre cele trei modaliti permise (C/pseudocod/Pascal). Pentru a nelege ct mai bine modul n care a fost implementat algoritmul, obiectul de coninut permite vizualizarea separat a zonelor implementrii alese. Pentru aceasta este suficient s fie poziionat cursorul mouse-ului n fereastra care descrie codul. n acest mod pot fi puse n eviden cele patru zone ale codului:

declaraiile de variabile iniializarea variabilelor cutarea distanei minime actualizarea distanelor

prin colorarea n albastru a zonei respective:

Urmtorul moment n desfurarea leciei este urmrirea desfurrii algoritmului cu ajutorul animaiei lansate prin intermediul butoanelor din controlul animaiei.

Descrierea n limbaj natural a algoritmului, precum i semificaia colorrii n rou/verde a arcelor n timpul desfurrii animaiei: arcele roii au fost selectate ca fcnd parte din drumul minim, cele verzi vor participa la calcul la pasul urmtor.

Descrierea n limbaj natural a modului de reconstituire a drumului de cost minim n vederea afirii acestuia. Sunt date n pseudocod att implementarea recursiv ct i implementarea nerecursiv a algoritmului de reconstituire a drumului.

Descrierea calculului ordinului de complexitate a algoritmului lui Dijkstra

Drumuri minime n graf Manualul profesorului Clasa a XI-a

- 24 -

Animaia poate fi lansat fie prin acionarea butonului care declaeaz execuia algoritmului, fie prin acionarea butonului care permite execuia "pas cu pas" a algoritmului. n momentul lansrii n execuie n zona destinat variabilelor apar valorile variabilelor (neiniializate), apoi, pe msura desfurrii algoritmului, aceste valori sunt actualizate n fiecare moment:

n acelai timp n zona codului, o band portocalie indic n fiecare moment instruciunea care este executat:

n acelai timp, pe hart sau pe graful asociat hrii (ca n imaginea anterioar) sunt indicate prin culori arcele care particip n acel moment la calcule prin culoarea roie sunt indicate arcele deja selectate pentru un drum minim, iar prin culoarea verde arce care sunt luate n calcul pentru urmtoarele calcule. Oricare dintre butoanele descrise mai sus sunt accesibile n orice moment al animaiei, ns acionarea unor instrumente din bara de butoane poate duce la resetarea animaiei. Astfel, de exemplu, dac n timpul derulrii animaiei se

Drumuri minime n graf Manualul profesorului Clasa a XI-a

- 25 -

dorete adugarea unui nou aeroport, operaia duce la oprirea animaiei, doarece operaia dorit produce un alt graf. Ca la fiecare moment de coninut i aici exist butonul la acionarea cruia, ntr-o fereastr detaliu, sunt afiate obiectivele pe care trebuie s le ating elevul dup parcurgerea acestui obiect de coninut.

Buton de informaii care conine informaii despre modul de utilizare a barei de unelte, precum i diferite avertismente sau atenionri, este n continuare disponibil.

Drumuri minime n graf Manualul profesorului Clasa a XI-a

- 26 -

3.4. Algoritmul Dijsktra evaluare Acest obiect de coninut const dintr-un set de exerciii recapitulative de diferite tipuri, numerotate de la 1 la 9 de forma . Exerciiile 1, 3, 4, 5, 7 sunt de tip interactiv, solicitnd completarea unor cmpuri cu valori care se cer determinate pe baza informaiilor furnizate:

exerciiul 1 cere determinarea drumului minim pe baza informaiilor furnizate de vectorul tata

exerciiul 3 cere determinarea matricii costurilor pe baza unei hri exerciiul 4 cere determinarea a dou drumuri distincte de cost minim de la

vrful de start la unul din vrfuri exerciiul 5 indic o situaie pe hart din timpul desfurrii algoritmului i

cere determinarea vectorului distanelor d dup urmtoarea selecie exerciiul 7 indic o situaie pe hart din timpul desfurrii algoritmului i

cere determinarea urmtorului vrf care va fi selectat Exerciiile 2, 6, i 8 sunt de tip test gril cu rspunsuri de tip complement simplu, adic doar o variant de rspuns corect. Exerciiile se selecteaz cu ajutorul mouse-ului.

Dup rezolvarea celor opt exerciii, pentru a determina corectitudinea rezolvrii se acceseaz butonul . n urma evalurii n stnga fiecrui exerciiu

Drumuri minime n graf Manualul profesorului Clasa a XI-a

- 27 -

apare semnul dac exerciiul a fost corect rezolvat, respectiv semnul dac exerciiul nu a fost rezolvat corect. n cazul n care exerciiul nu a fost rezolvat corect, la accesarea butonului care indic exerciiul incorect, n fereastra exerci-iului apare i soluia corect.

Dup terminarea evalurii, pentru a se genera un nou test se acceseaz butonul . Pentru fiecare exerciiu exist un numr de posibiliti de selectare n mod aleator, astfel nct probabilitatea de a selecta acelai test de evaluare format din nou exerciii pentru dou calculatoare alturate este extrem de mic. Ambele butoane ( i ) pot fi accesate n orice moment al evalurii, ns dup accesarea butonului de evaluare nu mai este permis accesul la nici unul din cele nou exerciii i trebuie generat un nou test. i n cazul acestui obiect de coninut exist butonul de informaii la acce-sarea cruia ntr-o fereastr detaliu sunt date informaii cu privire la modul de lucru n timpul rezolvrii celor opt exerciii de evaluare.

Drumuri minime n graf Manualul profesorului Clasa a XI-a

- 28 -

3.5. Algoritmul Roy-Floyd prezentarea problemei 3.6. Algoritmul Roy-Floyd reprezentarea informaiilor 3.7. Algoritmul Roy-Floyd implementare 3.8. Algoritmul Roy-Floyd evaluare 3.9. Algoritmul Belmann-Ford prezentarea problemei 3.10. Algoritmul Belmann-Ford reprezentarea informaiilor 3.11. Algoritmul Belmann-Ford implementare 3.12. Algoritmul Belmann-Ford evaluare Pentru obiectele de coninut 3.5. 3.8. elementele prezentate n obiectele de coninut 3.1. 3.4. rmn valabile, singura deosebire fiind algoritmul prezentat, i anume algoritmul Roy-Floyd. n mod analog, pentru obiectele de coninut 3.9. 3.12. elementele prezentate n obiectele de coninut 3.1. 3.4. rmn valabile, algoritmul prezentat fiind de data aceasta algoritmul Belmann-Ford.

Drumuri minime n graf Manualul profesorului Clasa a XI-a

- 29 -

4. Elemente de implementare a aplicaiei Tehnologiile utilizate n acest proiect sunt:

HTML JavaScript Flash XML ActionScript Shared Objects

ntreaga parte de interactivitate a fost realizat utiliznd facilitile puse la dispoziie de platforma Flash Player 7. Fiecare moment al leciei este creat ca fiind un fiier Flash distinct iar pentru biblioteca de hri am folosit un fiier XML extern, al crui format este uor de neles i editat, fr a fi necesar un editor specializat. Pentru parcurgerea pas cu pas a oricrui algoritm prezentat am folosit un vector de micri, pliate pe algoritm, ce simuleaz modul n care procedeaz mediul n care se ruleaz programul. Astfel, unui pas X i corespunde o aciune n vectorul de micri, aciune ce poate fi o modificare a unei variabile sau o mutare simpl pe cod. Pentru a obine desfurarea cursiv a animaiei pe cod a fost suficient crearea unei funcii care este apelat din secund n secund i care incrementeaz numrul pasului ce trebuie afiat. Practic, am implementat fiecare algoritm n ActionScript. Pentru operaii ce au necesitat stocarea unor date pe harddisk i utilizarea lor n mai multe momente s-a folosit tehnologia Shared Objects. Pentru salvarea hrilor n memorie pentru a putea fi folosite i n alte momente am folosit tehnologia Shared Objects n Flash. Fiecare hart este transformat n graf iar fiecare graf este transformat ntr-un obiect care, dup ce este automat serializat, este scris ntr-un fiier pe harddisk, fiind accesibil i la o alt rulare a aplicaiei. Pentru ncrcarea hrilor i transpunerea lor pe hart am inversat procesul. Astfel, dintr-un fiier de pe harddisk, prin deserializare automat, se extrage un obiect care este transformat ntr-un graf. n cazul n care graful rezultat este compatibil cu momentul (are numrul de vrfuri mai mic sau egal cu numrul maxim de vrfuri pentru momentul respectiv i costurile din graf corespund costurilor acceptate de moment) acesta este pliat pe hart.

Drumuri minime n graf Manualul profesorului Clasa a XI-a

- 30 -

4. Bibliografie

Cormen Th., Leiserson Ch., Rivest R., Introduction to Algorithms, MIT, 1990

Cerchez Em., Informatica, Culegere de probleme pentru liceu, Editura Polirom, Iai, 2002

Livoschi L., Georgescu H., Bazele informaticii. Algoritmi. Elaborare i complexitate. Bucureti, 1985

Lica D., Boriga R., Popescu-Anastasiu D., .a., Fundamentele programrii (Culegere de probleme pentru clasele IX-XI). Editura L&S Infomat, Bucureti, 2003