Ordonontare și Coordonare

Domeniu: Limbaje de Programare

Conține 1 fișier: doc

Pagini : 78 în total

Cuvinte : 15183

Mărime: 227.03KB (arhivat)

Publicat de: Liviu Lupu

Puncte necesare: 10

UNIVERSITATEA DE VEST TIMIŞOARA FACULTATA DE MATEMATICĂ ŞI INFORMATICĂ DEPARTAMENTUL DE INFORMATICĂ

Descarcă acum

Cuprins Extras Bibliografie Preview

Cuprins

Cuprins 1
A.Probleme de ordonanţare şi coordonare 4
I. Introducere 4
II. Probleme de ordonanţare 5
III. Probleme de coordonare 11
IV. Metoda PERT completă 16
V. Metoda drumului critic 19
VI. Rezumat 27
B. Probleme de drumuri în reţele 28
I. Introducere 28
II. Problema comis-voiajorului 29
III. Procedeul lui Little şi colaboratorii 30
IV. Algoritmul 31
V. Drumuri minime în reţele 39
V.A. O metodă grafică 39
V.B. O metodă matricială 42
VI. Rezumat 46
C.Aplicaţii 47
I. Introducere 47
II. Reprezentarea arborilor binari în calculator 48
III. Parcurgerea arborilor binari 50
3.1.Parcurgerea în preordine 50
3.1.1. Iterativ 50
3.1.2. Recursiv 51
3.2.Parcurgerea în inordine 51
3.2.1.Iterativ 51
3.2.2.Recursiv 52
3.3. Parcurgerea în postordine 52
3.3.1.Iterativ 52
3.3.2.Recursiv 53
IV. Traversarea grafurilor în adâncime ( deph-first search ) 54
4.1. Algoritm 54
4.2. Exemplu de implementare a algoritmului ( cod sursă C++ ) 55
V. Traversarea grafurilor prin cuprindere 56
5.1. Algoritm 56
5.2. Exemplu de implementare a algoritmului ( cod sursă C++ ) 57
VI. Aplicaţii ale traversării grafurilor 58
6.1. Determinarea arborelui de acoperire 58
6.2. Determinarea componentelor conexe 59
6.3. Puncte de articulaţie şi componente biconexe 59
6.3.1.Algoritm 60
6.3.2. Exemplu de implementare a algoritmului 60
6.4. Sortare topologică 62
6.5.Algoritmi pentru găsirea arborelui de valoare optimă 62
6.5.1. Algoritmul lui KrusKal 62
6.5.2. Algoritmul lui Solin 63
6.5.3. O varianta a algoritmului lui Kruskal 63
Bibliografie 64

Extras din proiect

A. PROBLEME DE ORDONANŢARE ŞI COORDONARE

I. INTRODUCERE

Se consideră două tipuri de probleme relative la ordinea în care trebuie efectuate o serie de activităţi. În primul caz, referitor la probleme de ordonanţare, obiectivul constă în a găsi ordinea în care trebuie efectuate activitaţi independente ce folosesc anumite servicii comune în aşa fel încât să se optimizeze o anumită măsură a execuţiei întregii mulţimi.

În acest capitol se discută două tipuri de probleme. Primul tip priveşte stabilirea ordinii într-un fir de aşteptare, ordine care în problemele de teoria aşteptării se consideră ca data sau fixdata. Alegerea unei ordini potrivite in care să fie serviţi clienţii care aşteaptă se numeşte ordonanţare.

În textul original: sequencing problems(probleme de stabilire a succesiunii unor operaţii). Denumirea probleme de ordonanţare este larg răspândită în literatura română de specialitate.

Al doilea tip de probleme se referă la proiecte sau lucrări care constau din activităţi ce trebuie executate într-o ordine dată. Aceste probleme cer să se determine cât de mare trebuie să fie efortul depus în executarea fiecărei activităţi şi când trebuie planificată fiecare activitate, astfel încât să se optimizeze o anumită măsură a executării proiectului în ansamblu. Aceste probleme pot fi gândite ca probleme de coordonare, dar sunt adesea denumite la fel ca metodele aplicate pentru rezolvarea lor: PERT şi drum critic.

II. PROBLEME DE ORDONANŢARE

Problemele de ordonanţarepot fi reprezentate printr-o matrice, astfel:

Tabelul nr. 1

Clienţi

(sau lucrări) Servicii Data la care

poate începe Data la

care

trebuie să termine

Activităţi prin care această

lucrare trebuie să

treacă în ordinea

cerută

Timp de

execuţie

Figura nr. 1.1

Se dă o mulţime formată din doi sau mai mulţi clienţi care trebuie serviţi sau din două sau mai multe lucrări ce trebuie executate, precum şi o muţime de unul sau mai multe servicii(activităţi) care trebuie efectuate pentru clienţi(lucrări). Trebuie să ştim când poate să înceapă fiecare lucrare şi până când trebuie termintă. De asemenea, trebuie să ştim ce activităţi sunt necesare pentru efecturea fiecărei lucrări, în ce ordine anume şi cât va dura fiecare operaţie.

Cel mai obişnuit context pentru asemenea probleme este un “magazin de lucrări”, adică un centru de producţie care prelucrează multe produse diferite, folosind o varietate de maşini. Într-un astfel de context, o problemă de ordonanţare este numită uneori problemă de planificare; nu se foloseşte acest termen aici pentru a evita o confuzie cu probleme de planificare din teoria aşteptării.

Trebuie subliniat faptul că problemele de ordonanţare pot apărea chiar dacă avem o singură activitate. De exemplu, dacă fiecare din lucrările ce trebuie executate are o dată la care trebuie terminată şi un “cost al întârzierii”, minimizarea costului total al întârzierii poate să nu fie uşor de obţinut. Astfel de probleme sunt destul de frecvente; un exemplu îl constituie stabilirea ordinii de acces a unor probleme la un calculator sau a unor urgenţe de medic.

Problemele de ordonanţare pot fi complicate, printr-un număr de condiţii, dintre care cele mai importante sunt:

1. Suprapuneri. Dacă o lucrare constă din fabricarea unui număr de produse similare(un lot), primul produs care rezultă dintr-o operaţie poate trece la operaţia următoare, înainte ca anumite produse ale lotului să fi intrat în prima operaţie.

2. Tipul de transport. Transportul produselor de la un loc de prelucrare la altul poate lua un timp apreciabil. Locurile unde se execută diferite operaţii se pot găsi chiar în fabrici diferite.

3. Refacerea lucrării. Dacă una din operaţii constă dintr-un control, produsele defecte pot fi înapoiate la o operaţie anterioară în vederea reluării acesteia, provocând fie o întârziere a produselor acceptabile, fie o separare a lucrării în două loturi. Dacă produsele defecte nu pot fi refăcute, poate apărea necesitatea de a începe o lucrare nouă.

4. Accelerări. Din cauza presiunilor din partea unui client sau a altcuiva, o lucrare poate fi scoasă din şir sau accelerată, adică i se poate schimba