Perguntas com a marcação «dc.parallel-comp»

Questões teóricas em computação paralela

18
É possível testar se um número computável é racional ou inteiro?

É possível testar algoritmicamente se um número computável é racional ou inteiro? Em outras palavras, seria possível para uma biblioteca que implementa números computáveis ​​fornecer as funções isIntegerou isRational? Suponho que isso não seja possível e que isso esteja de alguma forma relacionado...

14
Problemas no NC desconhecidos por NC2

Existem problemas interessantes em mas não em N C 2 ? No artigo 'A Taxonomy of Problems With Fast Parallel Algorithms', Cook menciona que MIS era conhecido por estar apenas em N C 5, mas isso foi reduzido a N C 2 . Eu estou querendo saber se existem outros problemas com algoritmos paralelos de...

13
Algoritmos paralelos para conectividade st direcionada

Chong, Han e Lam mostraram que a conectividade st não direcionada pode ser resolvida no EREW PRAM no tempo com os processadores O ( m + n ) . Qual é o algoritmo paralelo mais conhecido para conectividade st direcionada ? Indique o tempo de execução, o algoritmo determinístico / aleatório e o modelo...

13
Quando um processo gera outro processo

Minha formação é em teoria / lógica da complexidade (onde há apenas um processo na maioria das vezes) e em computação distribuída (onde há processos e um ou mais podem falhar ao longo do tempo). No entanto, agora eu quero poder dizer algo sobre um processo de criação / criação / criação de outro...

11
A estrutura do MapReduce é um tipo de BSP?

É preciso chamar a estrutura mapReduce de um tipo de estrutura de programação paralela síncrona em massa sem retenção de memória local nos processadores entre as sincronizações? Caso contrário, qual modelo de programação paralela encapsula com mais precisão a estrutura...