Herramientas de usuario

Herramientas del sitio


temarios-oia

¡Esta es una revisión vieja del documento!


Temarios relevantes para la OIA

Temario OIA Nivel 1 [Tentativo]

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 [No son relevantes los nombres ni la notación, sino las ideas]
    • Enunciados en primer orden (Diferencia entre existe y para todo)
    • Conectivos lógicos (propiedades básicas)
    • Modus ponens, modus tollens, y similares deducciones lógicas

Conocimientos de Ciencias de la Computación:

  • Programación
    • Sintaxis y semántica básicas de un lenguaje de alto nivel permitido
    • 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 y pasaje de parámetros
    • 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 subcadena)
    • Procesamiento y búsqueda secuencial

Temario OIA Nivel 2 [Tentativo]

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 [No son relevantes los nombres ni la notación, sino las ideas]
    • 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 [Tentativo]

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
  • Recursión
    • Estrategias de divide y vencerás
    • Backtracking recursivo
  • 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
    • Algoritmos sencillos con enteros:
      • 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

Temarios para la Olimpíada Internacional de Informática (IOI)

temarios-oia.1484334114.txt.gz · Última modificación: 2017/01/13 19:01 por santo