Clasa a VII-a lecția 11 - 21 nov 2019

Tema - rezolvări

Comentarii generale

• La problema oraș: unii ați testat brut conturul, cu opt teste individuale. Cam urît.
• La problema oraș: unii ați scris două funcții de fill aproape identice. De ce scriem funcții? Tocmai ca să nu repetăm cod. Vă rog factorizați.

Comentarii individuale

Am selectat anumite surse unde mi s-a părut că am ce comenta mai mult decît la altele.

Prima grupă

• Benescu: la enclave nu mi-e clar că ai înțeles definiția perimetrului. Funcția trebuia să semene cu cea de la curs, nu? La oraș puteai să scrii o singură funcție de fill. Nu duplica cod, factorizează!
• Mocanu: la problema oraș: te rog indentează, ne supărăm rău! O singură instrucțiune pe linie! Te rog nu mai folosi (i,j) pentru linie și coloană, folosește (l,c). Programul nu-ți trece nici un test din cauza primului punct. Greșești cumva recursivitatea. Nu era nevoie de recursivitate, se poate face iterativ. Faci căutare de caracter diferit de '.' în matrice astfel:

  i=1;
  j=1;
  while(i<=n && v[i][j]=='.'){
    j=1;
    while(j<=m && v[i][j]=='.'){
      j++;
    }
    if(v[i][j]=='.'){
      i++;
    }
  }

Corect era:

  i=1;
  j=m+1;
  while(i<=n && j>m){
    j=1;
    while(j<=m && v[i][j]=='.'){
      j++;
    }
    i++;
  }

Sau:

  i=1;
  j=1;
  while(i<=n && v[i][j]=='.'){
    j++;
    if(j>m){
      i++;
      j=1;
    }
  }

A doua grupă

• Cadîr: soluție bună la oraș, bun! Nimic la enclave?
• Grecu: soluție bună la oraș, bravo! Nimic la enclave, chiar așa?
• Ipate: la problema enclave: cred că programul nu funcționează pentru că calculează altceva. Cerința este puțin ambiguă, dar exemplul o clarifică. Nu ai de ce să calculezi aria unei enclave.
• Moroșan: la oraș: nu așa citim caractere în C. Vezi te rog lecția de lucru cu caractere de clasa a cincea la arhivă, pe algopedia: http://algopedia.ro/wiki/index.php/Clasa_a_V-a_lec%C8%9Bia_18_-_7_dec_2017 Ai rezolvat doar primul subpunct, nu ai vrut să încerci nimic la fill? La enclave ai schițat un început, dar atît. Nu faci bordare, drept care fill iese din matrice. Cred că te apuci tîrziu de teme și intri în criză de timp.
• Nicu: la oraș ai o funcție tip void, fill1(), care returnează un parametru primit ca pointer. Nu era mai simplu să returnezi o valoare? Ai două funcții de fill aproape identice, factorizează! La enclave: cred că nu-ți funcționează și pentru că tu calculezi și aria. Vezi comentariul din soluție, nu aveai de ce să calculezi aria.
• Stancu: la oraș: ai scris funcții pur recursive, simpatic :) Nu aveai restricții la așa ceva, bănuiesc că ai vrut să exersezi? Programul tău calculează bine punctele 1 și 2. La 3 i-am făcut modificări minimale pentru a-l corecta, problema era în funcția fillpmax(). Ti-am trimis pe email programul corectat. Felicitări, este foarte clar scris, altfel nu aș fi avut cum să îl depanez. Enclave nimic? Sînt convins că puteai să o rezolvi.
• Voicu: la oraș: te-ai complicat la calculul perimetrului. Nu era nevoie de fill. Și chiar dacă îl făceai, el trebuia repetat în buclă, căci nu spune nimeni că orașul este conex. Celelalte două subpuncte funcționează. Felicitări, un program aproape reușit! Un pic cam încîlcit, dar rezolvăm pe parcurs. La enclave: insist să nu plasezi 'return' acolo unde ai chef tu. La IQ Academy nu se acceptă programare nestructurată. Și pentru că ai întrebat, nu este ok să ai atîtea variabile globale, este rețeta bug-urilor. Pentru început le acceptăm.

