BRUNO SILVA DE OLIVEIRAOrientador JOSÉ CARLOS MAGOSSI

UM ESTUDO SOBRE RECURSIVIDADE E SUAS APLICAÇÕES

Universidade Estadual de CampinasAnálise e Desenvolvimento de SistemasTrabalho de Conclusão de Curso - 2014

AGENDA

•INTRODUÇÃO

•JORNADA HISTÓRICO CONCEITUAL

•DEFINIÇÃO FORMAL

•APLICAÇÕES DA RECURSÃO

•FRACTAIS E A EXPLORAÇÃO DA RECURSIVIDADE

•CONCLUSÃO

2

Motivação3

Objetivos

Mostrar que a recursão está em todos os lugares

Mostrar possíveis equívocos que podemos cometer com a definição incompleta do tema

Responder a questão: Pra que serve recursão?

4

5

INTRODUÇÃO

AGENDA

•INTRODUÇÃO

•JORNADA HISTÓRICO CONCEITUAL

•DEFINIÇÃO FORMAL

•APLICAÇÕES DA RECURSÃO

•FRACTAIS E A EXPLORAÇÃO DA RECURSIVIDADE

•CONCLUSÃO

6

Surgimento7

X

Ouroboros 3000 a.C. [Pike, 1872] Panini 500 a.C. [Chomsky, 1957]

Infinito: Dedekind e Cantor

“[Teorema 126] Seja θ uma função de Ω em Ω, onde Ω é um conjunto qualquer, e seja w um elemento qualquer de Ω. Então, existe uma e só uma função ψ de N em Ω, onde N é um conjunto simplesmente infinito qualquer, tal que:

[1] ψ{1} = w;

[2] ψ{n’} = θψ;”

[Dedekind, 1969]

8

Decidibilidade: Skolem, Church, Turing

{D} Δ(a,b) see (∃x)(a=bx).

D(a,b,c), a qual expressa que a é igual ao produto de b por um número entre 1 e c

(fornecendo assim um elemento decisório):

Δ(a,b,1) see a=b;

Δ(a,b,c+1) see Δ(a,b,c) ou a = b(c+1)

{D’} Δ(a,b) see Δ(a,b,a),

[Biraben, 1994]

9

Complexidade: Kolmogorov e Ockham

A complexidade de Kolmogorov pode ser definidasimplificadamente como o tamanho do menorprograma (ou descrição algorítmica) que computa naMáquina de Turing uma determinada string binária.

"Se em tudo o mais forem idênticas as váriasexplicações de um fenômeno, a mais simples é amelhor".

10

AGENDA

•INTRODUÇÃO

•JORNADA HISTÓRICO CONCEITUAL

•DEFINIÇÃO FORMAL

•APLICAÇÕES DA RECURSÃO

•FRACTAIS E A EXPLORAÇÃO DA RECURSIVIDADE

•CONCLUSÃO

11

12

DEFINIÇÃO FORMAL

“Sometimes recursion seems to brush paradox very

closely. For example there are recursive definitions. Such

a definition may give the casual viewer the impression that

something is being defined in terms of itself. That would be

circular and lead to infinite regress, if not to paradox

proper. Actually a recursive definition never defines

something in terms of itself but always in terms of

simpler versions of itself.” – Hofstadter [1979]

Aritmética de Skolem (APR)

R (f, x, 0) = x

R(f, x, S(y)) = f(R(f, x, y), y)

A função f(x,y) = x+y, ficaria, na APR, da seguinte forma:

f(x,0) = x

f(x,y+1) = S(f(x,y))

13

Funções recursivas primitivas

Função constante-0 ξ: é a função ξ, de vários argumentos, dado por ξ:N->N, tal que ξ(2)=0; Há variações constantes diferentes de zero da função, como ξij(n1,...,ni)=j;

Funções de projeção π: seja k>=1 e 1<=i<=k, define-se a i-ésima função de projeção πjk, com k argumentos, como sendo uma função de Nk em N, tal que πjk (n1, n2, n3...nn)=nj, para qualquer njpertencente a N.

Função sucessor σ: é a função σ:N->N tal que σ(n)=n+1 para todo n ∈ N.

14

Funções recursivas primitivas

Regra de Composição: Seja g uma função com L argumentos e sejam h1, h2 ... hl, funções com k argumentos, tais que, para todo n ∈ Nk. Nessas condições, f(n) = g(h1n,....,hLn). Neste caso, f é dita obtida a partir de g, h1,...,hl por composição

Regra de Recursão Primitiva: Seja k>=0. Seja g uma função com k argumentos, e h uma função com k+2 argumentos, tal que, para todo n em Nk, f(n,0)=g(n), e para todo n em Nk e m em N, f(n,m+1)=h(n,m,f(n,m)).

15

Funções parciais16

div(x,y) = μ [f](x,y,m), onde

f(x,y,m) = σ(x) − (m * y + y)

