�ݺ�ߣ

Tehnica Backtracking - Manualul profesorului Clasa a X-a

Cuprins:

1. Terminologie

2. Structură generală
2.1. Obiective didactice
2.2. Conţinut
2.3. Recomandări de structurare şi predare

3. Obiecte de conţinut - detaliere
3.1. M1 – Backtracking iterativ – Generarea aranjamentelor
3.2. M2 – Colorarea hărţilor
3.3. M3 – Colorarea hărţilor – Aplicaţie : Harta României
3.4. M4 – Backtracking recursiv – Plata unei sume de bani
3.5. M5 – Problema labirintului

4. Bibliografie

-2-


1. Terminologie

Butoane instructaj – – sunt amplasate în partea din dreapta-
sus a ecranului şi, atunci când sunt accesate, prezintă pas cu pas,
într-o fereastră de detaliu, instrucţiuni despre folosirea unei
aplicaţii.

Butoane demonstraţie – – sunt amplasate în dreptul
enunţurilor “Teoremă” sau în dreptul unui rezultat, şi îi oferă
utilizatorului, într-o fereastră de detaliu, demonstraţia teoremei,
respectiv modul în care s-a ajuns la acel rezultat.

Butoane start animaţie / trecere la pasul următor – – se
regăsesc în cadrul animaţiilor şi al aplicaţiilor ce conţin mai mulţi
paşi. Prin apăsarea lor se începe rularea animaţiei, respectiv se
trece la următorul pas al aplicaţiei.

Butoane de reiniţializare a animaţiei / aplicaţiei - - Prin
apăsarea lor se reiniţializează animaţia, respectiv aplicaţia.

Butoane de navigare între soluţii - - se regăsesc
în cadrul aplicaţiilor ce conţin prezentarea unor algoritmi care
trebuie să afişeze toate soluţiile unei probleme date. Apăsarea
primului buton duce la afişarea directă a următoarei soluţii a
problemei, sărind peste etapele intermediare. Apăsarea celui de-al
doilea duce la afişarea directă a ultimei soluţii a problemei, sărind
peste etapele intermediare. Apăsarea ultimului buton duce la
întreruperea animaţiei, reluarea facându-se prin apăsarea butonului
start animaţie.

Butoane pentru navigare secvenţială – – fac legătura
între ferestre de conţinut asemănător din interiorul unui modul.

Texte de reper – – reprezintă simboluri grafice
prezente intr-un text care, atunci când sunt accesate, prezintă
ferestre de ajutor, in care se detaliază o anumită noţiune.

-3-


Ferestre detaliu – sunt ferestre care oferă informaţii suplimentare
despre o anumită noţiune. Exemplu :

Butoane pentru închis ferestre - – sunt amplasate în
dreapta ferestrelor de detaliu iar apăsarea lor duce la închiderea
ferestrei.

-4-


2. Structura generală
În acest capitol sunt prezentate detaliat obiectivele didactice care
pot fi atinse cu ajutorul acestor lecţii. De asemenea sunt prezentate
succint conţinuturile materialului şi câteva sugestii pentru folosirea
lecţii.

2.1. Obiective didactice

Obiectiv Detaliere
Obiective de referinţă

R1 Să identifice problemele care pot fi rezolvate cu ajutorul
metodei backtracking.
R2 Să însuşească tehnica backtracking – metodă de alaborare
a algoritmilor.
R3 Să urmărească etapele de realizare a unei aplicaţii prin
metoda backtracking.
Obiective operaţionale

OP1 să utilizeze corect noţiunile învăţate în scrierea modulară
a programelor;
OP2 să evidenţieze condiţiile interne şi condiţiile de continuare
ale aplicaţiilor;
OP3 să identifice şi să construiască soluţiile posibile ale
aplicaţiilor;
OP4 să verifice soluţiile posibile care satisfac condiţiile interne,
conducând raţionamentul către soluţiile rezultat;
OP5 să analizeze corect fiecare problemă şi să dezvolte
gândirea algoritmică, capacitatea de generalizare şi
problematizare

-5-


2.2 Conţinut

Se prezintă lista obiectelor de conţinut şi caracteristicile lor
generale.

M1 – Backtracking iterativ – Generarea aranjamentelor
Obiective didactice OP1, OP2, OP3, OP4
Timp de predare 25 min
Tip de interacţiune cu • metode de comunicare orală :
elevii expunere, conversaţie, studiu de caz;
• metode de acţiune: exerciţiul, învăţarea
prin descoperire;
• proceedee de instruire: explicatia în
etapa de comunicare; învăţarea prin
descoperire dirijată, inductivă,
experimentală; conversaţia de consolidare
în etapa de fixare a cunoştintelor;
Descriere • exemplificarea generării aranjamentelor
• explicarea mecanismului de generare a
aranjamentelor prin utilizarea unei stivei
Cuvinte cheie metoda backtracking, aranjamente de n
elemente luate căte p

