Roteiro de skills por currículo

Referência para alinhar o catálogo de skills com disciplinas (ACM CS1–CS3 e trilha WOK: PC1, AED I/II, técnicas). Os slug em inglês refletem a padronização recomendada; até sincronizar o JSON com o banco, alguns nomes no cache podem diferir.

← Voltar para Skills

Papel na catalogação: use conceitos (skill_nature = concept) para tópicos “ensináveis” e instrumentos (instrument) para algoritmos concretos ou padrões de exercício. Temas de enunciado ficam em context (temático).

Básicas — núcleo mínimo do tópico (obrigatório para concluir o nível). Desejadas — cobertura padrão da disciplina / bons exercícios de consolidação. Avançadas (Extra) — aprofundamento, competição ou extensões opcionais.

Quadro 1 — Referência ACM (CS1, CS2, CS3)

Visão clássica por nível; útil para comparar com bibliografia internacional e com o courses.json (acm_level).

CS1 — Introdução à programação

Variáveis, fluxo, estruturas básicas, vetores/strings, funções introdutórias, matrizes.

Básicas

  • Raiz basic-programming
  • variables, input-output, selection / condicionais
  • while-loop, for-loop
  • arrays (acesso e percurso simples)

Desejadas

  • expressoes-precedencia-operadores (ou equivalente de expressões)
  • do-while, nested-loops
  • strings, characters
  • functions — definição, function-parameters, scope-lifetime
  • vetor-varredura-busca-linear
  • matrices

Avançadas (Extra)

  • recursion (introdução leve, sem exigir provas)
  • foreach / iteradores (se a linguagem do curso usar)
  • file-handling / E/S em arquivo (opcional por ementa)

CS2 — Estruturas e algoritmos básicos

Complexidade, recursão, ordenação, busca, estruturas lineares e hash.

Básicas

  • Notação assintótica / complexity (onde existir)
  • recursion (exemplos clássicos)
  • sorting — bubble-sort, selection-sort, insertion-sort
  • binary-search
  • stacks, queues, dynamic-array

Desejadas

  • mergesort, quicksort
  • lista (listas encadeadas simples / duplas)
  • hashing — mapa / conjunto, colisões (conceito)

Avançadas (Extra)

  • counting-sort, radix-sort, bucket-sort
  • deque / filas especiais (se no catálogo)
  • Heurísticas de two-pointers-array em vetor ordenado

CS3 — Estruturas avançadas e grafos

Árvores de busca, heaps, strings avançadas, grafos e fluxo.

Básicas

  • nonlinear-structures — trees, binary-tree-traversals, bst-operations
  • grafos — representação, BFS, DFS
  • topological-sort (intro)
  • minimum-spanning-tree + union-find-dsu

Desejadas

  • tree-rotations-avl / balanceamento (conforme ementa)
  • priority-queue-heap
  • Caminhos mínimos — Dijkstra / Bellman-Ford / Floyd-Warshall (o que a disciplina cobrir)
  • SCC, fluxo básico (ford-fulkerson ou equivalente no catálogo)
  • Ramo paradigms — greedy-algorithms, dynamic-programming (modelos introdutórios)

Avançadas (Extra)

  • trie-suffix, huffman-coding, lzw-compression
  • segment-tree, fenwick-tree, lazy / persistente
  • centroid-decomposition, emparelhamento / coloração (se existir)
  • PD em árvore / bitmask / digit-dp como extensão de dynamic-programming

Quadro 2 — Trilha WOK (courses.json)

Alinhamento aos cursos Programação de Computadores, AED I, AED II e Técnicas Avançadas.

PC1 — Programação básica

Até matrizes inclusive (curso cs1). Sem AED linear nem grafos.

Básicas

  • basic-programming — variables, input-output, selection, loops (while, for)
  • arrays

Desejadas

  • strings, characters, functions + function-parameters
  • nested-loops, do-while
  • matrices (teto do PC1)

Avançadas (Extra)

  • expressoes-precedencia-operadores, io-formatacao-parsing
  • recursion leve; scope-lifetime
  • simulation-ad-hoc em problemas introdutórios

AED I — Estruturas lineares

Complexidade, recursão, ordenação, busca binária, vetor dinâmico, listas, pilhas, filas.

Básicas

  • Complexidade / complexity
  • recursion
  • sorting — bubble-sort, selection-sort, insertion-sort
  • binary-search
  • stacks, queues, dynamic-array

Desejadas

  • mergesort, quicksort
  • lista (simples / dupla)
  • Transição para hashing (últimas semanas, conforme courses.json)

Avançadas (Extra)

  • counting-sort, radix-sort, bucket-sort
  • prefix-sum-difference-array, two-pointers-array
  • dp-space-optimization em modelos muito simples (opcional)

AED II — Não linear

Hash, árvores, heaps, texto, grafos e estruturas avançadas.

Básicas

  • hashing / mapas
  • trees, binary-tree-traversals, bst-operations
  • grafos — representação, BFS, DFS
  • counting-sort, radix-sort, bucket-sort (bloco ordenação linear)

Desejadas

  • tree-rotations-avl / rubro-negra (se na ementa)
  • priority-queue-heap, huffman-coding
  • trie-suffix, lzw-compression
  • topological-sort, SCC, minimum-spanning-tree, caminhos mínimos, fluxo
  • union-find-dsu

Avançadas (Extra)

  • segment-tree, fenwick-tree, segment-tree-lazy, persistente
  • centroid-decomposition, tree-euler-tour, tree-lca
  • dp-on-tree combinado com estruturas

Técnicas de programação

Paradigmas e modelos para maratona / aprofundamento (curso tecnicas).

Básicas

  • paradigms — greedy-algorithms, divide-and-conquer
  • dynamic-programming — dp-states-transitions, dp-memoization, dp-tabulation
  • Modelos: knapsack-01, coin-change, longest-increasing-subsequence (base)

Desejadas

  • dp-on-grid, dp-on-intervals, longest-common-subsequence, edit-distance
  • dp-on-tree, dp-solution-reconstruction
  • meet-in-the-middle, simulation-ad-hoc, bitmask-subsets, dp-bitmask
  • mathematical-induction; ramo mathematics — prime-numbers, gcd-euclides, combinatória
  • Reforço grafos (BFS/DFS, caminhos, MST) conforme semanas

Avançadas (Extra)

  • digit-dp, matrix-chain-multiplication, subset-sum-partition
  • dp-dag-path, fluxo em redes, estruturas do AED II em problemas mistos
  • Extensões de teoria dos números e geometria computacional (geometry) conforme catálogo

Resumo cruzado

Tópico PC1 AED I AED II Técnicas
Variáveis / E/S / seleção / laços●○ reforço——
Arrays, strings, funções, matrizes●○——
Complexidade + recursão○●○●
Ordenação + busca binária—●○ linear●
Listas, pilhas, filas, vetor dinâmico—●○○
Hash—○●○
Árvores / heaps / texto——●●
Grafos——●●
Gulosa, D&C, PD, ad hoc—○○●

● = núcleo do curso; ○ = reforço ou transição; — = fora do escopo principal. O detalhe por slug (Básicas / Desejadas / Avançadas) está nos cartões dos quadros 1 e 2 acima.