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 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

Structuri de date

Algoritmi si tehnici de programare

Matematica

Geometrie

computer graphics FAQ
cursuri dupa Computational Geometry: Algorithms and Applications, Mark de Berg, M. van Krefeld, M. Overmars, O. Schwarzkopf

Sortari si cautari

Greedy

Programare dinamica

Grafuri

  • Drumuri minime
    • Dijkstra (cu heapuri, cu set-uri, cu AINT-uri, cu coada ca pe TC - Cosmin stie)
    • Dijkstra cu costuri mici ;) cum se foloseste la problema car
    • 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
    • Bellman-Ford
      • De obicei mai simplu de implementat si cam aceeasi viteza ca si Dijkstra cu heapuri
      • Sistem de inegalitati
      • Ciclu de cost mediu minim
  • Flux
  • Arbori
  • APM
    • Prim
    • Kruskal
    • Al doilea APM
    • APM in graf orientat
    • Kirchhoff's matrix tree theorem
  • Pentru grafuri bipartite: cuplaj maxim, suport minim, multime independenta maxima
  • LCA, RMQ, Level Ancestor, Tree decompositions
  • Colorari de muchii, graf complet/bipartit/oarecare (teorema lui Vizing)
  • Grafuri planare
  • Grafuri turneu/ciclu hamiltonian
  • Implication graph si 2-SAT

Siruri de caractere

Limbaje formale si automate finite

Teoria jocurilor

Diverse

STL (Standard Template Library)

  • vector, deque, stack, list
  • string
  • set, map, hash_map
  • pair
  • sort
  • priority_queue
  • bitset
  • iteratori

Cautari

  • backtracking
  • iterative deepening
  • branch and bound

Optimizari

Lucrul cu memoria

Bulanit

  • Randomizare (2-opt, k-opt)
  • Constante
  • Interpolare Taylor / Gauss pentru formule polinomiale

Smenuri

Carti utile

  • Ioan Tomescu
    • "Probleme de combinatorica si teoria grafurilor" (din care s-a dat la ONI sau lot aproape in fiecare an cate o problema sau mai multe)
    • "Combinatorica si teoria grafurilor"
  • Ioan Cuculescu
    • "Olimpiadele Internationale de Matematica ale Elevilor"
  • E. A. Morozova, I. S. Petracov, V. A. Skvortov
    • "Olimpiade internationale de matematica"
  • "Probleme de matematica traduse din revista sovietica KVANT"
  • A. M. Iaglom, I. M. Iaglom
    • "Probleme neelementare tratate elementar"
  • Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest
  • D. E. Knuth
    • "Arta programarii calculatoarelor" ("The Art of Computer Programming")
    • "Concrete Mathematics"
  • Jon Bentley
    • "Programming Pearls"
  • Steven Skiena
    • "The Algorithm Design Manual"
  • M. Crochemore si W. Rytter
  • Mark de Berg
    • "Computational geometry"
  • Emanuela Cerchez si Marinel Serban
    • "Programarea in Limbajul C/C++ Pentru Liceu Volumul 1,2,3"