martes, 28 de octubre de 2008

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.

domingo, 4 de mayo de 2008

Inteligencia Artificial - MINIMAX - Clisp





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

--

miércoles, 23 de enero de 2008

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 ............


viernes, 11 de enero de 2008

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



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

miércoles, 9 de enero de 2008

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



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