h1. Training path

h1. Training path....

Vrem sa intocmim o baza de cunostinte fara precendent! Vrem ca aceasta pagina sa contina o lista cat mai completa cu ce trebuie sa stie un olimpic pentru a avea succes. 'Ajuta-ne':implica-te/scrie-articole si tu!
*Cosmin:* ar trebui sa facem o lista mai mica cu chestiile importante ca sa ajungi la ONI, ca sa nu se sperie cei ce abia incep.

Alta lista 'http://www.scribd.com/doc/58361421/Programming-Camp-Syllabus':http://www.scribd.com/doc/58361421/Programming-Camp-Syllabus
 

h2. Structuri de date
* Liste, stive, cozi

* 'Skiplists':skiplists
* 'Arbori indexati binar':aib

** 'Aplicatie din Arhiva Educationala':problema/aib

* Cozi de prioritati
** 'Heap-uri':heapuri
** Mergeable heaps (maxophobic heaps sunt cel mai simple)

h3. Matematica

* Inductie matematica

* 'Inductie matematica':http://ro.wikipedia.org/wiki/Induc%C5%A3ie_matematic%C4%83

* 'Algoritmul lui Euclid':algoritmul-lui-euclid

* CMMDC binar

* 'CMMDC binar':http://en.wikipedia.org/wiki/Binary_GCD_algorithm

* 'Ciurul lui Erathostene':ciurul-lui-erathostene
* 'Gray code':coduri-gray
* Rezolvare de ecuatii liniare modulare

* Simplex
* "Floyd's cycle finding":http://en.wikipedia.org/wiki/Cycle_detection
* Combinatorica

** 'Generare de permutari':problema/permutari, permutari cu repetitii, aranjamente, 'combinari':problema/combinari, Stirling, Catalan, Bell, Fibonacci

** 'Generare de permutari':problema/permutari, permutari cu repetitii, aranjamente, 'combinari':problema/combinari, 'Stirling':problema/stirling, Catalan, Bell, Fibonacci

** Trecere de la combinare/permutare la indexul ei si invers
** 'Codul Prufer. Numarare de arbori':http://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence

* Intersectie a doua segmente
* 'Cele mai apropiate puncte dintr-un plan':problema/cmap

* Punct in interiorul unui poligosmenun

* Punct in interiorul unui poligon

** http://geometryalgorithms.com/Archive/algorithm_0103/algorithm_0103.htm
** http://tog.acm.org/editors/erich/ptinpoly/
* Punct in poligon convex in $O(log n)$

* 'Cel mai lung subsir comun':problema/cmlsc
* 'Distanta de editare a 2 cuvinte':http://en.wikipedia.org/wiki/Levenshtein_distance
* Ciclu hamiltonian in $O(n^2^ * 2^n^)$

** problema 'adn':problema/adn

** problema 'adn':problema/adn , 'aplicatie in arhiva educationala':problema/hamilton

* Dinamicile in $3^n^$
** 'explicatie':http://forums.topcoder.com/?module=Thread&threadID=512824&start=0, 'problema':http://www.topcoder.com/stat?c=problem_statement&pm=6678&rd=9998&rm=249548&cr=8547850

** 'scara2':problema/scara2
** 'colorare':problema/colorare
** 'zebughil':problema/zebughil
** 'ndap':problema/ndap
** 'cast':problema/cast
** 'carti2':problema/carti2

* 'Arbore de cautare optim in $O(n^2)$':http://www.ics.uci.edu/~dan/class/165/notes/OptBST.html
* Dinamici pe arbori
* 'Numarul posibilitatilor de acoperire a unei table cu dominouri':probleme-de-acoperire-2#problema3

** A* has a lot of intuitive appeal for me. If you compare Dijkstra's vs. A*, Dijkstra's is like a puddle of water flooding outwards on a flat floor, whereas A* is like the same puddle expanding on a bumpy and graded floor toward a drain (the target node) at the lowest point in the floor. Instead of spreading out evenly on all sides, the water seeks the path of least resistance, only trying new paths when something gets in its way. The heuristic function is what provides the 'grade' of the hypothetical floor.
*** A* se foloseste foarte mult in industria jocurilor, fiind un algoritm foarte rapid in practica. Un exemplu unde este folosit este jocul de strategie Starcraft.
** 'Floyd-Warshall':problema/royfloyd

** 'Bellman-Ford':en.wikipedia.org/wiki/Bellman-Ford_algorithm

** 'Bellman-Ford':problema/bellmanford

*** De obicei mai simplu de implementat si cam aceeasi viteza ca si Dijkstra cu heapuri
*** Sistem de inegalitati
*** 'Ciclu de cost mediu minim':ciclu-de-cost-mediu-minim

* 'KMP':automate-finite-si-kmp
* 'Siruri de sufixe':siruri-de-sufixe
** 'In timp liniar':suffix-array-liniar

* 'Z-Algorithm':zalgorithm

* 'Aho-Corasick':http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf .
h3. Limbaje formale si automate finite

* Echivalenta de automate
* 'thread pe forum':http://infoarena.ro/forum/index.php?topic=3005.0

h3. Teoria jocurilor

h3. 'Teoria jocurilor':teoria-jocurilor

* Nim

* 'Nim':teoria-jocurilor/jocul-nim

* 'Numere Sprague-Grundy':numerele-sprague-grundy
* Min-max
* Alpha-beta

** "Programming Pearls"
* Steven Skiena
** "The Algorithm Design Manual"

* W. Rytter
** "Jewels of Stringology"

* M. Crochemore si W. Rytter
** "Jewels of Stringology":http://www-igm.univ-mlv.fr/~mac/JOS/JOS.html

* Mark de Berg
** "Computational geometry"
* Emanuela Cerchez si Marinel Serban