Problemilla interesante

[HaCkZJuaNN]

Resulta que un amigo de la universidad me ha contado esto, que por lo visto es un problema famoso, relacionado con informática.

La forma intuitiva de verlo es la siguiente:

Tienes una fila de soldados. Todos los soldados son exactamente iguales. Cada soldado puede hablar con el que tiene delante y con el que tiene detrás. Se trata de que tú en un momento dado le digas al último soldado: "Dispara", y los soldados se comuniquen unos con otros, SIGUIENDO UN ALGORITMO IGUAL EN TODOS, de forma que en un momento dado todos los soldados disparen al mismo tiempo.

Forma un poco más rigurosa:

Se trata de máquinas de estados finitos. El número de soldados que tienes es finito PERO NO LO CONOCES DE ANTEMANO!!!! No vale contar los soldados porque los soldados(como máquinas que son) tienen un límite de hasta dónde pueden contar, y ese límite puede ser más pequeño que el número de soldados que hay. Los soldados sólo pueden estar en un número finito predeterminado no dependiente del número de soldados de estados(por ejemplo, 5), y dar un número finito predeterminado no dependiente del número de soldados de instrucciones distintas.

Las entradas/salidas de cada soldado pueden ser todas las que quieras porque al fin y al cabo se podrían codificar todas en una sola(potencias de 2, etc...), pero un número finito(esto nos gusta mucho decirlo) ;)

Los soldados no pueden disparar antes de tiempo, se trata de que cuando disparen todos a la vez ninguno haya disparado todavía(menuda tontería si no xD).

Pues hala. Si tenéis preguntas decídmelo.

Por cierto, por si no queda claro, el problema trata de escribir el algoritmo de los soldados.

Este problema está resuelto y aparentemente era muy complicado(aunque yo lo he resuelto y no me parecía tan complicado), y se ha demostrado que el mejor algoritmo que lo resuleve es de orden 2n-2(n = número de soldados). Mi solución es un poco más larga :P, pero funciona.

Además, esto se puede perfectamente implementar en bennu, basta con crear un proceso "soldado" que tenga el algoritmo dentro y que sea capaz de comunicarse con el soldado "anterior" y el "siguiente".

PS: Se me olvidaba, el primer soldado y el último soldado SABEN QUE SON EL PRIMERO Y EL ÚLTIMO. Y podéis declarar todas las variables que os hagan falta(finitas y predeterminadas ;) )

[Windgate]

Al primer soldado le pasas un N = 1

En cada "FRAME" el soldado pasa al siguiente su N + 1

Así que al final cada soldado queda con un valor igual a su posición en la fila

El último soldado recibe un valor  que almacena en M

El último soldado pasa al anterior un valor M - 1

En cada "FRAME" el soldado pasa al siguiente anterior M - 1 y además suma 1 en un contador K inicializado a 0

Cuando el valor del contador K coincide con la M que reciben disparan

Espero que me se haya entendido... ::)

[HaCkZJuaNN]

Al primer soldado le pasas un N = 1

En cada "FRAME" el soldado pasa al siguiente su N + 1

Así que al final cada soldado queda con un valor igual a su posición en la fila

El último soldado recibe un valor  que almacena en M

El último soldado pasa al anterior un valor M - 1

En cada "FRAME" el soldado pasa al siguiente anterior M - 1 y además suma 1 en un contador K inicializado a 0

Cuando el valor del contador K coincide con la M que reciben disparan

Espero que me se haya entendido... ::)

Esa es la idea fácil, pero no vale.

Si no conoces el número de soldados que hay, N podría llegar a valer cualquier cosa(finita, pero cualquier cosa), y tú tienes que saber desde el principio hasta cuánto saben contar los soldados; sin depender del número de soldados que haya.

Así que tú me dices que saben contar hasta 5000? Y si hay 5001 soldados??? Saben contar hasta 5000000000000000000000 y si hay 5000000000000000000001 soldados? etc... Se puede resolver sin tener que utilizar eso.

[Windgate]

Entiendo... Tiene que ser a prueba de límites de overflow, sigo meditando.

[SplinterGU]

Resulta que un amigo de la universidad me ha contado esto, que por lo visto es un problema famoso, relacionado con informática.

La forma intuitiva de verlo es la siguiente:

Tienes una fila de soldados. Todos los soldados son exactamente iguales. Cada soldado puede hablar con el que tiene delante y con el que tiene detrás. Se trata de que tú en un momento dado le digas al último soldado: "Dispara", y los soldados se comuniquen unos con otros, SIGUIENDO UN ALGORITMO IGUAL EN TODOS, de forma que en un momento dado todos los soldados disparen al mismo tiempo.

