Drumurile In Grafuri. Proiectarea Activitatii Didactice

CUPRINS

INTRODUCERE

Teoria grafurilor s-a dezvoltat la început în paralel cu algebra și a avut ca punct de plecare jocurile matematice. Această formă a științei a căpătat în timp atât formă cât și conținut propriu, devenind un tot unitar bine conturat și bine fundamentat teoretic, cu largă aplicare practică.

Originile teoriei grafurilor se găsesc în rezolvarea unor probleme de jocuri și amuzamente matematice, care au atras atenția unor matematicieni de seamă, cum ar fi: Euler, Hamilton, Cayley, Sylvester, Birkoff.

„Data nașterii” teoriei grafurilor poate fi considerată anul 1736, când matematicianul elevețian Leonhard Euler a publicat în revista Comentarii Academiae Scientiarum Imperialis Petropolitanae un articol în limba latină (Solutio problematis ad geometriam situs pertinentis – Soluția unei probleme legate de geometria propoziției) în care a clarificat „problema celor șapte poduri”, stabilind astfel o metoda pentru rezolvarea unei întregi clase de probleme.

Numeroase situații din viața cotidiană pot fi modelate cu ajutorul teoriei grafurilor.

Numeroase probleme practice, cu aplicații în fizică, economie, chimie, sociologie etc., își găsesc soluția utilizând algoritmi din teoria grafurilor.

Cu 200 de ani mai târziu, în 1936, apărea la Leipzig prima carte de teoria grafurilor, al cărui autor este matematicianul maghiar Dénes König. În amintirea contribuției lui Euler, unele noțiuni și tipuri de grafuri de care acesta s-a ocupat sunt denumite de către König lanț (ciclu) eulerian, graf eulerian, etc.

Un alt matematician care s-a ocupat de aceleași probleme ca și Euler (se pare, fără a cunoaște articolul) dar care și-a publicat rezultatele cercetărilor sale în anul 1873, a fost Carl Hierholzer. Acesta a demonstrat în plus unele rezultate care lui Euler i se păruseră evidente.

În 1851 articolul lui Euler a fost tradus și publicat în revista Nouvelles Annales de Mathematiques, iar rezultatele sale au fost îmbogățite, fiind studiate în clase speciale de grafuri.

Alte izvoare ale teoriei grafurilor sunt: studiul rețelelor electrice, problema celor patru culori, aplicațiile teoriei grafurilor în chimie (inițiate de Cayley), probleme hamiltoniene, grafuri planare, etc.

Fizicianul Kirchhoff a studiat la mijlocul secolului trecut rețelele electrice cu metode care aparțin astăzi teoriei grafurilor, contribuind la dezvoltarea acestei teorii (în anul 1845 a formulat legile care guvernează circulația curentului într-o rețea electrică iar în anul 1847 tot el a arătat cum poate fi construită într-un graf o mulțime fundamentală de cicluri, demonstrând că, pentru orice graf conex cu n vârfuri și m muchii, o mulțime fundamentală de cicluri conține întotdeauna m-n+1 cicluri).

Lucrarea de față are drept scop să-i introducă pe cititorii ei, cu diferite niveluri de pregătire, în aplicațiile de Teoria Grafurilor. Ideea de bază, în jurul căreia gravitează întregul material, este de a găsi decizii pe termen scurt la problemele practice prin intermediul unor modele matematice aparținând teoriei grafurilor.

Punctul de vedere și tematica lucrării reflectă preocuparea de a găsi posibilitatea înțelegerii avantajelor pe care le oferă matematica unui cerc larg de cititori, începând chiar cu elevii de liceu. Pentru elevii de liceu, materialul prezentat constituie un stimulent în învățarea algoritmică și logică a problemelor din domeniul fizicii, chimiei, informaticii etc.

În scopul atingerii obiectivelor amintite, lucrarea, reluând teoria matricilor, vectorilor și sistemelor liniare și prezentând-o într-o manieră accesibilă, construiește o gamă largă de procedee și metode matematice pe care le trimite la probleme de interes practic. Noțiunile sunt prezentate treptat în funcție de gradul de dificultate, iar necesitatea introducerii acestora este justificată cu numeroase exemple practice.

Lucrarea este structurată în patru capitole și anume:

– Capitolul I – Elemente de teoria grafurilor, care cuprinde noțiuni generale despre grafuri orientate și neorientate, tipuri de conexitate în grafuri, matrici atașate unui graf orientat, metode pentru determinarea componentelor tare conexe ale unui graf și aplicații practice ale grafurilor;

– Capitolul II – Drumuri minime-maxime în grafuri, care cuprinde transport pe drumuri minime-maxime în grafuri, algoritmi pentru determinarea drumurilor minime și aplicații;

– Capitolul III, Drumuri hamiltoniene în grafuri, care cuprinde transport pe drumuri hamiltoniene, algoritmi pentru determinarea drumurilor hamiltoniene și aplicații la transporturi pe drumuri hamiltoniene;

– Capitolul IV, Aspecte metodice, care cuprinde aspecte metodice și aplicații. Fiecare capitol cuprinde o prezentare teoretică a informației, iar la final aplicații practice la noțiunile prezentate.

Am ferma convingere că maniera în care este concepută lucrarea va duce la creșterea interesului pentru informatică și mai ales pentru Teoria Grafurilor cu aplicabilitate mare în toate domeniile de activitate, arătând mai clar universalitatea aplicațiilor ei.

CAPITOLUL 1

GRAFURILE ORIENTATE ȘI NEORIENTATE

1.1. Noțiuni generale despre grafuri

Definiția 1.1.1. Fie V o mulțime finită și nevidă de elemente (pe care le numim vârfuri, noduri sau puncte) și fie E o mulțime de perechi ordonate de vârfuri din V (pe care le numim arce sau linii).

Cuplul format din mulțimile V și E se numește graf orientat și se notează prin G = (V, E).

Observația 1.1.1. Mulțimea V, a vârfurilor grafului, poate fi și infinită, dar numărabilă, caz în care graful este numit graf infinit. De asemenea, pot fi luate în considerație grafuri la care între doua vârfuri pot exista mai multe arce cu același sens (așa-numitele multigrafuri). Nu voi folosi astfel de grafuri în lucrarea de față.

Observația 1.1.2. Un arc de forma (xi, xj) cu xi V, se numește buclă. În lucrarea de față, nu voi lucra cu grafuri ce conțin bucle.

Exemplul 1.1.1. Fie V = [x1, x2, x3, x4, x5] mulțimea operațiilor de prelucrare, ce trebuie aplicate pentru fabricarea unei piese P, aceste operații reprezentând vârfurile unui graf orientat G. Vom considera că graful G conține arcul (xi, xj), cu xi, xj V, dacă operația notată cu xj nu poate fi efectuată dacă nu s-a efectuat anterior (indiferent când) operația xi. Conform acestei convenții, să presupunem că mulțimea arcelor grafului G este următoarea:

E = [(x1, x2), (x1, x3), (x1, x4), (x1, x5), (x2, x4), (x2, x5), (x3, x4), (x3, x5), (x4, x5)]

Fiind cunoscute mulțimile V și E, graful G = (V, E), care exprimă matematic, fenomenul de realizare a piesei P, este perfect determinat.

Deosebit de utilă este adesea reprezentarea geometrică a unui graf orientat, care se obține în modul următor:

se reprezintă vârfurile grafului ca puncte în plan;

fiecare arc (xi, xj) E se reprezintă printr-o linie ce unește punctul corespunzător vârfului xi cu punctul corespunzător vârfului xj, linie pe care se găsește o săgeată, cu sensul de la xi către xj.

Dăm, ca exemplu, reprezentarea geometrică a grafului G=(V, E), definit în exemplul precedent, aceasta având forma din figura 1.1.1.

În unele aplicații practice, la folosirea conceptului de graf nu este necesară orientarea liniilor grafului. În astfel de situații, în locul mulțimii de arce, se consideră o mulțime analoagă numită mulțimea muchiilor. O muchie, ce unește vârfurile xi și xj, este perechea neordonată a acestor vârfuri (nu contează ordinea lor); ea se reprezintă simbolic prin [xi,xj] și este evident identică cu [xj, xi]. Putem astfel să vorbim despre graful neorientat G=(V, E).

Observația 1.1.3. Un graf neorientat G=(V, E) poate fi înlocuit în aplicații printr-unul orientat, cu aceeași mulțime de vârfuri, dar corespunzător fiecărei muchii [xi, xj]E, introducându-se în noul graf două arce de sens contrar, (xi, xj) și (xj, xi). Pot fi folosite, de asemenea, și grafuri mixte, care conțin atât arce, cât și muchii.

Observația 1.1.4. Reprezentarea geometrică a unui graf neorientat se face asemănător cu aceea a unui graf orientat, cu deosebirea că nu mai punem săgeți pe linii.

Exemplul 1.1.2. Să interpretăm punctele importante ale unei rețele de curent alternativ ca vârfuri, iar liniile electrice care le unesc, ca niște muchii (evident, nu contează sensul acestora). Se definește astfel un graf neorientat, ce poate reprezenta matematic rețeaua electrică respectivă.

Considerând un arc (xi, xj), al unui graf orientat, spunem că xi este extremitatea inițială, iar xj extremitatea finală a arcului. Evident, în cazul unei muchii, distincția dintre cele două extremități nu se mai face.

Definiția 1.1.2. Două vârfuri ale unui graf, G=(V, E), se numesc vârfuri adiacente, dacă ele sunt unite în graf prin cel puțin un arc (o muchie). Spunem, de asemenea că un arc (muchie) este incident unui vârf, dacă vârful respectiv reprezintă una din extremitățile arcului (muchiei). Mai precis, în cazul grafului orientat, dacă este incident exterior vârfului, iar dacă vârful este extremitatea finală a arcului, spunem că arcul este incident interior vârfului.

Ca exemplu, să luăm arcul (x2, x5) din figura 1.1.1 el este incident exterior vârfului x2 și incident interior vârfului x5.

Definiția 1.1.3. Numărul de arce incidente exterior unui vârf xi V, poartă numele de grad exterior de incidență corespunzător vârfului xi și se notează cu g+(xi), sau, mai simplu, cu gi+. Analog, numărul de arce incident interior vârfului xi este gradul interior de incidență al vârfului xi și se notează cu g-(xi) sau cu gi-. Gradul de incidență al unui vârf xiV (fără specificarea de grad exterior sau interior) este dat de numărul de arce incidente vârfului xi; el se notează cu g(xi), sau mai simplu cu gi. În cazul unui graf orientat și fără bucle, avem evident: gi = gi++ gi-.

Pentru aplicarea grafurilor la problemele puse de practică, unui graf G=(V,E) i se mai atașează adesea o funcție reală w : ER, numită funcție valoare. Această funcție face ca fiecărui arc (xi, xj)E să-i corespundă o valoare reală notată cu w(xi, xj) și numită valoarea arcului. În acest fel, graful devine un graf ponderat și se notează, simbolic prin G=(V,E,w). Desigur, asemănător se pot atașa valori și muchiilor unui graf neorientat.

În ceea ce privește interpretarea valorilor ce se atașează, arcelor (muchiilor) unui graf, acesta depinde de problema practică ce se rezolvă cu ajutorul modelului graf corespunzător.

Exemplul 1.1.3 Se dă graful G = (V, E, w), în care:

– vârfurile reprezintă punctele ce trebuie aprovizionate de un depozit,

-arcele reprezintă posibilitățile de transport între diferitele puncte ale sistemului,

-valoarea w(xi, xj), atașată arcului (xi, xj)E, reprezintă cheltuielile de transport al unei unități de produs între punctele xi și xj (în această ordine).

Definiția 1.1.4. Se numește drum între vârfurile xi și xj, într-un graf orientat, o succesiune de arce, astfel încât extremitatea inițială a fiecăruia coincide cu extremitatea finală a celui precedent, excepție făcând extremitatea inițială a primului arc, care este xi și extremitatea finală a ultimului arc, care este xj. Drumul descris se reprezintă pe scurt prin d(xi, xj), iar desfășurat se scrie astfel:

d(xi, xj) = (xi, xk, x1, xm, …, xp, xj),

cu convenția că nu se scriu de două ori extremitățile ce coincid, pentru fiecare pereche de arce alăturate. Lungimea unui drum este, prin convenție, numărul de arce din care este compus drumul. Evident, un drum de lungime egală cu unu nu este altceva decât un arc. Valoarea unui drum este egală cu suma valorilor arcelor ce formează drumul. Astfel, fiind dată funcția valoare w:ER, valoarea drumului d(xi, xj) este dată prin:

w[d(xi, xj)] =

Definiția 1.1.5. Se numește drum elementar un drum care nu trece de două ori prin același vârf.

Definiția 1.1.6. Se numește drum hamiltonian – notat prescurtat cu DH – un drum care trece prin toate vârful grafului, câte o singură dată.

Dacă un graf orientat conține cel puțin un drum de la xi la xj, spunem că xi atinge pe xj, sau că xj este atins de la xi. Numărul de vârfuri, ce pot fi atinse de la vârfuri xi, poartă numele de putere de atingere a vârfului xi și se notează cu p(xi), sau mai scurt cu Pi. Două vârfuri, xi și xj, astfel încât în graful G, xi atinge pe xj, iar xj atinge pe xi, se zic vârfuri mutual atinse; aceasta înseamna de fapt că graful G conține cel putițn un drum de la xi la xj și cel puțin un drum de la xj la xi.

Definiția 1.1.7. Se numește circuit într-un graf, un drum închis, în sensul că extremitatea finală a drumului coincide cu extremitatea inițială a sa.

Definiția 1.1.8. Se numește circuit Hamiltonian, notat pe scurt prin CH, un circuit care trece prin toate vârfurile grafului câte o singură dată, cu excepția extremităților, ce coincid.

Toate conceptele, definite mai sus, ce exprimă legături între diferitele vârfuri ale unui graf, se numesc concepte orientate, deoarece în definirea lor se ține seama de orientarea arcelor. La baza lor stă noțiunea de drum, acesta având un sens ce corespunde cu sensurile tuturor arcelor ce îl compun.

Exemplul 1.1.4. Fie graful orientat din figura 1.1.2. Unul dintre drumurile de la x1 la x5 este format din arcele (x1, x4) și (x4, x5), puse cap la cap. El se scrie astfel: d(x1, x5) = (x1, x4, x5) și are o lungime egală cu doi (este format din două arce). Un alt drum de la x1, la x5, de asemenea, cu o lungime egală cu doi, este drumul d'(x1, x5) = (x1, x3, x5). Există în graful dat și alte drumuri între vârfurile x1 și x5. Dintre acestea, iată unul care nu este elementar, trecând de două ori prin vârful x3: d’’(x1,x5)=(x1,x3,x6,x2,x3,x5).

De asemenea, prezentăm două drumuri hamiltoniene ale grafului:

DH1 = (x1, x2, x3, x6, x4, x5)

DH2=(x3, x6, x4,x5, x1, x2).

Iată și un circuit hamiltonian: CH = (x1, x2, x3, x6, x4, x5,x1). În sfârșit, dăm un exemplu de circuit, al grafului, care nu este hamiltonian: d(x2, x2) = (x2, x3, x5, x2).

Conceptele neorientate, corespunzătoare celor prezentate mai sus, se definesc într-un graf neorientat.

Definiția 1.1.9. Într-un graf neorientat o succesiune de muchii puse cap la cap formează un lanț. Dacă lanțul trece prin fiecare vârf al grafului, câte o singură dată, el se, numește lanț hamiltonian, prescurtat LH.

Definiția 1.1.10. Un lanț închis (care se termină cu același vârf cu care începe) se numește ciclu. Un ciclu este hamiltonian dacă trece prin toate vârfurile grafului câte o singura dată, cu exceptia primului și ultimului vârf, care coincid; el se notează prescurtat prin CH.

Observația 1.1.5. În lucrarea de față, vom scrie lanțurile ca și pe drumuri, dar cu paranteze drepte.

Conceptele neorientate se pot defini și într-un graf orientat, dar ele se construiesc fără a ține seama de orientările arcelor, ci considerându-le ca pe muchii. Astfel, pentru două arce alăturate, ce intră în compunerea unui lanț definit pe un graf orientat, pot coincide două extremități de același fel (fie extremitățile inițiale, fie cele finale). În acest fel, unele arce ale lanțului au un sens ce coincide cu sensul de citire a lanțului, iar altele au sens contrar sensului: de citire a lanțului. Exemplele de mai jos vor lămuri mai bine aceste afirmații.

Exemplul 1.1.5. Fie graful neorientat din figura 1.1.3, în care există următoarele lanțuri între vârfurile x2 și x4: l1(x2, x4)= [x2, x3, x4], l2 (x2, x4)= [x2, x5, x4], l3(x2, x4)= [ x2, x5, x3, x4] etc.

Un lanț hamiltonian este următorul: LH1 = [x5, x1, x2, x3, x4], iar un ciclu hamiltonian este CH1 =[x1, x2, x3, x4, x5, x1]. Exemple de cicluri: [x1, x2, x5], [x2, x5, x4, x3] etc.

Exemplul 1.1.5. Fie acum graful orientat din figura 1.1.4, în care considerăm următorul lanț: l(x1, x2) = [x1, x5, x3, x2]. El este format cu ajutorul arcelor (x1, x5), (x3, x5) și (x2, x3), dintre care numai sensul primului coincide cu sensul de citire a lanțului, celelalte două având sensuri contrare și anume:

– arcul (x3, x5) apare în lanț cu sensul de citire de la x5, către x3

– arcul (x2, x3) apare în lanț cu sensul de citire de la x3 către x2

În aceeași figură 1.1.4, putem considera și ciclul [x1, x2, x3, x4, x5, x1], în care ultimele două arce sunt parcurse în sens contrar sensului lor.

1.2. Tipuri de conexiune a grafurilor

Definiția 1.2.1. Un graf (orientat sau neorientat) se numește graf conex, dacă pentru orice vârfuri, xi și xj ale sale, există în graf cel puțin un lanț care le leagă. În cazul contrar, când graful conține cel puțin două vârfuri nelegate prin nici un lanț, el este graf neconex. Ca exemple de grafuri conexe, putem da pe cele din figurile 1.1.1 – 1.1.4, iar ca exemplu de graf neconex dăm graful din figura 1.2.1,care are șase vârfuri. Într-adevăr, în acest din urmă graf, vârfurile x1 și x4 (de exemplu), nu sunt unite prin nici un lanț.

Definiția 1.2.2. Un graf orientat este tare conex, dacă orice două vârfuri ale sale sunt mutual atinse. Aceasta înseamnă că, dacă luăm spre cercetare două vârfuri ale grafului, xi și xj, alese la întâmplare, graful conține cel puțin un drum de la xi la xj și cel puțin un drum de la xj la xi.

Observația 1.2.1. Proprietatea de tare conexiune este foarte importantă, de exemplu, în rețelele de comunicații, în cadrul cărora trebuie să se poată ajunge oricând de la un punct oarecare xi al rețelei, la un alt punct xj al aceleași rețele. Dăm, ca exemplu de graf tare conex, pe cel din figura 1.2.2, verificarea proprietății de tare conexiune rămânând pe seama cititorului. Desigur, dacă graful ar avea un număr mare de vârfuri această verificare nu se mai poate face cu ușurință în mod direct, fiind necesară o metodă matematică.

Definiția 1.2.3. Dacă dintr-un graf G eliminăm o parte din arce (sau muchii), dar păstrăm toate vârfurile, obținem un alt graf, care se numește graf parțial al lui G.

Definiția 1.2.3. Dacă dintr-un graf G eliminăm o parte din vârfuri, împreună cu toate arcele incidente cu vârfurile eliminate, se obține un subgraf al lui G.

Definiția 1.2.4. Un subgraf maximal tare conex, al unui graf orientat G, se numește componentă tare conexă a lui G. Aici, cuvintul ,,maximal" are sensul că dacă subgraful menționat are măcar un vârf în plus, atunci își pierde proprietatea de tare conexiune. Analog, un subgraf maximal conex, al unui graf G (orientat sau neorientat), se numește componentă conexă a grafului G.

Observația 1.2.2. În lucrarea de față vom lucra numai cu grafuri conexe, deci cu grafuri ce au câte o singură componentă conexă.

Exemplul 1.2.1. Graful din figura 1.2.1. are două componente conexe și anume subgrafurile cu mulțimile de vârfuri {x1, x3, x5, x6} și {x2, x4}. Într-adevăr, dacă la prima submulțime a vârfurilor am adăuga fie vârful x2, fie vârful x4, am obține subgrafuri neconexe ale celui dat inițial. Pe de altă parte, să cercetăm graful G, din figura 1.2.3. Subgraful lui G, care conține numai vârfurile x1, x2 și x5, este o componentă tare conexă, deoarece:

– între aceste vârfuri există drumuri oricum le-am grupa, ceea ce se observă ușor, în mod direct,

– dacă adăugăm la aceste vârfuri, fie vârful x3, fie vârful x4, fie pe amândouă, în subgraful obținut există grupe de vârfuri între care nu există nici un drum.

Cea de a doua componentă tare conexă, a grafului G, este reprezentată de subgraful cu vârfurile x3 și x4, ceea ce se verifică, de asemenea, ușor, în mod direct.

Definiția 1.2.5. Graful condensat, corespunzător unui graf orientat G, este un graf G* = (V*,E*), definit astfel:

– vârfurile lui sunt componentele tare conexe ale grafului G, notate, de exemplu, prin C1, C2, … Ck,

– mulțimea E* conține arcul (Cr, Cs), dacă și numai dacă graful inițial G conține cel puțin un arc cu extremitatea inițială într-un vârf din Cr și cu extremitatea finală într-un vârf din Cs. Ca exemplu, dăm graficul condensat al grafului G reprezentat în figura 1.2.3; el are numai două vârfuri (corespunzătoare celor două componente tare conexe indicate mai sus) și un singur arc, așa cum apare în figura 1.2.4. Într-adevăr, dacă notăm cu C1 componenta tare conexă a lui G, care conține vârfurile xl, x2 și x5, iar cu C2 cealaltă componentă tare conexă, graful G* va conține arcul (C1, C2), deoarece G are arcele (x2, x3) și (x5, x4), dar nu va conține arcul (C2, C1), neexistând în G nici un arc de la x3 sau x4 spre x1, x2 sau x5.

1.3. Matrici atașate unui graf orientat

Pentru rezolvarea diferitelor probleme practice, cu ajutorul modelelor-grafuri, mai ales în cazul unor grafuri de dimensiuni mari, este necesar ca acestea să fie reprezentate sub forma unor matrici, pe care calculele se efectuează ușor.

Definiția 1.3.1. Fiind dat un graf orientat G, cu n vârfuri, se numește matricea arcelor a acestui graf o matrice pătrată A, de ordinul n, ale cărei elemente sunt egale cu zero și cu unu, construită după regula următoare: elementul ce se află la intersecția liniei de ordin i, cu coloana de ordin j, este egal cu unu dacă graful G conține arcul (xi ,xj) și este egal cu zero dacă graful nu conține acest arc. Putem reprezenta matricea arcelor grafului G=(V,E) simbolic, sub forma următoare:

A=(aij), i=1, 2, …, n; j= 1, 2, …, n,

Unde:

aij=

Observația 1.3.1. Elementele matricei arcelor grafului G le vom nota totdeauna cu aij, i=1, 2, …, n; j= 1, 2, …, n.

Deoarece toate elementele matricei A sunt egale cu zero și unu, se spune că aceasta este o matrice booleană. Accentuăm încă odată, că existența unui arc, între două vârfuri fixate ale grafului, este pusă în evidență de un element egal cu unu din matricea A, după regula: extremitatea inițială a arcului corespunde la linie, iar extremitatea finală la coloana matricei, în care se gasește elementul egal cu unu. De aceea, putem spune că liniile consecutive ale matricei A corespund la vârfurile grafului, așezate într-o ordine stabilită (de exemplu, în ordinea crescătoare a indicilor, x1, x2, … xn), iar coloanele consecutive ale matricei A corespund, de asemenea, vârfurilor grafului, așezate in aceeași ordine. Pentru a evidenția această corespondență, ce va ajuta în urmărirea calculelor ce vor fi descrise mai departe, vârfurile în cauză se pot trece pe marginile matricei, în partea stângă (pentru linii) și în partea de sus (pentru coloane), așa cum rezultă și din exemplul ce urmează.

Exemplul 1.3.1. Să considerăm graful orientat G, din figura 1.3.1. Matricea arcelor acestui graf este următoarea:

A=

Pentru o urmărire mai ușoară a modului în care s-a completat această matrice, ca și pentru folosirea ei în eventualele calcule, vom obișnui să scriem matricea arcelor ca în tabelul 1.3.1, notând în evidență vârfurile, ce corespund la diferitele linii și coloane ale ei. Astfel, de exemplu, elementul egal cu unu de pe linia x1, și coloana x2, arată existența în graf a arcului (x1, x2). De asemenea, elementul egal cu zero, de pe linia x1 și coloana x3, arată că în graful G nu există arcul (x1, x3).

Observația 1.3.2. Conform convenției făcute, în partea stângă a matricei A sunt scrise totdeauna plecările arcelor, iar în partea de sus a matricei sosirile acestor arce (arce corespunzătoare elementelor egale cu unu).

Observația 1.3.3. Faptul că un graf G nu conține bucle se poate deduce din inexistența elementelor egale cu unu, de pe diagonala principală a matricei arcelor acestui graf.

Tabelul 1.3.1

Observația 1.3.4. Deoarece elementele egale cu unu, de pe linia xi, a matricei arcelor unui graf G, reprezintă singurele arce ce au ca punct de plecare vârful xi, suma elementelor liniei xi este egală cu gradul exterior de incidență al acestui vârf. Analog, suma elementelor de pe coloana xj, din matricea arcelor unui graf G, este egală cu gradul interior de incidență al vârfului xi.

Definiția 1.3.2. 0 altă matrice, ce se atașează unui graf orientat G cu n vârfuri și pe care o folosim în mod deosebit, este matricea drumurilor, pe care o notăm cu D. Ea este, de asemenea, o matrice booleană, pătratică de ordinul n. 0 vom reprezenta simbolic prin:

D = (dij), i= 1,2, …, n; j=1, 2, …, n,

unde:

dij=

Pentru o utilizare comodă a matricei drumurilor, aceasta va fi reprezentată sub forma unui tabel asemănător cu cel folosit la matricea arcelor, adică în care atât liniile cât și coloanele corespund la vârfurile grafului, puse într-o anumită ordine. Convenția este aceeași, liniile corespunzînd la plecările de drumuri, iar coloanele la sosirile acestor drumuri.

Observația 1.3.5. Existența unor elemente egale cu unu, pe diagonala principală a matricei drumurilor, arată existența unor circuite în graful G. Evident, dacă matricea drumurilor unui graf are toate elementele de pe diagonala principală egale cu zero, graful corespunzător nu are circuite și reciproc.

Observația 1.3.6. Graful G este tare conex dacă și numai dacă toate elementele matricei drumurilor sunt egale cu unu. Această observație poate folosi ca metodă de verificare a faptului că un graf este sau nu tare conex.

Observația 1.3.7. Elementele egale cu unu, de pe linia xi, a matricei drumurilor unui graf G, arată spre ce vârfuri pornesc drumuri din xi, adică ce vârfuri sunt atinse de la xi. În acest sens, suma elementelor de pe linia xi a matricei drumurilor este egală cu puterea de atingere a vârfului xi. În plus, putem preciza că elementele egale cu unu, de pe cbloana xi a matricei drumurilor, arată de la ce vârfuri este atins xi în graful considerat

Exemplul 1.3.2. Metodă de calcul a matricei drumurilor. În cele ce urmează vom arăta, pe baza unui exemplu, cum se poate calcula matricea drumurilor unui graf orientat, pornind de la matricea arcelor a sa. Fie graful G, din figura 1.3.2, a cărui matrice a arcelor A este reprezentată în tabelul 1.3.2. Să calculăm, mai întâi, prima linie din matricea drumurilor D, linie ce corespunde vârfului x1: ea va conține ca elemente egale cu unu, pe cele ce indică existența drumurilor din graf, ce pornesc din x1. Există, evident, două drumuri cu lungimea egală cu unu, de acest fel, ele fiind formate din arcele (x1, x2) și (x1, x3),deci d12=1 și d13=1. Aceasta înseamnă, în general, că linia x1, din matricea drumurilor conține, pe lângă alte eventuale elemente egale cu unu: pe cele de pe linia corespunzătoare a matricei arcelor. Completând, într-o primă etapă, linia x, din D cu elementele egale, cu unu ce corespund la drumuri de lungime egală cu unu, aceasta are forma următoare (formă intermediară):

Tabelul 1.3.2

Aici, pe locurile rămase libere considerăm zerouri, pe care nu le scriem, deocamdată, deoarece se pot transforma în elemente egale cu unu (dacă există drumuri corespunzătoare, de lungimi mai mari ca unu).

Să cercetăm acum existența sau inexistența, pentru locurile rămase libere, a unor drumuri de câte două arce. Deoarece aceste drumuri trebuie să plece din x1, ele încep, fie cu arcul (x1, x2) , fie, cu (x1, x3) și se continuă cu încă câte un arc, ce pornește respectiv din x2 sau x3. Să considerăm aceste posibilități pe rând. Astfel, luând spre cercetare arcul (x1, x2) indicat prin primul element egal cu unu de pe linia incompletă de mai sus), el trebuie prelungit cu un alt arc, ce pornește din x2. Astfel de arce sunt indicate însă de elementele egale cu unu, de pe linia x2 din matricea arcelor; există doua astfel de elemente, unul în dreptul coloanei x4 și altul în dreptul coloanei x5, ele indicând deci existența în graf a arcelor (x2, x4) și (x2, x5). Cuplând arcele în cauză, rezultă că graful dat conține drumurile (x1, x2, x4) și (x1, x2, x5), adică x1 atinge atât pe x4 cât și pe x5. Consemnăm cele de mai sus, prin completarea liniei x1, din matricea drumurilor, cu încă două elemente, ea căpătând forma intermediară următoare:

Și de această dată, locurile rămase libere sunt considerate ca zerouri, dar nu au fost efectiv completate, deoarece unele dintre ele se pot transforma în elemente unu (dacă există în graf unele drumuri de câte trei sau mai multe arce).

A fost folosit elementul egal cu unu, din dreptul coloanei x2, al schemei (1), fapt indicat pe această schemă printr-o bifă. Continuăm raționamentul folosind elementul egal cu unu din dreptul coloanei x3, bifat și el în schema (2). Arcul (xI, x3) poate fi prelungit cu un arc ce pleacă din x3: există două astfel de arce (x3, x1) și (x3, x5), indicate de elementele egale cu unu de pe linia x3 a matricei A. Aceasta înseamnă că graful G conține drumurile (x1, x3, x1) și (x1, x3, x5). Existența primului, dintre aceste două drumuri, ne determină să punem d11=1 (primul element al liniei x1 din D este egal cu unu). Cel de al doilea, drum nu mai modifică linia x1 din schema (2), deoarece în această schemă este marcat anterior d15=1. Aceasta se explică prin faptul că de la x1 la x5, există mai mult decât un drum (unul prin x2, altul prin x3), iar noi marcăm cu unu existența a cel puțin unui drum între vârfurile respective. Consemnarea raționamentului de mai sus conduce la următoarea formă intermediară a liniei x1, din matricea D:

în care a rămas necompletat un singur loc. Pentru eventuala completare cu unu, a locului ramas liber, să cercetăm existența în graf a drumurilor de câtre trei arce. Un astfel de drum este compus dintr-un drum de două arce, prelungit cu incă un arc. Drumurile de câte două arce sunt reprezentate însă sub forma elementelor egale cu unu, apărute în etapa precedentă există drumuri de acest fel de la x1 la x1, x4 și x5, deoarece pe linia x1 din schema (3) au apărut elemente egale cu unu în dreptul coloanelor x1, x4 și x5. Cercetarea posibilităților de prelungire a lor cu câte un arc decurge în felul următor :

a) Drumul de la x1 la x1 se poate prelungi cu arcul (x1, x2) sau cu arcul (x1, x3), dând drumuri de la x1 la x2 sau de la x1 la x3. Existența unor asemenea drumuri este indicată însă în schema (3), prin elemente egale cu unu în dreptul coloanelor x2, și x3 (au existat drumuri cu lungimi mai mici, între vârfurile respective).

b) Drumul de la x1, la x4 se poate prelungi cu arcul (x4, x6) indicat de elementul a46=1 de pe linia x4 a matricei A. Există, deci un drum de trei arce, de la x1, la x6, ceea ce se va marca printr-un element egal cu unu in locul rămas liber în schema (3). Obținem astfel schema următoare:

în care nu mai are rost să continuăm operațiile, deoarece nu mai poate apărea nici un element egal cu unu. Prima linie, a matricei drumurilor grafului G, are numai elemente egale cu unu, ceea ce înseamnă că x1 atinge toate vârfurile grafului.

Să sintetizăm calculele efectuate până acum, pentru a da o regulă generală, de determinare a liniei x1, din matricea D, metodă în care să nu mai fie nevoie de a interpreta de fiecare dată unele sau altele dintre drumurile existente în graf. Pentru aceasta, vom folosi operația de adunare booleană a doua numere ce se execută numai în cadrul mulțimii {0,1}. Semnul acestei operații este semnul obișnuit de adunare a numerelor (semnul plus), cu un punct deasupra. Cele patru posibilități de adunare booleană, a două, numere, se definesc astfel:

Se observă că adunarea booleană a unui termen egal cu unu, face totdeauna ca rezultatul să fie egal cu unu (indiferent de termenul la care se adună el).

Revenind la modul de, calcul al liniei x1, din matricea D, observăm că ea începe cu linia corespunzătoare (linia x1,) din matricea A (vezi schema (1)). Cele două elemente egale cu unu, de pe această linie, se găsesc în dreptul coloanelor x2 și x3, de aceea, adunăm boolean, la linia din schema (1), liniile x2 și x3 din matricea arcelor (evident, pe rând, bifând elementele folosite, obținând schemele (2) și (3)). În acest fel, au apărut noi elemente egale cu unu, ce se găsește în dreptul coloanelor x1, x4 și x5. Conform acestor noi elemente apărute, adunăm boolean la linia din schema (3), liniile x1, x4 și x5 din matricea arcelor. Astfel de operații ar fi continuat cât era posibil dacă nu s-ar fi completat toată linia din, schema (4) cu elemente egale cu unu.

