Algorítmica en php - The Knight's Tour

El juego de The Knight's Tour

En un post anterior explicaba el algoritmo minimax (como introducción a la poda alfa-beta). Ahora veremos un poco de algorítmica, mas concretamente el backtracking. Podría decirse (a groso modo) que sería una busqueda minimax o poda alfa-beta pero sin heurística, además, el backtracking nos asegura que siempre encontrará la solución (si la hay) recorriendo así todos los estados posibles.

En wikipedia podemos obtener las reglas y una explicación de su complejidad, excelentes.

Pongo la implementación en PHP como una primera aproximación para la resolución del problema (La implementación la he realizado en php y orientada a objetos para que sea mas facil comprender el proceso de backtracking, evidentemente, no persigo eficiencia).


Backtraking




El software dispone de modo traza para ver los pasos de "vuelta atrás"



Algunos tiempos de ejecución en mi ordenador:

• Tablero 4x4 => 0.19897794723511 seg.
  

• Tablero 5x5 => 39.455229997635 seg.

• Tablero 6x6 => 364.00200605392 seg.

• Tablero 7x7 => 39521.259037971 segundos

• Tablero 8x8 => aún ejecutándose :)

Se observa (sin analizar matemáticamente la complejidad del algoritmo) su complejidad claramente exponencial.

Curva de Bézier

Teoría de códigos

Introducción práctica a la teoría de códigos

Probabilidad

El origen de la probabilidad

The Singularity Is Near

Inteligencia Artificial - MINIMAX - Clisp

Descargar Codigo Fuente / Download Source Code

En el juego de restar cuadrados, dos jugadores juegan por turno restando cuadrados de números de una cantidad inicial, elegida al azar entre 10 y 1000. El siguiente turno partirá de la cantidad resultante de restar el cuadrado elegido a la cantidad, y así sucesivamente.

Por ejemplo, si la cantidad elegida es 17 y juega MAX, éste tendrá cuatro movimientos posibles: restar 4*4, quedando 1, restar 3*3, quedando 8, restar 2*2, quedando 13, o restar 1*1, quedando 16.

MAX y MIN juegan por turno y pierde el que no pueda realizar más movimientos, es decir, cuando la cantidad sea igual a 0.

Ejemplos de partida, partiendo de 13 y jugando MAX:

Partida 1:
MAX juega 2*2, quedan 9
MIN juega 3*3, MAX pierde

Partida 2:
MAX juega 1*1, quedan 12
MIN juega 3*3, quedan 3
MAX juega 1*1, quedan 2
MIN juega 1*1, queda 1
MAX juega 1*1, MIN pierde

--

Las máquinas del futuro, ¿podrán llegar a ser conscientes?

http://www.redcientifica.com/doc/doc200302140312.html

--

Ecole Nationale Supérieure des Télécommunications

Allá voy al curso: "Scientific Research Method : Techniques, Models and Practices" .........


Ver mapa más grande

Who Killed the Software Engineer? (Hint: It Happened in College)

http://itmanagement.earthweb.com/career/article.php/11067_3722876_1

http://picandocodigo.net/index.php/2008/01/22/seguimiento-de-%c2%bfdonde-estan-los-ingenieros-del-manana/

A conversation with Robert Dewar is enough to make you wonder about the future of the American software engineer. Dewar, a professor emeritus of computer science at New York University, believes that U.S. colleges are turning out programmers who are – there’s no nice way to say this – essentially incompetent.

To support his claim, Dewar penned a scathing broadside decrying today’s college-level computer science training. (The article was co-authored by Edmond Schonberg, also a CS professor emeritus at NYU.) Entitled Computer Science Education: Where are the Software Engineers of Tomorrow?, the widely read article has prompted heated discussion throughout the tech industry ............

Sistemas justo a tiempo

Just in Time es un término inglés que significa Justo a tiempo. Es un sistema de organización de la producción para las fábricas, de origen japonés.

Las compañías japonesas que durante los últimos años han adoptado el "método Toyota" o JiT han aumentado su productividad en los últimos 20 años.

Wikipedia

Descargar Sistema Justo a Tiempo
Toyota

Calidad total en Informatica

La calidad se define como total por suponer la plena implicación de todos los miembros de la empresa y de todos los aspectos relacionados con la organización de ésta. Esto incluye la implicación de todos los miembros de la empresa en mejorar la calidad continuamente, por lo que la calidad se intenta obtener en todo lo relacionado a la organización, no exclusivamente en el producto o servicio.

A lo que mercadotecnia se refiere, la calidad está directamente relacionada con la satisfacción del cliente, así es que se dice que a mayor satisfacción del cliente, el producto o servicio prestado adquiere mayor grado de calidad.

Wikipedia

Descargar la Calidad total en Informatica

El Omnipresente Árbol-B

Por DOUGLAS COMER. Departamento de Ciencia Computacional, Universidad de Purdue, West Lafayette, Indiana 47907

Los árboles B han llegado a ser, de hecho, un estándar para la organización
de ficheros. Los ficheros dedicados a usuarios, a sistemas de base de datos, y
a métodos de acceso de propósito general, han sido propuestos e implementados
usando árboles-B.
Palabras clave y Expresiones: Árbol-B, Árbol-B*, Árbol-B+, organización de fichero, índice.
Categorías CR: 3.73 3.74 4.33 4.34

DESCARGAR

Este documento ha sido traducido para la asignatura de Estructuras de Datos II, de la Escuela Universitaria de Informática - UPM