Algoritmos galácticos

En Galactic Algorithms nos hablan de una forma de llamar a esos algoritmos que tienen un buen coste asintótico pero que no los usarísmoa para calcular nada: Dick Lipton comenta como es un gran avance el ser capaces de predecir el comportamiento de un algoritmo sin ejecutarlo. También que hay algoritmos que son un gran descubrimiento aunque luego no se utilicen en el ‘mundo real’, por motivos como: descubrir nuevas técnicas, ser utilizables en el futuro si algunos paradigmas de computación cambian, abrir la puerta a otros algoritmos que sí son utilizables, o descubrirnos que algunos cotas temporales de algunos son excesivas (un programa costoso, pero con una cota polinómica cambiaría las ideas previas sobre determinados problemas, por ejemplo).

Uno que entra en esta categoría podría ser el de divide y vencerás para multiplicar matrices grandes, el algoritmo de Strassen.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s