Problema tăierii proporționale a prăjiturii

Problema de tăiere proporțională a prăjiturii este un fel de problemă de tăiere corectă a tortului . Aceasta este o împărțire a unei resurse eterogene („tort”) care îndeplinește criteriul de proporționalitate , și anume că orice participant consideră că porțiunea de tort care i-a fost alocată nu este mai proastă de 1/ n din evaluarea totală a prăjiturii.

Când se discută proporționalitatea , se fac de obicei două ipoteze:

Evaluările participanților nu sunt atomice , adică nu există elemente indivizibile cu o evaluare pozitivă.
Scorurile participanților sunt aditive , adică atunci când o piesă este împărțită, scorul piesei este egal cu suma părților sale.

Proceduri

Pentru două persoane, procedura Delhi-and-Choose este o soluție clasică. O persoană împarte resursa în două jumătăți, pe care le consideră egale, iar cealaltă persoană alege „jumătatea” care îi place cel mai mult. Ipoteza non-atomică garantează că tăietorul poate tăia (cum crede el) în două părți egale. Ipoteza de aditivitate garantează că estimările ambilor participanți vor fi de cel puțin 1/2 pentru piesele lor.

Există multe modalități de a extinde această procedură la mai mult de 2 persoane. Fiecare dintre aceste metode are propriile sale avantaje și dezavantaje.

Proceduri simple

Ultimul minus este cea mai veche procedură de împărțire proporțională dezvoltată pentru n persoane:

Unul dintre participanți este rugat să aleagă o piesă, pe care o evaluează la 1/ n .
Alți participanți, la rândul lor, au posibilitatea de a obiecta și de a declara că piesa este mai mare de 1/ n . În acest caz, i se cere să reducă piesa astfel încât, conform estimării sale, partea rămasă a piesei să fie 1/ n .
Ultimul participant care reduce piesa o primește.
Participanții rămași împart restul tortului în același mod între oamenii rămași. $n-1$

Prin inducție, se poate dovedi că fiecărui participant care respectă regulile i se garantează că va primi 1/ n din tort, indiferent de acțiunile celorlalți participanți. Aceasta este o procedură discretă care poate fi efectuată în runde. În cel mai rău caz, va fi necesară o acțiune - o acțiune pentru fiecare participant în fiecare rundă. Cu toate acestea, majoritatea acestor acțiuni se pot face pe hârtie. Doar inciziile sunt cu adevărat necesare. Prin urmare, dacă tortul este conectat, atunci se poate garanta că fiecare bucată va fi conectată. $n\times (n-1)/2=O(n^{2})$ $n-1$

Procedura „Moving Knife” Dubins - Spaniereste o versiune continuă a „Last Reducing” [1] .

Cuțitul se mișcă de-a lungul torusului în paralel de la un capăt la altul.
Concurentul spune „stop” atunci când consideră că valoarea din stânga cuțitului a fost atinsă . O bucată de tort este tăiată și dată participantului care a spus. ${\tfrac {1}{n)}$
Această procedură se repetă cu restul tortului și cu participanții rămași. Ultimul participant primește restul tortului.

Protocolul Fink este un algoritm care continuă să se împartă în bucăți „egale” suficient de mici.

Primul participant împarte resursa în bucăți pe care le consideră egale;
Al doilea participant alege jumătate, lăsând restul primului participant;
Fiecare dintre acești doi participanți își împarte porția în treimi;
Al treilea participant alege două dintre porțiunile rezultate - câte una dintre primul și al doilea participant;
Dacă sunt patru participanți, fiecare dintre primii trei participanți își împarte partea în sferturi și procesul continuă.

Avantajul acestui protocol este că se poate face online - atunci când intră în joc noi parteneri, divizia existentă este adaptată pentru aceasta fără a fi nevoie să pornească de la început întregul proces de divizare. Dezavantajul acestui algoritm este că fiecare participant primește un număr mare de bucăți deconectate, mai degrabă decât o bucată conectată.

Single divideing este o procedură bazată pe o împărțire egală, efectuată de un singur agent. Avantajul procedurii este că poate fi generalizată pentrutăierea corectă simetrică a prăjiturii.

Vezi și: [2] .

Bisectie recursiva

