Saturday, November 15, 2014

Cat de greu ar fi tehnic sa se verifice toate listele suplimentare impotriva votului multiplu?


In turul 1 al alegerilor prezidentiale statisticile arata cam asa:

Aproximativ 1 milion de persoane au votat pe liste suplimentare (963.987 conform Hotnews)

Nu am la indemana numarul total de alegatori insa conform aceleiasi surse cei 1 milion reprezinta 11% din totalul voturilor. Asta inseamna ca putem obtine cu un mic calcul numarul total al alegatorilor - de ordinul a 9 milioane (aproximativ).

Presupunand ca toate CNP urile de pe listele suplimentare ar fi incarcate intr-o baza de date impreuna cu CNP urile de pe listele permanante - baza aceasta de date ar contine o lista cu toti oamenii care si-au exprimat votul la niste alegeri date. Din lista ne intereseaza doar CNP urile care poti fi folosite pentru a identifica unic fiecare alegator (in termeni de baze de date CNP ul este "cheie primara"). Desi ar fi problematic nu cred ca ar fi imposibil sa se incarce toate aceste date intr-o baza de date, din cate am auzit cel putin in diaspora s-au scanat pe loc formularele de declaratie pe proprie raspundere necesare votului pe listele suplimentare si s-au incarcat intr-o baza de date a STS tocmai pentru evitarea votului multiplu. Scriu mai multe despre dificultatea incarcarii in baza de date spre sfarsitul articololui. Incarcarea nu trebuie facuta neaparat pe loc pentru discutia mea, scopul meu este identificarea celor care au votat de mai multe ori dupa terminarea alegerilor in vederea sanctionarii lor sau a celor responsabili conform legii. Prevenirea este o alta discutie - desi este foarte posibila tehnic aici vor fi argumente (valide) conform carora nu poti sa pui in toate sectiile de votare calculator cu acces la internet si oameni care sa stie sa il foloseasca. 

Dimensiunea problemei

Avem astfel o baza de date cu 9 milioane de CNP uri, putem presupune ca listele permanente nu contin dubluri de CNP uri (sper ca asta este situatia). Astfel din acesti 9 milioane de oameni, 1 milion adica cei de pe listele suplimentare trebuie cautati in toata baza de date de 9 milioane pentru a verifica faptul ca nu au mai votat nici pe listele suplimentare nici pe cele permanente. 

Practic pentru fiecare din cei 1 milion de oameni de pe listele suplimentare ar trebui sa facem 9 milioane de comparatii pentru a gasi dubluri de CNP uri adica (1 milion = 10^6 adica 10 la puterea a 6-a):

       10^6 x 9x10^6 = 9 x 10^12 comparatii

Sa zicem ca fiecare comparatie de 2 CNP uri ar insemna pentru un calculator cel mult 10 instructiuni masina executate (pe un sistem modern cu un algoritm bine facut ar trebui sa fie mai putine). Avem astfel de facut 

        9 x 10^13 instructiuni (sau operatii)



9x10^13 instructiuni este un numar mare - inseamna 9 zeci de mii de miliarde de instructiuni. 

Puterea de calcul
Pe de alta parte un calculator modern poate sa faca destul de multe instructiuni destul de rapid. Fara sa intru in discutii despre servere care pot fi semnificativ mai puternice am luat ca exemplu un ipotetic sistem de calcul modern cu 4 nuclee ruland la o frecventa de 3 GHz (3 pentru calcule mai simple, in realitate se gasesc sisteme care merg semnificativ mai rapid). 

Un astfel de sistem de calcul va efectua (avand in vedere ca 1 Giga Herz = 10^9 Herz) 
3 x  10^9 cicli de ceas intern (oscilatii sau Herzi) pe fiecare nucleu de calcul adica in total 4 x 3 x 10^9 = 1.2 x 10^10 cicli pe secunda.
Presupunand ca sistemul poate executa in medie 2 instructiuni pe ciclu inseamna ca sistemul nostru poate executa in fiecare secunda 

       2.4 x 10^10 instructiuni pe secunda

Avand in vedere dimensiunea problemei si puterea de calcul putem calcula cate secunde ar dura acest calcul pe sistemul nostru ipotetic 

( 9 x 10^13 ) / ( 2.4 x 10^10 ) = 3750 secunde

Adica putin peste o ora - nu e de loc mult de asteptat pentru verificarea functionarii corecte a democratiei intr-o tara. Desigur se pot cumpara servere cu zeci de nuclee de calcul care pot reduce acest timp la doar cateva minute. Am pus aici un caz destul de nefavorabil - am incercat sa subestimez puterea de calcul disponibila si sa supraestimez problema cand a venit vorba de presupuneri - si totusi am obtinut un numar fezabil. Verificarea poate fi facuta in mod fezabil practic pe orice calculator luat de pe rafturile unui magazin de oricine. Daca cineva are acces la aceasta baza de date, costul echipamentelor de calcul pentru efectuarea verificarii ar fi minim sau chiar zero daca este folosit calculatorul pe care il are deja. 


