Proiect didactic

Proiect didacticTitlul leciei: Grafuri orientateObiectul: Informatica Data: 26 noiembrie 2010Timpul acordat : 50 min.Clasa: a-XI-a B, profil real

Tipul leciei: Lecia de comunicare i nsuire de noi cunotine Specializarea: matematic-informatic intensiv informatica

Profesor: Boca Alina GabrielaCompetene generale

1. Identificarea conexiunilor dintre informatic i societate

2. Identificarea datelor care intervin ntr-o problem i aplicarea algoritmilor fundamentali de prelucrare a acestora

3. Elaborarea algoritmilor de rezolvare a problemelor

4. Aplicarea algoritmilor fundamentali n prelucrarea datelor5. Implementarea algoritmilor ntr-un limbaj de programare

Competene specifice:

1.1 Transpunerea unei probleme din limbaj natural n limbaj de grafuri, folosind corect terminologia specific;1.2 Analizarea unei probleme n scopul identificrii datelor necesare i alegerea modalitilor adecvate de structurare a datelor care intervin ntr-o problem;1.3 Descrierea unor algoritmi simpli de verificare a unor proprieti specifice grafurilor;1.4 Descrierea algoritmilor fundamentali de prelucrare a grafurilor i implementarea acestora ntr-un limbaj de programare;

Obiective operaionale:Informative

Elevii vor fi capabili:

- s analizeze enunul unei probleme i s identifice modul corect de prelucrare;- s aleag metoda adecvat de structurare a datelor care intervin ntr-o problem;- s cunoasc principiile prelucrrii grafurilor.FormativeElevii vor ti:

- s prelucreze structuri complexe de date organizate n grafuri.

AfectiveElevii vor putea:- s decid asupra folosirii structurii de tip graf n rezolvarea de probleme.

Metode i procedee didactice:

Conversaia euristic;

Algoritmizarea;

Explicaia;

Demonstraia;

Rezolvarea de probleme.Mijloace de nvare:

Fie de lucru; Caietul de exercitii practice,Probleme model.

Material bibliografic:

[1] Vlad Huanu, Tudor Sorin, Manual de Informatic intensiv, clasa a XI-a, Editura L&S Soft, 2009;[2] Carmen Minca, Nua Dumitriu Lupan, Caiet de laborator pentru clasa a XI-a Profilul Real, Editura L&S Infomat 2009[3] Dana Lica, Mircea Paoi, Informatica Fundamentele Programarii culegere de probleme pentru clasa a XI-a, Editura L&S Infomat 2009

DESFURAREA LECIEI:Etapele lecieiTimpActivitatea desfurat de:Metoda de activitate

ProfesorElevi

01234

Moment organizatoric2Verific prezena elevilor, pregtirea clasei pentru lecie

Fixarea ancorelor10Exist probleme care conin date ntre care exist anumite relaii.Exemple: 1. Fie o clas de 29 de elevi. Unii dintre elevi sunt prieteni, relaia de prietenie este o relaie simetric.

2. Fie harta stradal a sectorului 1. Unele strzi au sens unic, n timp ce alte strzi (principale) au dou sensuri de circulaie. 3. Fie un grup de n persoane, unde fiecare persoan deine un telefon mobil. Pe agenda telefonului mobil a fiecrei persoane se gsesc numere de telefoane ale altor k 0 persoane din grup.Pentru fiecare dintre aceste exemple se poate imagina o reprezentare grafic care s exprime relaiile existente.

Convenim ca fiecare element s-l reprezentm grafic printr-un cerc n interiorul cruia i vom aduga o etichet. Obinem astfel o muime de obiecte pe care le vom numi noduri i pe care o vom nota, n general cu V (de la termenul n limba eneglez, vertex). Convenim s reprezentm fiecare relaie (de prietenie, de comunicare) existent ntre dou elemente printr-o sgeat dac relaia este ntr-un singur sens sau printr-o sgeat dubl sau pur i simplu printr-un segment de dreapa dac relaia este n ambele sensuri.

Atenie: Folosim deocamdat termenul de relaie n sensul din limba romn i nu n sens matematic.

Convenim ca fiecare relaie s o numim, dup caz, arc, respectiv muchie.

Pentru nceput, ne vom ocupa de cazurile n care relaiile dintre obiecte au loc ntr-un singur sens.

Pentru exemplu 3 arcul (i,j) are semnificaia c persoana identificat prin i are n agenda telefonic numrul persoanei identificat prin j. Cu alte cuvinte:

Pentru cele 3 exemple de mai sus, pot fi considerate dou mulimi: mulimea obiectelor reprezentate prin cercuri sau puncte etichetate cu 1, 2, ...i, ...j, ...n (pentru exemplul 1 mulimea elevilor, pentru exemplul 2 mulimea strzilor, pentru exemplul 3 multimea numerelor de telefon) i mulimea relaiilor reprezentat prin arce de forma ij (pentru exemplul 1 mulimea relaiilor de prietenie dintre elevi, pentru exemplul 2 mulimea sensurilor de deplasare pe strzi, pentru exemplul 3 mulimea apelurilor telefonice).Structura compus din cele dou mulimi se numete graf.

Rspund la ntrebrile profesoruluiNoteaz n caieteSunt ateni la precizrile profesorului i i noteaz n caiete.

Rezolv n caiete sarcinileFrontal

Conversaie

Consolidarea noilor cunotine30Definiie: Se numete digraf (graf orientat) perechea ordonat G=(V,E), unde V={v1,v2,...,vn} este o mulime finit de elemente numit vrfuri sau noduri i E este o mulime de arce, EVxV.

