Manualul profesorului

Grafuri orientate - Manualul profesorului Clasa a XI-a

- 2 -

Cuprins:

1. Terminologie 2. Structură generală

2.1. Obiective didactice 2.2. Conţinut 2.3. Recomandări de structurare şi predare

3. Obiecte de conţinut - detaliere

3.1. M1 – Noţiuni introductive 3.2. M2 – Lanţ. Drum. Circuit. 3.3. M3 – Graf parţial. Subgraf. 3.4. M4 – Graf orientat complet 3.5. M5 – Graful turneu 3.6. M6 – Test grilã pentru evaluarea cunoştinţelor (1) 3.7. M7 – Matrice asociate grafurilor orientate 3.8. M8 – Algoritmul Roy – Warshall 3.9. M9 – Problema celebrităţii 3.10. M10 – Test grilã pentru evaluarea cunoştinţelor (2) 3.11. M11 – Graf conex. Graf tare conex. Componente conexe 3.12. M12 – Test grilã pentru evaluarea cunoştinţelor (3)

4. Bibliografie


- 3 -

1. Terminologie Butoane instructaj – – sunt amplasate în partea din dreapta-sus a ecranului şi, atunci când sunt accesate, prezintă pas cu pas, într-o fereastră de detaliu, instrucţiuni despre folosirea unei aplicaţii. Butoane demonstraţie – – sunt amplasate în dreptul enunţurilor “Teoremă” sau în dreptul unui rezultat, şi îi oferă utilizatorului, într-o fereastră de detaliu, demonstraţia teoremei, respectiv modul în care s-a ajuns la acel rezultat. Butoane de reiniţializare a animaţiei / aplicaţiei - - Prin apăsarea lor se reiniţializează animaţia, respectiv aplicaţia. Butoane de validare Apar în aplicaţii care necesită verificarea soluţiei. Butoane de generare aleatoare - - Genereză în mod aleator soluţii valide pentru problemele propuse. Texte de reper – – reprezintă simboluri grafice prezente intr-un text care, atunci când sunt accesate, prezintă ferestre de ajutor, in care se detaliază o anumită noţiune. Ferestre detaliu – sunt ferestre care oferă informaţii suplimentare despre o anumită noţiune. Exemplu :


- 4 -

2. Structura generală În acest capitol sunt prezentate obiectivele didactice care pot fi atinse utilizând acest material. În finalul prezentării sunt incluse câteva recomandări privind unele moduri în care ar putea fi combinate aceste momente pentru a obţine o lecţie. 2.1. Obiective didactice Obiectiv Detaliere Obiective de referinţă R1 Identificarea problemelor care pot fi rezolvate cu ajutorul

teoriei grafurilor R2 Însuşirea şi aprofundarea noţiunilor teoretice ale teoriei

grafurilor R3 Urmărirea etapelor de realizare a unei aplicaţii prin metode

caracteristice teoriei grafurilor Obiective operaţionale OP1 Însuşirea în mod corect a noţiunilor învăţate : graf orientat,

gradul interior şi gradul exterior al unui nod, mulţimea succesorilor / predecesorilor unui nod, mulţimea arcelor care ies / intră dintr-un / într-un nod

OP2 Evidenţierea corectă a noţiunilor de lanţ, drum, circuit într-un graf orientat

OP3 Identificarea şi construirea de grafuri parţiale şi subgrafuri ale grafurilor orientate

OP4 Însuseaşirea noţiunii de graf complet OP5 Construiască corectă a grafurilor complete, cu un număr dat de

noduri OP6 Exemplificarea noţiunilor învăţate folosind graful special - graful

turneu. OP7 Evidenţierea matricelor asociate grafurilor orientate şi

formularea de observaţii pe marginea lor OP8 Însuşirea algoritmului Roy-Warshall pentru implementarea lui

ulterioară în aplicaţii OP9 Utilizarea proprietăţilor matricei de adiacanţă şi a matricei

drumurilor în rezolvarea aplicaţiilor OP10 Exemplificarea noţiunilor de graf conex, componentă conexă,

graf tare conex şi componentă tare conexă OP11 Analiza asemănărilor şi deosebirilor care apar între noţiunile de

graf conex - graf tare conex, componenta conexă – componenta tare conexă

OP12 Selectarea variantelor corecte şi să argumentarea alegerii unei anumite formule în rezolvarea aplicaţiilor

OP13 Analiza corectă a fiecărei probleme şi să dezvoltarea gândirii algoritmice, capacităţii de generalizare şi problematizare.