Oraș

Problema oras a fost dată la concursul .campion în anul 2011.

Enclave

Problema enclave este o problemă de introducere în flood fill.

Tema opțională - rezolvări

Problema ozn

Problema ozn este o problemă de flood fill.

Rezolvări aici [1]

Lecție - analiză amortizată

<html5media height="720" width="1280">https://www.algopedia.ro/video/2019-2020/2019-11-21-clasa-7-lectie-info-11-720p.mp4</html5media>

Despre analiza amortizată. Citat din CLRS: Î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 2ⁿ 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, 2ⁿ.

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) = 2ⁿ + 2^n-1 + 2^n-2 + ... + 2¹

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 2⁰ lipsește din sumă. Ce se întîmplă dacă adunăm 2 la acest număr? Vom obține:

111...110₍₂₎ + 2₍₁₀₎ = 100...0₍₂₎ (1 cu n+1 zerouri)

Acest număr este 2ⁿ⁺¹. Rezultă că:

T(n) + 2 = 2ⁿ⁺¹

și deci

T(n) = 2ⁿ⁺¹ - 2

Acesta este numărul total de operații, pentru toate incrementările. Împărțind la numărul de incrementări, care este 2ⁿ, 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:

Permutări cu liste

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 n vom așeza n cifre
• pentru fiecare cifră de pe nivelul n, pe nivelul n-1 vom așeza n-1 cifre
• pentru fiecare cifră de pe nivelul n-1, pe nivelul n-2 vom așeza n-2 cifre
• ...
• pentru fiecare cifră de pe nivelul 2, pe nivelul 1 vom așeza o cifră

Observație: ceea ce am denumit nivelul n este de fapt prima poziție în vectorul în care generăm permutările, nivelul n-1 este de fapt a doua poziție, și așa mai departe, nivelul 1 fiind ultima poziție din vector.

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 k operații. Apoi, pentru fiecare element așezat vom chema recursiv funcția, deci vom avea k apeluri la nivelul k-1:

T(k) = k + k T(k-1)
T(k) = k + k { (k-1) + (k-1)[(k-2) + (k-2)((k-3) + ... + 3(2 + 2 T(1)) ... )]}
T(k) = k + k(k-1) + k(k-1)(k-2) + ... + k(k-1)(k-2)...3 + k(k-1)(k-2)...3 2 + k(k-1)(k-2)...3 2 T(1)

Dar T(1) este 1, deoarece vom așeza un singur element. Așa încît:

T(k) = k + k(k-1) + k(k-1)(k-2) + ... + k(k-1)(k-2)...3 + k(k-1)(k-2)...3 2 + k(k-1)(k-2)...3 2 1)
T(k) = k!/(k-1)! + k!/(k-2)! + k!/(k-3)! + ... + k!/2! + k!/1! + k!/0!
T(k) = k!(1/(k-1)! + 1/(k-2)! + 1/(k-3)! + ... + 1/2! + 1/1! + 1/0!)

Suma:

1/0! + 1/1! + 1/2! + ... + 1/(k-1)!

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) ≅ e·k!

Numărul total de operații se obține pentru k = n:

T(n) = e·n!

Deoarece avem n! permutări rezultă că generarea unei permutări ne costă O(e) = 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.

Permutări cu vector de frecvență

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).

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 este, din nou, mai mică decît e-1, unde e este constanta e = 2.71828.... Drept pentru care:

T(k) ≅ n + (e-1) n k!

Numărul total de operații se obține pentru k = n:

T(n) = n + (e-1) n 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-1) n, adică O(n). De unde rezultă că acest algoritm este inferior celui cu liste.

Ar trebui să vedem că algoritmul cu liste este de x ori mai rapid, unde x=(e-1) n/e=(1-1/e)n. Pentru n=10 numărul x este circa 6.32. În realitate vom obține mai puțin deoarece algoritmul cu liste are o constantă multiplicativă ceva mai mare. Pe algoritmii prezentați am măsurat circa 3.8.

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. 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 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ția forță brută este ca pentru fiecare indice i să căutăm spre stînga primul indice j unde găsim un element mai mare. Această soluție este O(n²).