div(5,2) = μ[σ(5) – (t*2 + 2)]

6 – (0*2 + 2) = 6 – 2 = 4

6 – (1*2 + 2) = 6 – 4 = 2

6 – (2*2 + 2) = 6 – 6 = 0

div(5,2) = 2

Didática em sala de aula

a. Solução trivial: Fib(0) = 1 e Fib(1) = 1

b. Solução geral: Fib(x) = Fib(x-1) + Fib(x-2)

c. Algoritmo de decisão:

d. Garantir que a função termine

17

Didática em sala de aula

a. Solução trivial: Fib(0) = 1 e Fib(1) = 1

Ideia de complexidade e Teorema de Dedekind

b. Solução geral: Fib(x) = Fib(x-1) + Fib(x-2)

Funções recursivas de Godel e APR

c. Algoritmo de decisão:

Ideia de decidibilidade

d. Garantir que a função termine

Ideia de infinito e ideias de Skolem

18

AGENDA

•INTRODUÇÃO

•JORNADA HISTÓRICO CONCEITUAL

•DEFINIÇÃO FORMAL

•APLICAÇÕES DA RECURSÃO

•FRACTAIS E A EXPLORAÇÃO DA RECURSIVIDADE

•CONCLUSÃO

19

Johaan Sebastian Bach20

J. S. Bach – Musical Offering Part 1

Rei Frederico II Thema Regium [Gainer, 2007]

Escher21

House of StairsReptile

Day and Night

Torre de Hanói22

Hanoi (n; posteInicial; posteAuxiliar; posteF inal)

Se n = 1 entao

MoveDisco(1; posteInicial; posteFinal)

senao

Hanoi(n - 1; posteInicial; posteFinal; posteAuxiliar)

MoveDisco(n; posteInicial; posteFinal)

Hanoi(n - 1; posteAuxiliar; posteInicial; posteFinal).

AGENDA

•INTRODUÇÃO

•JORNADA HISTÓRICO CONCEITUAL

•DEFINIÇÃO FORMAL

•APLICAÇÕES DA RECURSÃO

•FRACTAIS E A EXPLORAÇÃO DA RECURSIVIDADE

•CONCLUSÃO

23

Euclides24

Mandelbrot25

Conjunto de Mandelbrot -> Z = Z*Z + C26

Conjunto de Mandelbrot -> Z = Z*Z + C27

Auto-semelhança, escala e complexidade28

Auto-semelhança, escala e complexidade29

Dimensão30

N =64; r =1/4, D = 3

N = 2; r =1/3; D = 1,59

Camada D Área Fractal (%)

A não-fractal 3.3

B 1.52 16.5

C 1.72 42.5

D 1.89 70.2

31

AGENDA

•INTRODUÇÃO

•JORNADA HISTÓRICO CONCEITUAL

•DEFINIÇÃO FORMAL

•APLICAÇÕES DA RECURSÃO

•FRACTAIS E A EXPLORAÇÃO DA RECURSIVIDADE

•CONCLUSÃO

32

M O S T R A R Q U E A R E C U R S Ã O E S T Á E M T O D O S O S L U G A R E S

E S T Á N A A R T E : M Ú S I C A , A R T E S P L Á S T I C A S , L I T O G R A V U R A , C I N E M A , P O E M A S . . .

E S T Á N A M A T E M Á T I C A : A L G O R I T M O S R E C U R S I V O S , G E O M E T R I A , A R I T M É T I C A . . .

E S T Á N A V I D A D O S E R H U M A N O , N A N A T U R E Z A , N A S C U L T U R A S , N A L I N G U A G E M . . .

CONCLUSÃO33

M O S T R A R E Q U Í V O C O S Q U E P O D E M O C O R R E R C O M A C O N C E I T U A Ç Ã O I N C O M P L E T A D O T E M A

A S A U L A S P A S S A M U M M É T O D O C O R R E T O , M A S U M A D E F I N I Ç Ã O I N C O M P L E T A

O E N S I N O D E R E C U R S Ã O P O D E R I A S E R M E L H O R C O M P R E E N D I D O S E P O S T O E M U M C O N T E X T O H I S T Ó R I C O

CONCLUSÃO34

R E S P O N D E R À Q U E S T Ã O : P R A Q U E S E R V E R E C U R S Ã O ?

S E R V E P A R A C O M P R E E N D E R O S F E N Ô M E N O S C A Ó T I C O S , S I S T Ê M I C O S , D I N Â M I C O S , C O T I D I A N O S E T E C N O L Ó G I C O S

A P E S A R D E C L Á S S I C O , O C A M P O D A R E C U R S Ã O A I N D A P O S S U I D I V E R S A S P O N T A S S O L T A S E V Á R I A S O P O R T U N I D A D E S D E P E S Q U I S A C O M O O C A S O D E F R A C T A I S , I L U S T R A D O P E L O T A Y L O R E P O L L O C K

CONCLUSÃO35