Ementa Modalidade Programação

Esta é a ementa (lista de conteúdos) oficial para a Modalidade Programação da Olimpíada Brasileira de Informática. Ela foi compilada por Arthur Pratti Dadalto com base no Syllabus da IOI, que também pode ser usado como referência. Para comentários, críticas ou sugestões entre em contato com a Coordenação da OBI (olimpinf@ic.unicamp.br ou corretor.obi@gmail.com).

A seguinte convenção é utilizada para definir os tópicos que podem ser cobrados na OBI em cada um de seus níveis:

[J] Tópico que pode ser cobrado a partir do Nível Júnior.
[N1] Tópico que pode ser cobrado a partir do Nível 1.
[N2] Tópico que pode ser cobrado a partir do Nível 2 (no Nível Sênior podem estar presentes os mesmos tópicos do Nível 2).
[S] Tópico que pode ser cobrado na Seletiva para a IOI.
  1. Conceitos básicos de Aritmética e Geometria
    1. [J] Inteiros, operações e comparações.
    2. [J] Propriedades básicas dos inteiros (sinal, paridade, divisibilidade, etc).
    3. [J] Frações.
    4. [J] Linha, segmento de linha, ângulo, triângulo, retângulo, quadrado, circunferência.
    5. [J] Distância Euclidiana. [5]
    6. [J] Teorema de Pitágoras.
    7. [J] Números primos.
    8. [N1] Ponto, vetor, coordenadas no plano.
    9. [N2] Aritimética modular básica: adição, subtração e multiplicação. [21] [30]
    10. [N2] Polígono (vértice, aresta, convexo, área).
    11. [N2] Operacões com matrizes (adição, multiplicação e exponenciação).
  2. Conceitos básicos de Matemática Discreta
    1. Conceitos de grafos e árvores
    2. [J] Arvóres e suas propriedades básicas, árvore enraizadas. [22] [23][38]
    3. [J] Grafos direcionados e não direcionados. [22] [23] [38]
    4. [J] Grau, caminho, ciclo, conectividade. [22] [23]
    5. [N1] Grafos com pesos, cores ou classificações nas arestas ou vértices. [22] [35]
    6. [N2] Operações simples em inteiros de tamanho arbitrário. [41]
    7. [N2] Algoritmos de força bruta e programção dinâmica com auxílio de máscaras de bits. [51] [52] [53]
    8. [N2] Exponenciação de matrizes para resolver problemas de programação dinâmica. [54]
    9. [S] Quickselect para achar o k-ésimo menor elemento. [55]
  3. Algoritmos em grafos
    1. [J] Percorrer grafos com busca em largura e busca em profundidade. [38] [37]
    2. [N1] Algoritmos de caminho mínimo (Dijkstra, Bellman-Ford, Floyd-Warshall). [46] [47]
    3. [N1] Encontrar componentes conexas.
    4. [N1] Ordenação topológica. [42] [43]
    5. [N1] Árvores geradoras mínimas. [48] [49]
    6. [N2] Encontrar um caminho/ciclo de Euler. [50]
    7. [S] Conjunto de arestas independentes em grafo bipartido (bipartite matching) em O(VE). [56]
  4. Estruturas de dados
    1. [J] Não é necessário, mas é muito útil conhecer a STL usando C++. [59]
    2. [J] Pilhas e filas. [60]
    3. [J] Listas ligadas. [61]
    4. [J] Representação de grafos.
    5. [J] Árvore de busca binária estática. [62]
    6. [N1] Heap binário. [63]
    7. [N1] Conjuntos disjuntos: Union-find. [64]
    8. [N1] Árvore de Fenwick (binary indexed tree) 1D. [65]
    9. [N1] Menor ancestral comum: algoritmo para responder perguntas em O(logN). [66]
    10. [N2] Árvore de Fenwick (binary indexed tree) 2D. [65]
    11. [N2] Árvore de segmentos (Segment tree). [67] [68] [69]
    12. [S] Estruturas de dados persistentes.
    13. [S] Divisão em buckets de tamanho N (square root decomposition). [1]
    14. [S] Árvores de busca binária balanceadas (Treaps, splay trees, etc). [70]
    15. [S] Árvore de segmentos 2D. [69]
    16. [S] Tries. [71]
  5. Geometria computacional
    1. [N1] Pontos, vetores, linhas e segmentos de linhas. [72]
    2. [N1] Pontos colineares, vetores paralelos e ortgonais. [72]
    3. [N1] Interseção de duas linhas. [72]
    4. [N2] Compressão de coordenadas. [73]
    5. [N2] Envoltória convexa (convex hull) em O(NlogN). [72]
    6. [N2] Line sweep. [4]
    7. [S] Calcular área de um polígono. [2] [72]
    8. [S] Checar se um polígono contém um ponto. [3] [72]
  6. Referências

    [1] http://www.infoarena.ro/blog/square-root-trick

    [2] https://en.wikipedia.org/wiki/Shoelace_formula

    [3] https://en.wikipedia.org/wiki/Point_in_polygon

    [4]https://www.topcoder.com/community/data-science/data-science-tutorials/line-sweep-algorithms/

    [5] https://pt.wikipedia.org/wiki/Distância_euclidiana

    [6] http://www.obmep.org.br/docs/apostila4.pdf

    [7] http://www.ime.usp.br/~pf/algoritmos/aulas/string.html

    [8] https://pt.wikipedia.org/wiki/Fun%C3%A7%C3%A3o_(matemática)

    [9] https://pt.wikipedia.org/wiki/Conjunto

    [10] https://pt.wikipedia.org/wiki/Defini%C3%A7%C3%A3o_recursiva

    [11] http://clubes.obmep.org.br/blog/texto_002-principio-das-casas-dos-pombos/

    [12]http://clubes.obmep.org.br/blog/texto_006-principio-fundamental-de-contagem/principio-fundamental-de-contagem-generalizacao/

    [13]http://vestibular.uol.com.br/ultnot/resumos/progressao-aritmetica-geometrica.jhtm

    [14] http://www.mat.uc.pt/~mat1131/Fibonacci.html

    [15] https://pt.wikipedia.org/wiki/Permuta%C3%A7%C3%A3o

    [16] https://pt.wikipedia.org/wiki/Combina%C3%A7%C3%A3o_(matemática)

    [17] http://www.infoescola.com/matematica/fatorial/

    [18] http://www.cin.ufpe.br/~gdcc/matdis/aulas/contagem.pdf

    [19]https://www.artofproblemsolving.com/wiki/index.php?title=Principle_of_Inclusion-Exclusion

    [20] http://www.cin.ufpe.br/~gdcc/matdis/aulas/binomial

    [21]https://pt.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-exponentiation

    [22] https://pt.wikipedia.org/wiki/Teoria_dos_grafos

    [23] http://www.ime.usp.br/~pf/teoriadosgrafos/texto/TeoriaDosGrafos.pdf

    [24] http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/guloso.html

    [25]http://www.decom.ufop.br/toffolo/site_media/uploads/2011-1/bcc402/slides/08._divisao_e_conquista.pdf

    [26] https://en.wikibooks.org/wiki/Algorithms/Backtracking

    [27]https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/

    [28] https://www.codechef.com/wiki/tutorial-dynamic-programming

    [29]https://www.quora.com/I-want-to-learn-memoization-What-are-some-links-with-problems-from-SPOJ-Topcoder-Codeforces

    [30]https://docs.google.com/presentation/d/1ABSFgyRu1I-yKyOxA6RyUqUxqmvxF7XaHySaGmUgSvc/edit?usp=sharing

    [31] https://pt.wikipedia.org/wiki/Algoritmo_de_Euclides

    [32] http://codeforces.com/blog/entry/15729

    [34] http://www.tutorialspoint.com/data_structures_algorithms/sorting_algorithms.htm

    [35] https://pt.wikipedia.org/wiki/Merge_sort

    [36] http://www.ime.usp.br/~pf/algoritmos/aulas/bubi.html

    [37]https://www.topcoder.com/community/data-science/data-science-tutorials/introduction-to-graphs-and-their-data-structures-section-2/

    [38]https://www.topcoder.com/community/data-science/data-science-tutorials/introduction-to-graphs-and-their-data-structures-section-1/

    [39] https://pt.wikipedia.org/wiki/Crivo_de_Erat%C3%B3stenes

    [40]https://www.topcoder.com/community/data-science/data-science-tutorials/algorithm-games/

    [41] https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic

    [42] https://pt.wikipedia.org/wiki/Ordena%C3%A7%C3%A3o_topol%C3%B3gica

    [43] http://www.geeksforgeeks.org/topological-sorting/

    [44] https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm

    [45] http://codeforces.com/blog/entry/16205

    [46]https://www.topcoder.com/community/data-science/data-science-tutorials/introduction-to-graphs-and-their-data-structures-section-3/

    [47] https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm

    [48] http://www.tutorialspoint.com/data_structures_algorithms/spanning_tree.htm

    [49] http://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/kruskal.html

    [50] https://en.wikipedia.org/wiki/Eulerian_path

    [51]https://www.topcoder.com/community/data-science/data-science-tutorials/a-bit-of-fun-fun-with-bits/

    [52] http://codeforces.com/blog/entry/18169

    [53] http://codeforces.com/blog/entry/337

    [54] http://fusharblog.com/solving-linear-recurrence-for-programming-contest/

    [55] http://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/

    [56]https://www.topcoder.com/community/data-science/data-science-tutorials/maximum-flow-section-2/

    [57] http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/

    [58] http://www.geeksforgeeks.org/bridge-in-a-graph/

    [59] https://community.topcoder.com/tc?module=Static&d1=features&d2=082803

    [60] http://www.facom.ufu.br/~madriana/EBD/Pilha.pdf

    [61] https://pt.wikipedia.org/wiki/Lista_ligada

    [62] http://www2.ic.uff.br/~boeres/slides_ed/ed8.pdf

    [63] https://en.wikipedia.org/wiki/Binary_heap

    [64]https://www.topcoder.com/community/data-science/data-science-tutorials/disjoint-set-data-structures/

    [65]https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/

    [66]https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/

    [67] http://codeforces.com/blog/entry/15729

    [68] http://codeforces.com/blog/entry/15890

    [69] http://e-maxx.ru/algo/segment_tree

    [70] https://en.wikipedia.org/wiki/Treap

    [71]https://www.topcoder.com/community/data-science/data-science-tutorials/using-tries/

    [72]https://www.topcoder.com/community/data-science/data-science-tutorials/geometry-concepts-basic-concepts/

    [73] https://www.quora.com/What-is-coordinate-compression

Volta ao início