¿Qué debe saber todo programador sobre las ecuaciones de diofantina?

Answer 1

Como una persona con un verdadero amor por la programación y un amor tremendo, no correspondido e insaciable por las ecuaciones de Diophantine, mi respuesta sería absolutamente nada .

No hay nada que todo programador necesite saber sobre las ecuaciones de diofantina, a menos que se estire y se invente la noción de tal manera que saber lo que significa GCD se considere saber algo sobre las ecuaciones de diofantina. Muchos, muchos programadores exitosos e increíbles no saben lo primero acerca de las ecuaciones de Diophantine, y eso está perfectamente bien.

Muchos buenos programadores tienen la capacidad suficiente para que el razonamiento matemático pueda resolver, por ejemplo, ecuaciones lineales de diofantina con solo pensar en el problema, pero eso no significa que debían comprender esa técnica para ser buenos programadores.

Algunos programadores pueden encontrar varias formas de ecuaciones de diofantina en el curso de su trabajo, y es bueno si pueden resolverlas por sí mismos, pero no creo que esto suceda más de una vez en mucho tiempo, y no a todos.

Para ser claros, creo que el mundo sería un lugar mucho mejor si todos estuvieran entusiasmados con las ecuaciones de Diophantine y pasaran tiempo aprendiendo sobre las fascinantes y profundas teorías que se desarrollaron para manejarlas. (Por cierto, tengo sentimientos similares sobre la programación). Pero no puedo ver de ninguna manera que este conocimiento se convierta en una necesidad para ser un buen programador.

Answer 2

El hecho de que el décimo problema de Hilbert se resolvió negativamente: no puede haber un algoritmo para resolver de manera confiable todas las ecuaciones de Diophantine, incluso si se permite el tiempo exponencial.

Las personas involucradas también son bastante interesantes:

• A Yuri Matiyasevich se le atribuyó la resolución del décimo problema de Hilbert cuando era un estudiante universitario. Más recientemente, fue responsable de un programa extenso y muy exitoso para capacitar a estudiantes de secundaria en St. Peterbug, Rusia, para las olimpiadas de matemáticas y CS (los que estén familiarizados con las estadísticas recientes de ICPC podrían estar impresionados).
• El trabajo de Martin Davis está muy relacionado, y también se le atribuye un marco ampliamente utilizado para resolver instancias booleanas de SAT en la práctica (él es el D en DPLL).

• Gregory y David Chudnovsky: Gregory aparentemente también tuvo una solución al décimo problema de Hilbert, pero fue desafortunado al ser rechazado por los poderes que están en la Unión Soviética (historia interesante: la contribución de Chudnovsky al MRDP). Fue honrado con un premio McArthur (la beca genio), y aparentemente construyó supercomputadoras en un departamento de Nueva York con su hermano.

En una nota personal, conocí a todas las personas mencionadas en las cenas (Martin Davis fue un orador en una reunión de la sociedad profesional, pero las cenas con Yu. Matiyasevich y los hermanos Chudnovsky fueron más personales).

Como se señaló en los comentarios, Julia Robinson fue otra figura clave en el período previo a la solución del décimo problema de Hilbert.

Answer 3

Por lo que sé, resolver ecuaciones de diofantina no tiene aplicaciones en el cifrado, por lo que sería seguro decir que no hay áreas en este momento en las que sea un experto en el número de teoría de ecuaciones de diofantina.

Sin embargo, si eres lo suficientemente inteligente como para saber esa rama de la teoría de números, probablemente sea un impulso para tu capacidad general de resolución de problemas. Es una habilidad ingeniosa no tener una habilidad requerida en este momento.