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.

Tipul lecției: lecție de comunicare și însușire de noi cunoștințe.

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. Momentul organizatoric (2 minute)

Activitatea profesorului. Profesorul notează absențele și verifică dacă toate stațiile de lucru funcționează. Cere elevilor să pornească calculatoarele și să deschidă mediul de programare C++.

Activitatea elevilor. Elevii pornesc calculatoarele, deschid mediul de programare și pregătesc caietele. Semnalează stațiile care nu funcționează.

Etapa 2. Reactualizarea noțiunilor necesare și anunțarea temei (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.

Întreabă apoi dacă în graful G1 se poate pleca dintr-un nod, trece o singură dată prin toate celelalte noduri și reveni în nodul de plecare. Anunță tema lecției, „Graful hamiltonian”, și precizează că la sfârșitul orei elevii vor verifica printr-un program dacă un șir de noduri este un ciclu hamiltonian.

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). Caută pe desen un traseu care trece prin toate nodurile și notează tema.

Etapa 3. Comunicarea conținutului nou: 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.