Buenas, no sabría a qué se refiere exactamente con corrección del algoritmo. Ni tampoco sabría cómo analizar su complejidad.
En respuesta a Juan Agustín Rivero Szwaicer
Re: Ej 3b y 3c Semana 14
Hola! Nosotros lo vimos en el monitoreo, la corrección es la que venimos haciendo hasta ahora. Esto en este caso se corresponde a demostrar que tu algoritmo responde true sii hay una asignación de personas a hospitales que no supera las capacidades de los mismos.
Por el tema del tiempo de ejecución, supongo que si seguiste la sugerencia hiciste una llamada a Ford Fulkerson y alguna cosa mas, luego tenes que analizar cuanto demora cada uno de los pasos, desde la creación del modelado, porque el algoritmo de Ford Fulkerson resuelve un problema de flujo en grafos, y de entrada nosotros lo que recibíamos eran personas y hospitales. Si usaste la sugerencia el orden de ejecución sale bastante facil.
Por el tema del tiempo de ejecución, supongo que si seguiste la sugerencia hiciste una llamada a Ford Fulkerson y alguna cosa mas, luego tenes que analizar cuanto demora cada uno de los pasos, desde la creación del modelado, porque el algoritmo de Ford Fulkerson resuelve un problema de flujo en grafos, y de entrada nosotros lo que recibíamos eran personas y hospitales. Si usaste la sugerencia el orden de ejecución sale bastante facil.
En respuesta a Valentina Pereira Ciaffone
Re: Ej 3b y 3c Semana 14
Buenas,
No tengo mucho más para agregar que lo que comentó Valentina. La corrección del algoritmo es probar que el algoritmo retorna true si, y sólo si, hay una asignación que cumple con la restricción de que a cada persona se le asigne un hospital a menos de 30km de su ubicación, y que a cada hospital se le asignen menos de de n/k pacientes.
La complejidad hace referencia al orden del tiempo del algoritmo en función del tamaño de la entrada que, en este caso, la medimos en base a n y k. Como siempre, es importante definir la estructura en la cual se recibiría la entrada (personas, hospitales y, para cada persona, aquellos hospitales que se encuentren a menos de 30km de su ubicación). Si seguiste la sugerencia, tu algoritmo debería invocar al algoritmo de Ford Fulkerson y para calcular el orden de dicha invocación podés usar alguna de las implementaciones del libro. Fijate que el orden de FF depende de m (la cantidad de aristas) y C (la suma de las capacidades de las aristas salientes del nodo s), estos dos datos dependen de la entrada de tu algoritmo (n y k).
Saludos,
JP
No tengo mucho más para agregar que lo que comentó Valentina. La corrección del algoritmo es probar que el algoritmo retorna true si, y sólo si, hay una asignación que cumple con la restricción de que a cada persona se le asigne un hospital a menos de 30km de su ubicación, y que a cada hospital se le asignen menos de de n/k pacientes.
La complejidad hace referencia al orden del tiempo del algoritmo en función del tamaño de la entrada que, en este caso, la medimos en base a n y k. Como siempre, es importante definir la estructura en la cual se recibiría la entrada (personas, hospitales y, para cada persona, aquellos hospitales que se encuentren a menos de 30km de su ubicación). Si seguiste la sugerencia, tu algoritmo debería invocar al algoritmo de Ford Fulkerson y para calcular el orden de dicha invocación podés usar alguna de las implementaciones del libro. Fijate que el orden de FF depende de m (la cantidad de aristas) y C (la suma de las capacidades de las aristas salientes del nodo s), estos dos datos dependen de la entrada de tu algoritmo (n y k).
Saludos,
JP