Pensamento Computacional Decomposição e recursão

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.(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