Lista de Exercícios

LISTA DE EXERCÍCIOS 1 Considere o algoritmo a seguir O algoritmo recebe uma matriz quadrada n n composta por números inteiros e devolve retorna um valor Assuma que a primeira chamada é dada passando os parâmetros M 1n 1n Assuma também que a matriz passada por parâmetro é indexada com valores entre 1 e n intervalo fechado Por questões de facilidade assuma que n é uma potência de 2 Pedese a Escreva as relações de recorrências e fórmula fechada do algoritmo b Determine a complexidade do algoritmo Algoritmo 2 Leia atentamente o texto abaixo sobre multiplicação de cadeia de matrizes O problema de Multiplicação de Cadeias de Matrizes busca determinar quais matrizes multiplicar primeiro para reduzir o número de operações em uma multiplicação A multiplicação de matrizes é uma operação binária que demanda Θ nml para multiplicar as matrizes A n m e B m l Dada um conjunto de matrizes A 1 A 2 A j arranjadas respeitando os requisitos de linha e coluna necessários para que ocorra a multiplicação desejase saber qual a ordem de multiplicações tal que o número de operações seja o mínimo possível Considere A i j como a matriz resultante da multiplicação entre as matrizes da sequência A i A i1 A j Considere também p 0 p 1 p j os valores de linha e coluna tal que A i tenha p i1 linhas e p i colunas A recorrência para encontrar o valor ótimo de número de operações pode ser visualizada abaixo OPT ij 0 se ij min ik j OPT ik OPT k1j p i 1 p k p j onde OPT ij representa o valor mínimo de operações para realizar a multiplicação das matrizes A i A i1 A j Com base nesse problema atenda o que se pede a Explique detalhadamente a recorrência OPT b Se um algoritmo de multiplicação de matrizes A nm e B ml de complexidade de tempo computacional Θ nl fosse conhecido o que mudaria na recorrência OPT ij para o problema de multiplicação de cadeia de matrizes considere o uso desse algoritmo de multiplicação