Clasa a 7-a lecția 8 - 5 nov 2015
Lecție
Liste
Definiție
Definiție: în informatică o listă înlănțuită este o structură de date care constă dintr-un grup de noduri care împreună reprezintă o secvență. În forma ei cea mai simplă fiecare nod este format din date și o referință (înlănțuire) către nodul următor în secvență. Lista înlănțuită permite inserarea și ștergerea eficientă a elementelor de pe orice poziție în secvență.
Implementare
O primă implementare posibilă este folosind doi vectori: un vector v care memorează elementele listei (numere întregi de exemplu) și un vector next, care memorează indicele următorului element din listă. Perechea (v[i], next[i]) conține un nod al listei.
Operații cu liste
Inserare
 |
 // pos conține poziția nodului de inserat
next[pos] = next[i];
next[i] = pos; |
Ștergere
 |
 next[i] = next[next[i]]; |
Aplicație 1: v-ați ascunselea
n copii numerotați de la 1 la n și așezați în cerc numără la v-ați ascunselea, din k în k, începînd cu copilul 1. Date n și k să se afișeze ordinea în care ies copiii din cerc.
O rezolvare simplă este să memorăm numerele de la 1 la n într-un vector și apoi să avansăm k elemente și să afișăm elementul curent, iar apoi să îl setăm pe zero. Reluăm căutarea de n ori, ignorînd elementele zero. Deoarece avansul cu k copii poate să dureze n (căci sărim peste elemente zero) soluția are complexitate O(n2):
#include <stdio.h>
int v[100];
int main() {
int n, k, i, j, pos;
scanf( "%d%d", &n, &k );
for ( i = 0; i < n; i++ )
v[i] = i + 1;
pos = n - 1;
for ( i = 0; i < n; i++ ) {
// avanseaza k elemente nenule
for ( j = 0; j < k; j++ ) {
pos = (pos + 1) % n;
while ( v[pos] == 0 )
pos = (pos + 1) % n;
}
printf( "%d ", v[pos] );
v[pos] = 0;
}
printf( "\n" );
return 0;
} |
O soluție mai eficientă, care folosește liste, are complexitate O(n∙k):
#include <stdio.h>
int v[100], next[100];
int main() {
int n, k, i, j, pos;
scanf( "%d%d", &n, &k );
// initializam lista
for ( i = 0; i < n; i++ ) {
v[i] = i + 1;
next[i] = (i + 1) % n;
}
pos = n - 1; // pos e pozitia copilului din-nainte de copilul de eliminat
for ( i = 0; i < n; i++ ) {
// avanseaza k - 1 elemente deoarece eliminarea conteaza ca un element
for ( j = 1; j < k; j++ )
pos = next[pos];
printf( "%d ", v[next[pos]] );
next[pos] = next[next[pos]];
}
printf( "\n" );
return 0;
} |
Aplicație 2: bile1
Cei de clasa a 7a ați avut ca temă problema bile1 dată la ONI 2012 clasa a 7a. Problema poate fi rezolvată folosind o matrice caracteristică a obstacolelor. Dar dacă memoria permisă ar fi fost mai mică nu o puteam rezolva în acest fel. Rezolvarea cu liste necesită doar O(m+n+p) memorie. Ca structuri de date vom folosi:
- un vector b[n] care memoreaza linia cu bile, O(n), n fiind numărul de coloane
- un vector liste[m] care pentru linie pointează la o listă de coloane pe care se află obstacole, O(m), unde m este numărul de linii.
- doi vectori paraleli col[p] și next[p] care memoreaza coloanele obstacolelor și următorul obstacol pe linie, O(p), unde p este numărul de obstacole.
Algoritmul folosit este următorul:
1. Citește m, n și p, setează i la zero
2. Citește fiecare obstacol (l, c) si:
2.1 col[i] = c
2.2 adaugă coloana c la lista de pe linia l, liste[l]:
2.2.1 next[i] = liste[l]
2.2.2 liste[l] = i
2.3 i = i + 1
3. Citește vectorul de bile
4. Pentru fiecare linie l de la 1 la m
4.1 parcurge lista de coloane liste[l] si pentru fiecare obstacol col[i] din listă:
4.1.1 actualizează vectorul de bile la indicele coloanei, col[i]Cum se compară cu algoritmul inițial care folosește o matrice caracteristică? Timpul de execuție este O(m+n+p) față de O(m×n+p). Memoria folosită este O(m+n+p) față de O(m×n). Observăm că atît timpul cît și memoria se îmbunătățesc substanțial.
Vă rămîne ca temă opțională să implementați această soluție.
Aplicație 3: zigzag
Problema zigzag dată la ONI 2012 clasa a 7a are o rezolvare foarte ușoară cu liste. Ca și la bile1, vom ține minte pentru fiecare linie a matricei de codificare cîte o listă cu coloanele unde apar litere. Vom genera aceste liste parcurgînd în matrice pozițiile (l, c) unde s-ar afla textul și adăugînd coloana c la lista liniei l. Apoi vom parcurge aceste liste, în ordine, și vom atașa fiecărei celule, pe lîngă coloană, o literă din text. De fapt vom vedea că nici nu avem nevoie să stocăm coloanele, ci doar literele. În final vom parcurge celulele în ordinea alocării lor, deoarece ea este chiar ordinea textului decodificat.
O diferență față de bile1 este că va trebui să ținem nu numai vectorul cu începutul listelor ci și un vector cu ultimul element din listă pentru a putea face adăugarea la coadă foarte rapid. O alternativă ar fi să parcurgem pozițiile in ordine inversă (pare mai complicat, însă). Să denumim vectorii prim și ultim.
Iată algoritmul de generare a listelor:
// pregatim listele cu pozitiile in matricea cheie
// cheie este cheia, iar n este numărul de caractere al mesajului,
// c aloca celulele listei si este si coloana in acelasi timp
l = 0;
pas = 1; // initial linia creste din unu in unu
// nu putem avea celule pe indexul 0 deoarece cu zero codificam finalul
// de lista, deci codificam coloanele incepind cu 1, no biggie
for ( c = 1; c <= n; c++ ) {
// pentru fiecare coloana a matricei calculam
// linia corespunzatoare literei (este una singura!)
// liniile vor fi de la zero, nici un motiv sa le numerotam de la 1
// avem perechea (l, c): aseaza c in lista l
next[c] = 0; // nu urmeaza nimeni după mine, sint ultima celula
if ( prim[l] == 0 ) // lista este vida
prim[l] = ultim[l] = c;
else // avem un ultim element
ultim[l] = next[ultim[l]] = c;// atasam celula la coada ultimului element
// avanseaza linia
l = l + pas;
if ( l < 0 || l >= cheie ) { // daca am depasit marginea inversam pasul
pas = -pas;
l = l + pas + pas; // adunam de doua ori pasul pentru a ne intoarce
}
}Vă rămîne ca temă să continuați această implementare. Mai aveți de parcurs listele in ordinea naturală și atașat literele din text, iar la final să parcurgeți celulele în ordinea alocării lor (cu indicele c).
Aplicație 4: Generarea de permutări cu liste simplu înlănțuite
#include <stdio.h>
#define MAX_N 100
int val[MAX_N];
int next[MAX_N];
int prim;
int liber;
void init() {
prim = 0;
liber = 1;
}
void insereaza_fata(int x){
val[liber] = x;
next[liber] = prim;
prim = liber;
liber++;
}
int v[MAX_N];
void perm(int n, int pos){
int k, kp, a;
if(pos == n){
for(k = 0; k < n; k++)
printf("%d ", v[k]);
printf("\n");
} else {
v[pos] = val[prim];
a = prim;
prim = next[prim];
perm(n, pos + 1);
prim = a;
kp = prim;
k = next[prim];
while(k != 0){
v[pos] = val[k];
a = next[kp];
next[kp] = next[next[kp]];
perm(n, pos + 1);
next[kp] = a;
kp = k;
k = next[k];
}
}
}
int main() {
int n, i;
scanf("%d",&n);
init();
for (i = n; i >= 1; i--)
insereaza_fata(i);
/*
i = prim;
while( i != 0 ) {
printf( "%d " , val[ i ] );
i = next[ i ];
}
*/
perm(n, 0);
return 0;
}Analiză amortizată
Despre analiza amortizată. Citat din CLR: În analiza amortizată facem media timpului necesar pentru a executa o secvență operații, împărțindu-l la toate operațiile executate. Prin analiza amortizată putem să arătăm că costul mediu al unei operații este mic, atunci cînd împărțim la numărul de operații, cu toate că o singură operație din secvență ar putea fi "scumpă". Acest cost mediu per operație se mai numește și costul amortizat.
Să luăm cîteva exemple clasice de analiză amortizată
Incrementarea unui contor binar
Să presupunem că vrem să incrementăm un număr binar ale cărui cifre se află într-un vector. Numărul are n cifre, cea mai puțin semnificativă cifră (ultima din număr) fiind stocată prima în vector. Cum arată această incrementare?
i = 0;
while ( v[i] == 1 ) {
v[i] = 0;
i++;
}
v[i] = 1;Vom face această operatiune de 2n ori, pentru a trece prin toate valorile binare posibile. Întrebarea este care este numărul de operații per incrementare?
Un răspuns intuitiv ar fi că numărul maxim de operații la o incrementare oarecare este n, deci probabil că numărul mediu de operații este n/2, ceea ce ne duce la un timp O(n) per incrementare. Desigur că răspunsul este incorect. Să încercăm să-l calculăm mai exact. Vom calcula numărul total de operații pe parcursul tuturor incrementărilor și îl vom împărți la numărul de incrementări, 2n.
Să observăm că ultima cifră își va schimba valoarea la fiecare incrementare. Penultima numai din doi în doi. Antepenultima numai din patru în patru și așa mai departe. De unde rezultă că numărul total de cifre schimbate (egal cu numărul de operații total) este:
T(n) = 2n + 2n-1 + 2n-2 + ... + 21
Această sumă se calculează folosind formula sumei unei progresii geometrice, pe care o veți învăța abia în clasa a zecea. Pînă atunci să folosim un artificiu: să observăm că numărul T(n) este 111...110 în baza doi. El conține n cifre 1, iar ultima cifră este zero deoarece 20 lipsește din sumă. Ce se întîmplă dacă adunăm 2 la acest număr? Vom obține:
111...110(2) + 2(10) = 100...0(2) (1 cu n+1 zerouri)
Acest număr este 2n+1. Rezultă că:
T(n) + 2 = 2n+1
și deci
T(n) = 2n+1 - 2
Acesta este numărul total de operații, pentru toate incrementările. Împărțind la numărul de incrementări, care este 2n, obținem aproximativ două operațiuni per incrementare!
Iată cum, folosind analiza amortizată, am obținut un rezultat mult mai bun. În loc de O(n) am aflat că incrementarea unui contor binar este O(1)!
Permutări
Am studiat în lecțiile trecute algoritmi de generare a permutărilor. Întrebarea, ca și la exercițiul anterior, este cîte operații ne costă generarea unei permutări? Un prim răspuns, intuitiv, este că trebuie să așezăm n elemente în vector pentru fiecare permutare, deci probabil costul este O(n). Desigur că este greșit. Să încercăm să îl calculăm:
Să considerăm al doilea algoritm studiat, cel cu liste, deoarece calculul este mai ușor. În acest caz avem n niveluri de recursivitate, la fiecare nivel așezînd cifre, astfel:
- pe nivelul 1 vom așeza n cifre
- pentru fiecare cifră de pe nivelul 1, pe nivelul 2 vom așeza n-1 cifre
- pentru fiecare cifră de pe nivelul 2, pe nivelul 3 vom așeza n-2 cifre
- ...
- pentru fiecare cifră de pe nivelul n-1, pe nivelul n vom așeza o cifră
Vom avea în total n! așezări de cifre. Dar cît durează așezarea unei cifre? Mulțumită listelor, la fiecare nivel parcurgem strict lista de cifre nefolosite, ceea ce înseamnă că așezarea unei cifre este O(1). De aici rezultă că numărul total de operații este O(n!). Deoarece avem n! permutări rezultă că generarea unei permutări ne costă O(1)! Din nou un rezultat surprinzător. Desigur că acest rezultat nu ia în calcul afișarea permutărilor, ci doar generarea lor în vector.
Să considerăm acum primul agoritm, cel care folosește un vector de incluziune pentru a ști dacă o cifră a mai fost folosită, înainte de a o plasa pe poziția curentă. Calculul este similar, pînă ajungem la întrebarea cît ne costă să așezăm o cifră. Aici ne împotmolim, deoarece nu este clar. La primul nivel ne costă o operație per cifră, dar undeva la mijloc vom face tot n operații pentru a așeza doar n/2 cifre, deoarece parcurgem toate cifrele pentru a determina care sînt cele așezabile. Ce facem în acest caz? Să folosim din nou matematica. Să notăm cu T(k) costul pentru a așeza permutările de k (ultimele k poziții ale vectorului de permutări). În final ne va interesa T(n). Observație: nivelurile sînt numerotate invers față de primul calcul. Prima poziție în permutare va fi considerată nivelul n, iar ultima poziție este nivelul 1.
Ce operațiuni efectuăm pe nivelul k? În primul rînd o parcurgere a tuturor elementelor, pentru a vedea dacă le putem folosi, deci n operații. Apoi, pentru fiecare element așezat vom chema recursiv funcția, deci vom avea k apeluri la nivelul k-1:
T(k) = n + k T(k-1)
T(k) = n + k { n + (k-1)[n + (k-2)(n + ... + 3(n + 2 T(1)) ... )]}
T(k) = n + k n + k(k-1)n + k(k-1)(k-2)n + ... + k(k-1)(k-2)...3 n + k(k-1)(k-2)...3 2 T(1)
Dar T(1) este n, deoarece vom parcurge toate elementele și vom așeza unul singur. Așa încît:
T(k) = n + n(k + k(k-1) + k(k-1)(k-2) + ... + k(k-1)(k-2)...3 + k(k-1)(k-2)...3 2)
T(k) = n + n(k!/(k-1)! + k!/(k-2)! + k!/(k-3)! + ... + k!/2! + k!/1!)
T(k) = n + nk!(1/(k-1)! + 1/(k-2)! + 1/(k-3)! + ... + 1/2! + 1/1!)
Suma dintre paranteze va fi studiată în clasa a zecea. Se demonstrează că ea este mai mică decît o constantă e = 2.71828.... Drept pentru care:
T(k) = n + enk!
Numărul total de operații se obține pentru k = n:
T(n) = n(1 + e n!)
Atunci cînd împărțim acest număr la numărul de permutări generate, n!, obținem costul per permutare ca fiind aproximativ e n, adică O(n). De unde rezultă că acest algoritm este inferior celui cu liste.
Clădiri vizibile
Să presupunem că avem n clădiri înșirate pe o stradă, lipite una de alta. Se cunosc înălțimile fiecărei clădiri. Pornind de la stînga la dreapta și mergînd pe acoperișurile clădirilor ne întrebăm, pentru fiecare acoperiș, ce clădire vedem la acea înălțime uitîndu-ne înapoi, spre stînga.
Să traducem această problemă în limbaj informatic: dat un vector v de n numere naturale să se calculeze un vector w, unde w[i] este v[j], j cel mai mare indice j < i astfel încît v[j] > v[i]. Cu alte cuvinte pentru fiecare element din vectorul v vom căuta primul element înapoi mai mare decît el.
Soluție elegantă: parcurgem v și menținem un vector s de elemente interesante, în care așezăm la rînd elemente din v, astfel: la pasul i vom șterge din s ultimele elemente, cele mai mici decît v[i]. Ultimul element rămas în s este chiar w[i]. Apoi îl adăugăm pe v[i].
Exemplu:
Fie vectorul de înălțimi ''v = [9 3 4 5 1 2 2]''
Vectorul s = []
Pasul 1:
s este gol, nu există nici un element mai mare ca 9
w = [X]
Adăugăm v[1] la s:
s = [9]
Pasul 2:
Scoatem din s toate elementele mai mici sau egale cu v[2] (nici unul)
Ultimul element din s este w[2]
w = [X 9]
Adăugăm v[2] la s:
s = [9 3]
Pasul 3:
Scoatem din s toate elementele mai mici sau egale cu v[3]
s = [9]
Ultimul element din s este w[3]
w = [X 9 9]
Adăugăm v[3] la s:
s = [9 4]
Pasul 4:
Scoatem din s toate elementele mai mici sau egale cu v[4]
s = [9]
Ultimul element din s este w[4]
w = [X 9 9 9]
Adăugăm v[4] la s:
s = [9 5]
Pasul 5:
Scoatem din s toate elementele mai mici sau egale cu v[5] (nici unul)
s = [9 5]
Ultimul element din s este w[5]
w = [X 9 9 9 5]
Adăugăm v[5] la s:
s = [9 5 1]
Pasul 6:
Scoatem din s toate elementele mai mici sau egale cu v[6]
s = [9 5]
Ultimul element din s este w[6]
w = [X 9 9 9 5 5]
Adăugăm v[6] la s:
s = [9 5 2]
Pasul 7:
Scoatem din s toate elementele mai mici sau egale cu v[7]
s = [9 5]
Ultimul element din s este w[7]
w = [X 9 9 9 5 5 5]
Adăugăm v[7] la s:
s = [9 5 2]
Ce complexitate are acest algoritm? Ar părea că la fiecare pas putem scoate din vectorul s n elemente, caz în care algoritmul ar avea complexitate O(n2). Să încercăm să calculăm numărul total de operații.
Deși nu știm cîte operații vom face la fiecare pas, observăm următorul lucru: fiecare element din vectorul v este adăugat fix o dată și scos fix o dată. Atunci cînd eliminăm elemente din s scoatem acele elemente adăugate anterior. Drept pentru care numărul total de operații va fi 2n. Complexitatea amortizată a adăugării unui element în s este, de fapt O(1), iar întregul algoritm are complexitate O(n).
Problema bibliotecarului (coada implementată cu două stive)
Un bibliotecar primește cărți una cîte una și le returnează în aceeași ordine, la cerere. În spatele ghișeului el are doi subalterni. Bibliotecarul trebuie să dea cărțile primite unuia din subalterni. Poate de asemenea să ceară înapoi cărți de la subalterni. Fiecare subaltern ține o stivă de cărți. Atunci cînd bibliotecarul îi dă o carte subalternul o pune peste toate celelalte, în stiva sa. Atunci cînd bibliotecarul îi cere o carte o ia pe prima din stivă și i-o returnează. Voi trebuie să găsiți algoritmul de funcționare a bibliotecarului astfel încît după un număr mare de depuneri și cereri de cărți numărul total de operații (înmînări de cărți) să fie cît mai mic ca complexitate. Puteți presupune că vor fi 500000 de depuneri de cărți și 500000 de cereri, în orice ordine coerentă.
Rezolvarea directă, evidentă, este, surprinzător, și cea corectă: bibliotecarul va da toate cărțile primite subalternului 1. Cînd i se cere o carte, i-o va cere subalternului 2. Dacă subalternul 2 nu are cărți atunci el îi va cere, pe rînd cărți subalternului 1 și i le va da subalternului 2, pînă ce subalternul 1 nu mai are cărți. Apoi returnează cartea pe care i-o va da subalternul 2.
Funcționează corect acest algoritm? Desigur, urmăriți un exemplu și vă veți convinge. Dar pare foarte ineficient! Pentru o carte cerută este posibil ca bibliotecarul să facă n operații! Să facem același calcul ca și mai devreme: orice carte va fi depusă la primul subaltern, apoi scoasă și depusă la cel de-al doilea subaltern și apoi returnată. Drept pentru care numărul total de operații va fi 3n, iar costul amortizat al unei operații de depunere sau de scoatere va fi O(1).
Concluzii
Cu aceasta am încheiat exemplele de analiză amortizată. Remarcați ce au ele în comun: de cele mai multe ori în analiza amortizată avem o stivă. Un vector în care depunem la coadă elemente și din care ștergem tot de la coadă toate elementele mai mari ca elementul pe care îl adăugăm. Evident poate fi pe dos în cazul cînd ne interesează minime.
Oare ne folosește la ceva analiza amortizată, sau este doar ceva pur academic? Ei bine, ea se dă destul de frecvent la olimpiadă (este posibil să nu o fi remarcat pînă acum pentru că nu știați semnalmentele după care să vă uitați). În lecția următoare vom vedea probleme cu analiză amortizată date la olimpiada de informatică și alte concursuri.
Temă
Pentru data viitoare veți avea de rezolvat următoarele probleme:
Rezolvări aici ...
