Exercițiul, la graful hamiltonian

Exercițiul

Exercițiul este metoda care constă în executarea conștientă și repetată a unor operații, în scopul formării și consolidării unor priceperi și deprinderi intelectuale sau practice.

Trei caracteristici ale metodei

1. Repetarea conștientă a operațiilor. Elevul execută de mai multe ori aceleași operații, pe date diferite, dar înțelege de fiecare dată ce face și de ce. Repetarea mecanică, fără înțelegerea regulii, nu duce la formarea deprinderii.

2. Gradarea exercițiilor, de la simplu la complex. Exercițiile se succed în ordinea dificultății: se începe cu recunoașterea noțiunii pe un exemplu dat, se continuă cu aplicarea unui algoritm cunoscut și se ajunge la rezolvarea unei probleme noi. Fiecare exercițiu se bazează pe deprinderile formate prin cele dinaintea lui.

3. Asigurarea feedbackului. Elevul trebuie să afle, după fiecare exercițiu, dacă a lucrat corect. Rezultatele se compară cu cele așteptate, iar greșelile se identifică și se corectează imediat, înainte ca ele să se fixeze.

Două tipuri de exerciții

Exercițiile de recunoaștere a unor noțiuni. Elevul identifică noțiunea studiată într-un exemplu dat: stabilește, pe desenul unui graf, dacă un șir de noduri este un ciclu hamiltonian.

Exercițiile aplicative. Elevul aplică un algoritm cunoscut pe date noi sau îl implementează într-un limbaj de programare: scrie programul care verifică dacă un șir de noduri citit este un ciclu hamiltonian al unui graf dat.

Elemente ale proiectării didactice

Disciplina: Informatică, clasa a XI-a, profilul real, specializarea matematică-informatică.

Unitatea de învățare: Grafuri neorientate și grafuri orientate.

Tema: Graful hamiltonian.

Competențele specifice vizate: 1.3 și 1.4.

Mijlocul de învățământ utilizat: fișa de lucru cu desenele a două grafuri neorientate, G1 și G2, și cu seturile de date de test pentru program.

Forma de organizare a clasei: activitate frontală, pentru reactualizare și pentru analiza rezultatelor, și activitate individuală, la calculator, pentru rezolvarea exercițiilor.

Activitatea de învățare: verificarea, pe grafuri date, dacă un șir de noduri este un ciclu hamiltonian și implementarea în limbajul C++ a algoritmului de verificare.

Scenariul didactic

Grafurile de pe fișa de lucru sunt:

• G1, cu nodurile 1, 2, 3, 4, 5, 6 și muchiile [1,2], [1,3], [1,4], [2,3], [2,5], [3,6], [4,5], [4,6], [5,6];
• G2, cu nodurile 1, 2, 3, 4, 5 și muchiile [1,2], [1,3], [2,3], [3,4], [3,5], [4,5].

Etapa 1. Reactualizarea noțiunilor necesare (5 minute)

Activitatea profesorului. Profesorul cere elevilor să definească lanțul elementar, ciclul elementar și gradul unui nod. Desenează pe tablă graful G1 și cere exemple de lanț elementar și de ciclu elementar în acest graf.

Activitatea elevilor. Elevii formulează definițiile: lanțul elementar are nodurile distincte, iar ciclul elementar are nodurile distincte, cu excepția primului și a ultimului, care coincid. Dau exemple în graful G1: lanțul (1, 2, 5, 6) și ciclul (1, 2, 3, 1).

Etapa 2. Definirea noțiunii și exercițiile de recunoaștere (10 minute)

Activitatea profesorului. Profesorul definește noțiunile:

• lanțul hamiltonian este un lanț elementar care conține toate nodurile grafului;
• ciclul hamiltonian este un ciclu elementar care conține toate nodurile grafului;
• graful hamiltonian este un graf care conține cel puțin un ciclu hamiltonian.

Distribuie fișa de lucru și cere elevilor să rezolve individual exercițiile de recunoaștere:

1. Este (1, 2, 3, 6, 5, 4, 1) un ciclu hamiltonian în graful G1?
2. Este (1, 2, 3, 6, 4, 5) un lanț hamiltonian în G1? Se poate închide într-un ciclu?
3. Graful G2 are un ciclu hamiltonian?

Urmărește rezolvarea și cere, pentru fiecare răspuns, justificarea pe desen.

Activitatea elevilor. Elevii rezolvă exercițiile pe fișă și prezintă răspunsurile:

1. Da: nodurile 1, 2, 3, 6, 5, 4 sunt distincte, sunt toate nodurile grafului, iar muchiile [1,2], [2,3], [3,6], [6,5], [5,4], [4,1] există.
2. Lanțul este hamiltonian, dar nu se închide într-un ciclu, fiindcă muchia [5,1] nu există.
3. Nu. Orice ciclu care trece prin nodurile 1 și 4 trece de două ori prin nodul 3, singurul nod comun al triunghiurilor {1, 2, 3} și {3, 4, 5}.