PROIECT DE LECŢIE

UNITATEA ŞCOLARĂ: Colegiul “Ștefan Odobleja”, CraiovaCLASA: aXIa CPROFESOR: Puncioiu Luiza IonelaDATA: 22.01.2013DISCIPLINA: InformaticăSUBIECTUL LECŢIEI: Grafuri parțialeUNITATEA DE ÎNVĂŢARE: Grafuri derivate dintr-un grafTipul lecției: Dobândire de cunoștințeDurata: 50minLocul de desfășurare: Sala de curs

Competente specifice:

CS1: Descrierea unor algoritmi simpli de verificare a unor proprietăţi specifice grafurilor

Obiective de referinţă:

OR1: sa obtina un graf partial dintr-un graf OR2: sa verifice daca un graf este graf partial al grafului respectiv

Obiective operaţionale:

OP1- sa inteleaga notiunea de graf partial al unui graf;OP2 – sa stie dintr-o matrice de adiacenta sa reprezinte in plan graful;OP3 - sa reprezinte un graf partial;OP4 – sa determine numarul de grafuri partiale al unui graf cu m muchii ;OP5 - sa stie sa verifice daca un graf Gp este un graf partial al unui graf G;OP6- sa stie sa obtina dintr-un graf un graf partial;

OP7 - sa stie sa scrie algoritmi pentru prelucrarea grafurilor partiale;OP8- sa stie sa implementeze algoritmii in c++.

Strategii didactice :Metode si procedee : conversatia, explicatia , problematizarea, activitate frontala , invatarea prin descoperireMijloace : manualul clasa XI- ed Didactica si Pedagogica(Autor Mariana Milosescu), fise de lucru, calculatorul, tabla interactiva, prezentarea .

Desfasurarea lectiei

Etapele lectiei

Obiective

Activitatea desfasurata de Strategii Didactice

TimpProfesor Elevi

Moment organizatoric

Verifica prezenta elevilor, pregatirea clasei pentru lectieSe pregatesc cu cele

necesare pentru lectie. Conversatia1 min

Captarea atentiei si trezirea

interesului pentru noua

lectie

Prezinta titlul lectiei .Comunica obiectivele lectiei :

- obtinerea un graf partial dintr-un graf- sa verificam daca un graf, dat prin matricea de adiacenta

este graf partial al grafului initial

Sunt atenţi la precizările profesorului şi îşi notează în caiete

Activitate frontala

Conversatia

2 min

Recapitulare Recapituleaza cu elevii:- notiunea de graf ;- clasificarea grafurilor;- reprezentarea grafurilor in memorie.

Raspund la intrebarile recapitulative ale profesorului.

ConversatiaAct.

Frontala

5 min

Conducerea Defineste graful partial si face observatia ca un graf partial poate fi Sunt atenti la precizarile Act. 25

2

invatarii

OP1

OP2

OP4

OP3

OP5

OP2

chiar graful insusi.Reprezinta in plan 2 grafuri: unul neorientat si unul orientat.Exemplifica modul de obtinere a unui graf partial pe un graf neorientat si un graf orientat .Solicita elevilor sa scrie pentru cele 2 grafuri elementele multimilor X si U.Enunta teorema care defineste numarul de grafuri partiale ale unui graf cu m muchii(arce).Realizeaza o demonstratie succinta a teoremei anterioare. Utilizeaza reprezentarea grafica pentru ai face pe elevi sa inteleaga

cum se ajunge la formula C + C + Cm

Exemplifica elevilor modul de obtinere al celor 23 grafuri partiale din graful cu matricea de adiacenta:

0 1 1a= 1 0 1 1 1 0Prezinta algoritmii pentru prelucrarea grafurilor partiale.Pentru inceput Verifica daca un graf G2 este graf partial al unui graf G1.

Propune la problema 1 doua matrice de adiacenta .Solicita ca elevii sa reprezinte in plan, graful corespunzator fiecarei matrice. Face o paralele intre cele doua matrice pentru a observa daca se poate ca din matricele de adiacenta ale celor doua grafuri sa se constate , daca unul este graf partial al celuilalt. Prin observarea celor doua matrice se constata ca cele doua matrice : a1 a lui G1 si a2 a lui G2 trebuie sa indeplineasca urmatoarele conditii:

