Reprezentarea grafurilor orientate cu matricea dr umurilor [614911]
0
UNIVERSITATEA DIN BUCUREȘTI
FACULTATEA DE MATEMATICĂ ȘI INFORMATICĂ
LUCRARE METODICO – ȘTIINȚIFICĂ PENTRU
OBȚINEREA GRADULUI DIDACTIC I
SPECIALITATEA INFORMATICĂ
COORDONATOR ȘTIINȚIFIC:
PROF. UNIV. DR. TOMESCU IOAN
CANDIDAT: [anonimizat]. TURIAC EVELINA
LICEUL TEORETIC “NICOLAE IORGA” BRĂILA
– 2012
UNIVERSITATEA DIN BUCUREȘTI
1
FACULTATEA DE MATEMATICĂ ȘI INFORMATICĂ
“GRAFURI NEORIENTATE ȘI ORIENTATE ÎN PROGRAMA
LICEALA DE INFORMATICĂ”
COORDONATOR ȘTIINȚIFIC:
PROF. UNIV. DR. TOMESCU IOAN
CANDIDAT: [anonimizat]. TURIAC EVELINA
LICEUL TEORETIC “NICOLAE IORGA” BRĂILA
– 2012 –
2
CUPRINS
Justificarea alegerii temei și prezentarea generală a lucrării ………………………….. 3
Capitolul I
Elemente de teoria grafurilor. Grafuri neorientate ………………………………………. 5
1.1 Grafuri neorientate – Noțiuni de bază ………………………… …………………………. 5
1.2 Reprezentarea grafurilor neorientate …………………………………………… …. 7
1.3 Clase speciale de grafuri neorientate ………………………………………………………………. 11
1.4 Parcurgerea grafurilor neorientate ………………………………………………… 15
1.5 Conexitate în grafuri neorientate ……………………………………………………………………. 26
1.6 Aplicații …………………………………………………………………………………………………….. 30
Capitolul II
Elemente de teoria grafurilor. Grafuri orientate …………………………………………………. 33
2.1 Grafuri orientate – Noțiuni de bază ………………………………………………………………… 33
2.2 Reprezentarea grafurilor orientate …………………………………………………………………. 36
2.3 Drumuri și circuite în grafuri orientate ……………………………………… …… 39
2.4 Conexitate în grafuri orientate ……………………………… ……………………. 41
2.5 Drumuri minime și maxime în grafuri orientate ………………… ……………….. 47
2.6 Aplicatii ………… ………….…………………………………………………….. 53
Capitolul III
Proiectarea activității didactice la disciplina „lnformatică" ………………………… 58
3.1 Obiective pedagogice și operaționale ………………………………………… …. 59
3.1.1 Obiectivele cadru ale disciplinei „Informaticã” în învãțãmântul
preuniversitar 59
3.1.2 Operaționalizarea obiectivelor …………………………………………… .. 62
3.2 Metode de învățământ folosite în predarea disciplinei „Informatică " ……… .. 64
3.2.1 Clasificarea metodelor de învățământ ……………………………………… 65
3.2.2 Metode specifice de predare a „Informaticii” ……………………………… 66
3.2.2.1 Metode de comunicare oralã ………………………………………………………. 66
3.2.2.2 Metode expozitive ……………………………………………… …… 66
3.2.2.3 Metode conversative …………………………………… …………… 66
3.2.2.4 Metode de comunicare scrisã …………………………….………….. 68
3.2.2.5 Metoda predãrii algoritmilor și tehnicilor de programare ……………….. 68
3.2.2.6 Metoda predãrii unui limbaj de programare …………………………………. 69
3.2.2.7 Metoda predãrii sistemelor utilitare …………………………………………….. 70
3.2.2.8 Metoda predãrii analizei numerice ……………………………………………… 70
3.2.2.9 Metode bazate pe acțiune …………………………………………………………… 71
3.2.2.9- a) Exercițiul ………………………………………………………………… 71
3.2.2.9- b) Metoda lucrãrii practice ……………………………………………. 71
3.2.2.9- c) Metoda proiectelor ……………………………………………………. 71
3.3 Mijloace de învățământ necesare în predarea disciplinei „lnformatică ” …… … 73
3.3.1 Funcțiile pedagogice ale mijloacelor de învățământ ……… ………………… 73
3.3.2 Clasificarea mijloacelor de învățământ ………………………………………. 74
3.4 Evaluarea randamentului școlar ……………………………………………… …. 75
3.4.1 Înnoiri aduse în domeniul evaluării de tehnologia didactică modernă …… … 75
3.4.2 Forme de evaluare ……………………………………………………………………………….. 76
3.4.3 Metode de evaluare …………….…………………………………………….. 77
3.5 Organizarea proces ului instructiv -educativ ………………… ………………….. 83
3.5.1 Structura lecției ………………… ………………………………………… … 83
3.5.2 Tipologia lecției …………………………………………………………… .. 83
3.5.3 Realizarea proiectului didactic ………………… …………………………… 85
Bibliografie …………………………………………………………………………………………….… ……. 97
Declarație de autenticitate ……………………………………………………………… 98
3
JUSTIFICAREA ALEGERII TEMEl
Șl PREZENTAREA GENERALĂ A LUCRĂRll
Într-un număr mare de situații, matematicianul, chimistul, inginerul ca și psihologul au
fost conduși la reprezentarea unor cazuri concrete prin desenarea unor puncte pe o foaie de
hârtie (aceste puncte reprezentând numere, localități, grupări chimice, indivizi dintr-un grup
social, operațiile unui proiect) și prin linii continue care l eagă anumite perechi de puncte și
care simbolizează o relație, un drum, o legătură chimică, o ati tudine sau o preferință, o legătură
dintre două noduri ale unei rețele electrice.3
Aceste puncte au fost numite vârfuri sau noduri, iar liniile care unesc perechile de
vârfuri au fost numite arce sau muchii (după cum ele sunt orientate sau nu).
Acest punct de vedere își are originea în lucrările lui Euler, care în 1736 studia
problema celor șapte poduri din Königsberg (astăzi Kaliningrad).
Prima carte de teoria grafurilor a fost publicată de D.Köni g ( Leipzig, 1936), urmată de
cea a lui C. Berge ( Paris, 1957). În ultimele decenii teoria gr afurilor s-a dezvoltat impetuos,
fiind ilustrată prin numeroase lucrări și tratate, simpozioa ne și conferințe în multe țări ale
lumii.
Astăzi folosirea grafurilor a devenit curentă în multe raționame nte de natură
combinatorică, fiind strâns legată de alte ramuri ale matema ticii, cum sunt teoria grupurilor,
teoria numerelor, topologia. Ramură a teoriei mulțimilor și î n același timp instrument
important al cercetării operaționale, teoria grafurilor are numeroase aplicații în inginerie,
economie, chimie, sociologie și lingvistică.
Cerințele actuale ale învățământului românesc se axează pe un proces didactic axat pe
elev, pe lecții cât mai dinamice și atractive.
Lucrarea “Grafuri neorientate si orientate in programa liceala de info rmatica” se
adresează profesorilor de informatică care se ocupă de pregă tirea elevilor la disciplina
4
"Informatică" și are aplicabilitate la liceu.
Din dorința de perfecționare a procesului instructiv – educativ, te ma are ca finalitate
formarea unor elevi cu un standard de pregătire teoretică și p ractică ridicat, în domeniul
informaticii.
Cele 3 capitole ale lucrării au menirea să înlesnească pe rfecționarea activității
profesorului la catedră.
Primul capitol prezintă elemente de teoria grafurilor-grafuri neorientate. S unt
prezentate noțiunile de bază ale grafurilor neorientate, reprez entarea grafurilor neorientate,
clase speciale de grafuri neorientate, parcurgerea grafuri lor neorientate, conexitate în grafuri
neorientate, iar la final am dat aplicații cu grafuri neorie ntate, pe care le-am explicat și le-am
rezolvat în limbajul de programare C++.
În capitolul II se prezintă elemente de teoria grafurilor-grafuri orientate . Am tratat
noțiunile despre reprezentarea grafurilor orientate, drumuri și circuite în grafuri orientate,
conexitate în grafuri orientate, drumuri minime și maxime în gr afuri orientate, iar la sfârșitul
capitolului sunt prezentate probleme cu aplicabilitate pra ctică, date la concursuri și olimpiade
școlare. Unele aplicații au fost tratate metodic, cu explic ații și rezolvarea în limbajul de
programare C++, iar ultimele le-am dat ca aplicații propuse.
Capitolul III tratează proiectarea activității didactice la disciplina „Informatică”
referindu-se la: obiectivele pedagogice și operaționale, m etode de învățământ folosite în
predarea disciplinei Informatica, mijloacele de învățământ ne cesare în predarea disciplinei,
evaluarea randamentului școlar, structura și tipologia lecției. De asemenea am prezentat și un
test de evaluare inițială. La sfârșitul capitolului am prez entat două proiecte didactice, primul cu
tema „Parcurgerea grafurilor neorientate în lățime”- lecție de predare/învățare
(comunicare/însușiri de noi cunoștințe) și al doilea cu tema ”Repre zentarea grafurilor orientate
cu matricea drumurilor” – lecție mixtă.
Am încercat în lucrarea mea de gradul I să prezint cât m ai multe exemple practice, am
folosit cât mai multe desene semnificative, pentru ca aceast ă lucrare să fie de un real folos atât
pentru mine ca profesor în activitatea didactică, cât și pe ntru elevii care studiază disciplina
„Informatica” în liceu.
5
Capitolul I
ELEMENTE DE TEORIA GRAFURILOR.
GRAFURI NEORIENTATE
1.1 GRAFURI NEORIENTATE – NOȚIUNI DE BAZĂ
Definiție : Se numește graf neorientat, o pereche ordonată de mulțimi (X,U), unde:
– X este o mulțime finită și nevidă de elemente numite vârfuri sau noduri;
– U este o mulțime de perechi neordonate de câte două elemente din X , numite
muchii.
Așadar, un graf neorientat poate fi reprezentat sub forma une i figuri geometrice
alcătuită din puncte (vârfuri, noduri) și linii drepte sau curbe care unesc ac este puncte (muchii).
{n cazul general, într-un graf neorientat G = (X, U) utilizăm notațiile :
– m → numărul muchiilor ; n → numărul vârfurilor ;
– X = {}nx xx ,…,,2 1 → mulțimea vârfurilor ;
– U = {}mu uu ,…,,2 1 → mulțimea muchiilor ;
– Dacă o muchie trece prin nodurile x și y, atunci ea se notează [x, y].
– muchie u k este o pereche neordonată [a, b] alcătuită din două elemente din X.
Definiție : Pentru o muchie u k = [a, b], vom spune că :
– vârfurile a și b sunt adiacente și se numesc extremitățile muchiei u k ;
– muchia u k și vârful a sunt incidente în graf. La fel, muchia u k și vârful b ;
– muchia [a, b] este totuna cu muchia [b, a] (nu existăo orientare a muchiei)
Definiție: Gradul unui vârf x, notat d(x), reprezintă numărul muchiilor care trec pr in nodul x
(muchii incidente cu nodul x).
Un varf care are gradul 0 se numește vârf izolat.
Un vârf care are gradul 1 se numște vârf terminal.
Teoremă: {ntr-un graf neorientat G = (X, U) cu n vârfuri și m muchii, suma gradelor tuturor
vârfurilor este egală cu 2 * numărul muchiilor.
6
.2)( …)()( )(
12 1 m xd xd xd xdnn
ii ⋅=+++=∑
=
Demonstrație: Fiecare muchie de forma [x i, x j] ( unde x i ]i x j sunt vârfuri, cu i, j ∈ {1,
2, …, n}), contribuie cu o unitate la gradul vârfului i ]i cu o unitate l a gradul vârfului j. A]adar
fiecare muchie adaugă două unități la suma gradelor. Cum [n g raf sunt m muchii, rezultăfoarte
clar căsuma gradelor este 2*m.
{n particular, suma gradelor este un număr par. De aici se deduce următorul corol ar.
Pentru orice graf neorientat G numărul vârfurilor de grad impar este p ar.
Exemplu :
Figura 1
Pentru graful G =(X, U) din figura 1 avem:
– X = { 1, 2, 3, 4, 5, 6, 7} → mulțimea vârfurilor ( nodurilor)
– U= { u 1, u 2, u 3, u 4, u 5} → mulțimea muchiilor
– Muchiile sunt : u 1 = [1, 2] ; u 2 = [2, 3] ; u 3 = [3, 4] ; u 4 = [2, 4] ; u 5 = [5, 6] ;
– d(1) = 1 ; d(2) = 3 ; d(3) = 2 ; d(4) = 2 ; d(5) = 1 ; d(6) = 1 ; d(7) = 0 ;
– vârful 7 este vârf izolat ;
– vâfurile 1, 5 și 6 sunt vârfuri terminale .
Definiție : Se numește lanț în graful G, o succesiune de vârfuri L = (z 1, z 2, …, z k), unde z 1, z 2,
…, z k ∈ X, cu proprietatea că oricare două vârfuri consecutive sunt adi acente, adică există
muchiile [z 1, z 2], [z 2, z 3],…, [z k-1, z k] ∈U.
Vârfurile z 1 și z k se numesc extremitățile lanțului, iar numărul de muchii care intră în
componența sa reprezintă lungimea lanțului.
Dacă vârfurile z 1, z 2, …, z k sunt distincte două câte două, lanțul se numește elementar.
In caz contrar, lanțul este neelementar.
7
Exemplu :
Figura 2
{n graful din figura 2 , putem distinge următoarele lanțuri:
L 1 = (1, 2, 3, 4) – lanț elementar
L 2 = (1, 2, 4, 3, 2, 3, 4) – lanț neelementar
L 3 = (2, 4, 3, 2, 1) – lanț neelementar
L 4 = (6, 5, 1, 2, 3, 4) – lanț elementar
Definiție: Se numește ciclu într – un graf, un lanț L = (z 1, z 2, …, z k) cu proprietatea că z 1 = z k și
muchiile [z 1, z 2], [z 2, z 3], …, [z k-1, z k] sunt distincte două câte două.
Dacă într – un ciclu, toate vârfurile cu excepția primului ș i a ultimului sunt distincte
două câte două, atunci ciclu se numește elementar. {n caz contrar, el este neelementar .
Exemplu: {n graful din figura 2 , putem distinge următoarele cicluri:
C1 = (2, 3, 4, 2) – ciclu elementar
C2 = (1, 2, 4, 3, 1) – ciclu elementar
C3 = (5, 2, 4, 3, 1, 5) – ciclu elementar
C4 = (1, 2, 3, 4, 2, 5, 1) – ciclu neelementar
C5 = (5, 2, 3, 4, 2, 1, 5) – ciclu neelementar
Observații: {n cadrul unui lanț, muchiile se pot repeta, dar în cadrul unui ciclu ele trebuie să
fie distincte.
1.2 REPREZENTAREA GRAFURILOR
NEORIENTATE
Considerăm un graf neorientat G = (X, U) cu m muchii ]i n vârfuri numerotate 1, 2, …, n.
Existămai multe metode de reprezentare a grafurilor neorienta te, dar cele mai cunoscute sunt:
matricea de adiacență, listele vecinilor, lista de adiacență]i vectorul de muc hii.
1. Matricea de adiacență
Este o matrice A cu n linii și n coloane, în care elementele a[i, j] se defines c astfel:
≠ ∃=altfeljicuji muchia dacajia, 0],, [ , 1], [
8
Exemplu : Pentru graful G=(X, U) din figura 3, matricea de adiacență asociată este:
Figura 3
Observație: Deoarece muchia [a, b] este totuna cu muchia [b, a], rezultă că
a[i, j] = a[j, i], oricare ar fi i, j }…,, 2, 1 { n∈ .
Proprietățile matricei de adiacență:
/head2right Este o matrice simetricăfațăde diagonala principală, adica a[i, j]=a[j, i], oricare ar fi
i, j ∈ {1, 2, …., n}, cu i≠j.
/head2right Pe diagonala principalătoate elementele sunt egale cu 0;
/head2right Suma elementelor de pe linia /coloana i reprezintăgradul nodului i;
/head2right Dacăelementele de pe linia/ coloana i sunt toate egale cu 0 atunci nodul este i zolat;
2. Listele vecinilor
Pentru fiecare nod i , cu i },…,2 , 1 { n∈ , formăm lista vecinilor lui i. Aceasta
cuprinde toate nodurile care sunt extremități ale muchiilor ce trec pri n nodul i.
Exemplu : Pentru graful G=(X, U) din figura 3 , prezentăm listele vecinilor ]i matricea de
adiacențăpentru a face o comparație.
coloana 1 2 3 4 linia nodul listele vecinilor
1
2
3
4
1
2
3
4 2
1, 3, 4
2, 4
2, 3
Observăm căfiecare linie i din listele vecinilor conține indicii coloanelor pe care se
găsesc valori de 1 [n linia i a matricii de adiacență.
3. Listele de adiacență
Această metodă este indicată în cazul în care graful are un număr mare de vârfuri și un
număr mic de muchii. Această metodă de reprezentare a grafurilor are două variante.
=
0110101011010010
A
=
0110101011010010
A
9
Varianta I.
Principiul acestei metode de memorare constă în: pentru fieca re vârf k se alcătuiește
lista vecinilor săi, notată L k.
Pentru un graf cu n vârfuri și m muchii, se construiește apoi un vector care conține
adresele celor n liste ale vecinilor fiecărui vârf, plus cele n liste propriu – zise. Întregul graf
poate fi privit ca un tablou T, bidimensional, cu 2 linii și n+2m coloane. Numărul de coloane
este stabilit ținând seama de faptul că pentru fiecare nod al grafului este necesară o coloană (
deci n coloane) și pentru fiecare muchie trebuie specificate cel e două noduri adiacente, (deci
încă 2m coloane). Se poate folosi alocarea static și dinamica.
Completarea tabloului se face astfel:
– prima linie T[1, j]:
a) dacă 1 ≤≤ ≤≤ j ≤≤ ≤≤ n, atunci T[1, j]=j;
b) dacă n+1 ≤≤ ≤≤ j ≤≤ ≤≤ n+2m , atunci T[1, j] conține elementele listelor L k;
– a doua linie T[2, j]:
a) dacă 1 ≤≤ ≤≤ j ≤≤ ≤≤ n, atunci T[2, j]=p, unde p este coloana unde se aflăprimul element
din lista L j, ( corespunzătoare fiecărui nod j).
b) dacă n+1 ≤≤ ≤≤ j ≤≤ ≤≤ n+2m , atunci
b1) T[1, j] nu este ultimul element al listei L j, atunci T[2, j] =p, unde p este
indicele coloanei unde se aflăelementul ce urmeazăvârfului T[1, j ] [n lista L k (
corespunzătoare fiecărui nod k).
b2) dacăT[1, j] este ultimul element al listei L k, atunci T[2, j] =0
(corespunzătoare fiecărui nod k).
Spre deosebire de reprezentarea prin matricea de adiac ență, reprezentarea prin liste de
adiacență folosește mai eficient memoria, dar căutarea efect ivă a muchiilor este mult mai
anevoioasă. Memoria necesară reprezentării este proportional cu suma dintre numărul de
noduri și numărul de muchii ale grafului, dar timpul de căutare al une i muchii este proporțional
cu pătratul numărului de vârfuri ( dacăgraful are n vârfuri, atunci un vârf
poate avea n-1 vârfuri adiacente).
Exemplu: Fie graful G =(X, U) din figura 4 cu n=5 vârfuri ]i m=6 muchii.
Figura 4
Pentru graful din figura 4 tabloul bidimensional T va avea 2 linii și 17 coloane ]i va avea
următoarea formă:
Pentru fiecare nod k , lista Lk a vecinilor săi este:
Vârful k Lista L k a vârfurilor adiacente cu vârful k
1 2, 3
2 1, 3, 4
3 1, 2, 4, 5
10
4 2, 3
5 3
Varianta II
O altăvariantăde reprezentare a unui graf G= (X, U) cu n noduri ]i m muchii, creează o
matrice L, numită matrice de legături, cu 2 linii și 2 coloane astfel:
– L[1, j] se completează cu toate elementele listelor L j, (corespunzătoare fiecărui nod
j în parte);
– L[2, j] se completează astfel:
a) Dacă L[1, j] nu este ultimul element al listei L j, atunci L[2, j] =p, unde p este
indicele coloanei unde se află elementul ce urmează vârfului L[1, j] în lista L j
(corespunzător fiecărui nod j în parte);
b) Dacă L[1, j] este ultimul element al listei L j, atunci L[2, j] =0 (corespunzător
fiecărui nod j în parte);
Indicele coloanei din L care conține primul element din lista L j se reține în coloana j a
unui tablou unidimensional CAP. Raționamentul este analog cu cel desc ris pentru tabloul T.
Așadar, se obține:
Întregul graf s-a reprezentat prin tabloul unidimensional CAP, i ndexat după noduri,
fiecare element j al său fiind un indice de coloană din lista nodurilor adiacente nodului j.
Ambele variante de reprezentare a listelor de adiacență pot folosi o alocare static dar și
o alocare dinamică a memoriei.
j 1 2 3 4 5 L1 L2 L3 L4 L5
6 7 8 9 10 11 12 13 14 15 16 17
T[1,j] 1 2 3 4 5 2 3 1 3 4 1 2 4 5 2 3 3
T[2,j] 6 8 11 15 17 7 0 9 10 0 12 13 14 0 16 0 0
j L1 L2 L3 L4 L5
1 2 3 4 5 6 7 8 9 10 11 12
L[1,j] 2 3 1 3 4 1 2 4 5 2 3 3
L[2,j] 2 0 4 5 0 7 8 9 0 11 0 0 j 1 2 3 4 5
CAP 1 3 6 10 12
11
4. Vectorul de muchii
Fiecare muchie a grafului poate fi privită ca o [nregistrare cu două c omponente: cele două
vârfuri care constituie extremitățile muchiei. Notând aceste extrem ități cu nod1 și nod2, putem
defini tipul de date tmuchie , astfel:
struct tmuchie { unsigned nod1, nod 2};
Graful în ansamblul său, este o mulțime de muchii, adică o mulțime de elemente de tipul
tmuchie . În consecință, definim graful ca un “vector de muchii”, adică un vector cu element e
de tipul tmuchie :
tmuchie v[30];
Numărul real de elemente este numărul de muchii m. Astfel, ele mentele efectiv folosite
ale vectorului vor fi v[1], v[2], …, v[m]. Fiecare element v[i] ( cu i =1, 2, …, m) este de tipul
tmuchie și reprezintă o muchie a grafului, având două componente:
v[i].nod1 ]i v[i].nod2 reprezentând extremitățile muchiei i din graf.
1.3 CLASE SPECIALE DE GRAFURI
NEORIENTATE
Definiție: Fie graful G = (X, U). Un graf parțial al lui G, este un graf G 1 = (X,V), cu V ⊆U.
Altfel spus, un graf parțial G 1 al lui G, este chiar G, sau se obține din G păstrând toate vârfurile
și suprimând niște muchii.
Exemplu: Fie graful G =(X, U) din figura 5 , unde X= {1, 2, 3, 4, 5, 6, 7} ]i
U ={ u 1, u 2, u 3, u 4, u 5 }. Construim alăturat graful parțial obținut prin eliminarea muchii lor ce
trec prin vârful 4. ( figura 6 ) Acesta este G1=( X, V), unde X= {1, 2, 3, 4, 5, 6, 7} ]i V ={ u 1,
u2, u 5 }. S-au eliminat muchiile u 3 ]i u 4, care trec prin nodul 4.
Figura 5 Figura 6
12
Definiție: Fie graful G = (X, U). Un subgraf al lui G, este un graf G 1 = (Y, T), unde Y ⊂ X și
T ⊂U, iar T va conține numai muchiile care au ambele extremităț i în Y. Altfel spus, un
subgraf G 1 al lui G, se obține din G eliminând niște vârfuri și păstrând doar acele muchii care
au ambele extremități în mulțimea vârfurilor rămase.
Exemplu: Fie graful G =(X, U) din figura 5 , unde X= {1, 2, 3, 4, 5, 6, 7} ]i
U ={ u 1, u 2, u 3, u 4, u 5 }. Construim subgraful obținut prin eliminarea vârfurilor 5, 6 ]i 7.(
figura 7 ) Acesta este G1=( Y, T), unde Y= {1, 2, 3, 4} ]i T ={ u 1, u 2, u3, u 4}. S-au eliminat
vârfurile 5, 6 ]i 7, precum ]i muchia u 5, care trece prin aceste noduri.
Figura 5 Figura 7
Definiție: Se numește graf complet cu n vârfuri, notat K n , un graf G= (X, U) cu proprietatea
că oricare două vârfuri sunt adiacente, adică:
Uyx muchia Xyx ∈ ∃⇒∈∀ ],[ ,)(
Exemplu : Fie următorul graf neorientat: G=(X, U).
Figura 8
Graful neorientat din figura 8 este complet deoarece între oricare două vârfuri ale sale
există muchii care le leagă și se noteaza K 5
1
2
3 4 5
13
1 4
2 5
3 6
7
Proprietățile grafurilor complete:
1. d(1) = d(2) = … = d(n) =n-1;
2. Dintre toate grafurile cu n noduri, K n are numărul maxim de muchii.
Teoremă: Un graf complet cu n vârfuri, are 2) 1 ( *−nn muchii.
Definiție : Un graf G = (X, U) se numește bipartit dacă există două mulțimi nevide A si B
incluse in X astfel încât:
/head2right X=A U B,
/head2right A ∩ B = Φ
/head2right toate muchiile grafului G au o extremitate în A iar cealaltă în B.
Exemplu: Fie graful G =( X, U), unde X={1, 2, 3, 4, 5, 6, 7} iar U ={u 1, u 2, u 3,u 4};
Considerăm mulțimile: A = {1, 2, 3} ]i B= {4, 5, 6, 7}. Generăm graful b ipartit următor (
figura 9):
Figura 9
Se observă că proprietățile grafului bipartit sunt îndeplini te adică: X=A U B, A ∩ B = Φ, iar
fiecare muchie are o extremitate în A și o extremitate în B.
Teoremă: Un graf este bipartit dacă și numai dacă nu conține cicluri impare.
Definiție: Un graf bipartit se numește graf bipartit complet dacă pentru orice vârf x din A și
orice vârf y din B, există muchia [x, y] ( unde A și B sunt două su bmulțimi care partiționează
mulțimea vârfurilor X).
14
Exemplu: Fie graful G =( X, U), unde X={1, 2, 3, 4, 5} iar U={u 1, u 2, u 3, u 4, u5, u6}.
Considerăm mulțimile: A = { 1, 2 } ]i B= { 3, 4, 5} care generează g raful bipartit complet
urmator:
Figura 10
1
4
2 5 3
15
1.4 PARCURGEREA GRAFURILOR
NEORIENTATE
Prin parcurgerea unui graf neorientat se înțelege vizitarea vâ rfurilor într-o anumitâ ordine,
dată de un anumit criteriu.
Există două metode de parcurgere:
• Parcurgerea în lățime BF (Breadth First);
• Parcurgerea în adâncime DF (Depth First);
Algoritmul de parcurgere în lățime BF
Algoritmul de parcurgere în lățime cunoscut și sub numele de alg oritmul lui Moore
acționează asupra unui graf neorientat G=(X,U) cu un vârf fixat x ∈X. Acesta calculează
distanțele de la vârful x la toate vârfurile la care se poa te ajunge plecând din x pe lanțuri
din G. Inițial, toate vârfurile sunt neetichetate.
Ideea algoritmului de parcurgere în lățime este:
– plecând din vârful x se vizitează fiecare vârf adiacent c u x, după care se vizitează toate
vârfurile adiacente cu acesta care nu au fost vizitate încă. În continuare se alege primul vârf
adiacent cu vârful de pornire și se vizitează toate vârfurile a diacente cu acesta nevizitate
încă; se continuă în acest mod până când vizităm toate vârfurile accesibile din x.
Exemplu: Fie graful neorientat G= (X, U) din figura 12
Figura 12
Vom parcurge în lățime acest graf pornind de la vârful de start 1:
Pa]ii parcurgerii Noduri vizitate
/head2right vizităm mai întâi vârful de start 1; 1
/head2right vizităm apoi vecinii lui 1, care sunt 2, 5 și 6 2, 5, 6
/head2right Pentru fiecare dintre acești vecini ai lui 1, vizităm vecinii s ăi
16
nevizitați încă:
– vecinii lui 2 sunt 1, 3 și 4, dar nevizitați sunt numai 3 și 4
– vecinii lui 5 sunt 1, 2 și 7, dar nevizitat este numai 7;
– vârful 6 nu are vecini nevizitați;
3, 4
7
/head2right Am vizitat până acum vecinii vârfurilor 1, 2, 5 și 6. Mai trebuie
vizitați vecinii noilor vârfuri care au fost vizitate la pasul anterior și
anume vecinii vârfurilor 3, 4 și 7. Observăm că aceste vârfuri nu mai au
vecini nevizitați, deci parcurgerea se încheie.
Pentru vârful de pornire 1, atunci parcurgerea BF este: 1, 2, 5, 6, 3, 4, 7.
Pentru vârful de pornire 3 avem următoarea parcurgere: 3, 2, 4, 1, 5, 6, 7
Pentru implementarea algoritmului vom folosi un vector c=(c 1, c 2, …, c k) care are
proprietățile unei cozi. Capetele de introducere ]i extrager e vor fi identificate prin pozițiile
p ]i respectiv u. Introducem mai [ntâi nodul de start [n coadă, apoi [n mod repetat până la
vizitarea tuturor nodurilor:
/head2right extragem din coadă vârful aflat [n capatul de extragere ]i [l vizităm;
/head2right introducem [n coadă, pe la celălalt capăt, capătul de introduce re, vecinii nevizitați ai
vârfului tocmai extras.
Să urmărim evoluția cozii pentru acela]i graf din figura 12 :
In continuare, se vor extrage pe rând vârfurile 6, 3, 4, 7. Nic i unul dintre aceste vârfuri nu
mai are vecini nevizitați, deci nu se va mai introduce nimic în coadă. În concluzie capătul de
introducere u nu se mai modifică rămânând 7. 1 p = u = 1 Introducem în coadă vârful de start 1
1 2 5 6 p=2, u=4. Extragem vârful 1 și
introducem vecinii săi nevizitați
2, 5 și 6
1 2 5 6 3 4 p=3
u=6
1 2 5 6 3 4 7 Extragem 2 și introducem vecinii săi nevizitați 3 și 4
Extragem 5 și introducem unicul său vecin nevizitat 7
p=4
u=7
17
Observații:
/head2right extragerea unui vârf nu [nseamnă eliminarea lui fizică din coa dă, ci este o simulare, ea
realizându-se numai prin deplasarea către dreapta a capătului de extragere p prin mărirea lui cu
o unitate, adica p=p+1;
/head2right după extragerea ultimului vârf de pe poziția 7, capătul de ext ragere p devine 8, deci se va
muta dincolo de capătul de introducere 7. {n concluzie ciclul ai cărui p a]i au fost descri]i mai
sus se execută cât timp p<=u.
Notăm cu n numărul de noduri din graf. Este necesar ca elementele matricei de adiacență a cu
n linii*n coloane să fie cunoscute.
Mai avem nevoie de un vector viz cu n elemente, în care elementele viz[k]
(k=1, 2, …, n) au semnificația:
=contrarcazindacakviz, 0at fost vizit ak varful , 1][
Mai întâi inițializăm tot vectorul viz cu 0 deoarece nici un vârf nu a fost vizitat .
Inițial în coadă se găsește vârful de pornire:
p=1, u=1, c[p]=x, viz[x]=1.
Cât timp mai sunt elemente în coada (“while (p<=u)”):
/head2right Extragem din coadă vârful aflat în capătul de extragere u, și-l memorăm în tr-o variabila
z: {z=c[p]}; Evident la primul pas, z va fi c[1] adică nodul de start prim.
/head2right Căutăm vecinii nevizitați ai lui z și îi introducem în coadă:
Pe linia z în matricea de adiacență a căutăm vecinii lui z. Elementele a[z][1], a[z][2], …,
a[z][n] care sunt 1, ne indică vecinii lui z. Pentru a introduce în coadă vecinii găsiți
pentru vârful z trebuie ca aceștia să nu fie vizitați.
Reprezentarea algoritmului în pseudocod
intregi c[20],viz[20], p, u, v, i, j, prim, a[20][20]
citirea matricei de adiacență din fi]ierul text “adiacent.txt”
pentru i /barb2left 1,n executa
viz[i] /barb2left0
c[i] /barb2left0
citeste prim // fie prim nodul de start
18
C[1] /barb2leftprim
p /barb2left1 // reprezintă poziția elementului cheie
u /barb2left1 // reprezintă poziția ultimului element din coadă
viz [prim] /barb2left1
Cat timp (p< = u) executa
v /barb2leftc[p]
Pentru j /barb2left1, n executa
Daca (a[v][j]=1) si (viz[j]=0) atunci
u /barb2leftu+1
c[u] /barb2leftj
viz[j] /barb2left1
p /barb2leftp+1
pentru i /barb2left1, u executa
scrie c[i]
Reprezentarea algoritmului în limbajul C++
#include<fstream.h>
#include<conio.h>
int a[10][10], n, m ;
void parcurgere_bf( ) // parcurgerea în lățime
{int j, i, c[20], viz[20], prim, u, v;
cout<<” Dati nodul de start: ”<<endl;
cin>>prim;
for (i=1; i<= n; i++)
{ c[i] =0;
viz[i]=0;}
p= 1; u=1; c[p] =prim; viz[prim]=1;
while (p <= u)
{v = c[p];
for (j=1; j<=n; j++)
if(a[v][j]= =1 && viz[j]= =0) / /îl adaug pe j în coadă dacă este vecin pentru v
îi nu a fost vizitat
{u ++;
19
c[u]=j;
viz[j]=1;}
p ++; }
}
void main()
{clrscr ( );
fstream f ( “adiacent.txt” , ios::in); // elementele matricii de adiacență și
valorile n , m se gasesc în fișierul adiacență.txt
f>>n>>m;
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
f>>a[i][j] ;
cout<<"matricea de adiacenta este : "<<endl; // afișare matrice de adiacență
for( i=1; i<=n; i++)
{for(j=1; j<=n; j++)
cout<<a[i][j]<<" ";
cout<<endl; }
parcurgere_bf ( );
for(i=1; i<=u; i++) // afi]area cozii
cout<<c[i]<<" ";
getch( );
}
Algoritmul de parcurgere [n adâncime DF
Algoritmul de parcurgere în adâncime a unui graf neorientat est e util în rezolvarea
diferitelor probleme care se referă la grafuri. El a fos t propus de Trémaux în secolul al XIX –
lea ca o tehnică de rezolvare a amuzamentelor matematice leg ate de parcurgerea labirinelor. O
versiune a acestui algoritm a fost propusă de Hopcroft și Tarjan.
Ideea algoritmului de parcurgere în adâncime este:
– se pornește de la un nod x și se alege primul dintre vecinii nevizitați ai acestuia;
algoritmul continuă până se ajunge la un nod care are toți vecinii vizitați. În cazul în care un
vârf nu mai are vecini nevizitați atunci ne întoarcem la nodul ant erior, iar pentru acel nod
căutam următorul vecin nevizitat al său. Vom folosi etichete pe ntru a recunoaște faptul că ne-
am întors într – un vârf deja vizitat.
20
1
2 3
5
8 6 4
7
1
2 3
5
8 6 4
7
1
2 3
5
8 6 4
7
Figura 15 Exemplu: Fie graful neorientat G= (X, U) din figura 13
Figura 13
Algoritmul folosește o structură de tip stivă în care va introdu ce (sau elimina) nodurile
vizitate din graf și un vector cu n componente numit viz pentru marcarea nodurilor vizitate.
Inițial vectorul viz are toate valorile nule:
viz =
Vom parcurge în adâncime acest graf pornind de la vârful de sta rt 4. Se introduce în
stivă nodul de start. Se afi]ează nodul 4 și se marchează ca fiind vizitat.
Se determină primul dintre vecinii nodului din vârful stivei, se măre ște cu o unitate
vârful stivei și pe această poziție se înregistrează nodul 1.
Se afișează nodul 1 și se marchează ca fiind vizitat.
Se determină primul dintre vecinii nevizitați ai nodului 1; acesta este nodul 2, se
mărește cu o unitate vârful stivei; pe noua poziție din stivă se înregistrează nodul 2. Se
afișează nodul 2 și se marchează ca fiind vizitat
1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0
1 2 3 4 5 6 7 8
0 0 0 1 0 0 0 0
1 2 3 4 5 6 7 8
1 0 0 1 0 0 0 0
1 2 3 4 5 6 7 8
1 1 0 1 0 0 0 0 viz= ps 4 S:
viz=
S:
ps
4 1
S:
ps
4 1 2
viz=
21
1
2 3
5
8 6 4
7
Figura 16
1
2 3
5
8 6 4
7
Figura 17
1
2 3
5
8 6 4
7
Figura 18
Se încearcă determinarea unui vecin nevizitat al nodului 2. Singurul vecin al nodului
2 este nodul 1 care a fost deja vizitat. Se extrage din stivă nodul 2 și se micșorează cu o
unitate vârful stivei ( figura 16)
Se determină primul dintre vecinii nevizitați ai nodului 1; acesta este nodul 3
( nodul 2 a fost deja vizitat); se mărește cu o unitate vârful stivei și pe noua poziție se
înregistrează nodul 3. Se afișează nodul 3 și se marchează ca fiind vizitat.
Se determină primul dintre vecinii nevizitați ai nodului 3; acesta este nodul 5; se
mărește cu o unitate vârful stivei și pe noua poziție se înre gistrează nodul 5. Se afișează
nodul 5 și se marchează ca fiind vizitat.
1 2 3 4 5 6 7 8
1 1 1 1 0 0 0 0
1 2 3 4 5 6 7 8
1 1 1 1 1 0 0 0 S:
ps
4 1
S:
ps
4 1 3
viz=
S:
ps
4 1 3 5
viz=
22
Algoritmul continuă cu determinarea vârfurilor nevizitate până când stiva este vidă.
Pentru graful de mai sus parcurgerea in adancime plecand de la varful 4 este: 4, 1, 2, 3, 5,
6, 8, 7.
Pentru implementarea algoritmului vom folosi:
– un vector s=(s 1, s 2, …, s k) care reprezintă stiva. Astfel există, în orice moment,
posibilitatea de a ajunge de la vârful curent la primul dintr e vecinii săi nevizitați încă,
acesta din urmă plasându – se în vârful stivei. De la acest vâr f se continuă parcurgerea în
același mod.
– un vector urm care determină, la fiecare pas, următorul vârf ce va fi vizita t după vârful k.
Pentru a-l determina, se parcurge linia k din matricea de adiac ență A asociată grafului,
începând cu următorul element, până se găsește un vecin j al lui k, nevizitat înc ă.
Dacă nu se poate determina un astfel de vârf, se coboară în st ivă, încercând să se aplice
același procedeu următorului element al stivei.
– un vector viz cu n elemente, în care elementele viz[k] (k=1, 2, …, n) au semnificația :
=contrarcazindacakviz, 0at fost vizit ak varful , 1][
Notăm cu n numărul de noduri din graf. Este necesar ca elementel e matricei de
adiacență a cu n linii*n coloane să fie cunoscute.
Folosind o structură de tip stivă, prelucrarea unui vârf aflat la un capăt al stivei constă în
introducerea, în același capăt al ei, a tuturor vârfurilor j vec ine cu k nevizitate încă. Pentru
început k este varful de start.
Capătul de introducere și extragere va fi identificat prin poziția p.
Mai întâi inițializăm vectorul viz cu 0 deoarece nici un vârf nu a fost vizitat și vectorul
urm cu 0 deoarece pornind din 0 determinăm prima valoare posib ilă pentru primul vârf spre
care se poate pleca din vârful j.
Introducem mai întâi nodul de start în stivă, acesta se reține ca vârf curent, se
marchează și se afișează.
Cât timp stiva este nevidă, se analizează vârful curent:
/head2right Dacă vârful curent mai are vecini nevizitați:
o se adaugă în stivă vârful j, primul dintre vecinii nevizitați ai vârfului curent și se
afișează;
23
o vârful j devine vârf curent.
/head2right Dacă nu există un astfel de vârf:
o se extrage din stivă vârful curent;
o vârful precedent celui curent devine vârf curent, dacă stiva nu este vidă.
Observații:
♦ deoarece în cazul în care un vârf are mai mulți vecini se poate alege oricare dintre aceștia,
se pot obține mai multe parcurgeri DF.
♦ Pentru a elimina acest neajuns, se face convenția ca vecinii vârf ului curent să se adauge în
stivă în ordinea crescătoare a notării lor.
Reprezentarea algoritmului în pseudocod
intregi s[20],viz[20], urm[20], p, n, m, k, i, j, x, y, prim, a[20][20]
se citesc cele m muchii ale grafului ]i se construie]te matricea de adia cență
asociată grafului
pentru j /barb2left 1,n executa
viz[j] /barb2left0
urm[j] /barb2left0
citeste prim // fie prim nodul de start
s[1] /barb2leftprim
p /barb2left1 // reprezintă pointerul de stivă care indică elementul curent
viz [prim] /barb2left1
scrie prim
Cat timp (p> = 1) executa // stiva este nevidă
j /barb2lefts[p] // scoate nodul din vârful stivei
k/barb2left urm[j]+1
cat timp k<=n si (a[j][k]=0 sau a[j][k]=1 si viz[k]=1) k /barb2leftk+1
// determină primul dintre vecinii k ai lui j nevizitați [ncă
urm[j] /barb2leftk
daca k=n+1 atunci p /barb2leftp-1 // dacă nu s-a găsit un element se coboară [n
stivă
altfel
scrie k
viz[k] /barb2left1
p /barb2leftp+1
s[p] /barb2leftk
24
Reprezentarea algoritmului în limbajul C++
#include<iostream.h>
#include<conio.h>
int a[10][10], n, m, k, p, i, j, s[20], urm[20], viz[20];
void init( )
{ int i, j;
for(i=1; i<=n; i++)
{viz[i]=0; // inițializăm vectorii viz și urm cu 0 precum și elementele din matr icea a
urm[i]=0;
for(j=1; j<=n; j++)
a[i][j]=0;}}
void complet( )
{int x, y, i;
for(i=1; i<=m; i++)
{cout<<"muchia"<<i<<"este";
cin>>x>>y; // determinăm matricea asociată grafului prin citirea celor m muchii
a[x][y]=1; a[y][x]=1;}}
void prelucrare( ) // parcurgem graful cu metoda DF
{int j;
j=s[p]; k=urm[j]+1;
while(k<=n && a[j][k]==0 || (a[j][k]==1 && viz[k]==1) )
k=k+1; urm[j]=k;
if(k==n+1)
p=p-1;
else
{cout<<k<<" ";
viz[k]=1; p=p+1; s[p]=k;}}
void main( )
{ clrscr ( );
cin>>n>>m;
init( );
complet( );
cout<<"vf de start=";
cin>> start;
25
s[1]=start;
p=1;
viz[start]=1;
cout<<"parcurgerea grafului prin metoda df este"<<start;
while(p>=1)
prelucrare( );
}
26
1.5 CONEXITATE ÎN
GRAFURI NEORIENTATE
Parcurgând [n lățime graful din figura 19 pornind de
la vârful 1 obținem următoarea succesiune: 1, 2, 5, 6, 3, 4,
7. Am obținut o proprietate importantă a grafului: faptul că
în urma parcurgerii au fost vizitate toate vârfurile.
Observație : Luând oricare două vârfuri, putem găsi cel puțin un traseu care p ornește dintr-un
vârf și ajunge în celălalt. Luând oricare două vârfuri, ele pot fi legate printr-un lanț.
Definiție: Un graf G este conex dacă oricare ar fi două vârfuri distincte ale sale, există un lanț
care le leagă.
Observație : Într-un graf conex, luând oricare două vârfuri, putem găsi cel puțin un tra seu
(lanț) care pornește dintr-un vârf și ajunge în celălalt. Dar nu toate grafurile sunt conexe. În
schimb putem desprinde din el “porțiuni” care, fiecare luată separat, e ste un graf conex.
Definiție : Se numește componentă conexă a grafului G= (X, U), un subgraf
G1= (X 1, U 1) a lui G, conex, cu proprietatea că nu există nici un lanț car e să lege un vârf din X 1
cu un vârf din X-X 1.
Exemplu : Fie graful neorientat din figura 20
Figura 20
În acest exemplu există 3 componente conexe
– G1 =(X 1, U 1), cu X 1={1, 2, 3, 4} și U 1={u 1, u 2, u 3, u 4}
– G2 =(X 2,U 2), cu X 2={5, 6} și U 2={u 5}
– G3 =(X 3,U 3), cu X 3={7} și U 1= Ø Figura 19
27
Teoremă: Fie G= (X, U) un graf conex și k numărul de muchii ale lanțului elementar de
lungime maximă. Oricare două lanțuri elementare diferite de lun gime k ( dacă există ) au cel
puțin un vârf comun.
Demonstrație: presupunem prin reducere la absurd că există două lanțuri ele mentare de
lungime maximă, disjuncte; fie lanțurile L 1 și L 2. Notăm prin l (L) lungimea lanțului L. ⇒
l(L 1) = l(L 2)=k.
Deoarece G este graf conex, [ntre oricare două vârfuri a și b din L 1, respectiv L 2, există
un lanț. Dintr –un asemenea lanț putem obține un lanț elementar Q c are are extremitățile x și y
în L 1 respectiv L 2 și care nu mai conține alte vârfuri din L 1 și L 2.
Vârful x împarte lanțul L 1 în două sublanțuri L 11 și L 12 ( unul din ele eventual vid).
Presupunem că L 11 este sublanțul de lungime maximă, deci l (L 11 ) ≥ k/2
Aplicăm același raționament pentru lanțul L 2 și presupunem că L 22 este sublanțul de
lungime maximă adică l(L 22 ) ≥ k/2. Construim un nou lanț elementar L reunind lanțurile L 11 , Q
și L 22 . Observăm că lungimea lanțului L este: l(L) ≥ (k/2)+(k/2)+1 ⇒ l(L) ≥ k+1.
Presupunerea făcută este falsă.
Propoziție: Un graf este conex dacă și numai dacă are o singură componentă conexă.
Demonstrație:
” ⇒”graful G este conex, înseamnă că pentru oricare două vârfurile x i și x j există un lanț care
le conține, deci există o singură componentă conexă.
“⇐” dacă graful G are două componente conexe X i și X j înseamnă că vârfurile x i și x j nu se
află pe același lanț, adică nu există un lanț care să unească vârfurile x i și x j. În acest caz graful
nu este conex. ( fals).
Verificarea conexității unui graf
Se citește matricea de adiacență a unui graf neorientat cu n vârfuri și se cere să se
afișeze toate componentele conexe precum și numărul acestora. Î n rezolvarea problemei se va
utiliza parcurgerea grafului în lațime BF.
Algoritmul este următorul:
1. Se alege un vârf de start și se inițializează cu 0 numărul componentelor conexe nc.
2. Se incrementează nc cu 1. Plecând din vârful de start, se vizitează graful cu algori tmul BF,
obținându-se astfel o componentă conexă, care se afișează.
– dacă au mai rămas noduri nevizitate în urma parcurgerii anteri oare, se alege alt nod de
start din rândul nodurilor nevizitate și se reia pasul 2.
– dacă toate nodurile au fost vizitate, se trece la pasul 3.
3. Se testează nc. Dacă acesta este 1, rezultă că graful este conex.
28
Pentru a implementa algoritmul [n limbajul C++ se folosesc următoarele func ții:
– citire_ graf( ) – care permite citirea numărului de vârf uri și de muchii ale grafului precum și
muchiile acestuia pentru a construi matricea de adiacență.
– afișare_ matrice( ) – afișează matricea de adiacență asociat ă grafului
– parcurgere_bf( ) – funcția realizează o parcurgere a graf ului folosind algoritmul de parcurgere
în lățime BF.
– nevizitat( ) verifică dacă în graf mai există vârfuri neviz itate în urma parcurgerii BF
anterioare, utilizând vectorul viz .
Reprezentarea algoritmului [n limbajul C++
#include<iostream.h>
#include<conio.h>
int a[10][10], c[20], viz[20], prim, p, nc;
void citire_ graf( )
{int m, i, j, k, x, y, n;
clrscr( ) ;
cout<< “ Numarul de varfuri : ”; cin>>n;
cout<<endl<<”Numarul de muchii: ”; cin>>m;
for ( i=1; i<=n; i++)
for ( j=1; j<=n; j++)
a[i][j]=0;
for ( k=1; k<=m; k++)
{ cout<<endl<<” dati muchia “<< k<< “ :”;
do { cin>>x>>y; }
while (x<1 || x>n ||y<1 ||y>n);
a[x][y]=1; a[y][x]=1;}}
void afisare_matrice( )
{ int i, j;
cout<<"matricea de adiacenta este : "<<endl;
for( i=1; i<=n; i++)
{for(j=1; j<=n; j++)
cout<<a[i][j]<<" ";
cout<<endl; }}
int nevizitat ( ) // parcurge tabloul viz și returnează primul nod nevizitat sau –1 dacă nu mai
sunt noduri nevizitate
{int prim_nev=1, j=1;
29
while ( j<=n && prim_nev ==-1)
{ if (viz[j]==0) prim_nev=j;
j++;}
return prim_nev;}
int parcurgere_bf(int prim ) //verifică dacă graful este conex returnând 1 sau 0
{int k, z, p, u;
for (k=1; k<= n; k++)
{ c[k] =0; viz[k]=0;}
p= 1; u=1; c[p] =prim; viz[prim]=1;
while (p <= u)
{v = c[p];
for (k=1; k<=n; k++)
if(a[v][k]= =1&& viz[k]= =0)
{u ++; c[u]=k; viz[k]=1;}
p ++; }
cout<<endl;
for( k=1; k<=u; k++)
cout<<c[k]<<” “;
if (nevizitat ( )==-1) return 1;
else return 0;}
void main()
{ citire_graf( ) ; afisare_matrice ( ) ;
cout<<endl<<” dati varful de plecare”; cin>> prim;
cout<< endl<< “ afisarea componentelor conexe “;
for (p=1; p<=n ; p++)
viz[p]=0; nc=0;
do { nc++; parcurgere_bf (prim );
cout<<endl;
prim= nevizitat( ); }
while ( prim!=-1);
cout <<endl<<” sunt “<<nc<<” componente conexe”;
if (nc==1) cout<<endl<<” graful este conex”;
else cout<< endl<< “ graful nu este conex”;
getch( );
}
30
1.6 APLICA|II
Problema – Labirint
Enunț: Se consideră un labirint, sub formă de matrice, cu n linii ș i n coloane, citit de program
dintr-un fișier text sub forma:
8 Prima linie reține numărul de linii ( coloane)
*ooooooo
**o**o** O cameră este reprezentată prin:
*ooo*o** * camera este ocupată
ooooo*** o camera este liberă
****oooo
oo*o****
oooooooo
o*o*o*o*
Două camere ale labirintului sunt învecinate dacă amândouă rețin o ș i au o muchie
comună. Se cere ca labirintul să fie transformat într –un graf neorientat prin respectarea
următoarelor condiții:
a) nodurile sunt numerotate în ordine 1, 2, …, n
b) dacă două camere sunt învecinate, atunci cele două noduri sunt adiacente.
c) graful va fi obținut prin matricea ponderilor forma 1, în care orice muchie are ponderea
1.
Matricea ponderilor va avea n*n linii și n*n coloane.
Rezolvare:
Citirea labirintului din fișier se face prin crearea unei matrici a stfel:
=o adica libera camera avem dacaocupata camera avem dacajiL, , 1* adica , , 0], [
Pe baza acestei matrici și a regulilor din enunț vom construi matricea p onderilor astfel:
– se inițializează cu INFINIT matricea a;
– cum avem n 2 noduri la generarea matricei ponderilor ne vom referi la config urația
labirintului astfel: pentru un nod i, avem
lin=(i-1) div n +1 și col =(i-1) mod n +1
Se verifică vecinii acestor căsuțe din labirint, anume:
31
LIN-1, COL
LIN, COL-1 LIN, COL LIN, COL +1
LIN +1, COL
– nodul reprezentat de (LIN, COL) este p= n* (LIN-1)+ COL. În ace st fel se verifică
toate camerele vecine pentru fiecare cameră ]i se completează ma tricea ponderilor.
Exemplu de construire a grafului asociat unui labirint:
Labirint Graful asociat:
* * o
* o o
o o *
sau Labirint:
0 0 1
0 1 1
1 1 0
Matricea ponderilor va fi simetrică, graful fiind neorientat.
Program C++
#include<iostream.h>
#include<fstream.h>
#define INFINIT 1000
int L[13][13], a[169][169], n, i, j;
void main()
{ char ch;
int l, c;
fstream f( “lab.in”, ios::in);
f>>n;
cout<<”labirint:”<<endl;
for (i=1; i<=n; i++)
{ for(j=1; j<=n; j++)
{ f>>ch;
if (ch==’*’) L[i][j]=0;
if(ch==’o’) L[i][j]=1; 0 11 0 1 11 00 1 11 1 001 000
INF INF INF INF INF INF INFINF INF INF INF INFINF INF INF INF INF INF INFINF INF INF INF INF INFINF INF INF INF INF INFINF INF INF INF INF INF INF INFINF INF INF INF INF INF INFINF INF INF INF INF INF INF INFINF INF INF INF INF INF INF INF
32
cout<<L[i][j]<<” “;}
cout<<endl;}
cout<<endl<<” graful asociat:”<< endl;
for (i=1; i<=n*n; i++)
for(j=1; j<=n*n; j++)
a[i][j]=INFINIT;
for (i=1; i<=n*n; i++)
{ l=(i-1)/n+1; c=(i-1)%n+1;
if( L[l][c]==1) {
if( c-1>=1 && L[l][c-1]==1) {
a[n*(l-1)+c-1][i]=1; a[i][n*(l-1)+c-1]=1;}
if (c+1<=n && L[l][c+1]==1) {
a[n*(l-1)+c+1][i]=1; a[i][n*(l-1)+c+1]=1;}
if (l-1>=1 && L[l-1][c]==1) { a[i][n*(l-2)+c]=1; a[n*(l-2)+c][i]=1;}
if (l+1<=n && L[l+1][c]==1) { a[n*l+c][i]=1; a[i][n*l+c]=1;}
}
a[i][i]=0;}
for( i=1; i<=n*n ;i++)
{ for (j=1; j<=n*n; j++)
if( a[i][j]==INFINIT) cout<<” INF “;
else cout<<a[i][j]<<” “;
cout<<endl;}
}
Probleme propuse spre rezolvare :
1. Să se scrie un algoritm bazat pe parcurgerea DF, care să verifice conexitatea, afișează
numărul de componente conexe și nodurile fiecărei componente. Citim din fișierul
CONEX.IN, valoarea n, urmată de matricea de adiacență (n linii , n elemente pe fiecare
linie).
2. Se citesc de la tastatură m perechi de numere întregi rep rezentând extremitățile
muchiilor unui graf neorientat cu n noduri. Verificați dacă o secvență de noduri dată
reprezintă sau nu un ciclu eulerian. Mesajul final se afișează pe ecran.
33
Capitolul II
ELEMENTE DE TEORIA GRAFURILOR.
GRAFURI ORIENTATE
2.1 GRAFURI ORIENTATE – NOȚIUNI DE BAZĂ
Un exemplu de graf orientat este rețeaua de străzi a unui oraș. Străzile sunt muchii în
graf, iar intersecțiile reprezintă vârfurile grafului. Întrucât mergând pe jos ne putem deplasa pe
orice stradă în ambele sensuri, vom spune că din punctul de vedere al pietonilor, „graful unui
oraș” este neorientat .
Cu totul altfel stau lucrurile în ceea ce privește conducătorii auto, pentru că în orice
oraș există străzi cu sens unic. Pentru un șofer străzile tre buie să primească în graf o anumită
orientare. Desigur că acele străzi pe care se poate cir cula în ambele sensuri vor primi orientare
dublă. Am ajuns astfel la noțiunea de graf orientat .
Definiție : Numim graf orientat , o pereche ordonată de mulțimi G=(X,U), unde:
– X este o mulțime finită și nevidă numită mulțimea nodurilor (vârfurilor);
– U este o mulțime formată din perechi ordonate de elemente ale lui X, numită mulțimea
arcelor
Observați i:
Prin noțiunea de perechi ordonate nu trebuie
să înțelegem că o muchie este mai mare decât alta, ci
pur și simplu că facem deosebire între o muchie de
forma (x,z) și o alta de forma (y,x). Cu alte cuvinte
muchiile sunt diferențiate prin ordinea de scriere a
simbolurilor.
Arcul (x,y) nu este tot una cu arcul (y,x).
Exemplu:
Pentru graful G=(X,U) din figura 1. avem:
X={1, 2, 3, 4} și U={u1, u2, u3, u4, u5, u6, u7,}=
{(1,1), (2,1), (3,2), (2,3), (2,4), (3,4), (3,4)}
Arcul va fi de forma u= (x,y), unde:
– x se numește extremitate inițială,
– y se numește extremitate finală a arcului.
Figura1
U3 U2
U4 U5
U6 U1
U7 3
4 1
2
34
Cu alte cuvinte, “arcul iese din nodul x și intră în nodul y”. La fel ca la grafurile
neorientate, vom spune că nodurile x și y sunt adiacente, iar arcul u și nodul x sunt incidente
(la fel arcul x și nodul y). Nodul y se numește succesor al lui x, iar nodul x se numește
predecesor al lui y. Un arc de forma (x,x), care iese din nodul x și intră tot x, se numește
buclă .
Exemplu:
În graful din figura 1, avem bucla (1,1).
Într-un graf putem avea două sau mai multe arce identice.
Exemplu :
În graful din figura 1, există două arce identice, u6 = u7 = (3,4)
Definiție : Se numește p-graf, un graf orientat în care numărul arcelor i dentice este mai mic
sau egal cu o valoare dată p.
În cele ce urmează vom analiza numai 1-grafuri fără bucle.
Gradul unui vârf. Mulțimile Γ și ω
Definiție : Gradul exterior al unui vârf x, notat d*(x), reprezintă numărul arcelor care ies din
nodul x, adică numărul arcelor de forma (x,z) ε U.
Analog, se definește gradul interior al unui vârf x, notat d-(x), ca fiind numărul arcelor care
intră în nodul x (de forma (y,x) ε U).
Exemplu:
În graful reprezentat în figura 1, pentru nodul x=2, avem:
– d*(2) =3 → există trei arce care ies din nodul 2, și anume : u2=(2,1), u4= (2,3) și u5 =
(2,4).
– d-(2) =1 → în nodul 2 intră un singur arc, în speță arcul u3=(3,2).
Se mai definesc următoarele mulțimi:
– ()(){ }UyxXy x ∈∈=Γ+, → mulțimea nodurilor ce constituie extremități fin ale ale
arcelor care pleacă din nodul x. Pe scurt, mulțimea succesorilor lui x;
– ()(){ }UxyXy x ∈∈=Γ−, → mulțimea nodurilor ce constituie extremități ini țiale ale
arcelor care pleacă din nodul x. Pe scurt, mulțimea predecesorilor lui x;
Exemplu:
În graful din figura 1, pentru nodul x=2, avem:
– Γ+(2) = {1,3,4} → urmare a faptului că muchiile care pleacă din nodul 2 sunt (2,1),
(2,3) și (2,4), putem spune că mulțimea succesorilo r nodului 2 este {1,3,4}.
– Γ-(2) = {3} → în nodul 2 intră doar muchia (3,2), dec i mulțimea predecesorilor lui 2
conține doar nodul 3.
– ω+(x) = {u = (x,y)| u ε U} → mulțimea arcelor care ies din nodul x;
35
– ω-(x) = {u = (y,x)| u ε U} → mulțimea arcelor care intră în nodul x;
Exemplu:
În graful din figura 1, pentru nodul 2, avem:
– ω+(x) = {(2,1), (2,3), (2,4)},
– ω-(x) = {(3,2)}
Graf parțial și subgraf
Definiție : Fie graful G = (X,U). Un graf parțial al lui G, e ste un graf G 1= (X,V), cu UV⊆ .
Altfel spus, un graf parțial G1 al lui G, este chia r G, sau se obține din G păstrând toate vârfurile
și suprimând niște arce.
Definiție : Fie graful G = (X,U). Un graf parțial al lui G, e ste un graf G 1= (Y,T), unde X V⊂ și
UT⊂ , iar T va conține numai arcele care au ambele extr emități în Y. Altfel spus, un graf
parțial G 1 al lui G, se obține din G eliminând niște vârfuri și păstrând doar acele arce care au
ambele extremități în mulțimea vârfurilor rămase.
Exemplu :
Se consideră graful G = (X,U) din figura 2, în care X = {1,2,3,4,5,6} și U={u1, u2, u3,
u4, u5, u6, u7}.
– Construim graful parțial G1 = (X,V), unde X = {1,2, 3,4,5,6} și V = { u2, u3, u4, u6,
u7} (figura 3) din graful G au fost eliminate arcel e u1 și u5.
– Construim subgraful G2 = (Y,T), unde Y = {3,4,5,6} și T = {u4, u5, u6, u7} (figura 4)
din graful G au fost eliminate nodurile 1 și 2 prec um și arcele u1, u2 și u3 care au o
extremitate în afara mulțimii nodurilor rămase.
1 2
4 3
5
6 u2
u1 u3
u4 u5
u7 u6 1 2
4 3
5
6 u2
u3
u4
u7 u6 4 3
5
6 u4 u5
u7 u6
Figura 2 Figura 3 Figura 4
36
2.2 REPREZENTAREA GRAFURILOR
ORIENTATE
Considerăm un graf orientat G= (X,U) cu m arce și n noduri. Cele mai cunoscute forme
de reprezentare sunt: matricea de adiacență, matricea vârfuri – arce, matricea drumu rilor
și listele vecinilor.
1. Matricea de adiacență
Are aceeași semnificație ca în cazul grafurilor neo rientate: fiecare element a[i,j], cu i,j ε
{1,2,…,n}, este: 1 dacă există arcul (i,j), respe ctiv 0 în caz contrar.
Datorită orientării, așa cum am mai spus, arcul (i, j) nu este totuna cu arcul (j,i). Prin
urmare, a[i,j] ≠ a[j,i]. Așadar matricea de adiacen ță nu mai este simetrică față de diagonala
principală, așa cum se întâmpla în cazul grafurilor neorientate.
Exemplu:
Pentru graful G=(X,U) din figura 5, matricea de adi acență este:
coloana 1 2 3 4
A= 0 0 0 0 1
1 0 1 1 2
0 0 0 1 3
0 1 0 0 4
2. Matricea vârfuri – arce:
Este o matrice b cu n linii și m coloane, în care f iecare element b[i,j] este:
– 1, dacă nodul i este o extremitate inițială a arcul ui u j;
– -1, dacă nodul i este o extremitate finală a arculu i u j; 1 2 3
4
Figura 5
37
– 0, dacă nodul i nu este o extremitate a arcului uj.
Exemplu:
Pentru graful de mai jos cu n=4 noduri și m=5 arce, matricea vârfuri – arce este:
1 0 0 0 0
-1 -1 -1 0 0
0 1 0 1 -1
0 0 1 -1 1
Pentru a exemplifica construcția matricei, vom dedu ce elementele liniei 3:
– a[3,1]= 0 pentru că nodul 3 nu este o extremitate a arcului u1. Analog, a[3,3]= 0
deoarece nodul 3 nu este extremitate a arcului u3.
– a[3,5]= -1 pentru că nodul 3 este o extremitate fin ală a arcului u5.
– a[3,2]= 1 și a[3,4]= 1 întrucât nodul 3 este o extr emitate inițială a arcului u2 respectiv
u4.
Observații:
Pe fiecare coloană j (aferentă arcului uj), avem ex act două elemente nenule: un 1 (linia i
pe care se află reprezintă extremitatea inițială a arcului uj) și un -1 (linia i pe care se află
reprezintă extremitatea finală a arcului uj)
Numărul valorilor de 1 de pe linia i, reprezintă gr adul exterior al nodului i (numărul
arcelor ce au ca extremitate inițială pe i), iar nu mărul valorilor de -1 de pe linia i reprezintă
gradul interior al nodului i (numărul arcelor care au ca extremitate finală pe i). 2
3 1
4 u3 u2 u1
u4
u5
Figura 6
38
3. Listele vecinilor
Pentru fiecare nod x se construiesc două liste ale vecinilor săi:
– L*(x) → lista vecinilor succesori; conține nodurile c e sunt extremități finale ale arcelor
care ies din nodul x.
– L-(x) → lista vecinilor predecesori; conține nodurile ce sunt extremități inițiale ale
arcelor care intră în nodul x.
Exemplu:
În graful din figura 6, pentru nodul x=4 avem:
– arcele care ies din nodul 4 sunt (4,2) și (4,3). În consecință, lista vecinilor succesori
L*(4) conține nodurile 2 și 3;
– în nodul 4 intră un singur arc, și anume (3,4), mot iv pentru care lista vecinilor
predecesori L-(4) conține doar nodul 3.
Prezentăm în continuare aceste liste ale vecinilor pentru graful din figura 6.
Nodul x L*(x) L-(x)
1 2 vidă
2 vidă 1,3,4
3 2,4 4
4 2,3 3
4. Matricea drumurilor
Această matrice va fi reprezentată în cadrul capito lului “Drumuri și circuite în grafuri
orientate”.
5. Reprezentarea grafului ca un vector de muchii
Fiecare arc al grafului poate fi privit ca o înregi strare cu două componente, în speță cele două
noduri care constituie extremitățile arcului:
– nod_in -> nodul din care iese arcul (“nodul de înce put” al arcului);
– nod_sf -> nodul în care intră arcul (“nodul de sfâr șit” al arcului);
Putem defini tipul de date ARC, astfel:
typedef struct
{
int nod_in, nod_sf;
39
} ARC;
Graful în ansamblul său, este o mulțime de arce, ad ică o mulțime de elemente de tipul ARC. În
consecință, definim graful ca un “vector de arce”, adică un vector de elemente de tipul ARC:
ARC v[25];
Numărul real de elemente este numărul de arce m. As tfel, elementele efectiv folosite ale
vectorului vor fi v(1), v(2),…, v(m). Fiecare ele ment v(i) (cu i € {1, 2, …, m}) este de tipul
ARC și reprezintă un arc al grafului, având două c omponente:
v[i].nod_in și v[i].nod_sf -> nodurile-extremități ale arcului .
2.3 DRUMURI ȘI CIRCUITE ÎN
GRAFURI ORIENTATE
Definiție : Se numește lanț intr-un graf orientat, o mulțime de arce L={u 1,u 2,…,u k}, cu
proprietatea ca oricare doua arce vecine in mulțime au o extremitate comuna.
Un lanț este de fapt un traseu care unește prin arce doua noduri numite extremitățile
lanțului, fără a tine cont de orientarea arcelor co mponente.
Definiție : Se numește drum în graful G, un șir de noduri D={z 1, z 2, z 3, …, z k}, unde z 1, z 2, z 3,
…, z k aparțin lui x, cu proprietatea că oricare două nod uri consecutive sunt adiacente, adică
există arcele [z 1, z 2], [z 2, z 3], …, [z k-1,z k] aparțin lui U.
Practic, un drum poate fi privit ca un traseu în ca re toate arcele au aceeași orientare, dată
de sensul de deplasare de la z1 la zk.
Dacă nodurile z 1, z 2, z 3, …, z k sunt distincte două câte două, drumul se numește
elementar . În caz contrar, drumul este ne-elementar .
Asemenea unui lanț într-un graf neorientat, un drum într-un graf orientat este de fapt un
traseu pe care l-am parcurge între două noduri depl asându-ne de-a lungul unor arce și trecând
prin niște noduri intermediare. Deosebirea unui dru m față de un lanț constă în faptul că de-a
lungul unui arc ne putem deplasa numai în sensul da t de orientarea arcului.
Definiție : Se numește circuit într-un graf, un lanț L={z 1, z 2, z 3, …, z k} cu proprietatea că z 1=z k
și arcele (z 1, z 2), (z 2, z 3), …, (z k-1,z k) sunt distincte două câte două.
Dacă într-un circuit, toate nodurile cu excepția pr imului și ultimului sunt distincte două
câte două, atunci circuitul se numește elementar . În caz contrar, el este ne-elementar .
40
Matricea drumurilor:
Este o matrice d cu n linii și n coloane , în care fiecare element d[i,j] este :
– 1, dacă există drum de la nodul i la nodul j în graf;
– 0, în caz contrar.
Algoritmul Roy-Warshall de determinare a matricei drumurilor
Matricea drumurilor se obține aplicând matricei de adiacență transformări succesive.
Vom spune că există drum de la nodul i la nodul j, dacă găsim un nod k (diferit de i, j) cu
proprietatea că există drum de la i la k și drum de la k la j. Astfel:
/square4 un element a (i, j) care este 0, devine 1, dacă exi stă un nod k astfel încât a (i, k)=1 și
a(k, j)=1. Pentru a găsi arcele nodului k, trebuie parcurse pe rând în varianta k toate
nodurile 1, 2, …, n.
for (k=1; k<=n; k++)
for (i=1; i<=n; i++) { i≠k }
for (j=1; j<=n; j++) { j≠k }
if (a[i] [j] ==0 && i!=k && j!=k)
a[i] [j] = a[i] [k]* a[k] [j];
Atribuirea a[i] [j] = a[i] [k]* a[k] [j] este o s criere elegantă a regulii de mai sus:
– în cazul în care unul din elementele a[i] [k], a[k] [j] este 0, a[i] [j] va rămâne 0;
– dacă a[i] [k] ==1 si a[k] [j] ==1, atunci a[i] [j] devine 1.
1 2
4 3
5
6 u2
u1 u3
u4 u5
u7 u6
Figura 8
41
2.4 CONEXITATE ÎN GRAFURI ORIENTATE
Definiție : Un graf G este conex , dacă oricare ar fi două vârfuri ale sale, există un lanț care le
leagă. Un lanț într-un graf orientat este un șir de arce {u 1, u 2, u 3 , …, un} cu proprietatea că
oricare două arce consecutive au o extremitate comu nă. Altfel spus, un lanț este un traseu care
unește prin arce două noduri numite extremitățile l anțului, fără a ține cont de orientarea arcelor
componente.
Exemplu:
Figura 1
Graful este conex pentru că oricum am lua două nodu ri putem ajunge de la unul la
celalalt pe un traseu de tip lanț. De exemplu, de l a nodul 4 la nodul 2 putem ajunge pe traseul
de noduri (4,3,2) stabilind astfel lantul {u 5, u 3}, dar ]i pe traseul de noduri (4,1,2) stabilind
lanțul {u 6, u 2}.
Exemplu
Figura 2
Graful din figura 2 nu este conex. Luând submulți mea de noduri {1,2,3}, putem spune
că între oricare două noduri din această submulțime exista cel putin un lanț, de exemplu lanțul
{u 1, u 2} sau {u 3, u 1}. La fel stau lucrurile cu submulțimea de noduri { 4,5,6}. Dar nu putem găsi
un lanț între un nod din prima submulțime și un nod din a doua submulțime.
Plecând dintr-un nod al primei submulțimi și deplas ându-ne pe arce, nu avem cum sa trecem în
a doua submulțime pentru că nu exista nici un arc d irect care să lege cele două submulțimi. De
42
exemplu plecând din nodul 1 putem ajunge [n nodul 2 pe traseul {u 3, u 2}, dar de aici nu putem
ajunge mai departe în nodul 4, deci nu există lanț de la 2 la 4.
Componenta conexa
Definiție : Se numește componentă conexă a grafului G=(X, U), un subgraf G 1=(X 1, U 1) a
lui G, conex, cu proprietatea că nu există nici un lanț care să lege un nod din X 1 cu un nod din
X-X 1 (pentru orice nod, nu există un lanț între acel nod și nodurile care nu fac parte din
subgraf).
De exemplu graful din figura 2 nu este conex, însa în el distingem două componente
conexe: G 1 =(X 1, U 1), unde X 1={1,2,3} ]i U 1={u 1, u 2, u 3}; și G 2=(X 2, U 2), unde X 2={4,5,6} și
U2={u 4, u 5}.
Graf orientat tare conex
Definiție : Graful tare conex este un graf orientat G=(X, U), dacă pentru oricar e două noduri x
și y aparțind lui X, există un drum de la x la y pr ecum și un drum de la y la x.
Exemplu :
Figura 3
Graful din figura 3 este tare conex. Pentru a demon stra acest lucru, formăm toate
perechile posibile de noduri distincte (x, y) cu x, y aparțin mulțimii {1,2,3}, și pentru fiecare
astfel de pereche căutăm un drum de la x la y și un drum de la y la x:
• x=1, y=2
De la 1 la 2 – drumul [1,3,2], pe arcele (1,3) si ( 3,2);
De la 2 la 1 – drumul [2,3,1], pe arcele (2,3) si ( 3,1).
• x=1, y=3
De la 1 la 3 – drumul [1,2,3], pe arcele (1,2) si ( 2,3);
De la 3 la 1 – drumul [3,2,1], pe arcele (3,2) si ( 2,1).
• x=2, y=3
43
De la 2 la 3 – drumul [2,1,3], pe arcele (2,1) si ( 1,3);
De la 3 la 2 – drumul [3,1,2], pe arcele (3,1) si ( 1,2).
Observație : În stabilirea drumurilor trebuie să fim atenți la orientarea arcelor prin care
trecem., pentru a respecta definiția noțiunii de d rum. Mai exact, toate arcele drumului trebuie
să aibă aceeași orientare.
Componenta tare conexa
Definiție : Fiind dat un graf orientat G= (X, U), se numește componentă tare conexă a lui G,
un subgraf G 1=(X 1, U 1), tare conex, și maximal șn raport cu această prop rietate (adică pentru
orice nod x aparține X-X 1, subgraful indus de X 1 reunit cu {x} nu mai este tare conex).
Se consideră un subgraf tare conex G 1=(X 1, U 1) al grafului G=(X, U). Prin adăugarea
la subgraf a unui nod x care nu face parte din mul timea nodurilor sale (x aparține X-X 1),
obținem mulțimea de varfuri X 1 reunit cu {x}. Subgraful indus pe mulțimea X 1 reunit cu {x}
se obține luând ]i arcele care trec prin nodul x.
Problemă – Afișarea componentelor tare conexe
Enunț: Se citește matricea de adiacență a unui graf ori entat din fișierul “adiac.txt”. Fișierul
conține: pe primul rând numărul n de linii și coloane, apoi, pe fiecare din următoar ele n
rânduri, elementele câte unei linii a matricii sepa rate prin spații. Realizați un program care
descompune graful dat în componente tare conexe și afișează componentele obținute.
Subprogramele folosite sunt:
► Funcția { void citire_matrice ( ) } citește matricea de adiacență dintr-un fișier t ext.
Funcția { void afi]are_matrice ( ) } tipărește matricea de adiacență pe monitor.
► Funcția { void formare_matrice_drumuri ( ) } conține algoritmul lui Roy-Warshall
pentru construirea matricii drumurilor. Matricea dr umurilor se obține printr-o serie de
transformări aplicate matricii de adiacență a, care se operează tot în a. La finele
algoritmului, tabloul a va conține matricea drumurilor în locul matricii d e adiacență.
► Funcția { void det_S (int i, int &nr ) } determină elementul S[i] al vectorului de
mulțimi S. Acest element este o mulțime, mai exact mulțimea nodurilor care sunt
extremități finale ale drumurilor ce pleacă din nod ul i. Inițializăm S[i] cu mulțimea
vidă “[ ]”. Parcurgem coloanele k=1,2,….,n ale liniei i [n matricea drumurilor a.
44
Fiecare element a [i] [k] egal cu 1 ne arată că există drum de la nodul i la nodul k
(deci un drum care pleacă din nodul i) , iar extremitatea finală a acestui drum este k. În
consecință, dacă a [i][k] ==1, trebuie adăugat nodul k la S[i].
► Funcția { void det_P (int i, int &nr ) } determină elementul P [i] al vectorului de
mulțimi P. Acest element este mulțimea nodurilor care sunt e xtremități inițiale ale
drumurilor ce intră în nodul i. Este evident că aceste noduri vor fi găsite pe c oloana i în
matricea drumurilor a. Algoritmul este asemănător cu cel al determinări i lui S[i]. A m
notat indicele de coloană tot cu i , dar acest fapt nu are nici o importanță, deoarec e i nu
este decât un contor definit ca variabilă locală.
► Funcția { void det_tare_conexe ( ) } conține algoritmul pentru determinarea
componentelor tare conexe.
Program C++
#include<iostream.h>
#include<stdio.h>
int a [20] [20], S [20] [20,], P[20] [20,], C[20] [20,], n, nc, L [20];
void cit_matr_fis ( )
//cite]te numărul de noduri și matricea de adiacență din fișierul text
{ int i, j ;
FILE *f ;
f=fopen (“d :țțadiac.txt”, “r “);
fscanf (f, “%dțn”, &n);
for (i=1; i<=n; i++)
{ for(j=1; j<=n; j++)
{ fscanf (f, “%d”, &a [i][j]);
cout << a [i][j] << “ “;
}
fscanf (f, “țn”);
cout << “țn”;
}fclose (f);
}
void afi]are_matrice ( )
45
// afișează matricea de adiacență a cu n linii*n coloane
{ int i, j ;
cout << “/n matricea de adiacență este : /n”;
for (i=1; i<=n; i++)
{cout << ”țn”;
for(j=1; j<=n; j++)
cout << a [i][j] << “ “;
}
}
void Roy-Warshall ( )
// constuiește matricea drumurilor pornind de la ma tricea de adiacență
{ int i, j, k ;
for (k=1; k<=n; k++)
{ for (j=1; j<=n; j++)
if (!a[i] [j] ==0 && i!=k && j!=k)
a[i] [j] = a[i] [k]* a[k] [j];
}
void det_S (int i, int &nr ) // determină multimea S(i), reprezentată ca linia i în matricea S
{ int k, j=0;
for (k=1; k<=n; k++)
if (a [i][k]==1)
{ S [i][j]=k; j++; }
nr=j++;
}
void det_P (int i, int &nr ) // determină mulțimea P (i) reprezentată ca linia i în matricea P
{ int k, j=0;
for (k=1; k<=n; k++)
if (a [k][i]==1)
{
P [i][j]=k; j++;
} nr=j++;
} int căutare (int A[20], int x, int m)
{ int j0, găsit ; //verifică dacă nodul x se găse]te în mulțimea L a nodurilor deja luate în componente
găsit=0;
for (j0=1; j0<=m; j0++)
46
if (A[j0]==x)
găsit=1; return găsit;
} void intersecție (int A[20], int B[20], int C[2 0], int m1, int m2, int &nr)
{ int j0, j1, j2; // determină intersecția mulțimilor memorate în ve ctorii A și B cu rezultatul în vectorul C
for (j0=1; j0<=m1; j0++)
{ j2=0;
for (j1=1; j1<=m2; j1++)
if (A[j0]==B[j1])
{ C[j2]= A[j0]; j2++;
}
} nr=j2; }
void det_tare_conexe () // descompune graful în componente tare conexe
{int i, j, k, ks, kp, i0; j=0; k=0; nc=0; //n c =numărul componentelor conexe
for (i=1; i<=n; i++)
if ( ! căutare (L, i, j)) // dacă nodul i nu a fost deja inclus în vreo compon entă
{ // inaugurează o nouă componentă
nc++;
det_S (i, ks); det_P (i, kp); // calculează componenta tare conexă C [i]
intersecție (S[i], P[i], C[i], ks, kp, k)
// adaugă C[i] la mulțimea nodurilor care fac deja p arte dintr-o componentă
for (i0=1; i0<=k; i0++)
{ L[j] =C [i] [i0]; j++; } // tipărește componenta conexă C[i]
cout << “țn Componenta conexă “ << nc << “ este “ ;
for (i0=1; i0<=n; i0++)
if ( căutare (C[i], i0, k))
cout << i0 << “ “; cout << endl;
}}
void main ( )
{ cit_matr_fis ( ) ;
afi]are_matrice ( );
Roy-Warshall ( );
det_tare_conexe ();
}
47
2.5 DRUMURI MINIME SI MAXIME ÎN
GRAFURI ORIENTATE
Considerăm un graf orientat G=(X,U) cu n noduri, în care fiecărui arc și este asociat un
număr întreg numit cost. Semnificația acestui cost poate fi foarte variată, în funcție de
domeniul pe care îl descrie graful De exemplu, dac ă graful reprezintă harta unui oraș în care
arcele sunt străzile, iar nodurile sunt intersecții le dintre străzi, atunci putem vorbi despre costul
deplasării cu automobilul între două intersecții, d e-a lungul unei străzi. Aceasta s-ar putea
măsura în cantitatea de benzină consumată, calculat ă prin prisma lungimii străzii în m sau km .
Matricea costurilor
Pentru evindențierea costurilor tuturor arcelor un ui graf cu n noduri se poate defini o
matrice a, cu n linii * n coloane. Există două forme ale acestei matrici:
Forma a): Fiecare element a [i], [j] poate fi:
♦ c, dacă există un arc de cost c>0 [ntre nodurile i ]i j;
♦ 0, dacă i=j;
♦ +∞, dacă nu există arc [ntre nodurile i ]i j.
Forma b ): Este absolut similară, cu singura deosebire că în l oc de +∞ avem – ∞.
Forma a se folosește pentru determinarea drumurilor de cost minim între două noduri, iar
Forma b) este utilizată pentru aflarea drumurilor de cost m axim.
Dacă dorim să citim matricea costurilor, evident că nu putem introduce de la tastatură
”+∞” ! în loc de “+∞” vom da un număr întreg foarte mare.
Problema determinării drumului minim/maxim între două noduri face obiectul
algoritmului următor.
48
Algoritmul Roy – Floyd
Se consideră un graf orientat cu n noduri, pentru c are se dă matricea costurilor în forma
a). Se cere ca, pentru fiecare pereche de noduri (i, j) , să se tipărească costul drumului minim
de la i la j.
Plecăm de la următoarea idee: dacă drumul minim în tre două noduri oarcare i și j trece
printr-un nod k, atunci drumurile de la i la k și de la k la j sunt la rândul lor minime. Pentru
fiecare pereche de noduri (i, j), cu i, j ε {1,2,….,n}, procedăm astfel:
♦ Dăm pe rând lui k valorile 1,2, ……., n , pentru că nodul k despre care vorbeam mai sus
poate fi, cel puțin teoretic, orice nod al grafului . Pentru fiecare k:
– dacă suma dintre costul drumului de la i la k și costul drumului de la k la j
este mai mică decât costul drumului de la i la j {a [i] [k] + a[k] [j] < a[i] [j]},
atunci drumul inițial de la i la j este [nlocuit cu drumul indirect i ->k -> j .
Această înlocuire fire]te că se va opera ca atare în matricea costurilor:
{ a [i] [j] = a [i] [k] + a[k] [j] }
Prezentăm în continuare procedura generare care c onține algoritmul descris:
void generare ()
{ int i, j, k;
for (k=1; k<=n; k ++)
for (i=1; i<=n; i ++)
for (j=1; j<=n ; j ++)
if (a [i] [k] + a[k] [j] < a[i] [j] )
a [i] [j] = a [i] [k] + a[k] [j]
}
Observații :
► Drumurile minime între toate nodurile se regăsesc la finele algoritmului tot în
matricea costurilor, care a suferit n transformări, pentru k=1, 2, 3,….., n .
► Unele elemente pot fi +∞, iar pentru simularea lui +∞ am spus că se introduce un
număr întreg foarte mare. Prin adunări repetate a d ouă numere întregi fparte mari putem
ajunge la un rezultat care depășește cea mai mare valoare posibilă de tip integer . De
aceea, recomandăm ca elementele matricii costuril or să fie de tipul longint .
► Drumurile de lungime maxima într-un graf există nu mai în cazul în care nu există
circuite de cost strict pozitiv. Dacă costurile aso ciate arcelor unui graf sunt numere
reale oarecare, atunci drumurile de lungime minimă există, dacă nu sunt circuite
negative, iar cele de lungime maximă, dacă nu sunt circuite pozitive.
49
APLICAȚIE – Drum într-un graf
Enunț : Scrieți un program care verifică dacă o secvență dată de noduri reprezintă un drum
elementar sau ne-elementar într-un graf orientat. N umărul de noduri și matricea de adiacență
se citesc de la tastatură, iar secvența testată se găsește în fișierul “drum.txt” (numerele
nodurilor ocupă în fișier un singur rând, separate prin spații).
Rezolvare:
Functia { void citire_matrice () } cite]te de la tastatură numărul de noduri n ale
grafului, precum și matricea de adiacenă cu n lin ii * n coloane, iar funcția { void
afi]are_matrice () } tipărește matricea de adiacență pe ecran.
Functia { void citire_secvență () } citește din fișierul “drum.txt” secvența de noduri ce
trebuie testată, memorând-o în vectorul s. Fie k un contor cu ajutorul căruia vom parcurge
vectorul s. Inițial vectorul s este gol, deci k=0 . Atâta timp cât nu s-a ajuns la stâr]itul fișierul ui:
– “pregătește o căsuță nouă la sfârșitul vectorului s, prin incrementarea lui k (k++);
– citește un număr de pe primul rând din fișier, mem orându-l în elementul s[k] tocmai
creat;
Ultima valoare a lui k, de la ie]irea din ciclu, re prezintă numărul de elemente ale
vectorului s, pe care îl vom memora în variabila n (n=k).
Functia { void afi]are_secvență () } tipărește secvența de noduri memorată în vector ul
s.
Întreg algoritmul care testează dacă secvența citi tă este drum elementar sau ne-
elementar a fost cuprins în funcția { void testare ( ) }. Fiind o testare logică, vom proceda prin
reducere la absurd, folosindu-ne de o variabilă “se mafor”- ok , care în final va indica “starea”
condiției testate. Presupunem mai întâi că secvența din vectorul s este drum, inițializând ok cu
valoarea 1.
Pentru a fi îndeplinită condiția de drum, este nec esar ca pentru oricare doua noduri
consecutive în secvență, s [i] ]i s [i+1] (cu i=1, 2, …, n+1 ), să existe un arc de la s [i] la s [i+1]
(exact cu această orientare!). Într-un ciclu, conto rul i va parcurge valorile 1,2,…, n-1 ; dacă
găsim o valoare a lui i pentru care nu există în g raf arcul ( s[i] , s[i+1] ), adică a[ s[i]] [s[i+1] ]
este 0, atunci secvența nu mai poate fi drum, caz î n care ok va primi valoarea 0.
Mai departe, dacă “semaforul” ok a rămas cu valo area inițială 1, înseamnă că secvența
testată este drum, și mai trebuie verificat dacă es te elementar sau nu. Într-un drum elementar
toate nodurile componente trebuie să fie distincte două câte două. În două cicluri, formăm pe
mulțimea nodurilor {1,2,….,n }, perechi de forma (i, j), cu i=1, 2, n-1 ]i j=i+1 , …., n; pentru
50
fiecare astfel de pereche (i, j) , dacă s[i]= s[j] [nseamnă că am găsit două noduri identice în
secvența s, ceea ce înseamnă că drumul este ne-elementar.
Algoritmul va afișa câte un mesaj pentru fiecare d in cele trei cazuri posibile. Funcția
principală main nu va conține altceva decât apelurile succesive al e subprogramelor descrise
mai sus.
Program C++
#include<iostream.h>
#include<stdio.h>
FILE *f;
int s[30], a[20] [20,], n, k;
void afi]are_matrice ()
// afi]ează matricea de adiacență a cu n linii * n coloane
{
int i, j;
cout << “/n matricea de adiacență este : /n”;
for (i=1; i<=n; i++)
{
cout << ”țn”;
for (j=1; j<=n; j++)
cout << a [i][j] << “ “;
}
}
void citire_matrice ()
// citește matricea de adiacență a de la tastatură
{
int i, j, k;
cout << “/nNumărul de noduri n=“ ;
cin >> n;
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
{
cout << “a[“ << i << “] [“ << j << “]=”;
cin >> a[i] [j];
51
}
}
void citire_secvență ()
{
// citește secvența ce trebuie testată din fișierul de intrare
f=fopen (“C://drum.txt”, “r”);
k=0;
while (!feof (f))
{
k++;
fscanf (f, “%d”, &s[k]);
}
n=k; // n reține numărul de elemente din secvența
fclose (f);
}
void afi]are_secvență ()
{
//tipărește secvența de noduri citită din fișierul d e intrare
int i;
cout << endl;
for (i=1; i<=n; i++)
cout << s[i] << “ ”;
}
void testare ()
{//testează dacă secvența memorată în vectorul s este drum, elementar sau ne-elementar
int ok=1; //presupunem că secvența este drum
int i, j;
//verifică dacă intre oricare două elemente consec utive există un arc
for (i=1; i<=n; i++)
if (!a[s[i]] [s[i=1]]
ok=0;
if (ok)
{ //dacă prima condiție a fost îndeplinită verifică dacă drumul este elementar
// adică dacă toate nodurile secvenței sunt distin cte
for (i=1; i<=n; i++)
52
for (j=i+1; j<=n; j++)
if (s[i]==s[j])
ok=0;
if (ok)
cout << “/n Secvența este un drum elementar”;
else
cout << “/n Secventa este drum ne-elementar”;
}
else
cout << “/n Secvența nu este drum”;
}
void main()
{citire_matrice ();
afi]are_matrice ();
citire_secvență ();
afi]are_secvență ();
testare();
}
53
2.6 APLICA|II
Problemă – Concurs hipic (graf turneu)
Enunț : Pe o arenă hipică urmează să se organizeze un concu rs de călărie, s-au montat n
obstacole, numerotate 1, 2,…, n. Traseul pe care îl vor parcurge călăreții în timpul concursului
trebuie să țină cont de următoarele:
– Se poate începe cu orice obstacol și trebuie sărite toate obstacolele, fiecare o singură
dată;
– Distanța dintre oricare două obstacole poate fi par cursă într-un singur sens, pe care
călăreții îl cunosc la intrarea în concurs.
Concepeți un program cu ajutorul căruia călăreții s ă-și stabilească traseul.
Reprezentare
Arena poate fi privită ca un graf orientat, în care nodurile sunt obstacole. Distanța între
oricare două obstacole poate fi parcursă exact într -un singur sens, de unde rezultă că:
– graful este orientat;
– între oricare două noduri există un arc și numai un ul care le leagă; arcul respectiv are
una dintre cele două orientări posibile.
Un graf cu proprietatea de mai sus se numește graf turneu . Deoarece știm că traseul pe
care trebuie să și-l aleagă călărețul va trece prin fiecare obstacol exact o singură dată, putem
spune că un astfel de traseu este de fapt un drum e lementar care trece prin toate nodurile
grafului.
Memorăm drumul într-un vector de noduri, în ordinea în care urmează a fi “vizitate”.
Introducem inițial în vector nodurile cu numerele 1 și 2, în ordinea dată de orientarea arcului
care le leagă. În continuare, pentru fiecare dintre celelalte noduri încercăm să găsim poziția pe
care o va avea în cadrul drumului (în vector). P entru a ilustra de exemplu modul în care poate
fi introdus nodul 3 în vectorul care inițial conțin e nodurile 1 și 2, prezentăm în continuare trei
variante de graf, cele din figurile A, B, C de mai jos. În toate cele trei grafuri, drumul inițial
conține nodurile (1,2), în această ordine:
54
– În graful din figura A, există arcul (3,1), deci p utem alcătui un drum cu arcele (3,1),
(1,2); prin urmare, putem plasa nodul 3 la început ul drumului (1,2) existent, caz în care
drumul ar deveni (3,1,2).
– În graful din figura B, nodul 3 nu poate fi plasat înaintea lui 1, deoarece nu există arcul
(3,1); nici varianta (1,3,2) nu este corectă, deoa rece, deși există arcul (1,3), nu există
arcul (3,2); în consecință drumul corect este (1,2, 3).
– în sfârșit, în graful din figura C, nodul 3 nu poat e fi pus înaintea lui 1, dar în schimb
va fi plasat între 1 și 2 deoarece există muchiile (1,3) și (3,2); am obținut astfel drumul
(1,3,2).
Un alt exemplu este graful din figura D în care, in troducând inițial primele două noduri
în vector în ordinea (2,1), vom obține drumul (4,2, 1,3).
Rezolvare
În funcția citire_matrice realizăm citirea matricii de adiacență. Vom citi n umai
elementele de deasupra diagonalei principale, parcu rgând liniile i de la 1 la n-1 și coloanele j
de la i+1 la n. Pentru fiecare element a[i] [j] ci tit, facem atribuirea a [j] [i] =1- a[i] [j] (d acă
a[i] [j] este 1 atunci a [j][i] va fi 0 și invers , marcând faptul că între cele două noduri există
un singur arc). Am valorificat astfel proprietatea de graf turneu. Generarea drumului
elementar în vectorul s se face în cadrul funcției generare_drum .
Mai întâi introducem în s primele două noduri în ordinea dată de orientarea a rcului care
le leagă (a[1] [2] egal cu 1 sau 0). Celelalte nodu ri, k=3, …, n vor fi adăugate pe rând într-un
ciclu. Fiecare nod k se va adăuga fie la [nceput, fie în interior, fie l a sfârșit, astfel încât vectorul
s să păstreze proprietatea de drum. Notăm cu L numărul elementelor deja adăugate, și cu p
poziția pe care urmează a fi adăugat nodul k.
Pentru a adăuga efectiv un nod k începem prin a căuta poziția p:
– dacă există arc de la nodul k la nodul s[1], atunci p=1 , ceea ce înseamnă că nodul k
se va insera la începutul vectorului (drumului);
– în caz contrar, încercăm să găsim poziția p în interiorul vectorului. Prin intermediul
unui ciclu dirijat de contorul i (inițializat cu 1) și variabila “semafor” g (inițializată
cu 0), încercăm să găsim un indice i cu proprietatea că există arc de la nodul s [i]
la nodul k și arc de la nodul k la nodul s[i+1] (a[s[i] [k]==1 ]i a[k] [s[i+1]] ==1 ).
Teoretic, căutarea are loc atâta timp cât i<L (nu am ajuns la sfârșitul vectorului) și
g==0 . Dacă există un astfel de indice i, atunci se va produce ieșirea din ciclul while ,
prin atribuirea g=1 , iar nodul k va fi adăugat ca element nou între s[i] ]i s[i=1] . În
55
caz contrar, se va ieși din ciclul while cu valoarea i=L . După acest ciclu, prin
atribuirea p=i+1 se va fixa poziția pe care urmează a fi adăugat nodul k (între s[i] ]i
s[i+1] sau la sfârșitul vectorului pe poziția L+1 ).
După ce am găsit poziția p, realizăm efectiv inserarea. într-un ciclu for , mutăm cu o
poziție mai la dreapta, toate elementele aflate dup ă poziția p inclusiv. Dar pentru a nu pierde
nici un element, mutarea se face în ordine inversă : s [j+1] =s[j] pentru j=L , L-1, … ,p+1, p.
în final, inserarea efectivă are loc prin atribuir ea s[p]=k . Programul mai conține o funcție
pentru afișaea vectorului s.
Program C++
#include<iostream.h>
int s [30], a [20] [20], n, L;
void citire_matrice ()
//cite]te de la tastatură matricea de adiacență a cu n linii * n coloane
{ int i, j, k, x, y;
cout << “țn Numărul de vârfuri ”;
cin >> n;
//inițializează cu 0 diagonala principal ă
for (i=1; i<=n; i++)
a[i] [i]=0;
//citește porțiunea din matrice situată deasu pra diagonalei principale
for (i=1; i<=n; i++)
for (j=i+1; j<=n; j++)
{ cout << “/n Există muchia (“ << i << “, “ << j << “ ) ? [1/0] “;
do
{ cin >> a[i] [j]; //citește elementul a[i] [j] cu validare (el trebu ie să fie 0 sau 1)
}
while ( ! (a[i] [j]==0 | | a[i] [j]==1) );
a[j] [i]=1- a[i] [j] ;
}
}
void afi]are_ drum ()
{
// tipărește secvența de noduri citită din fișier ul de intrare
int i;
56
cout << endl;
for (i=1; i<=n; i++)
cout << s[i] << “ “ ;
}
void generare_drum () // generează drumul cerut într-un vector de nodur i s
{ int k, i, j, p, g;
// introduce în vector primele două noduri 1 și 2, în ordinea dată de orientarea muchiei
directe
if (a[1] [2]==1)
{ s [1]=1;
s [2]=2;
}
else
{ s [1]=2; s [2]=1;
}
L=2; // L = numărul de noduri adăugate în vectorul s care deocamdată este 2
for (k=3; k<=n; k++) // adaugă pe rând fiecare nod în vectorul s
{
//dacă există arc de la nodul k la nodul s [1], at unci nodul k se va adăuga la începutul drumului e xistent
if (a [k] [s[1]]==1)
p=1;
else
{
// [n caz contrar, va insera nodul k în interiorul v ectorului s, sau la sfărșitul lui caută
poziția p pe care se va insera nodul k; el se va introduce între două noduri succesive s[i] si
s[i+1, daca există arc de la s[i] la k ]i de la k la s[i+1]
i=1; g=0;
while (i<L && ! g)
if (a[s[i]] [k]==1 && a[k][s[i+1]]==1)
g=1;
else
i++;
p=i+1;
}
// pentru a insera nodul k pe poziția p, mutăm m ai la dreapta toate elementele aflate după poziția p inclusiv
for (j=L; j>=p; j–)
57
s[j+1]=s[j];
s[p]=k;
L++;
}
cout << “țnL= “ << L;
}
void main ()
{
citire_matrice ();
generare_drum ();
afi]are_ drum ();
}
Probleme propuse spre rezolvare :
1. Fie un graf orientat, pentru care citim din fișieru l ARCE.IN, valoarea n, m, x și cele m
perechi de arce. Afișați pe ecran matricea de adiac ență, numărul drumurilor care încep
în x și numărul celor care se termină în x.
2. Să se verifice dacă o secvență de noduri reprezintă un drum elementar sau neelementar
într-un graf orientat. Mesajul va fi afișat pe ecra n. Numărul de noduri=n, numărul de
arce=m și cele m arce se citesc din fișierul DRUM.I N. Secvența de la tastatură are k
elemente.
3. Fiind dat un graf orientat cu n noduri și m arce de finit prin matricea vârfuri-arce în
fișierul VARF_ARC.IN, afișați pe ecran mulțimile Γ+ și Γ- pentru un nod x citit din
fișier (pe linia 1: n,m; liniile 2 – n+1 matricea, iar pe ultima linie valoarea x).
58
CAPITOLUL III
PROIECTAREA ACTIVITĂȚII DIDACTICE
LA DISCIPLINA „INFORMATICĂ”
Proiectarea didactică reprezintă o modalitate de pregătire cu rigurozitat e, pe
temeiuri științifice a activităților instructiv-edu cative. Ea constituie o cerință a teoriei
generale, a activității efective, potrivit căreia „ orice lucru bine făcut este rezultatul unui
proiect bine gândit.”
Proiectarea se referă la „operațiile de construcți e și organizare anticipativă, a
obiectivelor, conținutului, strategiilor de dirijar e a învățăturii, problemelor de evaluare și
mai ales a relațiilor dintre acestea.”
Putem spune că proiectare didactică este o activitate complexă , un proces de
anticipare a ceea ce dorește profesorul să realizeze împreună cu elevii săi în cadrul unei
lecții, sistem de lecții, temă, capitol sau pe parc ursul întregului an școlar pentru realizarea
obiectivelor programei la disciplina pe care o pred ă.
Ca orice acțiune bine gândită, proiectarea activit ății didactice presupune răspunsul
la patru întrebări esențiale, aranjate într-o anumi tă ordine care sugerează etapele principale
ale proiectării didactice.
Etapele Proiectării didactice
Întrebări Mod de realizare
1. Ce vei face? Precizarea în mod clar a obiectivelor
2. Cu ce voi face? Analiza resurselor educaționale de care
dispunem (în primul rând a conținutului
înșiruirii)
3. Cum voi face? Alcătuirea strategiei educaționale potrivite pentru
realizarea obiectivelor
4. Cum voi ști dacă ceea ce
trebuie realizat s-a realizat? Elaborarea sistemului de evaluare a activității.
59
3.1 OBIECTIVE PEDAGOGICE ȘI OPERAȚIONALE
3.1.1 Obiectivele cadru ale disciplinei informatica în învățământul
preuniversitar
Obiectivul didactic poate fi privit ca o schimbare, o transformare a comportamentului
elevului pe care intenționăm să o obținem prin lecț ie. Prin el indicăm ce urmează „să știe” și
„să facă” tânărul. Obiectivele cadru au valoare de ghid permanent și au un grad ridicat de
generalitate și complexitate. Ele au o structură com ună pentru toate disciplinele aparținând unei
arii curriculare și au rolul de a asigura legătura strânsa și armonioasă între acestea. Obiectivele
cadru indică scopuri pentru mai mulți ani de instru ire, pentru o întreagă perioadă de
școlarizare. Obiectivele cadru ale informaticii tre buie să indice ce se urmărește prin
introducerea studiului acestei discipline în școală.
Formarea deprinderilor de lucru cu informația (stocare, prel ucrare și
transmitere)
Orice domeniu de activitate implică o cantitate im portantă de informație cu care se
operează continuu și care este stocată pe calculato r. De aceea este nevoie de oameni care să știe
să prelucreze cu profesionalism informația, rapid, corect și sigur. Prelucrarea informației
constă în stocarea eficientă, prelucrarea propriu-z isă și transmiterea ei.
Dezvoltarea deprinderilor moderne de utilizator
Calculatorul este un instrument care nu este nece sar să fie folosit numai la locul de
muncă, el putând servi pe oricine în diverse scopur i (redactări de documente, transmitere de
mesaje etc.). De aceea este necesar ca elevului să i se formeze o bază, „o cultură informatică”,
formată din cunoașterea principalelor componente al e calculatorului, a funcționării rețelelor de
calculatoare, a interfețelor utilizator, a celor ma i cunoscute sisteme de operare și utilitare,
modul lor de instalare, exploatare și utilizare. Po rnind de la aceste cunoștințe, elevul trebuie să
poată să se adapteze la evoluțiile previzibile ale mediului social.
Dezvoltarea gândirii algoritmice
În realizarea acestui obiectiv informatica aduce o contribuție esențială. Împreună cu
celelalte științe exacte, informatica are rolul de a forma și dezvolta gândirea. Spre deosebire de
matematică, care formează în general o gândire abst ractă, teoretică, informatica dezvoltă
gândirea algoritmică, practică, prin faptul că elev ii sunt puși să rezolve probleme concrete
printr-o analiză amănunțită și progresivă a detalii lor. Ei trebuie să deprindă modul de
60
examinare și de rezolvare a unei probleme cât mai e ficient posibil, prin urmărirea unor pași
stabiliți de algoritmul ales.
Dezvoltarea deprinderilor muncii individuale
În faza de învățare, elevul este într-un permanent dialog cu calculatorul, testând
cunoștințele teoretice însușite sau căutând să și l e îmbogățească. Calculatorul este un
instrument amabil, dintr-un anumit punct de vedere, el se mulează perfect personalității
elevului – răspunde prompt cerințelor bine formulat e, nu-și pierde niciodată răbdarea – oferind
posibilitatea lucrului diferențiat cu cei talentați sau cu cei care lucrează mai lent. De aici rezultă
că informatica dezvoltă deprinderea de a lucra indi vidual. Acest lucru nu este totuși foarte bun,
deoarece dus la extrem poate conduce la formarea un or trăsături cum ar fi individualismul sau
egoismul, neadaptarea socială.
Dezvoltarea deprinderilor muncii colective
După cum am arătat mai sus, lucrul cu calc ulatorul conduce la dezvoltarea deprinderilor
muncii individuale. Este datoria profesorului să ev ite pe cât posibil ajungerea la excese, o
soluție fiind educarea elevilor în spiritul unei ac tivități desfășurate în grup, în colaborare.
După cum știm, majoritatea activităților întâlnite î n viața reală se desfășoară în echipă.
Profesorul trebuie să gândească proiecte pentru ech ipe de elevi, să coordoneze și să urmărească
modul de desfășurare a muncii în comun; proiectele trebuie să fie împărțite în activități
individuale, care ulterior trebuie interconectate, elevii trebuind să învețe să preia și să transmită
informații; munca de împărțire a proiectului pe mod ule poate fi realizată chiar de grup sau de
un lider al grupului, evident sub îndrumarea profes orului. Pentru un elev învățat să rezolve
singur o problemă de la început până la sfârșit, va fi foarte greu să privească în ansamblu o
lucrare de proporții mai mari și mai ales să modula rizeze. Rețelele de calculatoare sunt un bun
și foarte atractiv mijloc de transmitere a informaț iei între utilizatorii de calculatoare.
Obișnuirea elevilor cu diverse responsabilități pri vind finalizarea propriei munci și asigurarea
înlănțuirii unor elemente realizate în paralel, îi va pregăti pentru o activitate pe care cu
siguranță o vor întâlni în viitor.
Formarea capacității de analizare a problemei și de identificare a soft-
ului potrivit
Pus în fața unei probleme, elevul trebuie să fie ca pabil să o analizeze, să-i descopere cerințele
și, pe baza lor, să aleagă soft-ul cel mai adecvat. Dar, pentru a putea alege, el trebuie să știe de
existența mai multor tipuri de software și să le cu noască caracteristicile esențiale, trebuie, altfel
spus, să-și formeze o cultură generală informatică.
61
Dezvoltarea spiritului inventiv și creator
Alegerea metodei de rezolvare a problemei trebuie l ăsată la latitudinea elevului; este
bine ca el să fie îndrumat și motivat să aleagă cale a optimă, dezvoltându-și astfel spiritul
inventiv și creator. Elevul trebuie să fie conștient că ceea ce realizează trebuie să funcționeze
și, mai mult, trebuie să fie utilizabil, adică să fi e, pe cât posibil, un produs finit.
Calitățile unui produs finit sunt:
− interfață prietenoasă;
− bună funcționare;
− fiabilitate (aplicațiile trebuie verificate și testa te);
− performanță (complexitate mică, eficiență);
− portabilitate;
− întreținere facilă.
Folosirea tehnologiei informației în scopul rezolvă rii unor probleme
După cum am mai spus, la obiectul informatică trebu ie rezolvate probleme practice și ar
fi de dorit ca profesorii altor discipline să solic ite aplicații care să poată fi folosite în cadrul
unor lecții; acest lucru ar putea motiva elevul, el trebuind, pe de o parte, să înțeleagă cerințele
aplicației pe care trebuie să o dezvolte și teoria pe care se bazează, iar pe de altă parte, să
utilizeze informațiile dobândite la informatică.
Conștientizarea influenței informaticii asupra soci etății
Rolul computerului în viața socială și economică es te major. Elevii trebuie să
conștientizeze avantajele și riscurile care derivă d in utilizarea calculatoarelor, respectiv a
rețelelor, a serviciilor Internet etc.
Formarea unei conduite și a unei moralități profesi onale .
Elevii trebuie să cunoască prevederile legale cu pr ivire la dreptul de autor,
confidențialitatea informației, efectul dezvăluirii sau distrugerii informației prin spargeri de
parole, virusare, etc.
Obiectivele de referință
Obiectivele de referință sunt cele care indică scop uri ale învățării pe termen scurt, de
obicei sunt rezultatele așteptate la finalul unui a n de studiu și urmăresc progresul școlar al
elevului de la un an la altul.
De exemplu, pentru obiectivul cadru “Dezvoltarea deprinderilor de utilizare a unui
sistem de calcul și a unor produse software de largă răspândire”, vom formula obiective de
referință astfel:
La sfârșitul clasei a IX-a elevul va fi capabil:
62
1. să cunoască componentele și modul de utilizare a unu i calculator;
2. să cunoască și să utilizeze eficient dispozitivele p eriferice standard;
3. să cunoască modul de organizare a memoriei și modul de reprezentare în memorie a
informației;
4. să utilizeze un sistem de operare cu interfață elem entară;
5. să explice funcțiile unui sistem de operare;
6. să cunoască și să utilizeze un program simplu de asi stență a sistemului de operare (
ex. Norton/Windows Commander, Windows Explorer etc. );
7. să utilizeze un editor de text și un editor grafic pentru realizarea unor documente
simple; documente multimedia.
Pentru obiectivul cadru “Dezvoltarea spiritului inventiv și creator”, se pot da ca
obiective de referință astfel:
La sfârsitul anului școlar, elevul să fie capabil:
1. să desfășoare activități de lucru în echipă;
2. să participe activ la prezentarea și dezbaterea uno r lucrări practice realizate
împreună cu alți colegi.
3.1.2 Operaționalizarea obiectivelor
Operaționalizarea constă în formularea corectă și c lară a obiectivelor, transpunerea
lor în termeni de operații, acțiuni și comportament e observabile și măsurabile.
Ca sursă a unei tehnologii didactice, un obiectiv pedagogic specific deține două
funcții:
/head2right precizează un rezultat dorit la care trebuie să aju ngă elevii care învață,
menționând ce vor trebui să știe să facă la sfârșit ul unei perioade de învățare;
/head2right direcționează evalarea cât mai riguroasă a unui rez ultat concret obținut de
elevi.
Pentru a putea îndeplini aceste funcții, formulare a unui obiectiv trebuie să satisfacă
mai multe cerințe:
1. să descrie comportamentul final al elevului dorit a se forma prin învățare,
indicând o acțiune observabilă prin care să poată f i exteriorizat comportamentul respectiv ;
2. să precizeze condițiile în care acest comportament urmează să se realizeze;
3. să stabilească criteriile performanței accesibile.
/head2right În descrierea comportamentului elevului se vor avea în vedere următoarele:
/square4 Obiectivele se referă la activitatea elevului și nu a profesorului
63
Formulări corecte Formulări incorecte
elevul să compare …………..
elevul să analizeze …………..
elevul să identifice ………….. să familiarizez elevii cu ……………………
să transmită cunoștințe despre …………..
a demonstra elevilor ………………………..
/square4 Obiectivele se exprimă prin cuvinte (verbe) c are indică acțiuni, comportamente,
procese constatabile, observabile.
Formulări corecte Formulări incorecte
elevul să reprezinte grafic………
elevul să aplice …………..……..
elevul să descrie ……………..…. elevii vor asimila ………………………….. ………
elevii vor înțelege………………………….. ………
elevii vor cunoaște …………………………. ……..
Pentru disciplinele de specialitate pot fi fo losite următoarele verbe raportate la tipurile
de comportamente dorite:
o însușirea unor noi cunoștințe: a exprima, a recunoa ște, a defini, a identifica
etc;
o formarea deprinderilor intelectuale: a rezolva, a d emonstra, a reprezenta, a
interpreta, a diferenția, a calcula, a clasifica, a ordona, a demonstra, a analiza, a
separa,a identifica, a deduce, a examina, a formul a, a sintetiza, a prezenta, a
argumenta, a decide, a utiliza etc.;
o formarea deprinderilor motorii și senzoriale: a exe cuta, a realiza, a reconstrui,
a reproduce, a planifica etc.
o formarea atitudinilor: a accepta, a persevera, a în curaja, a respecta, a convinge,
a alege etc.
/square4 Fiecare obiectiv va viza o singură operație sau acț iune, o singură sarcină de învățare;
/square4 Obiectivele să fie exprimate în cât mai puține cuvi ne.
/head2right Cea de a doua condiție de operaționalizare pune în evidență condițiile concrete
în care elevii trebuie să dovedească comportamentul proiectat. Frazele care precizează
condiție încep de regulă cu expresiile: fiind date. ……….; având acces la ………..; pus în
situația de …………; fără a utiliza ………. ….; confruntat cu …………..
Condițiile vizează procesul învățării, dar și veri ficării/evaluării.
/head2right Stabilirea criteriilor de performanță (evaluarea) e ste cea de a treia condiție de
operaționalizare. Ea precizează eficiența învățării , nivelul la care trebuie să se ridice
cunoștințele, priceperile, deprinderile elevilor, a rată în ce măsură au fost atinse obiectivele
proiectate. Criteriile de reușită pot fi calitative și cantitative cum ar fi:
o numărul minim de răspunsuri corecte pretinse
64
o limita de timp. Exemplu: având la dispoziție maxim 10 min………;
o numărul de încercări sau erori admise. Exemplu: se admit maxim două
omisiuni
Operaționalizarea obiectivelor presupune determ inarea riguros științifică cel
puțin a standardelor minimale de performanță.
3.2 METODE DE ÎNVĂȚĂMÂNT FOLOSITE
ÎN PREDAREA DISCIPLINEI „INFORMATICĂ”
Informatica, sau oricare altă disciplină, nu poate fi predată utilizând o singură metodă.
Dacă în trecut, în predare se utiliza o singură met odă, cea considerată cea mai bună, astăzi se
acceptă folosirea unei mari varietăți de metode și mai ales combinarea lor. Metoda este o cale
eficientă de organizare și conducere a predării și învățării, un mod comun de a proceda, care
reunește într-un tot unitar eforturile profesorului și elevilor.
Procesul de învățământ se supune legii generale de apreciere a oricărei activități
umane – aceea de a obține rezultate cât mai bune cu mijloacele cele mai adecvate și
potrivite scopurilor și obiectivelor anticipate. Ca lea principală prin care se realizează acest
lucru este perfecționarea tehnologiei didactice, re spectiv a metodelor și mijloacelor prin
care se ajunge la rezultatul scontat.
Metodele de învățământ reprezintă modalități siste matice de lucru de care se poate
servi profesorul în activitatea de predare și elevi i în activitatea de învățare, capabile să
conducă spre realizarea obiectivelor pedagogice pro puse.
Rezultă că metoda evidențiază modalitatea de lucru o manieră de a acționa practic în
mod sistematic și planificat, un demers programat c are se află în permanență în atenția
profesorului. Așa cum se poate observa metoda de în vățământ care nu poate fi detașată de
contextul practic reflectă caracterul procesual, în săși demersul acțiunii didactice.
Din perspectiva profesorului metodele de învățământ servesc la organizarea și co nducerea
unei activități sistematice pe care elevii vor real iza obiectivele pedagogice, arătându-i
Metoda
didactic` Conținutul
instruirii
Resurse
materiale
Principii și
norme Resurse
umane
Verificare,
evaluare și
notare Obiective
65
elevului “ce sa facă” și “cum să acționeze”. Din perspectiva elevului metodele de
învățământ au menirea de a-i sprijini se parcurgă c alea spre cunoaștere, spre dobândirea de
noi comportamente care îi sporesc valoarea personal ității.
3.2.1 Clasificarea metodelor de învățământ
Metodele de învățământ sunt o componentă importantă a strategii lor didactice
reprezentând sistemul de căi, modalități, procedee și tehnici adecvate de instruire care
asigură eficiența procesului de predare-învățare. Manualele de pedagogie prezintă diferite
clasificări ale metodelor de învățământ care reflec tă variante, puncte de vedere.
Clasificarea metodelor de învățământ propusă de I. Cerghit :
1 Metode de comunicare Expozitive (orale) Descrierea
Explicarea
Prelegerea
Dialogate (orale) Conversația
Asaltul de idei
Problematizarea
Scrise Munca cu manualul și alte cărți
Lectura independentă
2 Metode de explorare Directă (investigare) Observația
Experimentul
Studiul de caz
Indirectă
Demonstrația
Modelarea
3 Metode de acțiune Reală Exercițiul
Algoritmizarea
Lucrarea de proiect
Fictivă Învățarea prin simulare
Jocuri didactice
4 Metode de instruire
programată
În procesul instructiv educativ al disciplinei info rmatică pot fi folosite oricare dintre
aceste metode, o pondere mai mare având instruirea prin metode active; problematizarea,
explorarea directă, metode bazate pe acțiune etc. În diferitele momente ale lecției
66
profesorul optează pentru folosirea metodelor care oferă potențialul pedagogic cel mai
adecvat față de obiectivele care urmează a fi reali zate de elevi.
3.2.2 Metode specifice de predare a informaticii
Metode de predare
Enumerăm în continuare cele mai des practicate meto de pe care profesorul le are la
dispoziție pe parcursul predării.
3.2.2.1 Metode de comunicare orală
Metodele din această grupă au comun faptul că se fo losesc de limbaj în diferitele sale
forme. Atuul principal al acestor metode este posib ilitatea profesorului de a adapta nivelul,
ritmul și conținutul lecției, în funcție de semnale le implicit sau explicit primite din partea clasei
privind recepționarea expunerii. În cadrul metodelo r de comunicare orală se disting:
3.2.2.2 Metode expozitive
• povestirea;
• descrierea;
• explicația;
• prelegerea (prelegerea școlară, cursul magistral, p relegerea cu oponent,
prelegerea gen dezbatere);
• instructajul;
• conferința, etc.
Expunerea, în variatele ei forme, se dovedește a f i una dintre cele mai simple și
funcționale căi de predare, directă și rapidă, econ omică și foarte eficace. În timp scurt se poate
comunica și recepta un volum mare de informații. Ne ajunsurile ei sunt: pasivitatea elevilor care
primesc cunoștințele de-a gata, posibilitatea gener ării superficialității și formalismului în
învățare, fluxul unidirecțional de comunicare.
3.2.2.3 Metode conversative
• conversația (reproductivă, euristică);
• problematizarea;
• învățarea prin redescoperire;
• seminarul, etc.
67
Dacă metodele expozitive au ca principal dezavantaj starea de pasivitate a elevilor și
preluarea semipreparatelor oferite de cadrul didact ic, care se memorează și se reproduc la
nevoie, metodele conversative, dimpotrivă, activize ază auditoriul, îl implică în transmiterea
noilor cunoștințe, obligându-l să facă efortul inte lectual impus de solicitările prin întrebări ale
cadrului didactic. Din păcate, metodele conversativ e nu pot fi utilizate oricând și oricum, și mai
ales pe problemele pentru care auditoriul nu are un anumit nivel de informații. Un rol
important îl are conversația în lecțiile în care nu se comunică cunoștințe noi, ci se aplică cele
cunoscute, deci în metoda exercițiului. În informat ică, aplicarea teoriei în practică, trecerea de
la general la particular are o importanță mult mai mare decât la alte obiecte de învățământ.
În cadrul metodelor conversative, un rol important îl are învățământul problematizat .
Noțiunea care indică specificul acestui învățământ este situația – problemă. Aceasta este o stare
conflictuală care se creează în mintea elevului înt re solicitările problemei propuse și
cunoștințele existente în momentul respectiv. Situa ția – problemă este o noțiune care premerge
însăși problema. Trebuie să remarcăm faptul că, în multe exemple, distanța dintre situația –
problemă și problema formulată este foarte mică; pr ima solicită doar avansarea unei păreri, pe
când a doua este deja formalizată într-un limbaj sp ecific. Ceea ce urmează poate ține de
metoda redescoperirii ; adică, elevul trece la rezolvarea problemei fără să aibă o metodă sau o
recomandare precisă; profesorul trebuie să-l conduc ă pe elev spre descoperirea metodei dorite
de rezolvare a problemei. De exemplu, metoda Divide et Impera poate fi introdusă cu ajutorul
problemei căutării unui element într-un șir ordonat . Elevul imediat se gândește la clasica
metodă de comparare a elementului respectiv cu toat e componentele șirului. Bineînțeles că
această metodă trebuie acceptată cu observația că, dacă elementul căutat se află spre coada
șirului atunci numărul de comparări tinde către lun gimea șirului. Sugestii binevenite din partea
profesorului – dacă ele nu vin din partea elevului – ar fi ordonarea șirului, compararea
elementului cu cel din mijloc și prin urmare, înjum ătățirea intervalului de căutare. Abia după
rezolvarea problemei, care nu este foarte dificilă, profesorul poate enunța numele acestei
metode de rezolvare cu ajutorul căreia se rezolvă o întreagă gamă de probleme.
V. Okon sistematizează foarte bine aceste idei în citatul următor : “La modul cel mai
general, prin predare problematizată înțelegem ansa mblul unor astfel de activități ca
organizarea situațiilor problematice, formularea pr oblemelor (treptat sunt atrași în acest proces
elevii înșiși), acordarea ajutorului indispensabil elevilor la rezolvarea problemelor și în
verificarea soluțiilor, în sfârșit, coordonarea pro cesului de sistematizare și fixare a
cunoștințelor astfel dobândite. Măiestria profesoru lui se poate manifesta în cel mai pregnant
mod, în organizarea situațiilor problematice în ses izarea și formularea problemelor, rezolvarea
68
și verificarea soluțiilor, care sunt și principale le momente ale procesului învățării
problematizate.”
3.2.2.4 Metode de comunicare scrisă
Aceste metode includ: lucrul cu manualul și alte su rse bibliografice, descoperirea prin
analogie și învățământul programat. De obicei, manu alul este folosit acasă, pentru rezolvarea
temelor, lucru considerat benefic pentru adâncirea, completarea și analiza materiei deja predate
de profesor. Informatica este un domeniu în care st udiul individual este necesar deoarece
informația se îmbogățește continuu și cu rapiditate . Nu puțini sunt elevii de liceu care cer
informații și materiale suplimentare. Și acest lucr u nu este valabil numai pentru informatică.
Elevul trebuie pregătit pentru studiu individual, e l trebuie să învețe să-și caute materialul
bibliografic de care are nevoie și să-l cerceteze a tât amănunțit cât și selectiv. Metodele de
comunicare orală sunt deficiente din acest punct de vedere, elevul primind de la profesor
informația gata selectată și prelucrată. De aceea a r fi folositor ca profesorul să rezerve câteva
ore “predării” modului de folosire al manualului.
Metodele de comunicare scrisă sunt influențate în mod decisiv de manualele utilizate.
În construirea manualelor de informatică s-a ținut cont de cerințele de corectitudine și
accesibilitate, dar a cam fost omisă cerința de atr activitate – design-ul lasă de dorit, iar modul
de expunere ar putea fi îmbunătățit.
Pentru reușita unei ore de predare, metodele preze ntate mai sus trebuie combinate și
dezvoltate pe baza experienței fiecărui profesor. E xistă însă câteva elemente de care trebuie să
se țină seama:
• domeniul propriu-zis al disciplinei;
• conținutul științific;
• categoria de vârstă;
• obiectivele generale și specifice;
• nivelul clasei;
• personalitatea clasei;
• personalitatea profesorului;
• convingerile profesorului.
În continuare vom prezenta metode specifice de abo rdare a predării diferitelor domenii
din informatică.
3.2.2.5 Metoda predării algoritmilor și tehnicilor de progr amare
Predarea algoritmilor trebuie să aibă ca obiectiv p rincipal formarea la elev a deprinderii
de a gândi logic, algoritmic. Pentru realizarea lui , un profesor trebuie să urmărească
următoarele etape:
69
• formalizarea problemei – enunțul problemei trebuie bine înțeles (ce se dă și ce se
cere); traducerea problemei într-un limbaj adecvat;
• pe baza problemei formalizate, respectând riguros s pecificațiile, se construiește
algoritmul folosind schema logică sau limbajul pseu docod. Aceste două noțiuni
se introduc la început cu ajutorul unor probleme ex trem de simple. De exemplu
pentru citire / scriere se enunță probleme de genul : „să se afișeze un mesaj” sau
„să se citească și să se afișeze un număr”, pentru structura liniară: „să se calculeze
suma a două numere”, „să se interschimbe valorile a două variabile”, etc.
• construirea algoritmilor pentru probleme cu grad de dificultate din ce în ce mai
mare. Este indicat ca aceste probleme să fie grupat e în clase după tipul lor. Astfel,
se pot forma clase de probleme cu numere, șiruri, m atrice.
3.2.2.6 Metoda predării unui limbaj de programare
Limbajul de programare este folosit ca un instrumen t în rezolvarea problemelor. După
cum am văzut, primii pași și cei mai importanți în rezolvarea unei probleme sunt formalizarea
ei și construirea algoritmului. Dar, pentru ca prob lema să fie pe deplin rezolvată, este necesar
ca algoritmul să fie transpus într-un program (folo sind un limbaj de programare). În ceea ce
privește predarea elementelor unui limbaj de progra mare există două tendințe:
• elementele limbajului de programare se predau într- o anumită ordine, stabilită pe
baza unor criterii. În acest caz, problemele sunt s ituate pe planul al doilea, ele
fiind folosite pentru aprofundarea noțiunilor învă țate;
• elementele limbajului sunt introduse cu ajutorul un or exemple concrete de
probleme rezolvate, urmând ca discutarea detaliilor să se facă ulterior. Această
metodă ar trebui să fie preferată, deoarece se știe că elevii sunt repede plictisiți
de teoretizări; ei doresc să vadă ceva concret. La clasa a IX-a, când se studiază
atât algoritmii cât și limbajul Pascal, atenția ele vilor este mult mai ușor de captat
dacă, de la început, elevul este pus în fața unei p robleme practice pe care
rezolvând-o, obține un rezultat – astfel el trebuie să construiască atât algoritmul
cât și programul.
Obs: Când se predă un al doilea limbaj de programare (d e exemplu în clasa a XI-a „C”-ul) este
recomandat să se evidențieze asemănări sau diferenț e între acesta și cel știut deja. Nu este însă
recomandat să se traducă programe dintr-un limbaj î ntr-altul.
70
3.2.2.7 Metoda predării sistemelor utilitare
Sistemele utilitare au fost de curând introduse în școli, profesorul având la dispoziție o
oră pe săptămână. Ar fi de dorit ca aceste ore să s e desfășoare într-un laborator dotat cu
calculatoare sau măcar într-o sală cu un calculator la care să lucreze, pe rând, fiecare elev.
În general, cea mai bună metodă de predare a sistem elor utilitare, este tot cea care
pornește de la o problemă concretă, simplă și cărei a pe parcurs i se tot adaugă câte un element.
De exemplu, în cazul unui editor de texte, se porne ște de la un text simplu, care, în timp, se
transformă cu ajutorul modificării fonturilor, form atărilor de paragrafe, introducerii de culori,
desene etc.
3.2.2.8 Metoda predării analizei numerice
Analiza numerică este o frontieră între matematică și informatică în sensul că se ocupă
cu construirea unor algoritmi de rezolvare a unor p robleme matematice greu de rezolvat cu
creionul. În general metoda folosită în predarea ac estei materii este cea orientată pe problemă.
Se pornește de la o problemă matematică concretă și se sugerează metoda de rezolvare care
urmează să fie construită pas cu pas cu ajutorul el evilor. Dacă există mai multe metode de
rezolvare este bine să se facă o comparație între e le pentru a le pune în evidență calitățile. De
exemplu pentru rezolvarea unei ecuații algebrice vo r fi prezentate metoda înjumătățirii, a
coardei, a tangentei.
Instrumente de predare
Metodele practicate de profesorul de informatică vo r fi eficiente dacă acesta va apela la:
− calculator;
− soft-uri educaționale și soft-uri de învățare de ti p Tutorial (este bine să se facă
cunoscute aceste soft-uri și profesorilor de alte s pecialități);
− produsele software adecvate învățării la nivelul cl asei respective;
− cărți, reviste de specialitate, documentații;
− retroproiector;
− programe demonstrative;
− studiul comparativ între noțiuni deja învățate;
− cât mai multe exemple simple din viața de zi cu zi;
− exersarea desfășurării unor activități în grup.
71
3.2.2.9 Metode bazate pe acțiune
3.2.2.9- a) Exercițiul
Metoda constă în efectuarea conștientă și repetată a unor acțiuni și operații în scopul
formării unor deprinderi teoretice și practice, con solidării cunoștințelor dezvoltării unor
capacități și aptitudini, stimulării potențialului creativ.
Exercițiul este o metodă care stimulează intens ac tivitatea elevului, solicitând din
partea acestuia efort intelectual sau fizic. Aceast ă metodă are o largă aplicabilitate putând fi
folosită la toate clasele și obiectele da studiu pe ntru realizarea unor variate sarcini didactice
cum ar fi:
/head2right formarea deprinderilor de natură intelectuală și pr actică;
/head2right mai buna înțelegere a cunoștințelor teoretice prin aplicarea lor în situații și
contexte diferite;
/head2right consolidarea cunoștințelor și deprinderilor însușit e anterior;
/head2right prevenirea uitării, evitarea fenomenului de interfe rență;
/head2right dezvoltarea operațiilor mentale, formarea de struct uri operaționale;
/head2right dezvoltarea unor capacități intelectuale și fizice, a unor trăsături de voință și de
caracter;
Exercițiul nu trebuie înțeles ca având numai un ca racter introductiv ci și un caracter
productiv atunci când se desfășoară sub forma unor activități libere, creatoare.
Reținem în concluzie, că bine concepute și organiz ate exercițiile contribuie la
înzestrarea elevului cu deprinderile și capacităție de muncă.
3.2.2.9-b) Metoda lucrărilor practice
Constă în efectuarea de către elevi a unui ansamblu de acțiuni cu caracter practic-
aplicativ, în scopul mai bunei înțelegeri și consol idări cunoștințelor însușite, aplicării
acestora prin rezolvarea unor probleme practice, te hnice, dobândirii unor priceperi și
deprinderi practice în activitatea productivă, cult ivării unei atitudini pozitive față de
muncă.
3.2.2.9- c) Metoda proiectelor
În pedagogia modernă prin metoda proiectelor se înț elege modalitatea de învățare
prin îmbinarea cunoștințelor teoretice cu activitat ea practică. Elevul se deprinde astfel să
72
învețe din cercetarea și din activitatea practică. Proiectul se distinge ca o metodă globală cu
caracter de interdisciplinaritate, care stimulează și dezvoltă pe multiple planuri
personalitatea în curs de e formare a celor pe care îi instruim.
Proiectul poate lua forme variate, în funcție de s copul urmărit, de gradul de
complexitate al temei și de specificul disciplinei etc.
După scopul urmărit distingem:
/head2right proiecte de absolvire a unui ciclu școlar (liceu, ș coală profesională);
/head2right proiecte de an, de semestru care materializează efo rtul pe o perioadă limitată de
muncă școlară;
/head2right lucrare științifică – pregătită pentru seminarii, s esiuni, simpozioane științifice
etc.
După forma concretă sub care se prezintă proiecte le pot fi:
/head2right modele, machee, aparate, dispozitive tehnice, refer ate teoretice etc.
Elaborarea proiectelor presupune desfășurarea unor activități dintre cele mai variate:
documentarea teoretică, microexperimente, investiga ții cu propunerea unor soluții,
confecționarea unor materiale didactice, elborarea de scheme, schițe, grafice, construirea
unor aparate, mașini etc.
La eleborarea proiectelor pe lângă documentarea te oretică se desfășoară și alte
activități, vizite, emitere de ipoteze, găsirea de soluții și verificarea lor etc.
Elevii sub îndrumarea profesorului își vor alege m odul de lucru, vor stabili mijloacele
materiale și tehnologice, vor realiza autocontrolul îndeplinirii sarcinilor.
Profesorului îi revine sarcina de animator, comsul tant sau for de avizare și sancționare a
rezultatelor parțiale și finale.
73
3.3 MIJLOACE DE ÎNVĂȚĂMÂNT NECESARE ÎN
PREDAREA
DISCIPLINEI “INFORMATICĂ”
Mijloacele de învățământ sunt resurse materiale care pot sprijini activitate a de
învățare a elevilor dar și desfășurarea procesului de instruire în vederea realizării obiectivelor
pedagogice și de evaluare a rezultatelor școlare, i nstrumente pedagogice folosite în procesul de
instruire.
Există o diversitate de mijloace de învățământ înt r-o continuă perfecționare datorită corelării
lor cu tehnica.
3.3.1 Funcțiile pedagogice ale mijloacelor de învă țământ
Mijloacele de învățământ îndeplinesc o serie de fun cții pedagogice și anume:
/head2right Funcția de comunicare – transmite direct informațiile despre obiectele,
fenomenele, faptele, evenimentele studiate, ajutând u-i pe elevi să-și lărgească orizontul de
cunoaștere.
/head2right Funcția instructiv – demonstrativă – asigură o bază receptivă, care face mai
accesibilă și convingătoare informația transmisă, p rin vizualizarea unor obiecte, fenomene,
procese greu accesibile sau inaccesbile observației directe.
/head2right Funcția formativ -educativă – contribuie la creșterea gradului de organizarea și
structurare a informației. Are efecte benefice pe p lanul dezvoltării atenției, memoriei,
imaginației, formării de deprinderi.
/head2right Funcția stimulativă/de motivare a învățării – evidențiază rolul mijloacelor de
învățare în stimularea curiozității în cultivarea, îmbogățirea și diversificarea intereselor, a
trăirilor a dorinței de a se autoperfecționa.
/head2right Funcția de raționalizare a efortului și timpului – activitatea de predare-
învățare, decurge prin posibilitatea unor mijloace de învățământ de a permite o mai rațională și
eficientă utilizare a timpului de instruire, concom itent cu diminuarea efortului depus pentru
rezolvarea unor sarcini. Această funcție se evidenț iază în cazul folosirii planșelor, graficelor,
machetelor, calculatoarelor etc.
/head2right Funcția de evaluare a randamentului școlar – constă în posibilitatea de a
măsura și aprecia nivelul de pregătire al elevilor, progreselor înregistrate de aceștia pe
parcursul unui program de instruire. Sunt mijloace de învățământ ce îi pun pe elevi în situația
de a opera cu datele învățate (să identifice, să co mpare, să explice, să interpreteze) pentru a
soluționa diferite probleme, a rezolva diferite sar cini de învățare.
74
3.3.2 Clasificarea mijloacelor de învățământ
După funcția îndeplinită, după rolul dominant pe ca re îl îndeplinesc în activitatea
didactică, mijloacele de învățământ se pot grupa în 4 categorii.
1. Mjloace informativ-demonstrative – reprezintă importante surse de
informații, servesc la transmiterea unor informații , la ilustrarea,
exemplificarea, concretizarea cunoștințelor, îndepl inind în principal funcții
informative și demonstrative.
2. Mijloace de exersare și formare a deprinderilor – această categorie de
mijloace asigură efectuarea experiențelor și experi mentelor, învățarea prin
descoperire, efectuarea de exerciții necesare formă rii priceperilor și
deprinderilor, exersarea creatoare a unor aptitudin i practice de muncă
productivă. Din această categorie de mijloace fac p arte: truse de laborator,
aparate de laborator (microscop, refractometru, etc ), echipamente tehnice,
utilaje și instalații de atelier, etc.
3. Mijloace de raționalizare a timpului în orele de curs – includ: planșe,
machete, folii pentru retroproiector, etc.
4. Mijloace pentru evaluarea rezultatelor învățării – pentru evaluarea
rezultatelor se folosesc: seturi de teste, aparate sau instalții de testare,
dispozitive de verificarea a deprinderilor, mijloac e tehnice audio-vizuale.
Alegerea materialelor didactice depinde de cunoașt erea caracteristicilor lor, de
avantajele și dezavantajele lor.
Mijloacele de învățământ cuprind toate resursele materiale ale procesului de învățare
care au un conținut informațional în raport cu obie ctivele ca urmează a fi realizate și la care se
recurge pentru a ușura comunicarea, înțelegerea, fi xarea, evaluarea și aplicarea cunoștințelor.
Varietatea obiectivelor pedagogice ale lecției nece sită diferite mijloace de învățământ pentru
realizarea obiectivelor de instruire și de un poten țial valoros de comunicare, de activitatea, de
formare economic
75
3.4 EVALUAREA RANDAMENTULUI ȘCOLAR
3.4.1 Înnoiri aduse domeniului evaluării de tehnol ogia
didactică modernă
Evaluarea rezultatelor școlare reprezintă un aspect esențial al procesului de învățare. Ea
însoțește activitatea instructiv – educativă în toa te etapele sale, construind punctual de plecare
și premiza autoreglării și perfecționării continue a acestei activități, a sistemului de învățământ
în general.
În evaluarea activității școlare trebuie să se țină seama de câteva transformări care au
survenit în ultimul timp. Acestea au drept scop o r edimensionare și o regândire a strategiilor
evaluative, în consens cu o serie de exigențe, avân d în vedere implicațiile majore ale efectelor
evaluării asupra psihicului, asupra motivației elev ului. Aceste schimbări vizează în principal
următoarele aspecte:
/head2right diversificarea tehnicilor de evaluare (extinderea f olosirii testului docimologic, a
lucrărilor cu caracter de sinteză, folosirea metode lor moderne);
/head2right centrarea evaluării asupra rezultatelor pozitive și nesancționarea în permanență a
celor negative;
/head2right transformarea elevului într-un partener autentic al profesorului în evaluare, prin
autoevaluare, prin interevaluare, etc.;
Centrată pe prestația elevului, funcția evaluării este aceea de măsurare a randamentului
școlar a progresului realizat de elevi, pentru a șt i cât mai corect unde se situează aceștia în
raport cu obiectivele educaționale.
Alături de funcția de măsurare a randamentului, a p restației școlare, evaluarea prezintă
și o certă valoare motivațională.
Verificarea / ascultarea ritmică îi face pe elevi s ă învețe cu regularitate, între frecvența
ascultării la lecție și reușita școlară există o co relație directă. „Ar fi cu totul nerealist să ne
așteptăm ca elevi să învețe cu regularitate, sistem atic și conștiincios în absența unor examinări
periodice”.
Evaluarea pune în valoare și motive specifice: dori nța de succes, teama de eșec, care
constituie imbolduri importante în învățare. Succes ul sistematic înscrie motivația învățării pe o
spirală ascendantă, în timp ce eșecul poate duce la „demotivare”.
Aprecierea obișnuită în școală este asimilată, inte riorizată de elevi devenind reper de
autoapreciere, în formarea imaginilor de sine. Note le școlare reprezintă de regulă printre elevi
și părinți „note de inteligență”.
76
Termenul de evaluare școlară desemnează actul prin care – referitor la o prestație orală,
scrisă sau practică – se formează o judecată prin p risma unor criterii. O asemenea judecată
capătă expresie numerică (de la 1 la 10), ce se îns crie în documente (catalog, foaie matricolă,
diplomă), adeseori se regăsește sub forma unor apre cieri calificative. Deci evaluarea și notarea
școlară alcătuiesc o modalitate de codare a rezulta telor obținute de elevi.
Pentru profesor evaluarea indică cum să-și dozeze materialul, ce an ume trebuie reluat
în pași mici, care sunt greșelile tipice și sursle de eronare, etc.
Pentru elev evaluarea reprezintă un indiciu în reluarea efortu lui de învățare, un reper în
dozarea investiției de timp, un “semnal de alarmă” pentru promovare, etc.
3.4.2 Forme de evaluare
Evaluarea urmărește modul în care obiectivele stabi lite se înfăptuiesc în activitatea
practică. Întrucât acest process este continuu și d e durată, evaluarea se poate efectua pe
parcurs, secvențial sau în finalul său.
Cercetările făcute și experiența practică au eviden țiat existența a trei forme de evaluare,
după modul de integrare a lor în activitatea didact ică: evaluare inițială, evaluare cumulativă
(sumativă), evaluarea continuă (formativă).
/head2right Evaluarea inițială se face la începutul unui program de instruire și are menirea
de a stabili nivelul de pregătire al elevilor, capa citatea lor de a asimila conținutul etapei ce
urmează. Prin verificarea realizată la începutul de an școlar, de semestru sau de capitol, se
obțin date pentru obiectivele proiectării viitoarei acțiuni, volumul și exacitatea cunoștințelor
necesare, a deprinderilor și capacităților ce vor f i utilizate în noua învățare.
/head2right Evaluarea continuă (formativă) se aplică pe tot parcursul procesului de
învățare. Ea constituie parte componentă a procesul ui de învățare, având un caracter
permanent, pe măsură ce procesul se derulează, prof esorul este preocupat de comandă și
control. În cazul evaluării continue a modului învă țării, a comportamentelor elevilor în timpul
instruirii se vor constata și apreciat stadiul lor. Astfel sunt evidențiate neajunsurile, dând
posibilitatea adaptării unor măsuri de recuperare p entru elevi, privind eșecul școlar. În felul
acesta, elevi câștigă încredere, își reglează efort urile și ritmul de muncă.
/head2right Evaluarea cumulativă (sumativă) este o estimare globală, de bilanț a
rezultatelor școlare (la sfârșitul semestrului sau anului școlar), cuprinde finalitățile învățării,
cunoștințe, deprinderi, capacități, aptitudini. Rez ultatele obținute trebuie raportate la cerințe
generale ale formării elevilor (capacitatea învățăm ântului), la nivelul inițial al elevilor
(progresul școlar), la posibilitățile fiecărui elev (randamentul, progresul).
77
Făcând o analiză comparativă a evaluării sumativă ș i formativă rezultă că ambele
strategii prezintă atât avantaje cât și dezavantaje astfel încât ele trebuie îmbinate pentru
obținerea unor efecte optime.
Evaluarea semestrială adoptată de noua reformă a în vățământului se realizează pe tot
parcursul anului și are un caracter preponderent fo rmativ.
3.4.3 Metode de evaluare
Evaluarea performanțelor școlare la disciplinele de specialitate se poate face utilizând
atât metode tradiționale: de verificare orală, de v erificare scrisă, de verificare prin probe
practice cât și prin metode și tehnici moderne: obs ervarea directă a elevului în timpul
activității, investigația, proiectul de cercetare, potrofoliu, fișa de evaluare / autoevaluare, test
docimologic.
Metode complementare de evaluare
/head2right Observarea sistematică a activității și comportamentului elevului . Prin
intermediul acestei metode, profesorul obține infor mații relevante asupra performanțelor
elevilor din perspectiva capacității lor de acțiune și reacțiune a competențelor și abilităților de
care dispun.
/head2right Fișa de evaluare este un instrument în care cadrul didactc consemne ază date
factuale cu privire la comportamentul sau modul de acțiune al elevului pe care apoi le
prelucrează și le interpretează.
/head2right Investigația este o metodă comportamentală de evaluare prin car e se obțin
informații cu privire la capacitatea elevului de a aplica în mod original, creativ cunoștințele
assimilate în situații noi și variate. Se poate rea liza pe parcursul unei ore sau a unei succesiuni
de ore de curs, individual sau pe grupe.
/head2right Proiectul este o metodă complexă de evaluare, mult mai mare decât investigația,
recomandată mai ales în cadrul evaluării sumative ș i se poate realiza individual sau în grup.
/head2right Portofoliul este o metodă și un instrument de evaluare complex , flexibil, prin care
profesorul urmărește progresul realizat de elevi la o anumită disciplină de-a lungul unui
semestru sau an școlar.
/head2right Autoevaluarea este o metodă prin care se urmărește înregistrarea imaginii elevului.
Este folosită în scopul de a-i ajuta pe elevi să-și cunoască dimensiunile propriei personalități și
manifestările comportamentale.
78
În continuare prezentăm un test de evaluare inițial ă
Numele elevului: ……………………………. …
Data: ……………………………………… ………..
Clasa: …………………………………….. ……….
Disciplina: ………………………………… ……..
PROBĂ DE EVALUARE – test inițial
Clasa a XII-a B-Profil real
Specializarea matematică informatică intensiv infor matică
Unitatea de învățare- Recapitulare clasa a XI-a
Nr.1
1) Se definește o muchie a unui graf neorientat ca o în registrare cu trei câmpuri: cele două
vârfuri extremități și un cost asociat muchiei.
Definim un graf neorientat ca un vector de muchii. Fiind dat vectorul de muchii al unui
graf neorientat cu m muchii și n vârfuri, să se tipă rească muchia de cost maxim.
2) Să se determine gradul exterior al unui vârf oareca re x dintr-un graf
orientat. Se vor folosi subprograme.
3) Se citește un șir de numere întregi. Să se creeze o listă liniară simplu
înlănțuită cu aceste numere, apoi să se afișez e elementele negative ale
listei.
Punctaj:1) 3p
2) 3p
3) 3p
4) 1p oficiu
Total: 10p
79
Nr.2
1) Se definește o muchie a unui graf neorientat ca o înregistrare cu trei câmpuri: cele
două vârfuri extremități și un cost asociat muchiei .
Definim un graf neorientat ca un vector de muchii.F iind dat vectorul de muchii al unui
graf neorientat cu m muchii și n vârfuri, să se dete rmine costul mediu al muchiilor
grafului.
2) Să se determine gradul interior al unui vârf oare care x dintr-un graf
orientat.Se vor folosi subprograme.
3) Se citește un șir de numere întregi. Să se creeze o listă liniară simplu
înlănțuită cu aceste numere, apoi să se afișez e elementele pare ale
listei.
Punctaj:1) 3p
2) 3p
3) 3p
4) 1p oficiu
Total: 10p
80
PROBĂ DE EVALUARE- TEZĂ
LUCRARE SCRISĂ PE SEMESTRUL II
CLASA a XI-a B
Nr 1
1.Câte muchii are un graf complet cu 10 noduri?
a. 40 b. 45 c. 25 d. 50
2.Fie graful G(V,U), unde mulțimea nodurilor este V ={1,2,3,4,5} și mulțimea muchiilor este
U={(1,2),(1,3),(2,3),(1,4),(4,5),(2,5)}. Următoarea secvență de noduri 3,1,2,5,4 este:
a. lanț elementar b. ciclu c. lanț neelementar d. ciclu elementar
3.Care din matricile de adiacență următoare nu poat e fi matricea grafului următor:
a. {{ 0 0 1 1},{0 0 1 1},{1 1 0 0},{1 1 0 0}}
b . {{ 0 1 0 1},{1 0 1 0},{0 1 0 1},{1 0 1 0}}
c . {{ 0 1 1 0},{1 0 0 1},{1 0 0 1},{0 1 1 0}}
d. {{ 0 1 0 1},{1 0 1 1},{0 1 0 0},{1 1 0 0}}
4.Fie graful cu 5 noduri și 5 muchii, dat prin matr icea de adiacență:
{{0 1 0 1 0},{1 0 0 1 0},{0 0 0 1 0},{1 1 1 0 1},{0 0 0 1 0}}.
Care din următoarele muchii aparțin grafului:
a. [2,3] b. [2,4] c. [3,5] d. [5,2]
5.Fie G un graf cu n=5 și m=4 și matricea de adiace nță:
{{0 0 0 1 1},{0 0 1 0 0},{0 1 0 0 0},{1 0 0 0 1},{1 0 0 1 0}}. Numărul de componente conexe
al grafului este: a. 0 b. 1 c.2 d.3
6.Fie graful cu n=4, m=4 și matricea de adiacență:
{{0 1 0 1},{0 0 0 0},{0 1 0 1},{0 0 0 0}}
6.1.Câte vârfuri u au gradul interior 0? a. 0 b. 1 c .2 d. toate
6.2.Câte circuite are graful? a. 0 b .1 c. 2 d. 3
7.Fie graful următor dat prin matricea de adiacență :{{0 0 0 0 1},{1 0 0 1 0},{0 1 0 0 0}, {0 0 1 0
1},{0 1 0 0 0}}.
7.1.Care este numărul minim de arce ce trebuie elim inate astfel încât graful să nu conținiă nici
un circuit? a. 1 b. 2 c. 3 d. 0
7.2.Câte circuite are graful? a. 4 b. 3 c. 2 d. 5
8.Fie graful următor: 1
Numărul de drumuri elementare de la 1 la 5 este:
a. 5 b. 4 c. 3 d. 2 2 3
4 5
9.Un arbore este:
81
a.un graf neorientat fără cicluri;
b.un graf neorientat conex;
c.un graf neorientat conex și fără cicluri;
d.un graf orientat, tare conex și fără cicluri
10.Fie un graf neorientat cu n noduri, m muchii și p componente conexe. Care dintre
următoarele relații este adevărată:
a. p+m=n-1; b. p+m+1=2n c. p+m<n d. p+m>=np
82
Nr 2
1.Câte muchii are un graf complet cu 9 noduri?
a. 40 b. 36 c. 25 d. 30
2.Fie graful G(V,U), unde mulțimea nodurilor este V ={1,2,3,4,5} și mulțimea muchiilor este
U={(1,2),(1,3),(2,3),(1,4),(4,5),(2,5)}. Următoarel e noduri sunt de grad impar:
a. 3,1,2 b. 1,2,5 c. 1,2 d. nici unul
3.Graful cu matricea de adiacență:{{ 0 1 0 1},{1 0 1 0},{0 1 0 1},{1 0 1 0}} :
a. are un ciclu elementar b. are un ciclu neelementar
c. este conex d. are două componente conexe
4.Fie graful dat prin matricea de adiacență:
{{0 1 0 0 },{1 0 1 0},{0 1 0 1},{0 0 1 0}. Prin adă ugarea unei muchii graful va conține:
a. exact un ciclu b. exact 2 cicluri c. nici un ciclu d. exact 4 cicluri
5.Fie graful G cu 5 noduri și 5 muchii, dat prin ma tricea de adiacență:
{{0 1 1 0 1},{1 0 1 0 1},{1 1 0 1 0},{0 0 1 0 1},{1 1 0 1 0}.
Care din următoarele grafuri, date prin matricele o or de adiacență sunt grafuri parțiale ale lui
G:
a. {{0 1 1 1 0},{1 0 1 0 1},{1 1 0 1 0},{1 0 1 0 1},{0 1 0 1 0}}
b. {{0 1 0 0 1},{1 0 1 0 0},{0 1 0 1 0},{0 0 1 0 1},{1 0 0 1 0}}
c. {{0 0 0 0 0},{0 0 1 0 1},{0 1 0 1 0},{0 0 1 0 1},{0 1 0 1 0}}
d. {{0 1 1 0 1},{1 0 1 0 1},{1 1 0 0 1},{0 0 0 0 1},{1 1 1 1 0}}.
6.Fie graful cu n=4, m=4 și matricea de adiacență:
{{0 1 0 1},{0 0 0 0},{0 1 0 1},{0 0 0 0}}
6.1.Câte vârfuri u au gradul exterior 0? a. 0 b. 1 c .2 d. toate
6.2.Câte componente tari conexe are graful? a. 4 b .1 c. 2 d. 3
7.Care este numărul minim de arce ce trebuie adăuga te astfel încât graful să conțină cel puțin
un circuit care să treacă prin toate nodurile? 1 2
a. 4 b. 3 c. 2 d. 1
3 4
8.Fie matricea de adiacență {{0 1 0 0 },{0 0 0 0},{ 1 0 0 0},{0 1 0 0}}.Ea aparție unui graf:
a. orientat b. neorientat c. nu poate fi matricea unui graf d. hamiltonian
9. Se citeste de la tastatura matricea de adiacenta a unu graf orientat G = (X, U) cu n noduri si
m muchii. Sa se determine numarul varfurilor pentru care gradul interior este strict mai mare
decat gradul exterior.
83
3. 5 ORGANIZAREA PROCESULUI INSTRUCTIV-EDUCATIV
3.5.1 Structura lecței
Prin structura lecției se înțelege modul de organiz are, succesiunea momentelor sau
etapelor prin care trece, asigurându-se realizarea sarcinilor instructiv-educative. Principalele
elemente și variabile pe care le implică lecția sun t:
/head2right Obiectivele instructiv-educative ale lecției . Ele indică în mod clar, precis și
sintetic ceea ce profesorul își propune să realize ze în lecția respectivă.
/head2right Conținutul informațional al lecției . Pe baza programei școlare se delimitează
cantitatea și calitatea informației cu care se va o pera în lecția respectivă.
/head2right Alegerea unei strategii de instruire . Constă în stabilirea metodelor și procedeelor
folosite în activitatea de învățare a elevilor. Obi ectivele urmărite vor determina în ultima
instanță strategia necesară.
/head2right Variabile personalității profesorului și variabile personalit ății elevului.
Profesorul se impune prin stilul de predare, asigur ând condițiile necesare desfășurării lecției.
La celălalt capăt, elevul (receptorul) se diferenți ază în funcție de profilul său psihologic.
/head2right Colectivul de elevi. Reprezintă o altă variabilă internă a lecției. Ace știa își pun
amprenta în desfășurarea lecției și a realizării ob iectivelor propuse. În timpul lecției se
declanșează relații de cooperare sau competiții.
3.5.2 Tipologia lecției
Învățarea completă și temeinică presupune diferite tipuri de activități: de comunicare și
însușire de noi cunoștințe, de recapitulare și siste matizare, de formare de priceperi și
deprinderi, de evaluare a rezultatelor . În desfășurarea unei lecții, una dintre aceste sa rcini se
impune ca dominantă, chiar dacă pe parcursul său se realizează și activități care conduc la
îndeplinirea celorlalte sarcini didactice.
În funcție de sarcina didactică urmărită, lecțiile se pot clasifica în următoarele tipuri:
1. Lecții de comunicare/însușiri de noi cunoștințe;
2. Lecții de formare a priceperilor și deprinderilor;
3. Lecții de recapitulare/consolidare și sistematizare a cunoștințelor;
4. Lecții de verificare și apreciere a rezultatelor șc olare;
5. Lecții mixte sau combinate.
84
Variantele de lecții au caracter flexibil, oferind posibilități multiple de montare a
acivității didactice. Profesorul, în activitatea lu i trebuie să folosească cât mai multe variante de
lecții, în concordanță cu condițiile concrete și fa ctorii variabili ce apar în procesul de
învățământ.
Este recomandabil să privim categoriile de lecții c a modele care pot fi modificate și
adaptate / remodelate, și nu ca tipare rigide, infl exibile în proiectarea și desfășurarea lecției.
Perceput astfel, termenul “categorie” nu mai are re zonanță negativă și nu mai conduce la
șabloane, ci, dimpotrivă, deschide calea spre o div ersitate de variante de lucru care se
structurează și se realizează în funcție de factoru l constant – obiectivul fundamental – al lecției.
Deci, obiectivul fundamental (care poate fi predomi nant instructiv sau predominant educativ)
constituie reperul oricărei activități educaționale și unitatea de măsură a eficienței muncii
elevului și profesorului. El servește drept criteri u în stabilirea categoriilor de lecții, fiecare
categorie de lecții purtând numele obiectivului fun damental al activității didactice respective.
85
3.5.3 REALIZAREA PROIECTULUI DIDACTIC
PROIECT DIDACTIC
CLASA A XI-a B – PROFIL REAL – SPECIALIZAREA
MATEMATICĂ INFORMATIC~ INTENSIV INFORMATICĂ
1. Liceul Teoretic”Nicolae Iorga”
2. Disciplina: Informatică
3. Clasa a XI-a B
4. Profesor: Turiac Evelina
5. Unitatea de învățare: Grafuri neorientate
6. Tema ”Parcurgerea grafurilor neorientate în lățime”
7. Tipul lecției: Predare-învățare (comunicare/însușiri de noi cunoștințe)
8. Condiții inițiale de realizare : în desfășurarea lecției se va ține cont de cunoșt ințele
însușite în lecțiile anterioare
9. Competențe specifice:
– Analizarea unei probleme în scopul identificării da telor necesare și alegerea
modalităților adecvate de structurare a datelor car e intervin într-o problema
– Descrierea algoritmului fundamental de parcurgere i n lățime a grafurilor neorientate și
implementarea acestuia într-un limbaj de programare
– {nsușirea și aplicarea algoritmului fundamental de parcurgere in lățime a grafurilor
neorientate
– Identificarea și clasificarea unor structuri de d ate adecvate rezolvării unor probleme
specifice.
– Dezvoltarea spiritului inventiv;
– Dezvoltarea capacității de lucru în echipă.
10.Competențe derivate (Obiective operaționale)
– să observe modul de parcurgere in lățime a grafuril or neorientate
– să observe modul de lucru cu structura de tip coada
– să scrie subprogramele corespunzătoare algoritmului în limbaj pseudocod
– să transpună subprogramele corespunzătoare algoritm ului din limbaj pseudocod în
limbajul de programare C++
86
11. Analiza resurselor:
♦ conținut : conform programei școlare
♦ capacitatea de învățare : bună
♦ spațiu de desfășurare : laboratorul de informatică
♦ mijloace de învățământ : calculator, cărți de specialitate
( manual-Informatică intensiv, varianta C++, cls. a XI _a –Miloșescu M.,
manual-Informatică, varianta C++, cls. a XI_ a-Mateescu G. D. ,Moraru
P.F.) caiete, tabla, creta, video – proiect or,
♦ metode și procedee didactice :
– expunerea M.P.1
– conversația (introductivă, pentru fixarea cunoștinț elor, pentru
– evaluarea cunoștințelor) M.P.2
– explicația M.P.3
– demonstrația M.P.4
– descoperirea propriu-zisă și dirijată M.P. 5
– exercițiul-pentru obținerea unor noi cunoștințe și dobândirea de
– priceperi și deprinderi M.P. 6
– metoda muncii cu manualul M.P. 7
♦ forme de organizare : individuală F1, frontală F2
10. Metode de evaluare:
♦ inițială (întrebări orale)
♦ continuă
♦ aplicații pe calculator
12.Elaborarea strategiei didactice :
I) Momentul organizatoric (3 minute)
♦ Profesorul organizează clasa pentru lecție: verifică prezența elevilor și aspectele de
disciplină școlară, asigurarea condițiilor didactic o-materiale M.P.2, F2
II) Comunicarea temei noii lecții și anunțarea obiectivelor (3 minut e)
Profesorul notează pe tablă titlul lecției, comunică elevilor obiectivele urmărite,
precum și modul de desfășurare a activității M.P.2 , F2
III) Predarea-învățarea noilor cunoștințe (24 minute)
87
Parcurgerea grafurilor neorientate
Prin parcurgerea unui graf se înțelege “vizit area” vârfurilor grafului într-o anumită ordine,
dată de un anumit criteriu.
Există doi algoritmi de parcurgere a grafuri lor neorientate: în lățime și în adâncime.
Parcurgerea grafurilor neorientate în lățime.
Se pornește de la un vârf de start care se viziteaz ă, apoi se vizitează toti vecinii lui.
Pentru fiecare dintre aceste vârfuri, se vizitează toti vecinii lui care nu au fost încă
vizitați.Pentru noile vârfuri se procedează la fel. Procedeul continuă până când s-au vizitat
toate vârfurile.
Exemplu: Fie graful din figura de mai jos. Presupun em ca vârful de start este 1.
Vom parcurge în lățime acest graf:
Pasii parcurgerii Noduri vizitate
1) vârful de start 1 1
2) vecinii lui 1 2, 5, 6
3) vecinii lui 2 nevizitați 3,4
4) vecinii lui 5 nevizitați 7
5) vecinii lui 6 nevizitați –
6) vecinii lui 3 nevizitați –
7) vecinii lui 4 nevizitați –
8) vecinii lui 7 nevizitați –
2
3 4 5
7
6 1
88
Ordinea vizitării nodurilor este: 1, 2, 5, 6, 3 , 4, 7.
Profesorul explica aceasta parcurgere în lățime din vârful 1.
Un elev iese la tăblă pentru a explica ordinea viz itării nodurilor pornind din vârful 2.
Vom folosi o coadă implementată cu ajutorul unui vector c.
Profesorul reactualizează împreună cu elevii noțiun ile învățate despre structura de tip
coadă. Apoi explică “evoluția” cozii pentru graful anterior, unde p – poziția capătului de
extragere al cozii, iar u – poziția capătului de i ntroducere al cozii.
Introducem mai întâi nodul de start în coadă, apoi în mod repetat până la vizitarea tuturor
nodurilor:
– extragem din coadă vârful aflat în capătul de extra gere și-l vizităm
– introducem în coadă pe la celălalt capat, capătul d e introducere, vecinii nevizitați ai
vârfului tocmai extras.
{n continuare se vor extrage pe rând vf. 6, 3 , 4, 7.Nici unul dintre aceste vârfuri nu mai
are vecini nevizitați , deci nu se va mai introduce nimic în coadă.{n concluzie capătul de
introducere u nu se mai modifică rămânând 7.
Observații : Se observă de către elevi ajutați de profesor:
– extragerea unui varf nu înseamnă eliminarea lui fiz ică din coadă, ci este o simulare ,ea
realizându-se numai prin deplasarea către dreapta a capătului de extragere p prin
mărirea lui cu o unitate, adica p=p+1; 1 p =u =1
1 2 5 6 p=2
u=4
1 2 5 6 3 4 p=3
u=6
1 2 5 6 3 4 7 p=4
u=7
89
– după extragerea ultimului varf de pe poziția 7, cap ătul de extragere p devine 8, deci se
va muta dincolo de capătul de introducere 7. {n con cluzie ciclul ai cărui pași au fost
descriși mai sus se execută cât timp p<=u.
Implementarea algoritmului în limbaj pseudocod
Se face de către profesor împreună cu elevii.
Enunțul problemei: Să se scrie algoritmul de parcurgere în lățime a u nui graf neorientat.
Graful va fi dat prin citirea matricei de adiacența din fișierul text “adiac.txt”. Va fi folosit
limbajul pseudocod.
Se definește vectorul viz cu n elemente, unde
=contrarcazindacaiviz, 0at fost vizit a i varful , 1] [
unde i=1, 2, …, n. Fie prim nodul de start.
Reprezentarea algoritmului în pseudocod
intregi c[20],viz[20], p, u, v, i, j, prim, a[20] [20]
citirea matricei de adiacență din fișierul text “ adiacent.txt”
pentru i /barb2left 1,n executa
vizîiș /barb2left0
cîiș /barb2left0
citeste prim // fie prim nodul de start
Cî1ș /barb2leftprim
p /barb2left1 // reprezintă poziția elementului cheie
u /barb2left1 // reprezintă poziția ultimului element din coadă
viz îprimș /barb2left1
Cat timp (p< = u) executa
v /barb2leftcîpș
Pentru j /barb2left1, n executa
Daca (aîvșîjș=1) si (viz[j]=0) at unci
u /barb2leftu+1
cîuș /barb2leftj
vizîjș /barb2left1
p /barb2leftp+1
pentru i /barb2left1, u executa
scrie cîiș
Observație : Se pune problema cate noduri vor trebui afișate; evident doar cele vizitate, care nu
trebuie neaparat să reprezinte toate nodurile grafu lui, ci valoarea finală a lui u.
90
Daca parcurgem în lățime graful următor plecând din vârful 1 avem ordinea 1, 2, 3, 4 iar dacă
plecam din vârful 5 avem ordinea 5, 7, 6.
7
5
M.P.1, M.P.2, M.P.3, M.P.4, M.P. 5, M.P. 6, F2
IV ) Operaționalizarea (fixarea) noilor cunoștințe ( 15 min)
Pentru asigurarea feedback-ului și evaluare a performanței elevii implementează pe
calculator programul în C++ corespunzător algoritm ului în limbaj pseudocod prezentat
anterior. Profesorul observă modul de lucru al fiec ăruia și îndrumă elevii pentru alegerea
soluției optime Se corectează eventualele erori.Se cere rularea programului pentru diferite
valori ale varfului de start: prim=1, 2, 3,…Discuta rea rezultatelor (un elev mai rapid scrie
rezolvarea programului în C++ pe tablă).
M.P.2, M.P. 6, F1, F2
V) Evaluarea cunoștințelor (2 min)
Profesorul notează elevii care au participat activ teoretic și practic la realizarea cerințelor
cerute.se explică notele puse din mai multe ascultă ri și finalizate acum.
M.P.2, M.P.3, F2
VI) Tema pentru acasă (3 min)
Scrieți programul complet în limbajul C++ acasă și verificați dacă un graf are vârfuri izolate pe
baza acestui algoritm.
M.P.2, M.P. 7, F2
Rezolvarea temei pentru acasa:
Reprezentarea algoritmului în limbajul C++
#include<fstream.h>
#include<conio.h> 2
3
4 1
6
91
int a[10][10], n, m ;
void parcurgere_bf( ) // parcurgerea în lățime
{int j, i, c[20], viz[20], prim, u, v;
cout<<” Dati nodul de start: ”<<endl;
cin>>prim;
for (i=1; i<= n; i++)
{ c[i] =0; viz[i]=0;}
p= 1; u=1; c[p] =prim; viz[prim]=1;
while (p <= u)
{v = c[p];
for (j=1; j<=n; j++)
if(a[v][j]= =1 && viz[j]= =0) // [l adaug pe j în coadă dacă este vecin pentru v și nu a fost vizitat
{u ++; c[u]=j; viz[j]=1;}
p ++; } }
void main()
{clrscr ( );
fstream f ( “adiacent.txt” , ios::in); // elementele matricii de adiacență și valorile n , m se gasesc în
fișierul adiacen\ă.txt
f>>n>>m;
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
f>>a[i][j] ;
cout<<"matricea de adiacenta este : "<<endl; // afișare matrice de adiacență
for( i=1; i<=n; i++)
{for(j=1; j<=n; j++)
cout<<a[i][j]<<" "; cout<<endl; }
parcurgere_bf ( );
for(i=1; i<=u; i++) // afișarea cozii
cout<<c[i]<<" ";
getch( ); }
92
PROIECT DIDACTIC
CLASA A XI-a B – PROFIL REAL – SPECIALIZAREA
MATEMATICĂ – INFORMATICĂ, INTENSIV INFORMATICĂ
1. Liceul Teoretic”Nicolae Iorga”
2. Disciplina: Informatică
3. Clasa a XI-a B
4. Profesor: Turiac Evelina
5. Unitatea de învățare: Grafuri orientate
6. Tema :”Reprezentarea grafurilor orientate cu matricea dr umurilor”
7. Tipul lecției: Mixtă
8. Condiții inițiale de realizare : În desfășurarea lecției se va ține cont de cunoșt ințele
însușite în lecțiile anterioare
9. Competențe specifice:
– Analizarea unei probleme în scopul identificării da telor necesare și alegerea
modalităților adecvate de structurare a datelor car e intervin într-o problemă
– Determinarea matricei drumurilor într-un graf orien tat, folosind proprietățile matricei
de adiacență – Algoritmul Roy-Warshall
– {nsușirea și aplicarea algoritmului Roy-Warshall
– Identificarea și clasificarea unor structuri de d ate adecvate rezolvării unor probleme
specifice.
– Dezvoltarea spiritului inventive,
– Dezvoltarea capacității de lucru în echipă.
10.Competențe derivate (Obiective operaționale)
– să deosebească matricea drumurilor de celelate tipu ri de matrici folosite în
reprezentarea grafurilor orientate
– să implementeze corect Algoritmul Roy-Warshall
– să observe avantajele și dezavantajele reprezentăr ii grafurilor orientate cu matrici, față
de reprezentarea cu listele de adiacență
11. Analiza resurselor:
♦ conținut : conform programei școlare
♦ capacitatea de învățare : bună
93
♦ spațiu de desfășurare : laboratorul de informatică
♦ mijloace de învățământ : calculator, cărți de specialitate
( manual-Informatică intensiv, varianta C++, cls. a XI _a –Miloșescu M.,
manual-Informatică, varianta C++, cls. a XI_ a-Mateescu G. D. ,Moraru
P.F.) caiete, tabla, creta, video – proiect or,
♦ metode și procedee didactice :
– expunerea
– conversația (introductivă, pentru fixarea cunoștinț elor, pentru evaluarea
cunoștințelor
– explicația
– demonstrația
– descoperirea propriu-zisă și dirijată
– exercițiul-pentru obținerea unor noi cunoștințe și dobândirea de priceperi și
deprinderi
– metoda muncii cu manualul
♦ forme de organizare : individuală, frontală
12. Metode de evaluare:
♦ inițială (întrebări orale)
♦ continuă
♦ aplicații pe calculator
13. Elaborarea strategiei didactice:
I) Momentul organizatoric (2 minute)
♦ Profesorul organizează clasa pentru lecție: verifică prezența elevilor și aspectele de
disciplină școlară, asigurarea condițiilor didactic o-materiale
II) Verificarea cunoștințelor (14 min)
♦ Profesorul verifică temele date elevilor acasă: implementarea în C ++ a
algoritmilor de determinare a gradului interior ș i a gradului exterior al unui nod dat
într-un graf orientat.
♦ Verificarea cunoștințelor din lecția precedentă cu tema: “Repre zentarea grafurilor
orientate cu matrici” prin întrebări:
– Care sunt tipurile de matrici folosite în reprezent area grafurilor orientate ?
Răspuns : matricea de adiacență, matricea vârfuri-arce, mat ricea
costurilor.
– Avantajele și dezavantajele reprezentării grafurilo r orientate cu matrici față
de reprezentara cu ajutorul listelor de adiacență
94
– Răspuns : Dezavantaj: există multe elemente nule în matric i, deci se
consumă multă memorie inutil, față de listele de ad iacență, unde memorarea
lor presupune puțin spațiu de memorie.
Avantaj: accesul ușor la info rmație, față de listele de
adiacență unde accesul la informație este mai dificil.
– Reluarea reprezentării cu marici pe un graf orienta t luat ca exemplu.
III) Comunicarea temei noii lecții și anunțarea obiectivelor (2 minut e)
Profesorul notează pe tablă titlul lecției, comunică elevilor obiectivele urmărite,
precum și modul de desfășurare a activității
IV) Predarea-învățarea noilor cunoștințe (14 minute)
Se pornește de la un exemplu de matrice de adiace nță pe un graf orientat dat și se
aplică o serie de transformări succesive. Fie grafu l orientat G cu n=4 noduri și matricea sa de
adiacență a:
Matricea drumurilor:
Este o matrice d cu n linii și n coloane , în care fiecare element a [i], [j] este :
– 1, dacă există drum de la nodul i la nodul j în graf;
– 0, în caz contrar.
Algoritmul Roy-Warshall de determinare a matricei drumurilor
Matricea drumurilor se obține aplicând matricei de adiacență transformări succesive.
Vom spune că există drum de la nodul i la nodul j, dacă găsim un nod k (diferit de i, j) cu
proprietatea că există drum de la i la k și drum de la k la j. Astfel:
95
/square4 un element a (i, j) care este 0, devine 1, dacă exi stă un nod k astfel încât a (i, k)=1 și
a(k, j)=1. Pentru a găsi arcele nodului k, trebuie parcurse pe rând în varianta k toate
nodurile 1, 2, …, n..
for (k=1; k<=n; k++)
for (i=1; i<=n; i++) { i≠k }
for (j=1; j<=n; j++) { j≠k }
if (aîiș îjș ==0 && i!=k && j!=k)
aîiș îjș = aîiș îkș* aîkș îjș;
Atribuirea a[i] [j] = a[i] [k]* a[k] [j] este o s criere elegantă a regulii de mai sus:
– în cazul în care unul din elementele a[i] [k], a[k] [j] este 0, a[i] [j] va rămâne 0;
– dacă a[i]ș [k] ==1 si a[k] [j] ==1, atunci a[i] [j] devine 1.
Conform algoritmului se obține matricea drumurilor d[i,j]:
Observații:
1. Dacă d[i,j] = 1 înseamnă că există un circuit care trece prin n odul i.
2. Dacă linia i și coloana i, din matricea obținută, cuprind numai elemente de 0,
deducem că nodul i este un vârf izolat, adică nu există drumuri care să ducă la
nodul i și nici care să plece din nodul i.
V) Operaționalizarea (fixarea) noilor cunoștințe (6 min)
Graful dat are n=4 noduri, deci matricea de adiace nță va suferi patru transformări într-
un ciclu, pentru k=1,2,3,4.
Profesorul formulează întrebări și solicită răspuns uri din partea elevilor:
– Ce se caută în matricea de adiacență inițială prin acest algoritm?
Răspuns : se caută elementele aîi, jș nule, impunând condiț iile ca i, j ≠ k ,
pentru care i, j, k =1,n .
– Ce face algoritmul pentru fiecare element găsit aîi,jș egal cu 0?
Răspuns : {ncearcă să-l transforme în 1 prin atribuirea
96
a[i, j] /barb2left a[i, k] * a[k, j]
Exemplu : a[i, j] /barb2left a[i, 1] * a[1, j], pentru k=1.
– Se specifică faptul că algoritmul Roy-Warshall va f i folosit în determinarea
componentelor tare conexe.
– Cum se stabilesc drumurile într-un graf orientat?
Răspuns : se va ține cont de orientarea arcelor prin care s e trece, pentru a
respecta noțiunea de drum.
– Se vor da exemple pe graful dat, de drumuri de la u n nod i la un nod j, cu
trecere prin noduri intermediare k. Câte drumuri există în graful dat și ce
tipuri?
Răspuns: D= [1,2,4,1] – drumul este un circuit.
– Ce problemă întâlnită anterior, la grafuri neorient ate, poate fi rezolvată cu
algoritmul de determinare a drumurilor între oricar e două noduri?
Răspuns: Determinarea componentelor conexe în grafuri
neorientate.
– Ce alte exemple de probleme s-ar putea rezolva cu a jutorul acestui algoritm?
Răspuns: Determinarea celei mai influente persoane dintr-un grup
de n persoane între care există relații. Se va căuta no dul cu grad
maxim, adică linia cu cei mai mulți de 1 dint r-o matrice a
drumurilor construită cu algoritmul Roy-Warsh all.
VI) Obținerea performanțelor (10 min)
Profesorul propune elevilor scrierea unor programe care să implementeze în C++
operațiile de citire și afișare a unei matrici, câ t și a algoritmului Roy-Warshall. Elevii sunt
îndrumați și supravegheați atât la tablă cât și în activitatea independentă.
VII) Tema pentru acasă (2 min)
Profesorul propune elevilor ca temă pentru acasă implement area în C++ a algoritmului Roy-
Warshall pentru:
– Deterrminarea celei mai influente persoane dintr-un grup de n persoane
– Determinarea celei mai celebre persoane dintr-un gr up de n persoane
Lecția pentru ora viitoare va fi: “Conexitate în grafuri orientate și determinarea
componentelor tare conexe”.
97
BIBLIOGRAFIE
1. Barna Andrei , Curs de pedagogie, Teoria instruirii curriculum-ulu i și evaluării,
Editura Logos, Galați, 2001.
2. Cerchez Emanuela , Informatica , Culegere de probleme pentru liceu , Editura Polirom,
Iași 2002.
3. Cerghit Ioan , Perfecționarea lecției în școala modernă , Editura didactică și
pedagogică, București 1998.
4. Cerghit Ioan , Didactica , Editura didactică și pedagogică, București 1995.
5. Cucoș Constantin , Psihopedagogie pentru examenele de definitivare și grade
didactice, Editura Polirom, Iași 1999 .
6. Ionescu Miron, Radu Ioan , Didactica modernă , Editura Dacia, Cluj-Napoca 2001.
7. Jinga Ioan , Manual de pedagogie , Editura All, București, 1998.
8. Nicola Ioan , Tratat de pedagogie școlară, Editura Aramis, București 2001.
9. Mateescu Emanuela, Maxim Ioan , Arbori , Editura |ara Fagilor, 1996.
10. Mateescu George Daniel, Moraru Pavel Florin , Informatica pentru liceu și
bacalaureat, materia de clasa a XI-a, profil matemati că-informatică intensiv, varianta
C++, Editura Donaris, Sibiu, 2006
11. Mateescu George Daniel, Moraru Pavel Florin , Fișe de lucru pentru elevi, clasa a
XI-a, profil matematică-informatică intensiv, variant ele Pascal și C++, Editura
Donaris, Sibiu, 2006
12. Miloșescu Mariana , Informatică intensiv, manual pentru clasa a XI-a, Ed itura
didactică și pedagogică, București 2006.
13. Proiectul Tempus S_Jep 11168-96 , Restructurarea perfecționării profesorilor în
informatică 1998/1999 , Editura Computer Libris Agora, Cluj 1999.
14. Sorin Tudor , Informatica, manual pentru clasa a XI-a, varianta C++ , Editura L&S
Infomat, București 2001.
15. Stan Mihaela Veronica (coordonator) , Algoritmi- culegere de probleme clasa a XI-a ,
Editura L& Soft, București 2004.
16. Tomescu Ioan , Bazele informaticii , Editura didactică și pedagogică, București 1996.
17. Tomescu Ioan , Ce este teoria grafurilor?, Editura științifică și enciclopedică,
București 1982.
18. Tomescu Ioan , Combinatorică și Teoria Grafurilor, București 197 8.
98
Declarație de autenticitate,
Subsemnata MOISE EVELINA, căsătorită TURIAC, înscri să la examenul final de
absolvire sesiunea I, martie 2012, Program de Conv ersie Profesională la nivel Postuniversitar
în ECONOMIE ȘI EDUCAȚIE ANTREPRENORIALĂ, seria VI, cu durata de 1,5 ani declar
pe propria răspundere următoarele:
a) lucrarea a fost elaborată personal și îmi aparți ne în întregime;
b) nu am folosit alte surse decât cele menționate î n bibliografie;
c) nu am preluat texte, date sau elemente de grafic ă din alte lucrări sau din alte surse
fără a fi citate și fără a fi precizată sursa prelu ării,
d) lucrarea nu a mai fost folosită în alte contexte de examen sau de concurs.
Dau prezenta declarație fiindu-mi necesară la preda rea lucrării metodico-științifice în vederea
avizării de către conducătorul științific, domnul p rofesor Conf. dr. Costel Nistor.
Declarant ,
(nume, prenume ) MOISE (TURIAC) EVELINA
( semnătura)…………………………………
Data 09.03.2012
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: Reprezentarea grafurilor orientate cu matricea dr umurilor [614911] (ID: 614911)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.