sgb
[Stanford GraphBase]. Colección de conjuntos de datos y programas de demostración diseñada para investigadores y estudiantes de algoritmos, combinatoria y estructuras de datos. Los programas están diseñados para ser interesantes por sí mismos como ejemplos de programación literaria. Incluye los progrmas assign_lisa, book_components, econ_order, football, girth, ladders, miles_span, multiply, queen, roget_components, take_risc y word_components.
$ assign_lisa
mostrará la asignación óptima de tareas o recursos minimizando el "descontento" de Lisa
$ book_components
analiza las interacciones entre los personajes de grandes obras de la literatura
$ econ_order
utiliza datos de la economía de los Estados Unidos para ordenar sectores económicos de manera que la mayoría de los flujos de dinero vayan en una sola dirección
$ football
toma los resultados de los partidos de la temporada de 1991 y modela un grafo para intentar asignar un ranking o clasificación justo a los equipos. Algunas opciones: Stanford, Miami, Notre Dame, Alabama o Texas
$ girth
encuentra la longitud del ciclo más corto posible dentro de él
$ ladders
encuentra el camino más corto para transformar una palabra de 5 letras en otra, cambiando solo una letra a la vez y pasando siempre por palabras válidas en inglés. Pide dos palabras de 5 letras, por ejemplo black white
$ miles_span
calcula el Arbol de Expansión Mínima [Minimum Spanning Tree - MST] utilizando datos de distancias reales entre ciudades de EE.UU
$ multiply
genera un grafo que representa la estructura de un circuito multiplicador de bytes
$ queen
colocar reinas en un tablero de ajedrez de $N \times N$ sin que se amenacen entre sí
$ roget_components
utiliza un diccionario de sinónimos y conceptos en inglés y crea un grafo dirigido donde los conceptos se apuntan entre sí
$ take_risc
genera un grafo que simula los estados y las instrucciones de una arquitectura de computadora tipo RISC
$ word_components
analiza el grafo de las palabras de 5 letras del idioma inglés. Dirá cuantas palabras de las que no puedes salir cambiando una sola letra para formar otra palabra válida
Nota.- En assign_lisa y miles_span, el programa dice cosas como: "Solved in 31246013 mems". Donald Knuth no mide el tiempo en milisegundos porque los procesadores cambian con los años, sino en "mems". Un "mem" es un acceso a la memoria de la computadora. Es la forma matemáticamente pura que inventó Knuth para comparar algoritmos: el algoritmo que use menos "mems" es el más eficiente, sin importar si se corre en una supercomputadora de 1993 o en una máquina de 2026.
