Baixe o app para aproveitar ainda mais
Prévia do material em texto
13/07/16 Departamento de Ciência da Computação Departamento de Ciência da Computação 1 DECOMPOSIÇÃO e RECURSÃO 13/07/16 Departamento de Ciência da Computação Departamento de Ciência da Computação 2 • Decomposição é quebrar um problema ou sistema em suas partes. • As vezes dividimos essas partes mais adiante. • Fazemos isso para resolver problemas complexos ou compreender sistemas complexos. DECOMPOSIÇÃO Fonte: https://barefootcas.org.uk/wp-content/uploads/2014/09/Decomposition-Concept-Barefoot-Computing.pdf 13/07/16 Departamento de Ciência da Computação Departamento de Ciência da Computação EXEMPLO DE DECOMPOSIÇÃO Duas pessoas poderiam fazer esse café da manhã ao mesmo tempo, um poderia fazer chá e um poderia fazer torradas 13/07/16 Departamento de Ciência da Computação Departamento de Ciência da Computação POR QUE A DECOMPOSIÇÃO É IMPORTANTE? • À medida que decompomos, aprendemos mais sobre o problema ou sistema. • Decompormos um problema, o torna mais gerenciável, pois podemos lidar com as partes separadamente e mais facilmente • É particularmente importante se estamos tentando entender as coisas que são complexas • As soluções criadas com a decomposição podem ser mais fáceis de compreender, testar, manter e mudar 13/07/16 Departamento de Ciência da Computação Departamento de Ciência da Computação Implementação da decomposição • Um código fica melhor estruturado quando ele é decomposto em várias funções e procedimentos • Estas funções e procedimentos são combinados no código para resolver o problema • Esta mesmas funções e procedimentos podem ser reusados em outros códigos • Facilita a manutenção do código 13/07/16 Departamento de Ciência da Computação 6 RECURSIVIDADE estamos de volta...de novo RECURSIVIDADE estamos de volta...de novo RECURSIVIDADE estamos de volta...de novo 13/07/16 Departamento de Ciência da Computação 13/07/16 Departamento de Ciência da Computação 13/07/16 Departamento de Ciência da Computação 13/07/16 Departamento de Ciência da Computação 13/07/16 Departamento de Ciência da Computação 13/07/16 Departamento de Ciência da Computação • N! = n.(n-1).(n-2).(n-3)...3.2.1 • Como é a definição recursiva? Fatorial 13/07/16 Departamento de Ciência da Computação • N! = n.(n-1).(n-2).(n-3)...3.2.1 • Definição recursiva Fat(n) = Fatorial 1, se n = 0 n.Fat(n-1), se n > 0 13/07/16 Departamento de Ciência da Computação Torres de Hanói 13/07/16 Departamento de Ciência da Computação Torres de Hanói Caso 1: problema com 1 disco A B C 13/07/16 Departamento de Ciência da Computação Torres de Hanói Caso 2: problema com 2 discos A B C 13/07/16 Departamento de Ciência da Computação Torres de Hanói Caso 3: problema com 3 discos A B C 13/07/16 Departamento de Ciência da Computação Torres de Hanói Caso n: problema com n discos A B C 13/07/16 Departamento de Ciência da Computação Torres de Hanói Caso n: problema com n discos A B C 13/07/16 Departamento de Ciência da Computação Departamento de Ciência da Computação Bibliografia Bibliografia Básica DOWNEY, Allen; ELKNER , Jeff; and MEYERS, Chris. How to Think Like a Computer Scientist: Learning with Python. (Aprenda Computação com Python 3.0, Versão em português). Green Tea Press. Wellesley, MA 2002. BELL, Tim; WITTEN, Ian H.; FELLOWS, Mike. Computer Science Unplugged: Ensinando Ciência da Computação sem o uso do computador. EUA: CSUnpluged, 2011. 13/07/16 Departamento de Ciência da Computação Departamento de Ciência da Computação Dúvidas 21
Compartilhar