Din modul în care am raționat pentru calculul liniei x1, a matricei D, putem deduce cu ușurință că deducerea oricărei linii xi, i= 1, 2, …, n, a matricei D, se poate face în mod asemănător, dar pornind inițial de la linia corespunzătoare xi, a matricei arcelor. Astfel, pentru a calcula linia x2, a matricei drumurilor, pornim de la schema următoare, în care am încărcat numai elementele egale cu unu de pe linia x2 a matricei A.

În schema (5) am bifat elementul egal cu unu din dreptul coloanei x4, urmând să adunăm boolean la linia x2 a schemei, linia x4, din matricea A. Această adunare booleană mai aduce un element egal cu unu, în dreptul coloanei x6, ajungându-se la schema următoare:

În schema (6) am bifat elementul egal cu unu, din dreptul coloanei x5, urmând să adunăm boolean, la linia din schema respectivă linia x5 din matricea arcelor; această operație nu mai aduce nimic nou la schema (6), existând elemente egale cu unu în dreptul coloanelor x4 și x6. Vom bifa deci și elementul egal cu unu, din dreptul coloanei x6, urmând să adunăm boolean linia x6 din matricea arcelor; nici accastă operație nu aduce nimic nou, linia în cauză fiind plină cu zerouri. Deoarece procesul de mai sus nu mai poate continua (nemaiexistând elemente egale cu unu nebifate), completăm efectiv locurile libere cu zerouri, rezultând astfel linia x2 din matricea drumurilor:

Procedând în mod asemănător cu toate vârfurile grafului G, se obține matricea drumurilor acestui graf, ce se găsește în tabelul 1.3.3

Tabelul 1.3.3

Observația 1.3.8. Ordinea în care se bifează elementele egale cu unu, pentru a face adunările booleene corespunzătoare, este indiferentă (chiar dacă aceste elemente au apărut mai devreme sau mai târziu). De asemenea, dacă una din liniile matricei D' a fost calculată, fie ea linia xi, iar la un moment dat urmează să adunăm boolean, la una din linii, linia xi a matricei A, putem înlocui această adunare cu adunarea booleană a liniei xi din matricea D, ceea ce poate scurta calculul.

Proprietatea 1.3.1. Deoarece dij = 1, dacă și numai dacă xi, atinge pe xj rezultă că suma elementelor de pe linia xi, i= 1, 2, …, n, a matricei drumurilor, reprezintă puterea de atingere a vârfului xi.

Proprietatea 1.3.2. Elementele egale cu unu, de pe diagonala principală a matricei drumurilor, arată existența în graf a unor circuite. De aici rezultă și o metodă de a testa dacă un graf este fără circuite: se calculează matricea drumurilor sale, ea trebuind să aibă pe diagonala principală numai elemente egale cu zero.

Teorema 1.3.1. Dacă în matricea drumurilor unui graf fără circuite, vârfurile sunt scrise într-o ordine descrescătoare a puterilor de atingere, această matrice este triangulară superior, adică toate elementele egale cu unu din ea se găsesc deasupra diagonalei principale.

Pentru justificarea acestei teoreme, să notăm vârfurile grafului, scrise într-o ordine descrescătoare a puterilor de atingere, prin x1’, x2’, x3’, …,xn’, deci:

p(x1’)p(x2’)p( x3’) …p(xn’)

Evident, aceste vârfuri sunt tot vârfurile x1, x2, x3, …, xn, dar scrise eventual într-o altă ordine. Menționăm în plus că atunci când unele vârfuri ale grafului au puteri de atingere egale, aceste vârfuri se așează între ele într-o ordine indiferentă, ceea ce justifică semnele de egalitate, din înșiruirea de mai sus a puterilor de atingere.

Matricea drumurilor grafului dat, în care vârfurile sunt scrise în ordinea x1’, x2’, x3’, …,xn’, are forma din tabelul 1.3.4, ea fiind notată cu D’.

Tabelul 1.3.4

Să notăm elementele ei cu d'ij, i=1, 2, …, n; j=1, 2, …, n, elementul d’ij fiind cel ce se află la intersecția liniei x’i cu coloana x’j. În tabelul 1.3.4, aceste elemente nu apar, ele fiind cercetate în cele ce urmează. Trebuie să arătăm că un element oarecare al matricei, care este egal cu unu, nu se poate afla decât deasupra diagonalei principale, marcată printr-o linie de tabel. Fie din elementul d'ij =1 și să arătăm că i<j, adică linia x’i (respectiv coloana x’i ) se află înaintea liniei x’j ( respectiv coloanei x’j ), ca în tabelul 1.3.4. aceasta înseamnă că trebuie să arătăm că vârful x’i are o putere de atingere cel puțin egală cu aceea a vârfului x’j. Pentru aceasta, să folosim definiția matricei drumurilor, din care deducem că graful dat conține cel puțin un drum de la x’i la x’j ( avem d’ij=1). Privind figura 1.3.3, observăm că, în condițiile menționate, orice vârf atins de la x’j, este atins și de la x’i; în plus x’i atinge încă cel puțin un vârf în plus, pe x’j, ceea ce înseamnă că p(x’i) > p(x’j). Cu aceasta, justificarea teoremei este completă.

Definiția 1.3.3. Vom numi matricea drumurilor, în care vârfurile sunt scrise într-o ordine descrescătoare a puterilor de atingere, matricea drumurilor triangularizată, ea fiind notată cu D'. În această matrice, toate elementele de pe diagonala principală și de sub această diagonală, sunt egale cu zero. Așa cum s-a arătat, toate elementele diferite de zero (egale cu unu) ale matricei se află deasupra diagonalei principale, putând însă exista deasupra acestei diagonale și elemente nule.

Observația 1.3.9. Pentru a scrie matricea D', corespunzătoare unui graf făra circuite, calculăm mai întâi matricea drumurilor grafului, din care se determină puterile de atingere ale vârfurilor. Apoi, în matricea D schimbăm ordinea liniilor, apoi a coloanelor, conform unei succesiuni a vârfurilor, având puteri de atingere descrescătoare. Exemplul ce urmează va lămuri pe deplin metoda.

Exemplul 1.3.3. Fie graful G, din figura 1.3.4, a cărui matrice a drumurilor este conținută de tabelul 1.3.5. În partea dreaptă a acestui tabel sunt calculate puterile de atingere ale vârfurilor, ca sume ale elementelor de pe liniile matricei D. Cea mai mare putere de atingere o are vârful x4(p4), ceea ce înseamnă că în noua înșiruire a vârfurilor, vom începe cu x4(x1’=x4). Urmează vârfurile x3 și x5, cu puterile de atingere egale (p3=p5=2), pe care le vom așeza într-o ordine arbitrară, de exemplu x’2=x3 și x’3=x5. Vor urma apoi în ordine, vârful x’4=x2 (cu puterea de atingere egală cu unu) și vârful x’5=x1 (cu putere de atingere nulă). În cazul nostru, succesiunea teoretică a vârfurilor, x1’, x2’, x3’, x4’, x5’, este următoarea:

x4, x3, x5, x2, x1.

Tabelul 1.3.5

Să schimbăm, mai întâi, ordinea liniilor matricei D, conform acestei noi succesiuni a vârfurilor, păstrând ordinea coloanelor neschimbată; obținem astfel matricea intermediară , din tabelul 1.3.6.

Tabelul 1.3.6

În această matrice intermediară, schimbăm ordinea coloanelor, astfel încât să coincidă cu ordinea nouă fixată mai sus, deci cu ordinea liniilor. Se obține astlel matricea drumurilor triangularizată D’ din tabelul 1.3.7.

Tabelul 1.3.7

Observația 1.3.9. Un rezultat asemănător s-ar fi obținut, dacă în ordinea descrescătoare a puterilor de atingere, vârfurile s-ar fi așezat în succesiunea x4 , x5, x3, x2, x1 .

Teorema 1.3.2. În matricea drumurilor triangularizată, corespunzatoare unui graf fără circuite, primul element egal cu unu de pe fiecare linie și ultimul element egal cu unu de pe fiecare coloană, corespund la drumuri de câte un singur arc în vârf.

Pentru justificare, să considerăm dij’=1, ca prim element egal cu unu, de pe linia xi’ a matricei D'. Pe de o parte, acest lucru înseamnă că graful conține cel puțin un drum de la xi’ la xj’. Să presupunem prin absurd că ar exista un astfel de drum cu mai mult de un arc, deci care ar trece printr-un vârf intermediar xm’ xi’. Reprezentăm acest drum prin d= (xi’ , …, xm’ , …, xj’). Este clar de aici, că graful dat conține cel puțin un drum de la xi’, la xm’, adică dim’=1; în plus, puterea de atingere a lui xm’ este mai mare decât a lui xj’ (orice vârf atins de la xj’ este atins și de la xm’ ). În consecință, coloana xm’ se găsește înaintea coloanei xj’ în matricea D', ceea ce înseamnă că elementul d’im=1 se află pe linia xi’, înaintea elementului d’ij=1. Această concluzie este însă absurdă prin ipoteză fiind precizat că d’ij=1 este primul element egal cu unu, de pe linia xi’. Ca urmare, un vârf intermediar, de forma xm’, nu poate exista în drumul de la xi’ la xj’: drurnul d(xi’, xj’) – (care sigur există) nu poate fi format decât dintr-un singur arc, (xi’, xj’). În mod asemănător se poate arăta că ultimul element egal cu unu, de pe o coloana xj’, a matricei D', corespunde la un arc în graf.

1.4. Metode pentru determinarea componentelor tare conexe ale unui graf orientat

O componentă tare conexă, a unui graf G, este determinată atunci când se cunoaște mulțimea M, a vârfurilor sale. Într-adevăr, componenta reprezentând un subgraf al grafului G, are drept arce toate arcele lui G, care au ambele extremități în mulțimea M, aceste arce putându-se deci determina cu ușurință dacă se cunoaște M. În cele ce urmează, cautăm o metodă pentru determinarea mulțimii M, a vârfurilor unei componente tare conexe, din care face parte un vârf fixat, xiX. Notăm această mulțime prin M(xi), componenta tare conexă corespunzătoare fiind C(xi). Este evident că, utilizând aceste notații, dacă vârfurile xi și xj fac parte din aceeași componentă tare conexă, avem C(xi) = C(xj), respectiv M(xi) = M(xj). Vom folosi în mod deosebit proprietatea aproape evidentă, că orice două vârfuri din G, care sunt mutual atinse, fac parte din aceeași componentă tare conexă (o justificare riguroasa a afirmației este ușor de făcut).

În cele de mai jos, facem raționamentul de deducere a metodei cerute, pe baza unui exemplu, anume vom căuta componenta tare conexă ce conține vârful x1, pe graful G din figura 1.4.1. Această componentă, notată cu C(xl), va conține toate vârfurile grafului G, mutual atinse cu x1 (conform proprietății menționate anterior) și numai pe acestea (conform definiției conexiunii tari). De aceea, vom determina separat următoarele două submulțimi de vârfuri ale grafului G:

– mulțimea vârfurilor atinse de la x1, pe care o vom nota cu V1.

– mulțimea vârfurilor ce ating pe x1, pe care o vom nota cu V’1.

Cu notațiile indicate, este clar că mulțimea vârfurilor mutual atinse cu x1 va fi dată de intersecția V1 V’1. Deoarece există și posibilitatea ca această intersecție să fie vidă, caz în care componenta tare conexă căutată este formată numai din vârful xl, vom scrie, în general, următoarea formulă de calculul a mulțimii vârfurilor componentei C(x1):

(i) M(xl) = V1 V’1 {x1}

Arătăm acum în ce mod se calculează submulțimile de vârfuri V1 și V’1,. Este cunoscut faptul că vârfurile atinse de la x1, în graful G, sunt indicate prin elementele egale cu unu, de pe linia x1, a matricei drumurilor. In tabelul 1.4.1 este scrisă matricea arcelor grafului G, sub care este calculată linia x1, din matricea drumurilor (cu ajutorul metodei prezentate anterior).

Tabelul 1.4.1

Această linie este notată cu V1, deoarece elementele egale cu unu, de pe ea, arată că vârfurile sunt atinse de la x1. Mai precis, deoarece există elemente egale cu unu, în dreptul tuturor coloanelor tabelului, putem scrie:

V1={x1, x2, x3, x4, x5, x6}.

Pornind de la coloana x1 a matricei A și efectuând operații analoage, doar pe coloane, obținem în dreapta tabelului o coloană suplimentară V’1, ale cărei elemente egale cu unu indică vârfurile ce ating pe x1, în graful G. Aceste calcule sunt efectuate, de asemenea, în tabelul 1.4.8, decurgând conform următoarei succesiuni de operații:

– mai întâi s-a scris, pe coloana V’1, elementul egal cu unu, din dreptul liniei x2, un astfel de element aflându-se inițial pe coloana x1,

– datorită elementului egal cu unu menționat, s-a adunat boolean la coloana V’1, coloana x2, această adunare aducând un nou element egal cu unu, în dreptul liniei x5.

– datorită noului element egal cu unu, apărut anterior, s-a adunat boolean la coloana V’1, coloana x2, ceea ce a adus un nou element egal cu unu, în dreptul liniei x1 (în dreptul liniei x2 exista element egal cu unu, deci aici nu se modifică nimic),

– adunarea booleană a coloanei x1, la coloana V’1, nu mai aduce modificări, ceea ce înseamnă că procesul descris mai sus a luat sfârșit,

– locurile rămase libere au fost completate cu zerouri.

Coloana V’1, calculată cu ajutorul operațiilor descrise mai sus, este egală cu prima coloană a matricei drumurilor, ceea ce justifică afirmația că elementele egale cu unu, de pe ea, indică vârfurile ce ating pe x1. Într-adevăr, dacă în graful G s-ar schimba sensurile tuturor arcelor, s-ar obține un alt graf G', a cărui matrice a arcelor este transpusă matricei A din tabelul 1.4.8. Datorită schimbării sensurilor, de pe arcele arborelui G, vârfurile atinse de la x1, în graful G', vor fi chiar vârfurile ce ating pe x1, în graful G, deci acestea se determină calculând prima linie a matricei drumurilor grafului G' (cu operațiile cunoscute, dar aplicate pe transpusa matricei A).

Din cele de mai sus, rezultă că V’1={x1, x2, x5} și prin urmare:

M(x1)=(V1 V’1) {x1}={x1, x2, x5}{x1}= {x1, x2, x5}

Componenta C(x1), pe care o vom nota pe scurt cu C1 (prima componentă tare conexă găsită), este reprezentată în figura 1.4.2. Această componentă a fost construită astfel:

– vârfurile ei sunt x1, x2, și x5, cele ce formează mulțimea M(x1),

– arcele ei sunt toate arcele grafului G, ce au ambele extremități în mulțimea M(x1).

Pentru a determin următoarea componentă tare conexă a grafului G, vom repeta procedeul pe subgraful lui G, cu vârfurile rămase în discuție, adică cu mulțimea de vârfuri: X – M(xl)= {x3, x4, x6}. Acest lucru se poate realiza pe același tabel, al matricei arcelor grafului G, adaugând linia suplimentară V2 și coloana suplimentară V2 (pentru găsirea celei de a doua componente, pe care, o vom nota cu C2), din tabel fiind suprimate liniile și coloanele corespunzătoare vârfurilor x1, x2 și x5. Se ajunge astfel la tabelul 1.4.2, se preiau calculele din vechiul tabel 1.4.1 și le prelungește în sensul indicat.

Tabelul 1.4.2

Pentru a nu strica claritatea tabelului, nu au fost șterse efectiv liniile și coloanele x1, x2, și x5, ci pe linia V2 și coloana V'2 au fost hașurate locurile corespunzătoare lor. Pentru calculul liniei V2 și al coloanei V'2, s-a pornit cu vârful x3 al grafului G(x1 și x2 au intrat în componența C1). Astfel, pentru linia V2, s-au făcut următoarele calcule:

– linia x3 a adus un singur element egal cu unu, în dreptul coloanei x4,

– adunarea booleană a liniei x4 a adus un nou element egal cu unu, în dreptul coloanei x6,

– adunarea booleană a liniei x6, nu a mai adus nici o modificare, locul rămas liber completându-se cu un zero.

Observația 1.4.1. Dacă prin adunarea booleană a unei linii ar trebui să fie adus un element egal cu unu pe un loc hașurat, nu ținem seama de el, coloana corespunzătoare din tabel fiind presupusă suprimată.

Din calculele efectuate, rezultă că: V2 = {x4, x6}. Pe de altă parte, pentru calculul coloanei V2, de la început coloana x3 nu aduce nici un element egal cu unu (cel din dreptul liniei x2 cade într-o regiune hașurată), deci locurile libere se completează cu zerouri și V’2=0. Aplicând o formulă asemănătoare cu formula (i), avem:

(ii) m(x3)=(V2 V’2){x3}={x3}

În consecință, C2, cea de a doua componentă tare conexă a grafului G este formată dintr-un singur vârf, x3 . În tabelul 1.4.2 este calculată și cea de a treia componentă tare conexă a lui G, prin eliminarea liniei și coloanei x3 (pe lângă cele eliminate anterior). Această componentă, notată cu C3, are următoarea mulțime de, vârfuri:

(iii) m(x4)= (V3 V’3){x4}={x4, x6}.

Observația 1.4.1. Într-un graf fără circuite, toate componentele tare conexe sunt formate din câte un singur vârf.

Calculul matricei arcelor grafului condensat. Să considerăm că graful G are k componente tare conexe, C1, C2, …, Ck,. Matricea A*, a grafului condensat G*, este o matrice pătrată de ordinul k, ale cărei linii și coloane corespund la componentele C1, C2, …, Ck , considerate ca vârfuri. Această matrice se deduce din matricea A, a arcelor grafului G, conform următoarelor proprietăți ușor de dedus (cititorul le poate intui sau justifica, imediat):

– linia Cs, s = 1, 2, …, k, din matricea A*, este suma booleană a liniilor din A, ce, corespund la vârfurile ce intră în componența componentei tare conexe Cs,

– coloana Ct t=1, 2, …, k, din matricea A*, este suma booleană, a colonelor din A, ce, corespund la vârfurile ce intră în componența componentei tare conexe Ct,

– matricea A* are în mod obligatoriu, toate elementele de pe diagonala principală egale, cu zero (dacă apare vreun element egal cu unu, pe această diagonală el se înlocuiește cu unu).

Evident, în calculul practic al matricei A*, matricea A se condensează – în modul indicat – mai întâi pe linii, apoi pe coloane (sau invers). Exemplul ce urmează va lămuri complet cele descrise mai sus.

Exemplul 1.4.1. Pentru graful din figura 1.4.1, a cărui matrice a arcelor, este cea din tabelul 1.4.1 și ale cărui componente au fost calculate în exemplul precedent, calculul matricei A se face în trei etape, dupa cum urmează. Mai întâi, se calculează, matricea dreptunghiulară A. din tabelul 1.4.3, ale cărei linii corespund la componentele tare conexe C1, C2 și C3, iar ale cărei coloane corespund la vârfurile grafului G. Linia C1 a fost calculată ca suma booleană a liniilor x1, x2 și x5 din matricea A(x1, x2 și x5 fiind vârfurile ce intră în componenta C1). Linia C2 coincide cu linia x3 din matricea A, x3 fiind singurul vârf din componenta C2. În sfârșit, linia C3 a fost calculată ca suma booleană a liniilor x4 și x6 din matricea A.

Tabelul 1.4.3.

În cea de a doua etapă, se procedează asemănător pe coloane, dar asupra matricei , ceea ce conduce la matricea , din tabelul 1.4.4., de data aceasta o matrice pătrată, ale cărei linii și coloane corespund la componentele C1, C2 și C3.

Tabelul 1.4.4.

Astfel, coloana C1 din matricea este suma booleană a coloanelor x1, x2 și x5, din matricea , coloana C2 din coincide cu coloana x3 a matricei , iar coloana C3 din este suma booleană a coloanelor x4 și x6 din .

În final, cea de a treia etapă constă în înlocuirea celor două elemente egale cu unu, de pe diagonala principală a matricei , prin zero, ceea ce conduce la matricea arcelor grafului condensat G, din tabelul 1.4.5.

Tabelul 1.4.5

Încheiem prezentarea noțiunilor generale despre grafuri, cu o proprietate a grafului condensat.

Teorema 1.4.1. Graful condensat, corespunzător unui graf orientat oarecare, este un graf fără circuite.

Justificarea acestei proprietăți rezultă din următoarea observație simplă: dacă în G*, există arcul (C’, C’’) atunci în G există drum de la orice vârf xi C’, spre orice vârf xjC’’. Într-adevăr, există în G*, a arcului (C’,C’’), arată, conform definiției grafului condensat, că G conține un arc (xs, xt ), cu xs în componenta C' și xt în componenta C”. Dar în C' și C’’ existând legături prin drumuri între orice vârfuri interne lor, există drumuri de forma d(xi, xs) și d(xt, xj), care se pot lega între ele prin intermediul arcului (xs, xt), conducând la un drum d(xi ,xj) figura I.4.2.

Conform observației de mai sus, existența unui circuit în graful condensat ar însemna că două vârfuri, xi și xj, ce fac parte din două vârfuri distincte ale lui G*, de pe acel circuit, sunt mutual atinse, ceea ce nu se poate (cele două componente, presupuse vârfuri distincte ale lui G*, s-ar contopi într-una singură).

1.5. Aplicații

Aplicația 1.5.1. Cele cinci puncte de lucru importante dintr-o secție sunt legate printr-un sistem de benzi transportoare. Asociem situației din secție un model-graf G=(V, E) în care vârfurile x1, x2, x3, x4 și x5 reprezintă cele cinci puncte de lucru, iar arcul (xi, xj)E reprezintă banda transportoare care duce piesele din xi către xj. Fie G graful din figura 1.5.1. Să se analizeze situația din secție cu ajutorul matricei arcelor A, indicând cum poate fi folosit un astfel de sistem de benzi, pentru un proces de fabricație ce trece prin toate cele cinci puncte.

Rezolvare. Matricea arcelor grafului G este prezentată în tabelul 1.5.1. La această matrice s-au atașat o linie și o coloană suplimentare, în care s-au calculat respectiv sumele pe coloane și sumele pe linii.

Tabelul 1.5.1

În partea dreapta a matricei, se găsesc deci gradele exterioare de incidență ale vârfurilor, iar în partea de jos a aceleiași matrice se găsesc gradele interioare ale acestor vârfuri. Se observă că gradul interior de incidentă a vârfului x3 este nul (g3-= 0), ceea ce înseamnă că procesul de fabricație trebuie să pornească din punctul de lucru x3, (aici nu sosește nici o bandă transportoare). Pe de altă parte, gradul exterior de incidență a vârfului x5 este nul (g5-= 0) ceea ce înseamnă că procesul de fabricație trebuie să se termine în punctul de lucru x5. În plus, prin observații directe, se poate găsi că procesul de fabricație trebuie să străbată succesiv punctele x3, x2, x1, x4, x5.

Aplicația 1.5.2. Un anumit produs poate fi fabricat într-o secție a unei întreprinderi, prin mai multe procedee tehnologice, folosind unele materii prime și trecând prin diverse tipuri de produse intermediare (semifabricate). Fie G=(V, E) un graf, în care X={xI, x2, …, x8} este mulțimea materiilor prime ce se pot folosi și a produselor intermediare respective (numite împreună mai scurt stări de prelucrare), iar E mulțimea posibilităților de trecere de la o stare de prelucrare la alta. Mai precis, (xi, xj)E, dacă starea de prelucrare xi (eventual împreună cu alte stări din mulțimea V) poate conduce, printr-o operație de prelucrări, la starea xj. Fie graful G, cel din figura 1.5.2.

a) Să se cerceteze posibilitățile de trecere între diferitele stări de prelucrare indicate în problemă.

b) Să se arate la ce stări de prelucrare se poate ajunge, pornind de la fiecare dintre stările de prelucrare presupuse în problemă.

c) x8 fiind starea finală (produsul finit), să se arate de la ce stări se poate ajunge la aceasta, conform condițiilor date de problemă.

Rezolvare. a) Matricea arcelor grafului G este calculată în tabelul 1.5.2.

Tabelul 1.5.2

Pornind de la această matrice și prin aplicarea metodei descrise în acest paragraf, s-a calculat matricea drumurilor din tabelul 1.5.3. Ea arată toate posibilitățile de trecere, între diferitele stări de prelucrare, indicate în problemă. Astfel, dacă elementul dij,i=1, 2, …, 8; j = 1, 2, …, 8, este egal cu unu, atunci există cel puțin o posibilitate de trecere de la starea xi la starea xj. În caz contrar, dacă , dij= 0, nu se poate trece de la starea xi la starea xj. Astfel, de pildă, deoarece d28 = 1, există posibilitatea trecerii de la starea x3 la starea x8. Prin observații directe, cititorul poate găsi următoarele trei drumuri de la x3 la x8; d1=(x3, x5, x7, x8), d2=( x3, x4, x6, x8), d3=( x3, x4, x7, x8).

Tabelul 1.5.3

b) Elementele egale cu unu din matricea D, ce se află pe o linie xi, arată la ce stări se poate ajunge pornind de la starea xi. În plus, puterile de atingere, calculate în partea dreaptă a matricei D, ca sume, ale elementelor de pe liniile respective, arată la câte stări se poate ajunge, pornind de la fiecare stare în parte.

c) Elementele egale cu unu, de pe coloana x8 a matricei drumurilor, arată de la ce stări se poate ajunge la starea finala x8. După cum se observa din tabelul 1.5.3, la starea finală se poate ajunge de la orice stare de prelucrare, menționată în problemă.

Aplicația 1.5.3. Șapte puncte, de lucru ale unei secții, ce folosese curent electric și alternativ, pot fi alimentate prin racordarea la rețea, folosind unele din legăturile posibile, reprezentate prin muchii în graful neorientat G, din figura 1.5.3. Să se determine una dintre posibilitățile de legare a punctelor de lucru, astfel încât toate să poată funcționa și nefolosind legături de prisos. În condițiile puse de problemă, există tipuri de legare a punctelor de lucru, care sa folosească mai puține sau mai multe legături între perechile de puncte?

Rezolvare. Trebuie construit un arbore-acoperire al grafului G. Pentru aceasta, vom considera toate cele șapte vârfuri, x1, x2, …, x7, drept vârfuri ale arborelui căutat, dar dintre muchii selectăm numai n – 1 = 7 – 1 = 6, muchii, ca în exemplul ce urmează.

Să pornim, de pildă, cu muchia [x1, x2]. Următoarea muchie, pe care o solicităm, va avea una din extremități în x1 sau în x2 (pentru conexiune): fie să selectăm pe [x2, x3]. La a treia selecție, vom evita alegerea muchiei [x1, x3], care ar închide un ciclul, să alegem, spre exemplu, muchia [x3, x4].

Evitând, de fiecare dată, alegerea unei muchii ce închide un ciclu, să presupunem că au fost alese succesiv următoarele muchii, de la a patra selecție în sus: [x4, x5], [x3, x6], [x4, x7]. Se observă că, la subgraful obținut, nu se mai poate adăuga nici o muchie, fără, să se închidă un ciclu, deci că s-a obținut un arbore-acoperire (vezi figura 1.5.4). Aceasta este una dintre soluțiile posibile ale problemei. În practică, alegerea diferitelor muchii ce se adaugă, se face conform unor criterii economice, ce vor fi prezentate.

În ceea ce privește numărul de muchii, ce trebuie selectate, pentru a forma un arbore-acoperire al lui G, acesta este mereu același, anume egal cu n – 1 = 6.

CAPITOLUL 2

DRUMURI MINIME-MAXIME ÎN GRAFURI

2.1. Transport pe drumuri minime-maxime

În practica economică apar multe probleme ce se pot rezolva folosind modele grafuri în care urmează să determinăm anumite drumuri de valori minime (sau maxime). În acest sens, dăm, în cele ce urmează, un exemplu.

Exemplul 2.1.1. Să presupunem că pentru transportul unui produs, între două localități, se poate utiliza o rețea de șosele, în cadrul căreia există mai multe posibilități de alegere a rutei pe care urmează să se efectueze acest transport. Rețeaua în cauză este reprezentată printr-un graf ponderat, ale cărui vârfuri sunt localități intermediare prin care se poate trece, iar ale cărui arce (muchii) sunt șoselele ce leagă localitățile respective, Ponderile (valorile) de pe arce pot reprezenta costurile unitare de transport de-a lungul acestor șosele sau alți indicatori legați de folosirea șoselelor. Evident, probleme asemănătoare de transport se pot pune și rezolva în cadrul unor sisteme de dimensiuni mai mici, ca spre exemplu în rezolvarea unor probleme de transport intern al unei întreprinderi, secții etc.

Observația 2.1.1. Și de această dată putem avea situații când rezolvăm prin metode asemănătoare (cu ajutorul determinării drumurilor de valori minime în grafuri) probleme ce nu sunt de transport, dar ale căror modele matematice coincid cu ale acestora.

În continuare vom arăta în ce constă problema determinării drumurilor de valori minime (respectiv maxime) într-un graf. Astfel, fiind dat un graf ponderat, G=(V, E , w), având vârfurile x1, x2, …, xn, să considerăm două vârfuri fixate ale sale, de exemplu x1 și xn, (x1 este localitatea de plecare, iar xn, este localitatea de destinație a transportului). Graful G conține mai multe drumuri de la x1. la xn, (cazul când există un singur drum de acest fel este banal). Să notăm aceste drumuri prin:: d1(x1, xn), d2(x1, xn), d3(x1, xn), …, dk(x1, xn). Fiecărui drum, dintre acestea, îi corespunde câte o valoare, egală cu suma valorilor arcelor ce îl compun (conform definiției date în paragraful precedent). Problema cercetată. cere ca, dintre drumurile menționate, să ne oprim la acela (sau acelea) cu valoarea cea mai mică. Notând un astfel de drum prin ds(x1, xn ), putem scrie deci definiția lui astfel:

