Angelica – Ioana TĂBÎRCĂ – Liceul Teoretic “Ion Heliade Rădulescu” Târgoviște
Nicolae – Radu TĂBÎRCĂ – Liceul Teoretic “Ion Heliade Rădulescu” Târgoviște
PROIECT DIDACTIC
Unitatea școlară: Liceul Teoretic “Ion Heliade Rădulescu” Târgoviște
Profesori propunători: Angelica – Ioana TĂBÎRCĂ, Nicolae – Radu TĂBÎRCĂ
Disciplina: INFORMATICĂ
Clasa: a XI-a
Data: ____________________
Unitatea de învăţare: Grafuri neorientate
Tema lecției: Grafuri euleriene
Tipul lecţiei – mixtă ( lecție care urmărește atât predarea, cât și fixarea, verificarea și aplicarea cunoștințelor )
Locul de desfăşurare: Laboratorul de informatică
Durata: 50 min.
Nivelul iniţial al clasei:
– elevii şi-au însuşit noţiunile teoretice legate de grafurile neorientate: terminologie, reprezentare, memorare;
– elevii rezolvă corect probleme simple cu grafuri, scriu programele sursă, le rulează şi depanează.
Competenţă generală :
- Identificarea datelor care intervin într-o problemă şi aplicarea algoritmilor fundamentali de
prelucrare a acestora
Competenţe specifice:
- Analizarea unei probleme în scopul identificării datelor necesare şi alegerea modalităţilor adecvate de structurare a datelor care intervin într-o problemă
- Transpunerea unei probleme din limbaj natural în limbaj de grafuri, folosind corect terminologia specifică
- Descrierea unor algoritmi simpli de verificare a unor proprietăţi specifice grafurilor
Obiective educaţionale:
- Obiective cognitive
- explicarea și exemplificarea noţiunilor legate de grafuri euleriene;
- aplicarea noţiunilor studiate, în aplicaţii concrete;
- emiterea de ipoteze pentru rezolvarea unor probleme;
- Obiective afective
- formarea convingerii că teoria grafurilor are aplicații în multe domenii ale științei și tehnicii, cât și în viața reală;
- manifestarea iniţiativei şi disponibilităţii de a aborda sarcini variate;
- Obiective psihomotorii
- utilizarea corectă a mediului de programare Code::Blocks pentru a realiza programe în C++;
- formarea deprinderii de a depana în timp util erorile ce apar în programele sursă;
- Obiective operaţionale
La sfârșitul lecției, elevii vor fi capabili:
- să analizeze dacă un graf neorientat este eulerian sau conține un lanț eulerian;
- să verifice, utilizând programarea în C++, dacă un graf este eulerian.
STRATEGIA DIDACTICĂ
- Metode de învăţământ
- expunere, conversaţie, problematizare;
- observarea independentă, exerciţiul euristic, rezolvarea de probleme;
- Procedee de instruire:
- – expunere în etapa de comunicare;
- – învăţarea prin descoperire, observarea independentă, exerciţiul euristic, rezolvarea de probleme;
- – problematizarea prin crearea situaţiilor problemă;
- – conversaţia de consolidare în etapa de fixare a cunoştinţelor;
- Forme de organizare a activităţii: frontal şi individual;
- Forme de dirijare a activităţii: dirijată de profesor și independentă;
- Material bibliografic:
- Manual de informatică Vlad Huțan, Tudor Sorin, – Aprobat prin Ordinul MEdC nr. 4446 din 19.06.2006 – editura L&S Soft București
- Ghid de evaluare – Informatică și Tehnologia informației, S.N.E.E., București 2001
- Mijloace de învățământ: http://informat21.wikispaces.com/
- Metode de evaluare :
- evaluare iniţială: întrebări orale, observarea sistematică a activității și comportamentului elevilor
- evaluare formativă: observarea sistematică a activității și comportamentului elevilor, set de aplicații poste pe site-ul wiki
- evaluarea finală ( sumativă ): întrebări orale, set de aplicații poste pe site-ul wiki
- Desfăşurarea activităţii
| Momentele lecției | Activitatea de predare – învățare | Metode de învățământ
(Metode şi mijloace de învăţământ utilizate) |
Modalități de evaluare
( instrument de evaluare ) |
|
| Activitatea profesorului | Activitatea elevilor | |||
| 1. Moment organizatoric | Asigură cadrul necesar începerii orei:
– amplasarea elevilor la calculatoare; – notarea absenților etc. |
Elevii se pregătesc pentru oră:
– verifică funcționarea calculatoarelor; – își organizează masa de lucru etc. |
– conversația | – observarea sistematică a activității și comportamentului elevilor ( listă de verificare );
|
| 2. Reactualizarea cunoștințelor | – Verifică tema pentru acasă
– Prezintă elevilor modalitatea prin care li se vor verifica cunoștințele referitoare la grafurile neorientate ( fișa nr. 1 ) |
Elevii adresează întrebări și răspund la întrebări referitoare la noțiuni specifice teoriei grafurilor neorientate ( conform informațiilor primite de la profesor ) | – explicația
|
– observarea sistematică a activității și comportamentului elevilor (listă de verificare);
– probă orală; |
| 3. Anunțarea temei și a obiectivelor lecției | Prezintă tema lecției și obiectivele acesteia ( expuse pe flipchart ) | Notează tema și obiectivele lecției | – conversația | – observarea sistematică a activității și comportamentului elevilor (listă de verificare); |
| 4. Parcurgerea secvențială a materialelor postate pe site-ul wiki | Prezintă, secvențial, conținutul site-ului wiki:
informat21.wikispaces.com, coordonând atent acțiunile elevilor spre atingerea obiectivelor lecției ( fișa nr. 2 ) |
Parcurg, sub îndrumarea profesorului, materialele postate pe site-ul wiki. Notează informațiile importante, rezolvă exercițiile și problemele propuse. | – expunerea,
– conversaţia euristică, – explicația, – problematizarea, – rezolvarea de probleme. |
– observarea sistematică a activității și comportamentului elevilor (listă de verificare);
|
| 5. Obținerea performanței și realizarea feed-back-ului | Verifică atingerea obiectivelor propuse prin intermediul:
– gradului de realizare de către elevi a aplicațiilor propuse pentru rezolvare în clasă; – întrebărilor finale referitoare la conținuturile lecției. Discută și analizează cu elevii tema propusă pentru acasă |
– Răspund la întrebări
– Rezolvă individual aplicațiile propuse și realizează programul în C++ utilizând mediul de programare Code::Blocks – Participă la discuțiile referitoare la modalitatea de realizare a temei pentru acasă, argumentează |
– conversaţia euristică,
– explicația, – rezolvarea de probleme. |
– observarea sistematică a activității și comportamentului elevilor (listă de verificare);
– probă orală; – probă practică. |
| 6. Încheierea activității | Apreciază participarea elevilor la lecție, dovedită și prin manifestarea iniţiativei şi disponibilităţii lor de a aborda sarcini variate
( fișa nr. 3 ) |
Ascultă observațiile profesorului, argumentând, manifestând opinii pro și contra.
Completează scara de clasificare. |
– conversația | – observarea sistematică a activității și comportamentului elevilor (listă de verificare);
|
Evaluare inițială – Grafuri neorientate:
Fișa nr. 1 – VERIFICAREA CUNOȘTINȚELE REFERITOARE LA GRAFURILE NEORIENTATE
Joc didactic desfășurat de elevi referitor la tema studiată ( 3 min. ) – care presupune, pentru elevi, formularea de întrebări și evaluarea răspunsurilor primite
Reguli:
- Elevii au primit ca temă pentru acasă recapitularea/ reactualizarea noțiunilor referitoare la grafuri neorientate ( definiții, teoreme, probleme specifice etc. ) ;
- Profesorul împarte cartonașe cu numere tuturor elevilor, astfel încât fiecare elev primește un cartonaș cu un număr cuprins între 1 și numărul total al elevilor din clasă ( numărul nu trebuie cunoscut decât de elevul respectiv );
- Profesorul adresează prima întrebare și solicită răspuns elevului cu numărul x;
- Dacă elevul răspunde corect este notat cu + în fișa de evaluare și este rugat să adreseze următoarea întrebare ( din domeniul studiat ) elevului cu numărul y ( ales la întâmplare );
- Dacă elevul nu răspunde corect sau nu știe să formuleze o întrebare este notat cu – în fișa de evaluare și profesorul nominalizează alt elev / număr ș.a.m.d.
- Jocul se derulează într-un timp finit.
Întrebări – Răspunsuri așteptate
Ce este un graf neorientat ? ( definiție )
R: Un graf neorientat este o pereche ordonată G=( V, E ), unde:
- V = {v1, v2, …, vn} este o mulțime finită și nevidă. Elementele mulțimii V se numesc noduri ( vârfuri )
- E este o mulțime finită de perechi neordonate de forma (vi, vj), unde i ≠ j și vi, vj є V. Elementele mulțimii E se numesc muchii.
- Orice muchie unește 2 noduri distincte.
- Când sunt 2 noduri adiacente ?
R: Când reprezintă extremitățile unei muchii. / Când sunt unite de o muchie.
- Ce reprezintă gradul unui nod ?
R: Numărul muchiilor incidente cu nodul respectiv. ( Not: d( v ) )
Observații:
- Dacă d(v) = 0, nodul v este nod izolat
- Dacă d(v) = 1, nodul v este nod terminal
Care este suma gradelor unui graf neorientat cu n noduri și m muchii ?
R: S = d1+d2+…dn= 2m
- Care sunt metodele ( studiate ) de memorare a grafurilor ?
R: Utilizând:
- Matricea de adiacență ( matrice pătratică, simetrică față de diagonala principală )
- Listele de adiacență ( prin utilizarea alocării statice )
- Ce este un graf complet ?
R: Un graf neorientat în care oricare 2 noduri sunt sunt adiacente ( Not: Kn )
Observații:
- Într-un graf complet, gradul oricărui nod este n-1 ( din fiecare nod pleacă / sosesc n-1 muchii )
- Într-un graf complet există relația m = n(n-1) / 2, unde m este numărul de muchii, iar n este numărul de noduri. ( C2n = n(n-1)/2 )
- Există un număr de 2n(n-1)/2 grafuri neorientate cu n noduri.
- Ce este un graf parțial al unui graf neorientat ?
R: Un graf parțial al unui graf neorientat dat G=(V,E) este un graf G1=(V, E1), unde E1 E
( Un graf parțial al unui graf dat este el însuși sau se obține prin suprimarea anumitor muchii.)
- Ce este un subgraf al unui graf neorientat ?
R: Un graf parțial al unui graf neorientat dat G=(V,E) este un graf G1=(V1, E1),
unde E1E, V1V, iar muchiile din E1 sunt toate muchiile din E care sunt incidente numai la noduri din mulțimea V1.
( Un subgraf parțial al unui graf dat G este el însuși sau se obține din G prin suprimarea anumitor noduri și a tuturor muchiilor incidente cu acestea.)
- Ce reprezintă parcurgerea grafurilor ?
R: Prin parcurgerea grafurilor înțelegem o modalitate de vizitare a nodurilor acestuia, cu scopul prelucrării informațiilor asociate nodurilor.
- Ce este un lanț ?
R: Un lanț L=[v1, v2, …, vp ] este o succesiune de noduri cu proprietatea că oricare două noduri vecine sunt adiacente.
- Ce reprezintă lungimea unui lanț ?
R: Numărul de muchii ce unesc nodurile lanțului.
- Ce este un lanț elementar ?
R: Un lanț elementar este un lanț care conține numai noduri distincte.
- Ce este un graf conex ?
R: Un graf în care există un lanț între oricare două noduri ale acestuia.
Observație: Graful conex admite o singură componentă conexă.
- Ce este un ciclu ?
R: Un lanț pentru care nodul inițial coincide cu nodul final.
- Ce este un ciclu elementar ?
R: Un ciclu care conține numai noduri distincte, cu excepția ultimului nod, care coincide cu primul.
Fișa nr. 2 – CONȚINUTUL SITE-ULUI WIKI: informat21.wikispaces.com
Fișa nr. 3 – Verificarea, utilizând mediul de programare C++, a faptului că un graf este sau nu eulerian
| G2.in | G2.out |
| 5
1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5 |
Graful este eulerian |
#include <iostream>
#include <fstream>
using namespace std;
int main ()
{
unsigned int i,j, n, s, a[10][10],ok=1;
ifstream f( „G2.in”);
ofstream g ( „G2.out”);
f>>n;
for(i=1;i<=n;i++)
for (j=1;j<=n;j++)
a[i][j]=0;
while (f>>i>>j)
a[i][j]=a[j][i]=1;
for(i=1;i<=n;i++)
{
s=0;
for(j=1;j<=n;j++)
s=s+a[i][j];
if(s%2!=0) ok=0;
}
if(ok==1)
g<<„Graful este eulerian”;
else
g<<„Graful nu este eulerian”;
f.close();
g.close();
}
Fișa nr. 4 – SCARĂ DE CLASIFICARE completată de elevi la finalul lecției
Tema lecției: GRAFURI EULERIENE DATA: _______________
Bifează, pentru fiecare întrebare, ceea ce consideri că te reprezintă.
- Noțiunile prezentate în lecție sunt importante pentru activitatea mea viitoare.
puternic dezacord dezacord neutru acord puternic acord
- Sunt interesat să aprofundez noțiunile prezentate la lecție și să rezolv tema pentru acasă.
puternic dezacord dezacord neutru acord puternic acord
- Am participat cu plăcere la lecție
puternic dezacord dezacord neutru acord puternic acord