M2 – Colorarea hărţilor
Obiective didactice OP2, OP3, OP4
elevii expunere, conversaţie, algoritmizare ;
prin descoperire;
• proceedee de instruire: explicatia în
etapa de comunicare; învăţarea prin
descoperire dirijată, inductivă,
experimentală; conversaţia de consolidare
în etapa de fixare a cunoştinţelor;
Descriere • exemplificarea colorării unei hărţi compusă
din şase ţări folosind cel mult patru culori;
• explicarea tehnicii backtracking folosită în
colorarea hărţii
Cuvinte cheie metoda backtracking, matricea asociată
hărţii, stiva st[]

-6-


M3 – Colorarea hărţilor – Aplicaţie : Harta României
elevii expunere, conversaţie, problematizare,
brainstorming;
prin descoperire;
• proceedee de instruire: conversaţia de
consolidare, problematizarea prin crearea
de situaţii problemă, exerciţiul de
consolidare;
Descriere exemplificarea colorării hărţii reprezentând
regiunile istorice ale României folosind cel
mult patru culori;
Cuvinte cheie metoda backtracking, matricea asociată hărţii

M4 – Backtracking recursiv – Plata unei sume de bani
elevii expunere, conversaţie, algoritmizare,
studiu de caz;
prin descoperire;
consolidare, învăţarea prin descoperire
dirijată, inductivă, experimentală, exerciţiul
de consolidare;
Descriere transpunerea unei algoritm backtracking în
termeni recursivi

Cuvinte cheie formule recursive, backtracking recursiv

-7-


M5 – Problema labirintului
elevii expunere, conversaţie, problematizare,
studiu de caz;
prin descoperire;
consolidare, problematizarea prin crearea
de situaţii problemă, exerciţiul de
consolidare;
Descriere exemplificarea generării tuturor soluţiilor de
ieşire dintr-un labirint, pornind dintr-o poziţie
dată.
Cuvinte cheie tehnica backtracking

-8-


2.2. Recomandări de structurare şi predare

1. Planul unităţii de învăţare Timp: 1 oră

Obiect de conţinut Timp (min)
M1 25
M2 25


M3 25
M4 25


M5 25
M6 25

-9-


3. Obiecte de coţinut - detaliere
În continuare vom prezenta în detaliu modul de utilizare a
elementelor din ferestrele lecţiei. (navigare, elemente specifice,
funcţionarea aplicaţiilor, etc.). Subliniem că navigarea elementară
se face cu ajutorul butoanelor descrise în Cap. 1 – Terminologie, al
acestui manual. Nu ne vom referi la acestea decât spicuitiv.

3.1. Backtracking iterativ – Generarea
aranjamentelor

În acest obiect de conţinut este rezolvată grafic problema generăriii
tuturor aranjamentelor de n obiecte luate câte p, particularizată
pentru n = 4 şi p = 3.

În partea stângă a obiectului de conţinut sunt reprezentate grafic
elementele teoretice cu care se lucrează: stiva, figurată printr-un
cilindru transparent în care se pot introduce obiecte printr-un singur
capăt, şi obiectele cărora li se aplică algoritmul, figurate prin bile de
culoare albastră, diferenţiate prin numere.

Alături de aceste elemente sunt afişate, prin enumerare, soluţiile
găsite cu ajutorul algoritmului până în momentul curent.

Elemente în
afara stivei

Soluţii afişate

Stiva
Elemente aflate în stivă

Bilele care se află la un moment-dat în cilindru corespund
elementelor ce se află în stivă. Elementele care nu se află în stivă
sunt reprezentate prin bilele aflate în secţiunea “Numere valide”.

În partea dreaptă este afişat programul sursă ce rezolvă problema
propusă. Săgeata roşie împreună cu dreptunghiul roşu marchează
linia şi instrucţiunea curente.

- 10 -


Dreptunghiul
marchează
Săgeata marchează linia instrucţiunea
de program curentă curentă
Programul sursă se parcurge pas cu pas, folosind butoanele de
navigare între soluţii.

3.2. Colorarea hărţilor

În acest obiect de conţinut este rezolvată grafic problema colorării
hărţilor utilizând cel mult 4 culori, astfel încât două ţări cu frontieră
comună să fie colorate diferit. Problema este particularizată pentru
n = 6 ţări, a căror hartă este reprezentată în partea din stânga jos:

Harta ţărilor Matricea
vecinătăţilor

Matricea vecinătăţilor ilustrează modul în care se învecinează ţările:
dacă a[i, j] are valoarea 0 înseamnă că ţara i nu se învecinează cu
ţara j, iar dacă [i, j] are valoarea 1, ţările i şi j sunt vecine.

Tot în partea stângă, sub hartă, se află un tabel în care sunt afişate
valorile intermediare ale principalelor funcţii şi variable ale
programului. Acestea sunt: k – contor care indică nivelul curent în
stivă; st[] – stiva la momentul curent; succ(), valid(), sol() – funcţii
ale algoritmului implementat; varianta – ultima soluţie găsită.

- 11 -


Contorul care indică Stiva curentă
nivelul curent în stivă

Valorile funcţiilor implementate de algoritm
Ultima soluţie găsită


Dreptunghiul
marchează


