¿Cuáles son algunos temas imprescindibles en matemática discreta y probabilidad de programación competitiva?

Inducción matemática Este principio es simple. Mire las fichas de dominó que caen aquíhttp: //en.wikipedia.org/wiki/Mathematical_induction. El paso inductivo es importante. Si alguna afirmación es verdadera para el número N implica que es cierta para N + 1, se deduce que la declaración es verdadera para cada número.

Prueba por inducción
¿Parece simple? ¿Listo para algunos ejercicios avanzados? Página en math.uoc.gr

Principio del agujero de paloma
¿Cuál es la relación entre Hashtables, Pigeonholes y Cumpleaños?
Hashtables, casilleros y cumpleaños
El principio del agujero de paloma parece muy simple: si intentas poner 6 palomas en 5 agujeros, inevitablemente quedarás fuera.
Pero sus aplicaciones son variadas. Por ejemplo, este problema de cumpleaños y también en la búsqueda de colisiones en tablas hash
En un aula típica de 30 estudiantes, ¿cuáles son las probabilidades de que dos de ellos tengan el mismo cumpleaños?
Teoría de grafos
Teoría de grafos | Mathigon
Página en alaska.edu

Originado por el método de Euler para determinar si cruzar 7 puentes exactamente una vez posible. Tiene maravillosas aplicaciones.
Busque aquí una lista de aplicaciones de la teoría de grafos Teoría de grafos

Vea la página en eprints.nuim.ie para ver pruebas tan hermosas, incluidas las de Gauss
Matemáticas para la informática

El profesor Leighton en el MIT (fundador de Akamai) explica los conceptos básicos de las matemáticas: inducción, teoría de números, aritmética modular
Página en princeton.edu
Los ejemplos son interesantes. Por ejemplo, uno es de una película: Bruce recibe una jarra de 3 galones y una de 6 galones y debe
Mida exactamente 4 galones. También explican cómo se utilizan los principios de la teoría de números para proteger sus datos, es decir, los fundamentos de la criptografía RSA. Ofrecen ejemplos agradables y prácticos en los que se utilizan gráficos para modelar

Estructuras de datos Cada vértice representa un objeto de datos. Hay un borde dirigido de uno
oponerse a otro si el primero contiene un puntero o referencia al segundo.
Atracción Cada vértice representa a una persona, y cada borde representa una atracción romántica.
El gráfico podría estar dirigido a modelar las desafortunadas asimetrías.
Conexiones de líneas aéreas Cada vértice representa un aeropuerto. Si hay un vuelo directo entre
dos aeropuertos, entonces hay un borde entre los vértices correspondientes. Estas
los gráficos a menudo aparecen en revistas de aerolíneas.
TheWeb Cada vértice representa una página web. Los bordes dirigidos entre vértices representan
hipervínculos

Permutaciones y Combinación

Permutaciones y combinaciones fáciles

Ejemplo: formas de organizar los colores

Matemáticas para el análisis de algoritmos
El análisis de algoritmos es explicado por Peteris
Introducción del MIT a Algoritmos, Conferencias 1 y 2: Análisis de Algoritmos
Apunta a la conferencia de Erik Demaine. La segunda mitad de la conferencia está dedicada a resolver ecuaciones de recurrencia. Se presentan tres métodos:
Método de sustitución,
Método de árbol de recursión, y
El método maestro.
Matemáticas para programadores
¿Cuántas matemáticas debe saber un programador? ¿Cuál es la forma correcta de aprender matemáticas? Steve Yegge escribe aquí
Matemáticas para programadores
Conocer incluso un poco de los tipos correctos de matemáticas puede permitirle escribir algunos programas bastante interesantes que de lo contrario serían demasiado difíciles. Nadie sabe todas las matemáticas, ni siquiera los mejores matemáticos.
Álgebra lineal
Página en uoregon.edu
Página en psu.edu
video conferencias
Descargar video conferencias de matemática discreta
Videos de la Academia Khan sobre Probabilidad / Álgebra Lineal
Probabilidad explicada
Página en khanacademy.org

Más información sobre Hyperbook – organizador de información

“Los temas que debes conocer pueden depender del nivel de problemas que estés abordando. Si estás en cosas bastante avanzadas, entonces la lista de requisitos cambia un poco.

Para la mayor parte del concurso, es posible que necesite conocimientos sobre los siguientes temas sin ningún orden en particular:

• Aritmética básica del módulo
• Exponenciación binaria para [matemáticas] a ^ b \; \ equiv \; mod \; n [/ matemáticas]
• Tamiz de Eratóstenes y Tamiz extendido o segmentado de Eratóstenes
• Fibonacci y otras relaciones de recurrencia como los números catalanes
• Aritmética larga (aritmética en números largos arbitrarios)
• Teorema del resto chino, módulo inverso
• Congruencias combinatorias como [matemáticas] N! \; \ equiv \; mod P [/ math] y el teorema de Wilson
• Máximo común divisor, MCM de n números
• GCD extendido y ecuaciones lineales de diofantina
• Función Euler Phi
• Factorización en log (N) y pruebas de primalidad, métodos probabilísticos y deterministas.
• Teoría de la probabilidad, variables aleatorias y expectativas y propiedades.
• Álgebra matricial y propiedades.

