Atividade 02
Leia com atenção as instruções abaixo.
Valor: 2,0 pontos na 1ª Nota.
Data da Entrega Limite: 16/04/2022
Formato de Entrega: envie um .pdf com a resolução, feito em meios digitais, para o chat privado do professor no Slack.
A atividade é individual.
Questão Única - 2,0 Pontos
Multiplicação de Matrizes utilizando uma máquima PRAM CREW. Sejam \(A\) e \(B\) \(\in\) \(R^{nxn}\) duas matrizes e \(C = A * B\) seu produto dado em coordenadas:
\begin{equation} C_{ij} = \sum_{k=0}^{n-1}{A_{ik} * B_{kj}}\text{ para todo $i$ e $j \in$ } \{0, ..., n-1\} \end{equation}
Projete um algoritmo CREW que utilize \(O(n^3)\) processadores e \(O(n^3)\) espaço em memória para calcular \(C\) em tempo logarítmico.
- Informe o pseudocódigo que é necessário para calcular o resultado quando \(n\) é potência de 2.
- Dê uma solução simples caso \(n\) não seja uma potência de 2. A complexidade é afetada?
- Sua solução é ótima em custo? (A equação do custo é linear?) Se não, forneça uma solução com custo ótimo.