Forma un poco más rigurosa:

Se trata de máquinas de estados finitos. El número de soldados que tienes es finito PERO NO LO CONOCES DE ANTEMANO!!!! No vale contar los soldados porque los soldados(como máquinas que son) tienen un límite de hasta dónde pueden contar, y ese límite puede ser más pequeño que el número de soldados que hay. Los soldados sólo pueden estar en un número finito predeterminado no dependiente del número de soldados de estados(por ejemplo, 5), y dar un número finito predeterminado no dependiente del número de soldados de instrucciones distintas.

Las entradas/salidas de cada soldado pueden ser todas las que quieras porque al fin y al cabo se podrían codificar todas en una sola(potencias de 2, etc...), pero un número finito(esto nos gusta mucho decirlo) ;)

Los soldados no pueden disparar antes de tiempo, se trata de que cuando disparen todos a la vez ninguno haya disparado todavía(menuda tontería si no xD).

Pues hala. Si tenéis preguntas decídmelo.

Por cierto, por si no queda claro, el problema trata de escribir el algoritmo de los soldados.

Este problema está resuelto y aparentemente era muy complicado(aunque yo lo he resuelto y no me parecía tan complicado), y se ha demostrado que el mejor algoritmo que lo resuleve es de orden 2n-2(n = número de soldados). Mi solución es un poco más larga :P, pero funciona.

Además, esto se puede perfectamente implementar en bennu, basta con crear un proceso "soldado" que tenga el algoritmo dentro y que sea capaz de comunicarse con el soldado "anterior" y el "siguiente".

PS: Se me olvidaba, el primer soldado y el último soldado SABEN QUE SON EL PRIMERO Y EL ÚLTIMO. Y podéis declarar todas las variables que os hagan falta(finitias ;) )

o lei muy por arriba o te falto decir que es lo que se busca o representa tu "2n-2(n = número de soldados)"...

y creo que windgate te esta explicando como implementarlo en bennu, que creo no es lo que vos estas planteando...

por otro lado, el disparar al mismo tiempo dependera del tiempo que tarda cada uno en pasar la voz al otro y en el tiempo que todos tardan en recibir la orden, pero aun asi, mas si los soldados de mas atras no pueden contar la cantidad que tienen delante, y no pueden verlos ni escucharlos mas alla de sus vecinos cercanos (1 soldado delante y 1 detras), nunca sabra cuando el ultimo recibio la señal, y solo hasta que el del frente (o detras segun el sentido) le informe de tal situacion... y esto aca entra en un ciclo sin fin... ya que el de delante debera saber cuando el ultimo sabe que el (el de adelante) sabe que tiene la orden de disparar... puff...

a mi me parece el planteo un poco ridiculo e ilogico... si los soldados no pueden recibir la orden de una unica fuente en comun, hacer la sincronizacion es imposible...

quizas vos preguntas otra cosa, pero te falta aclarar mejor tu planteo...

[Drumpi]

Hombre, la solución sencilla es que le demos la orden al último soldado, y este guarda una variable propia i=1, y al siguiente le pasa i++, que lo guarda y le pasa i++ al siguiente. Así el último sabe cuantos soldados hay en la cadena.
Entonces le pasa al anterior una señal y espera "numero de soldados" (su propia i) ciclos para disparar, que es el tiempo que tardará la señal del último en llegar al primero, que al tener un valor i==1 esperará un ciclo.

Pero planteas la posibilidad de haber overflow en el tipo de la variable i, por lo que necesitamos algo contable que no provoque overflow... y es demasiado de noche para pensar en ello ;D
O bien buscar la forma de que el primer y el último soldado se comuniquen a traves de la fila de forma que dos señales lleguen simultáneamente al primero y al último.

[DCelso]

En bennu es muy facil.
ordenas a todos a disparar al mismo tiempo. ;D

[Windgate]

Yo creo que se basa en pasarse un 1 o un 0 hasta que de alguna mágica manera al final todos reciban un 2 a la vez... Por supuesto con coste 2n-2 no se me ocurre nada, se me ocurren soluciones con coste n!

Podría empezarse así:

- El primero pasa un 0 al segundo, el segundo pasa un 1 al tercero, así se alternan 1s y 0s hasta llegar al último. (Coste n)

...pero no se me ocurre como seguir...

@Splinter: Asumía que en el coste que n es el número de soldados y que existe un tiempo de comunicación 1 de forma que el tiempo total de resolver el problema sea T = 2n - 2

[DCelso]