- 5 -

2.2 Conţinut Se prezintă lista obiectelor de conţinut (notate cu M) şi caracteristicile lor generale.

M2 – Lanţ, Drum, Circuit Obiective didactice OP2, OP13 Timp de predare 20 min Tip de interacţiune cu elevii

• metode de comunicare orală : expunere, conversaţie, studiu de caz

• metode de acţiune: exerciţiul, învăţarea prin descoperire

• proceedee de instruire: explicatia în etapa de comunicare; învăţarea prin descoperire dirijată, inductivă, experimentală; conversaţia de consolidare în etapa de fixare a cunoştinţelor

Descriere • descrierea noţiunilor de lanţ, drum, circuit într-un graf orientat

• evidenţierea deosebirilor existente între aceste noţiuni

Cuvinte cheie drum, lanţ, circuit

M1 – Noţiuni introductive Obiective didactice OP1, OP13 Timp de predare 15 min Tip de interacţiune cu elevii



• proceedee de instruire: explicatia în etapa de comunicare; învăţarea prin descoperire dirijată, inductivă, experimentală; conversaţia de consolidare în etapa de fixare a cunoştintelor

Descriere • descrierea prin exemple a noţiunilor de graf orientat, gradul unui nod (interior, exterior), mulţinea succesorilor unui nod, mulţinea predecesorilor unui nod, mulţimea arcelor

Cuvinte cheie graf orientat, gradul unui nod


- 6 -

M3 – Graf parţial, subgraf Obiective didactice OP3, OP13 Timp de predare 15 min Tip de interacţiune cu elevii

• metode de comunicare orală : expunere, conversaţie, brainstorming


• proceedee de instruire: conversaţia de consolidare, exerciţiul de consolidare

Descriere • prezentarea noţiunilor de graf parţial şi subgraf

• analizarea modalităţilor de obţinere a grafurilor parţiale şi a subgrafurilor pornind de la un graf dat

Cuvinte cheie graf parţial, subgraf

M4 – Graf orientat complet Obiective didactice OP4, OP5, OP13 Timp de predare 20 min Tip de interacţiune cu elevii



• proceedee de instruire: conversaţia de consolidare, învăţarea prin descoperire dirijată, inductivă, experimentală, exerciţiul de consolidare

Descriere • descrierea noţiunii de graf complet • construirea tuturor grafurilor complete cu

un număr dat de noduri

Cuvinte cheie graf orientat complet

M5 – Aplicaţia (1) – Graful turneu Obiective didactice OP6, OP13 Timp de predare 20 min Tip de interacţiune cu elevii

• metode de comunicare orală : expunere, conversaţie, problematizare, studiu de caz


• proceedee de instruire: conversaţia de consolidare, problematizarea prin crearea de situaţii problemă, exerciţiul de consolidare

Descriere • determinarea unui drum elementar care trece prin toate nodurile grafului într-un graf turneu

Cuvinte cheie graf turneu, drum elementar


- 7 -

M6 – Test grilă de evaluare a cunoştinţelor (1) Obiective didactice OP3, OP6, OP12 Timp de predare 10 min Tip de interacţiune cu elevii

• evaluare în formă scrisă prin intermediul calculatorului

Descriere • test grilă cu itemi de tip asociere (pereche)

Cuvinte cheie graf parţial, graf turneu

M7 – Matrice asociate grafurilor orientate Obiective didactice OP7, OP13 Timp de predare 25 min Tip de interacţiune cu elevii

• metode de comunicare orală : expunere, conversaţie



Descriere • descrierea noţiunilor de matricea de adiacenţă, matricea vârfuri arce, matricea drumurilor

• construirea acestor matrice Cuvinte cheie matricea de adiacenţă, matricea vârfuri-arce,

matricea drumurilor M8 – Algoritmul Roy - Warshall Obiective didactice OP8, OP13 Timp de predare 25 min Tip de interacţiune cu elevii

• metode de comunicare orală : expunere, conversaţie, algoritmizarea


• proceedee de instruire: algoritmizarea prin determinarea paşilor secvenţei Roy-Warshall, exerciţiul de consolidare

Descriere • descrierea algoritmului Roy-Warshall pentru determinarea matricei drumurilor

Cuvinte cheie algoritmul Roy-Warshall


- 8 -

M9 – Aplicaţie (2) - Problema celebritãţii Obiective didactice OP9, OP13 Timp de predare 20 min Tip de interacţiune cu elevii




