8/17/2019 Proiect Didactic Clasa a X-A

1/7

Proiect didacticTitlul lecţiei: 

Grafuri orientateObiectul: Informatica Data: 26 noiembrie 2010Timpul acordat : 50 min. Clasa:  a-XI-a B, profil realTipul lecţiei: Lec ia de comunicare i însu ire de noi cuno tin eț ș ș ș ț   Specializarea: matematic-informatic intensi! informatica

Profesor: Boca "lina #abrielaCompetenţe generale 1. Identificarea cone$iunilor dintre informatic %i societate

2. Identificarea datelor care inter!in într-o problem %i aplicarea al&oritmilor fundamentali de prelucrare a acestora'. (laborarea al&oritmilor de re)ol!are a problemelor *. "plicarea al&oritmilor fundamentali în prelucrarea datelor 5. Implementarea al&oritmilor într-un limba+ de pro&ramare

Competenţe specifice: 1.1 ranspunerea unei probleme din limba+ natural în limba+ de &rafuri, folosind corect terminolo&ia specific1.2 "nali)area unei probleme în scopul identificrii datelor necesare %i ale&erea modalitilor adec!ate de structurare a

datelor care inter!in într-o problem1.' /escrierea unor al&oritmi simpli de !erificare a unor proprieti specifice &rafurilor

1.* /escrierea al&oritmilor fundamentali de prelucrare a &rafurilor %i implementarea acestora într-un limba+ de pro&ramare

Obiective operaţionale :Informative(le!ii !or fi capabili:- s anali)e)e enunul unei probleme %i s identifice modul corect de prelucrare- s alea& metoda adec!at de structurare a datelor care inter!in într-o problem- s cunoasc principiile prelucrrii &rafurilor.

Formative(le!ii !or %ti:- s prelucre)e structuricomple$e de date or&ani)ateîn &rafuri.

Afective(le!ii !or putea:

- s decid asupra folosirii structurii de tip&raf în re)ol!area de probleme.

etode !i procedee didactice: on!ersaia euristic"l&oritmi)area($plicaia/emonstraiae)ol!area de probleme.

i"loace de #nv$ţare: i%e de lucru aietul de e$ercitii practice,3robleme model.

aterial bibliografic: 41 %lad &u anu' Tudor Sorinț , Manual de Informatică intensiv, clasa a XI-a, (ditura L7 7oft, 2008

8/17/2019 Proiect Didactic Clasa a X-A

2/7

42 Carmen inca' (u!a Dumitriu )upan, Caiet de laborator pentru clasa a XI-a Profilul Real , (ditura L7Infomat 20084' Dana )ica' ircea Pa oiș ,  Informatica Fundamentele Programarii culegere de probleme pentru clasa a XI-a,(ditura L7 Infomat 2008

D*SF+,-.A.*A )*C/I*I:

(tapele leciei imp"cti!itatea desf%urat de: 9etoda de

acti!itate3rofesor (le!i0 1 2 ' *

Moment

organizatoric2 ;erific pre)ena ele!ilor, pre&tirea clasei pentru lecie

Fixarea

ancorelor10 ($ist probleme care con in date între care e$ist anumite rela ii.ț ț

($emple: 1. ie o clas de 28 de ele!i.

8/17/2019 Proiect Didactic Clasa a X-A

3/7

12

D

6 5

'

*

(tapele leciei imp

"cti!itatea desf%urat de:

9etoda deacti!itate

Aten ieț : olosim deocamdat termenul de rela ie în sensul dințlimba romEn i nu în sens matematic.șon!enim ca fiecare rela ie s o numim, dup ca), arc, respecti!țmuc=ie.3entru început, ne !om ocupa de ca)urile în care rela iile dintrețobiecte au loc într-un sin&ur sens.3entru e$emplu ' arcul >i,+? are semnifica ia c persoanațidentificat prin i are în a&enda telefonic numrul persoaneiidentificat prin +.u alte cu!inte:3entru cele ' e$emple de mai sus, pot fi considerate doumul imi: mul imea obiectelor repre)entate prin cercuri sauț ț puncte etic=etate cu 1, 2, ...i, ...+, ...n >pentru e$emplul 1mul imea ele!ilor, pentru e$emplul 2 mul imea str)ilor, pentruț țe$emplul ' multimea numerelor de telefon? i mul imea rela iilor ș ț țrepre)entat prin arce de forma iF+ >pentru e$emplul 1mul imea rela iilor de prietenie dintre ele!i, pentru e$emplul 2ț țmul imea sensurilor de deplasare pe str)i, pentru e$emplul 'ț

mul imea apelurilor telefonice?.ț7tructura compus din cele dou mul imi se nume te &raf.ț ș

8/17/2019 Proiect Didactic Clasa a X-A

4/7

12

D

6 5

'

*