w[ds(x1, xn )] = {w[di(x1, xn )}.

Analog, dintre cele k drumuri de la x1 la xn, unul (sau mai multe) are valoarea cea mai mare. Notând un drum de valoare maximă de la x1 la xn, prin dt(x1, xn), definiția lui poate fi scrisă astfel:

w[dt(x1, xn )] = {w[di(x1, xn )}.

Observația 2.1.2. Vom nota, prin convenție, valoarea minimă drumurilor de la x1 la xn, cu m1n, iar valoarea maximă a acestor drumuri cu M1n. În general, considerând două vârfuri oarecare ale grafului, xiX și xjX, convenim să notăm:

mij = valoarea minimă a drumurilor de la xi la xj

Mij= valoarea maxima a drumurilor de la xi la xj.

Observația 2.1.3. Uneori, vom mai numi valoarea minimă (maximă) a drumurilor dintre xi și xj, distanța minimă și maximă) între cele două vârfuri.

Exemplul 2.1.2. Fie graful ponderat din figura 2.1.1, valorile arcelor fiind scrise pe arce. Ne propunem să găsim, prin enumerare (cercetarea directă a tuturor posibilităților), drumul (drumurile) de valoare minimă, respectiv maximă, între vârfurile x1 și x6.

Se poate observa cu ușurință, cercetând graful din figura 2.1.1, că există în acest graf șase (drumuri de la x1 la x6, și anume următoarele:

d1(x1, x6)= (x1, x2, x4, x6) ; d2(x1, x6)= (x1, x2, x4, x3, x5, x6) ;

d3(x1, x6)= (x1, x2, x5, x6) ; d4(x1, x6)= (x1, x3, x5, x6) ;

d5(x1, x6)= (x1, x4, x6) ; d6(x1, x6)= (x1, x4, x3, x5, x6) .

Valorile acestor șase drumuri se calculează după cum urmează:

w[d1(x1, x6)]= w(x1, x2)+ w(x2, x4)+ w(x4, x6)= 2+4+7=13,

w[d2(x1, x6)]=w(x1, x2)+w(x2, x4)+w(x4, x3)+w(x2, x5)+w(x5, x6)= 2+4+3+1+2=12,

w[d3(x1, x6)]= w(x1, x2)+ w(x2, x5)+ w(x5, x6)= 2+4+2=8,

w[d4(x1, x6)]= w(x1, x3)+ w(x3, x5)+ w(x5, x6)= 6+1+2=9,

w[d5(x1, x6)]= w(x1, x4)+ w(x4, x6)= 2+7=9,

w[d6(x1, x6)]= w(x1, x4)+ w(x4, x3)+ w(x3, x5)+ w(x5, x6)= 2+3+1+2=8.

Valoarea minimă a drumurilor de la x1 la x6, este deci:

m16= min{1 3; 12; 8; 9; 9; 8} = 8,

această valoare fiind atinsă pentru două drumuri dintre cele șase. Există deci două drumuri de valoare minimă (ambele cu valoarea egală cu opt) și anume d3(x1, x6) și d6(x1, x6). Dacă nu am fi scris și numerotat toate drumurile de la x1, la x6, aceste două drumuri ar fi putut fi scrise – prin convenție și astfel:

d’min(x1, x6) =(x1, x2, x5, x6); d"min(x1, x6) =(x1, x4, x3, x5, x6).

Analog, valoarea maximă a drumurilor de la x1 la x6 este:

M16= max{1 3; 12; 8; 9; 9; 8} = 13,

ea fiind atinsă numai pentru drumul d1(x1, x6), care este deci singurul drum de valoare maximă de la x1 la x6. Putem scrie:

dmax(x1, x6) =(x1, x2, x4, x6)

Observația 2.1.4. Drumurile de valoare minimă (respectiv maximă) dintr-un graf vor fi denumite pe scurt drumuri minime respectiv maxime în graf. Se mai folosește o denumire unitară, de drumuri optime, natura optimului (maxim sau minim) rezultând din contextul economic al problemei rezolvate. În același sens, vom folosi și expresia de valoare optimă a drumurilor dintre două vârfuri ale unui graf.

Observația 2.1.5. Trebuie să facem distincție între două noțiuni și anume:

– valoarea optimă a drumurilor dintre două vârfuri ale unui graf, care este un număr;

– drumul (drumurile) de valoare optimă între cele două vârfuri, care reprezintă succesiunea (succesiunile) corespunzătoare de vârfuri.

În sensul acestor două aspecte ale problemei, va trebui să dăm metode de rezolvare pentru fiecare în parte.

Înainte de a începe rezolvarea problemelor puse, vom accentua asupra a două proprietăți importante, pe care le prezentăm sub forma a două observații, ținând seama de faptul că cele mai multe dintre grafurile ponderate cu care lucrăm au valori pozitive și finite pe arce.

Proprietatea 2.1.1 Într-un graf cu valori finite și pozitive pe arce, există drumuri de valori minime finite între oricare două vârfuri ale grafului, ce sunt legate prin cel puțin un drum. În plus, orice drum de valoare minimă între două vârfuri, ale unui astfel de graf, este elementar.

Prima parte a acestei proprietăți este evidentă, din moment ce între cele două vârfuri există cel puțin un drum, a cărui valoare este sigur finită și pozitivă. Partea a doua a afirmației făcute va fi justificată pe baza unui exemplu simplificat și anume asupra grafului cu circuite din figura 2.1.2, (pe un graf fără circuite afirmația este evidentă, în astfel de grafuri existând numai drumuri elementare). Astfel, fie drumul neelementar d1(x1, x5)=(x1, x2, x3, x4, x2, x5), de valoare egală cu 16; el este neelementar, trecând de două ori prin vârful x2. Se observă cu ușurință că un astfel de drum (neelementar) trebuie să conțină un subdrum (o parte din drum), sub forma unui circuit, în cazul nostru (x2, x3, x4, x2). Eliminând din drumul d1(x1, x5) circuitul menționat se obține cu ușurință un alt drum de la x1 la x5, drum de forma d2(x1, x5)= (x1, x2, x5) a cărui valoare este mai mică decât valoarea lui d1(x1, x5), cu cinci unități (valoarea circuitului eliminat din drumul inițial). Modificările indicate ajută cu atât mai mult când drumul de la care se pornește trece de mai multe ori printr-un vârf, caz în care repetăm de câte ori se poate eliminarea unui circuit din drumul respectiv. Raționamentul descris ne convinge că un drum neelementar nu poate avea valoare minimă, existând totdeauna un alt drum, de valoare mai mică decât el, între aceleași vârfuri ale grafului.

Reținem, din justificarea făcută mai sus, o proprietate mai generală, ce rezultă cu ușurință și anume că:

Observația 2.1.6. Orice metodă de căutare a drumurilor de valori minime, între vârfurile unui graf cu circuite evită de la sine introducerea în aceste drumuri a circuitelor cu valori pozitive.

Proprietatea 2.1.2. Într-un graf cu circuite, în care există circuite cu valori pozitive, există vârfuri între care putem obține drumuri cu valori oricât de mari. În acest sens, problema determinării drumurilor de valoare maximă, între vârfurile respective, își pierde sensul. Dăm ca exemplu graful din figura 2.1.2, ce conține circuitul (x2, x3, x4, x2), de valoare egală cu cinci unități și în care putem scrie următorul șir de drumuri de la x1 la x5 cu valori din ce în ce mai mari:

d1(x1, x5)= (x1, x2, x5), de valoare egală cu 11,

d2(x1, x5)= (x1, x2, x3, x4, x2, x5), de valoare egală cu 16,

d3(x1, x5)= (x1, x2, x3, x4, x2, x3, x4, x2, x5), de valoare egală cu 21,

……………………………………………………………………….

Este clar că putem repeta circuitul (x2, x3, x4, x2), în drumul cerut, de câte ori este nevoie, pentru a obține un drum de valoare oricât de mare; acesta este echivalent cu a spune că, deși vârfurile x1 și x5, sunt legate prin drumuri, nu există un drum cu valoarea maximă între aceste vârfuri.

Observația 2.1.7. Într-un graf cu circuite pozitive nu are rost să căutăm drumurile de valori maxime între diferitele vârfuri ale grafului.

Observația 2.1.8. Dacă valorile atașate arcelor grafului pot fi și negative, probleme analoage se pot pune în cazul când graful conține circuite de valori negative, dar cu următoarele rezultate:

– drumurile de valori maxime, între diferitele vârfuri ale grafului, există întotdeauna (evident dacă vârfurile respective sunt legate prin drumuri și nu există circuite cu valori pozitive); aceste drumuri de valori maxime evită includerea în ele a circuitelor negative, fiind deci elementare,

– drumurile de valori minime nu există pentru anumite perechi de vârfuri, deși vârfurile respective sunt legate prin perechi de drumuri, adică problema pusă își pierde sensul (există drumuri cu valori oricât de mici, evident negative).

În paragraful de față, ne vom referi numai la grafuri ponderate, ale căror valori de pe arce sunt pozitive. De asemenea, vom trata numai cazul drumurilor cu valori minime, indicând de fiecare dată cum se adaptează metodele descrise, în situația când se cer drumurile cu valori maxime.

Problemele practice, care conduc la modelele-grafuri pe care le folosim, pot duce la două tipuri de probleme de determinare a drumurilor cu valori minime, dintre care, prima reprezintă un caz particular al celeilalte și anume:

(i) Determinarea valorii minime, respectiv a drumului (drumurilor) cu valoarea minimă, intre două vârfuri fixate ale grafului.

(ii) Determinarea valorilor minime, respectiv a drumurilor cu valori minime, între oricare doua vârfuri ale grafului.

Rezolvarea uneia, sau celeilalte probleme, dintre cele două de mai sus, depinde evident de problema practică ce se rezolvă, de rezultatele ce se cer. Evident, problema (i) se va rezolva cu calcule mai puține, dar problema (ii) dă rezultate mai cuprinzatoare.

În ceea ce privește rezolvarea problemei (ii), ea se realizează cu ajutorul unei matrici pătrate de ordinul n(n = numărul vârfurilor din graf), pe care o notăm de obicei cu M și o numim matricea valorilor minime ale drumurilor dintre oricare două vârfuri ale grafului. Mai precis, notând cu mij elementul matricei M, ce se află la intersecția liniei xi cu valoarea xj, avem:

Observația 2.1.9. Pentru elementul mij, linia în care se găsește el arată plecările de drumuri minime, iar coloana arată sosirile acestor drumuri minime.

Pentru problema analoagă, a determinării matricei valorilor maxime ale drumurilor din graf, vom nota ou M această matrice, iar cu Mij elementul de pe linia xi și de pe coloana xj a acestei matrice, definit astfel:

Metodele de rezolvare a problemelor (i) și (ii) folosesc așa-numita matrice a valorilor, notată cu W. Această matrice este o matrice pătrată de ordinul n, al cărei element wij, de pe linia xi și de pe coloana xj, se definește astfel:

Observația 2.1.10. În cazul când i j și graful nu conține arcul (xi, xj), se pune wij=, în cazul problemei de drumuri minime și wij= -, în cazul problemei de drumuiri maxime.

Observația 2.1.1.1. Pentru cazul unui graf neorientat, notațiile de mai sus rămân valabile, dar transformând mai întâi acest graf într-unul orientat, prin înlocuirea fiecărei muchii [xi , xj] cu două arce de sens contrar,(xi,xj) și (xj,xi),cu aceeași valoare (egală cu valoarea muchiei corespunzătoare).

Exemplul 2.1.3. Fie graful orientat G, din figura 2.1.3, valorile arcelor fiind scrise pe arce. Matricea valorilor acestui graf, scrisă în scopul rezolvării, problemei de drumuri minime, este cea din tabelul 2.1.1 Se observă că toate elementele de pe diagonala principală sunt egale cu zero, În locurile corespunzătoare arcelor existente în graf se găsesc valorile acestor arce, iar celelalte elemente sunt infinite.

De exemplu: w12 = 3, deoarece graful conține arcul (x1,x2), cu valoarea trei, dar w21=, deoarece graful nu conține arcul (x2,x1). Dacă matricea valorilor ar fi fost scrisă în scopul determinării valorilor drumurilor maxime, ea ar fi diferit de cea din tabelul 2.1.1 doar prin faptul că în locul elementelor egale cu , ar fi fost –

Tabelul 2.1.1

Prin cercetare directă, ne putem convinge că matricele valorilor minime, respectiv maxime, ale drumurilor (între oricare doua vârfuri ale grafului G, sunt cele din tabelele 2.1.2 și 2.1.3.

Tabelul 2.1.2.

Tabelul 2.1.3.

Exemplul 2.1.4. Graful neorientat din figura 2.1.4 a, poate fi înlocuit cu graful orientat din figura 2.1.4 b, a cărei matrice a valorilor este cea din tabelul 2.1.4. Evident, în graful dat se poate pune numai problema determinării valorilor minime ale drumurilor dintre oricare două vârfuri.

Tabelul 2.1.4

Deoarece problemele (i) și (ii) nu se pot rezolva cu ușurință prin cercetare directă, la grafuri de dimensiuni mari, este nevoie să folosim unii algoritmi în acest sens, algoritmi ce vor fi prezentați în cele ce urmează. La baza acestora stă principiul de optimalitate al lui Bellman, care este un principiu general în matematică și care aplicat la problema noastră se enunță astfel:

“Orice drum optim în graf este format din subdrumuri optime din acel graf".

Vom ilustra aplicarea acestui principiu în cadrul descrierii fiecărui algoritm de drum optim în parte.

În cele ce urmează, prezint doi dintre algoritmii de tipul (i). Ei vor da, pe lângă valoarea minimă a drumurilor dintre cele două vârfuri specificate și alte valori minime analoage, ce nu se cer în problemă.

2.2. Algoritmi pentru determinarea drumurilor minime

2.2.1. Algoritmul Bellman-Kalaba

Fie G=(V, E, w), unde V={x1, x2, …, xn}, un graf orientat. Interesează găsirea valorilor minime ale tuturor drumurilor de la fiecare vârf al grafului, xi (i =1, 2, …, n), la un anumit vârf fixat, fie acesta xn(dacă vârful fixat este altul decât xn, îl trecem pe ultimul loc). Pornim cu matricea W=.

Fie valoarea minimă a drumurilor formate din cel mult k arce, între xi și xn și fie valoarea minimă a tuturor drumurilor de la xi la xn, indiferent de numărul de arce.

Teorema 2.2.1.1. Fie G = (V, E, w), V = {x1, x2, …, xn} un graf orientat ponderat și xn un vârf fixat. Atunci:

pentru in.

Demonstrație. Evident, orice drum de valoare minimă de la xi la xn, format din cel mult k + 1 arce trebuie să fie format dintr-un arc (xi, xj), i j și un drum de la xj la xn, de cel mult k arce, care trebuie să aibă valoarea minimă față de toate celelalte drumuri formate din k arce de la xj la xn (conform principiului de optimalitate al lui Bellman).

Teorema 2.2.1.2. Fie G = (V, E, W), V = {x1, x2, …, xn} un graf orientat ponderat și xn, un vârf fixat. Dacă () kN, astfel încât oricare ar fi vârful xi, să avem:

=, atunci =, () xiX.

Demonstrație. Dacă vârfurile xi și xn, sunt fixate și două numere naturale k, pN sunt în relația kp, atunci evident . Trebuie arătat că, în condițiile teoremei: = , sN. Acest lucru se arată prin inducție matematică, după valorile numărului natural s.

Verificarea, este imediată pentru s =1, fiind chiar relația din enunț.

În etapa de demonstrare, presupunem adevărată relația =, pentru un s oarecare și trebuie să arătăm că este adevărată relația:

=.

Dar, aplicând rezultatul teoremei 2.2.1.1, avem:

== = , pentru xixn.

În acest șir de egalități am aplicat, de asemenea, ipoteza de inducție și condiția dată în enunțul teoremei.

Dacă xi = xn, proprietatea este evidentă.

Pe aceste teoreme se bazează algoritmul Bellman Kalaba, conținând următoarele etape:

Pas 1. Se construiește matricea valorilor W, corespunzând grafului ponderat dat.

Pas 2. Se atașează noi linii în partea de jos a matricei W, notate , ,… care dau valorile minime ale drumurilor formate din 1, 2, …, arce de la oricare vârf xi la vârful xn, fixat și anume:

a) Linia conține valorile minime ale drumurilor de la oricare vârf xi la xn, formate dintr-un singur arc deci conține valorile arcelor incidente interior lui xn. Aceste valori vor fi date, evident, de coloana lui xn, din matricea W.

b) Presupunând completată o linie oarecare se trece la calculul liniei , pe baza relației dată de teorema 2.2.1.1, pentru fiecare element în parte pentru in, dar evident adevărată și în cazul poziției diagonale când unul din arce este considerat degenerat (de valoare zero).

Evident =0, pentru orice k N

c) Atașarea liniilor continuă pentru k n – 1 până când =, și deci, conform teoremei 2.2.1.2, s-au obținut aici tocmai valorile minime căutate, indiferent de numărul de arce străbătute.

Pas. 3. Se determină efectiv vârfurile și arcele din drumul minim de la xi la vârful fixat xn, astfel: adunăm element cu element linia xi din W cu linia , căutând cea mai mică valoare a sumei. Presupunem că wii1+=. Atunci, evident, arcul (xi, xi1) este primul arc din drumul minim căutat. Când suma minimă se obține în dreptul mai multor coloane, atunci există mai multe drumuri corespunzând valorii minime și se urmărește până la capăt fiecare variantă în parte.

Analog se adună linia xi cu linia căutând arcul care asociat unui drum minim de la vârful atins la xn, să dea valoarea găsită anterior. Se determină astfel al doilea arc (xi1, xi2) din succesiunea căutată, procedând la fel până se află un arc cu vârful xn, extremitate terminală. Rezultă drumul de valoare minimă, unic sau nu, de forma (xi, xi1, xi2, …, xip, xn).

Observația 2.2.1.1. Algoritmul se poate aplica și în cazul determinării valorilor maxime ale drumurilor, înlocuind peste tot minimul prin maximum și luând în considerare matricea W corespunzătoare (eu – în loc de +).

Exemplul 2.2.1.1. Fie graful orientat din figura 2.2.1.1, arcele fiind căi de transport între diferitele puncte, iar valorile, scrise pe arce reprezentând costurile unitare de transport de-a lungul arcelor corespunzătoare se cere drumul pe care să se facă transportul, între x1 și x6, încât cheltuielile să fie minime. Trebuie aflată deci, mai întâi, valoarea minimă a drumurilor de la x1 la x6, precum și drumul (drumurile) ce realizează această valoare minimă.

Matricea valorilor, W, a grafului dat, este scrisă în .tabelul 2.2.1.1. Sub acest tabel, în continuarea matricei W, sunt calculate cinci linii suplimentare, ce sunt explicate parțial în continuare.

Tabelul 2.2.1.1.

Linia notată cu corespunde cu coloana x6 a matricei W, fiind însă transpusă. Elementele liniei au fost calculate succesiv astfel:

=min{0+; 3+; 7+1; +7; +6; +0}=8,

=min{+; 0+; +1; 2+7; +6; +0}=9,

=min{+; 1+; 0+1; +7; 2+6; 1+0}=1,

=min{+; 3+; 1+1; 0+7; +6; 7+0}=2,

=min{+; +; +1; 1+7; 0+6; 6+0}=6,

=min{+; +; +1; +7; +6; 0+0}=0,

Asemănător, au fost calculate celelalte linii suplimentare. Deoarece liniile și sunt identice, calculul acesta s-a oprit la linia ; primul element al acestei linii, încadrată în tabelul 2.2.1.1, reprezintă valoarea minimă a drumurilor de la x1 la x6: = 7.

Pentru a determina drumul (drumurile) ce realizează această valoare, procedăm astfel:

a) Printre sumele elementelor de pe linia x1, cu elementele corespunzătoare ale liniei , cea mai mică este egală cu 7 și se atinge pentru valoarea w12 = 3; înseamnă că primul arc al drumului căutat este (x1, x2).

b) Printre sumele dintre elementele corespunzătoare ale liniilor x2 și , cea mai mică este egală cu 4 și se atinge pentru valoarea w24=2; înseamnă că al doilea arc al drumului minim este (x2, x4).

c) Printre sumele elementelor corespunzătoare ale liniilor x4

și , cea mai mică este egală cu 2, atinsă pentru w43=1; cel de al treilea arc al drumului minim este deci (x4, x3)

d) Printre sumele elementelor corespunzătoare ale liniilor x3 și , cea mai mică este egală cu unu și este atinsă pentru w36=1; ultimul arc al drumului minim este deci (x3, x6).

Din cele de mai sus, rezultă că drumul de valoare minimă, de la x1 la x6; este unic și anume: d = (x1, x2, x4, x3, x6), având o valoare de șapte unități. Pe acest drum, urmează. să se organizeze transportul de la x1 la x6.

2.2.2. Algoritmul lui Yen

Pentru calculul valorilor minime de la un vârf al grafului fixat, fie acesta x1, la celelalte vârfuri, x2, x3, …, xn, din G, adica m12, m13, …, m1n, se poate proceda și astfel:

Pasul 1. Se scrie matricea valorilor W și se determină cea mai mică dintre valori, care pleacă din x1. Fie:

w1i0=, deci w1i0=m1i0.

Pasul 2. Toate elementele din prima linie a matricei W, exceptând w11=0 și w1i0, se transformă astfel: .

Din matricea astfel obținută, se suprimă linia de rang i0 și coloana de rang i0, păstrând pentru celelalte linii și coloane, rangurile lor inițiale. Dacă matricea obținută este de ordinul 2, atunci w12 din această matrice reprezintă valoarea minimă de la x1 la xk, unde k este rangul coloanei a doua (liniei a doua) din această matrice și algoritmul ia sfârșit. Dacă matricea obținută are cel puțin ordinul trei, atunci se repetă pași 10 și 20 asupra acestei matrici, ca și asupra matricei W, cu prima linie a acestei matrici.

Fiecare etapă de aplicare a algoritmului în cei doi pași scade ordinul matricei cu câte o unitate și dă la fiecare etapă câte o valoare minimă mli(i =1, 2, 3, …, n).

Justificarea algoritmului. În primul pas al primei, etape de aplicare a algoritmului w1i0=, deoarece, orice drum de valoare minimă de la x1 la xi0 trebuie să înceapă cu un arc incident exterior lui x1, deci valoarea sa este cel puțin egală cu valoarea celui mai scurt arc de forma (x1, xi0) care este în particular un drum de la x1 la xi0.

După, o etapă a algoritmului, se obține o matrice corespunzând unui subgraf G1=(V1, E1) al lui G, unde V1=V\{xi0}. Vom arăta cum se determină valorile minime de la x1 la xi (cu i i0) în graful G. Fie un vârf oarecare ,xixi0. Există două posibilități, pe care le cercetăm în continuare.

Cazul 1. In graful G există un drum de la x1 la xi care nu trece prin xi0, fie aceasta d=(x1, xj1 , xj2, …, xi) un drum minim. Rezultă că wij1w1i0+wi1j0, deoarece în caz contrar am putea înlocui arcul (x1, xj1) printr-un drum format din două arce, (x1, xi0) și (xi0, xj1) și care este mai scurt, contrazicând ipoteza. Prin înlocuirile de la pasul 20, elementul w1j1, din W rămâne neschimbat, deci valoarea drumului (x1, xj1 , xj2, …, xi) este aceeași în G și G1. În graful G1 însă, nu pot exista distanțe mai mici de la x1 la xi, cu ii0, deoarece oricărui drum (x1, xj1 ,…, xjs, xi) din G1 îi corespunde în G același drum, dacă w1j1 w1i0+wi0j1, sau îi corespunde drumul (x1, xi0, xj1 ,…, xjs, xi) din G dacă w1j1 w1i0+wi0j1 cu valoare egală. Deci distanțele minime se conservă în G și G1.

Cazul 2. În graful G, orice drum minim de la x1 la xi trece prin xi0. Fie un astfel de drum: d(x1, xi) = (x1, xj1, xj2, …, xi0, xk1, xk2, …, xi).

Deoarece valoarea arcului (x1, xi0) este mai mică sau egală cu valoarea arcului (x1, xj1), rezultă că și drumul:

d1(x1, xi) = (x1, xi0, xk1, xk2, …, xi)

este un drum de valoare minimă de la x1 la xi în G, în care xi0 nu mai apare încă odată între xk1, xk2, …, xi . Există evident relația: w1k1>w1i 0 + wi0k1, deoarece în caz contrar și drumul d”(x1, xi) = (x1, xk1, xk2, …, xi) este drum de valoare minimă în G de la x1 la xi și nu trece prin xi, contrazicând ipoteza.

În pasul 2 al algoritmului Yen s-a înlocuit w1k1 prin: w1i0 + wi0k1, deci valoarea drumului d1 în G este egală cu valoarea drumului d” în G1, deci se conservă distanțele minime și în acest caz.

Exemplul 2.2.2.1. Fie graful orientat din figura 2.2.2.1, ce reprezintă posibilitățile de transport al unui produs, între punctele x1, x2, x3, x4 și x5. Valorile de pe arce reprezentând costurile transportului pe arcele respective, să se determine drumul de la x1 la x5, încât costul total de transport să fie minim.

Matricea valorilor grafului este cea din tabelul 2.2.2.1. Avem: m11=0 și {3, , , 2}=2, deci xi0=x5 și m15=2, iar drumul este d(x1, x5)=(x1, x5).

Tabelul 2.2.2.1

Apoi, se suprimă din tabelul 2.2.2.1. linia și coloana corespunzând vârfului x5, ceea ce conduce la tabelul 2.2.2.2, în care s-au înlocuit elementele din prima linie ca la pasul 20 al algoritmului:

Tabelul 2.2.2.2.

Din prima linie a tabelului 2.2.2.2., se alege: min{3, , 5}=3, care corespunde vârfului x2. Avem deci m12=3 și d(x1, x2)= (x1, x2).

Acum se suprimă linia și coloana corespunzătoare lui x2 și modificăm elementele din prima linie a matricei din tabelul 2.2.2.2., cu formula de la pasul 20 a algoritmului:

Obținem tabelul 2.2.2.3, în care avem: m13=m14=5 și d(x1, x3)= (x1, x2, x3); d(x1, x4)= (x1, x5, x4).

Tabelul 2.2.2.3.

În general, la acest algoritm găsirea drumului minim se poate face așa cum se explică mai jos. Drumul cel mai scurt,de la xi la xj are lungimea mij, astfel că: mij=mik + wkj , dacă (xk, xj) este ultimul arc al drumului minim. Pentru distanța minimă mik de la xi la xk se procedează analog pentru găsirea ultimului arc al drumului. Dacă nu există nici un indice k cu proprietatea k i, k j care să verifice egalitatea: mij=mik + vkj, atunci singurul drum minim de la xi la xj este arcul: (xi, xj).

Observația 2.2.2.1. Pentru aflarea drumului de valoare maximă, se folosește inițial matricea W corespunzătoare și se alege de fiecare dată valoarea maximă de pe linia tabelului rămas.

În continuare, prezint trei algoritimi ce rezolva problemele (ii), deci care conduc la calcularea matricei M, a valorilor minime ale drumurilor dintre oricare doua vârfuri ale grafului.

2.2.3. Algoritmul Roy – Floyd

Fie G = (V, E, w), unde X={x1, x2, …, xn}.

Algoritmul Roy-Floyd determină atât valorile distanțelor minime între oricare două vârfuri ale grafului, cât și drumurile minime corespunzătoare și se bazează pe următoarea teoremă:

Teorema 2.2.3.1. Dacă, într-un graf oarecare G, este îndeplinită inegalitatea: wijwik+wkj, pentru orice i j, i k, j k, atunci valoarea minimă a drumurilor de la xi la xj este valoarea wij.

Demonstrație. Presupunem că există cel puțin un drum de valoare finită de la xi la xj, fie acesta:

d(xi, xj) = (xi, xk1, xk2, …, xk8, xj) și din ipoteza teoremei se deduce din aproape în aproape că:

wik2wik1+wk1k2,

wik3wik2+wk2k3 wik1+wk1k2 +wk2k3

………………………………………………………

wij wik1+wk1k2 + … +wksj.

de unde justețea concluziei teoremei.

Algoritmul pentru aflarea matricei M, a valorilor minime a drumurilor, are etapele următoare:

Pasul 1. Se asociază grafului matricea W = (wij), i, j=1, 2, …, n și matricea C Cij, i, j = 1, 2, …, n, unde Cij sunt mulțimi de noduri sau vârfuri din care pleacă arce, deci:

Pasul 2. Ținând seama de afirmația teoremei, se determină matricile Wk=wij(k) i,j=1, 2, …, n, k=1, 2, …, n în care se modifică valorile wij care nu satisfac teorema și deci se pot micșora, astfel:

În general, pentru k=2, 3, …, n, punem.

Analog se află matricile Ck, k=1, 2, …, n. Mai precis, elementele matricei Ck=║Cij(k)║, i, j = 1, 2, …, n, se află astfel:

cu convenția:

În final, WnM, iar Cn dă efectiv drumurile minime, ținând cont de mulțimile vârfurilor vecine cu fiecare vârf xj, date de elementele , reconstituind drumul în sens invers.

Exemplul 2.2.3.1. Fie graful din figura 2.2.2.1 folosit și în exemplul precedent. Trebuie să găsim costurile minime de transport, între oricare două puncte ale grafului. Cu alte cuvinte, trebuie să se determine matricea valorilor minime dintre vârfurile grafului și drumurile corespunzătoare acestor trasee optime. Matricile W și C, din primul pas al algoritmului, se găsesc în tabelele 2.2.3.1 și 2.2.3.1’.

Tabelul 2.2.3.1 Tabelul 2.2.3.1’

Aplicăm pasul 2 al algoritmului pe rând, pentru k = 1, 2, …, n. Avem succesiv rezultatele conținute în tabelele 2.2.3.2 -2.2.3.6’

Tabelul 2.2.3.2 Tabelul 2.2.3.2’

Tabelul 2.2.3.3 Tabelul 2.2.3.3’

Tabelul 2.2.3.4 Tabelul 2.2.3.4’

Tabelul 2.2.3.5 Tabelul 2.2.3.5’

Tabelul 2.2.3.6 Tabelul 2.2.3.6’

Să alegem câteva distanțe minime din tabelul Tabelul 2.2.3.6. – 2.2.3.6’

a) m14 = 5 și d(x1, x4)= (x1, x5, x4), citit pe prima linie din C5, reconstituind drumul de la sfârșit astfel: vârful x4 este precedat de x5 aflat în căsuța (1, 4), vârful x5 este precedat de x1 aflat în căsuța (1, 5), care este vârful inițial al dramului.

b) m25 = 4 și d(x2, x5)= (x2, x5), sau d(x2, x5)= (x2, x3, x5), deci două drumuri cu aceeași lungime minimă 4, aflate pe linia lui x2, din tabelul 2.2.3.6, ca mai sus.

c) m42 = 11 d(x4, x2)= (x4, x3, x5, x1, x2).

Drumurile aflate sunt cele pe care trebuie organizat transportul, între vârfurile corespunzătoare.

2.2.4. Algoritmul lui Dantzig

Algoritmul lui Dantzig este un procedeu de calcul recursiv pentru găsirea distanțelor minime în subgrafurile cu 2, 3, …, n vârfuri. În cazul în care funcția w:E R poate lua și valori negative, algoritmul poate detecta și eventualele circuite negative, a căror semnificație este că distanța între oricare două vârfuri poate fi făcută oricât de mică parcurgând circuitele respective de un număr de ori suficient de mare, deci nu există o cea mai mică distanță finită între vârfurile circuitelor.

Fie graful ponderat G = (V, E, w) și G(k) = (Vk, Ek, wk) subgraful lui G în care mulțimea vârfurilor este: Vk={x1, x2, …, xk}, kn. Fie, de asemenea, M(k)=║ ║, i,j=1,2, …,k, matricea distanțelor minime în subgraful G(k).

Pasul 1. Se face k = 2 și =w12; =w21. Dacă w12+w21<0 ne oprim, s-a detectat circuitul negativ (x1, x2, x1) și problema distanțelor minime în G își pierde sensul. În caz contrar, pentru w12+w210 se ia ==0 și se trece la pasul 20, succesiv pentru k = 3, 4, … , n.

Pasul 2. Cunoscând matricea M(k-1), se află elementele matricei M(k), prin recurență, astfel:

a) , pentru i=1, 2, …, k-1.

b) , pentru j=1, 2, …, k-1 .

Se verifică dacă există un indice i, anume 1 i k – 1, pentru care: < 0 și în acest caz ne oprim, existând un circuit negativ în subgraful cu mulțimea de vârfuri Vk care trece prin vârfurile xi și xk. În caz contrar, elementele de pe diagonală sunt egale cu zero și se calculează elementele:

c) pentru ij ; i,j=1, 2, …, k-1

La sfârșitul algoritmului, elementele dau distanțele minime în G, unde = 0, oricare ar fi i= 1, 2 , …, n și k= 2, 3, …, n. Dacă graful nu conține arce cu lungimea negativă, nu se mai verifică la pasul 20 existența circuitelor negative.

Justificarea algoritmului. Prin inducție după k, arătăm că valorile și date de formulele a), b), c) dau distanțele minime în subgrafurile cu mulțimile de vârfuri V2, V3, .., VnV (pentru k=2, 3, …, n, respectiv).

Pentru k=2, subgraful G(2) are numai două vârfuri, V2’ = {x1, x2} și distanțele minime între ele coincid cu distanțele directe (prin arce). Presupunând că nu există circuite negative, facem ipoteza că formulele sunt adevărate pâna la k – 1 și demonstrăm valabilitatea lor pentru G(k). Distanța minimă între un vârf xi(i = 1, 2, …, k – 1) și xk, în G este fie distanța directă wik, obținută din formula a) j = i, fie valoarea unui drum minim d(xi, xk,) = (xi, xk1, …, xks, xj0, xk), format cu vârfuri din Vk. Dar (xi, xk1, …, xks, xj0) este un drum minim în G(k-1), a cărui lungime este conform ipotezei de inducție, deoarece, în caz contrar, acest drum s-ar putea înlocui printr-un drum mai scurt de la xi la xj în G(k-1) și care prelungit cu arcul (xj0, xk) ar genera un drum mai scurt decât (xi, xk1, …, xks, xj0, xk), contrazicând ipoteza. Deci =adică formulele a) sunt adevărate pentru orice i = 1, 2, …, k-1.

Dacă ar există un indice i(1 i k – 1) pentru care +<0, atunci ar exista un circuit negativ care trece prin vârful xk în G(k), deci și în graful G.

Valabilitatea formulelor b) se face în mod asemănător. Pentru formulele c), considerăm un drum de valoare minimă de la xi la xj în subgraful G(k). Dacă acest drum nu trece prin vârful xk, atunci el este un drum minim în subgraful G(k-1) și are valoarea conform ipotezei de inducție. Dacă drumul trece prin xk, atunci el se compune din două subdrumuri, unul de la xi la xk, iar celălat de la xk la xj, minimalitatea sa impunând condiția ca ambele subdrumuri să fie drumuri minime în subgraful Gk (principiul lui Bellman).

Deci, valoarea drumului minim de la xi la xj este în acest caz +, unde și sunt date de formulele a) și b).

În concluzie, formula c) este adevărată pentru orice i, j=1, 2, …, k.

Exemplul 2.2.4.1. Reluând exemplul rezolvat anterior prin algoritmul lui Roy-Floyd, algoritmul lui Dantzig dă matricile drumurilor minime în subgrafurile G(2), G(3), G(4), G(5)G, ce se găsesc în tabelele 2.2.4.1 – 2.2.4.4. Subgrafurile însele sunt reprezentate în figura 2.2.4.1 a, b, c, respectiv în figura 2.2.2.1 (G(5)).

Tabelul 2.2.4.1 Tabelul 2.2.4.2

Tabelul 2.2.4.3. Tabelul 2.2.4.4

Găsirea drumurilor minime se poate face după cum urmează. Pentru =mij se ia linia lui xi din W, care dă valorile directe de la xi la alte vârfuri și se adună cu coloana xj din M(n)M, care dă valorile minime de la diferite vârfuri până la xi și se caută sumele de valoare mij. Se află un prim arc al drumului căutat, (xi, x1) și se lucrează analog cu linia xi, din W și coloana xj din M căutând suma mij pentru cel de al doilea arc al drumului ș.a.m.d. In exemplul dat, avem:

m42 = 11 și d(x4, x2) = (x4, x3, x5, x1, x2).

2.3. Arbori

2.3.1. Definiții și elemente de bază

În clasa grafurilor conexe, arborii reprezintă grafurile cele mai simple (ca structură) și, de asemenea, cele mai frecvent utilizate în practică. De studiul lor s-au ocupat matematicieni și fizicieni de seamă: Cayley a studiat arborii pentru aplicațiile lor în chimia organică, iar Kirchhoff, a studiat accastă categorie de grafuri pornind de la studiul rețelelor electrice.

Termenul do arbore a fost introdus de Cayley în 1857, plecând de la o analogie botanică.

Definiția 2.3.1.1. Se numește arbore un graf conex și fără cicluri.

Exemplul 2.3.1.1. În figura 2.3.1.1. este desenat un arbore. Se observă că oricum am elimina o muchie, graful își pierde proprietatea de conexitate, și oriunde am adăuga o muchie, apare un ciclu. Acest lucru este valabil în orice arbore.

Teorema 2.3.1.1. Fie un graf G=(V, E). Următoarele afirmații sunt echivalente:

1) G este arbore.

2) G este un graf conex, minimal cu aceasta proprietate (eliminând o muchie oarecare

se obține un graf neconex).

3) G este un graf fără cicluri, maximal cu aceasta proprietate (dacă se adaugă o muchie se obține un graf care are măcar un ciclu).

Demonstrație. Ca să demonstrăm teorema enunțată mai sus, este suficient să parcurgem următoarele implicații: 1)2), 2) 1),1) 3) și 3) 1)

Într-adevăr, după ce vom demonstra ce ne-am propus, vom putea scrie:

2) 1) 3).

și, deci, prin tranzitivitatea relației de echivalență, obținem și 2) 3).