Descriere • prezentarea problemei de determinare a persoanei celebre dintr-un grup

Cuvinte cheie matricea de adiacenţă

M10 – Test grilã pentru evaluarea cunoştinţelor (2) Obiective didactice OP4, OP7, OP12 Timp de predare 10 min Tip de interacţiune cu elevii


Descriere • test grilă cu itemi de tip asociere (pereche) Cuvinte cheie graf complet, matricea de adiacentă, matricea

drumurilor M11 – Graf conex. Graf tare conex. Componente conexe Obiective didactice OP10, OP11 Timp de predare 15 min Tip de interacţiune cu elevii




Descriere • descrierea noţiunilor de graf conex, graf tare conex

• determinarea componentelor conexe si a componentelor tare conexe;

Cuvinte cheie graf conex, graf tare conex, componentă conexă, componentă tare conexă

M12 – Test grilã pentru evaluarea cunoştinţelor (3) Obiective didactice OP10, Op11, OP12, OP13 Timp de predare 10 min Tip de interacţiune cu elevii


Descriere • test grilă cu itemi de tip asociere (pereche) Cuvinte cheie graf conex, graf tare conex, componentă tare

conxă


- 9 -

2.2. Recomandări de structurare şi predare

Plan de lecţie 1 Timp: 1 oră

Obiect de conţinut Timp (min)

M1 15 M2 20 M3 15



M4 20 M5 20 M6 10



M7 25 M8 25



M9 20 + implementarea algoritmului

M10 10



M7 25 M11 15 M12 10


- 10 -

3. Obiecte de coţinut - detaliere În continuare vom prezenta în detaliu modul de utilizare a elementelor din ferestrele lecţiei. (navigare, elemente specifice, funcţionarea aplicaţiilor, etc.). Subliniem că navigarea elementară se face cu ajutorul butoanelor descrise în Cap. 1 – Terminologie, al acestui manual. Nu ne vom referi la acestea decât spicuitiv. 3.1. Noţiuni introductive În acest obiect de conţinut sunt prezentate noţiunile introductive legate de noţiunea de graf orientat. De asemenea, este prezentat modul în care se poate compune un graf orientat plecând de la o serie de elemente între care se stabilesc relaţii.

Pentru a trasa un arc în graf apăsaţi cu mouse-ul mai întâi pe elementul iniţial şi apoi pe cel final.

Elemente între care se

stabilesc relaţii

Graful orientat obţinut

Mulţimea nodurilor

Mulţimea arcelor


- 11 -

Pentru a adăuga elemente apăsaţi pe butonul . Pentru a şterge ultimul element adăugat apăsaţi pe butonul . Prin apăsare pe butonul se activează modul de ştergere a arcelor dintre noduri. Butonul devine . În acest mod se poate şterge orice arc, prin simpla apăsare pe el. În timp ce se definesc legăturile între elemente se desenează şi graful asociat corespunzător şi se afişează mulţimile nodurilor şi a arcelor. În partea dreaptă se pot testa noţiunile teoretice explicate. Trageţi cu mouse-ul de una din literele ce semnifică noduri în graf şi aşezaţi-o în oricare din căsuţele albe pentru a vizualiza rezultatul corespunzător.

Litere care semnifică noduri

Rezultat

Noţiune teoretic

ă

Căsuţă albă


- 12 -

3.2. Lanţ. Drum. Circuit. Fiecare dintre cele trei noţiuni este prezentată separat. Selecţia uneia dintre noţiuni se face apăsând pe butonul corespunzător: Prin apăsare pe butonul se activează modul de ştergere a arcelor dintre noduri. Butonul devine . În acest mod se poate şterge orice arc, prin simpla apăsare pe el. Lanţ

Enunţul problemei sugerează faptul că trebuie sã generaţi un lanţ. Pentru a face acest lucru, trebuie să urmaţi următorii paşi:

• selectaţi nodul iniţial, apăsând pe una dintre clădirile marcate de la A la K. Acesta va fi marcat automat drept nodul curent, prin colorarea cu roşu a literei

• selectaţi unul din arcele ce au la una dintre extremităţi chiar nodul iniţial de la pasul precedent. Dacã arcul selectat este valid, va fi acum marcat drept nodul curent cealaltă extremitate a arcului

• atunci când sunteţi mulţumit de lanţul generat, apăsaţi butonul de validare


- 13 -

Drum

Enunţul problemei sugerează faptul că trebuie sã generaţi un lanţ. Pentru a face acest lucru, trebuie să urmaţi următorii paşi:

