Temarios orientativos por nivel para la OIA, Categoría Programación

Aclaraciones

El temario se encuentra publicado en el sitio web de la OIA.
Los conocimientos que se listan, son orientativos para los alumnos, docentes, y entrenadores, y son no excluyentes de otros conocimientos que se podrían incorporar ocasionalmente en los problemas de los certámenes.
Estos conocimientos son acumulativos para los distintos niveles (Se considera que los temas de cada nivel incluyen los temas correspondientes a los niveles anteriores).
El temario está pensado como una orientación general de los temas que podrían aparecer en un problema, incluso en los más difíciles. Por lo tanto:
- No se espera que los participantes necesariamente conozcan y dominen todos los temas del temario.
- Se espera que los problemas más sencillos requieran únicamente de los conocimientos más básicos.

Temario OIA Nivel 1

Conocimientos Matemáticos

Aritmética y Geometría
- Enteros, operaciones aritméticas, comparación
- Sistemas de numeración, conversión entre ellos
- Propiedades básicas de los enteros (signo, paridad, divisibilidad)
- Aritmética modular básica: suma, resta, multiplicación
- Fracciones, porcentajes
- Números primos
Lógica básica
- Entender enunciados matemáticos con “existe” y “para todo”, y su diferencia
- Conectivos lógicos (y, o, no, entonces)
- Uso de razonamientos y deducciones lógicas

Conocimientos de Ciencias de la Computación:

Programación
- Sintaxis y semántica básicas de algún lenguaje permitido en OIA
- Variables, tipos, expresiones y asignación
- Entrada y salida sencilla (desde y hacia archivos y stdin / stdout)
- Estructuras de control selectivas (if)
- Estructuras de control repetitivas (while / for / repeat)
- Funciones (subrutinas) y pasaje de parámetros en ambos sentidos
- Descomposición de problemas (pensamiento top-down)
Estructuras de datos fundamentales
- Tipos primitivos (booleanos, enteros con y sin signo, caracteres)
- Arreglos unidimensionales
- Cadenas y procesamiento básico de cadenas
- Variables globales y locales
Estrategias algorítmicas
- Iteración
Algoritmos
- Algoritmos sencillos con enteros:
  - Cambio de base
  - Test de primalidad (buscar divisores hasta la raíz)
  - Factorización (buscando divisores)
- Manipulación de arreglos:
  - Llenar
  - Desplazar
  - Rotar
  - Invertir
  - Mínimo/Máximo
  - Sumas parciales
- Algoritmos sencillos con cadenas de texto
  - Búsqueda directa de una subcadena dada
  - Invertir una cadena
  - Convertir entre mayúsculas y minúsculas
- Procesamiento y búsqueda secuencial

Temario OIA Nivel 2

Conocimientos Matemáticos

Aritmética y Geometría
- Recta, segmento, ángulo, triángulo, rectángulo, cuadrado, circunferencia
- Teorema de pitágoras
Funciones, relaciones y conjuntos
- Funciones (inyectivas, sobreyectivas, inversas, composición)
- Relaciones (Propiedad de ser simétricas, transitivas)
- Orden lexicográfico
- Conjuntos (inclusión, complementos, disjuntos)
Lógica básica
- Tablas de verdad
Técnicas de demostración
- Nociones de implicación, recíproco, contrarrecíproco, negación, contradicción
- Demostraciones directas, por contraejemplo, por absurdo
- Inducción matemática
- Definiciones matemáticas recursivas
Combinatoria básica
- Argumentos de conteo (principio de suma y multiplicación, progresiones aritméticas y geométricas, números de Fibonacci)
- Factorial, números combinatorios
- Principio del palomar
Grafos y árboles
- Árboles y sus propiedades básicas, árboles con raíz
- Grafos no dirigidos (grados, camino, ciclo, conectividad)
- Grafos dirigidos (grado de entrada, grado de salida, camino y ciclo dirigido)
- Árboles generadores
- Grafos con pesos, etiquetas, colores
- Multigrafos, grafos con bucles

Conocimientos de Ciencias de la Computación

