Contenido del examen NOI

1 Complejidad del tiempo (definición estricta de complejidad del tiempo asintótica, problema NP, método de análisis de la complejidad del tiempo, teorema principal)

2 Algoritmo de clasificación (aplicación del algoritmo de clasificación cuadrada, clasificación de capa, clasificación rápida, clasificación de subconsumo, inferior límites de complejidad temporal, tres clasificaciones lineales del tiempo, clasificación externa)

3 Teoría de números (divisibilidad, teoría de conjuntos, relaciones, números primos. Series, división euclidiana, división euclidiana extendida, congruencia, etc. Operaciones, resolución ecuaciones lineales congruentes, teorema del resto chino)

4 punteros (lista vinculada, criterios de búsqueda, lista de adyacencia, hash abierto, representación de árbol binario, representación de múltiples árboles)

5 operaciones de posición ( suma, o, xor, shl, shr, algunas aplicaciones)

6 Teoría de grafos (modelado gráfico, diagrama plano, fórmula de Euler y teorema de los cinco colores, búsqueda de componentes fuertemente conectados, búsqueda de puntos de corte Puente de suma, Euler ciclo, problema AOV, problema AOE, tres algoritmos para árbol de expansión mínimo, tres algoritmos para camino más corto, método de notación, sistema de restricción diferencial, verificación de gráfico bipartito, teorema de Koenig, algoritmo húngaro, algoritmo KM, sistema de matrimonio estable, algoritmo de flujo máximo, teorema de corte mínimo-flujo máximo, algoritmo de flujo máximo de costo mínimo)

7 Geometría computacional (solucionador de planos y sus aplicaciones, vectores, productos escalares y sus aplicaciones, productos cruzados y sus aplicaciones, intersección de semiplanos, búsqueda envolvente convexa de conjunto de puntos, problema de par de puntos más cercano, intersección de polígonos convexos, discretización y escaneo)

8 Estructuras de datos (búsqueda en amplitud, coincidencia de soportes de verificación, expresiones Cálculo de fórmulas, compilación recursiva, tabla hash, montón binario, árbol sesgado a la izquierda, montón sesgado, montón binomial, árbol de búsqueda binaria, AVL, Treap, Splay, árbol de búsqueda binario estático, árbol bidimensional, árbol de segmento de línea, árbol de segmento de línea bidimensional, árbol rectangular, árbol Trie , lista enlazada de bloques)

9 Matemáticas combinatorias (permutaciones y combinaciones, principio de casillero, principio de tolerancia y repulsión, recursividad, series de Fibonacci, series catalanas, números de Stirling, series en diferencias, funciones generadoras, permutación, principio de Polya)

10 Teoría de la probabilidad (probabilidad simple, probabilidad condicional, teorema de Bayes, valor esperado)

11 Matriz (concepto y operación de matriz, solución de ecuaciones recursivas lineales binarias, número de esquemas de cobertura de dominó , eliminación gaussiana)

12 Procesamiento de cadenas (KMP, árbol de sufijos, autómata de estados finitos, codificación Huffman, criptografía simple)

13 Programación dinámica (colas monótonas, convexa completa monotonicidad, reglas de movimiento de árboles, polinomios a bifurcaciones, clases de compresión de estados de reglas de movimiento, desigualdades cuadráticas)

14 Teoría de juegos (resta de Nim) Juego, árbol de juegos, juego de intercambio de Shannon)

15 Búsqueda (A*, ID, IDA*, ajuste aleatorio, algoritmo genético)

16 Cálculo preliminar (ideas límite, derivadas, Integrales, integrales definidas, geometría analítica sólida)