Extras din laborator
1. Un graf se numeşte rar dacă numărul său de muchii m este mai mic decât , unde n reprezintă numărul de vârfuri. O justificare este aceea că matricea de adiacenţă A a grafului, care ocupă n2 locaţii de memorie, poate fi întotdeauna reprezentată folosind O( ) locaţii de memorie, astfel încât răspunsul la o întrebare „A(i, j) = 1 ?” să se facă în O(1). Descrieţi o astfel de schemă de reprezentare.
Soluţie:
Având în vedere faptul că în matricea de adiacenţă A a unui graf fiecare element
A(i, j) poate lua doar valorile 0 şi 1, este suficient un singur bit pentru a memora aceste informaţii.
Pentru reducerea spaţiului ocupat de matricea de adiacenţă se propune următoarea schemă de reprezentare:
- matricea A este împărţită în matrice pătratice de dimensiune X ;
- numărul acestor matrice este ;
- se creează o nouă matrice pătratică A’ de dimensiune ;
- fiecare element al matricei A’ este o codificare a unei matrice de dimensiune X după cum urmează:
o o astfel de matrice are log n elemente ce pot lua doar valorile 0 şi 1;
o dacă matricea este parcursă pe linii se obţine o segvenţă de log n biti;
o fiecare astfel de segvenţă poate fi reprezentarea binară a unui număr între 0 şi 2log n = n;
o fie B o matrice de dimensiune X obţinută prin partiţionarea lui A ca mai sus, cu B(i,j) = A(k1 +i, k2 +j) şi fie s secventa de biti obtinută prin parcurgerea matricei B pe linii; atunci A’(k1, k2) = m, unde m este numărul a cărui reprezentare binară este s;
o având în vedere că reprezentarea binară a numerelor naturale este unică, dacă B1 ≠ B2, atunci s1 ≠ s2 şi m1≠ m2;
- obţinerea răspunsului la întrebarea: „A(i, j) = 1 ?”: valoarea lui A(i,j) se poate obţine din matricea A’ astfel:
o din modul de partiţionare a lui A se constată că elementul A(i,j) se obţine din procesarea elementului A’( , );
o reprezentarea binară a elementului A’( , )este succesiunea liniilor matricii B, unde B(p,q) = A(i,j), cu
p = i mod şi q = j mod , adică bitul de pe poziţia (i mod )* + j mod din reprezentarea binară a lui A’( , ), numărând de la stânga la dreapta;
Observaţie: Având în vedere faptul că numănul n nu se împarte întotdeauna exact la , este posibil ca matricele de la extremităţile dreapta, respectiv jos ale matricei A matricele obţinute prin patriţionare să nu aibă dimensiunile cerute, ci dimensiuni mai mici.
De exemplu, o matrice de dimendiune 5 X 5 trebuie patriţionată în matrici de dimensiune 2 X 2. Coloana a cincea va fi deci împărţită în 3 matrice, două de dimensiune 2 X 1 şi una de dimensiune 1 X 1. Aceste matrice vor fi „extinse” la matrice de dimensiune 2 X 2 astfel:
Fie B1 o matrice de dimensiune 2 X 1 (de exemplu, B1(0,0) = A(0,4) şi B1(1,0) = A(1,4) şi B2 matricea de dimensiune 2 X 2 la care va fi extinsă B1; atunci B2(0,0) = B1(0,0), B2(1,0) = B1(1,0), iar B2(0,1) şiB2(1,1) pot avea oricare din valorile 0 şi 1. B2(0,0) B2(0,1), B2(1,0), B2(1,1) este reprezentarea binară a valorii elementului A’(2,0).
Am văzut mai sus cum se face extragerea dintr-un element al lui A’ a bitului care reprezintă valoarea lui A(i, j). De acolo ne dăm seama că nu se va încerca niciodată extragerea unui bit care nu corespunde unui element din matricea A, deci valorile elementelor adăugate la extinderea matricelor B nu au importanţă.
- complexităţi:
o matricea A’ are elemente, deci complexitatea spaţiu a reprezentării sale este O( );
o operaţiile de calcul al elementului corespunzător lui A(i,j) din A’ se fac prin efectuarea unor împărţiri sau calcule de resturi, operaţii ce necesită timp constant O(1);
o accesul la elementele matricei A’ se face în timp constant O(1);
o extragerea unui bit din reprezentarea binară a unui element din A’ se poate face în timp constant O(1) prin operaţii logice pe biţi (utilizându-se eventual o mască);
În concluzie,răspunsul la întrebarea: „A(i, j) = 1 ?” se poate obţine în timp constant (independent de n) O(1).
2. Diametrul unui graf este lungimea maximă a unui drum de lungime minimă între două vârfuri ale grafului. Două vârfuri care sunt extremităţile unui drum minim de lungime maximă în graf se numesc diametral opuse. Demonstraţi că următorul algoritm determină o pereche de vârfuri diametral opuse într-un arbore T :
• Dintr-un vârf oarecare se execută o parcurgere BFS a arborelui; fie u ultimul vârf vizitat;
• Din vârful u se executa o parcurgere BFS a arborelui; fie v ultimul vârf vizitat;
• Return u, v.
Rămâne valabil algoritmul pentru un graf conex arecare?
Soluţie :
Preview document
Conținut arhivă zip
- AlgGr_Tema1.doc
- AlgGr_Tema10r.doc
- AlgGr_Tema11.doc
- AlgGr_Tema12.doc
- AlgGr_Tema2.doc
- AlgGr_Tema3.doc
- AlgGr_Tema4.doc
- AlgGr_Tema5f.doc
- AlgGr_Tema6f.doc
- AlgGr_Tema7f.doc
- AlgGr_Tema8f.doc
- AlgGr_Tema9f.doc
- g01.doc
- g02.doc
- g03.doc
- g04.doc
- g05.doc
- g06.doc
- g07.doc
- g08.doc
- g09.doc
- g10.doc
- g11.doc
- g12.doc
Alții au mai descărcat și
Lucrarea nr. 1 Structura de arbore. Arbori generalizati 1. Scopul lucrarii este prezentarea structurii de arbore si a operatiilor de baza ce se...
LISTE SIMPLU ÎNLANTUITE 1. Continutul lucrarii În lucrare sunt prezentate operatiile importante asupra listelor simplu înlantuite si...
Shell Unix Shell-ul este principala interfată de comunicare între utilizator si sistemul de operare. Desi, în mod intuitiv, shell-ul este...
MODULUL 1 1. CONCEPTE DE BAZĂ ALE TEHNOLOGIEI INFORMAŢIEI 1.1 HARDWARE, SOFTWARE ŞI TEHNOLOGIA INFORMAŢIEI (TI) “Modul cum culegi, administrezi...
Cap.1. Noţiuni de bază despre interfeţe de proces În primul capitol, Noţiuni de bază despre interfeţe de proces, se va defini termenul de proces,...
Un graf orientat G este format dintr-o pereche ordonata de multimi G=(X,U). ca si in cazul grafurilor neorientate, X este multimea varfurilor sau...
Te-ar putea interesa și
INTRODUCERE IN TEORIA GRAFURILOR Exista situatii când oameni ce lucreaza în diverse domenii ajung la reprezentarea unor cazuri concrete prin...
CAPITOLUL 1 NOTIUNI TEORETICE PRIVIND COSTURILE SI CALCULATIA COSTURILOR 1.1 DEFINIREA CALCULATIEI COSTURILOR Necesitatea cunoaşterii...
1. Introducere Numeroase situatii din viata cotidiana pot fi modelate cu ajutorul teoriei grafurilor. Teoria grafurilor este o importanta...
Am ales aceasta tema in scopul de a va arata ca si in informatica exista distante (adica ”drumuri”) atat minime cat si maxime intre elementele unui...
Într-o mare varietate de contexte se pune problema deplasãrii unei cantitãti Q ce poate fi materie, energie, informatie, etc. din unele locuri...
Planul temei 1. Procesul asociativ: baza analizei co-ocurentelor 2. Ce semnifica termenul de ocurenta? 3. Fazele analizei co-ocurentelor 4....
Lucrarea 1 ERORI SCOPUL LUCRĂRII În prima parte a lucrării se prezintă conceptele fundamentale ale reprezentării numerelor reale, utile în...
1.1. Elemente de logica a problemelor economice Prin „problema” se întelege o dificultate care, neputând fi depasita în mod automat, presupune o...