Insa metoda de calcul descrisa este ineficienta, problema mai poate fi simplificata. Putem de exemplu tine lista permananta de CNP uri sortata dupa CNP. In momentul in care vom avea de cautat 1 CNP de pe listele suplimentare in cele 8 milioane de CNP uri de pe listele permanente nu va mai trebui sa facem 8 milioane de verificari. Daca lista de 8 milioane de CNP uri este sortata putem folosi un algoritm de cautare binara: 
- cautam prima data la mijlocul listei sortate si comparam CNP ul cautat cu cel de acolo. 
- daca CNP ul cautat este mai mare decat ce am gasit am eliminat jumatatea de lista mai mica din cautare, daca este mai mic am eliminat jumatatea mai mare
- repetam acest pas pe jumatatea de lista ramasa
- ne oprim cand am gasit CNP ul cautat sau cand am eliminat prin aceasta metoda toate variantele
Mai multe detalii despre cautarea binara aici.
Asta ar reduce numarul de comparatii de facut pentru fiecare CNP de pe listele suplimentare de la 8 milioane la logaritm in baza 2 din 8 milioane adica aproximativ 20. Numarul total de operatii va fi redus de la 9 x 10^13 la 10^13 + 2 x 10^8 adica aproximativ cu un ordin de marime mai mic. Am considerat aici 9 x 10 ^13 = 10,000,000 x ( 1,000,000 + 8,000,000) iar cele 8,000,000 vor deveni 20 cu noul algoritm.  

Se poate insa si mai bine. Ce ne impiedica sa sortam toata lista de 9 milioane de CNP uri crescator? 
Folosind un algoritm bun de sortare de exemplu mergesort (descris aici in engleza) sortarea a 9 milioane de CNP uri ar necesita undeva de ordinul a 9 milioane x logaritm in baza 2 din 9 milioane comparatii. Folosind presupunerea de 10 instructiuni pe comparatie vom avea astfel 9,000,000 x 23 x 10 = aproximativ 2.1 x 10 ^9 instructiuni adica 2.1 miliarde de instructiuni. Mult mai putin decat cele cateva zeci de mii de miliarde calculate initial. 
Pentru un calculator modern 2 miliarde de instructiuni sunt o nimica toata, sistemul nostru ipotetic considerat mai sus am zis ca face 2.4 x 10^10 instructiuni pe secunda adica 24 de miliarde de instructiuni pe secunda. El ar putea termina acest calcul mai rapid decat am reusi noi sa ii dam comanda sa o faca. 

Odata sortata lista de CNP uri este suficienta o singura parcurgere a ei de la cap la coada. Daca cineva apare de mai multe ori in lista va fi gasit de mai multe ori consecutiv in lista sortata. Este deci necesar sa verificam pentru fiecare element din lista daca apare si pe pozitia imediat urmatoare si daca da pe cate din pozitiile urmatoare se afla. Presupunand ca majoritatea populatiei nu a votat de 2 sau mai multe ori vom avea de facut inca 9 milioane de comparatii adica 90 de milioane de instructiuni - numar mult mai mic decat cele necesare sortarii. Asta inseamna ca operatia poate fi facuta si ea foarte rapid.

Probabil ca se poate si mai bine, insa de la acest punct discutia devine pur filozofica. Ideea de baza este ca operatiunea de verificar este fezabila - daca ai acces la aceasta baza de date poti face calculele si pe telefonul mobil aproape instantaneu.  Orice ar spune autoritatiile despre dificultatea calculului este probabil vrajeala. 

Dar dificultatea probabil consta in centralizarea datelor intr-o baza de date. Avand in vedere ca fiecare declaratie pe proprie raspundere trebuie introdusa manual in baza de date probabil ar fi destul de greu sa fie introduse fara greseala umana 1 milion de CNP uri. Asta presupunand ca listele permanente sunt deja introduse si nici ele nu contin erori. Nu zic ca ar fi imposibil, cu putina organizare s-ar putea face in cateva zile in paralel cu numaratul voturilor insa ar fi greu. Si foarte probabil ar exista greseli umane. Totusi considerca in majoritatea cazurilor sistemul ar functiona si ar ajuta la identificarea majoritatii celor care au fraudat votul prin vot multiplu. Datele ar trebui in cazul ideal sa fie introduse direct in calculator la momentul votului pe listele suplimentare (eventual citite automat de pe buletin/pasaport ca sa eliminam eroarea umana din ecuatie). 

Si aici revenim la problema existentei unui calculator cu acces sigur la internet si personal calificat sa il foloseasca in fiecare sat din Romania. Daca nu am avea aceasta problema am putea introduce automat datele fiecarui votant in sistem in momentul votului folosind aceste sisteme. Nici nu ar mai fi nevoie de liste permanente si suplimentare, fiecare votant s-ar putea duce in principiu la orice sectie si ar fi inregistrat in baza de date in momentul votului. Sistemul l-ar cauta in lista de oameni cu drept de vot si apoi in lista de oameni care au votat deja si va semnala pe loc tentativa de vot multiplu. De asemenea fiecare votant ar putea verifica online pe loc daca s-a votat pe CNP ul lui si unde si ar putea raporta abuzurile.  

Pretul unui astfel de sistem ar fi insa destul de mare. In Romania sunt de ordinul a cateva zeci de mii de sectii de votare (estimez eu, sigur se stie numarul asta doar ca nu il am eu la indemana) iar pentru fiecare sectie de votare am putea estima ca ar costa in medie 20,000 euro dotarea cu suficiente calculatoare, legarea acestora la internet prin cablu unde se poate si prin reteaua de telefonie mobila sau satelit in rest si calificarea personalului in a le folosi. Asta inseamna 20,000 x cateva zeci de mii = cateva sute de milioane, poate peste 1 miliard. Sunt destul de multi bani mai ales pentru o tara ca Romania - democratia e scumpa. Probabil ca in practica ar fi de vreo 10 ori mai scump avand in vedere cum se sifoneaza banii in proiectele majore ale statului. Oare s-ar putea face pe fonduri euroene?  

No comments:

Post a Comment