h1. Arhiva educationala
h1. Arhiva educationala ==Stars(rating="5")==
Se propune construirea unei noi arhive de probleme care sa aiba exclusiv scop educational. Spre deosebire de probleme de concurs in care se imbina mai multi algoritmi si rezolvarea de obicei nu este evidenta, problemele din aceasta arhiva vor fi create special pentru cei care vor sa invete cum sa implementeze un algoritm sau o metoda de rezolvare anume. Se va permite accesul la teste, surse si se vor da si link-uri catre documentatie. Mai multe despre acest proiect gasiti 'aici':http://infoarena.ro/propuneri/6-arhiva-educationala.
Se propune construirea unei noi arhive de probleme care sa aiba exclusiv scop educational. Spre deosebire de probleme de concurs in care se imbina mai multi algoritmi si rezolvarea de obicei nu este evidenta, problemele din aceasta arhiva vor fi create special pentru cei care vor sa invete cum sa implementeze un algoritm sau o metoda de rezolvare anume. Se va permite accesul la teste, surse si se vor da si link-uri catre documentatie. Mai multe despre acest proiect gasiti 'aici':propuneri/6-arhiva-educationala.
Mai jos sunt trecuti utilizatorii care sunt implicati in dezvoltarea acestui proiect:
(toc)*{text-align:center} *Continut*
* 'Cum ne poti ajuta?':implica-te/arhiva-educationala#cum
* 'Echipa implicata in proiect':implica-te/arhiva-educationala#echipa
* 'Documentatie':implica-te/arhiva-educationala#documentatie
* 'Continutul arhivei':implica-te/arhiva-educationala#probleme
* == user(user="filipb" type="tiny") ==
* == user(user="PaulDB" type="tiny") ==
h2(#cum). Cum ne poti ajuta?
In tabelul de mai jos se afla cei mai importanti algoritmi care trebuie sa se gaseasca sub forma de probleme in arhiva educationala. Pentru fiecare problema este trecut si un responsabil. Responsabilul pe problema va fi cel care s-a oferit prin voluntariat sa o introduca in arhiva. El va fi cel care va scrie enuntul, va crea testele si eventual un evaluator.
table(example). |_. Denumire problema |_. Categorie|_. Responsabil |_. Stare|
|Cel mai lung subsir comun|Programare dinamica|== user(user="filipb" type="tiny") ==|==Stars(rating="0" scale="1" type="small")==|
|Knapsack|Programare dinamica|-|==Stars(rating="0" scale="1" type="small")==|
|Cautare binara|?|-|==Stars(rating="0" scale="1" type="small")==|
|Parcurgere BFS|Grafuri|-|==Stars(rating="0" scale="1" type="small")==|
|Parcurgere DFS - componente conexe|Grafuri|-|==Stars(rating="0" scale="1" type="small")==|
|Componente biconexe|Grafuri|-|==Stars(rating="0" scale="1" type="small")==|
|Componente tare-conexe|Grafuri|-|==Stars(rating="0" scale="1" type="small")==|
|Componente tare-conexe|Grafuri|-|==Stars(rating="0" scale="1" type="small")==|
|Sortare topologica|Grafuri|-|==Stars(rating="0" scale="1" type="small")==|
|Ciclu eulerian|Grafuri|-|==Stars(rating="0" scale="1" type="small")==|
|Algoritmul lui Prim|Grafuri|-|==Stars(rating="0" scale="1" type="small")==|
|Algoritmul lui Kruskal|Grafuri|-|==Stars(rating="0" scale="1" type="small")==|
|Algoritmul lui Djikstra|Grafuri|-|==Stars(rating="0" scale="1" type="small")==|
|Algoritmul Floyd-Warshall|Grafuri|-|==Stars(rating="0" scale="1" type="small")==|
|Algoritmul Bellman-Ford|Grafuri|-|==Stars(rating="0" scale="1" type="small")==|
|Flux maxim|Grafuri|-|==Stars(rating="0" scale="1" type="small")==|
|Flux maxim de cost minim|Grafuri|-|==Stars(rating="0" scale="1" type="small")==|
|Cuplaj maxim|Grafuri|-|==Stars(rating="0" scale="1" type="small")==|
|Cuplaj maxim de cost minim|Grafuri|-|==Stars(rating="0" scale="1" type="small")==|
|Lowest Common Ancestor|Grafuri|-|==Stars(rating="0" scale="1" type="small")==|
|Potrivirea sirurilor|Siruri de caractere|-|==Stars(rating="0" scale="1" type="small")==|
|Arbori de sufixe|Siruri de caractere|-|==Stars(rating="0" scale="1" type="small")==|
|Trie|Siruri de caractere|-|==Stars(rating="0" scale="1" type="small")==|
Mentionam faptul ca anumiti algoritmi pot fi implementati in complexitati diferite. De exemplu, pentru algoritmul de drumuri minime al lui Djikstra exista atat o solutie de complexitate {$O(N^2^)$}, cat si o solutie {$O(M log{~2~} N)$}. In acest caz, propunem sa nu se faca doua probleme diferite, ci sa se diferentieze punctajul in functie de rezolvare. Diferentierea pentru diferite abordari (complexitati) va fi precizata clar in enunt la rubrica de restrictii. De exemplu: "Un algoritm de complexitate {$O(N^2^)$} obtine $50$ de puncte", "Algoritmul Ford-Fulkerson obtine 30 de puncte. Pentru punctaj maxim este necesara implementarea algoritmului lui Dinic.".
1. Ofera sugestii la dezvoltarea proiectului.
2. Contribuie cu feedback pentru a imbunatati calitatea problemelor existente.
3. Vino cu idei pentru probleme noi.
Ajuta si tu la randul tau comunitatea infoarena!
h2(#echipa). Echipa implicata in proiect
Echipa care este implicata activ in acest proiect este alcatuita din urmatorii membri:
* == user(user="Marius" type="tiny") ==, coordonator de proiect
* == user(user="savim" type="tiny") ==
* == user(user="cezarmocan" type="tiny") ==
* == user(user="GavrilaVlad" type="tiny") ==
* == user(user="mishu91" type="tiny") ==
* == user(user="GheorgheMihai" type="tiny") ==
Pe langa cei de mai sus, de-a lungul timpului au contribuit considerabil la acest proiect 'o serie de alti membri ai comunitatii infoarena':implica-te/arhiva-educationala/membri-emeritus. Le multumim pe aceasta cale!
h2(#documentatie). Documentatie
Fiecare voluntar are obligatia sa citeasca urmatoarele materiale inainte de a putea trece efectiv la lucru:
* 'Editare de probleme':documentatie/editare-de-probleme
* 'Ghid evaluator':documentatie/ghid-evaluator
* 'Ghid pentru arhiva educationala':documentatie/arhiva-educationala
h2(#probleme). Continutul arhivei
In tabelul de mai jos se afla probleme la care se lucreaza in momentul de fata. Finalizarea lor reprezinta unul dintre $OKR$-urile din trimestrul IV, 2009. Pentru a va familiariza si cu restul obiectivelor din acest trimestru, cititi 'aici':okr.
table(example). |_. Denumire problema|_. Voluntar|_. Finalizat|_. Review |
| 'Arbori de intervale (aplicaţie cu 4 tipuri de operaţii)':problema/arbint2 | == user(user="savim" type="tiny") == | ==Stars(rating="1" scale="1" type="small")== | ==Stars(rating="0" scale="1" type="small")== |
| 'Arbori de intervale 2D':problema/arbint2d | == user(user="savim" type="tiny") == | ==Stars(rating="0" scale="1" type="small")== | ==Stars(rating="0" scale="1" type="small")== |
| 'NIM':problema/nim | == user(user="GavrilaVlad" type="tiny") == | ==Stars(rating="1" scale="1" type="small")== | ==Stars(rating="0" scale="1" type="small")== |
| 'Punct în poligon oarecare':problema/pinpo | == user(user="cezarmocan" type="tiny") == | ==Stars(rating="0.5" scale="1" type="small")== | ==Stars(rating="0" scale="1" type="small")== |
| 'Treapuri':problema/treapuri | == user(user="marius" type="tiny") == | ==Stars(rating="0.5" scale="1" type="small")== | ==Stars(rating="0" scale="1" type="small")== |
| 'Interclasarea a doi vectori sortati':problema/interclas | == user(user="pauldb" type="tiny") == | ==Stars(rating="0.5" scale="1" type="small")== | ==Stars(rating="0" scale="1" type="small")== |
| 'Aria unui poligon':problema/ariapoli | == user(user="pauldb" type="tiny") == | ==Stars(rating="0.5" scale="1" type="small")== | ==Stars(rating="0" scale="1" type="small")== |
| 'Arbori de căutare':problema/arbcautare | ==user(user="bogdan2412" type="tiny") == | ==Stars(rating="0.5" scale="1" type="small")== | ==Stars(rating="0" scale="1" type="small")== |
In tabelul de mai jos se afla sugestii privind algoritmii care trebuie sa se gaseasca sub forma de probleme in arhiva educationala. Puteti veni oricand cu propuneri si sugestii de probleme noi pe "forum":/forum/index.php?topic=3401.0.
table(example). |_. Denumire problema|_. Categoria|
|Knapsack|Programare dinamica|
|Sprague-Grundy|Teoria jocurilor|
|Algoritmul lui Gauss|Matematica|
| Principiul lui Dirichlet | Matematică |
|Problema de acoperire|Programare dinamica + Backtracking|
|Heavy Path Decomposition|Algoritmi pe grafuri|
|Siruri de sufixe|Siruri de caractere|
|Algoritmi {$O(sqrtN)$}|Structuri de date|
|Ortogonal Range Search|Structuri de date|
|Intersectia a doua drepte|Geometrie|
|Punct in poligon convex|Geometrie|
|Minimum enclosing circle|Geometrie|
|Sortare prin numarare|Diverse|
|RadixSort|Diverse|
|Operatii pe numere mari|Diverse|
h2. Discutii pe forum
==SmfTopics(board_id="61")==