3.3. Colorarea hărţilor – Aplicaţie : Harta României

Acest obiect de conţinut reprezintă aplicarea algoritmului de
colorare a hărţior pentru regiunile istorice ale României. În partea
dreaptă este reprezentată harta României, ale cărei regiuni trebuie
colorate cu ajutorul steguleţelor de diverse culori.

Harta de
colorat

Steguleţe
colorate
- 12 -


Selectaţi cu mouse-ul unul din steguleţele disponobile şi trageţi-l
deasupra zonei a cãrei culoare doriţi sã o schimbaţi, ţinând apãsat
butonul stânga al mouse-ului. Eliberaţi steguleţul deasupra
cerculeţului corespunzător fiecărei regiuni : . Pentru a schimba
culoarea unei zone deja colorate, plasaţi steguleţul nou deasupra
vechiului steguleţ.

3.4. Backtracking recursiv – Plata unei sume de
bani

În acest obiect de conţinut este rezolvată grafic problema plăţii uneii
sume de bani s având la dispoziţie n tipuri de bancnote de diferite
valori date.

În partea stângă se pot alege datele de intrare, astfel:
• alegeţi mai întâi suma ce trebuie plãtitã, folosind butoanele
şi pentru a o scădea sau creşte valoarea ei. Această
valoare este reprezentată în chenarul dintre cele două
butoane ;

• alegeţi apoi tipurile de bancnote cu care se face plata apãsând
pe butoanele corespunzãtoare :

• în cazul în care suma este diferitã de 0 şi aţi selectat cel puţin
o bancnotã, în partea dreaptã a ecranului vor apărea
butoanele necesare pentru execuţia pas cu pas a programului.

Tot în partea stângă se află un tabel cu valorile intermediare ale
diverşilor parametri ai programului.

Astfel, datele de intrare în program sunt:

Numărul de
Suma de bani bancnote
selectate

Mulţimea valorilor bancnotelor selectate

- 13 -


iar valorile prelucrate de program în timpul rulării sunt :

Numărul maxim de bancnote din fiecare tip cu
care se poate plăti suma de bani

Nivelul curent în stivă

Stiva la Suma curentă
momentul curent
Ultima soluţie găsită


Dreptunghiul
marchează


3.5. Problema labirintului

În acest obiect de conţinut este rezolvată grafic problema găsirii
tuturor drumurilor de ieşire dintr-un labirint, plecând de la o poziţie
iniţială dată.

Labirintul este reprezentat printr-o matrice cu m linii şi n coloane.
Fiecare element al matricei reprezintă o “poziţie” (celulă, cameră) a
labirintului. Fiecare astfel de cameră are una sau mai multe ieşiri.
Nu există camere izolate.

- 14 -


Se consideră direcţiile de deplasare ale omului în labirint: nord, est,
sud, vest, luate în această ordine. Astfel, ajungând într-o anumită
cameră, se încearcă mai întâi deplasarea către camera din nord.
Dacă există legătură între cele două camere, se face deplasarea.
Dacă nu, se încearcă deplasarea în următoarea direcţie. Acest
algoritm se repetă până s-au epuizat toate posibilităţile.

Pentru fiecare cameră a labirintului se reţine numărul zecimal a
cărui reprezentare binară este dată de ieşirile posibile, astfel: pentru
fiecare direcţie cu ieşire se reţine 1, iar în caz contrar se reţine 0.

Drumurile de ieşire din labirint sunt afişate în momentul găsirii lor,
într-o fereastră de soluţii :

O soluţie este formată de toate camerele prin care trebuie să se
treacă pentru a se ieşi din labirint. O cameră este caracterizată de
linia (x) şi coloana (y) din labirint. Afişarea soluţiilor se face astfel:
pe prima linie, notate cu x, se pun coordonatele liniilor camerelor ce

- 15 -


fac parte din soluţie, iar pe a doua linie, notate cu y, coordonatele
coloanelor camerelor.

Algoritmul respectă regulile tehnicii backtracking şi rulează până
când toate camerele labirintului au fost parcurse.

- 16 -


4. Bibliografie

• Bucur Carmen, Bucur Doina, Pintea Adrian, Salaţiu,
Cristina, Stanca Florentina, Vaida Dana; Informatica –
Culegere de probleme pentru liceu, Editura U.T. Pres, Cluj-
Napoca, 2002

• Cerchez Emanuela, Şerban Marinel; Informatica –
Manual pentru clasa a X-a, Editura Polirom, 2000

• Livovschi L., Georgescu H., Sinteza şi Analiza
algoritmilor, Editura Ştiinţifică şi Enciclopedică, Bucureşti,
1986

• Sorin Tudor; Manual de informatica-clasa a X-a, varianta
C++, Editura L&S Infomat, 2000

• Knuth D. E; Tratat de programarea calculatoarelor
Algoritmi fundamentali, Editura Tehnică, 1974

- 17 -

�ݺ�ߣ

Manualul profesorului

Recommended

More Related Content

Viewers also liked (20)

Similar to Manualul profesorului (20)

More from natashcka (13)

Manualul profesorului