• enunţul problemei sugereazã faptul că trebuie sã generaţi un drum. Pentru a face acest lucru, trebuie să urmaţi următorii paşi

• selectaţi unul din nodurile care sunt legate printr-un arc cu nodul de la pasul anterior. Dacã nodul selectat este valid, acesta va fi marcat drept nodul curent


Circuit

Enunţul problemei sugereazã faptul cã trebuie sã generaţi un circuit. Pentru a face acest lucru, trebuie să urmaţi următorii paşi:


- 14 -

• selectaţi nodul iniţial, apăsând pe una dintre clădirile marcate de la A la K. Acesta va fi marcat automat drept nodul curent, prin colorarea cu roşu a literei

• selectaţi unul din nodurile care sunt legate printr-un arc cu nodul de la pasul anterior. Dacă nodul selectat este valid, acesta va fi marcat drept nodul curent


3.3. Graf parţial. Subgraf. Cele două noţiuni sunt prezentate separat. Selecţia uneia dintre ele se face apăsând pe butonul corespunzător: Graf parţial Obţinerea unui graf parţial se face prin ştergerea unuia sau mai multor arce ale grafului iniţial.

Selectarea arcului care urmeazã a fi şters se face prin poziţionarea mouse-ului deasupra sa, moment în care arcul respectiv devine de culoare roşie. Ştergerea propriu-zisă se face apăsând pe arcul selectat.


- 15 -

Subgraf Obţinerea unui subgraf se face prin ştergerea unuia sau mai multor noduri ale grafului iniţial.

Selectarea nodului care urmeazã a fi şters se face prin poziţionarea mouse-ului deasupra sa, moment în care nodul respectiv devine de culoare roşie. Ştergerea propriu-zisă se face apăsând pe nodul selectat. 3.4. Graf complet În acest obiect de conţinut este prezentată noţiunea de graf complet. Se urmăreşte găsirea tuturor grafurilor complete ce se pot forma cu trei noduri.

Zona de lucru Zona de salvare a soluţiilor

Butoane de parcurgere a soluţiilor


- 16 -

Pentru a trasa un arc în graf apăsaţi cu mouse-ul mai întâi pe nodul iniţial şi apoi pe nodul final. Pentru a şterge un arc al grafului, se apasă pe nodul iniţial şi apoi pe cel final. Dacă graful este complet, apăsaţi pe butonul de validare pentru a-l salva. Pentru a reveni asupra unei soluţii deja salvate, apăsaţi cu mouse-ul pe pătratul din partea dreaptă ce conţine imaginea acesteia. Se va deschide un meniu în care aveţi posibilitatea sã alegeţi operaţia doritã.

3.5. Graful turneu În acest obiect de conţinut este prezentată noţiunea de graf turneu, care este un caz particular de graf complet. Problema care se pune este găsirea unui drum în graf care să treacă prin fiecare nod o singură dată.


- 17 -

Definirea drumului pe care îl va parcurge cartea se face prin trasarea arcelor ce îl vor compune, care vor fi de culoare roşie. Trasarea unui arc se face apăsând cu mouse-ul mai întâi pe nodul iniţial şi apoi pe nodul final. Prin apăsare pe butonul se activează modul de ştergere a arcelor dintre noduri. Butonul devine . În acest mod se poate şterge orice arc, prin simpla apăsare pe el. Pentru revenirea la starea iniţială se apasă încă o dată pe acest buton. Ştergerea unui arc al drumului duce la ştergerea arcelor ce urmează în continuarea sa în compunerea drumului.

3.6. Test de evaluare a cunoştinţelor Acest obiect de conţinut conţine un test grilă cu răspunsuri de tip “complement simplu”, adică doar o variantă de răspuns corectă.

Pentru a trece de la o problemă la alta poziţionaţi mouse-ul pe numărul problemei dorite. Bifarea răspunsurilor se face prin apăsarea cu mouse-ul pe căsuţa corespunzătoare raspunsului dorit. Se poate reveni asupra răspunsului la oricare dintre întrebări, atâta timp cât nu s-a răspuns la toate întrebările. După bifarea răspunsurilor pentru fiecare problemă, în dreapta butoanelor cu numărul problemelor vor apărea indicatori de validare a răspunsului:


- 18 -

pentru răspuns corect şi pentru răspuns greşit

