Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-01-22 21:15:17.
Revizia anterioară   Revizia următoare  

Training path

Algoritmi

  • Matematica
    • Algoritmul lui Euclid
      • binar
    • Ciurul lui Erathostene
    • Teorema mica a lui Fermat
    • Teorema chineza a resturilor
    • Rezolvare de ecuatii liniare modulare
    • Teorema lui Pick
    • Numere mari: adunare, scadere, inmultire, impartire, radical
    • Recurente si exponentiere rapida de matrici (+evaluare rapida a expresiilor folosind exponentiere in timp logaritmic)
    • Principiul includerii si al excluderii
    • Sisteme de ecuatii liniare (Gauss)
    • Simplex (pur si simplu un hill climbing pe mai multe variabile)
    • Combinatorica
      • Permutari, permutari cu repetitii, aranjamente, combinari, Stirling, Catalan, Bell, Fibonacci
      • Trecere de la combinare/permutare la indexul ei si invers
      • Numarare de arbori (codul Pruffer)
  • Geometrie
    • Intersectie a doua segmente
    • Punct in interiorul unui poligon
    • Punct in poligon convex in O(log n)
    • Aria unui poligon
    • Centrul de greutate al unui poligon
    • Triangularizare de poligon in O(n^2)
    • Intersectia a doua cercuri
    • Minimal enclosing circle
    • Convex hull
    • Baleiere verticala/radiala
    • Rotating calipers
    • Intersectie de poligoane convexe
    • Intersectie de semiplane (fara dualizare)
    • Dualizare (intersectie de semiplane, diagrame Voronoi)
  • Sortari si cautari
    • Shell sort, merge sort, heapsort, quicksort, counting sort, radix sort
    • Statistici de ordine
    • Cautare binara/ternara si aplicatii
  • Greedy
    • Huffman
    • Job scheduling
  • Programare dinamica
    • Parantezare optima de matrici
    • Cel mai lung subsir crescator O(N*log N)
    • Knapsack
      • Knapsack pe biti
    • Cel mai lung subsir comun
    • Distanta de editare
      • Cosmin: In O(n) memorie (cum am dat eu la ginfo), in O(d*n) timp unde d este distanta de editare finala (cum a dat Mars la ONI). Paper beton ce contine ambele si un jmen misto: http://www.xmailserver.org/diff2.pdf
    • Ciclu hamiltonian in O(n2 * 2n)
    • Dinamicile in 3n
    • Arbore de cautare optim in O(n^2)
    • Dinamici pe arbori
    • Numarul posibilitatilor de acoperire a unei table cu dominouri
    • Memoizare (trading space for time)
  • Limbaje formale si automate finite
    • Evaluari de expresii aritmetice
    • CYK
    • Matching with wildcards
    • Construirea unui automat care sa accepte un set de cuvinte
    • Simplificare de automate
    • Echivalenta de automate
  • Teoria jocurilor
    • Nim
    • Sprague-Grundy
    • Min-max
    • Alpha-beta

Structuri de date

  • Structuri arborescente
    • Arbori indexati binar
    • Heaps
    • Mergeable heaps
    • Structuri de multimi disjuncte
    • Arbori de intervale
    • Tries
    • Arbori binari de cautare (treaps, AVL, red-black trees)
    • Quad trees, kd-trees
  • Grafuri
    • Parcurgeri
      • dfs, bfs, meet in the middle bfs
      • Componente biconexe
      • Componente tare-conexe
      • Sortare topologica
      • Ciclu eulerian
    • Drumuri minime
      • A*, iterative deepening
      • Dijkstra (cu heapuri, cu set-uri, cu AINT-uri, cu coada ca pe TC - Cosmin stie)
      • Dijkstra cu costuri mici ;)
        • 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.
      • 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
      • Edmonds-Karp
      • Taietura minima
      • Dinic
      • Flux maxim de cost minim
      • Flux cu capacitati inferioare
      • Circulatii
      • Problema postasului chinez
    • Arbori
      • Diametrul, centrul unui arbore
      • Testare daca doi arbori sunt izomorfi
      • Cod Pruffer
    • APM
      • Prim
      • Kruskal
      • Al doilea APM
      • APM in graf orientat
    • Pentru grafuri bipartite: cuplaj maxim, suport minim, multime independenta maxima
    • LCA, RMQ, Level Ancestor, Path Decomposition
    • Colorari de muchii, graf complet/bipartit/oarecare (teorema lui Vizing)
    • Grafuri planare
    • Grafuri turneu/ciclu hamiltonian

Tehnici de programare (TODO: nume mai bun pentru subcategoria asta)

  • STL
    • vector, deque, stack, list
    • string
    • set, map, hash_map
    • pair
    • sort
    • priority_queue
    • bitset
    • iteratori
  • Optimizari
    • Parsare
    • Lucru cu biti
  • Brute force
  • Bulanit
    • Randomizare (2-opt, k-opt)
    • Constante

Harababura (TODO)

  • hill climbing
  • meet in the middle trick
  • 2SAT
  • jmenu lui batog (+ lca in sqrt(n))
  • jmenu lui mars
  • gray code
  • matrix tree theorem
  • Floyd's cycle finding
  • (colored range searching)
  • pt bulanit: interpolare taylor / gauss (scos din categoria mate)
  • ad hoc

Carti utile

  • Ioan Tomescu
    • "Combinatorica si teoria grafurilor"
  • Ioan Cuculescu
  • Morzova (TODO: carti)
  • "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")
  • "Programming Pearls" (TODO: autor)
  • "The Algorithm Design Manual" (TODO: autor)
  • "Concrete Mathematics" (TODO: autor)
  • "Jewels of Stringology" (TODO: autor)
  • "Computational geometry" (TODO: autor)