- n1 =n2 nr de linii(coloane) al lui a1 trebuie sa fie egal cu nr de linii(coloane) al lui a2

- toate valorile de 1 care sunt in a2 trebuie sa se gaseasca pe aceleasi pozitii si in numar >= in a1

profesorului si isi noteaza in caiete.

Noteaza in caiete enuntul teoremei de pe tabla aplicare in exercitii.

Reprezinta pe caiete grafurile partiale si determina numarul lor.

Realizeaza pe caiete reprezentarea fiecarui graf .

Fac observatii asupra elementelor celor doua matrice.

FrontalaConversatiaProblematiz

areaAlgoritmiza

reaExercitiul

min

3

OP7OP8

Dupa extragerea acestor concluzii cu ajutorul elevilor , incearca cu ajutorul lor sa scrie o functie numita partial()care sa verifice aceste doua conditii.Datele de intrare: - n1 si n2 se citesc din fisier. - matricele de adiacenta a1 si a2 se citesc din fisier.Functia partial() va returna valoarea 0 daca:

- n1 diferit de n2- sau daca (a2[i][j]=1 si a1[i][j]=0)

Va vizualiza pe tabla interactiva tot programul si-l va rula pentru a analiza datele de iesire.

Scriu pe caiete functia partial() si restul programului.

Aprofundarea

cunostiintelor

OP6

OP7OP8

Prezinta Cum se obtine un graf partial dintr-un graf G prin eliminarea unor muchii ce au ca noduri valori ce indeplinesc o conditie.Se citeste enuntul problemei 2.Se ia spre exemplificare nodul x=5 si se vor elimina muchiile [2,5], [4,5].Se construieste matricea de adiacenta a grafului partial obtinut.Discuta cu elevii algoritmul problemei si se determina subprogramele necesare rezolvarii problemei:

- functia citeste() va citi din fisier val lui x, a lui n- nr de linii si valorile matricei de adiacenta.

- functia grad() va determina gradul unui nod.- functia graf_partial() va fi functia care construieste graful

partial prin atribuirea valorii 0 in matricea de adiacenta pentru a[i][x] si pentru a[x][i] unde i este nodul cu grad par , iar x este nodul a carui valoare este citita din fisier.

- functia scrie() va afisa graful partial obtinut prin afisarea extremitatilor fiecarei muchii din graf.

Intreaba elevii cum se obtine gradul unui nod t si discuta implementarea in c++.Numeste un elev sa scrie pe tabla interactiva functia graf_partial() in c++.Vizualizeaza pe tabla intregul program si-l ruleaza un elev.

Participa activ la rezolvarea problemei 2 si ofera detalii despre determinarea gradului unui nod..

Activitate frontala

ConversatiaExercitiulStudiul de

cazInvatarea

prin descoperire

dirijata

10 min

4

Analizeaza corectitudinea datelor de iesire

Evaluarea performantei

OP2OP7 OP8

Face aprecieri, recomandari, noteaza elevii care s-au remarcat la lectie, in special cei care au iesit la tabla .

Conversatia1 min

Tema Recomanda ca tema pentru acasa subiectul 3 din fisa si discuta cerintele problemei.

Elevii incercuiesc subiectul .

Conversatia 1 min

Fisa :

1) Fie urmatoarele matrice de adiacenta :

0 1 0 0 0 1 0 0a1= 1 0 1 1 si a2= 1 0 1 1 0 1 0 1 0 1 0 0 0 1 1 0 0 1 0 0 Reprezentati in plan graful corespunzator fiecarei matrice de adiacenta.

2) Scrieti programul care citeste din fisier :- pe prima linie numarul de noduri si eticheta unui nod x ; - de pe urmatoarele randuri matricea de adiacenta a unui graf neorientat.si genereaza un graf partial prin eliminarea muchiilor care au la extremitati un nod cu gradul par si nodul x.Informatiile despre graful partial obtinut se vor afisa pe monitor sub forma de perechi de valori ce reprezinta extremitatile muchiilor.

Pentru exemplificare se considera graful:

3) Care este numărul minim de muchii ce pot fi eliminate din graful alăturat astfel încât în graful parţial rezultat să existe exact un vârf de grad 0?

5

12

3

4

5

6