(tapele leciei imp

"cti!itatea desf%urat de:

9etoda de

acti!itate

Consolidarea

noilorcunoştinţe

'0Defini ieț : 7e nume te di&raf >&raf orientat? perec=ea ordonatș#G>;,(?, unde ;GH!1,!2,...,!n este o mul ime finit de elementețnumit !Erfuri sau noduri i ( este o mul ime de arce, (ș ț   ⊂ ;$;.3entru &raful din desenul de mai sus ;GH1,2,',*,5,6,D,(GH>1,2?, >1,5?, >1,D?, >2,'?, >',6?, >*,'?, >*,5?, >6,2?

Defin ie:ț Jn &raful orientat #G>;,(? !Erfurile distincte >! i,! +?sunt adiacente dac e$ist cel pu in un arc care le une te.ț ș"!em urmtoarele ca)uri:

1. "rcul >1, 2? este incident spre e$terior cu !Erful 12. "rcul >1,2? este incident spre interior cu !arful 2.

Defini ieț : Jntr-un &raf orientat, prin &radul e$terior al unui !Erf !!om în ele&e numrul arcelor incidente spre e$terior cu !.ț

Informal: numrul arcelor care KiesK. #radul e$terior al unui nod!a fi notat cu d>!?.Defin ieț : Jntr-un &raf orientat prin &radul interior al unui !Erf !,!om în ele&e numrul arcelor incidente spre interior cu !.țInformal: numrul arcelor care KintrK în nod. #radul interior alunui nod !a fi notat cu d->!?.

 3entru &raful de mai sus a!em: d >1? G ', d>2? G 1, d>'? G 1,d>*? G 2, d>5? G 0, d>6? G 1, d>D? G 0, d->1? G 0, d->2? G 2, d-

>'? G 2, d->*? G 0, d->5? G 2, d->6? G1, d->D? G 1.

7unt ateni la preci)rile profesorului %i î%i notea)în caiete.e)ol! în caietesarcinile.

orectea) aplicaiile: pentru fiecare aplicaieiese un ele! la tabl, si sediscut soluia cu ceilaltiele!i din clasa.

rontal

Indi!idual

21

8/17/2019 Proiect Didactic Clasa a X-A

5/7

(tapele leciei imp

"cti!itatea desf%urat de:

9etoda deacti!itate

7e obser! c d>1? d>2? d>'? d>*? d>5? d>6? d>D? Gd->1? d->2? d->'? d->*? d->5? d->6? d->D? G M.Jntr-un &raf orientat a!em urmtoarea rela ie:ț

∑ ∑= =

−+==

n

i

n

i

mid id 

1 1

?>?>

, unde n repre)int numrul de !Erfuri iș

m numrul de arce.7e nume te descendent direct al unui nod i, un nod + pentru careșe$ist un arc >o rela ie? de la nodul i la nodul +. iF+.ț3entru &raful de mai sus descenden ii directi ai nodului 1 suntțnodurile 2, 5, D.7e nume te descendent indirect al unui nod i un nod + pentrușcare e$ist mai multe arce între nodul i i nodul +, primul arcș pornind de la nodul i.3entru &raful de mai sus descenden ii indirec i ai nodului 1 suntț țnodurile ' i 6.ș3relucrarea &rafurilor orientate cu a+utorul calculatorului

 presupune în primul rEnd repre)entarea lor astfel încEt s poat fimemorate în calculator. ea mai simpl metod de memorare a&rafurilor const din NcalculareaK matricei de adiacent. "ceastmatrice are un numr de linii e&al cu numrul de coloane i e&alșcu numrul de elemente din mul imea ;. Jn celula de lațintersec ia liniei corespun)toare nodului i cu coloanațcorespun)toare nodului + se !a depune !aloarea 1 sau 0 dupcum e$ist sau nu un arc de la nodul i la nodul +. ormali)at:

  a4i4+G

( )

altfel 

 jidacă

0

,1

e obser!mO (ste aceast matrice simetric sau nuO /e ceO3entru &raful de mai sus matricea de adiacen este:ț

0 1 0 0 0 1 10 0 1 0 0 0 00 0 0 0 0 1 0

8/17/2019 Proiect Didactic Clasa a X-A

6/7

(tapele leciei imp

"cti!itatea desf%urat de:

9etoda de

acti!itate

0 0 1 0 1 0 00 0 0 0 0 0 00 1 0 0 0 0 00 0 0 0 0 0 0

e!entual în ordine cresctoare? to i descenden ii si direc i.ț ț ț1: 2, 5, D2: '': 6*: ', 55:6: 2D:ie urmtoarele aplica ii:ț/esena i &raful orientat definit de XGH1,2,',*,5,6 i 1,2?,ț ș

>1,5?, >',2?, >5,6?, >',6?, >6,1?, >*,2?, >*,'?7e consider un &raf 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 >iP1? la toatenodurile numerotate cu numere ce aparin mulimii di!i)orilor proprii ai lui i >di!i)ori 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 nodulnumerotat cu i-13entru &raful dat stabili i &radul intern i &radul e$tern alț ș

fiecrui nod, precum i descenden ii direc i, iar apoi construi iș ț ț țmatricea de adiacen i listele de adiacen .ț ș ț

Feed-back* Jntreab ele!ii despre noiunile în!ate în ora respecti!&raf orientat,

descendent, matrice i lista de adiacen .ș țspund la întrebrile

 profesoruluirontalon!ersaie

Evaluare şi

notare1 Cotea) ele!ii care au dat rspunsuri corecte.

Tema pentru ' 1? epre)enta i printr-un &raf mul imea capitalelor din (uropa înț ț 3rimesc fi%a cu tema rontal

8/17/2019 Proiect Didactic Clasa a X-A

7/7

(tapele leciei imp"cti!itatea desf%urat de:

9etoda deacti!itate

acasă

care se !orbesc limbi a!End aceea i ori&ine >limbi din familia:șlatin, sla!, &ermanic etc.?

2? /a i un e$emplu de situa ie cu care !-a i întElnit în cursulț ț țacestui an i care poate fi repre)entat printr-un &raf.ș

'? 7crie i un pro&ram care s citeasc matricea de adiacen ț ța unui &raf i care s calcule)e &radele interior i e$teriorș ș

 pentru fiecare nod i s le afi e)e.ș ș*? 7crie i un pro&ram care s liste)e listele de adiacen .ț ț

 pentru acas %i notea)indicaiile pofesorului