1) 2) ipoteză : G conex și fără cicluri

concluzia: G conex și minimal cu această proprietate

Se observă că proprietatea de conexitate este comună ipotezei și concluziei. Presupunem prin reducere la absurd că în E există o muchie e =[x,y] prin a cărei eliminare să se obțină un graf G1 care este totuși conex. Rezultă din conexitatea lui G1 că în acest graf exista un lanț între oricare două vârfuri, deci și intre x și y, fie acesta Lxy. Din acesta putem obține un lanț elementar L’xy. Dacă adăugăm muchia eliminată, ne situăm din nou în G și, în plus, se obține un ciclu, ceea ce este absurd. Urmează că G este intr-adevăr minimal cu proprietatea de conexitate.

2) 1) Ipoteză: G conex și minimal cu aceasta proprietate Concluzia: G conex și fără cicluri

Din nou proprietatea de conexitate este comună ipotezei și concluziei. Mai rămâne să demonstrăm că G este fără cicluri. Presupunem prin reducere la absurd că în G există un ciclu C =[x1, x2, …, xk, x1]. Eliminăm muchia [x1,x2] și argumentăm că se obține un graf G1, tot conex. Într-adevăr, pentru că G este conex, între orice două vârfuri există un lanț. În lanțurile care folosesc muchia, [x1,x2] (doar acestea sunt afectate de eliminarea muchiei), vom înlocui această muchie cu lanțul [x2, x3, …, xk, x1]. Urmează deci că G1 este intr-adevăr conex, ceea ce vine în contradicție cu ipoteza. Rezultă că presupunerea făcută a fost, falsă și deci G este fără cicluri.

1) 3) Ipoteză: G conex și fără cicluri

Concluzia: G fără cicluri și maximal cu această proprietate.

Proprietatea lui G de a fi fără cicluri este comună ipotezei și concluziei. Deoarece G este conex, rezultă că între oricare două vârfuri distincte și neadiacente x și y există un lanț. Din el construim un lanț elementar care să lege x si y. Dacă am adăuga muchia [x,y] atunci ar apare un ciclu, deci G este fără cicluri, maximal.

3) 1) Ipoteză: G fără cicluri și maximal cu această proprietate

Concluzia: G conex și fără cicluri.

Din nou ipoteza și concluzia au o parte comună. Mai rămâne să demonstrăm conexitatea lui G. Fie x și y două vârfuri neadiacente în G. Dacă am adăuga muchia [x,y], am obține, conform ipotezei, un graf care conține un ciclu C (în care apar, evident, vârfurile x si y), C =[x,y,t,…, x]. Eliminând muchia [x,y], ne plasăm din nou în G, și, în plus, din ciclul C putem evidenția un lanț L =[x, t,…, x] care leagă cele două vârfuri x și y. În concluzie, graful G este conex. Demonstrația teoremei este acum terminată.

Definiția 2.3.1.2. Fie G un graf. Un graf parțial H al său care în plus este și arbore se numește arbore partial.

Corolarul 2.3.1.1. Un graf G=(V, E) conține un arbore parțial, dacă și numai dacă G este conex.

Demonstrație:

I. Presupunem că G conține un arbore parțial H=(V, T). Atunci, cum H este conex (fiind arbore), pentru G el este graf parțial. Rezultă că prin adăugarea la H a muchiilor din E-T pentru a reconstitui pe G din H, proprietatea de conexitate se păstrează. Deci G este conex.

II. Dacă G este conex atunci există două cazuri:

1. G este arbore, caz în care H=G.

2. G nu este arbore. Rezultă că el conține cicluri, deci există în G măcar un ciclu C. Fie o muchie e=[x,y] a acestui ciclu. Prin eliminarea muchiei e, proprietatea de conexitate se păstrează. Se obține astfel un graf G1. Dacă G1 este arbore, atunci H=G1. Dacă nu, procedăm similar cu G1. După un număr finit de pași (la fiecare pas se elimină o muchie), obținem arborele parțial căutat H.

Propozitia 2.3.1.1. Orice arbore H = (V,E) cu n > 2 vârfuri conține cel puțin două vârfuri terminale.

Demonstrație: Presupunem prin absurd, că există un arbore H cu n > 2 vârfuri și care conține cel mult un vârf terminal, adică un vârf al cărai grad este 1. Alegem în H un lanț elementar de lungime maximă (care conține numărul maxim de muchii posibil); fie acesta L=[x1, x2, …, xk]. Rezultă că cel mult o extremitate este de gradul 1, deci cel puțin una din extremități are gradul cel puțin 2; fie aceasta x1. Mai există în H măcar un vârf în afară de x2 cu care x1 este adiacent; fie z unul din ele. Dacă z nu ar aparține lanțului L, am deduce că L ar mai putea, fi prelungit cu măcar o muchie, contradicție. Urmează deci că z este pe lanțul L, L=[x1, x2, …, z,…, xk]. Din acest lanț am putea construi un ciclu C=[x1, x2, …,z, x1], ceea ce este absurd. Contradicția provine din presupunerea existenței a cel mult unui vârf terminal. Demonstrația este terminată.

Propoziția 2.3.1.2. Orice arbore cu n vârfuri are n-1 muchii.

Demonstrație. Să observăm mai întâi (ca exemplu) că arborele din figura 2.3.1.1 are 12 vârfuri și 11 muchii.

Facem demonstrația prin inducție după n. Pentru n=1, există un singur arbore și el nu are muchii, deci numărul său de muchii este 1-1=0.

Presupunem proprietatea din enunț adevărată pentru orice arbore cu n vârfuri și să o demonstrăm pentru arborii cu n+1 vârfuri.

Fie H un arbore cu n+1 vârfuri. Conform propoziției anterioare, rezultă că există în H un vârf terminal; fie acesta x. Eliminând din H vârful x împreună cu muchia, incidentă cu el, obținem un arbore H, cu n vârfuri (într-adevăr, H1 este conex și fără cicluri). Pentru el aplicăm ipoteza inductivă (el având n vârfuri) și deducem că H1 are n-1 muchii. Adăugând la loc muchia eliminată, refacem arborele H și constatăm în plus că el are (n-1)+1=n=(n+1)-1 muchii, ceea ce și voiam să demonstram.

Din cele două etape ale inducției, rezultă că afirmația din enunț este, demonstrată.

Ne propunem să vedem cum rezolvăm algoritmic unele probleme legate de arbori.

O primă problemă este aceea a verificării dacă un graf este arbore. Verificăm mai întâi dacă el este conex, folosind, de exemplu una din metodele de parcurgere. Dacă el este, conex, pentru a fi arbore ar fi suficient ca graful să aibă n-1 muchii, lucru ușor de verificat, chiar înainte de verificarea conexității.

O altă problemă interesantă este aceea a verificării dacă un graf este fără cicluri.

Definiția 2.3.1.3. Un graf G=(V, E) care nu conține cicluri se numește aciclic.

Algoritmul pe care îl propunem se bazează pe faptul că reconstituim mulțimea V de vârfuri, plecând inițial de la extremitățile primei muchii, Se adaugă la V noi vârfuri adiacente cu vârfuri deja adăugate anterior la Y. Dacă în tentativa de a căuta asemenea vârfuri, găsim unul în V care este adiacent cu un vârf care este de asemenea în V, deducem ușor că am depistat existența unui ciclu și ne oprim. Dacă nu găsim nici o muchie care să aibă o extremitate în V și o extremitate în afara lui V, se adaugă la V extremitățile unei muchii oarecare, neutilizate încă. Căutarea vârfurilor, pentru a le adăuga în V, o facem deci printre extremitățile muchiilor grafului. Se pornește inițial cu mulțimea Y a indicilor muchiilor grafului, exceptând prima muchie pe care o folosim pentru inițializarea mulțimii V. Pe măsură ce prelucrăm anumite muchii (adăugând la V o extremitate sau chiar pe amândouă), scoatem din Y indicii lor.

În continuare algoritmul scris în pseudocod. Presupunem că muchiile grafului sunt date în vectorul u.

Pas 1. aciclic:=true; {dacă vom descoperi ca G = (V,E) conține cicluri, vom schimba valoarea variabilei aciclic în false}

V={u[1].x,u[1].y}; {punem în X, extremitățile primei muchii;}

Y=; { inițializăm Y cu mulțimea vidă;}

Pas 2. pentru i:=2,m execută Y:=Y{i}; {punem în Y indicii tuturor muchiilor, exceptând 1}

Pas 3. atâta timp cât (aciclic=true) and (Y<>) execută

g:=false; {se folosește pentru a testa dacă am găsit o muchie cu o extremitate în V}

pentru j:=2,m execută {determină prima muchie care are cel puțin o extremitate în V}

dacă jY atunci

x1:=u[j].x;y1:=u[j].y;

dacă (xV) or (y1V) atunci g:=true break;

dacă g=false atunci determină prima muchie j din Y V:=V{u[j].x,u[j].y}

Y:=Y-{j}

Altfel, dacă (x1V) and (y1V) atunci aciclic:=false; {G are cicluri}

altfel determină extremitatea t (a muchiei j) care nu este în V

V:=V{t}; {adaug t la V};

Y:=Y-{j}; {scot muchia j din Y}

Pas 4. Dacă aciclic=true atunci scrie 'graf aciclic'

altfel scrie 'graful conține cicluri'

De asemenea s-ar putea pune problema construirii unui arbore parțial pentru un graf conex. Se poate folosi ideea din algoritmul anterior. De data aceasta alegem o muchie numai dacă ea are o extremitate în V și o extremitate în afara mulțimii V. Precizăm încă odată că în algoritm, V este o variabilă de tip mulțime cu ajutorul căreia noi alegem sau nu o muchie sau un vârf, și nu semnificația tradițională de mulțime a tuturor vârfurilor grafului G.

Definiția 2.3.1.4. Un graf G care nu, conține cicluri se numește pădure.

Exemplul 2.3.1.2. În figura 2.3.1.2 este desenat un graf care este pădure. Denumirea introdusă se justifică prin faptul că fiecare componentă conexă a unui graf fără cicluri este un arbore.

2.3.2. Arbore parțial de cost minim. Algoritmi

Fie un graf G =(V, E) conex, V = {1, 2, …, n}, și o funcție C:ER+ asociază fiecărei muchii u, un număr real pozitiv c(u), numit costul său.

Definitia 2.3.2.1. Pentru un graf parțial H =(V,T) al lui G, costul său reprezintă suma costurilor muchiilor sale, adică:

c(H) =

Exemplul 2.3.2.1. Fie graful G = (V, E), a cărui reprezentare grafică este dată în figura 2.3.2.1, costul fiecărei muchii fiind scris pe ea. Pentru H = (V, T) unde:

T ={[1,2],[3,5], [4,3],[6,7]},

c(H)=c([1,2])+c([3,5])+c([4,3])+c([6,7])=2+2+1+5=10

Fig. 2.3.2.1.

Fig. 2.3.2.1.

Problemă: Să se determine un graf parțial H al lui G care să fie conex și să aibă costul minim.

Observația 2.3.2.1. Pentru un arbore parțial de cost minim folosim notația prescurtată APM.

Problema enunțată este cunoscută și sub numele de “problema conectării cu cost minim a orașelor", deoarece putem să interpretăm cele n vârfuri ale grafului ca fiind n orașe, iar costul muchiei [i, j] ca reprezentând costul conectării, directe a orașelor i și j. Un arbore parțial conex de cost minim reprezintă modalitatea optimă din punct de vedere financiar de a lega direct unele perechi de orașe astfel încât în final orice două orașe să fie conectate (direct sau prin intermediul altora).

Propoziția 2.3.2.1. Pentru graful G conex, cu funcția de cost c, există un graf parțial H conex și de cost minim, care, în plus, este arbore.

Demonstrație. Dacă G este arbore, atunci H=G deoarece orice muchie s-ar elimina, proprietatea de conexitate s-ar pierde. Dacă G nu este arbore, el conține un număr finit de grafuri parțiale care să fie în plus și conexe, fie acestea G1,G2,…, Gk. Îl alegem pe cel de cost minim și il notăm cu H.

Presupunem prin reducere la absurd că H nu este arbore. Cum el este conex, rezultă că are cel puțin un ciclu. Eliminăm o muchie u aparținând unui ciclu, obținem un graf parțial H, de asemenea conex și în plus c(H1) = c(H) – c(u), de unde rezultă că c(H1), < c(H), ceea ce este absurd. Urmează că H este arbore.

Pentru rezolvarea acestei probleme, sunt cunoscuți mai mulți algoritmi. Ne rezumăm numai la unul.

2.3.2.1. Algoritmul lui Kruskal

Acest algoritm a fost stabilit de Kruskal în anul 1956 și de cele mai multe ori referirea la algoritm se face folosind numele autorului

Se pornește inițial cu un graf parțial al grafului G care nu conține nici o muchie, deci conține n vârfuri izolate. Se poate așadar considera ca sunt n arbori disjuncți H1, H2,…, Hi = ({I},Ø), i = 1, …., n. La pasul k (k=0, 1, …, n-2) al algoritmului avem n-k arbori disjuncți, fie aceștia H1, H2, .., Hn-k , Hi = (Xi,. Ei), astfel încât V1V2 …Vn-k = V și ViVj= ij. Obținem astfel prin unificarea a doi dintre arborii existenți, aleși intr-un anumit mod, n-k-1 arbori disjuncți. Alegerea celor doi arbori ce vor fi unificați se face în felul următor: dintre toate muchiile nealese încă, se, selectează aceea de cost minim care are cele două extremități în doua mulțimi diferite Vi și Vj (aceasta condiție se impune pentru ca adăugarea unei muchii să nu provoace apariția unui ciclu în graful parțial de cost minim ce se construiește din aproape în aproape). Prin adăugarea acestei muchii u, din arborii Hi si Hj, se va forma un nou arbore H'=(V',T’), V'= Vi Vj, T' =TiTj {u}. Evident, după pasul n-2 obținem un singur arbore.

Detalii de implementare pentru algoritmul lui Kruskal

Pentru graful conex dat se folosește al treilea mod de reprezentare, iar pentru a ști în fiecare moment care sunt vârfurile ce aparțin aceluiași subarbore parțial Hi, se asociază tuturor vârfurilor lui H, aceeași valoare; evident pentru subarbori parțiali distincți vârfurile acestora vor avea asociate valori distincte. Folosim pentru acest scop vectorul L cu n componente.

struct Muchie

{

int a,b;

float cl;

};

……………………….

Muchie u[50];

Int L[30] ;

Etapele algoritmului lui Kruskal sunt:

Pas 1. L[i]=i, i =1,2, …, n. Inițial fiecare vârf face parte, singur, dintr-un subarbore, Hi=({I},).

Pas 2. Se ordonează vectorul u crescător după costul c al muchiilor.

Pas 3. ct=0; {costul total};

k=0; {numărul total de muchii alese};

i=1; { indice pentru vectorul ce conține muchiile};

Pas 4. Pentru a alege cele n-1 muchii ale arborelui parțial de cost minim se parcurg elementele vectorului u astfel:

Fie v=[u[i].a, u[i].b] muchia ce urmează să fie analizată. Inițial i, este 1. Dacă în vectorul L în extremitățile acestei muchii, avem valori egale, rezultă că ele aparțin deja aceluiași, subarbore, deci alegerea ei ar provoca apariția unui ciclu. Prin urmare, această muchie nu este, aleasă. Dacă, din contră, în extremitatile, ei vectorul L are valori diferite, înseamnă că ele fac parte din doi subarbori diferiți, fie aceștia Ha=(Va,Ea) și Hb=(Vb,Eb), care pot fi unificați, operație care presupune că în toate vârfurile aparținând celor doi subarbori să facem sa apară aceeași valoare, provenită din, primul sau din al doilea subarbore. Se obține subarborele Hc=(VaVb, EaEb{v}). Acest pas se repeta până am reușit să, alegem cele n-1 muchii ale arborelui parțial de cost minim.

Scriem intr-o formă condensată pasul 4:

Pas 4. atâta timp cât k < n – 1 execută

dacă L[u[i].x]#L[u[i].y] atunci k:=k+1 {alege muchia i;}

ct:=ct+u[i].c

w:=L[u[i].x] {urmeaza unificarea celor doi subarbori;}

v:=L[u[i].y]

pentru j:=1, n execută

dacă L[j]=v atunci L[j]: =w;

i:=i+1;

Pas 5. scrie ct.

Pentru graful din figura 2.3.2.1. inițial avem:

u1 u2 u3 u4 u5 u6 u7 u8 u9 u10 u11

u=([2,5], [1,7], [6,2], [2,7], [6,5], [2,3], [5,4], [1,2], [3,4], [3,5], [7,6])

După ordonarea elementelor vectorului, în ordinea crescătoare a lui c, avem:

u = ( [5,4], [3,4], [3,5], [1,2], [2,5], [2,3], [6,5], [2,6], [2,3], [1,7], [7,6])

c = ( 1, 1, 2, 2, 2, 3, 3, 3 , 3, 4, 5 )

Se inițializează L cu (1, 2, 3, 4, 5, 6, 7).

În acest moment avem Hi=({i},), pentru i=1, …, 7.

Se alege muchia [5, 4] , L devine: (1, 2, 3, 5, 5, 6, 7).

Au fost unificați subarborii H4 și H5, obținându-se subarborele H5= ({4,5}, {[5,4]}). Ceilalți subarbori Hi cu i{1,2,3,6,7}, rămân neschimbați.

Se alege muchia [3,4] și L devine: (1,2,3,3,3,6,7).

Obținem H3=({3,4,5},[3,4],[5,4]), iar Hi=({i},), pentru i{1,2,6,7}.

În, acest moment urmează la rând muchia [3,5] care nu poate fi luată deoarece avem L[3] = L[5] (vârfurile 3 și 5 aparțin deja aceluiași subarbore H3) si alegerea ei ar provoca apariția unui ciclu.

Se merge mai departe și se alege muchia [1,2]. L devine: (1,1,3,3,3,6,7).

Obținem H1 =({1,2}, { [1,2]}). Apoi se alege [2,5] si L=(1, 1, 1, 1, 1,6,7). în acest moment avem trei subarbori: H1=({1,2,3,4,5},{[1,2], [2,5],[3,4], [5,4]}) iar H6 si H7 rămân neschimbați.

Muchia [2,3] nu poate fi luată pentru că ar crea un ciclu (vârfurile 2 si 3 aparțin deja aceluiași subarbore H1. Se aleg pe rând, muchiile [6,5] (obținându-se subarborele H1=({1,2,3,4,5,6}, {[1,2], [2,5], [3,4], [5,4], [6,5]})) și, în sfârsit, [2,7], L devenind: (2,2,2,2,2,2,2), ceea ce corespunde arborelui parțial de cost minim H=({1,2,3,4,5,6,7}, {[1,2], [2,5], [3,4], [5,4], [6,5], [2,7]}). Nu are importanta care subarbore se alege pentru a transfera în vârfurile celuilalt subarbore (în componentele corespunzătoare lor din vectorul L) aceeași valoare.

Programul C++ care determina APM folosind algoritmul lui Kruskal este următorul:

#include<iostream.h>

struct muchie

{

int x,y;

float cost;

};

muchie u[20];

int i,j,m,n,k,L[20],ct,v,w,aux;

void citire()

{ cout<<"\n Dati numarul de noduri";

cin>>n;

cout<<"\n Dati numarul de muchii";

cin>>m;

for(i=1;i<=m;i++)

{ cout<<"\n Dati muchia "<<i<<endl;

cin >>u[i].x;

cin >>u[i].y;

cout<<"\n dati costul muchiei "<<i<<endl;

cin>>u[i].cost;

}

}

main()

{

citire();

int m1=m;

for (i=1;i<m1;i++)

for (j=i+1;j<=m1;j++)

if (u[i].cost>u[j].cost)

{

aux=u[i].cost;

u[i].cost=u[j].cost;

u[j].cost=aux;

}

cout<<endl;

for(i=1;i<=m;i++)

cout<<u[i].cost<<" ";

cout<<endl;

for (int t=1;t<=n;t++)

L[t]=t;

ct=0;

k=0;

i=1;

while (k<n-1)

{

if (L[u[i].x]!=L[u[i].y])

{

k++;

ct=ct+u[i].cost;

cout<<u[i].x<<" "<<u[i].y<<" ";

v=L[u[i].y];

w=L[u[i].x];

for (j=1;j<=n;j++)

if (L[j]==v) L[j]=w;

}

i++;

}

cout<<"\n Costul total este " <<ct;

}

2.3.3. Arbori binari de căutare optimali

O clasa foarte importantă de arbori cu rădăcină o constituie arborii binari.

Definiția 2.3.3.1. Un arbore binar este un arbore cu rădăcina în care gradul oricărui vârf este cel mult egal cu doi.

Putem defini recursiv arborii binari astfel :

Definiția 2.3.3.2. Un arbore binar este un arbore care fie este vid, fie constă dintr-un nod rădăcina și doi arbori binari disjuncți numiți subarborele stâng, respectiv subarborele drept.

Fig. 2.3.3.1.

A1 subarbore stâng; A2 subarbore drept.

Se face o distincție clară între subarborele drept și cel stâng. Daca subarborele stâng este nevid, rădăcina lui se numește fiul stâng al rădăcinii. Analog, dacă subarborele drept este nevid, rădăcina lui se numeăte fiul drept al rădăcinii.

De exemplu,

Fig. 2.3.3.2.

sunt doi arbori binari distincți.

Fie a1<a2< …<an o mulțime statică de chei. Să se construiască un arbore binar de căutare optimal. Deci, odată arborele construit, nu se vor efectua operații de inserare sau ștergere, ci numai operații de căutare. Pentru evaluarea optimalității unui arbore binar de căutare se impune definirea unei funcții cost pe mulțimea tuturor arborilor binari de căutare cu cheile a1<a2<…an.

Notăm cu pi probabilitatea de a căuta valoarea ai. În cazul în care s-ar efectua numai căutări cu succes, costul arborelui ar fi:

deoarece pentru căutarea valorii ai în arbore, numărul de comparații necesare este egal cu numărul de noduri de pe drumul de la rădăcină la nodul cu cheia ai, deci, în ipoteza că nivelurile sunt numerotate de la zero, este egal cu nivel (ai)+1.

Dar nu se execută numai căutări cu succes, de aceea trebuie să includem în costul arborelui și costul căutărilor fără succes. Să partiționăm mulțimea valorilor care nu sunt în arbore în n clase, astfel:

C0 ={ x x <a1}

Cn ={ x x > an}

Ci ={ x ai < x <ai+1}, i1,2,…,n-1.

Notăm cu qi probabilitatea ca valoarea căutată să fie în clasa Ci, i0,1,…,n.

Costul căutărilor fără succes va fi:

deoarece orice căutare fără succes se termină pe un nod extern. Nodul extern i, 0 i n, (considerând numerotarea de la stânga la dreapta) este nodul corespunzător clasei Ci.

Definiția 2.3.3.3. Numim arbore binar de căutare optimal pentru mulțimea a1<a2<…<an un arbore binar de căutare de cost minim, care minimizează expresia

+

Exemplul 2.3.3.1. Fie a1=5, a2=10, a3=20. Arborii binari de căutare pentru această mulțime de valori sunt:

Fig. 2.3.3.3.

Dacă vom considera p1=p2=p3=1/7 și q0=q1=q2=q3=1/7, deci orice valoare este căutată în arbore cu aceeași probabilitate, obținem:

cost(arbore a.) = 15/7

cost(arbore b.) = 13/7

cost(arbore c.) = 15/7

cost(arbore d.) = 15/7

cost(arbore e.) = 15/7

Așa cum era de așteptat, arborele binar de căutare optimal este b.

Dar, pentru p1=0.5; p2=0.1; p3=0.05 și q0=0.15; q1=0.1; q2=0.05; q3=0.05 obținem :

cost(arbore a.) = 2.65

cost(arbore b.) = 1.9

cost(arbore c.) = 2.05

cost(arbore d.) = 1.5

cost(arbore e.) = 1.6

Deci, arborele binar de căutare optimal este arborele d.

Pentru determinarea arborelui binar de căutare optimal pentru o mulțime dată de valori a1<a2<…<an, o primă soluție ar fi să generăm toți arborii binari de căutare pentru mulțimea de valori dată, să calculăm costul fiecărui arbore și să selectăm arborele de cost minim.

Dar numărul arborilor binari cu n vârfuri date este :

ceea ce face ca aplicarea acestei metode să nu fie posibilă pentru valori mari ale lui n.

Făcând unele observații referitoare la proprietățile arborilor binari de căutare optimali, un algoritm mult mai eficient se bazează pe metoda programarii dinamice.

Se notează pentru orice 1i<jn :

Conform acestor notații:

T0n este arborele binar de căutare optimal pentru a1, … ,an;

c0n este costul arborelui binar de căutare optimal T0n;

r0n este rădăcina arborelui binar de căutare optimal pentru a1, … ,an;

w0n =1.

Fie Ti, j este un arbore binar de căutare optimal pentru ai+1, … ,aj și ri, j = k (i < k j).Ti, j are doi subarbori : subarborele stâng, care conține cheile ai+1,…,ak-1, și subarborele drept, care conține cheile ak+1, … ,aj.

Fig. 2.3.3.4.

Atunci:

Din această relație deducem că Ti, j este optimal dacă și numai dacă S și D sunt optimali, deci S=Ti, k-1 și D=Tk, j (altfel înlocuind S sau D cu un arbore de cost mai mic, am obține un arbore pentru ai+1, … ,aj de cost mai mic decat ci, j, în contradicție cu ipoteza că Ti, j optimal).

Problema are prin urmare substructură optimală pe care o caracterizam prin următoarea relație de recurență :

Ci, j = Ci, k-1 + Ci, k + wi, j (*)

Cum Ti, j este optimal, rădăcina sa ri, j=k trebuie sa fie selectată astfel încât sa se obțină un cost minim.

Vom folosi această relație pentru a obține T0n în mod bottom-up, conform principiilor programării dinamice.

De exemplu, pentru n=4 și

Utilizând relația (*) calculăm wi, j , ci, j , ri, j , pentru i,j{0,1,2,3,4}, i j :

Deci arborele binar de căutare optimal este:

Fig. 2.3.3.5.

Algoritm de determinare a unui arbore binar de căutare optimal :

calcul( r, c, w, p, q)

pentru i 0, n-1 executa //inițializare

w[i, i] q[i]

c[i, i] 0

r[i, i] 0

w[i, i+1] q[i]+q[i+1]+p[i+1]

c[i, i+1] w[i, i+1]

r[i, i+1] i+1

sfarsit_pentru

c[n,n] 0 r[n,n] 0 w[n,n] q[n]

pentru d 2, n executa

pentru i 0, n-d executa

j i+d

w[i, j] w[i, j-1]+p[j]+q[j]

k i+1

pentru t i+2, j executa

daca c[i, k-1]+c[k, j] > c[i, t-1]+c[t, j] atunci k t

sfarsit_daca

sfarsit_pentru

r[i, j] k

c[i, j] c[i, k-1]+c[k, j]

sfarsit_pentru

sfarsit_pentru

sfarsit_calcul

Observația 2.3.3.1. Construirea unui arbore binar de căutare optimal prin metoda programării dinamice are complexitatea timp de O(n3).

Se poate îmbunătăți timpul de execuție a algoritmului, utilizând un rezultat datorat lui D. E. Knuth, conform căruia putem restrânge domeniul în care se caută valoarea ce minimizează expresia lui Ci, j de la intervalul [i+1,j] la intervalul [ri, j-1 , ri+1, j]. În acest caz procedura de calcul va fi O(n2).

2.4. Aplicații

Aplicația 2.4.1. Într-o secție a unei întreprinderi, se aplică asupra unui produs anumite operații de prelucrare. Prelucrările ce se pot face, tehnologiile posibile de ordonare a lor și costurile unitare asociate fiecărei prelucrări sunt date într-un model-graf ponderat cu reprezentarea geometrică dată prin figura 2.4.1.

Să se determine tehnologia corespunzătoare celui mai scăzut cost unitar total.

Rezolvare. Sensul economic al elementelor grafului dat impune ca acesta să nu aibă circuite, ceea ce verificăm cu ajutorul matricei drumurilor.

Tabelul 2.4.1 conține matricea arcelor grafului dat, cu ajutorul căreia s-a calculat matricea drumurilor, din tabelul 2.4.2

Tabelul 2.4.1 Tabelul 2.4.2

Trebuie determinat drumul de valoare minimă de, la x1 (care evident reprezintă starea inițială a produsului) la x8 (care reprezintă starea finală).

Aplicăm algoritmul Bellman-Kalaba. Matricea valorilor, împreună cu liniile suplimentare, se găsesc în tabelul 2.4.3.

Tabelul 2.4.3.

Din cercetarea acestui tabel, se observă că tehnologia de la x1 la x8, cu cost minim, corespunde costului 11. Căutăm arcele care formează drumul de valoare minimă, adunând întâi linia x1 la și căutând sumele de valoare minimă, adica 11, avem: 2 + 9 = 6 + 5 = 4 + 7; deci sunt trei variante, anume drumul începe fie cu arcul (x1, x2), fie cu arcul (x1, x3), fie cu arcul (x1, x6). Urmărim prima variantă, adunând linia x2 la mi8, și căutând sumele de valoare 9, avem 2 + 7 = 9, deci al doilea arc din prima variantă este (x2, x5) și rămâne de la x5 la x8, un drum de lungime minima 7, care este tocmai arcul (x5, x8). Drumul în prima variantă, format din 3 arce, este: (x1, x2, x5, x8). Analog procedăm în celelalte două variante și obținem drumurile: (x1, x3, x7, x8) și (x1, x3, x3, x7, x8). Geometric, cele trei drumuri optime găsite, formează graful parțial din figura 2.4.2

Aplicația 2.4.2. Pentru aprovizionarea cabanelor dintr-un complex turistic alpin, se folosesc atât posibilitățile de transport rutier pe drumurile forestiere cât și transportul pe teleferic. Condițiile existente fac ca pe unele trasee să se poată circula în ambele sensuri, iar pe altele într-un singur sens, bine determinat. Aceste posibilități sunt oglindite într-un model graf prin muchii sau, respective arce, considerând că muchia conține două arce de sens contrar. Se cunosc distanțele pe fiecare porțiune a diverselor trasee. Știind că aprovizionarea se poate face din centrele x1 și x2, Să se găsească cele mai scurte trasee ce trebuiesc parcurse de la aceste centre la toate cabanele complexului, modelul graf fiind cel din figura 2.4.3

Rezolvare. Graful mixt poate fi transformat în graf orientat, înlocuind fiecare muchie prin două arce de sens contrar și de aceeași valoare, ceea ce conduce la graful orientat din figura 2.4.4.

Aplicăm algoritmul lui Dantzig, pentru aflarea tuturor rutelor minimale. Pornim cu matricea valorilor W, din tabelul 2.4.4.

Tabelul 2.4.4.

Deducem recursiv matricele M(k), k = 2, 3, …, 8, ce se găsesc în tabelele 2.4.5 – 2.4.11. Ultimul dintre aceste tabele conține matricea M căutată.

Tabelul 2.4.5. Tabelul 2.4.6. Tabelul 2.4.7.

Tabelul 2.4.8. Tabelul 2.4.9.

Tabelul 2.4.10. Tabelul 2.4.11

Drumurile de valori minime, care pleacă din centrul x1, sunt:

d(x1, x2)=(x1, x2) , cu m12=5;

d(x1, x3)=(x1, x4, x3) , cu m13=6;

d(x1, x4)=(x1, x4) , cu m14=4;

d(x1, x5)=(x1, x2, x5) , cu m15=11;

d(x1, x6)=(x1, x4, x6) , cu m16=9;

d(x1, x7)=(x1, x4, x7) , cu m17=10;

d(x1, x8)=(x1, x2, x5, x8) , cu m18=13;

Drumurile de valori minime, care pleacă din centrul x4, sunt:

d(x4, x1)=(x4, x4, x1) , cu m41=5;

d(x4, x2)=(x4, x3, x1, x2) , cu m42=10;

d(x4, x3)=(x4, x3) , cu m43=2;

d(x4, x5)=(x4, x3, x1, x2, x5) , cu m45=16;

d(x4, x6)=(x4, x6) , cu m46=5;

d(x4, x7)=(x4, x7) , cu m47=6;

d(x4, x8)=(x4, x7, x8) , cu m48=12;

CAPITOLUL 3

DRUMURILE HAMILTONIENE ÎN GRAFURI

3.1. Transporturi pe drumuri hamiltoniene

Adesea, transportul unor produse trebuie organizat cu ajutorul unei rețele do transport cunoscute (un graf), astfel încât să se treacă prin toate punctele importante luate în considerație (prin toate vârfurile, grafului), netrecând de, două sau mai multe ori prin niciunul dintre acestea. De exemplu, putem fi puși în fața necesității de a organiza aprovizionarea unor magazine, (cantine; puncte de lucru ale unei întreprinderi etc,) cu ajutorul unui singur camion, care să treacă succesiv, pe la fiecare dintre acestea, folosind o rețea de comunicații cunoscute. În plus dacă o astfel de organizare poate fi făcută în mai multe feluri se poate pune problema găsirii unei soluții care să fie cât mai convenabilă (optimă) din punct de vedere, al cheltuielilor făcute, al timpului consumat etc.

Definiția 3.1.1. a)Fie G = (V,E) un graf. Un lanț¸ elementar, ciclu elementar, drum elementar sau circuit elementar în graful G ce conține toate nodurile lui G se numește hamiltonian.

b) Un graf neorientat se numește hamiltonian dacă are (cel puțin) un ciclu hamiltonian.

c) Un graf orientat se numește hamiltonian dacă are (cel puțin) un circuit hamiltonian.

În problema dată ca exemplu, mai sus, se poate cere drumul cu care să se aprovizioneze punctele respective, fără a considera drumurile camionului de la și la garaj (caz în care problema este de determinare a unui drum hamiltonian prescurtat DH), sau se poate lua în considerare și întoarcerea camionului în punctul de plecare (caz în care problema este de determinare a unui circuit hamiltonian, prescurtat CH). În plus, dacă se iau în considerare și costurile de transport, suntem conduși la problema determinării unui drum hamiltonian de valoare minimă prescurtat DHM, respectiv la problema determinării unui circuit hamiltonian de valoare minimă – prescurtat CHM. În sfârșit, dacă graful folosit este neorientat, denumirilor și notațiilor de mai sus le corespund următoarele: lanț hamiltonian (LH), ciclu hamiltonian (CH), lanț hamiltonian de valoare minimă (LHM), ciclu hamiltonian de valoare minimă (CHM).