Folosind strategia împărțiți și cuceriți , diviziunea proporțională poate fi realizată în timp [3] . Pentru simplitate, procedura descrisă aici este dată pentru un număr par de participanți, dar poate fi adaptată cu ușurință oricărui număr de participanți: $O(n\log n)$

Fiecare participant este rugat să tragă o linie care împarte tortul în două bucăți pe care le consideră echivalente. Este necesar ca tăieturile să nu se intersecteze. Cel mai simplu mod de a garanta acest lucru este de a permite doar linii orizontale sau numai linii verticale.
Algoritmul sortează cele n linii în ordine crescătoare și taie tortul la mediana liniilor. De exemplu, dacă există 4 participanți care desenează linii în puncte și , algoritmul taie tortul vertical în punctul . $x=1,x=3,x=5$ $x=9$ $x=4$
Algoritmul atribuie fiecare dintre cele două jumătăți n /2 participanți - parteneri ale căror linii sunt în interiorul jumătății. De exemplu, membrii care au tras linii la puncte sunt alocați jumătății de vest, în timp ce membrii rămași sunt alocați jumătății de est. Fiecare jumătate este împărțită recursiv între cei n /2 participanți alocați acelei jumătăți. $x=1$ $x=3$

Se poate demonstra prin inducție că oricărui jucător care joacă după reguli i se garantează o piesă cu o valoare de cel puțin 1/ n , indiferent de modul în care se comportă ceilalți jucători.

Datorită strategiei de împărțire și cucerire, numărul de iterații va fi doar O(log n ), spre deosebire de valoarea O( n ) din procedura Ultima Descreștere. La fiecare iterație, fiecare participant este însărcinat să facă o notă. Prin urmare, numărul total de note va fi egal cu . $O(n\log n)$

Algoritmul are o versiune randomizată care poate fi folosită pentru a reduce numărul de căpușe. Vezi articolul „ Algoritmul Even-Paz ”.

Proceduri de selecție

O altă abordare a tăierii tortului este de a lăsa fiecărui participant să extragă un anumit număr de bucăți în funcție de numărul de participanți, p ( n ), și de a oferi fiecărui participant una dintre piesele alese astfel încât piesele să nu se suprapună.

Ca exemplu simplu de procedură de selecție, imaginați-vă un tort ca un segment unidimensional și fiecare participant dorește să obțină un segment separat conectat. Folosim următorul protocol:

Fiecare participant împarte în mod privat tortul în n intervale, pe care le consideră egale ca valoare, să numim aceste piese candidați .
Protocolul aranjează candidații în ordinea granițelor lor de est (de la vest la est) și selectează segmentul cu capătul estic cel mai vestic. Acest segment se numește piesa finală . $n^{2}$
Protocolul dă piesa de capăt proprietarului său și elimină toți candidații care se intersectează cu acesta. Pasul #2 se repetă apoi pentru segmentele rămase ale celorlalți participanți. $n-1$

Regula de selecție din pasul #2 asigură că la fiecare iterație, cel mult un segment al fiecărui participant este eliminat. Prin urmare, după fiecare iterație, numărul de segmente per participant rămâne egal cu numărul de participanți, iar procesul poate continua până când toți participanții primesc un segment [4] .

Acest protocol necesită ca fiecare parte să răspundă la n interogări, astfel încât complexitatea interogării este , similară cu procedura Ultima scădere. $O(n^{2})$

Versiuni randomizate

Puteți utiliza randomizarea pentru a reduce numărul de interogări. Ideea este că fiecare participant nu raportează întregul set de n candidați, ci doar un număr constant d de candidați aleși la întâmplare. Complexitatea interogării este O( n ), care va fi, evident, cea mai bună posibilă. În multe cazuri, rămâne posibil să se acorde fiecărui participant un singur candidat care să nu se suprapună cu alții. Cu toate acestea, există scenarii în care o astfel de distribuție nu este posibilă.

Putem tăia tortul cu interogări O( n ) dacă facem compromisuri:

În loc să garantăm proporționalitatea deplină, garantăm proporționalitatea parțială , adică fiecare participant primește o anumită fracțiune constantă f ( n ) din valoarea totală, unde . $f(n)<{\tfrac {1}{n)}$
În loc să transmitem fiecărui participant o piesă conectată separată, îi transmitem participantului unirea uneia sau mai multor piese care nu se intersectează.

Schema generală este următoarea [5] :

