Pasar de la intuición abstracta a la prueba formal

Esta pregunta es algo abierta y es poco probable que haya una única respuesta fija para esto, pero me encantaría escuchar algunas opiniones de las personas con una comprensión más profunda de este campo que la mía.

Estoy tomando una clase de nivel de posgrado en Optimización Combinatoria, y hemos pasado algunas de las primeras semanas revisando pruebas en Teoría de Grafos y problemas en Flujo de Redes.

Vengo de una formación en ingeniería, pero he tomado Matemáticas Discretas y Algoritmos en el pasado, por lo que tengo una comprensión funcional de estos temas. Sin embargo, lo que me falta es convertir la intuición que tengo para estas técnicas/teoremas en pruebas reales.

Por el bien de un ejemplo, considere el caso de la "Reclamación de cuello de botella" como se toma de aquí :

Teorema 1 Si ( GRAMO = ( V , mi ) , s , t , C ) es una red en la que el coste del caudal máximo es optar , entonces hay un camino desde s a t en el que cada borde tiene capacidad al menos optar | mi | .

Luego pasa a probar el teorema usando la Descomposición de flujo descrita a continuación

Lema 2 (descomposición de flujo) ( GRAMO = ( V , mi ) , s , t , C ) ser una red, y F ser un flujo en la red. Entonces hay una colección de flujos factibles F 1 , … , F k y una colección de s → t caminos pag 1 , … , pag k tal que:

  1. k ≤ | mi | ;

  2. el costo de F es igual a la suma de los costos de los flujos F i

  3. el flujo F i envía flujo positivo sólo en los bordes de pag i .

Ahora hay una cantidad razonable de intuición detrás de todo esto, para cualquier camino s → t camino, i , reduce el flujo en F i (el cuello de botella); puedes hacer esto a lo sumo | mi | tiempos antes ya no hay caminos. Y usando esto, es lo suficientemente simple como para mostrar que el Teorema 1 es correcto.

Claramente, la intuición está ahí, pero lucho con el proceso de pensar o construir tal prueba de forma independiente.

La pregunta, entonces, es: ¿qué tipo de recursos/herramientas están disponibles para alguien que espera profundizar en la informática teórica, para agudizar la intuición en algo más formal? La mayoría de los libros de texto que he tratado de leer recientemente, los he encontrado un tanto inaccesibles y densamente repletos de notación que no es muy útil.

Cualquier comentario, filosófico o de otro tipo, y/o consejos generales también son bienvenidos.

Desarrollar una intuición que pueda traducirse en una prueba formal es como el santo grial de la comprensión de las matemáticas. Creo que Tao lo llama la tercera etapa de la comprensión matemática. Desafortunadamente, muchos autores omiten la intuición, por alguna razón. Me ha ayudado a buscar autores que se preocupen por explicar la intuición (como Feynman en física). A menudo encuentro las mejores explicaciones de la intuición, y cómo la intuición se conecta con pruebas rigurosas, o puede convertirse en una prueba rigurosa, aquí en math.stackexchange.
Si está interesado en la complejidad computacional, tal vez le interese el libro Quantum Computing Since Democritus de Scott Aaronson.
@littleO gracias por la recomendación del libro. De hecho, estoy empezando a encontrar este sitio web como un gran lugar para discutir pruebas y conceptos en todos los niveles.

Respuestas (2)

No sé si esa es la respuesta que está buscando, pero para mí personalmente, la clave para comprender el flujo de la red es simplemente pensar en el flujo de agua. Es decir, supongamos que en el vértice s hay algo de bomba de agua bombeando X cantidad de agua por segundo, y en el vértice s hay un agujero, drenaje X cantidad de agua por segundo. En el medio, el agua viaja a lo largo de algunos bordes a diferentes caudales, que realmente no puedes controlar. Pero el caudal máximo entre un borde está limitado por su capacidad, que puedes imaginar como el grosor de una tubería de agua correspondiente. (Un pequeño tecnicismo es que técnicamente también puedes tener agua fluyendo en ciclos en algún lugar, desobedeciendo las leyes de la física y formando un móvil perpetuo).