Pentru graful din desenul de mai sus V={1,2,3,4,5,6,7}, E={(1,2), (1,5), (1,7), (2,3), (3,6), (4,3), (4,5), (6,2)}

Definie: n graful orientat G=(V,E) vrfurile distincte (vi,vj) sunt adiacente dac exist cel puin un arc care le unete.

Avem urmtoarele cazuri:

1. Arcul (1, 2) este incident spre exterior cu vrful 1

2. Arcul (1,2) este incident spre interior cu varful 2.

Definiie: ntr-un graf orientat, prin gradul exterior al unui vrf v vom nelege numrul arcelor incidente spre exterior cu v. Informal: numrul arcelor care ies. Gradul exterior al unui nod va fi notat cu d+(v). Definie: ntr-un graf orientat prin gradul interior al unui vrf v, vom nelege numrul arcelor incidente spre interior cu v. Informal: numrul arcelor care intr n nod. Gradul interior al unui nod va fi notat cu d-(v).

Pentru graful de mai sus avem: d+(1) = 3, d+(2) = 1, d+(3) = 1, d+(4) = 2, d+(5) = 0, d+(6) = 1, d+(7) = 0, d-(1) = 0, d-(2) = 2, d-(3) = 2, d-(4) = 0, d-(5) = 2, d-(6) =1, d-(7) = 1.Se observ c d+(1) + d+(2) + d+(3) +d+(4) +d+(5) +d+(6) +d+(7) = d-(1) + d-(2) +d-(3) + d-(4) + d-(5) +d-(6) +d-(7) = 8.ntr-un graf orientat avem urmtoarea relaie:

, unde n reprezint numrul de vrfuri i m numrul de arce.

Se numete descendent direct al unui nod i, un nod j pentru care exist un arc (o relaie) de la nodul i la nodul j. ij.

Pentru graful de mai sus descendenii directi ai nodului 1 sunt nodurile 2, 5, 7.

Se numete descendent indirect al unui nod i un nod j pentru care exist mai multe arce ntre nodul i i nodul j, primul arc pornind de la nodul i.

Pentru graful de mai sus descendenii indireci ai nodului 1 sunt nodurile 3 i 6.

Prelucrarea grafurilor orientate cu ajutorul calculatorului presupune n primul rnd reprezentarea lor astfel nct s poat fi memorate n calculator. Cea mai simpl metod de memorare a grafurilor const din calcularea matricei de adiacent. Aceast matrice are un numr de linii egal cu numrul de coloane i egal cu numrul de elemente din mulimea V. n celula de la intersecia liniei corespunztoare nodului i cu coloana corespunztoare nodului j se va depune valoarea 1 sau 0 dup cum exist sau nu un arc de la nodul i la nodul j. Formalizat: a[i][j]=

Ce observm? Este aceast matrice simetric sau nu? De ce?Pentru graful de mai sus matricea de adiacen este:0100011001000000000100010100000000001000000000000Un alt mod de memorare se realizeaz prin listele de adiacen.n acest caz, considerm pe rnd fiecare nod i enumerm (eventual n ordine cresctoare) toi descendenii si direci.

1: 2, 5, 7

2: 3

3: 6

4: 3, 5

5:6: 27: Fie urmtoarele aplicaii:

Desenai graful orientat definit de X={1,2,3,4,5,6} i U={(1,2), (1,5), (3,2), (5,6), (3,6), (6,1), (4,2), (4,3)}

Se consider un graf orientat cu 6 noduri numerotate de la 1 la 6 i cu mulimea arcelor format doar din arcele:

- de la fiecare nod numerotat cu un numr neprim i (i>1) la toate nodurile numerotate cu numere ce aparin mulimii divizorilor proprii ai lui i (divizori diferii de 1 i de i)

- de la nodul numerotat cu 1 la nodul numerotat cu 6

- de la fiecare nod numerotat cu un numr prim i la nodul numerotat cu i-1

Pentru graful dat stabilii gradul intern i gradul extern al fiecrui nod, precum i descendenii direci, iar apoi construii matricea de adiacen i listele de adiacen.

Sunt ateni la precizrile profesorului i i noteaz n caiete.

Rezolv n caiete sarcinile.

Corecteaz aplicaiile:

pentru fiecare aplicaie iese un elev la tabl, si se discut soluia cu ceilalti elevi din clasa.FrontalIndividual

Feed-back4ntreab elevii despre noiunile nvate n ora respectivgraf orientat, descendent, matrice i lista de adiacen. Rspund la ntrebrile profesoruluiFrontal

Conversaie

Evaluare i notare1Noteaz elevii care au dat rspunsuri corecte.

Tema pentru acas31) Reprezentai printr-un graf mulimea capitalelor din Europa n care se vorbesc limbi avnd aceeai origine (limbi din familia: latin, slav, germanic etc.)2) Dai un exemplu de situaie cu care v-ai ntlnit n cursul acestui an i care poate fi reprezentat printr-un graf.3) Scriei un program C++ care s citeasc matricea de adiacen a unui graf i care s calculeze gradele interior i exterior pentru fiecare nod i s le afieze.4) Scriei un program C++ care s listeze listele de adiacen.Primesc fia cu tema pentru acas i noteaz indicaiile pofesoruluiFrontal

1

2

7

6

5

3

4

2

1

1

2

7

6

5

3

4

_1470413418.unknown

_1470413419.unknown

_1470413417.unknown