[Música] bom pessoal então na aula de hoje a gente vai falar da estratégia de divisão em Conquista né para o projeto de algoritmos então é que nem a gente tinha comentado na última aula quando a gente falou de recorrência né a estratégia de divisão em Conquista né ela consiste basicamente em a gente solucionar problemas maiores né dividindo eles em problemas menores normalmente utilizando recorrência aí e depois combinando né de forma apropriada as soluções até a gente chegar na solução do nosso problema original tá então quando a gente está aplicando né o paradigma da divisão em
Conquista normalmente a gente vai passar por três etapas tá então na primeira etapa né que a etapa de divisão né então eu vou dividir o problema original nem problemas né de instâncias menores né ou seja em sub problemas desse problema original tá na etapa de conquista nesse sub problemas eles vão sendo resolvidos normalmente né de forma recursiva até até que eu chegue no último nível de recorrência que é o caso e por fim né na etapa de combinação então eu vou combinar essas soluções né de forma né a retornar e obter a solução do meu
problema original Além disso né é importante salientar né que às vezes né na etapa de combinação é necessário a resolução de um problema que não é exatamente né É igual ao problema original né ele não é um sub-problema do problema original né como por exemplo quando a gente trabalhou com o algoritmo emerge sorte né a gente viu lá que a parte do combina né na verdade ele trabalhava lá com sequências que já estavam ordenado aqui um corresponde exatamente ao problema original tá mas quando ocorre esse tipo de evento né então a gente considera que tudo
isso tá lá dentro da Etapa combina Além disso tá pode ser que algumas vezes né durante a recorrência eu tenho uma chamada indireta né ou seja o meu algoritmo chama um segundo algoritmo que resolve né uma etapa da resolução e esse algoritmo por sua vez né Chama faz novamente uma chamada ao algoritmo original é causando assim uma nova recorrência tá bom uma outra questão que é importante a gente colocar aqui quando a gente viu lá um merda de sorte né a gente viu que a gente quebrava sempre o problema em partes iguais né então nossa
equação de recorrência né o nosso tign né levavam ter higiene sobre dois tá Ou seja a Instância né do sub problemas era a metade do tamanho da instância original mas nem sempre Isso é regra tá então eu posso ter diferentes situações aí né diferentes quebras do problema original é resultante em diferentes equações de recorrência tá então por exemplo eu poderia ter né um problema onde a quebra dele aqui consistiria né nesse tipo de equação de recorrência Ou seja eu quebro o meu problema numa Instância de tamanho né 2n sobre 3 da instância original né considerando
questões original tem tamanho M né e um outro problema de tamanho ele sobre 3 ou se a gente pegar lá quando a gente trabalhou né com o nosso algoritmo do polinômio né que ocorria né Em cada chamada recursiva né A Nova Instância tinha simplesmente né uma unidade a menos do que o tamanho da instância original né Ou seja a minha equação de recorrência era da forma né tign Igual TG - 1 + 1 teta de um tá bom Então na verdade o que que eu tô contando para vocês que isso daqui né como quando a
gente utiliza a estratégia de divisão em Conquista a gente normalmente vai isso vai levar o projeto de algoritmo secursivos é os algoritmos recursivos né Normalmente eles vão entregar para a gente né equações de recorrência né Para que eu possa resolver essas equações de recorrência e estabelecer né os tempos de execução assintótipos desses algoritmos tá então a gente precisa ter ferramentas aí né para poder resolver essas equações de recorrência E é isso que a gente vai fazer ao longo dessa semana tá então a gente vai estudar três métodos né para resolver equações de recorrência Então a
gente vai estudar o método da substituição que a gente vai ver na próxima aula tá que basicamente Qual que é a ideia aqui né então a gente começa a supondo aí um limite assim tóxico para recorrência então a gente aplica lá indução matemática que a gente já viu né Para a gente mostrar que a nossa hipótese Inicial é válida tá um outro método né é o método lá da árvore de recursão tá então o que que eu vou fazer nesse caso eu vou converter a recorrência numa árvore né cujos nós eles representam né os custos
do sub-problemas Tá Na verdade a gente já até fez isso quando a gente calculou né o tempo de execução do sorte né lá eu comentei com vocês que eu não tava formalizando esse método que a gente ia formalizar depois é o que a gente vai fazer essa semana tá mas ali a gente já teve né uma primeira visão dessa metodologia aí da árvore de recursão e por fim né existe um método mestre tá que ele pode ser utilizado sempre né que o meu problema me entregar uma equação de recorrência nessa forma né ou seja um
tign que pode ser escrito como um a t Gene sobre B mais um FG n tá onde esse a que é uma constante maior igual a um B uma constante maior que um e fgn aqui é uma função dada ok bom mas para a gente falar aqui na ilustrar essa ideia né da divisão em Conquista vamos pegar um nessa um exemplo prático né então vamos imaginar que o problema de multiplicação de matrizes então primeiro a gente vai simplesmente imaginar como que a gente faria multiplicação de duas matrizes e depois a gente aplica então estratégia de
divisão em Conquista né de forma a gente obter aí um procedimento né um algoritmo para resolver esse problema utilizando divisão em Conquista tá Então olha só Então imagina aí que a gente quer projetar um algoritmo né que faça a multiplicação de duas matrizes A e B tá é inicialmente Vamos considerar por uma questão de simplicidade né que as nossas matrizes são matrizes quadradas né ou seja são matrizes irem por ele tá Então imagina que eu tenho aqui uma matriz x uma matriz y e eu tenho uma matriz resultante aqui dessa multiplicação que essa minha Matriz
a gente sabe né que um elemento Z e j ou seja um elemento aqui da minha Matriz Z na linha e na coluna J ele pode ser escrito que como simplesmente né multiplicação elemento a elemento de todos os elementos aqui da linha I da minha Matriz x pela coluna J da minha Matriz y e somados depois né ou seja né matematicamente né zij ele pode ser escrito né como esse somatório né de um até ele né que é o comprimento aqui tanto da linha quanto da coluna tá de X aí eu travo o i aqui
na Trava a linha para x Trava a coluna para y e corro k Ou seja eu vou de um até cá que tanto nos elementos da linha quanto os elementos da coluna tá bom e como que a gente poderia projetar então o algoritmo que fizesse isso para a gente Então vamos dar uma olhadinha nisso daí tá então um algoritmo que fizesse isso a gente acabou de falar ali qual que é operação que eu preciso fazer para um único elemento só que eu preciso fazer isso para todos os elementos né então o que que eu preciso
fazer aqui eu preciso correr né todas as linhas da Matriz x e todas as colunas da Matriz Y né realizando essa operação aqui tá Então olha só então primeiro algoritmo Que resolveria esse problema para gente né a gente tá chamando aqui de mmq né que seria multiplica matriz quadrada Então ele recebe as matrizes x y aqui né que tem dimensão n tá então na linha 1 aqui que a gente tá fazendo né eu tô criando inicializando essa Matriz Z que é a matriz que vai ser resultante dessa multiplicação tá E aí eu começo a criar
laços né Então nesse primeiro laço aqui eu faço de um até n então eu varro todas as linhas depois para J de um ATM eu varro todas as colunas iniciali isso aqui cada elemento da minha nova Matriz J tá E aí eu vou correr cara de um até ele né então quem que é o meu elemento resultante aqui né vai ser né o valor acumulado de z i j né x e k vezes y k J né Que nada mais é do que essa expressão que a gente comentou agora a pouco tá hora que eu
terminar esses três laços aqui então eu tenho finalizado aqui né A minha Matriz resultante dessa multiplicação tá bom vamos dar uma olhadinha no tempo de execução desse algoritmo né então a gente tem aqui né para eu criar a matriz Inicial Z O tempo é constante então é a teta de um é a mesma coisa que a linha 7 né Para eu devolver essa Matriz também o tempo é constante bom aí eu tenho que eu tenho esse laço mais externo aqui esse laço vai executar n vezes e aí eu tenho um laço interno esse laço né
que executa esse laço interno aqui vai executar o que n vezes n vezes né porque executa n vezes para cada vez o laço externo né então é n vezes n e o laço mais interno aqui ele vai executar n vezes n vezes n vezes né ele executa n vezes o laço externa ele e depois o outro que tá mais externo ainda tá então a gente pode afirmar né que o tempo de execução aqui é né Ou seja a gente tem aqui teta de um teta de um a gente já sabe né que quando a gente
faz esse tipo de soma esse cara domina né então eu posso desprezar esse teto de um aqui eu fico com teta de bom agora a gente vai fazer o que agora a ideia a gente aplicar né a divisão em Conquista para a gente criar então né um algoritmo né para resolver esse mesmo problema só que agora é aplicando a divisão e conquista então é qual que é a ideia né que a gente falou é pegar o problema original e quebrar ele em sub problemas cada vez menores tá então é fácil a gente quebrar por exemplo
uma matriz n por n né a multiplicação de matrizes por ele em matrizes dele por dois por n por dois n por quatro por n por 4 e fazendo assim até que eu chegue né no caso base lá que seria uma matriz um por um tá Então imagina que eu tenho aqui agora uma matriz X N por n uma matriz y n por n Então como que seria quebrar essa Matriz essa operação de multiplicação na verdade na operação entre matrizes por dois por ele por dois então cada Matriz aqui ó a b c d e
a mesma coisa que em Y né Tem o quê dimensão n sobre 2 por n sobre 2 tá então a minha Matriz Z aqui ela pode ser escrita Como que como a somatória da multiplicação dessa sub-matrizes então Z1 aqui seria simplesmente o que a vezes Z + B XG ou seja o resultado da multiplicação de uma matriz de duas matrizes n por 2 pela soma de outras duas matrizes por 2 e o mesmo para z22 z33 e z44 tá então o que que a gente fez aqui na verdade eu troquei né a multiplicação de uma
matriz n por ele não é pelo produto de 8 matrizes só que agora n por 2 por 2 ou seja eu quebrei né O meu problema original que tinha tamanho M por n um problema ele por dois por ele por dois e eu posso continuar fazendo isso que nem eu comentei com vocês até a gente chegar aqui um por um tá então a ideia o que que é eu tenho a minha Matriz original eu quebro ela em matrizes ele por dois vou pegar cada Matriz ele por dois quebrar em Matriz dele por quatro ele por
8 e vou quebrando assim até eu chegar no caso um por um né então eu vou quebrando então tapa de divisão aí eu começo a solucionar cada uma desses problemas e combinar as soluções né então eu vou voltando até eu chegar na minha solução original que corresponde a multiplicação das matrizes ele por n Tá então vamos dar uma olhadinha como que ficaria o pseu do código né de um algoritmo que implementasse a divisão em Conquista Então nesse caso aqui a gente está chamando ele de mmq né multiplicação quadrada recursivo então o que que o meu
algoritmo vai fazer ele recebe a matriz X e Y né de dimensão n na entrada ele cria que nem outro algoritmo né uma inicialismo uma matriz Z né de dimensão n por n e aqui ó se ele for igual a um Z1 é simplesmente X1 x y1 eu tô no caso base aqui mas se eu não tiver no caso base né se ele ainda não foi igual o que que eu vou fazer eu vou sair quebrando esse cara tá então é o que tá aqui na linha 4 né então se eu não tô no caso
base né ou seja se ele não é igual a um então eu vou particionar essas matrizes em oito matrizes ele por dois por n por 2 é que são aquelas Matriz que a gente acabou de falar né as nossas matrizes a b c d e f g e aí vou calcular agora como elementos da minha Matriz Z exatamente esses elementos que a gente acabou de ver lá né então eles são o que é a somatório do resultado das multiplicações as matrizes que tem a metade da dimensão da Matriz original tá então eu vou fazer isso
e esse algoritmo é recursivo né então que que vai acontecer ele vai vir aqui vai fazer essa chamada aí eu vou entrar agora no vou entrar no mesmo algoritmo só que agora o a dimensão da Matriz n sobre 2 ainda não é igual a 1 então eu vou entrar de novo vai ser no sobre 4 então vai ocorrer aquela quebra que eu acabei de mostrar para vocês e até a gente chegar no caso básico e aí depois eu retorno né fazendo calculando os resultados e combinando as soluções tá bom vamos dar uma olhadinha como é
que ficaria o tempo de execução desse algoritmo Então a gente tem aqui nessas três primeiras linhas aqui são tetas de um né eu tenho tempo constante né de execução a gente pode considerar que que essa linha aqui também a linha 4 né eu particionar em oito matrizes eu posso considerar que tem um tempo constante tá quanto tempo que eu gasto aqui nessa chamada né na verdade que eu tô fazendo aqui é o mesmo algoritmo resolver um problema né com entrada n sobre dois metade né ou seja o tempo que eu vou gastar agora é a
metade do tempo original né então é Ter Dinheiro sobre dois aqui também ter gênero sobre dois só que que acontece para para cada resultado dessas multiplicações eu preciso depois do que somar essas duas matrizes né E como eu sou matrizes n sobre dois por n sobre dois então eu tenho que n sobre dois vezes n sobre dois da n² / 4 Elementos Então eu tenho n a quarta somas né então eu tenho aqui teta de n² somas tá então eu tenho posso dizer que se n for igual a um eu tô no caso base Então
esse cara é teta de um né E se n for maior do que um que eu tenho eu tenho 8 chamadas recursivas né então eu tenho 8t de n sobre 2 mais né quatro quatro operações de soma aqui n² sobre 4 então teria 4 teta de n² + o teta de 1 né que seria a divisão dessas matrizes aqui tá bom a gente sabe né que a anotação assintoxica Na verdade o que que ela representa né um limitante superior né que é definido como uma função mesmo uma constante então eu fazer quatro vezes uma função
vezes uma constante né eu posso esse quatro absorvido pela própria constante Então na verdade aqui né eu posso simplesmente dizer que isso daqui é 8t mais teta de n² aí o teta de 1 teta de um é o mesmo caso do anterior né n² domínio Então posso desprezar Sobra para a gente simplesmente 8 T de n sobre 2 mais teta de n², quando n é maior do que 1 tá depois quando a gente for falar do teorema mestre a gente vai ver que na verdade né Essa equação de recursão aqui ela me dá esse resultado
tá teta de n o cubo que é na verdade em termos de tempo de execução é o mesmo tempo de execução né que a gente gastou lá no primeiro algoritmo cada um algoritmo interativo tá aqui na verdade a gente não ganhou em termos de tempo de execução né a gente simplesmente está mostrando duas abordagens diferentes né uma interativa e outra aplicando divisão e conquista levando a um algoritmo recursivo E aí a gente viu que apareceu inclusive aqui a nossa equação de recorrência né Para a gente poder calcular aqui o tempo de execução bom Além disso
eu queria falar para vocês né do algoritmo de strass é na verdade o que aconteceu a gente viu ali né nos dois casos ali no caso interativo e quando a gente aplicou divisão em Conquista né que o nosso tempo de execução assintotico era teta de n³ E durante muito tempos acreditou que isso era o melhor que isso conseguia fazer né na operação de multiplicação entre duas matrizes tá só que em 1969 né um matemático alemão chamado volkerstrassen né ele mostrou um algoritmo que era significativamente superior em termos de tempo de execução tá é mostrando que
ao invés né na divisão que eu acabei de falar para vocês né que a gente divide e transforma num problema de multiplicação de oito matrizes sobre dois porém sobre dois Na verdade ele mostrou que era possível né a gente quebrar isso daqui na verdade não é uma multiplicação de sete matrizes tal de sete multiplicações de matrizes né a maneira que ele fez isso né foi uma álgebra engenhosa né que tá fora do escopo desse desse curso tá mas o fato é né através dessa solução que os tracendeu né Eu agora passei a precisar somente de
sete multiplicações de matrizes e não mais de 8 Então o que aconteceu Aquela minha equação de recorrência que a gente acabou de ver né no nosso algoritmo onde aqui era 8tdiane sobre dois passou a ser 7 né de ter gênero sobre 2 tá isso daqui se a gente calcular o resultado é assintótico vai dar um tempo de execução teta de n elevado a 2,81 isso pode parecer pouco vai falar não o outro era n elevado a ocupa agora é 2 elevar n elevado a 2,81 né Mas se a gente pegar aqui um exemplo simples imagine
aqui multiplicação de matrizes 10 por 10 lembra que tempo assim então acho que a gente está sempre interessado em valores elevados de n né então a gente teria um tempo assim tóxico da ordem né de 1 milhão de execuções né se a gente utilizasse né a maneira clássica que a gente acabou de ver ali pra multiplicação de duas matrizes então se eu aplicar agora esse limitante né ou seja o algoritmo de strassem Eu tenho algo que da ordem de 400 mil execuções operações né o passos para eu resolver o meu problema ou seja cair por
menos da metade o tempo de execução tá então de fato é algo significativo bom pessoal então é a ideia que realmente apresentar para vocês né formalmente na estratégia de divisão de conquista a gente já tinha utilizado ela né mais informalmente então a gente formalizou ela aqui e a gente viu né que quando a gente aplica essa estratégia normalmente isso vai levar a gente a construção né de algoritmos recursivos né que vão entregar equações de recorrência para a gente né então a gente precisa de ferramentas né de metodologia para resolver essas equações de forma a gente
determinar né o tempo assim tópico de execução e é o que a gente vai fazer nas próximas duas aulas né a gente vai estudar três métodos aí pra gente resolver equações de recorrência Tá ok então até as próximas aulas pessoal [Música] [Música]