Probleme de acoperire

Probleme de acoperire (partea I)

h1. Probleme de acoperire

h1. Probleme de acoperire (partea I)

(Categoria _Algoritmi_, autor _Cosmin Negruşeri_)

(Categoria _Algoritmi_, Autor _Cosmin Negruşeri_)

(toc){width: 33em}*{text-align:left} *Cuprins:*
* 'Problema 1 ( _Olimpiada de informatică, Bucureşti, etapa pe sector, 1995,_ [1] ) ':probleme-de-acoperire#prob1
* 'Problema 2 ( _Lot 2001,_ [1] ) ':probleme-de-acoperire#prob2
* 'Problema 3 ( _Concursul naţional de informatică Lugoj, 1998_ ) ':probleme-de-acoperire#prob3
* 'Problema 4':probleme-de-acoperire#prob4
* 'Problema 5':probleme-de-acoperire#prob5
* 'Problema 6 ( _ONI 2001, clasa a X-a,_ [3] ) ':probleme-de-acoperire#prob6
* 'Problema 7 ( _ACM ICPC 1997_ ) ':probleme-de-acoperire#prob7
* 'Problema 8 ( _Lot matematică 2001, acm.uva.es - 10644 Floor tiles_ ) ':probleme-de-acoperire#prob8
* 'Problema 9':probleme-de-acoperire#prob9
* 'Concluzii':probleme-de-acoperire#concl
* 'Bibliografie':probleme-de-acoperire#biblio

== include(page="template/implica-te/scrie-articole" user_id="marius") ==
 
(toc){width: 33em}*{text-align:center} *Conţinut*
* 'Problema 1 (Olimpiada de Informatică, Bucureşti, 1995)':probleme-de-acoperire-1#problema1
* 'Problema 2 (Lot 2001)':probleme-de-acoperire-1#problema2
* 'Problema 3 (Concursul Naţional de Informatică Lugoj, 1998)':probleme-de-acoperire-1#problema3
* 'Problema 4':probleme-de-acoperire-1#problema4
* 'Problema 5':probleme-de-acoperire-1#problema5
* 'Problema 6 (ONI 2001)':probleme-de-acoperire-1#problema6
* 'Problema 7 (ACM ICPC 1997)':probleme-de-acoperire-1#problema7
* 'Problema 8 (Lot matematică 2001, acm.uva.es)':probleme-de-acoperire-1#problema8
* 'Problema 9':probleme-de-acoperire-1#problema9
* 'Concluzii':probleme-de-acoperire-1#concluzii
* 'Bibliografie':probleme-de-acoperire-1#bibliografie

În acest prim articol vom prezenta o serie de probleme apărute la concursurile de programare care au o tematică similară şi anume aceea de acoperire în plan. În general acest tip de probleme sunt $NP complete$, dar pentru cazurile particulare prezentate problemele sunt rezolvabile. Cea de a doua parte a articolului o puteţi găsi în "$secţiunea următoare...$":probleme-de-acoperire2.