Fiecare participant împarte în mod privat tortul în bucăți egale , conform evaluării sale subiective. Aceste piese vor fi numite candidați . $n\cdot an$
Fiecare participant alege 2 d candidați în mod uniform la întâmplare, cu o retur. Candidații sunt grupați în d perechi, pe care participantul le raportează algoritmului. Aceste perechi vor fi numite seturi de sferturi de finală . $n\cdot d$
Din fiecare set sferturi de finală, algoritmul selectează o singură piesă, cea care intersectează cel mai mic număr de alți candidați. Aceste piese vor fi numite semifinale . $n\cdot d$
Pentru fiecare participant, algoritmul selectează o singură piesă, să o numim finală . Piesele finale sunt selectate astfel încât fiecare punct al tortului să fie acoperit de maximum două bucăți finale (vezi mai jos). Dacă aceasta reușește, mergeți la pasul numărul 5. Dacă nu reușește, reveniți la pasul numărul 1.
Fiecare bucată de tort care aparține unei singure piese finale este dată proprietarului piesei respective. Fiecare parte a tortului care aparține ultimelor două piese este împărțită proporțional de orice algoritm de diviziune proporțională deterministă.

Algoritmul garantează că, cu probabilitate, fiecare participant va primi cel puțin jumătate de la una dintre piesele sale candidate, ceea ce implică (dacă estimările sunt aditive) că estimarea nu va fi mai mică de 1/2 an . Există O( n ) bucăți candidate și O( n ) diviziuni suplimentare în pasul #5, fiecare luând timp O(1). Prin urmare, timpul total de rulare al algoritmului este O( n ). $O(1a^{2})$

Problema principală în această schemă este selecția pieselor finale în pasul 4. Consultați protocolul Edmonds-Prus pentru detalii .

Rezultate după dificultate

Rezultatele privind complexitatea sunt formulate în termenii „modelului standard Robertson-Webb”, adică se referă la proceduri care utilizează două tipuri de acțiuni: „Estimează” și „Tăiează”.

Orice procedură de diviziune proporțională deterministă pentru participanți trebuie să utilizeze cel puțin n acțiuni, chiar dacă toate funcțiile de punctare sunt identice [3] . $n\geqslant 3$

Mai mult, orice procedură de divizare proporțională deterministă sau randomizată (probabilistă) care atribuie fiecărui participant o piesă conectată trebuie să folosească acțiuni [6] . $\Omega (n\log n)$

Mai mult, orice procedură de diviziune proporțională deterministă trebuie să efectueze acțiuni, chiar dacă procedura este permisă să atribuie fiecărui participant o piesă care este unirea segmentelor și chiar dacă procedura este permisă să garanteze doar corectitudinea aproximativă . Dovada se bazează pe o limită inferioară a complexității de a găsi pentru jucătorii individuali o bucată de tort care este de mare valoare și subțire în lățime [7] [8] . $\Omega (n\log n)$

Din aceste rezultate de dificultate rezultă că bisectia recursivă este cel mai rapid algoritm pentru a obține proporționalitatea completă cu piesele conectate și este cel mai rapid algoritm determinist posibil pentru a obține proporționalitate parțială chiar și cu piesele deconectate. Singurul caz în care poate fi îmbunătățit este în algoritmi randomizati care garantează proporționalitate parțială cu piesele deconectate.

Dacă jucătorii sunt capabili să taie doar cu o precizie finită, atunci limita inferioară include și protocoale randomizate [7] [8] . $\Omega (n\log n)$

Următorul tabel conține rezultate cunoscute [5] :