Vom începe, studiul sistematic al unora dintre problemele puse, cu problema determinării drumului hamiltonian (drumurilor hamiltoniene), într-un graf orientat și neponderat. Determinarea acestor drumuri hamiltoniene se face în mod diferențiat, în grafuri fără circuite și în grafuri cu circuite.

a) Problema drumurilor hamiltoniene în grafuri fără circuite.

În construcția matricei drumurilor triangularizate, D', am putut observa că primul element diferit de zero din fiecare linie, ca și ultimul element diferit de zero din fiecare coloană corespund în graful dat, G = (V, E).

Teorema 3.1.1.(Y. Chen). Fie G = (V, E) un graf orientat și fără circuite, cu n vârfuri. Condiția necesară și suficientă pentru ca G să conțină un drum Hamiltonian este ca numărul elementelor egale cu unu din matricea D, să fie:

Demonstrație. Presupunem că există un drum hamiltonian: DH=() corespunzând permutării: .

Deoarece graful nu are circuite, rezultă că xi1 atinge (n-1) vârfuri, deci pe linia lui xi1, în matricea D sunt (n – 1) elemente egale cu unu. Vârful xi2, atinge (n-2) vârfuri, deci linia corespunzătoare lui din D are (n-2) elemente egale cu unu ș.a.m.d., pentru fiecare vârf, al drumului hamiltonian numărul de elemente egale cu unu scade cu câte o unitate, până la vârful xin, care este ultimul vârf al drumului hamiltonian, deci are puterea de atingere zero (în caz contrar, graful nu ar corespunde ipotezei de a nu avea circuite). Deci numărul total de elemente egale cu unu în matricea D este suma unei progresii aritmetice cu rația unu, adică: (n-1)+(n-2)+, …, +2+1=.

Reciproc, presupunem că suma cifrelor de unu din D, sau suma puterilor de atingere, este . Considerăm forma triangularizată, D', în care notăm vârfurile x1’, x2’,…, xn', deduse prin permutarea elementelor x1, x2, …, xn în ordinea descrescătoare a puterilor de atingere. În D' toate elementele egale cu unu se află deasupra diagonalei principale și cum deasupra diagonalei principale sunt locuri, înseamnă că nici o cifră zero nu se află deasupra diagonalei principale. Putem scrie o succesiune de arce, corespunzând primului element diferit de zero din fiecare linie: (), (), …, (), succesiune care formează un drum hamiltonian DH = .

Teorema 3.1.2. Într-un graf G =(V, E), orientat și fără circuite, dacă există un drum hamiltonian, acesta este unic.

Demonstrație. Fie DH=, unde vârfurile se succed în ordinea descrescătoare a puterilor de atingere. Orice altă succesiune a vârfurilor conține cel puțin o inversare a indicilor. Presupunem prin absurd că ar exista cel puțin un arc de forma () cu j < i, adică linia x’j; precede linia x'i în D', astfel că d'ji =1, deci situat deasupra diagonalei principale în D'. Deducem de aici existența unui drum d(x’j, x’i). Cum însă succesiunea de sus conține, drumul(x’i, x’j,), rezultă că graful are circuit, contrar ipotezei. Deci presupunerea că în graf drumul hamiltonian nu este unic, este falsă.

Exemplul 3.1.1. Prelucrarea unui obiect artizanal poate trece prin șase faze distincte, notate într-un model de graf prin xi(i =1, 2, …, 6), iar posibilitățile de trecere de la o fază la alta sunt reprezentate prin arce (vezi figura 3.1.1.). Este posibil ca obiectul să treacă prin toate fazele de prelucrare? Dacă acest lucru este posibil, să se indice tehnologia corespunzătoare.

Rezolvare. Matricea arcelor grafului dat este cea din tabelul 3.1.1 Cu ajutorul ei s-a calculat matricea drumurilor, din tabelul 3.1.2, Deoarece aceasta din urmă are numai zerouri pe diagonala principală, graful dat nu are circuite.

Tabelul 3.1.1. Tabelul 3.1.2.

Calculăm ceea ce se observă direct, în tabelul 3.1.2. Deci graful dat are un drum hamiltonian, anume:

DH=(x4, x5, x6, x1, x2, x3)

Tabelul 3.1.3.

Succesiunea respectivă corespunde la tehnologia căutată.

Observația 3.1.1. Forma triangularizată a matricei drumurilor este reprezentată în tabelul 3.1.3.

b) Problema drumurilor hamiltoniene în grafuri oarecare (cu circuite)

În grafuri oarecare se pot determina drumurile hamiltoniene pe mai multe căi. În cele ce urmează prezentăm doi algoritmi uzuali.

3.2. Algoritmul pentru determinarea drumurilor hamiltoniene

3.2.1. Algoritmul ce folosește graful condensat

Algoritmul pleacă de la o serie de observații evidente, în legătură cu graful condensat G* și anume:

Observația 3.2.1.1. Dacă într-un graf G există cel puțin un drum hamiltonian atunci și graful său condensat G*, conține un astfel de drum. Drumul hamiltonian din G trebuie să parcurgă, succesiv, toate vârfurile oricărei componente tare conexe, iar de la o componentă la alta ordinea este dictată de ordinea componentelor în drumul hamiltonian din G*.

Observația 3.2.1.2. Dacă graful condensat G* nu conține nici un drum hamiltonian atunci nici graful G nu conține nici un drum hamiltonian. Această observație este negația logică a propoziției precedente.

Observația 3.2.1.3. Dacă graful condensat G* conține un drum hamiltonian nu rezultă că și graful G conține drum hamiltonian în mod necesar. În funcție de legăturile directe (arcele din G) între componentele tare conexe, graful G poate să aibă sau poate să nu conțină drum hamiltonian.

Algoritmul de deducere a drumurilor hamiltoniene din G, prin reducerea la drumul hamiltonian din G*, cere parcurgerea următoarelor etape:

Pas. 1. Găsirea tuturor componentelor tare conexe. Fie mulțimea lor: V* ={Cl, C2, …, Ck}.

Pas. 2. Determinarea matricei arcelor A* pentru G* și matricei drumurilor D*.

Pas.3. Cercetarea existenței DH* în G*, pe baza teoremei Chen, verificând egalitatea:

Pas. 4. Dacă G* nu conține un drum hamiltonian, atunci nici graful G nu conține un drum hamiltonian .

Dacă G* conține un drum hamiltonian fie DH* =;determinăm drumurile hamiltoniene din fiecare componentă tare conexă și le legăm prin arcele care leagă componentele succesive în toate modurile posibile. Cum am mai afirmat, în G poate să existe sau poate să nu existe drum hamiltonian, în funcție de aceste legături.

Exemplul 3.2.1.1. La un șantier hidroenergetic, trebuie livrate materiale de construcții în cinci puncte de lucru. Aceste puncte de lucru au fost legate prin niște căi de acces, croite după posibilitățile permise de teren, ca în graful din figura 3.2.1.1. Se pune problema dacă basculantele pot trece pe la toate punctele de lucru să descarce materialele necesare.

Rezolvare. Graful are circuite. Să aplicăm algoritmul bazat pe construirea grafului condensat. În tabelul 3.2.1.1. sunt efectuate calculele pentru determinarea componentelor tare conexe.

Tabelul 3.2.1.1.

Avem:

C1=C(x1):(W1 W’1){x1}={x1, x5},

C2=C(x2):(W2 W’2){x2}={x2, x4},

C3=C(x3):{x3}.

Deci G* = (V*, E*), unde V* = {C1, C2, C3 }.

Cu ajutorul matricelor intermediare din tabelele 3.2.1.2 și 3.2.1.3, determinăm matricea A* din tabelul 3.2.1.4. Avem deci: E*={(C1,C2), (C2, C3)}.

Tabelul 3.2.1.2 Tabelul 3.2.1.3 Tabelul 3.2.1.4

Construim matricea drumurilor în G*, cu algoritmul Chen, ca în tabelul 3.2.1.5.

Tabelul 3.2.1.5.

(graful condensat are n*=3 vârfuri), în graful condensat există drumul hamiltonian ce urmează:

DH* = (C1, C2, C3).

Grafic, avem descompunerea grafului dat, ca în figura 3.2.1.2.

Ținând seama și de arcele ce leagă componentele consecutive din DH*, reprezentate în figura 3.2.1.3. rezultă că există și în graful inițial,un drum hamiltonian, anume:

DH = (x2, x1, x4, x2, x3).

Acesta este drumul pe care urmează să îl facă basculantele, pentru a trece pe la toate punctele.

3.3. Aplicații

Aplicația 3.3.1. Un produs finit poate fi verificat în privința respectării indicilor de calitate pe la șapte puncte de control. Procesul de producție este automatizat și trecerea se face pe bandă rulantă. Cum fiecare punct de control verifică o anumită calitate a produsului, bine determinată, găsiți posibilitatea de a folosi într-o anumită ordine aceste puncte de control, astfel încât verificarea sa fie completă. Graful corespunzător se găsește în figura3.3.1.

Rezolvare. Graful nu are circuite. Într-adevăr, folosind matricea arcelor din tabelul 3.3.1, se obține matricea drumurilor din tabelul 3.3.2, aceasta neavând nici un element egal cu unu pe diagonala principală. În tabelul 3.3.2. sunt calculate și puterile de atingere ale vârfurilor grafului.

Tabelul 3.3.1

Tabelul 3.3.2.

După cum se vede, avem:

Ca urmare, graful dat are un drum hamiltonian, acesta având forma următoare:

DH=(x7, x1, x3, x2, x4, x5, x6).

Aplicația 3.3.2. Într-o hală industrială procesul de producție se desfășoară pe un sistem de benzi rulante, care, leagă șase puncte de lucru, ca în figura 3.3.2. În fiecare din aceste puncte de lucru se execută câte o anumită operație. Întreprinderea, asimilează un produs nou, care trebuie să treacă prin toate cele șase operații, deci pe la toate punctele de lucru. Arătați dacă sistemul de benzi rulante existent în hală permite acest lucru, iar dacă nu, indicați o modificare tehnică cât mai simplă care să ducă la soluționarea problemei.

Rezolvare. Matricea arcelor grafului, din tabelul 3.3.3, conduce la matricea drumurilor, din, tabelul 3.3.4. Cercetând acest din urmă tabel, observăm că graful este fără circuite și . În consecință nu există drum hamiltonian. Pentru ca produsul să poată trece pe la toate punctele de lucru, căutăm să scriem forma triangularizată, ordonând vârfurile care au aceeași putere de atingere după criteriul unui numar mai mic de zerouri în coloana corespunzătoare din D, deoarece astfel numărul elementelor egle cu zero situate imediat deasupra. diagonalei principale va fi mai mic.

Tabelul 3.3.3.

Tabelul 3.3.4.

12

Alegem ordinea (x2, x3, x6, x4, x5, x1) care va da un drum hamiltonian dacă se construiește o bandă rulantă între punctele x5 și xl, după cum rezultă din forma triangularizată ce se găsește în tabelul 3.3.5

Cu construcția benzii de la x5 la x1 produsul trece prin toate cele 6 operații, în ordinea: x2, x3, x6, x4, x5, x1.

Tabelul 3.3.5.

Dacă nu am fi respectat regula de a ordona vârfurile cu aceeași putere de atingere după numărul mai mic de zerouri din coloana corespunzătoare din D, atunci ordinea era: x2, x3, x4, x1, x5, dar se construiau două benzi rulante, între x4 și x1, ca și între x1 și x5, deci nu constitute cea mai simplă soluție tehnică.

Aplicația 3.3.3. Un inspector trebuie să facă un control asupra celor cinci unități de alimentație publică din cadrul unei stațiuni montane. Posibilitățile de acces între aceste unități sunt reprezentate în tabelul-graf din figura 3.3.3. , prin arce. Se pune problema, cum trebuie să procedeze inspectorul pentru a controla toate unitățile, deci care este unitatea cu care trebuie să înceapă controlul și ordinea în care va controla celelalte unități.

Rezolvare. Graful are, evident, circuite. Să aplicăm algoritmul Kaufmann. Pentru aceasta se folosesc matricile M(1) și din tabelele 3.3.6 și 3.3.7.

Tabelul 3.3.6.

Tabelul 3.3.6’.

Cu rezultatele intermediare din tabelele 3.3.7 și 3.3.8 se obține rezultatul final din tabelul 3.3.9

Tabelul 3.3.7.

Tabelul 3.3.8.

Tabelul 3.3.9.

Matrice M(4) dă toate drumurile hamiltoniene, în număr de șapte. Se vede că se poate începe controlul cu oricare unitate. Între aceste variante se alege una după un anumit criteriu de optim. Cele șapte drumuri hamiltoniene sunt următoarele:

DH1=(x1, x5, x3, x4, x2),

DH2=(x1, x2, x5, x3, x4),

DH3=(x1, x3, x4, x2, x5),

DH4=(x2, x5, x1, x3, x4),

DH5=(x3, x4, x2, x3, x1),

DH6=(x4, x2, x5, x1, x3),

DH7=(x5, x1, x3, x4, x2),

Aplicația 3.3.4. Trebuie stabilit drumul unui raliu care să treacă prin zece localități. Șoselele existente între localitățile respective au fie sens unic, fie ambele sensuri de circulație și au ca model un graf cu imaginea din figura 3.3.4. Trebuie stabilit din ce localitate trebuie să pornească raliul și care este drumul prin celelalte localități. Dacă s-a cronometrat și timpul mediu de parcurgere a fiecărei porțiuni de șosea cu automobilul (în ore), care este decizia cea mai bună de stabilire a drumului?

Rezolvare. Trebuie cercetat dacă acest graf cu circuite admite existența unui drum hamiltonian, iar în cazul existenței a mai multor drumuri hamiltoniene trebuie determinat cel minim (DHM).

Tabelul 3.3.8. conține calculele pentru determinarea componentelor tare conexe.

Tabelul 3.3.8.

Avem:

C1=C(x1)= (W1 W’1){x1}={x1, x2, x7, x8, x9, x10}

C2=C(x3)= (W2 W’2){x3}={x3, x4}

C3=C(x3)= (W3 W’3){x5}={x5, x6}

Cu ajutorul tabelelor 3.3.9 și 3.3.10, s-a calculat matricea arcelor grafului condensat, din tabelul 3.3.11.

Tabelul 3.3.9.

Tabelul 3.3.10.

Tabelul 3.3.11.

Graful condensat are, deci, imaginea din figura 3.3.5.

Deoarece G* nu are circuite, determinăm matricea D* și puterile de atingere ale celor trei ,,vârfuri", C1, C2, C3. Această matrice se găsește în tabelul 3.3.12.

Tabelul 3.3.12

Avem:

,

deci, există DH* = (C1, C2, C3).

În C1 aplicăm algoritmul Kaufmann pentru determinarea drumurilor hamiltoniene în acest subgraf, cu șase vârfuri. Pentru simplitatea scrierii, convenim să trecem secvențele numai prin intermediul indicilor, adică ij în loc de xixj.

În tabelele 3.3.13-3.3.18. sunt efectuate calculele, ultima matrice furnizând rezultatul. Astfel: din matricea -M(5) citim cele două drumuri hamiltoniene din componenta C1 anume:

DH1 = {x2, x1, x9, x10, x7, x8}

DH2 ={x10, x7, x8, x1, x9, x2}

Tabelul 3.3.13.

Tabelul 3.3.14.

Tabelul 3.3.15.

Tabelul 3.3.16.

Tabelul 3.3.17

Tabelul 3.3.18.

Componentele C2 și C3 au numai câte două vârfuri, deci drumurile lor hamiltoniene vor fi:

(x3, x4) și (x4, x3) în C2

(x5, x6) și (x6, x5) în C3

Cercetăm legăturile între ultimul vârf din DH1 și DH2 din C1, și primul vârf din componentele ce urmează în DH*, anume C2, apoi între ultimul vârf din C2 și primul din componenta ce sfârșește DH* în G*, adică, C3. Avem schema din tabelul 3.3.19.

Tabelul 3.3.19.

Rezultă două drumuri hamiltoniene pentru graful inițial:

DH1=(x10, x7, x8, x1, x9, x2, x3, x4, x5, x6),

de valoare egală cu 40 ore,

DH2=(x10, x7, x8, x1, x9, x2, x3, x4, x5, x6)

de valoare egală cu 41 ore, deci trebuie ales raliul pe drumul dat de DH1.

CAPITOLUL 4

CONSIDERAȚII METODICE

4.1. Obiectivele generale ale disciplinei informatică

Transformările societății românești din ultimii ani, dezvoltarea și răspândirea informaticii, pătrunderea hardware-ului și software-ului modem in viața economică, socială și în învățământ, impun o pregătire diversificată a tinerilor în acest domeniu. Învățământul preuniversitar de informatică trebuie să asigure dobândirea, fie a unor cunoștințe de informatică la nivel de cultură generală, necesare continuării studiului, fie a unor cunoștințe având caracter aplicativ la un nivel mediu de profesionalism care să asigure posibilitatea găsirii unui loc de muncă.

Toți tinerii trebuie să-și asigure un minim de cunoștințe de tehnologia informației, necesare utilizării calculatoarelor în rezolvarea problemelor profesionale în diversele domenii ale vieții economice. Indiferent dacă vor absolvi sau nu o instituție de învățământ superior, vor avea extrem de mult de câștigat dacă vor avea cunoștințe de informatică, reușind astfel să corespundă cerințelor pe care locurile de muncă ale prezentului și viitorului apropiat le vor ridica în fața lor.

Obiectivele generale ale disciplinei informatică în învățământul preuniversitar sunt:

a) Pornind de la faptul ca nu există domeniu de activitate unde să nu se prelucreze și să nu se transmită informații atât în cadrul domeniului respectiv cât și spre exteriorul lui, afirmăm că azi informația este foarte valoroasă ea trebuie stocată, prelucrată și transmisă în condiții care asigură corectitudine și exactitate, deci la nivel profesional. Rezultă direct ca unul din obiectivele învățământului de informatică trebuie să fie asigurarea înțelegerii tuturor problemelor legate de informație și de stocarea, prelucrarea, respectiv transmiterea ei.

b) Dezvoltarea deprinderilor moderne de utilizator, adică pregătirea elevilor astfel încât să poată beneficia de lumea calculatoarelor, respectiv să poată folosi posibilitățile asigurate de cultura informatică, trebuie să stea în atenția învățământului preuniversitar. Aceasta presupune identificarea și înțelegerea principalelor componente ale calculatorului, precum și a funcționării rețelelor de calculatoare. Elevii trebuie să cunoască interfețele utilizator ale sistemelor de operare și ale celor mai răspândite utilitare, modul de instalare, exploatare și utilizare a acestora, să dobândească deprinderi necesare cunoașterii și folosirii oricărui software nou, precum și a versiunilor noi pentru cel existent.

c) Dezvoltarea gândirii algoritmice este un obiectiv la realizarea căruia informatica are o contribuție esențială și eficientă. Asemenea matematicii, informatica dezvoltă gândirea în general și are în școală, dar și în viața de zi cu zi, un rol esențial în procesul de învățare, în formarea caracterului și a personalității. Dar informatica (în plus față de matematică) dezvoltă gândirea algoritmică diferită de gândirea matematică (preponderent teoretică și abstractă) prin faptul că obligă elevii să finalizeze rezolvări ale unor aplicații practice concrete. Această gândire nu se leagă doar de cunoștințele de programare, ci și de cunoștințe referitoare la gestionarea bazelor de date, la utilizarea tabelatoarelor, editoarelor de texte, etc. Demonstrarea teoretică a existenței unei soluții pentru o problemă dată (ca în matematică) chiar dacă este importantă, nu este echivalentă cu rezolvarea problemei specificate. Este nevoie de dezvoltarea concrete de a rezolva probleme.

d) Dezvoltarea deprinderilor necesare muncii individuale se realizează într-un proces firesc, în dialog cu calculatorul. Acesta este un instrument care reacționează imediat la încercările elevului și care totodată nu își pierde răbdarea niciodată, oferă șansa unei învățări conform ritmului propriu al fiecăruia, oferă posibilitatea lucrului diferențiat cu elevi talentații sau cu cei care lucrează mai lent.

Informatica este esențial legată de lucrul individual cu un calculator, deci dezvoltă într-un mod firesc deprinderea de a lucra individual. Din nefericire, aceasta poate conduce la formarea unor trăsături cum ar fi individualismul sau egoismul. Aici intervine esențial rolul profesorilor: să încurajeze și să organizeze activitate în grupuri.

e) Prin folosirea rețelelor de calculatoare a apărut posibilitatea unui schimb de informație între utilizatorii de calculatoare, mult mai eficient decât cel clasic (poștă, telefon, telex etc.). Educarea elevilor în spiritul unei activități desfășurate în grup, în colaborare, se finalizează prin predarea informaticii orientată pe proiecte. Realizarea unor aplicații mai complexe impune lucrul în grup, modularizarea programului și păstrarea contactelor cu ceilalți membri ai grupului. în viața reală majoritatea activităților nu se desfășoară izolat, de aceea profesorii trebuie să stimuleze acest fel de activități. Proiectele trebuie să fie împărțite în activități repartizate pe individ, interconectate și elevii trebuie învățați să preia și să transmită informații respectând anumite specificații. Evident, profesorul are rol de supervizor.

Obișnuirea elevilor cu diverse responsabilități, cu răspunderea privind finalizarea propriei munci și asigurarea înlănțuirii unor elemente realizate în paralel, îi va pregăti pentru o activitate pe care cu siguranță o vor întâlni în viitor.

f) Este important ca elevii să fie capabili să aleagă din instrumentarul existent pe cel de care au nevoie, să identifice și să folosească software-ul cel mai potrivit aplicației pe care o realizează.

Rezultă că trebuie să fie capabili să analizeze problema să descopere cerințele și să decidă ce software și ce instrumente ale acestuia sunt cele mai utile. Pe de altă parte, pentru ca elevul să poate „alege” ceva, el trebuie să afle măcar de existența și caracteristicile esențiale mai multor tipuri de software.

g) Educarea elevilor, urmărind atent dezvoltarea spiritului inventiv și creator, se realizează în mai multe sensuri în cadrul disciplinei informatică. Indiferent de conținutul programului, sau al aplicației, ceea ce realizează elevul trebuie să funcționeze, trebuie să fie utilizabil; altfel spus, trebuie să aibă toate calitățile unui produs finit. Aceste cerințe in informatică se concretizează prin:

– interfața prietenoasa;

– asigurarea funcționării aplicației în mod inteligibil chiar și în cazul unui utilizator neautorizat, sau al unuia care nu cunoaște aplicația;

– fiabilitate; aplicațiile trebuie verificate și testate;

– performanță; analiza complexității ( în cazul algoritmilor) și a eficienței (în cazul aplicațiilor nealgoritmice) trebuie să devină obișnuință;

– portabilitate.

h) În liceu, informatica trebuie să pornească de la un nivel de bază, incluzând Tehnologia Informaticii. La acest nivel, nu putem spune că informatică este o disciplină izolată sau independentă. Un scop important este ca elevii să știe să folosească tehnologia informației pentru a rezolva diverse probleme. Astfel, profesorii altor discipline pot prezenta sau solicita realizarea unor aplicații de tip software educațional, deci elevii ar trebui să știe să utilizeze cunoștințele dobândite la orele de informatică, realizând la rândul lor, instrumente noi, care se pot folosi în cadrul altor lecții.

4.2. Metode didactice specifice învățământului de informatică

Metodele de învățare sunt modalități de lucru de care profesorii și elevii se folosesc în activitatea didactică. O metodă de învățare este o structură de procedee, un program potrivit căruia se reglează acțiunile practice și intelectuale întreprinse cu elevii în vederea realizării obiectivelor pedagogice.

Procedeul este un detaliu al metodei cu diferite funcții în procesul predării-învățării: înlătură obstacolele de înțelegere, stimulează și motivează elevul, previne oboseala, monotonia etc.

Funcțiile metodelor de învățare:

Funcția de transmitere și însușire a cunoștințelor. Prin metodele de învățare se asigură transferul experienței, al valorilor de la societate la elev.

Funcția formativ-educativă. O metodă de învățare se folosește în măsura în care aceasta contribuie la formarea anumitor abilități, capacități de ordin intelectual, afectiv sau psihomotor, contribuie la dezvoltarea anumitor trăsături de personalitate ale elevilor cu care profesorul lucrează.

Funcția normativ-instrumentală. Metodele orientează activitatea didactică, arată cum trebuie procedat pentru ca obiectivele activității să fie realizate, să se transpună în performanțe ale elevilor.

Funcția motivațională. Prin metodele de învățare folosite, profesorul stârnește curiozitatea și dezvoltă interesele de cunoaștere, de autodepășire ale elevilor.

Metodele creează suportul motivațional al învățării.

Sarcinile didactice se realizează cu ajutorul metodelor, tehnicilor și procedeelor didactice. Folosirea judicioasă a metodelor are o deosebită importanță pentru reușita activității de la catedră; pe de altă parte, conținuturile fiecărei discipline și obiectivele pe care și le propune să le îndeplinească, pretind metode adecvate. Adoptarea și nu adaptarea metodelor de predare ale unor discipline la alte discipline pot conduce la rezultate contradictorii.

Cert este că informatica poate adapta metode de predare de la alte discipline, dar adaptarea trebuie să se facă ținând cont de:

– dinamica conținuturilor și particularitățile metodice ale predării disciplinei;

– individualizarea învățării informaticii, ca disciplină deschisă și dinamică;

– activismul care pretinde o participare prioritară conștientă a elevului la procesul de autoinstruire;

– studiul informaticii atât ca disciplină autonomă, cât și ca instrument operațional al altor discipline.

În cele ce urmează se vor analiza metodele utilizate în predarea informaticii: expunerea, conversația, problematizarea, modelarea, demonstrarea folosind materialul intuitiv, exercițiul, învățarea pe grupe mici, munca cu manualul, jocurile didactice, asaltul de idei (brainstorming), instruirea programată.

În tratarea acestor metode se vor urmări cu predilecție particularitățile specifice predării disciplinelor de informatică și în special, aplicațiile practice de laborator și contribuția informaticii la realizarea obiectivelor didactice ale disciplinelor în învățământul preuniversitar.

4.2.1. Expunerea sistematică a cunoștințelor

Dintre formele pe care le îmbracă expunerea sistematică a cunoștințelor (povestirea, prelegerea, descrierea, explicația, conversația etc.), opinăm că informatica utilizează cu precădere explicația. Elementele explicative domină procesul de instruire informatică, acestea fiind caracteristice atingerii unor obiective de referință care cuprind formarea de deprinderi și abilități practice de utilizare a unor produse soft deseori complicate și dominate de interfețe „neprietenoase" față de utilizator (netransparente). Ceea ce conferă o accentuată notă de adaptabilitate este operativitatea impusă de aplicarea acestei metode prin alternarea expunerii cu demonstrația practică, elevii fiind astfel scoși din pasivitatea posturii de simpli receptori. Analogiile cu situații cunoscute fac din receptorul pasiv un participant activ la expunere. Expunerea nu se desfășoară în condiții perfect univoce, adică fără alternative și reveniri, nici la disciplinele cărora metoda le este caracteristică. La informatică, aceasta se întâmplă cu atât mai puțin. Elevul primește în condiții univoce doar ceea ce i se comunică în funcție de nivelul de cunoștințe dobândit, de propriile-i presupuneri, de experiența sa practică, de nivelul său de gândire, de înțelegerea codului de comunicație, ca să nu mai vorbim de oscilațiile de atenție. Profesorul trebuie să reproiecteze lecția prin prisma posibilităților elevilor și cu mijloacele lor de gândire. Accentul trebuie pus pe raționament, prin argumentări temeinice, prin scoaterea în evidență a modului în care trebuie să gândească. Expunerea trebuie să fie însoțită de un control permanent al gradului de receptivitate al clasei, urmărindu-se mimica elevilor (edificatoare în special la elevii mici), satisfacția înțelegerii lecției sau îngrijorarea și neliniștea în cazul în care elevul a pierdut firul explicației citindu-se pe fața elevilor, întrebările, repetiția, explicațiile suplimentare, analogiile cu alte noțiuni cunoscute permit realizarea unui control permanent al receptivității la expunere. În informatică recurgem neapărat la metoda expunerii (explicației) atunci când tema este complet nouă și printr-o metodă activă nu se poate descoperi noutatea sau metoda activă este ineficientă din punctul de vedere al operativității. Astfel, este necesară această metodă pentru a înțelege noțiunea de algoritm (inclusiv exemplificările clasice), de structură de date (inclusiv exemplificările clasice), de structură de date (inclusiv modalitățile de reprezentare), de comandă, funcție sau procedură standard (în legătură cu sistemul de operare sau mediul de programare ales), de raționament (într-un spațiu închis ales) și chiar a modalității de prezentare și introducere a unor programe utilitare, softuri de aplicație etc. În acest context, pentru reprezentarea comenzilor unui sistem de operare, a unui editor de texte (sau grafic), a altor softuri mai complicate (prevăzute de programa școlară) se poate recurge la următoarele (sub)metode:

• Expunerea (la tablă, prin slide-uri pe retroproiector sau prin PowerPoint) cu „desenarea" meniurilor și prezentarea funcțiilor fiecărei opțiuni, urmând ca elevul (prin aplicațiile de laborator) să exerseze fiecare funcție în parte, individual sau în grupe mici de lucru.

• Prezentarea meniurilor și funcțiilor fiecărei opțiuni simultan cu exersarea acestora în cadrul orelor de aplicații practice de laborator.

• Prezentarea meniurilor și funcțiilor fiecărei opțiuni simultan cu demonstrarea practică în momentul prezentării lor de către profesor, sarcina elevului fiind numai aceea de a urmări și reține modul de executare a operațiilor prezentate de profesor, urmând ca elevul să aplice cunoștințele dobândite în cadrul orelor de laborator, în aplicații ample (integrate, de dorit, într-un mediu economic clar), care necesită utilizarea în mod repetat și în situații diferite a funcțiilor fiecărei opțiuni din meniul discutat.

Fiecare dintre variantele de mai sus au avantajele și dezavantajele lor. Prima variantă este cel mai des folosită deoarece, de regulă, profesorul nu are la dispoziție un laborator și pentru predare (iar aceasta se face cu întreaga clasă). Ea prezintă dezavantajul că elevul „nu vede pe viu" efectul executării fiecărei opțiuni (profesorul fiind nevoit în acest caz să-1 descrie în cuvinte), dinamica transformării și efectul video al acestora fiind greu de redat în cuvinte. Singurul avantaj este cel al obținerii de către elev a unui rezumat logic și coerent după care se va ghida în timpul realizării unor aplicații practice. A doua variantă înlătură dezavantajul neobservării pe viu a efectului executării fiecărei opțiuni, dar atenția elevului este îndreptată spre realizarea practică (simultan cu comunicarea modului de realizare a funcțiilor opțiunilor din meniuri). Astfel, o parte dintre funcții sunt abordate prea „abrupt" sau sunt chiar omise, iar altele sunt exersate prea mult. La acest dezavantaj se adaugă și reducerea randamentului prin faptul că profesorul trebuie să urmărească modul în care fiecare elev sau fiecare grupă aplică funcția prezentată și să intervină ori de câte ori un elev sau o grupă este în impas. În plus, unii elevi își formează mai repede deprinderea utilizării, iar alții mai greu, primii fiind tentați să încerce între timp alte opțiuni (chiar neprezentate încă de către profesor), ceea ce creează disfuncționalități în desfășurarea lecției, aprecierea gradului de asimilare și chiar formarea unor idei greșite de utilizare (datorate încercărilor individuale, necoordonate). Pe lângă acestea, se pierde din vedere și realizarea unui rezumat sistematic al modului de optimizare, elevul fiind tentat să exerseze imediat funcția și uită să-și noteze „în stil propriu" modul de utilizare a acesteia. Ultima variantă pare să cumuleze toate avantajele celor anterioare prin faptul că elevul urmărește și reține (neavând alte preocupări care să-i distragă atenția) modul în care profesorul execută (corect) și explică simultan, elevii putând nota tot ce acesta prezintă. Este o manieră de expunere ce înlătură formarea unor deprinderi greșite, mărind randamentul la predare și asimilarea noilor cunoștințe. Această variantă are însă și un dezavantaj: necesitatea existării unei dotări speciale, care să permită observarea în bune condiții, de către toți elevii clasei, a ecranului calculatorului pe care profesorul face demonstrația. Utilizarea unui retroproiector sau a unui videoproiector are multe inconveniente (în afară de costul ridicat), printre care faptul că trebuie să existe anumite condiții de mediu specifice în sala de clasă. De exemplu, pentru grupe mici poate fi folosit numai calculatorul ca atare, dacă elevii pot fi așezați în preajma acestuia astfel încât fiecare să poată observa fără efort ecranul. Indiferent de conținutul lecției, metoda expunerii nu se folosește singură decât foarte rar pe parcursul unei ore întregi, aceasta alternând cu alte metode de predare. Pe de altă parte, există o tendință accentuată a cadrelor didactice de a nu-și propune aprioric folosirea cu precădere a nici unei metode, ceea ce este foarte dăunător.

4.2.2. Metoda conversației

Metoda conversației se referă la dialogul dintre profesor și elev, în care profesorul nu trebuie să apară în rolul examinatorului permanent, ci în rolul unui colaborator care nu numai întreabă, ci și răspunde la întrebările elevilor. Prin metoda conversației se stimulează gândirea elevilor în vederea însușirii, fixării și sistematizării cunoștințelor și deprinderilor, în vederea dezvoltării spiritului de colaborare și de echipă. Se asigură astfel o participare activă din partea elevilor, întrebările putând fi adresate (teoretic) în orice moment al lecției. Metoda conversației este frecvent utilizată în învățarea informaticii, ea implicând un dialog continuu între elev și profesor, respectându-se anumite reguli elementare de colaborare constructivă care să nu determine diminuarea demersului didactic, ci să-l amplifice și să-l consolideze. Conversația didactică poate îmbrăca forme diferite, în funcție de anumite criterii. În funcție de numărul de persoane, ea poate fi:

