Seguimos buscando a Arshak. Ayudanos compartiendo!
Encuesta no oficial de docentes
Resultados de la encuesta no oficial de docentes
Probaste el SIGA Helper?

Donar $100 Donar $200 Donar $500 Donar mensualmente


Enviar respuesta 
 
Calificación:
  • 0 votos - 0 Media
  • 1
  • 2
  • 3
  • 4
  • 5
Buscar en el tema
Función_de_Ackermann
Autor Mensaje
LeaTex Sin conexión
Presidente del CEIT
.
********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 4.848
Agradecimientos dados: 56
Agradecimientos: 264 en 55 posts
Registro en: Apr 2008
BlogSpot Facebook Google+ Last.fm LinkedIn Twitter
YouTube
Mensaje: #1
Lightbulb Función_de_Ackermann
Hablando de nerdeadas en el trabajo, un compañero nos mostró la función de Ackermann, y tratamos de probar algunos valores haciendo el algoritmo en nuestra herramienta diaria (Smalltalk).

\[A(m;n)\begin{cases}n+1 & \text{ if } m=0 \\ A(m-1;1) & \text{ if } m>0 \wedge n=0 \\ A(m-1;A(m;n-1)) & \text{ if } m>0 \wedge n>0\end{cases}\]

Lo loco es que para valores 0, 1 o 2 es relativamente sencillo de calcularlo mentalmente. Después de empieza a complicar la cosa.

Cuando el primer parámetro de la función (m) llega a 4, se va todo a la mierda. Mientras tanto el segundo parámetro (digamos n) puede crecer hasta 8 sin problema. Ya a partir de 9 empieza a complicarse la cosa.

Acá les dejo una implementación en Smalltalk.

| ack |

ack := [:m :n :function |
m = 0
ifTrue: [ n+1 ]
ifFalse: [ n= 0
ifTrue: [ function value: (m-1) value: 1 value: function]
ifFalse: [ function value: (m-1) value: (function value: m value: (n-1) value: function) value: function]]].

0 to: 3 do: [ :m |
0 to: 8 do: [ : n | |start|
start := Time millisecondClockValue.
Transcript
show: ('A( %1 ; %2 ) = %3' bindWith: m printString with: n printString with: (ack value: m value: n value: ack) printString);
tab; tab; tab;
show: ('time %1 ms' bindWith: (Time millisecondClockValue - start));
cr
]
]



En Wikipedia está el detalle con la implementación en varios lenguajes. Si alguno se anima a probar A(4;1) y calcular el tiempo que tarda (deberían ser unos 10 minutos) cuéntenos cómo le fue.

04-07-2014 16:35
Visita su sitio web Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
luchovl2 Sin conexión
Presidente del CEIT
Dígame, Ingeniero.
********

Ing. Electrónica
Facultad Regional Buenos Aires

Mensajes: 1.334
Agradecimientos dados: 24
Agradecimientos: 355 en 323 posts
Registro en: May 2009
Mensaje: #2
RE: Función_de_Ackermann
"A(4, 2) es mayor que el número de partículas que forman el universo elevado a la potencia 200 y el resultado de A(5, 2) no se puede escribir dado que no cabría en el Universo físico."

Ja, ja. Es tan grande, que no entra ni en el universo.
04-07-2014 16:58
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Jarry Sin conexión
Anomalía de Belady
I know teh codez
**********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 2.007
Agradecimientos dados: 188
Agradecimientos: 259 en 98 posts
Registro en: May 2008
Mensaje: #3
RE: Función_de_Ackermann


ack 0 n = n + 1
ack m 0 = ack (m - 1) 1
ack m n = ack (m - 1) (ack m (n - 1))

main = print $ ack 4 2



ehm, copiar y pegar de wikipedia no sirvio, despues lo arreglo

ahora si, se rompe

No estoy necesariamente de acuerdo con lo que dice en el post de arriba
[Imagen: 971aa6599664453c05cb3e42d58bbc0eo.jpg]
(Este mensaje fue modificado por última vez en: 04-07-2014 17:45 por Jarry.)
04-07-2014 17:31
Visita su sitio web Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Buscar en el tema
Enviar respuesta 




Usuario(s) navegando en este tema: 1 invitado(s)