Pentru a vedea rezolvarea apăsaţi butonul Rezolvare. În locul variantelor de răspuns ale fiecărei probleme vor apărea rezolvările corespunzătoare. În partea din dreapta-jos a ferestrei va fi specificat răspunsul corect. În locul butonului de rezolvare va apărea butonul Înapoi. Apăsaţi acest buton pentru ca în locul rezolvărilor să fie afişate din nou variantele de răspuns.

3.7. Matrice asociate grafurilor orientate În acest obiect de conţinut sunt definite trei tipuri de matrice asociate grafurilor orientate: matricea de adiacenţă, matricea drumurilor şi matricea vârfuri arce.


- 19 -

Pentru a trasa un arc în graf apăsaţi cu mouse-ul mai întâi pe elementul iniţial şi apoi pe cel final. Pentru a adăuga elemente apăsaţi pe butonul . Pentru a şterge ultimul element adăugat apăsaţi pe butonul . Prin apăsare pe butonul se activează modul de ştergere a arcelor dintre noduri. Butonul devine . În acest mod se poate şterge orice arc, prin simpla apăsare pe el. Matricele asociate se actualizează la fiecare modificare făcută pe graf.

3.8. Algoritmul Roy-Warshall În acest obiect de conţinut este prezentat algoritmul Roy-Warshall, un algoritm simplu de obţinere a matricei drumurilor pornind de la matricea de adiacenţă.

Apăsaţi butonul pentru a porni execuţia pas cu pas a algoritmului. Apăsaţi butonul pentru a opri execuţia algoritmului. Săgeata, împreună cu dreptunghiul de culoare roşie, indică linia şi respectiv funcţia care se executã la momentul curent.

Săgeata indică

linia curentă

Dreprunghiul indică funcţia curentă

Elementul prelucrta la momentul curent

Prelucrări curente


- 20 -

3.9. Problema celebrităţii În acest obiect de conţinut este prezentată o aplicaţie practică: problema celebrităţii.

Pentru a adăuga elemente apăsaţi pe butonul . Pentru a şterge ultimul element adăugat apăsaţi pe butonul . Stabilirea răspunsurilor la întrebarea din enunţ se face prin apăsarea repetată cu mouse-ul pe zona de răspuns, reprezentatã prin : . Răspunsul poate fi sau . În funcţie de aceste răspunsuri se formează graful corespunzător şi matricea de adiacenţă ataşată acestuia.

Graful asociat

Răspunsuri Matricea de adiacenţă

asociată grafului


- 21 -

3.10. Test de evaluare a cunoştinţelor (2) Acest obiect de conţinut conţine un test grilă cu răspunsuri de tip “complement simplu”, adică doar o variantă de răspuns corectă.


pentru răspuns corect şi pentru răspuns greşit



- 22 -

3.11. Graf conex. Graf tare conex. Componente conexe Iniţial vă aflaţi în modul "Adăugare arce". Generarea de subgrafuri ce au proprietăţile cerute se face astfel: se selectează mai întâi (prin apăsarea cu butonul mouse-ului) acele arce ale grafului care doriţi sã se găseascã în subgraf. Atunci când sunteţi mulţumit de subgraful generat apăsaţi butonul de validare pentru a vede ce proprietăţi are subgraful. Prin apăsare pe butonul se activează modul de ştergere a arcelor dintre noduri. Butonul devine . În acest mod se poate şterge orice arc, prin simpla apăsare pe el.


- 23 -

3.12. Test de evaluare a cunoştinţelor (3) Acest obiect de conţinut conţine un test grilă cu răspunsuri de tip “complement simplu”, adică doar o variantă de răspuns corectă.


pentru răspuns corect pentru răspuns greşit



- 24 -

4. Bibliografie

• Atanasiu A.; Bazele informaticii, Universitatea din Bucureşti, 1989

• Livovschi L., Georgescu H.; Sinteza şi analiza

algoritmilor, Editura Ştiinţifică si Enciclopedică, Bucureşti, 1986

• Tomescu I.; Probleme de combinatorică şi teoria

grafurilor, Editura Didactică şi Pedagogică, Bucureşti, 1981

• Tomescu I.; Ce este teoria grafurilor?, Editura Ştiinţifică şi Pedagogică, Bucureşti, 1981

• Ivaşc Cornelia, Prună Mona; Bazele informaticii- Manual

pentru clasa a X-a, Editura Petrion, Bucureşti

• Knuth D. E; Tratat de programarea calculatoarelor. Algoritmi fundamentali, Editura Tehnică, 1974

Date post:	24-May-2015
Category:	Education
Upload:	natashcka
View:	1,148 times
Download:	6 times

Manualul profesorului

Education