MO417 - Questão para a prova oral

Número: 064

Enunciado:
Multiplicar cadeias de matrizes é um problema extremamente importante. Em Computação Gráfica, por exemplo,
diversos tipos de transformações geométricas encadeadas podem ser representados por matrizes. Além disso,
placas gráficas aceleradoras implementam multiplicação de cadeias de matrizes em hardware.
Vimos que a multiplicação de cadeias de matrizes é um problema que pode ter sua solução otimizada por meio
de Programação Dinâmica. Com relação a isso, NÃO podemos afirmar que:

1. Podemos obter uma estratégia ótima simulando a multiplicação de pares de matrizes consecutivas da cadeia, resolvendo os subproblemas resultantes, e escolhendo o melhor.
2. Poderíamos explorar o fato de que a multiplicação de matrizes é comutativa e obter soluções ainda mais otimizadas para o problema da multiplicação de cadeias de matrizes.
3. Diferentes pares de matrizes consecutivas podem ser multiplicados primeiro porque a multiplicação de matrizes é associativa.
   
4. O modo como são colocados os parênteses numa cadeia de matrizes pode ter um enorme impacto sobre o custo de avaliação do produto.
5. NDA

Autor(a): Fábio de Souza Azevedo