Note de curs, clasele 11-12, 28 septembrie 2012

From Algopedia
Jump to navigationJump to search

Prima întâlnire a decurs identic cu cea de la 9-10. Diferă doar răspunsurile de la chestionar, incluse aici.

Evident, au fost mult mai mulți care au rezolvat corect problemele, în special pe cele de programare.

algoritmul da nu altceva
Un algoritm de sortare în O(n2) 11 0 0
Un algoritm de sortare în O(n log n) 11 0 0
Descompunere în factori primi 11 0 0
Operații pe numere mari (adunare, scădere, înmulțire, împărțire) 11 0 0
Căutări în șiruri de caractere (KMP sau altceva eficient) 3 6 2
Generarea permutărilor, combinărilor, submulțimilor unei mulțimi 11 0 0
Parcurgere de graf (matrice de adiacență) 11 0 0
Parcurgere de graf (liste de adiacență) 9 1 1
Parcurgere de arbore (în adâncime) 10 1 0
Parcurgere de arbore (în lățime) 10 1 0
Arborele de cost minim (Kruskal, Prim sau alt algoritm) 7 4 0
Componentele tare conexe ale unui graf 3 8 0
Sortare topologică 8 3 0
Drumurile cele mai scurte de la un nod la toate celelalte 7 3 1
Drumurile cele mai scurte între oricare două noduri 7 3 1
Cuplaj într-un graf bipartit 3 8 0
Flux maxim 3 8 0
Flux maxim de cost minim 1 9 1
Programare dinamică (cel mai lung subșir crescător, distanța între două șiruri de caractere, problema rucsacului etc.) 9 2 0
Liste înlănțuite (cu pointeri) 8 3 0
Heaps 4 7 0
Tabele hash 2 9 0
Arbori de căutare 2 7 2
Structuri de mulțimi disjuncte (union-find) 4 7 0