Soluție elegantă: parcurgem v și menținem o stivă 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 = [7 3 2 5 4 3 9 7]''
  Stiva s = []
  Vectorul w = []
Pasul 0:
  Scoatem din s toate elementele mai mici sau egale cu v[0] == 7
  s este goală, nu există nici un element mai mare ca v[0] == 7
  Calculăm w[0] = vîrful stivei = nu există, deci îl vom marca cu X 
    (X este o valoare ce indică lipsa unui element mai mare ca v[0] la stînga)
  Adăugăm v[0] == 7 la s
  Obținem:
    v = [7 3 2 5 4 3 9 7]
    w = [X]
    s = [7]

Pasul 1:
  Scoatem din s toate elementele mai mici sau egale cu v[1] == 3
  Nu există astfel de elemente, deci stiva rămîne nemodificată
  Calculăm w[1] = vîrful stivei = 7
  Adăugăm v[1] == 3 la s
  Obținem:
    v = [7 3 2 5 4 3 9 7]
    w = [X 7]
    s = [7 3]

Pasul 2:
  Scoatem din s toate elementele mai mici sau egale cu v[2] == 2
  Nu există astfel de elemente, deci stiva rămîne nemodificată
  Calculăm w[2] = vîrful stivei = 3
  Adăugăm v[2] == 2 la s
  Obținem:
    v = [7 3 2 5 4 3 9 7]
    w = [X 7 3]
    s = [7 3 2]

Pasul 3:
  Scoatem din s toate elementele mai mici sau egale cu v[3] == 5
  Vom elimina ultimele două elemente, 3 și 2, deci stiva devine s = [7]
  Calculăm w[3] = vîrful stivei = 7
  Adăugăm v[3] == 5 la s
  Obținem:
    v = [7 3 2 5 4 3 9 7]
    w = [X 7 3 7]
    s = [7 5]

Pasul 4:
  Scoatem din s toate elementele mai mici sau egale cu v[4] == 4
  Nu există astfel de elemente, deci stiva rămîne nemodificată
  Calculăm w[4] = vîrful stivei = 5
  Adăugăm v[4] == 4 la s
  Obținem:
    v = [7 3 2 5 4 3 9 7]
    w = [X 7 3 7 5]
    s = [7 5 4]

Pasul 5:
  Scoatem din s toate elementele mai mici sau egale cu v[5] == 3
  Nu există astfel de elemente, deci stiva rămîne nemodificată
  Calculăm w[5] = vîrful stivei = 4
  Adăugăm v[5] == 3 la s
  Obținem:
    v = [7 3 2 5 4 3 9 7]
    w = [X 7 3 7 5 4]
    s = [7 5 4 3]

Pasul 6:
  Scoatem din s toate elementele mai mici sau egale cu v[6] == 9
  Vom elimina toate elementele din s, deci stiva devine vidă
  Calculăm w[6] = vîrful stivei = nu există, deci îl vom marca cu X
  Adăugăm v[6] == 9 la s
  Obținem:
    v = [7 3 2 5 4 3 9 7]
    w = [X 7 3 7 5 4 X]
    s = [9]

Pasul 7:
  Scoatem din s toate elementele mai mici sau egale cu v[7] == 7
  Nu există astfel de elemente, deci stiva rămîne nemodificată
  Calculăm w[7] = vîrful stivei = 9
  Adăugăm v[7] == 7 la s
  Obținem:
    v = [7 3 2 5 4 3 9 7]
    w = [X 7 3 7 5 4 X 9]
    s = [9 7]

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(n²). 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ă

• Tema 11 clasa a 7^a
  • tower dată la Shumen 2016 juniori
  • maxp dată la OJI 2013 clasa a 8^a
  • nrtri dată pregătire Vianu clasa a 9^a

• Tema 11 opțională clasa a 7^a
  • nrtri1 problemă identică cu nrtri cu limitele modificate

Rezolvări aici [2]