Individuală. Se poartă între elev și profesor.

Colectivă sau frontală. Întrebările sunt adresate întregii clase, iar răspunsurile “vin” de la diferiți elevi.

După obiectivele urmărite în diferite variante de lecții, conversația poate fi:

• Introductivă. Aceasta este folosită în momentul captării atenției și reactualizării
cunoștințelor asimilate anterior, pentru a trezi interesul pentru lecția care urmează.

• Expozitivă. În timpul prezentării unei noi lecții, ea poate trezi interesul pentru
fixarea noilor cunoștințe.

Recapitulativă. Este utilizată atunci când se urmărește recapitularea și generalizarea unor rezultate prezentate anterior.

Evaluativă. Este indicată, desigur, pe parcursul procesului de evaluare și verificare.

Dezvoltată. Este destinată prezentării unui nou subiect, nu complet necunoscut.

Caracteristicile principale ale întrebărilor, indiferent de forma de conversație, impun precizie și vizarea unui singur răspuns. De multe ori se pun întrebări vagi, care încep cu „Ce puteți spune despre…" sau „Ce știți despre…", care plasează elevul într-un dubiu total în legătură cu conținutul răspunsului. Din aceeași gamă face parte și celebrul îndemn de evaluare “Prezintă subiectul pe care-l cunoști tu cel mai bine”. Nu este normal ca întrebarea să conțină răspunsul sau să ceară un răspuns prin „da" sau „nu". Ea contribuie la dezvoltarea gândirii. De asemenea, răspunsurile acceptate trebuie să fie corecte, complete, exprimate în termeni preciși, să oglindească o înțelegere efectivă a problemei abordate. Discuțiile au și rolul de a corecta greșelile din răspuns. Identificarea cauzei, eliminarea greșelii, cât și posibilitatea reapariției ei sunt foarte importante. Conversația are un rol primordial prin faptul că ajută la formarea limbajului informatic, la dezvoltarea raționamentului logic și a gândirii elevului. Dificultățile pe care elevul le întâmpină în formarea limbajului de specialitate pot lăsa urme în plan afectiv, repercutându-se asupra dezvoltării lui intelectuale. De aceea se impune o analiză amănunțită a cauzelor acestor dificultăți, iar scoaterea lor în evidență trebuie relevată prin examinări (scrise, orale, reprezentări schematice, utilizarea simbolurilor specifice). A fi la curent cu dificultățile de limbaj pe care le au elevii la anumite vârste școlare și la un anumit stadiu de însușire al disciplinei înseamnă în primul rând să nu se abuzeze de termeni de specialitate (înlocuindu-i cu termeni sinonimi din vocabularul curent sau explicându-le sensul, dacă un alt înțeles al termenului este accesibil). Dificultatea formării vocabularului de specialitate constă și în faptul că aceste cuvinte noi sunt introduse în același timp cu introducerea noțiunilor noi, ceea ce face ca îmbogățirea limbajului informatic să se facă simultan cu dezvoltarea și formarea gândirii informatice. Stăpânirea limbajului se reflectă în rezolvarea problemelor și înțelegerea textelor și documentațiilor de specialitate. Nestăpânirea acestuia provoacă inhibiție, imposibilitatea comunicării sau chiar o comunicare și o înțelegere defectuoasă, făcându-1 pe elev timid, incoerent sau chiar ridicol în exprimare. Această metodă mai are și următoarele subdirecții:

Euristică. Nu există reguli precise, se bazează doar pe întrebare/răspuns, în
funcție de evoluția concretă a dialogului.

Tip dezbatere. Se realizează un schimb de păreri în care este implicat un anumit
colectiv. Ar fi bine să fie trase și niște concluzii care să nu aibă doar un rol istoric.

Catehetică. Aceasta impune efectuarea unor teste care implică memoria.

Este clar că o conversație se face prin întrebări. În plus, acestea trebuie să satisfacă următoarele condiții (unele dintre ele rezultă din ceea ce am amintit mai înainte):

Să fie precise (vizând un singur răspuns)

Să nu conțină răspunsul și să aibă un rol instructiv.

Să stimuleze gândirea și capacitatea de creativitate a elevilor („De ce?", „Din ce cauză?" etc.)

Să fie formulate prin enunțuri variate și „atrăgătoare".

Să se adreseze întregului colectiv vizat.

• Să conțină întrebări ajutătoare atunci când răspunsul este eronat sau parțial.
Răspunsurile acceptate trebuie să fie nu numai corecte, ci și exprimate în termeni

preciși și să oglindească un anumit nivel de înțelegere. Răspunsurile eronate trebuie corectate imediat, prin discuții individuale. Cadrul didactic trebuie să dirijeze conversația astfel încât ideile să fie bine conturate înainte de a trece la altele, în timp ce lecția își menține caracterul unitar. În ceea ce privește informatica, recomandăm și utilizarea unor instrumente ajutătoare, ca de exemplu introducerea/exprimarea noțiunilor printr-un „limbaj de programare" (scris/oral) care să implice utilizarea eficientă a simbolurilor (în afară de latura didactică propriu-zisă), ceea ce înseamnă separarea clară a sintaxei de semantică.

4.2.3. Problematizarea și învățarea prin descoperire

Predarea și învățarea prin problematizare și descoperire presupun utilizarea unor tehnici care să producă elevului conștientizarea „conflictului” dintre informația dobândită și o nouă informație, determinându-l să acționeze în direcția lichidării acestuia prin descoperirea unor (noi) proprietăți ale fenomenului studiat. Pedagogic vorbind, conflictele se mai numesc și situații-problemă, putând fi de cel puțin două tipuri:

Contradicții între posibilitățile existente ale elevului (nivelul intelectual și de pregătire) și cerințele, situațiile în care este pus de noua problemă. Aceste conflicte se datorează imposibilității elevului de a selecta dintre cunoștințele sale anterioare pe cele potrivite cu valoarea operațională de aplicabilitate a viitorului.

Incapacitatea elevului de a integra noțiunile selectate într-un sistem, în același timp
cu conștientizarea faptului că sistemul este pe moment ineficient operațional (lucru care poate fi remediat doar prin completarea informației de bază).

Întrebările frontale sau individuale utilizate în etapa de pregătire a introducerii unei noțiuni, a prezentării unui domeniu nou, întrebări care se adresează capacității de reacționare a individului, pot genera noi situații conflictuale de tipul menționat anterior. Pe cât posibil, cadrul didactic trebuie să gestioneze el însuși apariția situațiilor-problemă. La modul ideal, ele trebuie să apară de la sine în mintea elevului. Relativ la condițiile pedagogice ale acestor situații conflictuale generate de anumite probleme practice putem spune că problemele trebuie să aibă un sens precis și să fie enunțate într-un moment „optim" al lecției. Ele trebuie să înglobeze cunoștințe anterior însușite de elev, să le trezească interesul, să le solicite un anumit efort mental creator. Există părerea că rezolvarea problemei poate fi privită ca un proces prin care elevul descoperă că o combinație de reguli învățate anterior se poate aplica pentru găsirea soluției unei noi situații conflictuale. În acest sens se pot evidenția următoarele etape în rezolvarea problemei:

– Prezentarea problemei (verbal, scris, grafic etc.)

– Definirea problemei de către elev în sensul distingerii caracteristicilor esențiale ale situației, însușirii enunțului, găsirii legăturii între date, informații etc.

– Formularea de către elev a anumitor criterii, ipoteze care pot fi aplicate în vederea găsirii unei soluții. Verificarea succesivă a unor asemenea ipoteze, eventual și a altora noi și găsirea efectivă a unei soluții (sau a tuturor).

Desigur că în contextul de mai sus expresiile situație conflictuală, problemă, rezolvare de problemă se referă la probleme și soluții noi, necunoscute încă de elev, și nu la ceva de tipul substituirii de valori numerice în expresii date, execuția unui program dat pentru niște valori de intrare etc. Utilizarea în predare a acestei metode este totdeauna utilă în momentul în care se găsește și rezolvarea conflictului.

Descoperirea apare ca o întregire a problematizării. Se pot pune astfel în evidență trei modalități principale de învățare prin problematizare și descoperire (clasificarea făcându-se după tipul de raționament folosit):

Modalitatea inductivă;

Modalitatea deductivă;

Modalitatea prin analogie.

În primul caz este vorba de generalizări. Elevul trebuie să-și dezvolte propria cale de învățare, care să nu contrazică lucrurile în care deja „crede", prin folosirea unor mijloace tehnice și resurse informaționale personale. În al doilea caz se folosește logica sau, mai exact, sistemele deductive (ca metodă de raționament). Putem deriva cunoștințe noi din cunoștințe vechi (cu ajutorul unor reguli de inferență specifice). În ultimul caz, se încurajează folosirea unei experiențe anterioare nu numai dintr-un domeniu conex, ci chiar din domenii total diferite.

Problematizarea are astfel inferențe cu conversația, întrebările individuale sau frontale adresate gândirii, raționamentului născând situații conflictuale. Generarea situațiilor-problemă trebuie produsă astfel încât întrebările să apară în mintea elevului, fără ca acestea să fie puse de către profesor. După cum am mai precizat, ca disciplină cu caracter formativ, informatica își propune formarea unei gândiri algoritmice, sistematice și riguroase, care să promoveze creativitatea, să stimuleze imaginația și să combată rutina. Chiar dacă aparent travaliul informatic se sprijină pe anumite șabloane, acestea reprezintă numai tendințe utile de standardizare. Procesele care izvorăsc din situații reale, care implică folosirea calculatorului în rezolvarea unor probleme aparținând diferitelor sfere ale vieții de zi cu zi, analiza acestor probleme, alegerea structurilor de date pe care se mulează informația oferită de mediul înconjurător, pașii algoritmilor și programarea în sine determină folosirea metodei problematizării, iar aplicarea acestei metode necesită formarea unor deprinderi ce nu se obțin decât printr-un exercițiu îndelungat. Rezolvarea de probleme, ceva curent în învățarea informaticii, poate fi privită ca un proces prin care elevul descoperă că o altă combinație de reguli învățate anterior conduc la rezolvarea unei noi situații problematice. Formularea de probleme de către elevii înșiși constituie forme ale creativității și presupune că elevii și-au format deprinderi intelectuale eficiente din punctul de vedere al generalizării și aplicabilității (orice soluție generează o nouă problemă). Problemele propuse pot fi inspirate din viața cotidiană, din cunoștințele dobândite prin studiul altor discipline, din generalizarea unor probleme de informatică rezolvate anterior, probleme de perspicacitate, jocuri etc. Problematizarea și descoperirea fac parte din metodele formativ-participative, care solicită gândirea creatoare a elevului, îi pun la încercare voința, îi dezvoltă imaginația, îi îmbogățesc experiența. În lecțiile în care se aplică aceste metode profesorul alege problemele, le formulează, dirijează învățarea și controlează munca depusă de elev în toate etapele activității sale. Această metodă este caracteristică, de exemplu, unor lecții de aplicații practice de laborator, metoda învățării prin descoperire fiind frecvent aplicată în momentul în care este necesară folosirea programelor utilitare, a softurilor de aplicație etc. Utilitarele se abordează în funcție de problemele concrete care urmează a fi rezolvate. Obiectivul imediat este cunoașterea și exploatarea produsului, nu îmbunătățirea lui. Concentrarea atenției va fi dirijată spre rezolvarea problemei și nu asupra analizei facilităților și lipsurilor produsului de software. Cu siguranță, în acest caz este deosebit de importantă experiența dobândită, cunoștințele și deprinderile formate în alte situații similare de învățare: lucrul cu meniuri, funcții comune mai multor utilitare, cunoașterea structurilor de date, dexteritatea în tehnoredactare etc. Cunoașterea facilităților produsului soft se face în momentul ivirii necesității exploatării acestuia și nu printr-o prezentare a lui ca o înșiruire mai mult sau mai puțin sistematică și completă de funcții sau facilități. Bineînțeles că este obligatorie o prezentare generală a utilitarului. În contextul altor produse similare, trebuie concepută o viziune de ansamblu din care să se desprindă caracteristicile dominante ale utilitarelor din clasa respectivă și să se prezinte particularitățile specifice produsului, cu îmbunătățiri față de versiunile anterioare și perspective de dezvoltare pentru cele viitoare.

Ca informaticieni, ne interesează (în acest context) ceea ce numim rezolvarea problemelor (problem solving). Îndemânările dobândite în legătură cu acest subiect depind în primul rând de cunoștințele specifice acumulate, dar din punctul de vedere al psihologiei există acordul că se pot căpăta și „îndemânări generale". Procesul cognitiv în ansamblu este foarte complicat, numai pentru explicarea coerentă a acestuia fiind necesară o întreagă carte. Vom sublinia doar câteva elemente-cheie și direcții principale pentru abordarea rezolvării unor probleme. Astfel, când dorim să rezolvăm o problemă cu ajutorul calculatorului, presupunând că enunțul este „acceptat", trebuie să ne întrebăm în primul rând:

Ce știm în legătură cu domeniul implicat?

Cum sunt apreciate pe piață rezultatele?

Care strategii generale sunt aplicabile?

Care sunt motivațiile suplimentare?

După ce problema a fost enunțată și sunt furnizate anumite indicații suplimentare, putem trece la alegerea strategiei concrete de rezolvare. Aceasta trebuie să fie selectată după un anumit plan, să permită un anumit tip de verificare și generalizare. De asemenea, trebuie avute în vedere metode sau metodologii prin care să se interzică anumite „ramuri" și să se permită explorarea de direcții colaterale. Una dintre strategiile generale poate fi următoarea:

Pot să rezolv problema (am cunoștințele necesare).

Definesc în mod (semi)formal.

Caut informațiile suplimentare astfel încât să am o definiție formală concretă
(eventual, chiar într-un limbaj de programare concret).

Fac planul de implementare.

Îl execut (scriu „programele" și le „rulez").

Verific faptul că ceea ce am făcut este „corect".

Generalizez (la alte cazuri, la alte probleme).

Peste tot, cunoașterea măcar a unei părți din logica formală este indispensabilă.

4.2.4. Modelarea

Modelarea ca metodă pedagogică poate fi descrisă ca fiind un mod de lucru prin care gândirea elevului este condusă la descoperirea adevărului, folosind un așa-numit model și utilizându-se raționamentul prin analogie. Modelul și metoda în sine nu presupun o asemănare perfectă cu cazurile reale inițial specificate, ci numai cu o analogie rezonabilă. Ea constă în construirea unui sistem s1 a cărui descriere coincide cu descrierea sistemului original s; până la un anumit punct, s1 poate avea o natură diferită și este în general mai simplificat și formalizat. Ideea este că, investigând sistemul s1 prin metode specifice legate de o anumită temă de lecție, se pot găsi noi soluții, care apoi pot fi translatate în concluzii asupra sistemului de bază. Modelarea are o mare valoare euristică colaterală, prin utilizarea ei putându-se dezvolta spiritul de observație, capacitatea de analiză și sinteză, creativitatea. Ideea ar fi să putem determina elevii să descopere singuri modelul. Astfel elevul se obișnuiește să creeze noi probleme ce trebuie rezolvate, să adapteze algoritmi cunoscuți la situații noi etc. Realitatea înconjurătoare este percepută și înțeleasă pe baza unor modele deja cunoscute. Dezvoltarea deprinderilor de modelare, obișnuirea elevilor cu gândirea logică se realizează prin prezentarea exactă și clară a modelelor și prin transparența particularizărilor. Un exemplu edificator îl constituie învățarea metodelor de elaborare a algoritmilor. Necesitatea unor formalizări se impune prin rigoarea modului de abordare a problemei, prin sistematizarea organizării informației de intrare, a exactității proiectării prelucrării și prin standardizarea ieșirii. Formalizarea necesită cunoștințe dobândite în studiul altor discipline, fundamentate teoretic, iar accesibilitatea formalizării este condiționată de factori specifici nivelului de cunoștințe dobândite anterior, de categoria de vârstă, de capacitatea de asimilare. Abordarea ponderată a acestor aspecte conduce la dezvoltarea deprinderilor de abstractizare, a gândirii algoritmice și sistemice. Utilizarea modelelor în realizarea algoritmilor presupune stabilirea unor analogii și în organizarea datelor de intrare. Învățarea algoritmilor este legată de cunoașterea modului de organizare a datelor, de cunoașterea profundă a structurilor de date posibile a fi prelucrate ușor de către calculator. Etapa cea mai importantă este cea a descoperirii algoritmului, urmată de stabilirea modului de organizare a datelor, dar importanța acestui ultim aspect este esențială în determinarea performanțelor produsului program care implementează algoritmul. Modelarea (ca metodă pedagogică) este definită ca un mod de lucru prin care gândirea elevului este condusă la descoperirea adevărului cu ajutorul modelului, grație raționamentului prin analogie. Modelarea similară constă în realizarea unui sistem de aceeași natură cu originalul care să permită evidențierea trăsăturilor esențiale ale originalului. O gamă variată de probleme sunt rezolvate prin metoda Backtracking. Pentru implementarea într-un limbaj de programare a unui algoritm implementat prin Backtracking, elevul are nevoie de un model reprezentat de un program, cum ar fi cel de generare a permutărilor sau de rezolvare a problemei celor opt dame și, prin mici modificări, el poate obține multe alte programe care implementează algoritmi ce rezolvă probleme clasice, cum ar fi: generarea aranjamentelor, combinărilor, problema parantezelor, partițiile unei mulțimi, problema celor opt turnuri etc. Similar se procedează în rezolvarea problemelor care necesită utilizarea stivelor sau cozilor, folosind operațiile elementare cu elementele acestor structuri dinamice elementare. Modelarea analogică nu presupune o asemănare perfectă cu originalul, ci numai folosirea unei analogii. Modelele cunoașterii în procesul modelării sunt:

Trecerea de la original la model;

Transformarea modelului sau experimentarea pe model;

Transferul pe original a rezultatelor obținute pe model;

Verificarea experimentală pe original a proprietăților obținute pe model.
Trecerea de la original la model se face prin simplificare. Se impune ca simplificarea să nu fie exagerată, pentru a nu se omite trăsăturile esențiale ale originalului. Totodată, trebuie să nu se scape din vedere că valoarea modelului va fi apreciată prin prisma eficacității lui, adică a posibilităților pe care le oferă pentru atingerea scopului și că noile informații obținute pe baza modelului vor fi transferate cu grijă asupra originalului, având în vedere diferența dintre model și original. Modelul devine astfel purtătorul unei semnificații, informații care poate fi exprimat printr-un suport material sau ideal. O clasificare a modelelor după natura suportului sub care se vehiculează informația poate fi:

Modele materiale, care au suport concret și care se folosesc foarte puțin în
învățarea informaticii: folosirea unei table de șah în rezolvarea problemei celor opt dame determină o rapidă înțelegere a mecanismului metodei Backtracking; utilizarea unei stive de monede de dimensiuni diferite pentru înțelegerea rezolvării problemei turnurilor din Hanoi. Nu trebuie exclusă posibilitatea învățării direct pe obiectul de studiu, caz întâlnit (și recomandat) în studiul structurii și arhitecturii sistemelor de calcul și a conexiunilor între ele, în contextul funcționalității ca un ansamblu (sistem), este esențială.

Modele ideale (virtuale), care se exprimă prin imagini, sisteme de simboluri sau semne convenționale.

Învățarea informaticii prin modelare presupune două etape. Într-o primă etapă, învățarea se va face pe baza modelelor construite „de profesori", etapă în care se vor analiza trăsăturile modelului și compararea lui cu originalul. Pentru a reliefa condițiile pe care trebuie să le îndeplinească modelul, se vor da și contraexemple. În a doua etapă, elevii vor fi deprinși să construiască singuri modele. Importanța descoperirii modelului de către elev constă în faptul că elevul este obișnuit să reprezinte într-o formă standard condițiile impuse de problemă și-și adâncește convingerea că informatica este un domeniu în care rezultatele pozitive se obțin doar printr-o înlănțuire logică de raționamente. Folosirea modelelor nu înseamnă impunerea unor metode care trebuie reținute și aplicate orbește. Se va pune accentul pe înțelegerea pașilor unui algoritm și se va încuraja prezentarea oricăror metode care exclud modelul și care se impun prin eleganță și eficiență. Elevii vor fi încurajați să-și dezvolte și să-și prezinte ideile proprii, contribuind astfel la creșterea încrederii în posibilitățile lor, în valoarea ideilor lor. Ei nu trebuie să fie obligați să reproducă ideile altora, să aștepte ca totul să fie prezentat de profesor, să asimileze rețete, ci să descopere metode noi, să le prezinte, analizeze și perfecționeze printr-o comunicare continuă și constructivă. Folosirea modelelor în învățare deschide pentru informatică o impresionantă arie de aplicabilitate (inclusiv utilizarea ei în predarea altor discipline, de la artele plastice la cele mai diverse domenii ale tehnicii).

4.2.5. Exemplificarea sau demonstrarea materialului intuitiv

Prin exemplificare sau demonstrație, în acest caz, înțelegem prezentarea sistematizată și organizată a unor obiecte, procese, experimente, cu scopul de a ușura înțelegerea intuitivă și executarea corectă a unor activități programate. Cuvântul intuiție din titlu înseamnă utilizarea oricărui raționament inductiv, în contextul temei și bagajului de cunoștințe ale elevului. Utilizarea intuiției împreună cu exemplificarea necesară poate implica folosirea a diverse modalități și tehnici didactice datorită diversității materialului de studiu. Exemplificarea sau demonstrarea materialului intuitiv presupune utilizarea obiectelor reale, cum ar fi: material grafic (planșe, scheme), retroproiector/videoproiector și material pretipărit, calculator (imagini grafice, multimedia, Power Point). În acest context, putem spune că: „Prin demonstrarea materialului intuitiv se înțelege prezentarea sistematică și organizată a unor obiecte, procese etc. sau producerea unor experiențe, fenomene în fața elevilor, cu scopul de a ușura înțelegerea și executarea corectă a unor activități". Un rol deosebit îl joacă astfel intuiția (intuiția este o experiență mentală; înseamnă o simplă observare și notare a unor fapte; intuiția poate fi asimilată cu un raționament de tip inductiv). Intuiția realizează corelația dintre imagine și cuvânt, fiind atât sursă de cunoștințe, cât și mijloc de verificare. Informatica nu poate fi desprinsă decât artificial de bazele ei intuitive și de extinderea ei în realitatea cotidiană. Convertirea principiului intuiției în metoda demonstrației se realizează în funcție de materialul intuitiv: machete, grafică, film didactic, televiziune școlară, software-uri de învățare.

Ținând cont de eficiența transmiterii informației prin mijloacele vizuale (inclusiv Internet) și de orientarea cu predilecție spre mijloacele de orientare rapidă care solicită atât memoria vizuală, cât și cea auditivă și formarea involuntară a unui public consumator de informație audio-video, o orientare a metodelor și procedeelor didactice în vederea exploatării acestei stări de lucruri creează un avantaj aparte procesului instructiv-educativ. Crearea unor filme (casete video) didactice care să urmărească cu exactitate programa școlară creează facilități de predare multor discipline și ar permite elevului să poată revizualiza predarea lecției. Aceasta ar putea elimina ambiguitățile sau golurile create de momentele de neatenție din timpul predării și ar constitui un veritabil profesor la purtător al elevului. Este evident că acest mijloc didactic nu poate înlocui (nici măcar suplini) exercițiul individual și nici prezența efectivă a cadrului didactic. Efortul profesorului este însă cu totul special. Nu este suficient ca un elev să vadă un material, el trebuie învățat să vadă. Pentru că în acest moment ar trebui să aducem în discuție euristicile și încurajarea creativității. Se pot pune în evidență chiar euristici pentru dezvoltarea creativității:

încercați să aveți cât mai multe idei. Cu cât sunt mai multe, cu atât puteți selecta câteva „bune".

„Inversați" (reformulați, reiterați, puneți într-un alt context) problema.

„Ghiciți" o soluție la întâmplare.

Gândiți-vă la ceva distractiv, apropos de utilizările posibile ale rezolvării.

Gândiți-vă la probleme similare și la soluțiile acestora, chiar în contexte diferite.

Concepeți o listă generală „explicativă" de cuvinte-cheie, proprietăți utile, stimulente, ș.a.m.d. care au cât de cât legătură cu tema în cauză.

4.2.6. Metoda exercițiului

La modul general, exercițiile pot fi privite ca acțiuni concrete efectuate conștient și repetat în scopul dobândirii unor priceperi și deprinderi (mai rar cunoștințe) noi, pentru a ușura anumite activități și a contribui la dezvoltarea unor aptitudini. Avantajele metodei exercițiului sunt:

-se poate forma o gândire productivă, creatoare, cu implicație financiară;

-se oferă posibilitatea câștigării unei anumite independențe;

-se oferă posibilitatea inițierii unui dialog-conversație cu obiective precise asupra unor metode și soluții;

-se activează atitudinea critică și poate crește discernământul elevilor în privința celor mai bune metode de lucru;

-se oferă profesorului o anumită posibilitate de a analiza și evalua activitatea sau performanțele generale ale unui elev.

Condiția primordială de reușită este dată în principal de selecția corespunzătoare a problemelor sau exercițiilor, precum și de activitatea de îndrumare-proiectare. Prin urmare, exercițiile sunt acțiuni efectuate în mod conștient și repetat de către elev cu scopul dobândirii unor priceperi și deprinderi și chiar cunoștințe noi, pentru a ușura alte activități și a contribui la dezvoltarea altor aptitudini. Însușirea cunoștințelor de informatică este organic legată de exersarea utilizării softului de aplicație, de rezolvarea unor probleme de programare etc. Nu există lecție în care să nu se aplice această metodă. Alte avantaje sunt concretizate în rezultatele aplicării ei: formează o gândire productivă, oferă posibilitatea muncii independente, oferă posibilitatea analizei diverselor metode și soluții de rezolvare a problemelor, activează simțul critic și autocritic și îi învață pe elevi să-și aprecieze rezultatele și metodele de lucru, oferă posibilitatea depistării și eliminării erorilor.

Este clar că metoda nu contribuie numai la formarea priceperilor și deprinderilor de lucru cu calculatorul, ci contribuie substanțial la formarea unui comportament flexibil și operant. Pentru profesor, alegerea, formularea și rezolvarea problemelor și apoi exploatarea rezultatelor obținute constituie o sarcină de importanță deosebită. Alegerea problemelor este condiționată de programa analitică, succesiunea prezentării noțiunilor în manuale, metodele de rezolvare ce pot fi folosite și de elevii cărora li se adresează. Formularea problemelor trebuie să țină cont de noțiunile cunoscute de elevi, să fie clară, concisă și să folosească limbajul de specialitate numai în măsura în care este cunoscut elevilor. Rezolvarea trebuie să aibă în vedere obținerea rezultatelor pe căi clare și ușor de verificat, reținerea tipurilor de raționamente folosite, deschiderea perspectivei pentru rezolvarea unor probleme analoage sau mai complexe. Folosirea rezultatelor obținute trebuie să vizeze lămurirea conținutului activ în cunoașterea noțiunilor învățate și adâncirea semnificației lor, asimilarea metodelor de rezolvare și aplicarea lor la rezolvarea altor probleme. Utilizarea pe scară largă a acestei metode a condus la clasificarea exercițiilor și problemelor în funcție de aportul capacităților intelectuale necesare rezolvării lor. În subsecțiunile care urmează insistăm asupra unor particularizări.

4.2.7. Probleme care permit însușirea unor noțiuni

Specifice informaticii sunt problemele al căror grad de dificultate crește treptat, odată cu formarea și asimilarea noțiunii, fiecare nouă problemă aducând un plus de dificultate. În rezolvarea unei probleme de programare este necesar să se țină cont de următoarele etape:

Analiza inițială a problemei prin care se stabilește formatul și natura datelor de
intrare, intervalele de variație a datelor de intrare, variabilele de lucru (date intermediare), precum și formatul și intervalele de variație a datelor de ieșire. Tot în această etapă se va stabili un algoritm (plan) de rezolvare, exprimat, eventual, în limbaj natural, pe baza căruia se va permite fiecărui elev să lucreze independent.

Rezolvarea propriu-zisă a problemei este etapa în care se realizează transpunerea într-un limbaj de programare a algoritmului stabilit în prima etapă. În prealabil, algoritmul este reprezentat într-una dintre formele cunoscute, se stabilesc variabilele de lucru, forma lor de alocare, prelucrările ce vor avea loc, apoi se trece la implementarea în limbajul dorit. Dacă rezolvarea se poate face pe mai multe căi, trebuie să se sublinieze, dacă este posibil, calea optimă.

Verificarea soluției sau soluțiilor obținute va permite elevului să-și dea seama dacă soluția obținută este cea corectă. În această etapă intervine profesorul cu seturi de date de test care să cuprindă, dacă este posibil, majoritatea (dacă nu toate) cazurilor ridicate de problemă și în special cazurile critice, la limită, ale datelor de intrare.

Aceste date cuprind în esență: însușirea enunțului, discutarea problemei și stabilirea algoritmului de rezolvare, rezolvarea propriu-zisă, verificarea soluțiilor. Ele se pot modifica după natura problemelor. Acolo unde problema permite mai multe căi de rezolvare, profesorul analizează toate aceste căi și le selectează pe cele mai importante, propunându-le spre rezolvare pe grupe, comparând rezultatele, avantajele și dezavantajele fiecărei metode în parte. Se va evidenția în mod obligatoriu cea mai bună soluție.

O posibilă clasificare a problemelor/exercițiilor (relativ la capacitățile intelectuale pentru rezolvare) ar fi:

• Exerciții de recunoaștere a unor noțiuni (unitate curentă de I/E, unitate de disc, memorie internă, comandă externă, programe executabile de tip .com sau .exe, HTTP-uri, telnet etc.)

• Exerciții aplicative (programe pentru transcrierea unor formule, pseudocoduri)
Aceste două clase de exerciții sunt recomandate în special pentru fixarea unor cunoștințe deja predate. În acest context poate fi utilă o complicare graduală a enunțului inițial, urmărindu-se memorarea mai bună a formulei sau a ideii algoritmului, cum ar fi: încadrarea acestuia într-un eventual alt tip de probleme cunoscute, complicarea lui în mod progresiv în vederea utilizării sale în alte situații, prezentarea unor cazuri-limită care pot conduce la rezultate eronate.

• Exerciții grafice – planșe, vizualizări

• Exerciții complexe – presupun o analiză mai detaliată a problemei în ansamblu și implică descompunerea problemei în subprobleme, succesiv, până în momentul în care rezolvarea subproblemelor elementare este cunoscută.

În rezolvarea exercițiilor este importantă crearea posibilității îndeplinirii unei independențe (individual, grup, echipă). Pentru formarea unor priceperi sau abilități legate de munca independentă, se poate utiliza și așa-numita formulă a exercițiilor comentate. Aceasta constă în rezolvarea exercițiilor de către toți elevii, în timp ce un elev desemnat explică permanent rezultatele obținute. Nu este nevoie ca această explicație să fie utilizată pe calculator. Profesorul poate în orice moment să invite oricare alt elev pentru continuarea explicației (în acest fel, metoda este deosebit de activă). Discuțiile suplimentare sunt obligatorii în acest caz. Se vor evidenția permanent avantajele și dezavantajele rezolvărilor propuse, alte metode de rezolvare, idei privind utilizarea acestor rezolvări în lecțiile următoare, particularizări ale lor în lecțiile anterioare.

4.2.8. Metoda învățării în grupe mici

Activitatea de învățare pe grupe mici se definește ca o metodă în care sarcinile sunt executate de grupuri de elevi, grupuri care sunt câteodată autoconstituite și care se autodirijează. Activitatea în informatică se desfășoară în general în echipă, travaliul individual fiind o componentă a muncii corelate din cadrul unui grup de lucru. Tehnicile de organizare a muncii în unitățile de informatică evidențiază ca o formă de organizare echipa programatorului-șef, echipă în care fiecare membru are sarcini bine stabilite (de analiză, programare, implementare, exploatare), sarcini corelate între ele. Este normal ca și activitatea didactică să recurgă la metode de învățare colectivă, fără a neglija însă munca individuală, ci doar privind-o pe aceasta ca o componentă a muncii în echipă. Profesorii recunosc, în general, eficacitatea unei asemenea organizări a activității didactice și o integrează în arsenalul metodic al predării disciplinei. Criteriile de formare a grupelor sunt în funcție de obiectivele urmărite (însușirea de noi cunoștințe, rezolvare de probleme etc.): grupuri omogene, formate din elevi cu același nivel de cunoștințe; grupuri eterogene, formate din elevi de toate categoriile (foarte buni, buni și slabi), dar în proporții apropiate; grupuri formate pe criterii afective (prieteni, vecini de bancă). Numărul elevilor dintr-un grup poate varia de la 2 la 10, dar cele mai potrivite grupuri sunt cele formate din 4-6 elevi. La lecțiile de aplicații practice de laborator, grupurile de lucru formate din 4 elevi, care dispun de două calculatoare par a fi cele mai eficiente. Grupuri formate din mai mult de 2 elevi la un calculator se dovedesc a fi neproductive. Este bine ca la întocmirea grupurilor să se stabilească criterii clare de formare și elevii să fie lăsați să se grupeze singuri, respectând criteriile cerute. Pentru grupurile omogene, sarcinile pot diferi în funcție de scopul propus. Pentru grupurile eterogene sau create pe criterii afective, sarcinile vor fi aceleași la fiecare grup, dar profesorul va rezerva sarcini suplimentare elevilor mai buni din fiecare grup. Etapele pretinse de această metodă de învățare sunt: repartizarea materialului (problemelor) fiecărui grup; munca independentă a grupurilor sub supravegherea profesorului; discutarea în plen a rezultatelor obținute. Activitatea profesorului se concretizează în două etape. Prima este una proiectivă, în care se pregătește materialul de repartizat pe grupe și materialul în plus pentru elevii buni, iar a doua de îndrumare/supraveghere și de animare a activității grupelor de lucru. Ajutorul dat grupelor de lucru trebuie să fie numai la cerere și în așa fel încât profesorul să se situeze pe poziția de colaborator și nu pe cea de autoritate care își impune părerile și soluția personală. Profesorul va interveni cu autoritate numai atunci când activitatea grupului se îndreaptă într-o direcție greșită. Când unul sau mai multe grupuri descoperă o soluție, propunerile lor vor fi discutate și analizate succesiv sau în paralel. Scopul acestei discuții este de a reliefa corectitudinea rezolvării, determinarea celei mai eficiente și mai elegante soluții și de a descoperi eventualele erori. Importanța dezbaterilor pentru dezvoltarea raționamentului este foarte mare, iar rolul profesorului este acela de a incita și coordona discuțiile în direcția obținerii concluziilor care se impun. Se impută, pe bună dreptate, acestei munci în grup o intensitate și o productivitate scăzute. Diversificarea sarcinilor grupurilor și împărțirea sarcinilor între membrii grupurilor atenuează această deficiență. Dacă prin activitatea în grup se intenționează dobândirea de noi cunoștințe prin lucrul cu manualul, documentația sau produse soft, profesorul este obligat să organizeze dezbaterile finale care să stabilească dacă elevii și-au însușit corect noțiunile și și-au format deprinderi corecte. Este de asemenea greșit să se lucreze mereu cu grupuri constituite după aceleași criterii pentru că astfel sunt suprasolicitați elevii buni din grupurile eterogene, iar elevii slabi se bazează exclusiv pe aportul liderilor de grup, fie, în grupurile omogene, elevii slabi se complac în postura în care se află și nu mai încearcă să scape de acest calificativ. Alte câteva probleme pot fi abordate sub un unghi diferit în acest context. Astfel, se pot pune întrebări mult mai individualizate (acestea nu țin neapărat de conținutul în sine al lecției). Ce întrebări se pot pune și modul în care se pun poate fi mai important decât întrebarea în sine. Apoi, este mai simplă „contactarea" elevilor în timpul lecției și chiar după ea. Susținem, ca prioritate și soluție la anumite probleme locale de învățământ aducerea unor specialiști care lucrează în lumea reală pentru a preda lecții de sinteză, lecții speciale etc.