Algunos temas avanzados:

• Transformadas rápidas de Fourier
• Graham scan para casco convexo
• Algoritmo de Bentley Ottmann para enumerar todos los puntos de intersección de n segmentos de línea en O ((n + I) * logn
• Algoritmos de barrido de línea / barrido de plano
• Triangulación de Delaunay de n puntos en O (n * logn)
• Área de unión del círculo
• Diagramas de Voronoi de n puntos en O (n * logn) usando el algoritmo Fortunes
• Punto en un polígono
• Función Mobius, símbolos Legendre
• Fórmula V de Euler – E + F = 2
• Teorema de Pick

La segunda lista contiene principalmente geometría computacional y teoría de números avanzados. Recursos que puede usar para leer sobre ellos:

• Matemáticas para Topcoders
• MAXimal :: algo
• Proyecto euler

A2A.

No estoy mencionando algoritmos específicos que usan conceptos matemáticos, solo algunos conceptos que generalmente se requieren.

1. Módulo aritmético (incluido el teorema del resto chino, el pequeño teorema de fermat, las ecuaciones de diofantina, etc.).
2. Contar (incluido el teorema de Lucas y los números catalanes, los números de Bell, etc.).
3. Transformada rápida de Fourier
4. Tamiz de eratóstenes, función totler euler
5. Fórmula de inversión de Mobius y sus requisitos previos.
6. Álgebra matricial (especialmente eliminación de gauss-jordania)
7. Geometría Euclidiana (principalmente lo básico)
8. Geometría coordinada (especialmente las diversas formas de ecuaciones para línea, círculo, plano y esfera).
9. Trigonometría (especialmente las diferentes fórmulas para área y para inradius, circumradius, etc.)
10. Teoría de la probabilidad y teoremas sobre variables aleatorias.

Gracias por A2A.

Bueno. Lo primero que hay que tener en cuenta aquí es que lo que sea que voy a decirte no será una lista exhaustiva, porque se crean tantas preguntas cada día, que no puedes cubrirlas todas.

Por lo tanto, mantener ese hecho a un lado tener conocimiento previo de algunos temas matemáticos siempre es una ventaja para la programación competitiva.

Temas como permutación y combinaciones, suma de diferentes tipos de series, geometría básica se usan con mucha frecuencia en las preguntas.
También debe tener conocimiento sobre los números primos y sus propiedades, mcd, mcm y hcf y sus propiedades.

Estos son solo pequeños temas que generalmente no se hacen directamente en las preguntas, pero de alguna manera se utilizan para optimizar las soluciones.

La mejor manera en que me siento al aprender las matemáticas requeridas para la programación no es a través de todos estos temas y aprendiendo todas sus propiedades, porque hacerlo es directamente inútil, sino implementarlos durante las preguntas. Por lo tanto, le recomiendo que deje de preocuparse por las matemáticas y comience a practicar y cada vez que encuentre una pregunta en la que encuentre algunas matemáticas involucradas, búsquelas en Google, aprenda sobre ellas, impleméntelas y luego nunca las vuelva a olvidar. Obviamente, esta forma será un poco más lenta, pero terminarás con resultados mucho mejores.

Algunos recursos que pueden ayudarlo,

Acerca de – Proyecto Euler (Preguntas relacionadas con las matemáticas)
HackerRank (Busque el concurso llamado Proyecto Euler y resuelva estos problemas diariamente)
La preparación de la entrevista de codificación es fácil (hay muchos subdominios que involucran preguntas de matemáticas, practíquelas)

Espero eso ayude.
Si tiene más consultas, puede enviarme un ping o preguntarme en los comentarios.

DORMIR. COMER. CÓDIGO. REPETIR.

Las matemáticas discretas son un tema amplio, pero aquí hay algunas cosas esenciales que debes saber para poder resolver problemas de concurso de programación:

Conteo: verá muchos problemas como “Cuenta el número de formas de hacer X”. En la mayoría de los casos, enumerar todas las formas posibles simplemente no va a funcionar, y se espera que utilice algún tipo de programación dinámica. Para poder resolver los problemas de conteo correctamente, debe tener una buena comprensión de ciertos temas, tales como:

• Relaciones de recurrencia: ubicuas en el conteo de problemas. En particular, aprenda a encontrar recurrencias para contar. Además, aprenda a convertir las recurrencias de alta complejidad en menor complejidad
• Exponenciación de la matriz: en el caso de recurrencias que tienen coeficientes constantes, es posible expresar el vector de estado final como el producto de la potencia de una matriz y el vector de estado inicial. Un buen ejemplo es calcular números de Fibonacci usando la multiplicación de matrices. Este truco ayuda a reducir la complejidad de encontrar el enésimo término de algunas recurrencias de O (N) a O (Log N)
• Coeficiente binomial: muchos problemas de conteo con simetrías se pueden reducir a encontrar algunos casos y multiplicarlos con algunos coeficientes binomiales. Entonces, aprenda a calcularlos de manera eficiente según el tipo de problema. Hay diferentes tipos de cálculos previos que uno hace. Además, trate de aprender las propiedades de los coeficientes binomiales módulos primos.
• Principio de casillero: más de una técnica de ayuda de prueba en lugar de algo que se aplica directamente. Pero he usado esto en casos donde se me pidió que encontrara dos casos que compartan alguna propiedad. El ataque de cumpleaños puede considerarse como la variante probabilística del principio del casillero, pero no es tan común.
• Principio de inclusión-exclusión: Cómo formalizar el tratamiento de la doble contabilidad. A veces es mucho más fácil contar dos veces al principio y usar la inclusión-exclusión más tarde que intentar contar dos veces para evitar la recurrencia
• Subconjuntos y permutaciones: aprenda a generar subconjuntos de un conjunto y permutaciones de una secuencia. Existen algunos problemas de conteo en los que se espera que sume cantidades sobre permutaciones o subconjuntos. DP sobre subconjuntos es algo que también debe aprender a este respecto.
• Objetos indistinguibles y distinguibles: aprenda la diferencia y sepa cómo contar los cambios entre los dos casos.
• Problemas de celosía: contar el número de formas de ir entre dos puntos en una red con varios tipos de restricciones es un problema muy común. Aprenda el método básico y cómo aparecen en las soluciones cosas como los coeficientes binomiales y los números catalanes.
• Contando con gráficos: las preguntas de este tipo que he visto comúnmente incluyen DP de árbol. Los problemas de conteo en gráficos que no son de árbol suelen ser difíciles. Ves problemas surgiendo según el teorema de Kirchhoff de vez en cuando también.
• Teorema de enumeración de Pólya: He visto esto surgir en concursos solo un par de veces. Pero aprenda esto y si surge algo, debería ser fácil para usted.
• Aprenda a trabajar con módulos: la mayoría de las veces, se le pide que haga el mod de conteo con un gran número primo (el más favorito es 10 ^ 9 +7). Aprenda a hacer los cálculos sin desbordamiento y aprenda algunas propiedades básicas de los números primos de la teoría de grupos que ayudan a resolver algunos problemas.

Valor de probabilidad y expectativa: Estas son las cosas básicas que debe saber:

• Cálculo de probabilidades como razones de problemas de conteo: haga esto y podrá calcular las cosas con muy buena precisión.
• Recurrencias para probabilidades y valores de expectativa: en muchos casos, incluso cuando puede contar y tomar razones para obtener probabilidades, es mucho más fácil encontrar una recurrencia directamente en términos de probabilidades. Sin embargo, cuidar el doble conteo puede ser un dolor.
• Linealidad del valor de la expectativa: aprenda a usarlo correctamente (no puedo) y muchos problemas con el valor de la expectativa deberían ser un paseo para usted.
• Caminata aleatoria: los problemas de caminata aleatoria modificada surgen muy a menudo como problemas de valor de probabilidad / expectativa, así que aprenda los resultados básicos.
• Problemas de lanzamiento de monedas: otro conjunto de problemas prácticamente utilizados en exceso.

PD: Probablemente me he perdido un par de cosas. Recuérdame en los comentarios y ampliaré la respuesta.

La mayor información está disponible para el Tutorial de Matemáticas Discretas.

Una excelente respuesta que ya tienes aquí; Solo agregaré que puede revisar los tutoriales de TopCoder (Tutoriales de algoritmos) y los foros de Cookbook (Foros de TopCoder) para ver muchos de los temas que necesitará explicados en la aplicación de los problemas de TopCoder.

Aunque la gran mayoría de los temas y conceptos matemáticos discretos se entrelaza con la informática y la programación, estos son los que debe conocer

1. Conjuntos
2. Lógica
3. Teoría de los números
4. Teoría de grafos
5. Arboles
6. Combinatoria
7. Teoría de la computación
8. álgebra de Boole

No estoy convencido de que la falta de antecedentes en matemáticas discretas sea la culpa de su bloqueo mental con las preguntas de TopCoder. Es bueno tener cierta familiaridad con los gráficos, incluidas cosas como listas vinculadas, árboles y gráficos acíclicos dirigidos. Pero todo eso también debería estar cubierto en sus cursos de estructuras de datos. Otros temas discretos de matemática, como la teoría de la complejidad y la combinatoria, también deben ser cubiertos en sus cursos de CS.

https://www.quora.com/What-topics-should-one-study-to-become-good-at-solving-mathematical-questions-in-Programming-Competitions?srid=moSf

Puede ver la lista de temas en el enlace de arriba.

¿Cuáles son los temas matemáticos que se cubrirán para la programación competitiva como acm, topcoder, facebook hackers cup, google code jam, codechef?

Consulte esta respuesta del usuario de Quora. Muy bien escrito

Veo las matemáticas discretas más como una forma de pensar sobre las cosas que sobre qué pensar. La teoría de grafos en general es enorme, una forma de pensar sobre algoritmos en general, teoría de conjuntos y cosas que puedes hacer con conjuntos. Es más un marco cuando se aplica a la programación que un conocimiento específico (y a menudo se usa para escribir notación para el núcleo de algoritmos).