2n-2 significa lo siguiente:
el primer soldado llama al que tiene a su lado, este nuevo llama al siguiente, asi hasta llegar al último, y vuelta hacia atras
el último solidado llama al qui tiene a su lado, este nuevo llama al siguie, así hasta llegar al primero,
justo aqui dispararían todos a la vez.
Una representación gráfica con cuatro soldados sería (2*4-2 = 6). O: soldado, _:iteración

   1    2    3
   _    _    _
O1_O2_O3_O4
   
    6   5    4

[Windgate]

Sí, tiene pinta de ser así DCelso, es como pasarse la patata caliente.

Pero en cada "turno" supongo que no sólo se comunicará un soldado con el siguiente, si no que habrá comunicación al mismo tiempo entre varios. Si no no le veo solución...

[DCelso]

Pero, probasteis mi ejemplo?

[HaCkZJuaNN]

o lei muy por arriba o te falto decir que es lo que se busca o representa tu "2n-2(n = número de soldados)"..

Es el orden del algoritmo más rápido que resuelve el problema. Si hay 10 soldados, el algoritmo tarda 18 instrucciones en funcionar. Eso es lo que quiere decir(es aproximado, 2n-2 es sólo cuando el número de soldados es muy muy grande). Yo no pido la solución óptima, yo ni la sé; la solución que yo encontré es de orden 3n(si hay 5000 soldados, tarda 15000 instrucciones en funcionar, aproximadamente).

y creo que windgate te esta explicando como implementarlo en bennu, que creo no es lo que vos estas planteando...

No, implementarlo en bennu sin restricciones es relativamente fácil, me refiero a resolver el problema con las condiciones que he impuesto(es la definición de máquina de estados finitos según tengo entendido), y que una vez resuelto, se puede comprobar que funciona en bennu(lo cual no quiere decir que en bennu haya soluciones más fáciles)

por otro lado, el disparar al mismo tiempo dependera del tiempo que tarda cada uno en pasar la voz al otro y en el tiempo que todos tardan en recibir la orden, pero aun asi, mas si los soldados de mas atras no pueden contar la cantidad que tienen delante, y no pueden verlos ni escucharlos mas alla de sus vecinos cercanos (1 soldado delante y 1 detras), nunca sabra cuando el ultimo recibio la señal, y solo hasta que el del frente (o detras segun el sentido) le informe de tal situacion... y esto aca entra en un ciclo sin fin... ya que el de delante debera saber cuando el ultimo sabe que el (el de adelante) sabe que tiene la orden de disparar... puff...

a mi me parece el planteo un poco ridiculo e ilogico... si los soldados no pueden recibir la orden de una unica fuente en comun, hacer la sincronizacion es imposible...

quizas vos preguntas otra cosa, pero te falta aclarar mejor tu planteo...

Nono, lo entendiste perfectamente, y ahí está la gracia, que es treméndamente complicado hacer que todos se comuniquen sin comunicarse. Pero se puede hacer, lo juro por mi vida. El truco está en hacer que se sincronicen sin tener que comunicarse... de alguna manera...

[HaCkZJuaNN]

Sí, tiene pinta de ser así DCelso, es como pasarse la patata caliente.

Pero en cada "turno" supongo que no sólo se comunicará un soldado con el siguiente, si no que habrá comunicación al mismo tiempo entre varios. Si no no le veo solución...

Obviamente tiene que haberla ;)

[HaCkZJuaNN]

2n-2 significa lo siguiente:
el primer soldado llama al que tiene a su lado, este nuevo llama al siguiente, asi hasta llegar al último, y vuelta hacia atras
el último solidado llama al qui tiene a su lado, este nuevo llama al siguie, así hasta llegar al primero,
justo aqui dispararían todos a la vez.
Una representación gráfica con cuatro soldados sería (2*4-2 = 6). O: soldado, _:iteración

   1    2    3
   _    _    _
O1_O2_O3_O4
   
    6   5    4

Pero el tema es que el último no tiene ni idea de cuándo llegas al primero, ya que él sólo se comunica con el anterior a él, así que cómo le dices que dispare cuando llegues al primero, si él no sabe cuándo llegas??? Y si le pasas la información a través de todos los de en medio, para cuando le llegue la orden, el primer ha disparado hace 3 horas. Se trata de que disparen A LA VEZ.

Por cierto, se supone que las instrucciones tardan todas el mismo tiempo y se sincronizan..., todos los soldados deciden que van a comunicar y cuando se les da la orden se lo comunican al siguiente y al anterior lo que le tengan comunicar. Como los FRAMES en bennu. Un sistema de "turnos".

[HaCkZJuaNN]

No se pueden poner spoilers en este foro?? Lo digo para poner mi solución y que sólo la lean los que quieran.