Si quieres ser un programador competitivo muy serio, profundizaré un poco en los detalles de todas las matemáticas que puedas necesitar para una programación competitiva.
- Aritmética y Geometría: –
- Enteros, operaciones (incluida la exponenciación), comparación
- Propiedad básica de los enteros (signo, paridad, divisibilidad)
- Aritmética modular básica (suma, resta, multiplicación, división)
- Números primos (es un gran tema)
- Fracciones y porcentajes
- Línea, segmento de línea, ángulo, triángulo, rectángulo, cuadrado, círculo (y especialmente la forma de representarlos en su código)
- Punto, vector, coordenadas en un plano
- Polígono (vértice, lateral / borde, simple, convexo, interior, área)
- Distancias euclidianas
- Teorema de Pythogorean (Hay un uso bastante diverso de este teorema)
- En algunas preguntas, es posible que necesite el pequeño teorema de Fermat, el teorema del resto chino, o que necesite usar la función de Euler, etc. Debe mejorar la teoría de números. He encontrado algunos problemas en codechef que los necesito.
- Conocer algunas técnicas como el Algoritmo Euclidiano y la exponenciación rápida se considera un requisito previo en algunos concursos.
- Algunas técnicas de geometría computacional como Graham Scan y casco convexo.
- Estructuras discretas: –
- Funciones, relaciones y conjuntos
- Funciones (sobreyecciones, inyecciones, inversas, composición)
- Relaciones (reflexividad, simetría, transitividad, relaciones de equivalencia, relaciones de orden total / lineal, orden lexicográfico)
- Conjuntos (cardinalidad, inclusión / exclusión, complementos, productos cartesianos, conjuntos de potencia)
- Lógica básica
- Lógica de primer orden
- Conectivos lógicos (incluidas sus propiedades básicas)
- Tablas de verdad
- Cuantificación universal y existencial
- Modus ponens y Modus tollens (No se deje intimidar por los nombres: P)
- Técnicas de prueba (no las necesita demasiado rigurosamente)
- Conceptos básicos de contar
- Contar argumentos (suma y regla de producto, progresiones aritméticas y geométricas, números de Fibonacci)
- Permutaciones y combinaciones (definiciones básicas)
- Función factorial, coeficientes binomiales
- Principio de inclusión-exclusión
- Principio de casillero
- Identidad de Pascal, teorema binomial
- Resolviendo relaciones de recurrencia
- Lema de Burnside
- Gráficos y arboles
- Árboles y sus propiedades básicas, árboles enraizados
- Gráficos no dirigidos (grado, ruta, ciclo, conectividad, ruta / ciclo de Euler / Hamilton, lema de apretón de manos)
- Gráficos dirigidos (en grado, fuera de grado, ruta / ciclo dirigido, ruta / ciclo de Euler / Hamilton)
- Árboles de expansión
- Estrategias transversales
- Gráficos ‘decorados’ con etiquetas de borde / nodo, pesos, colores
- Multigrafos, gráficas con auto-bucles
- Gráficos bipartitos
- Gráficos planos
- Teoría de la probabilidad (Esto no está dentro del alcance del plan de estudios del IOI, por lo que no entraré en detalles. Dejaría un recurso aquí para su referencia aunque, porque soy un ángel 0 :-))
- Tutorial de Topcoder: Comprender las probabilidades
- Álgebra Lineal (incluyendo pero no limitado a)
- Multiplicación matricial, exponenciación, inversión y eliminación gaussiana
- Transformada rápida de Fourier
Aunque muchos de estos temas no se deben dominar rigurosamente, algunos son requisitos previos y los programadores competitivos deben tener el conocimiento básico de al menos la mayoría de ellos para estar entre los mejores programadores.
Espero que esto haya ayudado 😀
- ¿Cuál es el enfoque más fácil para abordar los problemas de programación dinámica?
- ¿Cómo es útil la matemática (integral, pecado, cos) en la programación?
- ¿Cuántos bits aleatorios se necesitan para generar un entero uniformemente aleatorio entre 0 y 9?
- Informática teórica: ¿cómo empiezo a resolver el problema P = NP?
- ¿Cuál es una explicación intuitiva del aprendizaje probablemente aproximadamente correcto (PAC)?
¡Feliz codificación!
Fuente: IOI syllabus 2015
