Diferente pentru problema-majoritatii-votului intre reviziile #29 si #32

Nu exista diferente intre titluri.

Diferente intre continut:

(Categoria _Algoritmi_, Autor _Cosmin Negruşeri_)
(toc){width: 20em}*{text-align:center} *Conţinut:*
* 'Enunţ':problema-majoritatii-votului#enunt
** 'Soluţie $O(n^2^)$':problema-majoritatii-votului#solutie-1
** 'Soluţie $O(n + k)$ particulară':problema-majoritatii-votului#solutie-2
** 'Soluţie $O(n)$ cu tabele de dispersie':problema-majoritatii-votului#solutie-3
** 'Soluţie $O(n log{~2~}n)$':problema-majoritatii-votului#solutie-4
** 'Soluţie $O(n)$ cu statistici de ordine':problema-majoritatii-votului#solutie-5
** 'Soluţie $O(n log{~b~} k)$ particulară':problema-majoritatii-votului#solutie-6
** 'Soluţie $O(n + k)$ probabilistică':problema-majoritatii-votului#solutie-7
** 'Soluţie $O(n)$':problema-majoritatii-votului#solutie-8
* 'Generalizare':problema-majoritatii-votului#generalizare
** 'Soluţii $O(n*k)$':problema-majoritatii-votului#solutie-9
* 'Bibliografie':problema-majoritatii-votului#bibliografie
 