Estructuras de datos fundamentales
- Arreglos multidimensionales
- Registros / Tipos de Datos definidos por el usuario
- Estructuras enlazadas (listas, árboles binarios, árboles con raíz, y similares estructuras naturalmente recursivas)
- Estrategias de implementación de grafos y árboles
Recursión
- Implementación de funciones matemáticas recursivas
Análisis de algoritmos
- Complejidades estándar (constante, logarítmica, lineal, N lg N, cuadrática, cúbica, exponencial)
- Medición empírica de la eficiencia
Estrategias algorítmicas
- Algoritmos de fuerza bruta / búsqueda exhaustiva
- Algoritmos golosos
Algoritmos
- Algoritmos sencillos con enteros:
  - Algoritmo de Euclides
  - Criba de Eratóstenes
  - Factorización (con criba)
- Operaciones sencillas con enteros de precisión arbitraria (suma, resta, multiplicación cuadrática)
- Manipulación de arreglos:
  - Redimensionar
  - Histogramas
  - Bucket / counting sort
- Búsqueda binaria
- Quicksort y Quickselect (k-ésimo elemento)
- Heapsort y Mergesort
- DFS y BFS
- Recorrido Inorder, Preorder, Postorder
- Aplicaciones de DFS (Orden topológico)
- Componentes conexas
- Algoritmo de Dijkstra
- Árbol generador mínimo (Prim / Kruskal)
Estructuras de datos:
- Pilas y colas
- Representación de grafos (listas de adyacencia, matriz de adyacencia)
- Heap binario
- Estructura de Union-Find (Listas de componentes + Arreglo de representantes)

Temario OIA Nivel 3

Conocimientos Matemáticos

Aritmética y Geometría
- Punto, vector, coordenadas en el plano
- Polígono (vértices, lados, simple, convexo, interior, área)
- Distancia euclídea
Funciones, relaciones y conjuntos
- Relaciones (de equivalencia, de orden, de orden total)
- Conjuntos (producto cartesiano, conjunto de partes)
Combinatoria básica
- Principio de inclusión/exclusión
Grafos y árboles
- Grafos no dirigidos (ciclo y camino Euleriano / Hamiltoniano)
- Grafos dirigidos (camino y ciclo Euleriano / Hamiltoniano dirigido)
- Grafos bipartitos
- Grafos planares (propiedades básicas)

Conocimientos de Ciencias de la Computación

Estructuras de datos fundamentales
- Uso elemental de números de punto flotante en cómputos numéricamente estables
- Representación de datos en memoria
- Memoria Heap vs Stack
- Implementación de fracciones para cálculos exactos
Análisis de algoritmos
- Especificación, precondición, poscondición, correctitud, invariantes
- Análisis asintótico de complejidad
- Notación de O grande
Estrategias algorítmicas
- Divide y vencerás
- Backtracking (recursivo y no recursivo), Branch-and-bound
- Programación dinámica
Algoritmos
- Exponenciación eficiente (especialmente con aritmética modular)
- Aplicaciones de DFS (encontrar ciclo/camino euleriano)
- Clausura transitiva
- Algoritmos de Bellman Ford, Floyd-Warshall
- Matching máximo bipartito O(VE)
- Biconectividad en grafos no dirigidos (puentes, puntos de articulación)
- Conectividad en grafos dirigidos (componentes fuertemente conexas)
Estructuras de datos:
- Árboles binarios balanceados estáticos (Fenwick Tree o Segment Tree)
- Árbol binario de búsqueda balanceado (Treap | Splay Tree | AVL u otros)
- Árbol binario de búsqueda aumentado
- Consulta de LCA en tiempo logarítmico
- Estructuras de datos persistentes
- Composición de estructuras de datos (Fenwick Tree en 2 dimensiones)
- Tries
Algoritmos avanzados
- Nociones básicas de teoría de juegos combinatoria: posiciones perdedoras y ganadoras, minimax para juego óptimo
- Algoritmos Online vs Offline
- Algoritmos probabilísticos
Algoritmos geométricos
- Representación de puntos, vectores, rectas, segmentos
- Detección de puntos alineados, vectores paralelos / perpendiculares, giros horarios / antihorarios
- Intersección de dos rectas
- Intersección de dos segmentos
- Área de polígono
- Verificación de punto en polígono
- Compresión de coordenadas
- Algoritmos O(N lg N) para cápsula convexa
- Método de Sweep Line
Teoría de lenguajes
- Gramáticas sencillas en BNF