h2(#prob1). Problema 1 ( _Olimpiada de informatică, Bucureşti, etapa pe sector, 1995,_ [1] )

h2(#prob1ema1). Problema 1 ( _Olimpiada de informatică, Bucureşti, etapa pe sector, 1995,_ [1] )

bq. Se dă un pătrat de latură $2^n^$ care se împarte în pătrate disjuncte de latură $1$. Unul dintre aceste pătrate se elimină. Se cere acoperirea suprafeţei rămase cu piese de forma:

Se vede clar acum, cum prin metoda $divide et impera$ putem să acoperim întreg pătratul cu piesele cerute.

h2(#prob2). Problema 2 ( _Lot 2001,_ [1] )

h2(#prob1ema2). Problema 2 ( _Lot 2001,_ [1] )

bq. Se dă un pătrat de latură $6N + 1$ care se împarte în pătrate disjuncte de latură $1$. Unul dintre aceste pătrate se elimină. Se cere acoperirea suprafeţei rămase cu piese de forma:

p=. !probleme-de-acoperire?P22.jpg!

h2(#prob3). Problema 3 ( _Concursul naţional de informatică Lugoj, 1998_ )

h2(#prob1ema3). Problema 3 ( _Concursul naţional de informatică Lugoj, 1998_ )

bq. Să se acopere complet un pătrat de latură $N >= 6$ cu următoarele piese, astfel ca fiecare piesă să fie folosită cel puţin o dată.

p=. !probleme-de-acoperire?P33.jpg!

h2(#prob4). Problema 4

h2(#prob1ema4). Problema 4

bq. Să se determine dacă putem acoperi o tablă de dimensiune $N x N$ cu dominouri după ce îi eliminăm două colţuri opuse.

Orice domino amplasat pe tablă va acoperi două pătrăţele de culori diferite, deci tabla trebuie să aibă un număr egal de pătrăţele colorate alb şi negru, fapt care nu se întâmplă în problema noastră. De aici deducem că nu putem acoperi tabla din care au fost eliminate două colţuri opuse. O problemă ce se poate aborda cu o tehnică asemănătoare este următoarea: „Se dă un dreptunghi de dimensiuni $7 x 10$. Din colţurile lui scoatem câte un pătrat de latură $1$. Să se arate că figura rămasă nu poate fi pardosită cu dreptunghiuri de laturi $3$ şi $1$.” Pentru probleme de acelaşi gen şi soluţia la această problemă puteţi să consultaţi în [1] secţiunea $1.1 Invariant$, sau în [2] secţiunea $Probleme de colorare şi acoperire$. Problema în care eliminăm două pătrate de aceiaşi culoare sau chiar cazul generalizat în care eliminăm un număr mai mare de pătrăţele o vom discuta în numărul viitor.

h2(#prob5). Problema 5

h2(#prob1ema5). Problema 5

bq. Determinaţi numărul de moduri în care poate fi acoperit un dreptunghi de dimensiuni $2 x N$ cu dominouri.

p=. !probleme-de-acoperire?P51.jpg!

h2(#prob6). Problema 6 ( _ONI 2001, clasa a X-a,_ [3] )

h2(#prob1ema6). Problema 6 ( _ONI 2001, clasa a X-a,_ [3] )

bq. Determinaţi numărul de moduri în care poate fi acoperit un dreptunghi de dimensiuni $3 x N$ cu dominouri.

Iar cum o matrice o putem ridica la o putere în număr logaritmic de paşi, putem afla <tex> X[n] </tex> mult mai repede.

h2(#prob7). Problema 7 ( _ACM ICPC 1997_ )

h2(#prob1ema7). Problema 7 ( _ACM ICPC 1997_ )

bq. Determinaţi numărul de moduri în care poate fi acoperit un dreptunghi de dimensiuni $N x M (N <= 20, M <= 20)$ cu dominouri.

* Pentru cazul general $M x N$, presupunem fără a reduce generalizarea că $N$ e multiplu de $3$. Pentru $M <= 5$ problema e deja rezolvată. Să vedem acum rezolvarea pentru $M > 5$: dacă $M$ e par atunci putem obţine uşor o soluţie folosind dreptunghiuri de dimensiune $2 x 3$, iar dacă $M$ e impar atunci obţinem întâi o soluţie pentru $(M – 2) x N$ la care adăugăm o bandă de dimensiune $2 x N$ formată din dreptunghiuri $2 x 3$.

h2(#prob9). Problema 9

h2(#prob1ema9). Problema 9

bq. Pentru un dreptunghi de dimensiuni $N x M$ să se determine o acoperire cu dominouri a lui astfel încât să nu existe vreo linie verticală sau orizontală care să taie dreptunghiul în două fără să intersecteze vreun domino.

p=. !probleme-de-acoperire?P93.jpg!

h2(#concl). Concluzii

h2(#concluzii). Concluzii

Acest articol a pus accentul mai mult asupra gândirii matematice în problemele de acoperire. În articolul următor încercăm o abordare orientată spre algoritmică.

h2(#biblio). Bibliografie

h2(#bibliografie). Bibliografie

* [1] Mircea Ganga, Teme şi probleme de matematică, ed.tehnică, Bucuresti, 1991
* [2] Valentin Vornicu, Olimpiada de matematică de la provocare la experienţa, ed. Gil, 2003