El teorema de descomposición del flujo simplemente establece que cada s - t -el flujo se puede descomponer en como máximo | mi | forma de "ríos" s a t (y/o flujos circulares). Si acepta el teorema de descomposición del flujo tal como se da, el teorema 1 se vuelve realmente fácil: si hay como máximo | mi | ríos de s a t , al menos uno de ellos tiene que llevar al menos el caudal medio, que es al menos optar / | mi | .

Ahora, ¿cómo se probaría el teorema de descomposición del flujo? Suponga que tiene algunos s - t -flujo, luego seleccione algún borde mi tal que hay un flujo distinto de cero mi , digamos un flujo de 10 unidades/segundo por ejemplo. Ahora considere el gráfico dirigido H que consiste en todos los bordes sobre los cuales fluye algo de agua y el borde dirigido en la dirección en que fluye el agua. Entonces puedes extender mi ya sea en un dirigido s - t -camino o un ciclo dirigido PAG en H (porque el agua debe venir de algún lado , ¿no?). Ahora, el flujo a lo largo de los bordes de PAG no es necesariamente 10 unidades/segundo en todas partes, pero hay un borde de cuello de botella en PAG , decir con un flujo de C unidades/segundo. Luego puedes "restar" mentalmente un flujo a lo largo PAG de valor C . Tenga en cuenta que ahora el borde del cuello de botella desapareció de H , por lo que puede proceder por inducción y tiene la garantía de tomar | mi | pasos como máximo.

Ahora, por supuesto, no todos los teoremas tienen una explicación intuitiva como esta. En general, la intuición en matemáticas es muy difícil de obtener y toma mucho tiempo y es diferente para todos. En particular, los ejercicios ayudan mucho, en mi opinión.

¡Gracias por su respuesta! Lo que más me interesa comprender es el proceso de llevar la intuición que tenemos para ciertos objetos matemáticos y llevarla a pruebas más rigurosas. Elegí el ejemplo de flujo porque era con el que estaba trabajando en ese momento, pero una gran parte de esta pregunta se extiende a las pruebas en general.
En el momento en que publiqué esta pregunta, pude entender cómo y qué implica probar cosas con el flujo de la red, y supongo que estoy empezando a ver lo que se necesita para construir pruebas. ¡Espero que algún día pueda dar una respuesta satisfactoria a esta pregunta yo mismo!

Entré en redes con experiencia en física y matemáticas. Así, me había formado en las demostraciones de cosas que, partiendo de leyes muy fundamentales expresadas en términos matemáticos, llegan a los resultados después de muchas (a veces brutales) derivaciones matemáticas. Guardé mis respuestas a las asignaciones de Electrodinámica de Jackson después de más de 20 años, porque este tema (y QM relativista de Bjorken y Drell) transformó mi cerebro de alguna manera y determinó la metodología que seguí desde entonces.

Cuando llegué a la creación de redes, fue una historia diferente. Creo que podemos decir que la base matemática de las redes es la teoría de grafos (GT). Sin embargo, GT permite (diferente a la topología) algorítmico que el razonamiento algebraico. Entonces, después de pasar por la misma experiencia que te hizo hacer esta pregunta, decidí estudiar GT por mi cuenta, básicamente con la intención de entrenarme con esta forma de pensar y, con suerte, combinarla con mi experiencia en los métodos matemáticos que adquiero como un físico

Finalmente, llegué a la conclusión de que la respuesta está en aprender una metodología específica para modelar un problema y su solución. Sí, algo más relacionado con la filosofía (gnoseología y/o epistemología tal vez) como aconsejaste anteriormente. También recuerdo cuando estaba enseñando Física I, cómo los estudiantes con Calc II y III luchaban para resolver una ecuación cuadrática en términos de tiempo; de alguna manera no pudieron hacer la conexión de que usas los mismos métodos que usan en álgebra universitaria para resolver problemas de cinemática... entonces una sonrisa borró la frustración de sus rostros...

Si has encontrado tu respuesta, compártela.

Pasar de la intuición abstracta a la prueba formal
RespuestasAquíPolítica de privacidad1y, 0v