Últimos Comentarios

martes, 26 de agosto de 2008

El problema de los filósofos cenando

Buenas noches familia...

Acabo de ver en Buenafuente (que ha salido un momento, pero no quiere dejar de cobrar royalties) que un tío bastante friki ha preguntado pidiendo ayuda para resolver un acertijo matemático que ya hemos resuelto en la cafetería de la Facultad de Medicina de Santiago de Compostela. Si alguien no lo sabe todavía, es donde curso estudios (sí, en la cafetería).


Resulta que entre la gente con la que me relaciono, hay un conjunto de personas bastante friki y de los de más alto nivel (de los que ven Naruto en japonés y cosas por el estilo), y que después de comer se aburren bastante sólo jugando al tute. Tanto se aburren que mientras memorizan las bazas que han salido para comentar la mano al final (si hubieras tirado el 3 de bastos cuando él tiró el 4 de copas...) se dedican a resolver acertijos y juegos matemáticos por pura diversión. Y este fue uno de los que cayó.

Como en internéééé ya hay de todo, podéis pasar por la wikipedia y mirar las soluciones que allí ponen y explican desde el punto de vista matemático, y donde también mencionan las situaciones de competencia y los bloqueos que hay que evitar en la resolución de problemas lógicos como este.

Bueno, pues al meollo. El planteamiento del problema viene siendo este:

Quién tiene hambre? Mmmm...

Cinco filósofos se sientan a cenar en una mesa donde hay 5 platos de fideos y 5 palillos/tenedores. Para poder comer, cada filósofo necesita 2 palillos y, evidentemente, debe compartirlos con sus comensales. Se trata de optimizar el uso de los palillos para que ninguno se muera de hambre.

Si todos deciden coger el palillo de su derecha a la vez, ninguno tendrá dos palillos y no podrán comer.
Si estableces turnos de uno en uno y luego sigue el de la derecha, es decir, uno come el resto mira, el que está a la izquierda del que empieza puede morirse esperando.

La solución que encontramos, y que es la mejor subjetivamente hablando, es la de establecer un turno doble, es decir, comen dos filósofos en posiciones alternas (dejando uno en medio). De esta forma, en una mesa de cinco comensales lo máximo que tarda un filosofo en comer son dos turnos.

El primer filósofo que pasa 2 turnos sin comer es el que se sienta a la izquierda del filósofo en el que empezamos a contar para repartir los turnos. Como el turno gira hacia la derecha, el defecto de esperar dos turnos también se hereda hacia la derecha. Es decir, si tuviste la suerte de comer como número uno, luego vas a pasar 2 turnos sin comer.

Si se reduce el tiempo durante el cual se tienen los dos tenedores, ninguno de los filósofos pasa hambre, ni siquiera el primero que espera los dos turnos.

¿Sencillo verdad?

Y no he necesitado hacer colas para los palillos (que esto no es el eMule por diox), ni poner un portero que controle que haya n-1 comensales para garantizar que al menos uno tenga dos palillos para poder comer.

Ya os pondré el de las monedas, que ese si que es divertido y no la parida esta, que se explica en cualquier carrera de Ingeniería.

Y os preguntaréis, ¿pero tú no estudias Medicina?

Ya, pero aunque no veo Naruto en japonés, soy bastante Geek.

5 comentarios:

Capuleto dijo...

No hace falta ser friki para llegar a esa solución. De hecho, con no ser un inútil llega.

Neodian dijo...

Yo lo estudie en sistemas operativos, para ejemplificar los bloqueos irreversibles(alias culegues) del SO.

Pero si te soy sincero era una de esas cosas que por su escaso interes habia olvidado.

Gui-J dijo...

Esta entrada debería de llamarse "Cómo rayarse con muy poco". Vaya perogrullada.

Por cierto Neodian, espero que algun dia me expliques como va el tema de los "culegues" del SO, que parece interesante, XDDDDDDDDDDDDD.

Neodian dijo...

Gui-j aun que se que es una pregunta retorica yo te respondo.

Como bien dice Monty en el articulo si cada uno de los filosofos coge el tenedor de su derecha o su izquierda se quedaran bloqueados eternamente esperando a que alguno lo libere, esto se llama bloqueo irreversible.

En un ordenador puede pasar de la misma forma si por ejemplo un programa necesita un fichero y la grabadora de cd. Asi que bloquea la grabadora de cdrom porque va a usarla, mientras otro que tiene bloqueado el fichero necesita la grabadora y asi ambos programas se quedan "colgados" en un estado de bloqueo irreversible un esperando por el fichero y otro por la grabadora.

El problema de estos bloqueos es que no se pueden resolver y pueden colgar la maquina, asi que en este caso se usa el algoritmo de la avestruz que consiste en agachar la cabeza y olvidarse del problema(true story), si se resuelve el solo pues de pm, sino habra que reiniciar.

Que conste que esto sucede mas a menudo de lo que os podais imaginar.

Un saludo y a cascarla.

BlackMouth dijo...

Guau!! Parece que el tema os ha molado...y que habéis vuelto de las vacaciones.

Y yo que pensaba que preferíais el porno...

Me ha gustado lo del avestruz, a ver si os pongo el de las monedas, que además sirve para ganar apuestas facilmente, nada de doblar pitillos con un billete ni cosas por el estilo.

Gracias por los comentarios!!!