>> [RONALDO] OLÁ, PESSOAL! TUDO BEM? DANDO CONTINUIDADE À NOSSA AULA DE RESOLUÇÃO DE PROBLEMAS, HOJE NÓS VAMOS FALAR DAS TÉCNICAS PARA A CONSTRUÇÃO DE ALGORITMOS.
ENTÃO, NÓS ESTAMOS PENSANDO AQUI ESPECIFICAMENTE PROBLEMAS COMPUTACIONAIS. EXISTEM VÁRIAS TÉCNICAS QUE PERMITEM VOCÊ DESENVOLVER UMA SOLUÇÃO COM MAIS EFICIÊNCIA E FACILIDADE. NÓS JÁ COMENTAMOS NA AULA ANTERIOR SOBRE ISSO, MAS SÓ RELEMBRANDO, EU TENHO A DECOMPOSIÇÃO, QUE É JUSTAMENTE EU PODER DECOMPOR O PROBLEMA EM PROBLEMAS MENORES, NÉ, E PARA ISSO EU VOU USAR AS TÉCNICAS DE REFINAMENTO SUCESSIVO, REUSO E RECURSÃO.
A TÉCNICA DE GENERALIZAÇÃO, QUE CONSISTE JUSTAMENTE EM VOCÊ CONSTRUIR UMA SOLUÇÃO MAIS GENÉRICA. E A PARTIR, NO CASO, DESSE PROBLEMA MAIS GENÉRICO, EU POSSO UTILIZAR ESSE ALGORITMO EM OUTROS CONTEXTOS, EM OUTROS PROBLEMAS. PARA ISSO, EU POSSO USAR O RECONHECIMENTO DE PADRÕES E O REUSO, E A TRANSFORMAÇÃO, QUE É JUSTAMENTE VOCÊ UTILIZAR UMA SOLUÇÃO DE UM PROBLEMA, PARA A SOLUÇÃO DE UM OUTRO.
. . PARA SOLUCIONAR UM OUTRO PROBLEMA.
BEM, UMA METÁFORA BASTANTE INTERESSANTE AQUI É O PROBLEMA DO ELEFANTE, NÉ? SERÁ QUE EU CONSIGO COMER UM ELEFANTE NO ALMOÇO? QUAL A RESPOSTA PARA ISSO?
SIM. "MAS COMO ASSIM EU CONSIGO COMER UM ELEFANTE? " CLARO, SE EU CONSEGUIR DAR UMA MORDIDA DE CADA VEZ, NO FINAL EU VOU ACABAR COMENDO ESSE ELEFANTE.
CLARO QUE EU TENHO QUE TER UM ESTÔMAGO PARA COMER UM ELEFANTE, MAS QUE EU CONSIGO, EU CONSIGO. OU SEJA, EU VOU FAZER O QUÊ? EU VOU PENSAR NESSA ANALOGIA QUE EU TENHO UM GRANDE PROBLEMA, UM PROBLEMA COMPLEXO, QUE PRECISA SER DECOMPOSTO EM TAREFAS MENORES E MAIS FÁCEIS DE SEREM RESOLVIDAS.
ISSO É O QUÊ? É A DECOMPOSIÇÃO. NO MOMENTO EM QUE EU TENHO UM PROBLEMA COMPLEXO, EU CONSIGO DIVIDIR ESSE PROBLEMA EM PROBLEMAS MENORES, EU VOU TER SOLUÇÕES PARA RESOLVER ESSES PROBLEMAS MENORES, EU FAÇO O QUE A GENTE CHAMA DE MÉTODO ANALÍTICO, QUE É JUSTAMENTE DECOMPOR UM PROBLEMA EM PROBLEMAS MENORES.
E DEPOIS EU FAÇO UM PROCESSO DE SÍNTESE, QUE É JUSTAMENTE JUNTAR ESSAS PARTES PEQUENAS NOVAMENTE, PARA QUE EU TENHA A SOLUÇÃO DO MEU PROBLEMA. UMA OUTRA TAREFA AQUI DO NOSSO DIA A DIA É ESCOVAR OS DENTES, NÉ? ALGUNS FALAM QUE ISSO NÃO É UM PROBLEMA, PARA OUTROS É UM GRANDE PROBLEMA, PARA AS CRIANCINHAS PRINCIPALMENTE.
MAS EU POSSO PENSAR NESSA TAREFA EM CINCO PASSOS, NÉ? E SE EU DIVIDIR ESSES CINCO PASSOS, EU SEI QUE SE EU RESOLVER CADA UM DESSES PASSOS, EU CONSIGO RESOLVER ESSE MEU PROBLEMA MAIOR. BEM, AGORA EU JÁ TENHO PROBLEMAS QUE SÃO MAIS COMPLEXOS, NÉ?
POR EXEMPLO, CONSTRUIR UMA RODOVIA, O LANÇAMENTO DE UM FOGUETE, UMA CIRURGIA NO CÉREBRO, OU, POR EXEMPLO, CRIAR UM APLICATIVO. ENTÃO, EU SEI QUE SÃO PROBLEMAS MAIS COMPLEXOS, QUE EU PRECISO PENSAR MANEIRAS QUE EU POSSO ESTAR DIVIDINDO, DECOMPONDO ESSE PROBLEMA EM PARTES MENORES, PARA QUE EU FAÇA DE MANEIRA SUCESSIVA, OU SEJA, SUCESSIVAMENTE EU VOU DIVIDINDO ESSE PROBLEMA EM MAIS PROBLEMAS MENORES AINDA, ATÉ QUE EU TENHA A SOLUÇÃO PARA ESSE PROBLEMA. ENTÃO, ESSA DIVISÃO, QUE EU FALO DE FAZER UM REFINAMENTO SUCESSIVO, É UMA TÉCNICA QUE ORIENTA JUSTAMENTE O PROCESSO DE VOCÊ DIVIDIR ESSE PROBLEMA EM PROBLEMAS MENORES.
ENTÃO, VOCÊS JÁ VÃO OUVIR FALAR MAIS VEZES SOBRE ISSO, MAS O REFINAMENTO SUCESSIVO É DIVIDIDO EM QUATRO ETAPAS. PRIMEIRO EU FAÇO O QUÊ? EU DIVIDO O MEU PROBLEMA EM PARTES PRINCIPAIS, COM AS PARTES QUE EU TÔ CONSEGUINDO VISUALIZAR.
DEPOIS EU VOU ANALISAR CADA DIVISÃO, PARA VERIFICAR SE TEM REALMENTE UMA COERÊNCIA. OU, ALÉM DA COERÊNCIA, NA TERCEIRA ETAPA TEM QUE VERIFICAR SE ESSA MINHA GARANTIA DE QUE ESTÁ COERENTE. .
. MAS SERÁ QUE EU PRECISO AINDA QUEBRAR ISSO? OU SEJA, TEM ALGUMA PARTE QUE AINDA ESTÁ COMPLEXA, EU PRECISO DIVIDIR ESSE PROBLEMA?
ENTÃO, SE EU TIVER QUE QUEBRAR ESSE PROBLEMA MAIS UMA VEZ, EU VOLTO PARA A PRIMEIRA ETAPA E VOU QUEBRAR ESSE PROBLEMA EM OUTROS PROBLEMAS, OU SEJA, VOU FAZENDO O QUE A GENTE CHAMA DE REFINAMENTO, EU ANALISO O PROBLEMA, SE ELE AINDA FOR COMPLEXO, EU CONSIGO DIVIDIR, EU DIVIDO ESSE PROBLEMA MAIS UMA VEZ. E NA ÚLTIMA ETAPA, EU VERIFICO, FAÇO UMA ANÁLISE. E SE O RESULTADO ESTÁ SATISFATÓRIO, COERENTE, ÓTIMO, EU NÃO PRECISO MAIS FAZER O REFINAMENTO, SENÃO EU TENHO QUE ANALISAR COM CALMA E VOU FAZER TANTOS QUANTOS PASSOS FOREM NECESSÁRIOS DE REFINAMENTO, PARA QUE EU CONSIGA RESOLVER O MEU PROBLEMA.
ESSA TÉCNICA É CONHECIDA COMO "TOP DOWN", OU SEJA, DE CIMA PARA BAIXO. POR QUÊ? EU COMEÇO COM UM GRANDE PROBLEMA E VOU REFINANDO ELE ATÉ OS MENORES POSSÍVEIS, PARA QUE EU TENHA A SOLUÇÃO DO MEU PROBLEMA.
UM EXEMPLO AQUI SERIA DESENHAR UM QUADRADO, NÉ? COMO EU FAÇO PARA DESENHAR UM QUADRADO? EU POSSO DIVIDIR EM PARTES.
ENTÃO, EU TENHO LÁ QUATRO PARTES, EU DESENHO UMA RETA, DEPOIS EU TENHO A SEGUNDA RETA, A TERCEIRA RETA E A QUARTA RETA. FORMEI O MEU QUADRADO. QUANDO EU PENSO ISSO COMO ALGORITMO, EU VOU FAZER O QUÊ?
VOU DESENHAR UMA RETA, DEPOIS EU VOU GIRAR A 90 GRAUS NO FINAL DESSA RETA, DESENHO A PRÓXIMA RETA, GIRO A 90 GRAUS NOVAMENTE. . .
LEMBRANDO, NO SENTIDO HORÁRIO. E DEPOIS DA QUARTA, EU NOVAMENTE FAÇO ISSO, ATÉ QUE EU FECHO O MEU QUADRADO. ENTÃO, EU TENHO AQUI, DESENHO A PRIMEIRA RETA, GIRO E DESENHO A SEGUNDA NOVAMENTE, ATÉ QUE EU OBTENHO AQUI O MEU QUADRADO.
BEM, NO ALGORITMO EXISTE QUATRO VEZES A AÇÃO "DESENHAR UMA RETA". ENTÃO, A GENTE PODE OBSERVAR O SEGUINTE: QUANDO EU VOU FAZENDO O REFINAMENTO SUCESSIVO, OU SEJA, EU VOU FAZENDO A DECOMPOSIÇÃO, EU POSSO AGRUPAR CERTAS ROTINAS, CERTO CONJUNTO DE INSTRUÇÕES, QUE NÓS CHAMAMOS DE MÓDULOS, SUBCONJUNTOS, ROTINAS OU COMPONENTES. COM ISSO, EU TENHO O QUE NÓS CHAMAMOS DE MODULARIZAÇÃO, OU SEJA, EU POSSO TÊ-LA AO DESENHAR UMA RETA, SENDO UM MÓDULO, NÉ?
COM ISSO, EU TENHO QUAIS VANTAGENS? EU FACILITO A RESOLUÇÃO, PRINCIPALMENTE NO DESENVOLVIMENTO; O GERENCIAMENTO, PORQUE SE EU ALTERAR A MANEIRA COMO EU ESTOU DESENHANDO UMA RETA, EU SÓ VOU ALTERAR ISSO UMA ÚNICA VEZ NO MODO QUE EU ESTOU ELABORANDO; O REAPROVEITAMENTO, O REUSO, PORQUE EU POSSO DEPOIS CHAMAR ESSE MÓDULO, OU REAPROVEITAR ESSE MÓDULO; E TAMBÉM NA PARALISAÇÃO QUE EU VOU APRESENTAR MAIS PARA FRENTE. BEM, ESSE MÓDULO QUE É CRIADO, QUE SERIA UM CONJUNTO DE INSTRUÇÕES, FICA BASTANTE CLARO NESSE EXEMPLO AQUI, EU TENHO UM ALGORITMO, ENTÃO EU TENHO O INÍCIO DO ALGORITMO, DE REPENTE EU TENHO O QUE NÓS CHAMAMOS DE "CHAMADA", OU "ATIVAÇÃO", DO MEU MÓDULO.
ENTÃO, NESSE MOMENTO AQUI, EU ESTOU ACIONANDO, CHAMANDO, ATIVANDO O MÓDULO, QUE SERIA O MÓDULO PRIMEIRO. NESSE MÓDULO TAMBÉM TEM O QUÊ? UM CONJUNTO DE INSTRUÇÕES.
ENTÃO, QUANDO OCORRE UMA CHAMADA, O FLUXO DE EXECUÇÃO PASSA PARA O MÓDULO CHAMADA. OU SEJA, NESSE MOMENTO, QUEM ESTÁ COM O FLUXO DE EXECUÇÃO É O MÓDULO, NÉ? TERMINANDO ESSE MÓDULO, ELE RETORNA PARA A LINHA POSTERIOR À CHAMADA E CONTINUA A SEQUÊNCIA DE INSTRUÇÕES.
QUANDO SE CONCLUI, ENTÃO, ELE VOLTA PARA ONDE? RETORNA PARA O MÓDULO CHAMADOR. OBSERVA QUE EU TENHO DOIS MÓDULOS AQUI, A GENTE PODE CHAMAR DE DOIS PROCEDIMENTOS, ROTINAS, COMPONENTES.
COMO EU DISSE, EU POSSO CHAMAR ESSE MÓDULO, POR EXEMPLO, O PRIMEIRO, VÁRIAS VEZES, COMO SE FOSSE, NO CASO, DESENHAR UMA RETA, ENTÃO EU CHAMO ESSA. . .
CHAMO OU ATIVO, NÉ, COMO VOCÊS QUEIRAM DIZER AQUI COM RELAÇÃO À CHAMAR A EXECUÇÃO DE UM DETERMINADO MÓDULO. O QUE EU JÁ DISSE, MAS REPETINDO, REFORÇANDO, É QUE QUANDO EU TRABALHO COM MODULARIZAÇÃO, EU. .
. FICA MUITO MAIS FÁCIL PARA CORRIGIR PROBLEMAS, NÉ? PORQUE, ALTERANDO O QUE ESTÁ AQUI NESSE MÓDULO, DEPOIS TODA VEZ QUE ALGUÉM CHAMAR AQUELE MÓDULO, BASTA EU ALTERAR UMA ÚNICA VEZ QUE JÁ ESTÁ RESOLVIDO O PROBLEMA.
AQUI EU TENHO UM EXEMPLO DE MODULARIZAÇÃO USANDO O SOFTWARE SCRATCH, ENTÃO EU TENHO AQUI O MÓDULO - O PROCEDIMENTO, NÉ, NO SCRATCH NÓS CHAMAMOS DE PROCEDIMENTO - QUADRADO E AQUI EU TENHO UMA AÇÃO. QUANDO EU CLICAR LÁ NA BANDEIRINHA, ELE VAI CHAMAR TRÊS VEZES NESSA ROTINA, ESSE PROCEDIMENTO QUE DESENHA UM QUADRADO. BEM, EU TINHA FALADO PARA VOCÊS QUE A GENTE IA FALAR DE PARALELIZAÇÃO, OU PARALELISMO, QUE SIGNIFICA O QUÊ?
SIGNIFICA ORGANIZAR RECURSOS, PARA QUE SIMULTANEAMENTE, LEMBRE DESSA PALAVRA, SIMULTANEAMENTE REALIZAR TAREFAS PARA ALCANÇAR UM OBJETIVO COMUM. ENTÃO, EU COLOQUEI ESSE FOGÃO AQUI, ACESO, COM ALGUMAS PANELAS, PARA QUE A GENTE POSSA FAZER UMA ANALOGIA. QUANDO VOCÊ DECIDE FAZER ALGUM TIPO DE COMIDA, UM PRATO ESPECÍFICO, QUE DEPENDE, POR EXEMPLO, DE COZIMENTO DE ALIMENTOS, CADA ALIMENTO TEM UM TEMPO DE COZIMENTO.
ENTÃO, SE EU ESPERAR COZINHAR UM PRIMEIRO, TERMINA, COZINHA O SEGUNDO E ASSIM POR DIANTE, SE EU QUERO AGILIZAR O MEU PROCESSO, EU POSSO COLOCAR O QUÊ? ESSES ALIMENTOS PARA SEREM COZIDOS EM PANELAS DIFERENTES, USANDO, VAMOS CHAMAR AQUI DE PROCESSADORES DIFERENTES, QUE SERIA A CHAMA DE CADA UMA DAS BOCAS DO FOGÃO, PARA FAZER O COZIMENTO DESSE ALIMENTO, E COM CERTEZA EU VOU TER ESSE RESULTADO MUITO MAIS ÁGIL. POR QUÊ?
EU JÁ ESTOU PROCESSANDO VÁRIOS ALIMENTOS AO MESMO TEMPO, QUE SERIA COZINHANDO, PARA QUE DEPOIS EU JUNTE TUDO ISSO E CONCLUA MEU PRATO. ENTÃO, NO CASO DE PROCESSAMENTO PARALELO, PARALELIZAÇÃO, EM COMPUTAÇÃO É JUSTAMENTE O PROCESSO DE VOCÊ RESOLVER PROBLEMAS DE FORMA PARALELA, EU CONSIGO FAZER COM QUE O MEU PROBLEMA SEJA REALIZADO, SEJA SOLUCIONADO POR MEIO DO PROCESSAMENTO EM VÁRIAS. .
. NO QUE NÓS CHAMAMOS DE VÁRIAS CPUS. POR QUÊ?
EU PRECISO TER, PARA PODER FAZER PROCESSAMENTO PARALELO, VÁRIAS CPUS, VÁRIOS PROCESSADORES. NESSE EXEMPLO TAMBÉM QUE EU TÔ COLOCANDO AQUI, DE VÁRIAS COLHEITADEIRAS, PARA QUE EU POSSA FAZER A COLHEITA, EU TÔ USANDO VÁRIOS PROCESSAMENTOS, VÁRIAS CPUS QUE PARA NÓS SÃO QUEM? SÃO AS MÁQUINAS COLHEITADEIRAS.
NESSE OUTRO EXEMPLO EM QUE EU ESTOU LEVANTANDO UMA CONSTRUÇÃO AQUI, O PROCESSAMENTO ESTÁ SENDO FEITO POR QUEM? PELOS SERES HUMANOS QUE ESTÃO MONTANDO ISSO AQUI. ENTÃO, PARA QUE EU POSSA FAZER O PROCESSAMENTO DE VÁRIAS TAREFAS AO MESMO TEMPO, EU PRECISO TER PROCESSADORES QUE FAÇAM ISSO.
É IMPORTANTE A GENTE VERIFICAR QUE EU TENHO UM FLUXOGRAMA DE UMA EXECUÇÃO SEQUENCIAL, ENTÃO TENHO LÁ O INÍCIO, A EXECUÇÃO DA PRIMEIRA TAREFA, DA SEGUNDA E DA ÚLTIMA TAREFA. ENTÃO, PARA EU IR PARA A SEGUNDA TAREFA, PRIMEIRO EU EXECUTEI A PRIMEIRA, PARA IR PARA A "N", EU EXECUTEI TODAS AS ANTERIORES. JÁ NO ALGORITMO PARALELO, EU POSSO TER O PROCESSAMENTO DE TODAS AS TAREFAS AO MESMO TEMPO.
MAS PARA QUE ISSO ACONTEÇA, EU TENHO QUE FAZER O QUÊ? EU TENHO QUE OLHAR PARA O MEU CONJUNTO DE INSTRUÇÕES E DEFINIR QUAIS SÃO AS TAREFAS QUE PODEM SER EXECUTADAS EM PARALELO, PORQUE ALGUMAS VEZES UMA TAREFA DEPENDE DO RESULTADO DE OUTRA E ISSO NÃO DÁ PARA SER EXECUTADO EM PARALELO. POR ISSO QUE OS CIENTISTAS PESQUISAM VÁRIOS MÉTODOS PARA QUE EU POSSA DIVIDIR UM PROBLEMA, DE MANEIRA QUE ELE POSSA SER TRABALHADO DE FORMA RECURSIVA.
NO FLUXO DE EXECUÇÃO DE UM ALGORITMO SEQUENCIAL, NÓS PODEMOS VERIFICAR QUE A TAREFA 2 SÓ VAI SER EXECUTADA APÓS A TAREFA 1 SER CONCLUÍDA. JÁ NO ALGORITMO PARALELO, NESSE FLUXO AQUI, NÓS PODEMOS VERIFICAR QUE TODAS AS TAREFAS VÃO SER EXECUTADAS AO MESMO TEMPO, NÉ? POR ISSO QUE O FLUXO, INCLUSIVE, O FLUXOGRAMA, ELE É ALTERADO.
BEM, QUAL É O PROBLEMA? O PROBLEMA É QUE EU TENHO UM CONJUNTO DE INSTRUÇÕES PARA RESOLVER MEU PROBLEMA, EU TENHO QUE AGRUPAR ESSE CONJUNTO DE INSTRUÇÕES EM TAREFAS, PARA QUE ESSAS TAREFAS SEJAM REALIZADAS EM QUÊ? EM PARALELO.
LEMBRANDO QUE UMA TAREFA NÃO DEPENDE DO RESULTADO DE UMA OUTRA TAREFA, PARA QUE ELA POSSA SER PROCESSADA, EXECUTADA EM PARALELO. E POR ISSO QUE NÓS TEMOS VÁRIAS PESQUISAS EM ANDAMENTO, JUSTAMENTE SOBRE COMO EU POSSO DIVIDIR PROBLEMAS, PORQUE NÃO É TÃO TRIVIAL VOCÊ PEGAR UM PROBLEMA, DIVIDIR ELE, PARA QUE ELE POSSA SER EXECUTADO DE FORMA PARALELA. BEM, EXISTEM VÁRIOS SOFTWARES QUE TÊM A NECESSIDADE DA EXECUÇÃO SIMULT NEA.
O PROBLEMA É COMO EU JÁ DISSE, EU PRECISO TER HARDWARES ESPECÍFICOS E PRECISO DIVIDIR O MEU PROBLEMA, PARA QUE ELE POSSA SER EXECUTADO EM PARALELO. NA VERDADE, O QUE VEM ACONTECENDO É QUE EXISTE UMA EXECUÇÃO CONCORRENTE. OU SEJA, O PROBLEMA É QUE A GENTE NÃO TEM HARDWARE, ENTÃO O PARALELISMO ACONTECE COM A INTERCALAÇÃO DE PROCESSOS.
ESSE EXEMPLO AQUI, ESSE GIF, ONDE EU TENHO AQUI UM MORCEGO E UM GRILO, NA VERDADE, AQUI NÃO ESTÁ ACONTECENDO SIMULTANEAMENTE, EXISTE UMA CONCORRÊNCIA, OU SEJA, O GRILO DÁ UM PASSO, DEPOIS O MORCEGO BATE ASAS, E VICE-VERSA. SÓ QUE ISSO ACONTECE TÃO RÁPIDO, QUE VOCÊ TEM A SENSAÇÃO DE QUE A COISA ESTÁ ACONTECENDO DE FORMA SIMULTÂNEA. BEM, A TÉCNICA DE GENERALIZAÇÃO É EXTREMAMENTE IMPORTANTE, PORQUE A PARTIR DO MOMENTO QUE A GENTE CONSEGUE IDENTIFICAR UM PADRÃO, E ESSE PADRÃO PODE SER UTILIZADO NA RESOLUÇÃO DE OUTROS PROBLEMAS, DE OUTRAS CLASSES DE PROBLEMA, EU TENHO UMA GRANDE VANTAGEM QUE É JUSTAMENTE A ECONOMIA, ECONOMIA NO SENTIDO DE TEMPO, DESENVOLVIMENTO.
E NÃO SÓ ISSO, EU CONSIGO ADAPTAR SOLUÇÕES, OU PARTE DELAS, PARA OUTRAS CLASSES DE PROBLEMAS, PORQUE EU JÁ SEI QUE AQUELE PROBLEMA FOI RESOLVIDO E COMO FOI RESOLVIDO. ALÉM DISSO, EU POSSO USAR TAMBÉM PARA CRIAR MODELOS PREEMPTIVOS. O QUE SIGNIFICA ISSO?
COMO EU JÁ TENHO PADRÕES, EU POSSO USAR ESSES MODELOS PARA QUE ELES SEJAM CAPAZES DE PREDIZER AÇÕES FUTURAS. ANALISANDO A SEQUÊNCIA DE FIBONACCI, VOCÊ PODE VERIFICAR QUE ELA É DEFINIDA EM TERMOS DE SI PRÓPRIA. SE A GENTE FOR VERIFICAR A FORMA GERAL, ONDE EU TENHO QUE FIBONACCI DE "N" É FIBONACCI DE "N" MENOS 1, MAIS FIBONACCI DE "N" MENOS 2.
ENTÃO, ELA ESTÁ SENDO DEFINIDA EM TERMOS DE SI PRÓPRIA. ESSE CONCEITO É CHAMADO DE RECURSIVIDADE. ENTÃO, A RECURSÃO, COMO NÓS PODEMOS DIZER, É UMA FORMA INTERESSANTE DE A GENTE PODER RESOLVER PROBLEMAS COMPLEXOS, PORQUE EU POSSO DIVIDIR UM PROBLEMA EM PROBLEMAS MENORES, SÓ QUE DE MESMA NATUREZA.
ENTÃO, NESSE CASO AQUI, EU TÔ DIVIDINDO O MEU PROBLEMA EM PROBLEMAS MENORES DA MESMA NATUREZA. E QUANDO A GENTE FOR IMPLEMENTAR UM ALGORITMO RECURSIVO, EU TENHO QUE LEVAR EM CONSIDERAÇÃO DUAS PARTES, A PRIMEIRA DELAS NÓS CHAMAMOS DE CASO TRIVIAL, OU SEJA, É UMA CONDIÇÃO DE PARADA, UMA SOLUÇÃO JÁ CONHECIDA. NESSE CASO AQUI, EU JÁ SEI QUE O RESULTADO DE FIBONACCI 1 É 1.
ENTÃO, ISSO NÓS CHAMAMOS COMO CONDIÇÃO DE PARADA, NÉ? E, ALÉM DISSO, EU PRECISO TER UM MÉTODO GERAL QUE REDUZA O PROBLEMA A UMA OU MAIS SOLUÇÕES MENORES. SÓ PARA LEMBRAR AQUI, UMA METÁFORA BASTANTE INTERESSANTE É QUE PARA VOCÊ FAZER IOGURTE, VOCÊ PRECISA DE LEITE E TAMBÉM UM POUCO DE IOGURTE, QUE SERIA DEFINIDO EM TERMOS DE SI PRÓPRIO, PARA FAZER UM IOGURTE, EU PRECISO DE IOGURTE, TÁ?
VANTAGENS DA RECURSIVIDADE. VÁRIOS PROBLEMAS COMPLEXOS SÃO INERENTEMENTE RECURSIVOS, ENTÃO EU PRECISO RESOLVÊ-LO DE FORMA RECURSIVA, O MEU ALGORITMO VAI FICAR MUITO MAIS CLARO, MAIS CONCISO. O PROBLEMA.
O PROBLEMA É QUE EU PRECISO, QUANDO EU FAÇO A EXECUÇÃO, AS CHAMADAS RECURSIVAS, EU VOU CONSUMIR MAIS MEMÓRIA E COM CERTEZA VAI FICAR MAIS LENTO A EXECUÇÃO DESSE PROCESSO. ALGUNS EXEMPLOS. ENTÃO, VÁRIOS PROBLEMAS SÃO RECURSIVOS, UM FIBONACCI, QUE EU JÁ DISSE, ENTÃO EU TENHO UMA CONDIÇÃO DE PARADA AQUI, QUE FIBONACCI DE "N" IGUAL A ZERO, RETORNA ZERO, FIBONACCI DE 1, O RESULTADO É 1.
E A FÓRMULA GERAL, QUE FIBONACCI DE "N" É: FIBONACCI DE "N" MENOS 1, MAIS "N" MENOS 2. ENTÃO, ESSE FIBONACCI AQUI PARA NÓS VAI SER O QUÊ? UMA MODULARIZAÇÃO, UM MÓDULO, UM ROTINA, UM PROCEDIMENTO QUE EU VOU CHAMAR, QUE IMPLEMENTA A FÓRMULA GERAL.
TEM UM EXEMPLO DO FATORIAL, QUE FATORIAL DE "N" VAI SER "N" VEZES QUEM? FATORIAL DE "N" MENOS 1. BEM, AGORA AQUI EU APRESENTO DOIS ALGORITMOS, UM EU CHAMO DE ALGORITMO ITERATIVO.
O ALGORITMO QUE NÃO É RECURSIVO, É CONHECIDO COMO ALGORITMO ITERATIVO. O ALGORITMO É PARA SOMAR OS "N" PRIMEIROS NÚMEROS INTEIROS, TÔ FAZENDO AQUI O VALOR INICIAL, "N" COMEÇANDO COM 5. COMO É QUE EU FAÇO PARA SOMAR OS "N" PRIMEIROS NÚMEROS?
ENTÃO, SE EU TENHO LÁ SOMA DE "N" SENDO CINCO, EU TENHO "1+2+3+4+5", O TOTAL É 15. SE FOR PARA IMPLEMENTAR O ALGORITMO QUE FAZ ISSO, EU TÔ COLOCANDO AQUI O PSEUDO CÓDIGO, ENTRANDO COM O VALOR DE "N", LENDO "N", ENTÃO TENHO AS VARIÁVEIS, NÉ? LEMBRANDO QUE VARIÁVEL É O QUÊ?
VARIÁVEL EU VOU UTILIZAR PARA ARMAZENAR OS VALORES EM MEMÓRIA. ENTÃO, FAZENDO A ENTRADA DE DADO, COM O VALOR DE "N", QUE EU QUERO FAZER A SOMA DOS "N" PRIMEIROS NÚMEROS. E COMO EU QUERO FAZER INDEPENDENTE DO VALOR DESSE "N", EU TENHO QUE PENSAR NO MEU ALGORITMO, QUE ELE VAI FAZER O QUÊ?
VAI FICAR FAZENDO O QUÊ? UMA REPETIÇÃO PARA QUE EU POSSA FAZER A SOMA. ENTÃO, ENQUANTO O MEU "I" FOR MENOR QUE O "N", VOU SOMAR "I" AO "N".
OK? BEM SIMPLES ESSE ALGORITMO. AGORA, EU POSSO PENSAR UM ALGORITMO QUE SOMA E QUE JÁ É SIMPLES, DE MANEIRA RECURSIVA, NÉ?
PORQUE EU SEI QUE A SOMA DE "N" VAI SER QUEM? "N" MAIS. .
. A SOMA DE "N" MENOS 1, QUE SERIA A SOMA DE 5 É 5, MAIS SOMA DE 4, E ASSIM POR DIANTE. ENTÃO, EU POSSO IMPLEMENTAR UMA FUNÇÃO RECURSIVA, ONDE EU TENHO A CONDIÇÃO DE PARADA, QUE É O QUÊ?
QUANDO "N" FOR IGUAL A 1, RETORNO QUEM? O VALOR 1. JÁ QUANDO.
. . SE O "N" NÃO FOR 1, VOU RETORNAR QUEM?
"N" MAIS A CHAMADA DA MINHA FUNÇÃO RECURSIVA, PASSANDO QUEM? "N" MENOS 1. OU SEJA, AQUI EU TÔ FAZENDO A CHAMADA RECURSIVA, EU TÔ CHAMANDO A FUNÇÃO SOMA DENTRO DA DECLARAÇÃO DELA MESMA.
OU SEJA, ELA É DECLARADA EM TERMOS DE SI PRÓPRIA. BEM, AQUI AGORA EU APRESENTO UM DESAFIO PARA VOCÊS, SÓ LEMBRANDO ANTES O SEGUINTE: NÓS FALAMOS DE VÁRIAS TÉCNICAS QUE SÃO IMPORTANTES PARA A CONSTRUÇÃO DE ALGORITMOS, PROVAVELMENTE VOCÊS NÃO CHEGUEM A IMPLEMENTAR NENHUMA DESSAS TÉCNICAS, PORQUE O NOSSO OBJETIVO É QUE VOCÊS CONHEÇAM ESSAS TÉCNICAS E POSSAM SABER CONCEITOS, E POSTERIORMENTE APLICAR ISSO NO DIA A DIA DE VOCÊS. BEM, NESSE DESAFIO QUE EU TÔ APRESENTANDO AGORA, É O DESAFIO É DESSE TEMA, NO CASO DE RESOLUÇÃO DE PROBLEMAS, É A TORRE DE HANÓI, QUE É UM QUEBRA-CABEÇA QUE FOI DIVULGADO EM 1883 E É BASTANTE INTERESSANTE, PORQUE É UM JOGO QUE CONTRIBUI PARA O RACIOCÍNIO LÓGICO E PRINCIPALMENTE PARA A RESOLUÇÃO DE PROBLEMAS.
QUAL O OBJETIVO DO HANÓI? O OBJETIVO É QUE EU POSSA MOVER TODOS OS RISCOS DE UMA HASTE, OU SEJA, DA PRIMEIRA HASTE PARA A ÚLTIMA HASTE, USANDO A HASTE MEIO COMO AJUDA, NO CASO. E QUAL É A REGRA?
PARA QUE EU POSSA PASSAR TODOS OS DISCO, DO PRIMEIRO PARA O ÚLTIMO, EU NÃO POSSO TER UM PINO, NO CASO AQUI, DE MAIOR DIÂMETRO, FICANDO SOBRE O DE MENOR DIÂMETRO. OU SEJA, OS PINOS MAIORES SEMPRE VÃO ESTAR EMBAIXO. OK?
ENTÃO, AQUI O OBJETIVO NOSSO DESSE DESAFIO É VOCÊS PODEREM CALCULAR O NÚMERO DE MOVIMENTOS MÍNIMOS PARA RESOLVER O HANÓI COM QUALQUER QUANTIDADE DE DISCOS. OK? ENTÃO, EU TÔ MOSTRANDO AQUI NO ESTÁGIO INICIAL, NÓS VAMOS TRABALHAR COM TRÊS DISCOS, AQUI NÓS FALAMOS PINOS, MAS OS PINOS SÃO OS DISCOS.
OK? SÓ PARA DEIXAR ISSO CLARO PARA VOCÊS. ENTÃO, EU TENHO O ESTADO INICIAL, ENTÃO EU POSSO FAZER O QUÊ?
VOU MOVER O MEU PRIMEIRO DISCO, NÉ, QUE É O MENOR, PARA O TERCEIRO EIXO. DEPOIS EU VOU MOVER O DO MEIO, O SEGUNDO, LEVO ESTE DO MEIO, É O SEGUNDO EIXO. DEPOIS EU VOU VOLTAR ESSE PARA CÁ, PORQUE EU POSSO MOVER O MENOR PARA O SEGUNDO, PARA QUE AGORA EU POSSA MOVER O MAIOR PARA O TERCEIRO.
ESS CASO AQUI JÁ ESTÁ FINALIZADO, NÉ? AGORA EU VOU FAZER QUAL MOVIMENTO? EU VOU PEGAR O MENOR E VOU JOGAR PARA O PRIMEIRO.
AGORA EU POSSO JOGAR O DISCO DO MEIO PARA O TERCEIRO E DEPOIS EU FINALIZO. OBSERVE QUE A GENTE FEZ ISSO COM QUANTOS PASSOS? SETE PASSOS.
E O NOSSO OBJETIVO, SÓ VOLTANDO PARA VOCÊS ENTENDEREM, EU QUERO SABER QUAL O NÚMERO DE PASSOS MÍNIMO PARA QUALQUER QUANTIDADE DE DISCOS. ENTÃO, VOCÊS PODEM, NO CASO, USAR ALGUNS ALGORITMOS PRONTOS, ALGORITMOS OU JOGOS PRONTOS. EU DEIXEI UM LINK, INCLUSIVE, DA UNIVESP, QUE JÁ TEM UM OBJETO DE APRENDIZAGEM QUE FAZ ISSO.
OK? E FINALIZANDO, ENTÃO, É IMPORTANTE QUE VOCÊS SAIBAM O SEGUINTE: QUE NÃO EXISTE UM ALGORITMO PARA CONSTRUIR ALGORITMOS, SENÃO SERIA MUITO FÁCIL, NÉ? A CRIAÇÃO DE ALGORITMOS É O EXERCÍCIO DE CRIATIVIDADE E EXPERIÊNCIA.
E, POR FIM, A CAPACIDADE DE SOLUCIONAR PROBLEMAS COMPLEXOS É UMA HABILIDADE MUITO IMPORTANTE PARA OS FUTUROS PROFISSIONAIS. ENTÃO, EU QUERO QUE VOCÊS ENTENDAM ISSO, QUE FIQUE CLARO QUE VOCÊS APRENDENDO A RESOLVER PROBLEMAS, COM CERTEZA VOCÊS SERÃO MELHORES PROFISSIONAIS, INDEPENDENTE DA ÁREA QUE VOCÊS VÃO TRABALHAR. OK?
ENTÃO, FINALIZO ESSE TEMA E ATÉ A PRÓXIMA AULA, PESSOAL!