Proporționalitate ( complet / parțial)	Piese (conectate/ deconectate)	Tip de protocol (determinist / randomizat )	Interogări (exact/ aproximativ)	Numărul de cereri
complet	mesageri	determinat	exacte	$O(n\log n)$ [3] [6] $\Omega (n\log n)$
complet	mesageri	determinat	aproximativ	$\Omega (n\log n)$ [6]
complet	mesageri	randomizat	exacte	$O(n\log n)$ [3] [6] $\Omega (n\log n)$
complet	mesageri	randomizat	aproximativ	$\Omega (n\log n)$ [6]
complet	incoerent	determinat	exacte	$O(n\log n)$ [3] [7] [8] $\Omega (n\log n)$
complet	incoerent	determinat	aproximativ	$\Omega (n\log n)$ [7] [8]
complet	incoerent	randomizat	exacte	$O(n\log n)$ [3]
complet	incoerent	randomizat	aproximativ	$\Omega (n\log n)$ [7] [8]
parțial	mesageri	determinat	exacte	$\Omega (n\log n)$ [3] [7] [8] $\Omega (n\log n)$
parțial	mesageri	determinat	aproximativ	$\Omega (n\log n)$ [7] [8]
parțial	mesageri	randomizat	exacte	$\Omega (n\log n)$ [3]
parțial	mesageri	randomizat	aproximativ	$\Omega (n\log n)$ [7] [8]
parțial	incoerent	determinat	exacte	$O(n\log n)$ [3] [7] [8] $\Omega (n\log n)$
parțial	incoerent	determinat	aproximativ	$\Omega (n\log n)$ [7] [8]
parțial	incoerent	randomizat	exacte	O( n ) [5]
parțial	incoerent	randomizat	slab aproximativ (independent de eroarea de estimare )	O( n ) [5]
parțial	incoerent	randomizat	aproximativ	$\Omega (n\log n)$ [7] [8]

Opțiuni

Diverse acțiuni scadente

Testul de proporționalitate poate fi generalizat la o situație în care cotele cuvenite ale participanților nu sunt egale. De exemplu, o resursă poate fi deținută de doi acționari, Alice deține acțiuni și George deține . Acest lucru conduce la un criteriu de proporționalitate ponderată (WPR) - există unele ponderi w i , a căror sumă este 1 și orice participant i trebuie să primească cel puțin o cotă w i din resursă conform propriei evaluări. Mai mulți algoritmi pot fi utilizați pentru a găsi diviziunea WPR. Principala problemă este că numărul de tăieturi poate fi mare chiar dacă sunt doar doi participanți. Vezi Tăiere proporțională a tortului cu diferite cote datorate . ${\tfrac {8}{13}}$ ${\tfrac {5}{13}}$

Diviziune superproporțională

O diviziune super-proporțională este o diviziune în care fiecare participant primește strict mai mult de 1/ n din resursă conform propriei evaluări subiective.

Desigur, o astfel de împărțire nu există întotdeauna - dacă toți participanții au exact aceleași funcții de evaluare, cel mai bine putem face este să oferim tuturor exact 1/ n . Astfel, o condiție necesară pentru existența unei împărțiri super-proporționale este cerința ca nu toți partenerii să aibă aceeași măsură de evaluare.

În mod surprinzător, dacă funcțiile de evaluare sunt aditive și nu atomice, această condiție este și ea suficientă. Adică, dacă există cel puțin doi participanți ale căror funcții de evaluare sunt doar puțin diferite, atunci există o diviziune super-proporțională în care toți participanții primesc mai mult de 1/ n . Consultați Divizia super proporțională pentru detalii.

Restricții de vecinătate

Pe lângă restricția obișnuită conform căreia toate piesele trebuie conectate, există restricții suplimentare în unele cazuri. În special, atunci când tortul care urmează să fie împărțit este un teritoriu disputat între mai multe țări, este posibil ca fiecare piesă dată unei țări să fie adiacentă graniței actuale a țării. Împărțirea proporțională în acest caz există întotdeauna și poate fi găsită prin combinarea protocolului Ultima scădere cu tehnici geometrice folosind mapări conforme . Vezi articolul „ The Hill-Beck Land Dividing Problem ”.

Constrângeri geometrice 2D

Când un „tort” este împărțit în spațiu bidimensional (un plan), cum ar fi atunci când se împarte loturi de teren sau spațiu publicitar în media tipărită sau electronică, este adesea necesar ca piesele să satisfacă unele constrângeri geometrice pe lângă conectivitate. De exemplu, poate fi necesar ca fiecare piesă să fie un pătrat, un dreptunghi gros (adică lungimea și lățimea nu diferă de câteva ori) sau o figură groasă de formă generală. În prezența unor astfel de restricții asupra cifrelor, împărțirea proporțională de obicei nu există, dar diviziunea parțial proporțională există de obicei și poate fi găsită folosind algoritmi eficienți [9] .

Diviziune eficientă din punct de vedere economic

Pe lângă proporționalitate, adesea se cere ca diviziunea să fie eficientă din punct de vedere economic , adică să maximizeze beneficiul total (definit ca suma utilităților tuturor agenților).

