Extras din proiect
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.
Preview document
Conținut arhivă zip
- Algoritmul lui Kruskal
- Anexe.doc
- Proiect pt predat.doc