4.2.9. Metoda lucrului cu manualul și documentația

Manualele școlare, purtătoare ale valențelor formative prin deosebitul lor conținut metodic și didactic, reprezintă o limită impusă de programa școlară din punctul de vedere al conținutului informativ. În informatică, mai mult decât în alte domenii, manualul este supus perisabilității conținuturilor prin frecvența cu care disciplina este receptivă la noutățile domeniului. Realitatea didactică reliefează faptul că elevul folosește pentru învățarea teoriei doar notițele luate în clasă la predare și, din considerente de comoditate sau de obișnuință, foarte puțin (sau deloc) manualele. Acestea sunt consultate în cel mai fericit caz doar pentru citirea enunțurilor problemelor. Atitudinea de reținere sau de respingere față de manual are consecințe negative atât asupra caracterului formativ, cât și asupra celui informativ al învățării. Capacitatea de raționament a unui copil nu se formează numai după modele de raționament oferite de profesor, ci și prin eforturi proprii, prin activitatea proprie de căutare și comparare cu alte scheme de raționament. Valoarea acestei metode nu constă numai într-o însușire temeinică a cunoștințelor, ci și în formarea unor deprinderi de activitate intelectuală. Mulți elevi încheie ciclul liceal fără a avea deprinderi de lucru cu manualul și documentația, ceea ce le creează serioase probleme de adaptare și explică eșecurile din primul an de studenție și greutatea de adaptare la cerințele studiului universitar. Metoda muncii cu manualul este un aspect al studiului individual și se introduce ca metodă, treptat, sub directa îndrumare și supraveghere a profesorului. Sunt discipline și profesori care aplică în mod abuziv această metodă. Pe lângă efectele negative asupra învățării, aceste abuzuri ascund și alte aspecte care nu fac obiectul prezentei lucrări. Înainte de a aborda această metodă, profesorul trebuie să atragă atenția elevului asupra aspectelor importante ale lecției, care trebuie urmărite în mod special, cerându-i să realizeze un rezumat cu principalele idei de reținut. Rolul profesorului nu se limitează numai la a indica lecția din manual sau documentația care trebuie studiată. În timpul studierii de către elevi a noului material, profesorul are un rol activ. El urmărește fiecare elev cum își urmărește conspectul, dă îndrumări cu voce scăzută elevilor care-l solicită, verifică planurile întocmite de aceștia, corectând acolo unde este cazul. Profesorul poate să descopere în acest fel anumite lacune în cunoștințele anterior dobândite ale elevilor și să intervină ulterior pentru remedierea lor. El se ocupă deopotrivă de elevii slabi și de cei buni cărora le dă sarcini suplimentare, reușind să-și facă o părere despre stilul de lucru și ritmul fiecărui elev. După studierea individuală din manual sau documentație, urmează discuții asupra celor însușite de către elevi. Aceste discuții au rolul de a preciza problemele esențiale ale lecției, de a le sistematiza, da a înlătura posibilitatea unor omisiuni din partea elevilor sau chiar a însușirii eronate a unor noțiuni. Profesorului i se cere o pregătire minuțioasă a materialului, pentru a fi în măsură să răspundă prompt la orice întrebare pusă de către elevi. Nu orice lecție poate fi însușită din manual. Metoda se aplică numai lecțiilor care au în manual o redactare sistematică și accesibilă nivelurilor de vârstă și de cunoștințe ale elevilor. Metoda poate fi aplicată pentru studiul unor aplicații soft, limbaje procedurale (de exemplu HTML) sau în studiul comenzilor sistemelor de operare. Elevilor li se recomandă studiul temei stabilite pentru acomodarea cu noțiunile, apoi profesorul reia prezentarea cu sublinierea aspectelor esențiale. Având o asemenea bază, profesorul se poate concentra asupra discursului său (ceea ce urmează este în strânsă legătură și cu precedentele metode). Dacă este bine organizat, există următoarele avantaje:

Urmărirea atentă a audienței: fiecărui „ascultător" îi poate fi sugerată ideea că este personajul principal, că el este vizat în primul rând.

Noi porțiuni de text pot fi ușor introduse suplimentar, prin referirea la „manual".

Se prezintă lucruri deja verificate. Nimic nu poate „merge rău", exceptând…îmbolnăvirea profesorului. Stresul fiecărui elev în parte poate fi micșorat, el știind că nu este „destinatarul" special. Există posibilitatea unui „feedback" rapid și anumite principii de învățare pot fi folosite imediat. Există posibilitatea pregătirii prealabile a materialului, cu durată determinată, inclusiv cea a expunerii. Posibilitatea de control asupra a ceea ce s-a transmis/recepționat, cui, când, sub ce formă, precum și a modului „de reacție" este foarte mare.

Desigur că există și dezavantaje. Nu insistăm, pentru că ideea este că fiecare avantaj de mai sus devine un dezavantaj dacă profesorul este un prost gestionar al metodelor și timpului său. Oricum, se poate ajunge, din partea clasei, la pasivitate, stagnare, plictiseală, lipsă de individualizare etc.

4.2.10. Metoda jocurilor didactice

Jocurile didactice (și nu numai) pe calculator au valențele lor educative. Ca metodă de învățare, jocurile didactice dau rezultate deosebite în special la clasele mici, dar marele pericol care planează asupra acestei metode îl constituie acele aplicații soft care au o încărcătură educativă redusă, dar prin atractivitate captează și rețin atenția elevului, uneori ore în șir, fără ca acesta să dobândească cunoștințe sau deprinderi pe măsura efortului făcut. Un rol aparte se atribuie jocurilor manipulative, prin care elevul devine conștient de proprietățile obiectului studiat, își formează deprinderi și dexterități de utilizare a acestuia prin simularea pe calculator a utilajului sau dispozitivului respectiv. Aceste jocuri, numite uneori și simulatoare, necesită în cele mai frecvente cazuri echipamente periferice suplimentare, unele specializate pe lângă cele clasice. Amintim în acest caz utilizarea unor căști speciale pentru obținerea efectului de realitate virtuală, echipamente care simulează condiții de zbor etc. alte tipuri de jocuri, numite reprezentative, prin simbolizarea sau abstractizarea unor elemente reale, conduc la descoperirea unor reguli de lucru (sau joc) cu aceste elemente, dezvoltând în acest fel imaginația elevului. Ce altceva reprezintă un produs soft (de exemplu, un editor grafic sau de text) atunci când înveți să-l utilizezi, decât un joc mult mai serios? Chiar dacă metoda nu este caracteristică studiului informaticii, la limita dintre jocul didactic și învățarea asistată de calculator se situează o bună parte dintre software-urile de învățare, atât a informaticii, cât și a altor discipline.

4.2.11. Instruirea programată și învățarea asistată de calculator

Instruirea programată poate fi aplicată cu mare succes în momentele în care obiectul primordial al predării îl constituie utilizarea unui mecanism real. În cadrul instruirii programate, esențiale devin probele și produsele demonstrative, pe care ar trebui să le descriem elevilor. Trebuie avut în vedere că numărul de ore afectat acestei instruiri programate să nu fie foarte mare. Acestea trebuie să includă un număr suficient de ore de verificare a cunoștințelor acumulate, evitându-se însă monotonia și instaurarea plictiselii (se recomandă utilizarea alternativă a altor metode). Trebuie evitată și folosirea metodei un timp îndelungat, lucru care poate conduce în anumite situații la o izolare socială a elevului. O idee pentru contracararea acestor efecte ar fi creșterea numărului de ore sau organizarea activităților pe grupuri sau în echipă. Instruirea asistată de calculator este un concept diferit de instruirea programată doar prin modalitatea de utilizare. Există aceleași premise și moduri de utilizare, cu excepția faptului că un sistem de calcul devine principala interfață dintre un profesor și un elev. Absolut toate noțiunile, conceptele, exercițiile, problemele, evaluările, testările, prezentările legate de o anumită temă în cadrul unei lecții (inclusiv estimarea îndeplinirii obiectivelor) sunt îndepliniri, dirijări, verificări cu ajutorul calculatorului (mediul soft corespunzător). Procesul de predare-învățare și verificare-evaluare funcționează pe baza principiului cibernetic comandă-control-reglare (autoreglare). Instruirea programată, ca metodă didactică, presupune construirea unor programe care, prin fragmentarea materialului de studiat în secvențe, realizează o adaptare a conținuturilor la posibilitățile elevilor, la ritmul lor de învățare, asigură o învățare activă și o informare operativă asupra rezultatelor învățării, necesară atât elevului, pentru autocorectare, cât și profesorului. În elaborarea programelor de învățare se au în vedere următoarele operații:

– precizarea obiectivelor operaționale în funcție de conținut și posibilitățile elevilor;

structurarea logică a conținutului după principiul pașilor mici și al învățării
gradate;

– fracționarea conținutului în secvențe de învățare (unități didactice) inteligibile și înlănțuite logic;

– fixarea după fiecare secvență a întrebărilor, exercițiilor sau problemelor ce pot fi
rezolvate pe baza secvenței informaționale însușite;

stabilirea corectitudinii răspunsurilor sau soluțiilor elaborate; aceasta se poate
realiza prin alegerea dintre mai multe răspunsuri posibile (trei, patru sau cinci). În situația în care nu s-a ales răspunsul corect, se poate recurge la întrebări suplimentare sau se elaborează un răspuns și se compară cu cel corect.

Ca orice inovație, instruirea programată a trecut prin câteva faze contradictorii. La început s-a lovit de rezerva tenace a tradiției și de dificultățile materiale, apoi, după ce a câștigat teren în conștiința teoreticienilor și practicienilor, s-au exagerat într-o oarecare măsură valențele ei aplicative, creându-se iluzia descoperirii pietrei filozofale în domeniul pedagogic. În final, după o analiză lucidă, s-a admis că există părți pozitive și părți negative. Criticile aduse instruirii programate sunt atât de ordin psihologic, cât și de ordin pedagogic și metodic. Psihologic, instruirii programate i se impută faptul că nu ține seama de principiile psihologice ale învățării, vizând învățarea ca o simplă succesiune și înmagazinare de fapte. De asemenea, se știe că motivația învățării nu poate fi analizată numai prin prisma reținerii și învățării imediate, făcând abstracție de interesul elevului față de conținut. În plus, lucrând singur sau cu calculatorul, elevul se simte izolat. Pedagogic vorbind, fărâmițarea conținuturilor este în detrimentul formării unei viziuni globale, iar valoarea cunoașterii imediate de către elev a rezultatului obținut are valențe contestabile. Metodic, decupajul analitico-sintetic al conținuturilor îngustează elevului posibilitatea formării aptitudinilor de analiză și sinteză. Aceste critici au determinat mutații serioase în concepția de aplicare a metodei, dar practica didactică dovedește că atunci când se cunosc și se evită cauzele care generează efecte negative, metoda produce rezultate bune. Tendințele de îmbunătățire a aplicării metodei se îndreaptă spre alternarea utilizării metodei cu celelalte metode clasice. Inserarea într-o lecție programată a unor metode clasice schimbă determinarea muncii școlare, repunându-l pe elev în directă dependență de activitatea profesorului și dându-i acestuia posibilitatea să verifice gradul de însușire a cunoștințelor cunoscute în program. O altă tendință este aceea de a modifica modul de redactare al programului, în special prin mărirea volumului de informație din unitățile logice și prin separarea părții de verificare, existând situații în care verificarea se va face după câteva ore sau chiar a doua zi. În plus, în program se pot insera secvențe independente, care să necesite timp mai mare de gândire sau de lucru. Izolarea imputată învățării programate poate fi contracarată prin alternarea cu munca în grup sau chiar prin învățare programată în grup, situație în care grupul parcurge în colectiv un program special conceput în acest sens.

4.3. Metode de evaluare a rezultatelor școlare

Evaluarea este activitatea prin care profesorul constată, în diferite momente ale procesului didactic, măsura în care rezultatele obținute de către elevi sunt în concordanță cu cerințele programei, cu obiectivele pedagogice preconizate.

Evaluarea este o componentă esențială a procesului de învățământ, îndeplinind funcții bine conturate:

– funcția de diagnoză (de constatare și apreciere). Prin evaluare sunt furnizate informații despre nivelul rezultatelor obținute în activitatea de predare-învățare, comparativ cu obiectivele prevăzute;

– funcția de reglare. Datele obținute prin verificarea și aprecierea rezultatelor școlare stau la baza analizei cauzelor care au influențat pozitiv sau negativ nivelul pregătirii și a măsurilor de ameliorare a activității;

– funcția de predicție și orientare. Pe baza rezultatelor controlului și aprecierii, a interpretării acestora, se organizează activitatea didactică ulterioară, se prevăd direcțiile de desfășurare care să asigure rezultatele scontate prin măsurile de ameliorare;

– funcția educativă. Evaluarea, atunci când este corect realizată, are efecte pozitive asupra procesului de învățare, orientează elevul spre conținuturi semnificative, determină stilul de învățare și motivația, dezvoltă capacitatea de analiză, sinteză, autocontrol, contribuie la clarificarea și aprofundarea cunoștințelor;

– funcția de clasificare și selecție. Potrivit rezultatelor evaluării, se realizează o ierarhizare a elevilor dintr-o clasă.

Orice proces de evaluare constă în a compara, a raporta un rezultat la o valoare prestabilită, la un etalon. În învățământ, etalonul cu care se compară performanțele elevilor sunt obiectivele pedagogice.

Un prim demers în procesul de evaluare constă în verificarea rezultatelor. Prin verificare, profesorul determină elevul să exprime, să exteriorizeze, într-o formă sau alta, cunoștințele pe care le deține, capacitatea de a le aplica, de a opera cu acestea, modul de a gândi, de a raționa.

Un alt demers îl reprezintă aprecierea, care este în strânsă legătură cu măsurarea. A măsura înseamnă a stabili numărul de caracteristici de o anumită natură pe care le întrunesc răspunsurile, performanțele elevilor verificați (numărul de răspunsuri corecte, numărul de greșeli, gravitatea acestora etc.). Numărul caracteristicilor și valoarea acestora se raportează la obiectivele pedagogice și, prin comparație, se stabilește nota, se face aprecierea.

Principalele forme de evaluare întâlnite în practica didactică sunt:

– evaluarea inițială, care conduce la formarea unei imagini despre bagajul de cunoștințe cu care elevul pornește la drum. Trebuie să ne asigurăm de ceea ce cunoaște elevul înainte de a-l învăța lucruri noi. Această formă de verificare creează și o imagine asupra posibilităților de progres ale elevului, asupra capacității lui de învățare, în funcție de care se va stabili programul de instruire;

– evaluarea formativă (continuă) este forma de evaluare pe care profesorul o aplică pe întreaga durată a procesului de instruire, în cadrul lecțiilor și la încheierea unui capitol. Această formă de verificare oferă permanent informații cu privire la eficiența programului de instruire și permite profesorului să ia cele mai potrivite măsuri de prevenire a insuccesului școlar. Verificarea ritmică oferă, pe baza mecanismului de feed-back continuu, semnalele necesare atât elevului, cât și profesorului, fiind un veritabil „metronom" al activității didactice;

– evaluarea sumativă (cumulativă) este forma tradițională de evaluare realizată la sfârșitul unui semestru sau an școlar și cuprinde întreaga materie, conform programei școlare, pe intervalul de timp la care se aplică verificarea. Rezultatele acestei forme de verificare nu reflectă întotdeauna adevăratul nivel de performanță al elevilor, dar prin faptul că determină o recapitulare și o abordare globală a materiei parcurse, are efecte pozitive în direcția dezvoltării capacității de cuprindere și de sinteză a elevului.

Superioară prin caracterul ei predictiv, evaluarea formativă trebuie totuși completată și cu celelalte forme.

Rezultatele școlare sunt obiectivate în cunoștințele acumulate, în priceperi și deprinderi, capacități intelectuale, trăsături de personalitate și de conduită ale elevilor.

Metodele de verificare a randamentului școlar presupun observarea modului în care învață elevul (logic, mecanic, creativ, ritmic, continuu, în salturi etc.) și se realizează prin probe orale, scrise și practice, teste de cunoștințe și deprinderi.

Verificarea orală, cea mai frecvent folosită, are anumite avantaje care o impun, prin faptul că favorizează dialogul, elevul putând să-și argumenteze răspunsurile și să participe la o confruntare de idei cu întreaga clasă, iar profesorul poate detecta cu ușurință erorile și poate interveni și corecta imediat. Verificarea orală are însă și numeroase limite: întrebările nu au toate același grad de dificultate, unii elevi sunt emotivi și se blochează, mai ales atunci când sunt ironizați de către profesor sau răspunsurile lor stârnesc ilaritate în clasă, timpul nu permite o verificare completă a conținutului predat, iar comportamentul și starea psihică a profesorului pot influența notarea.

Verificarea scrisă este utilizată sub forma unor lucrări de scurtă durată, lucrări „tip obiectiv", lucrări de una sau două ore, semestriale, care sunt înainte anunțate și pregătite în clasă, respectiv lucrări de tip examen. Cercetările au dovedit că evaluarea formativă în formă scrisă, după fiecare capitol, și combinată cu verificările orale este deosebit de eficientă și stimulativă.

Probele scrise sunt preferate de elevi și profesori pentru că asigură un grad mai mare de obiectivitate la notare, oferă elevilor mai emotivi sau celor care gândesc mai lent posibilitatea de a se exprima fără a fi influențați de factori perturbatori, asigură evaluarea unui număr mare de elevi, întrebările au același grad de dificultate și favorizează realizarea comparării rezultatelor. Dezavantajele metodei sunt marcate de faptul că profesorul nu poate interveni și corecta pe loc erorile descoperite, el urmând să o facă în clasă, la discutarea lucrărilor. Elevii nu pot fi corectați dacă fac anumite confuzii sau când răspunsul nu este complet. Răspunsurile incomplete pot genera și diferențe de apreciere și notare. Examinarea prin probe practice este caracteristică disciplinelor cu pronunțat caracter aplicativ, cu atât mai mult informaticii. Ea se poate desfășura în forme variate, de la realizarea unor programe simple, lucrându-se individual sau în grup, până la aplicații complexe, realizate într-un interval mai lung de timp. Sunt verificate și evaluate cunoștințele teoretice necesare realizării lucrării, cât și deprinderile și dexteritățile necesare executării ei.

O altă formă de verificare este evaluarea prin teste și care se efectuează la începutul programului de instruire (inițiale), pe parcursul acesteia (de progres) și la sfârșitul programului (finale). Rezultatele acestor teste pot fi prelucrate statistic și conduc la concluzii interesante în legătură cu eficiența metodelor de predare-învățare folosite.

Este necesară formarea la elevi a capacității de autoevaluare, prezentându-le criteriile de apreciere, ceea ce va mări încrederea elevului în propriile sale forțe și va înlătura orice urmă de suspiciune.

Deși imperfect, sistemul de evaluare permite o ierarhizare a elevilor în clase după criterii reale de competență, oferă informații edificatoare asupra nivelului de cunoștințe al fiecărui elev, stimulează elevul la învățătură.

Controlul cunoștințelor dobândite de către elevi are o însemnătate deosebită, dă posibilitatea profesorului să dezvolte la elevi simțul răspunderii, să sesizeze la timp lipsurile, să aprecieze just munca elevilor. Controlul trebuie să fie sistematic, zilnic și în mod echilibrat. La fiecare lecție se verifică modul în care a fost înțeleasă și asimilată lecția nouă, iar cum lecția are un caracter instructiv, trebuie verificat și gradul în care cele expuse au fost reținute.

Verificarea gradului de asimilare se face în diferite feluri:

– prin repetarea raționamentelor de bază pe parcursul lecției cu sprijinul elevului (prin întrebări de control);

– prin rezolvarea de probleme;

Toate acestea ajută la verificarea rezultatelor muncii efectuate în clasă.

Verificarea lucrărilor scrise acasă se face:

– printr-o trecere (printre bănci) și o examinare superficială, cantitativă;

– prin prezentarea rezolvării (ideea de rezolvare) de către un elev și confirmarea de către ceilalți elevi.

Este important ca verificarea temelor să se coreleze cu un set de întrebări, dinainte stabilite, care să verifice întreaga lecție predată anterior.

Aceasta va permite elevilor să combine repetarea notițelor predate cu formarea și dezvoltarea deprinderilor de a corela noțiunile teoretice între ele și de a le aplica în practică.

La verificarea problemelor este bine să se evidențieze diferite variante de rezolvare a aceleiași probleme și să se urmărească cele mai eficiente forme de rezolvare. De regulă se ascultă întâi expunerea coerentă a rezolvării, apoi se pun întrebările.

O altă formă de verificare este cea orală, cu toată clasa, când se pun întrebări, elevii sunt lăsați să se gândească, apoi este numit unul dintre ei care să răspundă. Ceilalți sunt îndemnați să completeze răspunsul sau să corecteze greșelile. Această examinare, sumară de regulă, nu se notează, dar în situația în care un elev nu a învățat deloc sau un altul a răspuns constant bine la mai multe întrebări, aceștia trebuie notați. La examinarea orală se pun întrebări care nu necesită desene, notări în caiete sau la tablă, calcule.

Examinarea cu scoaterea la tablă se face cu unul sau mai mulți elevi. În timp ce elevii pregătesc răspunsurile, se poate lucra cu clasa sau verifica tema de acasă. Când elevii răspund, toată clasa este atentă și pregătită să intervină. Profesorul poate să pună întrebări suplimentare sau ajutătoare, atât elevilor ascultați, cât și celor din bănci. Prin întrebări se caută să se pună în evidență aspectele esențiale ale lecției. Profesorul trebuie să-și pregătească dinainte întrebările și nu trebuie să transforme verificarea într-o scoatere cu sila la tablă și punerea unui noian de întrebări care duc chiar până la sugerarea răspunsului.

Când elevul tace, profesorul nu trebuie să-i spună fraza sau ideea, ci să desemneze un alt elev. Intervenția profesorului face ca să se creeze o ambiguitate cu privire la răspuns și la cunoștințele elevului.

După ce ascultă răspunsurile, profesorul pune note.

Lucrările de control scrise variază ca dimensiune astfel:

– cele scurte, de 10-15 minute, se dau în a doua parte a lecției și urmăresc modul de asimilare a lecției noi sau a cunoștințelor predate anterior, dar în corelație cu lecția nouă;

– cele de 1-2 ore, se dau numai după ce au fost anunțate din timp și pregătite, eventual, printr-o lecție de recapitulare. Orice procedeu de verificare trebuie să îndeplinească anumite condiții.

Verificarea trebuie:

– să aibă un scop precis, care, chiar dacă nu este transparent pentru elev, el trebuie să fie foarte clar pentru profesor;

– să dezvolte deprinderea elevului de a raționa rapid și de a da răspunsuri corecte, precise și scurte, dar complete;

– să dezvolte la elevi grija pentru formulări exacte și exprimări corecte din punct de vedere științific și gramatical;

– să permită elevilor să aprecieze răspunsurile;

– să fie operativi (să nu ia mult timp).

4.4. Proiectarea activității didactice

În practica didactică s-a stabilit ca profesorul să prezinte o planificare anuală (calendaristică). Planificarea calendaristică trebuie să conțină eșalonarea conținutului disciplinei pentru care se realizează. În planificarea calendaristică se vor face referiri la materialul didactic și la lucrările practice care vor fi efectuate. Rubricația planificării calendaristice depinde de gradul de detaliu la care se dorește să se realizeze aceasta. Temele specificate în planificare sunt concretizate în lecții, pentru care profesorul trebuie să întocmească un proiect de tehnologie didactică la nivel de detaliu.

Un prim demers în elaborarea unui proiect de lecție constă în analiza conținuturilor învățării delimitat de programă și a obiectivelor corespunzătoare.

Profesorul va analiza conținuturile învățării corelat cu obiectivele propuse de programă pentru a stabili abilitățile, calitățile proceselor psihice, ale motricității și afectivității care se pot dezvolta prin însușirea conținutului respectiv. Și nu în ultimul rând, pentru a stabili sarcinile didactice, adică acțiunile cele mai potrivite și succesiunea acestora pentru ca elevii să-și dezvolte capacitățile pe care le prilejuiește însușirea acestor cunoștințe, să se atingă performanțele prescrise prin obiective.

Deoarece lecția este un act de creație, ce nu se poate încadra în șabloane, acestea furnizează doar sugestii pentru întocmirea de scenarii didactice. Lecția se caracterizează prin mobilitatea structurii și prin flexibilitate.

4.4.1. Lecție pentru formare și consolidare de deprinderi si priceperi

LICEUL:

DISCIPLINA : Informatică

CLASA a XI-a

Unitatea de învățare : Parcurgerile grafurilor neorientate

Tema : Parcurgerea grafului în lățime și în adâncime .

Tipul lecției : formarea și consolidarea de deprinderi si priceperi

Locul de desfășurare : laboratorul de informatică

Nivelul inițial al clasei :

elevii și-au însușit toate noțiunile legate de modul de reprezentare a grafurilor neorientate .

elevii utilizează corect noțiunile anterioare și modurile de reprezentare a grafurilor neorientate .

Obiectiv cadru: realizarea de aplicații utilizând parcurgerile grafurilor neorientate

Obiective de referință :

– să aplice parcurgerile prezentate

să utilizeze în algoritmi parcurgerea cea mai avantajoasă din punct de vedere al optimului

Obiective educaționale :

obiective cognitive :

să utilizeze corect parcurgerile

să recunoască în aplicații ce parcurgere s-a utilizat

să compare variantele de parcurgere

să analizeze modul diferit de funcționare a aplicațiilor în funcție de parcurgerea utilizată

obiective afective :

să argumenteze corect alegerea unei parcurgeri, utilizate într-o aplicație

să aprecieze corect soluțiile la problemele oferite de alți colegi

să se autoevalueze corect în raport cu clasa

obiective psihomotorii :

sa utilizeze corect noțiunile teoretice însușite

sa deosebească modalitățile de parcurgere

să implementeze algoritmi care să utilizeze parcurgeri ale grafurilor într-un limbaj de programare

Obiective operaționale :

să utilizeze corect parcurgerile

să-și însușească corect modul de funcționare al parcurgerilor

să analizeze corect fiecare problemă pentru a alege cea mai bună modalitate de parcurgerea grafurilor neorientate

Strategii didactice :

Principii didactice :

Principiul participării și învățării active

Principiul asigurării progresului gradat al performantei

Principiul conexiunii inverse

Metode de învățământ :

Metode de comunicare orală: expunere, conversație, problematizare

Metode de acțiune : exercițiul, învățare prin descoperire

Procedee de instruire :

Explicația in etapa de comunicare

Învățarea prin descoperire, prin rezolvare de probleme

Problematizarea prin creare situațiilor problema

Conversația de consolidare în etapa de fixare a cunoștințelor

Forme de organizare : frontală si individuală

Forme de dirijare a învățării : dirijată de profesor sau independentă

Resurse materiale :

George Daniel Mateescu – Informatica – Manual pentru clasa a XI-a Editura Niculescu

Cornelia Ivasc, Mona Pruna – Bazele Informaticii – Proiect de manual – Editura Petrion

Metode de evaluare :

Evaluare inițială : test grilă

Set de aplicații

Desfășurarea lecției :

Moment organizatoric

Pregătirea lecției :

Întocmirea proiectului didactic

Pregătirea setului de întrebări

Pregătirea setului de aplicații

Pregătirea temei

Organizarea si pregătirea clasei :

Verificarea frecvenței

Captarea atenției clasei :

Anunțarea subiectului pentru tema respective

Anunțarea obiectivelor urmărite

Anunțarea modului de desfășurare a activității

Reactualizarea cunoștințelor

Se realizează un set de întrebări pentru reactualizarea cunoștințelor teoretice ca în tabelul de mai jos :

Parcurgeri de grafuri neorientate . Exemple.

Se prezintă un graf sub forma grafică ca în figura alăturată :

și se pun următoarele probleme :

Care este parcurgerea grafului în lățime începând cu nodul 2 ?

Răspuns așteptat : 2,1,3,4,6,7,5,8

Care este parcurgerea grafului în lățime începând cu nodul 3 ?

Răspuns așteptat : 3,1,2,4,6,7,5,8

Care este parcurgerea grafului în adâncime începând cu nodul 7 ?

Răspuns așteptat : 7,3,1,2,4,5,6,8

Care este parcurgerea grafului în adâncime începând cu nodul 5 ?

Răspuns așteptat : 5,4,3,1,2,7,6,8

Obținerea performanței .

Set de probleme în care se utilizează parcurgerile grafurilor :

Se dă un graf neorientat prin matricea de adiacență citită dintr-un fișier text și nouă noduri x respectiv y. Să se verifice dacă între cele două noduri există lanț care să le unească .

Se dă un graf neorientat prin matricea de adiacență citită dintr-un fișier text . Să se determine lungimile lanțurilor minime de la un nod x, citit de la tastatură, la celelalte noduri ale grafului .

Rezolvările așteptate :

#include<fstream.h>

int a[30][30], viz[30], n,x,y,i,j,v,p,u, c[30];

void citire(int a[30][30],int &n, int &x, int &y)

{int i,j;

ifstream f (”graf.in”);

f>>n;

for (i=1; i<=n; i++)

for (i=1; i<=n; i++)

f>>a[i][j]);

f>>x>>y;

f.close();

}

void main()

{

citire(a,n,x,y);

c[1]=x;

p=1;

u=1;

viz[x]=1;

while p<=u do

{

v:=c[p];

for (i=1; i<=n; i++)

if (a[i][v]==1 && viz[i]==0)

{

u++;

c[u]=i;

viz[i]=1;

}

p++; }

if (viz[y]==1) cout<<”exista lant”);

else cout<<”nu exista lant”); }

2.

#include<fstream.h>

int a[30][30], viz[30], n,x,y,i,j,v,p,u, c[30];

void citire(int a[30][30],int &n)

{int i,j;

ifstream f (”graf.in”);

f>>n;

for (i=1; i<=n; i++)

for (i=1; i<=n; i++)

f>>a[i][j]);

f.close();}

void main()

{ citire(a,n);

cout<<”dati nodul”;

cin>>x;

c[1]=x;

for (i=1 ; i<= n ; i++)

viz[i]=-1

p=1;

u=1;

viz[x]=0;

while p<=u do

{ v=c[p];

for (i=1; i<=n ; i++)

if (a[i][v]==1 && viz[i]==0)

{

u++;

c[u]=i;

viz[i]=viz[v]+1;

}

p++;

}

for( i=1 ; i<=n ; i++)

if (viz[i]=-1) cout<< ”nu exista lant de la ”<<x<<” la”<<i);

else cout<<” lungimea minima de la ”<<x<<” la”<< i<<”,viz[i])”;

} }

4.4.2. Lecție pentru recapitulare și sistematizare

LICEUL:

DISCIPLINA : Informatică

CLASA a XI-a

Unitatea de învățare : Conexitate în grafuri neorientate

Tema : Noțiunile preliminarii : lanț, ciclu, componenta conexă, graf conex

Tipul lecției : recapitulare și sistematizarea cunoștințelor

Locul de desfășurare : laboratorul de informatică

Nivelul inițial al clasei :

elevii și-au însușit toate noțiunile legate de lanț, ciclu și componentă conexă

elevii utilizează corect noțiunile definite anterior cu privire la lanț elementar și neelementar, ciclul elementar și neelementar și a componentelor conexe

Obiectiv cadru : realizarea de aplicații utilizând noțiunile legate de conexitate

Obiective de referința :

– să aplice corect noțiunile învățate

să utilizeze în algoritmi parcurgerile grafurilor pentru studiul conexității

Obiective educaționale :

obiective cognitive :

să definească corect noțiunile : lanț, ciclu, componentă conexă și graf conex

să recunoască în aplicații utilizarea lanțurilor sau a ciclurilor

să compare variantele de obținere a componentelor conexe în funcție de parcurgerea utilizată

să analizeze modul diferit de formare a componentelor conexe în funcție de parcurgeri

obiective afective :

să argumenteze corect alegerea unei parcurgeri pentru studiul conexității grafului

să aprecieze corect soluțiile la problemele oferite de alți colegi

