Note de curs, clasele 11-12, 28 septembrie 2012
From Algopedia
(Redirected from Note de curs 11-12 2012-09-28)
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 |
