¿Cuáles son algunos algoritmos de utilidad legítima que son simplemente demasiado complejos para implementar? Permítanme ser claro: no estoy buscando algoritmos como el algoritmo de multiplicación de matriz óptima asintótica actual (Coppersmith-Winograd), que es razonable de implementar pero tiene...
¿Ha habido investigaciones sobre la implementación de construcciones de extractor de aleatoriedad? Parece que las pruebas de extractor utilizan Big-Oh, dejando la posibilidad de grandes constantes ocultas, lo que hace que las implementaciones programáticas sean potencialmente poco...
Me gustaría saber si hay bibliotecas de gráficos gratuitas para probar si existe un conjunto específico de menores en un gráfico
Estoy interesado en implementar SM para la tarea LP, sin embargo, he oído hablar de posibles dificultades: el libro de Cormen dice que es posible tener datos de entrada que harán que la implementación ingenua se comporte en un tiempo exponencial. También he oído que la implementación ingenua puede...
Estoy buscando una implementación de un algoritmo para calcular el ancho de ruta de un gráfico. Es bien sabido que calcular el ancho de ruta es equivalente a calcular el número de búsqueda de nodos, el número de separación de vértices o el grosor de intervalo del gráfico. El algoritmo no tiene que...
¿Cuáles son los algoritmos más eficientes en la práctica para multiplicar dos matrices booleanas muy dispersas (digamos, N = 200 y solo hay unos 100-200 elementos distintos de cero)? En realidad, tengo la ventaja de que cuando multiplico A por B, las B están predefinidas y puedo hacer un...
El libro A = B de Petkovsek, Wilf y Zeilberger describe algoritmos para calcular diferentes sumas de binomios. AFAIK, estos algoritmos todavía están siendo mejorados por diferentes autores. ¿Sabes dónde podemos encontrar las implementaciones más actualizadas de estos algoritmos? ¿Y sabe si existen...
Hay una muy buena construcción por Conway de números surrealistas. Son "números" que contienen números reales y ordinales, están totalmente ordenados y tienen todas las propiedades de un campo (excepto que no forman un conjunto sino una clase). Vea, por ejemplo, este pdf o Wikipedia para una...
¿Se han implementado árboles de partición? Aquí, estoy hablando de los árboles de partición de la geometría computacional. Las primeras versiones (casi) óptimas de las cuales se debieron a Matousek y otros, y más recientemente a Timothy Chan: https://cs.uwaterloo.ca/~tmchan/optpt_2_10.pdf Me...
Me refiero a la pregunta aquí: algoritmos poderosos demasiado complejos para implementar . Si un algoritmo es poderoso, pero demasiado complejo para implementar, ¿cómo puede estar seguro de que el algoritmo es correcto? Sin la implementación, no podrá probar el algoritmo en un escenario del mundo...