să se autoevalueze corect în raport cu clasa

obiective psihomotorii :

să-și formeze deprinderi de lucru specifice temei de lucru

să-și dezvolte gândirea logică, capacitatea de generalizare și problematizare

să implementeze algoritmi care să utilizeze componentele conexe ale grafurilor într-un limbaj de programare

Obiective operaționale :

1) să utilizeze corect noțiunile de lanț și ciclu

2) să-și însușească corect modul de obținere a componentelor conexe

3) să analizeze corect fiecare problemă pentru a alege cea mai bună

modalitate de a verifica dacă un graf este conex sau nu

Strategii didactice :

Principii didactice :

Principiul participării și învățării active

Principiul asigurării progresului gradat al performanței

Principiul conexiunii inverse

Metode de învățământ :

conversația

explicația

exercițiul

problematizarea

algoritmizarea

Procedee de instruire :

Conversația de consolidare

Exerciții de consolidare

Problematizarea prin creare situațiilor problemă

Forme de organizare : frontală, individuală și pe grupe

Forme de dirijare a învățării : dirijată de profesor sau prin materiale didactice respectiv independentă

Resurse materiale :

Fișe de lucru

Set de aplicații

calculatorul

Metode de evaluare :

Evaluare sumativă

Evaluare continuă pe parcursul lecției ( fișa de lucru și calculatorul )

Evaluare formativă

Desfășurarea lecției :

Moment organizatoric

Pregătirea lecției :

Întocmirea proiectului didactic

Pregătirea setului de întrebări

Pregătirea setului de aplicații

Pregătirea temei

Organizarea si pregătirea clasei :

Verificarea frecvenței

Verificarea cantitativă si calitativă a temei

Verificarea existenței și operaționalității resurselor materiale

Captarea atenției clasei :

Anunțarea subiectului pentru tema respective

Anunțarea obiectivelor urmărite

Anunțarea modului de desfășurare a activității

Reactualizarea cunoștințelor

Se realizează un set de întrebări pentru reactualizarea cunoștințelor teoretice ca în tabelul de mai jos :

Fișă de lucru :

Este prezentată sub forma tabelului următor :

Fisa 1. – Test grilă

Fisa 2. – Probleme

1. Se consideră un graf neorientat prin matricea de adiacență. Se citește un șir de p noduri. Să se verifice dacă șirul formează un lanț, iar în caz afirmativ să se specifice natura .

2. Se consideră un graf neorientat prin matricea de adiacență. Se citește un sir de p noduri. Să se verifice dacă șirul formează un ciclu, iar în caz afirmativ să se specifice natura .

3. Se consideră un graf neorientat prin matricea de adiacență. Să se specifice un număr minim de muchii ce ar trebui adăugate astfel încât graful sa devină conex .

Rezolvări așteptate :

1.

#include<fstream.h>

int a[30][30], n,p,x[30];

void citire(int a[30][30],int &n, int x[30], int &p)

{int i,j;

ifstream f (”graf.in”);

f>>n;

for (i=1; i<=n; i++)

for (i=1; i<=n; i++)

f>>a[i][j]);

f>>p;

for (i=1; i<=p; i++)

f>>x[i];

f.close();

}

int lant(int x[30];int p)

{

int i;

for (i=1; i<p; i++)

if (a[x[i]][x[i+1]]==0) return 0;

return 1;

}

int natura(int x[30], int p)

{

int i,j;

for (i=1; i<p ; i++)

for (j=i+1 ; j<=p ; j++)

if( x[i]==x[j]) return 0;

return 1;

}

void main()

{

citire(a,n,x,p);

if (lant(x,p))

if (natura(x,p))

cout<<”este lant elementar”;

else cout<<” este lant neelementar”;

else cout<< ”nu este lant”;

}

#include<fstream.h>

int a[30][30], n,p,x[30];

void citire(int a[30][30],int &n, int x[30], int &p)

{int i,j;

ifstream f (”graf.in”);

f>>n;

for (i=1; i<=n; i++)

for (i=1; i<=n; i++)

f>>a[i][j]);

f>>p;

for (i=1; i<=p; i++)

f>>x[i];

f.close();

}

int ciclu(int x[30], int p)

{

int i;

if (x[1]!=x[p]) return 0;

for (i=1 ; i< p ; i++)

if ( a[x[i]][x[i+1]]==0 ) return 0;

return 1;

}

int natura(int x[30], int p)

{

int i,j;

for (i=1 ; i< p-1 ; i++)

for ( j=i+1 ; j< p ; j++)

if ( x[i]==x[j]) return 0;

return 1;

}

void main()

{

citire(a,n,x,p);

if ( ciclu(x,p))

if (natura(x,p))

cout<< ”este ciclu elementar”;

else cout<<”este ciclu neelementar”;

else cout<<” nu este ciclu ”;}

#include<fstream.h>

int a[30][30], n,p,y[30],i,j,c[30],nc,v,m,u,viz[30];

void citire(int a[30][30],int &n, int &m)

{int i,j;

ifstream f (”graf.in”);

f>>n>>m;

for (i=1; i<=n; i++)

for (i=1; i<=n; i++)

f>>a[i][j]);

f.close();

}

int nod(int viz[30])

{

int i;

for( i=1 ; i<=n ; i++ )

if (viz[i]==0) return i;

return 0;}

void main()

{ citire(a,n,m);

x=nod(viz);

while( x>0)

{

nc++;

c[1]=x;

y[nc]=x;

viz[x]=1;

p=1;

u=1;

while( p<=u)

{

v=c[p];

for( i=1; i<=n ; i++ )

if (a[v][i]==1 && viz[i]==0)

{

u++;

c[u]=i;

viz[i]=1;

}

p++;

}

x=nod(viz);

}

cout<< ” nr. minim de muchii ce trebuie adaugate ca sa devina conex =”<<nc-1;

cout<< ”exemplu de muchii ”);

for (i=1; i<nc ; i++)

cout<<”(”<<y[i]<<”,”<<,y[i+1]<<”)”;

}

Fisa 3. – Probleme pentru obținerea performanței

Obținerea performanței se realizează prin utilizarea fișei cu numărul 3, propusă pentru elevii capabili de performanță care o pot realiza în clasă și constituind temă pentru acasă celorlalți elevi .

1. Se dă un graf neorientat prin matricea de adiacență. Să se verifice dacă trei noduri x, y și z fac parte din aceeași componentă conexă.

2. Se dă un graf neorientat prin matricea de adiacență . Să se determine lungimile drumurilor minime de la un nod dat x la celelalte noduri.

4.4.3. Fișe de lucru pentru pregătirea concursurilor școlare

4.4.3.1. Probleme rezolvate

1. Scara (Olimpiada de Informatică, faza județeană 2005)

Domnul G are de urcat o scară cu n trepte. În mod normal, la fiecare pas pe care îl face, el urcă o treaptă. Pe k dintre aceste trepte se află câte o sticlă cu un număr oarecare de decilitri de apă, fie acesta x. Dacă bea toată apa dintr-o astfel de sticlă, forța și mobilitatea lui G cresc, astfel încât, la următorul pas el poate urca până la x trepte, după care, dacă nu bea din nou ceva, revine la “normal”. Sticlele cu apă nu costă nimic. Cantitatea de apă conținută de aceste sticle poate să difere de la o treaptă la alta.

Pe j trepte se află câte o sticlă cu băutura energizantă. Și pentru aceste sticle, cantitatea de băutură energizantă poate să difere de la o treaptă la alta. Să presupunem că într-una dintre aceste sticle avem y decilitri de băutură energizantă. Dacă bea q (qy) decilitri dintr-o astfel de sticlă, la următorul pas G poate urca până la 2q trepte, după care și în acest caz, dacă nu bea din nou ceva, el revine la “normal”. Însă băutura energizantă costă: pentru o cantitate de q decilitri consumați, G trebuie să plătească q lei grei.

Pot exista trepte pe care nu se află nici un pahar, dar și trepte pe care se află atât o sticlă cu apă cât și una cu băutură energizantă. În astfel de situații, nu are rost ca G să bea ambele băuturi deoarece efectul lor nu se cumulează; el poate alege să bea una dintre cele două băuturi sau poate să nu bea nimic.

Cerință

Determinați p, numărul minim de pași pe care trebuie să îi facă G pentru a urca scara, precum și suma minimă pe care trebuie să o cheltuiască G pentru a urca scara în p pași.

Date de intrare

Fișierul text de intrare scara.in conține:

pe prima linie un număr natural n, reprezentând numărul total de trepte;

pe cea de a doua linie un număr natural k, reprezentând numărul de trepte pe care se află sticle cu apă;

pe fiecare dintre următoarele k linii câte două numere naturale separate printr-un spațiu, reprezentând numărul de ordine al treptei pe care se află o sticlă cu apă și respectiv cantitatea de apă din acea sticlă exprimată în decilitri;

pe următoarea linie un număr natural j, reprezentând numărul de trepte pe care se află sticle cu băutură energizantă;

pe fiecare dintre următoarele j linii câte două numere naturale separate printr-un spațiu, reprezentând numărul de ordine al treptei pe care se află o sticlă cu băutură energizantă și respectiv cantitatea de băutură energizantă din acea sticlă exprimată în decilitri.

Date de ieșire

Fișierul text de ieșire scara.out va conține o singură linie pe care vor fi scrise două numere naturale p c separate printr-un spațiu, p reprezentând numărul minim de pași, iar c suma minimă cheltuită.

Restricții

n 120

0 k n

0 j n

Cantitatea de apă aflată în oricare sticlă este 1 x 100

Cantitatea de băutură energizantă aflată în oricare sticlă este 1 y 100

Exemple

Descrierea soluției

Se construiește un graf orientat cu n noduri (care corespunzător celor n trepte) la arcele căruia se atașează costuri urmărind ca:

între două noduri costul să fie cu atât mai mic cu cât nodurile sunt “mai depărtate”

costul pentru salturi efectuate după ce se bea băutura energizantă să fie mai mare decât costul salturilor făcute după ce se bea apă între aceleași noduri, dar acest cost să nu depașească costul saltului între două noduri mai apropiate.

În calculul costurilor între doua noduri am folosit formulele:

cost[i][i+1] = 999000

cost[i][j]= 1000000 – (j-i) pentru salturi când se bea apă j>i

cost[i][j]= 1000000 – (j-i) + q pentru salturi când se bea energizantă j>i, 1 q y

Pe acest graf se aplică apoi un algoritm de aflare a drumului minim de sursă unică

Rezolvare

#include <fstream.h>

#include <values.h>

const nmax=121;

unsigned long cost[nmax+1][nmax+1];

unsigned long c[nmax+1],pd[nmax+1],d[nmax+1],min;

int eng[nmax+1];

void main()

{ifstream fi("scara.in");

ofstream fo("scara.out");

int n,k,j,i,x,cx,i1,nod1,nod2,y,p,v;

fi>>n;

for (i=0;i<n+1;i++)

for (j=0;j<n+1;j++)

cost[i][j]=MAXLONG;

//costul sariturii pe prima treapta

cost[0][1]=999000;

//costurile cand merge din 1 in 1

for (i=1;i<=n;i++)

cost[i][i+1]=999000;

fi>>k;

for (i=0;i<k;i++)

{ fi>>p>>x;

if (! fi.good() || x>100) cout<<"apa incorect\n";

nod1=p;

for (nod2=nod1+2,i1=2;i1<=x;i1++,nod2=nod2+1)

if (nod2<=n)

cost[nod1][nod2]=1000000-100*(nod2-nod1);

}

//costurile cand bea energizanta

fi>>j;

for (i=0;i<j;i++)

{ fi>>p>>y;

if (! fi.good() || y>100) cout<<"baut incorect\n";

eng[p]=y;

}

for (i=1;i<=n;i++)

if (eng[i]!=0)

{

nod1=i;

for (nod2=nod1+1,i1=1;i1<=eng[i];i1++,nod2=nod2+2)

{if (nod2<=n)

if (cost[nod1][nod2]>1000000-100*(nod2-nod1)+i1)

cost[nod1][nod2]=1000000-100*(nod2-nod1)+i1;

if (nod2+1<=n)

if (cost[nod1][nod2+1]>1000000-100*(nod2-nod1+1)+i1)

cost[nod1][nod2+1]=1000000-100*(nod2-nod1+1)+i1;

}

}

for (i=1;i<n+1;i++)

{ c[i]=1;

d[i]=cost[0][i];

}

pd[1]=0;

for (j=0;j<n-1;j++)

for (i=1;i<n+1;i++)

if (c[i]!=0)

if (min>d[i])

{min=d[i];

v=i;

}

c[v]=0;

for (i=1;i<n+1;i++)

if (c[i]!=0)

if (d[i]>d[v]+cost[v][i])

{

d[i]=d[v]+cost[v][i];

pd[i]=v;

}

}

i=n;

int ct=0,cst=0;

while (i!=0)

{j=pd[i];

ct++;

if (cost[j][i]%100!=0)

cst = cst+cost[j][i]%100;

i=j;

}

fo<<ct<<' '<<cst<<endl;

fo.close();

}

2. Cezar (Olimpiada de Informatică, faza județeană 2007)

În Roma antică există n așezări senatoriale distincte, câte una pentru fiecare dintre cei n senatori ai Republicii. Așezările senatoriale sunt numerotate de la 1 la n, între oricare două așezări existând legături directe sau indirecte. O legătură este directă dacă ea nu mai trece prin alte așezări senatoriale intermediare. Edilii au pavat unele dintre legăturile directe dintre două așezări (numind o astfel de legătură pavată ”stradă“), astfel încât între oricare două așezări senatoriale să existe o singură succesiune de străzi prin care se poate ajunge de la o așezare senatorială la cealaltă.

Toți senatorii trebuie să participe la ședințele Senatului. In acest scop, ei se deplasează cu lectica. Orice senator care se deplasează pe o stradă plătește 1 ban pentru că a fost transportat cu lectica pe acea stradă.

La alegerea sa ca prim consul, Cezar a promis că va dota Roma cu o lectică gratuită care să circule pe un număr de k străzi ale Romei astfel încât orice senator care va circula pe străzile respective, să poată folosi lectica gratuită fără a plăti. Străzile pe care se deplasează lectica gratuită trebuie să fie legate între ele (zborul, metroul sau teleportarea nefiind posibile la acea vreme).

În plus, Cezar a promis să stabilească sediul sălii de ședințe a Senatului într-una dintre așezările senatoriale aflate pe traseul lecticii gratuite. Problema este de a alege cele k străzi și amplasarea sediului sălii de ședințe a Senatului astfel încât, prin folosirea transportului gratuit, senatorii, în drumul lor spre sala de ședințe, să facă economii cât mai însemnate. În calculul costului total de transport, pentru toți senatorii, Cezar a considerat că fiecare senator va călători exact o dată de la așezarea sa până la sala de ședințe a Senatului.

Cerință

Scrieți un program care determină costul minim care se poate obține prin alegerea adecvată a celor k străzi pe care va circula lectica gratuită și a locului de amplasare a sălii de ședință a Senatului.

Date de intrare

Fișierul cezar.in conține

pe prima linie două valori n k separate printr-un sațiu reprezentând numărul total de senatori și numărul de strazi pe care circulă lectica gratuită

pe următorele n-1 linii se află câte două valori i j separate printr-un spațiu, reprezentând numerele de ordine a două așezări senatoriale între care există stradă.

Date de ieșire

Pe prima linie a fișierului cezar.out se va scrie costul total minim al transportării tuturor senatorilor pentru o alegere optimă a celor k străzi pe care va circula lectica gratuită și a locului unde va fi amplasată sala de ședințe a Senatului.

Restricții

– 1<n≤10000, 0<k<n

– 1≤i,j≤n , i≠j

– Oricare două perechi de valori de pe liniile 2,3,…,n din fișierul de intrare reprezintă două străzi distincte.

– Perechile din fișierul de intrare sunt date astfel încât respectă condițiile din problemă.

– Pentru 25% din teste n≤30, pentru 25% din teste 30<n≤1000, pentru 25% din teste 1000<n≤3000, pentru 10% din teste 3000<n≤5000, pentru 10% din teste 5000<n≤10000.

Exemplu

Descrierea soluției

Se elimină succesiv, dintre frunzele existente la un moment dat, frunza de cost minim. Toate nodurile au costul inițial 1. La eliminarea unei frunze, se incrementează cu costul fiului costul tatălui acesteia. Validitatea metodei rezultă din observația că, la eliminarea unei frunze oarecare, tatăl acesteia poate deveni frunză la rândul lui, dar cu un cost strict mai mare decât al frunzei eliminate.

Se poate reține arborele cu ajutorul listelor de adiacență (liniare sau organizate ca arbori de căutare), iar frunzele se pot memora într-un minheap de costuri, structură care se actualizează în timp logaritmic.

Rezolvare

#include <fstream.h>

struct NOD{int nod;NOD* next;};

NOD *dp[10000];

long s; int *c,n,k,h[10001],lh;

void add(NOD*& p, int a)

{NOD* q;

q=new(NOD);q->next=p;

q->nod=a;p=q;

}

void remove(NOD*& p, int a)

{NOD *q,*r;

if (p->nod==a){

q=p;p=p->next;

delete q;

}

else {

q=p;

while (q->next->nod!=a) q=q->next;

r=q->next;q->next=q->next->next;

delete r;

}

}

void citire()

{int i,x,y;

ifstream f("cezar.in");

f>>n>>k;

c=new int[10000];

for (i=0;i<n;i++){

*(c+i)=1;dp[i]=0;h[i]=n;

}

for (i=0;i<n-1;i++){

f>>x>>y;

add(dp[x-1],y-1);add(dp[y-1],x-1);

}

for (i=0;i<n;i++)

if (!dp[i]->next)h[++lh]=i;

*(c+n)=20000;h[n]=n;

f.close();

}

void desfrunzire()

{ int ii,i,j,pmin;long min;

s=0;

for (ii=n-1;ii>=k+1;ii–){

pmin=h[1];s+=*(c+pmin);

j=dp[pmin]->nod;

*(c+j)+=*(c+pmin);

remove(dp[j],pmin);

if(!dp[j]->next)h[1]=j;

else {h[1]=h[lh];h[lh]=n;lh–;}

i=1;

while (2*i<=lh){

if (*(c+h[2*i])<*(c+h[2*i+1])) j=2*i; else j=2*i+1;

if (*(c+h[i])>*(c+h[j]))

{int aux=h[i];h[i]=h[j];h[j]=aux;i=j;}

else i=n;

}

}

}

void main()

{ citire();

desfrunzire();

ofstream f("cezar.out");

f<<s<<'\n';

f.close();

}

3. Graf (Olimpiada de Informatică, faza județeană 2006)

Se știe că într-un graf neorientat conex, între oricare două vârfuri există cel puțin un lanț iar lungimea unui lanț este egală cu numărul muchiilor care-l compun. Definim noțiunea lanț optim între două vârfuri X și Y ca fiind un lanț de lungime minimă care are ca extremități vârfurile X și Y. Este evident că între oricare două vârfuri ale unui graf conex vom avea unul sau mai multe lanțuri optime, depinzând de configurația grafului.

Cerință:

Fiind dat un graf neorientat conex cu N vârfuri etichetate cu numerele de ordine 1,2,…,N și două vârfuri ale sale notate X și Y (1≤X,Y≤N, X≠Y ), se cere să scrieți un program care determină vârfurile care aparțin tuturor lanțurilor optime dintre X și Y.

Date de intrare:

Fișierul graf.in conține

pe prima linie patru numere naturale reprezentând: N (numărul de vârfuri ale grafului), M (numărul de muchii), X și Y (cu semnificația din enunț).

pe următoarele M linii câte două numere naturale nenule Ai,Bi (1≤Ai,Bi≤N, Ai ≠ Bi , pentru 1≤i≤M ) fiecare dintre aceste perechi de numere reprezentând câte o muchie din graf.

Date de ieșire:

Fișierul graf.out va conține

pe prima linie, numărul de vârfuri comune tuturor lanțurilor optime dintre X și Y;

pe a doua linie, numerele corespunzătoare etichetelor acestor vârfuri, dispuse în ordine crescătoare; între două numere consecutive de pe această linie se va afla câte un spațiu.

Restricții:

2≤N≤7500; 1≤M≤14000

pentru 50% din teste N≤200

Exemple:

Descrierea soluției

Dacă definim distanța între două vârfuri ale unui graf neorientat ca fiind lungimea celui mai scurt lanț dintre care are drept capete vârfurile, atunci putem să observăm că un vârf oarecare Z se află pe un lanț de lungime minima dintre X și Y dacă și numai dacă d(X,Z)+d(Z,Y)=d(X,Y) , pentru cazul în care considerăm lungimea lanțului ca fiind numărul muchiilor și d(X,Z)+d(Z,Y)=d(X,Y)+1, pentru cazul în care considerăm lungimea ca fiind numărul vârfurilor.

Stabilim prin câte o parcurgere în lățime distanțele tuturor vârfurilor față de X și respectiv Y (capetele lanțului, citite din fișier). Vedem care dintre vârfurile ce aparțin cel puțin unui lanț de lungime minima între X și Y au proprietatea ca sunt singurele aflate la o anumită distanță de X. Acestea sunt vârfurile care aparțin tuturor lanțurilor de lungime minimă dintre X și Y.

Rezolvare

#include <fstream.h>

const nmax = 7501;

struct node { int x; node * next;};

typedef int sir[nmax];

typedef node* nod;

nod v[nmax];

int *dx, *dy, *num, *vertex, *at, l[nmax];

int n,m,x,y,i,j,xx,yy,nr;

nod p;

ifstream fi("graf.in");

void bfs (int x, int d[])

{ int tail, ttail, head, i;

nod p,q;

setmem(d,(n+1)*sizeof(int),0);

head=1; tail=1; ttail=1;

l[1]=x; d[x]=1;

do

{ for (i=head; i<=tail; i++)

{

p = v[l[i]];

while (p!=NULL)

{ if (d[p->x]==0)

{ ttail++;

l[ttail] = p->x;

d[p->x] = d[l[i]]+1;

}

p = p->next;

}

}

if (tail==ttail) break;

head = tail+1;

tail = ttail;

}

while (1);

}

void main()

{

fi>>n>>m>>x>>y;

for (i=1;i<=m;i++)

{ fi>>xx>>yy;

p = new node;

p->x = yy;

p->next = v[xx];

v[xx] = p;

p = new node;

p->x = xx;

p->next = v[yy];

v[yy] = p;

}

dx = new int[n+1];

bfs(x, dx);

dy = new int[n+1];

bfs(y,dy);

num = new int[n+1];

for (i=0;i<=n;i++)

num[i]=0;

vertex = new int[n+1];

for (i=0;i<=n;i++)

vertex[i]=0;

for (i=1;i<=n;i++)

if (dx[i] + dy[i] == dx[y]+1)

{ num[dx[i]]++;

vertex[dx[i]] = i;

}

at = new int[n+1];

for (i=0;i<=n;i++)

at[i]=0;

nr = 0;

for (i=1;i<=n;i++)

if (num[i]==1)

{ nr++;

at[vertex[i]]=1;

}

ofstream fo("graf.out");

fo<<nr<<endl;

for (i=1;i<=n;i++)

if (at[i]==1)

fo<<i<<' ';}

4.4.3.2. Probleme propuse spre rezolvare

1. Problema sponsorului (Olimpiada Națională de Informatică, Suceava 1996) RATUC Suceava, unul dintre sponsorii olimpiadei, își propune să îmbunătățească transportul în comun în localitate. Directorul va pune la dispoziție o schemă pe care sunt reprezentate stațiile, numerotate pentru simplificare, de la 1 la n și cele k linii directe între stații, astfel încât între oricare două stații există legătură, eventual cu schimbarea mijlocului de transport. Trebuie să determinați dacă există cel puțin o linie directă prin blocarea căreia legătura, directă sau indirectă, între cel puțin două stații să fie întreruptă. Dacă astfel de linii există, să se propună înființarea unui număr cât mai mic de linii directe între stațiile existente astfel încât prin blocarea unei singure linii directe, oricare ar fi aceasta, circulația între oricare două stații să fie posibilă; se alege soluția pentru care suma ocolurilor pe traseele varianta (măsurate în număr de linii directe) să fie cât mai mică. Implementați eficient algoritmul lui Kruscal de determinare a unui arbore Speologii au cercetat n culoare subterane pentru a stabili dacă aparțin aceleiași peșteri. Prin tehnici specifice de curenți de aer și de colorare a cursurilor de apa, a fost demonstrată existența unor canale de legătură între mai multe culoare. Precizându-se perechile de culoare între care au fost stabilite legături, să se afle dacă sistemul de culoare corespunde unei singure peșteri .

2. Într-o stațiune de tratament s-au întâlnit n sahiști, codificați prin numere de la 1 la n, care au jucat p partide de șah. Pentru fiecare partidă se precizeaza cei doi jucători. Să se determine un grup cât mai mare de jucători care, prin jocurile pe care le-au desfășurat, au format o grupare de tip turneu (în care fiecare a jucat cu fiecare).

3. Rețeaua de distribuție a apei calde pentru o centrala termica zonală este formată dintr-un sistem de conducte care leagă centrala de blocuri și blocurile între ele. Blocurile din rețea sunt numerotate cu numere întregi de la 1 la n, centrala fiind punctul 0 de distribuție. Se cunosc distanțele de la centrală la blocuri precum și distanțele între oricare doua blocuri . Să se afișeze perechile de numere desemnând punctele de distribuție între care trebuie să se monteze conducte astfel încât fiecare bloc sa fie alimentat cu apă caldă (nu neapărat direct de la centrală) și lungimea totală a conductelor necesare să fie minimă .

4. Un elev vrea să călătorească din localitatea X în localitatea Y . Dacă în țara respectivă există n localități și știind timpul necesar pentru a ajunge dintr-o localitate în alta (în cazul în care se poate ajunge direct) se cere să se determine timpul minim în care elevul poate să ajunga din X in Y .

5. Se consideră un grup de n persoane, având fiecare un anumit număr de preocupări, cel mult p preocupări fiecare . Preocupările sunt codificate prin numere întregi nenule.

Să se determine perechile de persoane care au preocupări comune, specificând pentru fiecare astfel de pereche numărul de preocupări comune .

Să se determine perechea (eventual perechile) de persoane cu un număr maxim de preocupări comune.

Să se determine preocuparea îmbrățișată de un număr maxim de persoane.

6. Într-o zona de munte, există n cabane, între cabane existând trasee de legătură . Să se determine, dacă există, o ordine de vizitare a cabanelor, astfel încât să se parcurgă o singura dată toate traseele de legătură din zonă revenind la aceeași cabană de la care s-a pornit .

7. Fie un arbore cu n vârfuri . În fiecare nod al arborelui se află câte un bec . Prin atingerea unui bec acesta își schimbă starea (din aprins în stins și invers), la fel și vecinii lui directi. Considerând că inițial toate becurile sunt stinse, să se scrie un program care generează o secvență de „atingeri” prin care pomul este aprins complet. Datele de intrare se citesc din fișierul „pom.in” cu formatul : pe prima linie numărul de noduri , și pe urmatoarele n-1 linii muchiile arborelui .

8. Să presupunem că un graf neorientat este format din n vârfuri și m arce. Se stie că sunt folosite toate muchiile pentru a lega vârfurile și că doua vârfuri pot fi legate direct prin cel mult o muchie. Să se determine valoare maximă a expresiei unde d(i) reprezintă gradul nodului i .

9. Într-un oraș intersecțiile sunt numerotate de la 1 la n (se consideră intersecție nu numai locul unde se intersectează mai multe străzi ci și capetele de străzi). Edilii orașului doresc să numeroteze și strazile orașului, dar într-un mod care să tină seama de numerotarea intersecțiilor, și anume: doua străzi diferite să aiba numere diferite și în fiecare intersecție trebuie să sosească o stradă care să aibă numărul intersecției. În condițiile acestei probleme, prin stradă se înțelege o porțiune de drum aflată între doua puncte de intersecție, neglijând faptul că în practică străzile cuprind mai multe intersecții. Întrebarea este dacă se poate , și dacă da , cum se poate face o astfel de numerotare .

În fișierul de intrare se găsesc mai multe seturi de date separate de cate un rând liber; un set de date are pe prima linie numărul n de puncte de intersecție(terminale). Fiecare astfel de punct este identificat prin numărul cu care este numerotat, iar pe următoarele n linii sunt date pentru fiecare intersecție k puncte cu care acesta comunică direct printr-o stradă .

Pentru fiecare set de date trebuie afișată o numerotare a străzilor dacă există, respectiv mesajul: „Nu există o astfel de numerotare” dacă nu există . Numerotarea se afișează astfel: pe fiecare linie o pereche de numere care reprezintă intersecțiile care delimitează strada și apoi numărul străzii .

4.5. Concluzii

Metodica predării informaticii este o disciplină care diferă de disciplinele propriu-zise de informatică în conținut și stil, dar diferă și de metodica predării altor discipline (de exemplu, matematică). Ea are legătură cu alte științe, după cum urmează:

Pedagogia adică știința care se ocupă cu studiul metodelor de educație și de instruire a oamenilor, în special a persoanelor cu puțina experiență.

Psihologia este știința care se ocupă cu studiul proceselor și particularităților psihice umane.

Metodica este partea didacticii generate care studiază principiile, metodele și formele de predare adaptate specificului fiecărui obiect de învățământ.

Didactica este o parte a pedagogiei care se ocupă cu principiile și metodele predării materiilor de învățământ, precum și cu organizarea învățământului.

Din punctul de vedere al unui cadru didactic, aceste științe sunt importante în egală măsură și trebuie studiate/stăpânite simultan. Cunoștințele acumulate (oricât de vaste și de profunde ar fi) nu sunt suficiente pentru desfășurarea procesului de instruire. Pentru ca activitatea profesorului să aibă rezultatul dorit este nevoie de un mediu corespunzător (legislativ, economic, social, etc), dar și de talent și perseverența.

Începând cu 1980, termenul „informatică" a fost un sinonim pentru: știința calculului, știința calculatoarelor, ingineria calculatoarelor, tehnologia informației și a comunicării ș.a.m.d. Aceste definiții informale pot căpăta noi valențe, sub o formă mai mult sau mai puțin detaliată, fără însă a avea pretenția că sunt complete. Iată doar câteva posibile exemple:

1. Informatica se ocupă cu studiul calculatoarelor și al fenomenelor majore din jurul acestora.

2. Informatica cuprinde totalitatea cunoștințelor asupra calculatorului și al calculului.

Ea are componente teoretice, experimentale și de proiectare și include:

a) teorii pentru înțelegerea echipamentelor de calcul, a programelor și sistemelor;

b) experimente pentru testarea și dezvoltarea conceptelor;

c) metodologii (reguli, metode) de proiectare (algoritmi, unelte pentru aplicații practice particulare),

d) metode de analiză pentru verificarea faptului că realizările îndeplinesc cerințele.

3. Informatica se ocupă cu studiul reprezentării cunoștințelor si a implementării acestora.

4. Informatica se ocupă cu studiul modelelor si a complexității cunoștințelor.

5. Informatica se ocupă cu studiul sistematic al proceselor algoritmice care descriu și transformă informația (teoria informației), precum și cu analiza, proiectarea, implementarea și aplicarea acestora.

Vom admite astfel că scopurile introducerii informaticii ca disciplină de sine stătătoare (opțională/facultativă/obligatorie) în planurile de învățământ școlare sunt:

Dezvoltarea capacității de utilizare a terminologici, a unui limbaj informatic specific si de folosire a tehnicii de calcul în însușirea de noi cunoștințe.

înțelegerea informaticii ca mijloc de modelare a fenomenelor realității înconjurătoare și de simulare a acestora.

Asigurarea nivelului de cultură generală în informatică prin parcurgerea principalelor etape prin dezvoltarea informaticii ca știință.

Dezvoltarea unei motivații intrinseci în studiul informaticii.

Crearea unei atitudini favorabile activității de rezolvare a problemelor cu ajutorul calculatorului, prin deprinderea strategiilor de abordare a acestora si tratarea lor într-un mod riguros.

Dezvoltarea unor capacități de autoinstruire.

Crearea unei atitudini pozitive privind importanța deosebită a informaticii în lumea contemporană și pătrunderea ei în toate domeniile vieții economico-sociale.

BIBLIOGRAFIE

C. Bălcău, Combinatorică și teoria grafurilor, Editura  Universității din Pitești, Pitești, 2007.     

E. Cerchez, M. Șerban, Programarea în Limbajul C / C++ pentru liceu, POLIROM, 2006;

E. Ciurea, Algoritmi. Introducere în algoritmica grafurilor, Editura Tehnică, București, 2001;

T.H. Cormen , C.E. Leiserson , R.R. Rivest, Introducere in Algoritmi, Computers Libris Agora, 2001;

L. Ezechil, Prelegeri de didactica generala, Editura Paralela 45 Educational, Pitești 2003 ;

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

D. Logofătu, Algoritmi fundamentali în C++. Aplicații, POLIROM, 2007;

G.D. Mateescu, P.F. Moraru, C. Popescu, Informatică. Teste și variante de subiecte pentru bacalaureat, Editura Donaris, Sibiu, 2001;

O. Pătrășcoiu, Gh. Marian, N. Mitroi, Elemente de grafuri și combinatorică. Metode, algoritmi și programe, Editura All București, 1994;

C. Petre, D. Popa, Șt. Crăciunoiu, C. Iliescu, Metodica predării Informaticii și Tehnologiei Informației, Editura Arves, Craiova, 2002;

R. Pintea, D. Popescu Anastasiu, Bacalaureat la Informatică, Editura L&S Infomat, București, 2005;

I. Tomescu, Probleme de combinatorică și teoria grafurilor, Editura Didactică și Pedagogică, București, 1981.

www.academia.edu/Didactica_specialitii_Informatica_Curs_3_III._Metode_tehnici_procedee_didactice

Tehnologia informației și a comunicațiilor (Tehnici de documentare asistată de calculator), clasa a XI-a, ciclul superior al liceului, filiera vocațională, profilul ordine și securitate publică și profilul pedagogic, toate specializările

http://blogoenciclopedia.blogspot.ro/2014/07/metode-didactice-utlizate-in-procesul.html

www.google.ro/Metodica predarii informaticii