Algoritmul lui Kruskal

PROIECT DE LECTIE

Propunator : Coroiu Cristina

Data : 29.11.2007

Clasa : a XII-a B

Disciplina : Informatica

Subiectul lectiei : Algoritmul lui Kruskal

Durata : 1 ora

Tipul lectiei : Predare – Invatare

Obiective operationale :

- sa poata defini notiunile de ciclu si lant intr-un graf neorientat

- sa poata defini notiunea de graf conex

- sa poata defini notiunea de arbore

- sa utilizeze corect notiunile teoretice existente la grafuri

- sa poata aplica algoritmul lui Kruskal pentru determinarea arborelui de pondere minima pe un exemplu concret

Obectiv fundamental : Introducerea unui algoritm de determinare a arborelui de pondere minima

Metode didactice :

Expunerea , Conversatia , Conversatia Euristica , Exercitiul , Explicatia

Mijloace de predare : Manual clasa a XI –a , editura Niculescu , Teste de evaluare clasa a XI –a

DESFASUAREA LECTIEI

Etapele lectiei care duc la desfasurarea obiectivelor Activitatea desfasurata de profesor Activitatea desfasurata de elevi Metode de activitate

1 2 3 4

Moment organizatoric

Verificarea temei pentru acasa

Verificarea si actualizarea cunostiintelor anterioare

Evaluarea performantelor

Anuntarea titlului lectiei

Prezentarea materialului nou.

Comunicarea noilor cunostiinte.

Dirijarea invatarii si asigurarea feedback-ului

Evaluarea cunostiintelor

Dirijarea invatarii pe grupe

Dirijarea invatarii pe grupe

Evaluarea performantelor

Verific prezenta elevilor si notez absentele.

Verific daca exista materialele necesare pentru desfasurarea lectiei.

Daca au existat dificultati la rezolvarea temei , le mai explic odata.

Daca la ora anterioara s-a dat test, tema o va reprezenta acel test .

Pun intrebari referitoare la lectia anterioara :

1. Definitia unui lant si a unui ciclu

2. Definitia unui graf conex

3. Definitia unui arbore

Fac legatura cu lectia anterioara propunand spre rezolvare urmatoarele probleme :

Problema 1 :

Se da graful neorientat G1.

a). Sa se precizeze daca secventele urmatoare sunt lanturi :

L1 = {u3, u5, u7, u4, u1}

L2 = {u1, u2, u5, u6, u7}

b). Sa se precizeze daca secventele urmatoare sunt cicluri :

C1 = (2, 3, 4, 5, 1, 2)

C2 = (4, 1, 2, 3, 5, 4)

(Rezolvare in Anexa 1)

Numesc cate un elev pentru a rezolva cate o cerinta a problemei.

Problema 2 :

Se da graful neorientat G2.

a). Este un graf conex ?

b). Este arbore ?

(Rezolvare in Anexa 2)

Numesc cate un elev pentru a rezolva cate o cerinta a problemei.

Analizez impreuna cu elevii solutia data si trag concluzii asupra greseliilor comise.

Anunt titlul lectiei si il scriu pe tabla.

Enunt obiectivele si scopul lectiei de zi : determinarea arborelui de pondere minima.

Ponderea unui arbore P = (X, T) , subgraf al

lui G, l(P) = .

Determinarea arborelui de pondere minima presupune unul din urmatoarele rationamente :

Dandu-se un graf conex G = (X, U) cu valori pentru muchii atunci :

1) ordonam crescator muchiile dupa ponderi si cautam sa nu formeze ciclu

2) ordonam descrescator muchiile dupa ponderi si eliminam muchiile cu valoarea cea mai mare asa incat sa nu isi piarda conexitatea

3) daca nu ordonam muchiile dupa ponderi, atunci cautam muchia de valoare cea mai mare si daca avem ciclu, o eliminam

Prezint algoritmul lui Kruskal.

Acest algoritm determina arborele de valoare minima.

Exista 3 cazuri :

1. G = (X, U), U = {u1, u2, ...,um}, ordonate crescator dupa ponderi

l(u1)≤ l(u2)≤... ≤l(um).

T := {u1} ;

Pentru celelalte muchii daca T {uk}, k = 2,m nu contine ciclu atunci

T := T {uk}

2. G = (X, U), U = {u1, u2, ...,um}, ordonate descrescator dupa ponderi

l(u1)≥ l(u2)≥... ≥l(um).

T := U ;

Daca T – {uk}, k = 1,m este conex, atunci T := T – {uk}

3. G = (X, U), U = {u1, u2, ...,um} neordonate.

T := {u1} ;

Pentru k := 2,m T := T {uk}.

Daca T contine ciclu atunci determinam muchia v cu valoare cea mai mare si o eliminam T := T – {v}.

Problema 3 :

Se da un graf neorientat G = (X, U). Sa se determine arborele de pondere minima, prin cele 3 metode.

(Rexolvarea in Anexa 3)

Liderul fiecarei echipe va scrie la tabla rezolvarea problemei.

Problema 4 :

Se da un graf neorientat G = (X, U). Sa se determine arborele de pondere minima, prin cele 3 metode.

(Rexolvarea in Anexa 4)

Liderul fiecarei echipe va scrie la tabla rezolvarea problemei.

Analizez impreuna cu elevii solutia data si trag concluzii asupra greseliilor comise.

Pun intrebari referitoare la rezolvarea temei .

Elevii scriu pe tabla varianta corecta a rezolvarii temei.

Elevii raspund pe rand , enuntand definitia ceruta.

Noteaza in caiete enuntul problemei.

Elevii desemnati raspund pe rand la intrebari , argumentand raspunsul lor .

Noteaza in caiete enuntul problemei.

Elevii desemnati raspund pe rand la intrebari , argumentand raspunsul lor .

Elevii noteaza in caiete solutia corecta si observatiile facute de profesor.

Noteaza in caiete titlul lectiei.

Noteaza explicatiile date de profesor.

Noteaza in caiete descrierea algoritmului lui Kruskal.

Elevii noteaza in caiete enuntul problemei.

Elevii noteaza in caiete enuntul problemei.

Elevii noteaza in caiete solutia corecta si observatiile facute de profesor.

Conversatia

Conversatia frontala,

conversatia euristica

Demonstratia prin exemple si rezolvari de probleme

Munca individuala

Observatia , explicatia,conversatia frontala.

Expunerea.

Observatia,explicatia,conversatia euristica.

Demonstratia prin exemple si rezolvarea problemelor.