În acest articol dezbatem problema dezvoltării de algoritmi eficienţi pentru determinarea candidatului care a întrunit un număr majoritar de voturi.
h2. Enunţ
h2(#enunt). Enunţ
bq. Se dă un şir de $n$ numere naturale. Se cere determinarea unui element care apare de cel puţin $[n/2]+1$ ori în şir dacă există un astfel de element în şir.
h3. Soluţie O(n^2^)
h3(#solutie-1). Soluţie O(n^2^)
Un algoritm naiv ar verifica pentru fiecare element din şir de câte ori mai apare acesta. O astfel de rezolvare are complexitatea $O(n^2^)$ ca timp şi $O(n)$ ca memorie.
== code(cpp) |
}
==
h3. Soluţie O(n + k) particulară
h3(#solutie-2). Soluţie O(n + k) particulară
Dacă numerele din şir aparţin unei mulţimi ${1, 2, ... k}$ iar acest $k$ este mic comparativ cu $n$, atunci putem să îmbunătăţim ideea de mai devreme şi să folosim un şir auxiliar $b$, unde $b[x]$ va număra de câte ori apare un număr $x$ în şirul nostru. Această soluţie are complexitate $O(n + k)$ ca timp şi $O(n + k)$ ca spaţiu.
}
==
h3. Soluţie O(n) cu 'tabele de dispersie':tabele-hash-prezentare-detaliata
h3(#solutie-3). Soluţie O(n) cu 'tabele de dispersie':tabele-hash-prezentare-detaliata
Soluţia precedentă este destul de eficientă în cazul menţionat anterior, dar când $k$ este mult mai mare decât $n$, atunci această rezolvare ajunge să fie foarte lentă. Însă folosind o structură avansată de date putem să facem soluţia din nou eficientă. Această structură are la bază o tabelă de dispersie: ea mapează perechi de numere $<cheie, valoare>$, unde cheile vor fi numerele din şir, iar valorile vor fi numărul de apariţii al cheilor în şirul nostru.
Această soluţie are complexitate $O(n)$ ca timp, şi $O(n)$ memorie suplimentară. Menţionăm că un dezavantaj al acestei soluţii ar fi că este una randomizată.
h3. Soluţie O(n log{~2~}n)
h3(#solutie-4). Soluţie O(n log{~2~}n)
O altă soluţie care ar permite numărarea eficientă a numărului de apariţii al unui element în acest şir ar fi să sortăm şirul pentru că apoi elementele egale vor fi în poziţii consecutive.
Această soluţie are complexitatea O(n log n), nu foloseşte memorie suplimentară, dar suprascrie şirul iniţial.
h3. Soluţie O(n) cu 'statistici de ordine':problema/sdo
h3(#solutie-5). Soluţie O(n) cu 'statistici de ordine':problema/sdo
O idee ce ne vine pe urma acestei rezolvări este aceea că în şirul sortat, un element majoritar se va afla în şirul sortat şi pe poziţia $n/2$. Ştim că există algoritmi de selecţie care ne găsesc elemente de o poziţie fixată $k$ din şirul sortat în complexitate $O(n)$. Astfel, vom găsi întâi elementul de pe poziţia $n/2$ iar apoi vom verifica dacă acesta este elementul majoritar al şirului. Astfel avem o soluţie de complexitate $O(n)$ iar şirul iniţial va fi modificat. Există metode de selecţie nerandomizate, dar pentru uşurinţa implementării vom folosi una randomizată.
}
==
h3. Soluţie O(n log{~b~} k)
h3(#solutie-6). Soluţie O(n log{~b~} k) particulară
O altă idee de rezolvare porneşte de la observaţia următoare: dacă există un element majoritar în şir, atunci ultima lui cifră va fi elementul majoritar în şirul format din ultimele cifre a numerelor din şirul iniţial. Această observaţie este valabilă pentru orice cifră a numerelor nu doar ultima. Astfel putem determina pentru fiecare a $x$-a cifră a numerelor care este cifra majoritară şi apoi să punem cap la cap cifrele majoritare pentru a forma numărul majoritar. Evident putem să folosim orice bază, dacă folosim baza $b$ şi valoarea maximă a unui număr ar fi $k$ atunci algoritmul va avea complexitatea $O(n log{~b~} k)$ şi foloseşte memorie suplimentară $O(b * log{~b~}k)$.  În practică putem considera acest algoritm ca fiind liniar. Să vedem o implementare a algoritmului pentru $b = 1000$ şi $k = 999 999 999$.
}
==
h3. Soluţie O(n + k) probabilistică
h3(#solutie-7). Soluţie O(n + k) probabilistică
Putem aborda probabilistic. Astfel dacă alegem un număr aleator şi există o celebritate, avem probabilitatea $0.5$ să nu îl nimerim. Dacă alegem $k$ numere aleatoare din şirul respectiv, atunci avem probabilitatea <tex> (\frac{1}{2})^k </tex> să nu îl nimerim. Astfel algoritmul nostru va fi să luăm $k$ numere aleatoare, iar apoi să numărăm de câte ori apare fiecare din aceste $k$ numere în şirul nostru. Dacă folosim o structură ce mapează $<chei, valori>$ atunci algoritmul va avea complexitate $O(n + k)$ şi probabilitate de reuşită <tex> P = 1 - (\frac{1}{2})^k </tex>. În practică o valoare de $10$ pentru $k$ ne dă o probabilitate de reuşită de $0.999$. Să vedem mai departe codul:
}
==
h3. Soluţie O(n)
h3(#solutie-8). Soluţie O(n)
Un ultim algoritm şi cel mai eficient dintre cele prezentate apare în lucrarea [1] şi probabil acesta este cunoscut cititorilor. Autorii au un mod plastic de a prezenta algoritmul:
Această problemă a fost propusă în prima rundă a concursului Bursele Agora în 2005. Atunci nu era posibilă ţinerea tuturor numerelor din fişier în memorie şi citirea numerelor era greoaie. Doar doi concurenţi au reuşit obţinerea unui punctaj maxim la acea rundă. Autorul a fost unul dintre aceştia. El a evitat citirea de două ori a fişierului de intrare prin folosirea soluţiei cu cifre, în care calcula două rezultate pentru două baze diferite b1 şi b2 alese aleator la startul rulării, iar apoi verifica dacă candidaţii care erau probabil câştigatori erau egali. Aceasta rezolvare făcea improbabilă scrierea unui răspuns incorect.
h2. Generalizare
h2(#generalizare). Generalizare
bq. Se dă un şir de $n$ numere naturale şi un număr întreg $k$, se cere determinarea tuturor elementelor care apar de cel puţin $[n/k]+1$ ori în şir.
h3. Soluţii O(n*k)
h3(#solutie-9). Soluţii O(n*k)
Primele trei rezolvări prezentate pentru problema iniţială pot fi evident generalizate şi folosite şi pentru această problemă. Generalizarea abordării care implica folosirea cifrelor pentru a rezolva noua problemă pare imposibilă. Vom vorbi mai departe de două din celelalte trei abordări.
}
==
h2. Bibliografie
h2(#bibliografie). Bibliografie
# T.H.Cormen, C. E. Leiserson, R. R. Rivest, Introducere în algoritmi, ed. Agora 2000
# R. S. Boyer, J. S. Moore A Fast Majority Vote Algorithm
# T.H.Cormen, C. E. Leiserson, R. R. Rivest, _Introducere în algoritmi_, ed. Agora 2000
# R. S. Boyer, J. S. Moore, _A Fast Majority Vote Algorithm_
!probleme-majoritatii-votului?IA_bug_in_FF2.jpg!

Nu exista diferente intre securitate.

Diferente intre topic forum:

4381
4383