De exemplu, luați în considerare un tort care conține 500 de grame de ciocolată și 500 de grame de vanilie care este împărțit de doi participanți, dintre care unul dorește doar ciocolată, iar celălalt preferă vanilie. Multe protocoale de tăiere a prăjiturii vor oferi fiecărui agent 250 de grame de ciocolată și 250 de grame de vanilie. Această împărțire este proporțională, deoarece fiecare participant primește 0,5 din valoarea totală, deci beneficiul total normalizat este 1. Totuși, această împărțire va fi foarte ineficientă, deoarece putem da toată partea de ciocolată primului participant și toată partea de vanilie. celuilalt participant, obținând un beneficiu total normalizat 2.

Problema diviziunii proporționale optime este problema găsirii unei partiții proporționale care maximizează beneficiul total între toate distribuțiile proporționale posibile. În prezent, problema are soluție doar pentru prăjituri foarte speciale când este un segment unidimensional și funcțiile de densitate de utilitate sunt liniare (adică ). În general, problema este NP-hard . Dacă funcțiile de utilitate nu sunt normalizate (adică permitem fiecărui participant să aibă estimări diferite ale semnificației totale a tortului), problema este NP-grea chiar și pentru aproximarea cu un factor [10] . $u(x)=Ax+B$ ${\tfrac {1}{\sqrt {n}}}$

Târg împărțire

Corectitudinea nu este o proprietate a diviziunii, ci mai degrabă o proprietate a protocolului. Toate protocoalele de împărțire proporțională sunt slab corecte , în sensul că orice participant care acționează conform adevăratei sale valori este garantat să primească cel puțin 1/ n (sau 1/ an în cazul unui protocol parțial proporțional), indiferent de modul în care se comportă ceilalți participanți. Chiar dacă ceilalți membri formează o coaliție doar pentru a-i face rău, el va obține totuși proporția sa garantată [11] .

Cu toate acestea, majoritatea protocoalelor nu sunt strict corecte , în sensul că unii participanți pot avea stimulente să mintă pentru a obține chiar mai mult decât este garantat. Acest lucru este valabil chiar și pentru un protocol simplu de împărțire și alegere - dacă tăietorul cunoaște preferințele celui care aleg, el poate tăia o bucată pe care alegătorul o evaluează puțin sub 1/2, dar pe care tăietorul însuși o prețuiește mult peste. 1/2.

Există mecanisme corecte pentru obținerea unei partiții perfecte . Deoarece diviziunea perfectă este proporțională, aceste mecanisme sunt și mecanisme de divizare proporțională corectă.

Aceste mecanisme pot fi extinse pentru a obține o împărțire super-proporțională , dacă aceasta există [12] :

Solicităm fiecărui participant să furnizeze o măsură completă de evaluare.
Alegem o partiție aleatorie (a se vedea articolul de Mossel și Tamuz [12] pentru detalii).
Dacă partiția aleatoare se dovedește a fi superproporțională conform măsurilor raportate, o executăm. În caz contrar, folosim un mecanism corect pentru a asigura o împărțire perfectă.

Dacă există o diviziune superproporțională, există o șansă pozitivă ca aceasta să fie obținută în pasul 2. Prin urmare, valoarea așteptată pentru orice participant onest este strict mai mare decât 1/ n . Pentru a înțelege că mecanismul este corect, luați în considerare trei cazuri: (a) Dacă partiția aleasă este într-adevăr superproporțională, atunci singurul rezultat posibil al minciunii este de a păcăli mecanismul, făcându-l să creadă că partiția nu este superproporțională. Acest lucru va forța mecanismul să aplice o împărțire perfectă, ceea ce este mai rău pentru toți cei implicați, inclusiv pentru ticălos. (b) Dacă despărțirea aleasă nu este superproporțională doar pentru că mincinosul precizează 1/ n sau mai puțin, singurul efect al minciunii este de a face motorul să creadă că despărțirea este superproporțională și de a o folosi, ceea ce va răni doar mincinosul însuși. (c) Dacă împărțirea selectată nu este într-adevăr superproporțională, ceea ce dă celeilalte părți o valoare de 1/ n sau mai puțin, atunci false nu va avea niciun efect, deoarece împărțirea nu va fi folosită deloc.

