Preguntas teóricas en computación paralela
La década de 1980 dio lugar a los modelos PRAM y BSP de cómputo paralelo. Parece que el apogeo de ambos modelos fue a finales de los 80 y principios de los 90. ¿Estas áreas aún están activas en términos de investigación para algoritmos paralelos? ¿Existen modelos más nuevos y sofisticados para la...
¿Existe un análogo paralelo natural a los árboles rojo-negros con propiedades similares o incluso no terriblemente peores para las actualizaciones, mientras que es razonablemente eficiente en el trabajo? En términos más generales, ¿qué es lo mejor que podemos hacer para la búsqueda paralela con...
O ( log c n ) O ( n k )NCNC\mathsf{NC} captura la idea de eficientemente paralelizable, y una interpretación de la misma son los problemas que se pueden resolver en el tiempo usando procesadores paralelos para algunas constantes , . Mi pregunta es si hay una clase de complejidad análoga donde el...
Estoy buscando una buena encuesta sobre algoritmos y complejidad del álgebra lineal (operaciones como rango, inverso, valores propios, ... para matrices booleanas, y enteros / racionales) con énfasis en paralelo ( jerarquía ) y algoritmos polytime. No pude encontrar uno reciente....
En la clase de complejidad , se conjetura que algunos problemas NO están en la clase N C , es decir, problemas con algoritmos deterministas paralelos. El problema del flujo máximo es un ejemplo. Y se cree que hay problemas en N C , pero todavía no se encuentra una prueba.PAGP\mathsf{P}N...
Esta pregunta se relaciona principalmente con un problema práctico de ingeniería de software, pero me gustaría saber si los teóricos podrían proporcionar más información al respecto. En pocas palabras, tengo una simulación de Monte Carlo que usa un generador de números pseudoaleatorio, y me...
Estoy interesado en la complejidad de resolver ecuaciones lineales módulo k , para k arbitrario (y con un interés especial en las potencias primarias), específicamente: Problema. Para un sistema dado de ecuaciones lineales en incógnitas módulo , ¿existe alguna solución?n kmmmnnnkkk En el...
¿Es posible probar algorítmicamente si un número computable es racional o entero? En otras palabras, ¿sería posible que una biblioteca que implementa números computables proporcione las funciones isIntegero isRational? Supongo que no es posible, y que esto está relacionado de alguna manera con el...
La complejidad del circuito de profundidad limitada es una de las principales áreas de investigación dentro de la teoría de la complejidad del circuito. Este tema tiene su origen en resultados como "la función de paridad no está en AC0AC0AC^{0} " y "la función mod no es calculada por ", donde es la...
A partir de los comentarios sobre una de mis preguntas sobre MathOverflow, tengo la sensación de que la pregunta sobre que GCD está en vs. es similar a la pregunta sobre la Factorización de enteros en vs. .NCNC\mathsf{NC}PP\mathsf{P}PP\mathsf{P}NPNP\mathsf{NP} ¿Hay algo así como un algoritmo...
¿Hay problemas interesantes que están en pero no se sabe que están en N C 2 ? En el documento 'Una taxonomía de problemas con algoritmos paralelos rápidos', Cook menciona que se sabía que MIS solo estaba en N C 5, pero esto se ha reducido a N C 2 . Me pregunto si hay otros problemas con los...
Chong, Han y Lam mostraron que la conectividad st no dirigida se puede resolver en la EREW PRAM en tiempo con procesadores . ¿Cuál es el algoritmo paralelo más conocido para la conectividad st dirigida ? Indique el tiempo de ejecución, el algoritmo determinista / aleatorio y el modelo PRAM...
Mi experiencia es en teoría / lógica de complejidad (donde solo hay un proceso la mayor parte del tiempo), y en computación distribuida (donde hay procesos y uno o más pueden fallar con el tiempo). Sin embargo, ahora quiero poder decir algo sobre un proceso que genera / crea / deriva de otro...
Chong, Han y Lam mostraron que la conectividad st no dirigida se puede resolver en la EREW PRAM en tiempo con procesadores O ( m + n ) .O ( log n )O(Iniciar sesiónnorte)O({\log}n)O ( m + n )O(metro+norte)O(m+n) ¿Cuál es el algoritmo paralelo más conocido para la conectividad st en gráficos planos...
¿Es correcto llamar al framework mapReduce un tipo de framework de programación paralela síncrona masiva sin retención de memoria local dentro de los procesadores entre sincronizaciones? Si no, ¿qué modelo de programación paralela encapsula con mayor precisión el marco
En resumen, la pregunta es: en qué medida, la capacidad computacional para tareas difíciles realmente lo ayuda a resolver tareas fáciles. (Podría haber varias formas de hacer esta pregunta interesante y no trivial, y aquí hay uno de esos intentos). Pregunta 1: Considere un circuito para resolver...
Imagine un lenguaje de programación funcional cuyos únicos tipos de datos son escalares numéricos y anidaciones arbitrarias de matrices. El lenguaje carece de cualquier medio de iteración ilimitada, por lo que no se permite lo siguiente: bucles explícitos (de todos modos, sin mucho uso sin...
Estoy buscando notas de conferencias disponibles en línea u otros recursos que brinden una buena introducción a la programación paralela, al igual que el análogo paralelo de las clases básicas de informática. Mi enfoque es el siguiente: si bien puedo hablar sobre divide y vencerás, algoritmos...
En el documento con el mismo título que el de esta pregunta, los autores describen cómo construir una operación CAS de varias palabras linealizable sin bloqueo utilizando solo un CAS de una sola palabra. Primero presentan la operación de doble comparación, intercambio único, RDCSS, de la siguiente...
¿Qué clasificadores de aprendizaje automático son los más paralelizables? Si tuviera un problema de clasificación difícil, tiempo limitado, pero una LAN decente de computadoras para trabajar, ¿qué clasificadores probaría? Por supuesto, me parece que algunos clasificadores estándar que conozco se...