Subiect dat la admitere la FMI in 2010

[•blue_phoenix]

Salut!

M-am uitat/ incercat sa rezolv subiectele care s-au dat anul trecut la facultatea de matematica si informatica, domeniul de licenta informatica.
Subiectele le gasiti aici http://fmi.unibuc.ro/ro/admitere_licenta/examen_admitere_iulie_2010/, la sectiunea "Subiecte si barem DL INFO". La problema de informatica, punctul a), nu-mi dau seama care e complexitatea.
Am luat numarul, l-am impartit pe rand, cat se poate, la 2, apoi la 3 si apoi la 5. daca rezultatul da 1, inseamna ca numarul apartine multimii H.
care ar fi complexitatea? eu nu stiu decat sa recunosc o coplexitate O(N),O(N^2),O(N^3)... sau O(log2 din n), chestii mai complexe nu prea....
As vrea sa stiu si ce e cu complexitatile, dar la un nivel nu prea ridicat (dar mai profund decat O(n)....) si cu nivel de cunostinte de matematica de liceu Stie cineva vreun astfel de material pe net?  eu dau admiterea la fmi anul acesta si n0as vrea sa pierd un punct si aici 

[•nparfene2004]

Uite aici un articol legat se sirul lui Hamming:

http://www.dponline.ro/articol.php?idarticol=82

Spor la studiu!

[•blue_phoenix]

Mersi muuuult! gasisem problema rezolvata undeva, dar nu stiam ca e chiar clasica (chiar nu stiam de la ce vine "H"-ul). Oricum, stiam si am inteles rezolvarea liniara pt generarea primelor n nr din H/a numerelor mai mici ca un nr dat. Ce nu stiu e care ar fi complexitatea pt punctul a (functia care verifica daca un nr dat apatine sau nu multimii H)

[•SpiderMan]

Well, complexitatea worst case la tine (e cea mai buna metoda) este de O(logN), deoarece poti face maxim logN impartiri, cand N este 2. (N = a in acel subiect). Sper ca ti-am fost de ajutor.
P.S. : Mai poti sa faci in O(sqrtN), factorizand numarul si verificand, dar nu este mai optim decat ce ai spus tu.

[•blue_phoenix]

Multumesc!
Ma gandisem ca primul while e ceva log in baza 2 din a, dupa aia a scade muuult (fiindca l-am tot impartit la 2); urmatorul while e log in baza 3 din noul a si tot asa... din cate am gasit pe internet, complexitatile sunt totusi doar ca sa arate ordinul de marime/tipul de algoritm...(in caz ca mai cauta cineva informatii simple legate de complexitate, eu le-am gasit aici http://www.excelenta.ro/Manuale/Informatica/Clasa%2011/1102%20Analiza%20complexitatii.pdf)

[•morlock]

E voie cu libraria Algorithm la admitere?

[•maritim]

Nu stiu cum va fi anul acesta dar anul trecut la admitere a interzis tot ce exista in STL, adica vectori, liste, set-uri, hash-uri.

[•MariusTitulescu]

Exista vreun site unde sa fie postate subiectele date in anii precedenti?
Multumesc anticipat!
__________________________________________
Marius
Vezi si Solutii Informatice