Împărțirea proporțională a sarcinilor

Dacă resursa care urmează să fie partajată este nedorită (similar cu o împărțire a sarcinilor ), o împărțire proporțională este definită ca o diviziune care oferă fiecărei persoane nu mai mult de 1/ n din resursă (adică, semnul inegalității în cealaltă direcție).

Majoritatea algoritmilor de divizare proporțională pot fi adaptați pentru a împărți sarcinile fără dificultate.

Vezi și

Împărțirea exactă . Vezi și „Diviziunea perfectă”

Note

↑ Dubins și Spanier, 1961 , p. 1–17.
↑ Tasnadi, Attila. O nouă procedură proporțională pentru problema de tăiere a prăjiturii pentru n persoane . poarta de cercetare. Preluat: 24 septembrie 2015. (nedefinit)
↑ 1 2 3 4 5 6 7 8 9 Even, Paz, 1984 , p. 285.
↑ Această secțiune a procedurii este similară cu soluția polinomială greedy )
↑ 1 2 3 4 Edmonds, Pruhs, 2006 , p. 623–634.
↑ 1 2 3 4 5 Woeginger, 2007 , p. 213–220.
↑ 1 2 3 4 5 6 7 8 9 10 11 Edmonds, 2006 , p. 271–278.
↑ 1 2 3 4 5 6 7 8 9 10 11 Edmonds, 2011 , p. 1–12.
↑ Segal-Halevi, Nitzan, Hassidim, Aumann, 2017 , p. 1–28.
↑ Bei, Chen, Hua et al., 2012 .
↑ Steinhaus, 1948 , p. 101–4.
↑ 1 2 Mossel, Tamuz, 2010 , p. 288–299.

Literatură

O prezentare generală a diviziunilor proporționale și a altor diviziuni a apărut în articol:
Austin AK Sharing a Cake // The Mathematical Gazette. - 1982. - T. 66 , nr. 437 . — S. 212–215 . - doi : 10.2307/3616548 . — .
Lester Eli Dubins, Edwin Henry Spanier. Cum să tăiați o prăjitură în mod corect // The American Mathematical Monthly. - 1961. - T. 68 , nr. 1 . - doi : 10.2307/2311357 . — .
Chiar S., Paz A. O notă despre tăierea prăjiturii // Matematică aplicată discretă. - 1984. - T. 7 , nr. 3 . - doi : 10.1016/0166-218x(84)90005-2 .
Jeff Edmonds, Kirk Pruhs. Alocări echilibrate de tort // 2006 Cel de-al 47-lea Simpozion anual IEEE privind fundamentele informaticii (FOCS'06). - 2006. - ISBN 978-0-7695-2720-8 . - doi : 10.1109/focs.2006.17 .
Gerhard J. Woeginger. Despre complexitatea tăierii prăjiturii // Optimizare discretă. - 2007. - T. 4 , nr. 2 . - doi : 10.1016/j.disopt.2006.07.003 .
Jeff Edmonds. Tăierea prăjiturii chiar nu este o simplă simplă // Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithm - SODA '06. - 2006. - ISBN 978-0898716054 . doi : 10.1145 / 1109557.1109588 .
Jeff Edmonds. Tăierea prăjiturii nu este chiar o simplă // Tranzacții ACM pe algoritmi. - 2011. - T. 7 , nr. 4 . - doi : 10.1145/2000807.2000819 .
Erel Segal-Halevi, Shmuel Nitzan, Avinatan Hassidim, Yonatan Aumann. Târg și pătrat: Tăierea prăjiturii în două dimensiuni // Journal of Mathematical Economics. - 2017. - T. 70 . - doi : 10.1016/j.jmateco.2017.01.007 . - arXiv : 1409.4511 .
Xiaohui Bei, Ning Chen, Xia Hua, Biaoshuai Tao, Endong Yang. Tăiere proporțională optimă a tortului cu bucăți conectate // Proceedings Conference AAAI. — 2012.
Hugo Steinhaus. Problema împărțirii echitabile // Econometrica. - 1948. - T. 16 , nr. 1 . — .
Elchanan Mossel, Omer Tamuz. Divizia Târg Adevărat // . - 2010. - T. 6386. - (Note de curs în Informatică). - ISBN 978-3-642-16169-8 . - doi : 10.1007/978-3-642-16170-4_25 .