Suponha que um algoritmo necessite 20 horas de processament...

A alternativa correta é a E - 20.

Para resolver essa questão, é necessário compreender a Lei de Amdahl, que é um modelo usado para prever o ganho teórico máximo de desempenho (speedup) na execução de tarefas em sistemas de processamento paralelo. A Lei de Amdahl afirma que o speedup é limitado pela porção de um programa que não pode ser paralelizada.

De acordo com a Lei de Amdahl, o speedup \( S \) é definido pela fórmula:

\[ S = \frac {1} {(1 - P) + \frac {P} {N}} \]

onde:

• P é a fração do algoritmo que pode ser paralelizado (neste caso, 19/20 ou 0.95, pois 19 horas de um total de 20 horas podem ser paralelizadas);
• N é o número de processadores (para o potencial teórico máximo, consideramos um número ilimitado de processadores).

Como o número de processadores é teoricamente ilimitado, o termo \( \frac {P} {N} \) tende a zero, e a fórmula se simplifica para:

\[ S \approx \frac {1} {(1 - P)} \]

Substituindo \( P \) por 0.95, temos:

\[ S \approx \frac {1} {(1 - 0.95)} = \frac {1} {0.05} = 20 \]

Portanto, o potencial teórico máximo de melhoria na velocidade de execução é de 20 vezes.

A parte não paralela pode ser feita em um processador paralelo somado a uma quantidade inversamente proporcional de processadores infinitos.

Pra que o comentário abaixo? Agregou conhecimento em que? Explicou algo ou veio somente pra confundir? enfim....

Questão retirada da Desciclopédia, ops digo: Wikipédia:

"Lei de Amdahl

...

Por exemplo, se o programa precisa de 20 horas usando um único núcleo de processamento, e a parte específica de um programa que demora uma hora para executar não pode ser paralelizado, enquanto as 19 horas restantes (95%) do tempo da execução pode ser paralelizado, independente de quantos processadores são dedicados a execução paralela deste programa, o tempo de execução mínima não pode ser menor que aquela crítica uma hora. Por isso o aumento de velocidade é limitado em no máximo 20x."

Fonte: https://pt.wikipedia.org/wiki/Lei_de_Amdahl

GABARITO ALTERNATIVA E

O Speedup é dado por: 1/((1-f)+f/n).

Temos que o f é dado por 19/20 que é o percentual do processamento que pode ser paralelizavel.

Logo: 1/ (0,05 + (0,95/n)

Entretanto como queremos saber o maximo que é possível paralelizar, seria como se n valesse infinito (diversos processadores realizando a operação).

logo podemos admitir que 0,95/n é igual 0, zerando essa parte na equação.

voltando para a equação temos que o speedup é 1/0,05 = 20

Gabarito E