Módulo 3 - Apresentação - Algoritmos e Programação II

Prévia do material em texto

<p>Algoritmos e Programação II</p><p>Prof. MSc. Samuel Benjoino Ferraz Aquino</p><p>Módulo 3 – Algoritmos recursivos</p><p>Unidade 1 - Recursividade e Algoritmos Recursivos</p><p>Roteiro</p><p>● Unidade 1: Recursão e Algoritmos Recursivos</p><p>● Unidade 2: Algoritmos de Busca</p><p>● Resumo</p><p>Introdução</p><p>● Programas desenvolvidos até o momento</p><p>○ Variáveis</p><p>○ Estruturas condicionais</p><p>○ Estruturas de repetição</p><p>○ Funções</p><p>Introdução</p><p>● Exemplo de criação e uso de funções</p><p>def funcao1(valor):</p><p>valor = valor + 1</p><p>valor = valor * 2</p><p>funcao2(valor)</p><p>def funcao2(valor):</p><p>valor = valor / 3</p><p>Introdução</p><p>● Em alguns problemas, é útil que uma função chame a si</p><p>mesma para resolver um problema!</p><p>● Parece estranho, mas fazemos isso na vida real!</p><p>Introdução</p><p>quarto_1 quarto_2</p><p>banheiro sala</p><p>casa</p><p>Introdução</p><p>arrumar(casa)</p><p>quarto_1 quarto_2</p><p>banheiro sala</p><p>casa</p><p>Introdução</p><p>arrumar(casa)</p><p>arrumar(quarto_1)</p><p>quarto_1 quarto_2</p><p>banheiro sala</p><p>casa</p><p>arrumar(quarto_2) arrumar(banheiro) arrumar(sala)</p><p>Recursividade</p><p>● Capacidade de uma função resolver um problema usando</p><p>chamadas da própria função</p><p>● Se encaixa bem para problemas com determinadas</p><p>características</p><p>● Simula um laço</p><p>Algoritmos Recursivos</p><p>● Passos para o desenvolvimento de uma função recursiva:</p><p>1 - Dividir um problema em problemas menores</p><p>2 - Resolver os problemas menores com a própria função</p><p>3 - Parar quando a solução for pequena o suficiente</p><p>● Passos para o desenvolvimento de uma</p><p>função recursiva:</p><p>1 - Dividir um problema em problemas</p><p>menores</p><p>Algoritmos Recursivos</p><p>quarto_1 quarto_2</p><p>banheiro sala</p><p>casa</p><p>● Passos para o desenvolvimento de uma</p><p>função recursiva:</p><p>2 - Resolver os problemas menores</p><p>com a própria função</p><p>Algoritmos Recursivos</p><p>quarto_1 quarto_2</p><p>banheiro sala</p><p>casa</p><p>arrumar(casa)</p><p>arrumar(quarto_1) arrumar(quarto_2) arrumar(banheiro) arrumar(sala)</p><p>● Passos para o desenvolvimento de uma</p><p>função recursiva:</p><p>3 - Parar quando a solução for pequena</p><p>o suficiente</p><p>Ex: vou parar a arrumação do quarto 1</p><p>quando a cama estiver pronta.</p><p>Algoritmos Recursivos</p><p>quarto_1 quarto_2</p><p>banheiro sala</p><p>casa</p><p>Algoritmos Recursivos</p><p>Dividir</p><p>(1)</p><p>Resolver</p><p>(2)</p><p>Parar</p><p>(3)</p><p>Algoritmos Recursivos</p><p>● Vantagem</p><p>○ Implementação “direta” para alguns problemas</p><p>● Desvantagem</p><p>○ Maior consumo de memória</p><p>● Recursão é indicada quando solução iterativa simples não é</p><p>possível</p><p>Unidade 2</p><p>Algoritmos de Busca</p><p>Módulo 3 – Algoritmos recursivos</p><p>Unidade 2 - Algoritmos de Busca</p><p>Algoritmos de Busca</p><p>● A busca de informação é uma das aplicações mais</p><p>importantes dos computadores</p><p>● Problema básico de busca: encontrar um valor x em um vetor</p><p>10 21 15 14 19 16 18 25</p><p>16x</p><p>?</p><p>Algoritmos de Busca</p><p>● Dois principais tipos de busca</p><p>○ Busca sequencial/linear</p><p>○ Busca binária</p><p>Algoritmos de Busca</p><p>● Busca sequencial</p><p>○ Estratégia mais básica</p><p>○ Procura o elemento em todas as posições</p><p>Algoritmos de Busca</p><p>● Busca sequencial</p><p>○ Estratégia mais básica</p><p>○ Procura o elemento em todas as posições</p><p>10 21 15 14 19 16 18 25</p><p>16x</p><p>?</p><p>Algoritmos de Busca</p><p>● Busca sequencial</p><p>○ Estratégia mais básica</p><p>○ Procura o elemento em todas as posições</p><p>10 21 15 14 19 16 18 25</p><p>16x</p><p>?</p><p>Algoritmos de Busca</p><p>● Busca sequencial</p><p>○ Estratégia mais básica</p><p>○ Procura o elemento em todas as posições</p><p>10 21 15 14 19 16 18 25</p><p>16x</p><p>?</p><p>Algoritmos de Busca</p><p>● Busca sequencial</p><p>○ Estratégia mais básica</p><p>○ Procura o elemento em todas as posições</p><p>10 21 15 14 19 16 18 25</p><p>16x</p><p>?</p><p>Algoritmos de Busca</p><p>● Busca sequencial</p><p>○ Estratégia mais básica</p><p>○ Procura o elemento em todas as posições</p><p>10 21 15 14 19 16 18 25</p><p>16x</p><p>?</p><p>Algoritmos de Busca</p><p>● Busca sequencial</p><p>○ Estratégia mais básica</p><p>○ Procura o elemento em todas as posições</p><p>10 21 15 14 19 16 18 25</p><p>16x</p><p>?</p><p>Algoritmos de Busca</p><p>● Busca sequencial</p><p>○ Estratégia mais básica</p><p>○ Procura o elemento em todas as posições</p><p>10 21 15 14 19 16 18 25</p><p>16x</p><p>?</p><p>Algoritmos de Busca</p><p>● Busca sequencial</p><p>○ Possui variações de implementação</p><p>○ Menos eficiente que a busca binária</p><p>10 21 15 14 19 16 18 25</p><p>16x</p><p>?</p><p>Algoritmos de Busca</p><p>● Busca binária</p><p>○ Assume uma ordenação prévia dos elementos</p><p>○ Mais eficiente que busca linear</p><p>Algoritmos de Busca</p><p>● Busca binária</p><p>○ Assume uma ordenação prévia dos elementos</p><p>○ Mais eficiente que busca linear</p><p>10 14 15 16 18 19 21 25</p><p>19x</p><p>?</p><p>Algoritmos de Busca</p><p>● Busca binária</p><p>○ Assume uma ordenação prévia dos elementos</p><p>○ Mais eficiente que busca linear</p><p>10 14 15 16 18 19 21 25</p><p>19x</p><p>?</p><p>Algoritmos de Busca</p><p>● Busca binária</p><p>○ Assume uma ordenação prévia dos elementos</p><p>○ Mais eficiente que busca linear</p><p>■ Apenas 2 comparações nesse caso!</p><p>10 14 15 16 18 19 21 25</p><p>19x</p><p>?</p><p>Algoritmos de Busca</p><p>● Busca binária</p><p>○ Vantagens:</p><p>■ Custo muito inferior à busca linear</p><p>■ Apropriada para conjuntos grandes</p><p>○ Desvantagens:</p><p>■ Precisa manter elementos ordenados</p><p>■ Recomendável para conjuntos com poucas alterações</p><p>Roteiro</p><p>● Unidade 1: Recursão e Algoritmos Recursivos</p><p>● Unidade 2: Algoritmos de Busca</p><p>● Resumo</p><p>Licenciamento</p><p>Respeitadas as formas de citação formal de autores de acordo com as normas da</p><p>ABNT NBR 6023 (2018), a não ser que esteja indicado de outra forma, todo material</p><p>desta apresentação está licenciado sob uma Licença Creative Commons -</p><p>Atribuição 4.0 Internacional.</p><p>https://creativecommons.org/licenses/by/4.0/</p><p>https://creativecommons.org/licenses/by/4.0/</p>