Page 39 - Telebrasil - Maio/Junho 1986

paralelo (p ro cessa d o res C r a y ), q u e , s e ­ m u l t i f u n c i o n a i s ; p e r m a n ê n c i a d o s

gundo J.P. Jacob , t a m b é m a p r e s e n t a m g r a n d e s c o m p u ta d o re s; e e x p a n s ã o d a s

suas im ita çõ es ta is co m o p r o b le m a s d e e s ta ç õ e s d e tra b a lh o .
l

r o t e a m e n to ; d e e n t r a d a e s a í d a ; d e A p rop ósito d e e s t a ç õ e s d e tr a b a lh o ,

gerenciam ento d e m e m ó r ia s d e m u i t a e e x p l i c o u a i n d a J . P . J a c o b q u e e s t a s

j
alta c a p a c id a d e ; e d e r e c o n v e r s ã o do o p era m co m a n e l a s q u e d e v e m s im u la r

software e x is t e n t e ( e s t im a d o e m 1 t r i­ r a p id a m e n te a a p lic a ç ã o q u e o u s u á r io

f
lhão de dólares) q u e o r a m p r o g r a m a d o s d eseja, o q u e r e q u e r p od er c o m p u t a c io ­

s
para iste m a s d e V o n N e u m a n . nal s u f i c i e n t e p a r a m o d ific a r 3 M b it s

s
s
c
A eguir, o o n fe r e n c is ta d e s t a c o u a s em 1 e g u n d o , e n ã o d e v e m s e r co n fu d i-
tendências m a is c o r r e n te s d a in d ú s t r ia d a s com m u ltip r o c e s s a m e n to .

de nform ática, q u e fo ra m a s s e g u in t e s : F in a l m e n t e , d e s t a c o u co m o u m d o s
i

explosão do m erca d o d e s i s t e m a s e s p e ­ m a io r e s p r o b le m a s da in d ú s tr ia d e in ­
Memória estática de acesso aleatório, com

cia lista s ( m a is d e 2 0 0 e m p r e s a s ) ; a u ­ três nano-segundos de velocidade. liste chip f o r m á t ic a o d e s e n v o l v i m e n t o d o s o ft­

mento das redes in t e r lig a n d o m a in tra ­ experimental de 32k está cercado degráos de ware, n a s u a o p in iã o , u m d a sa fio m u n ­

mes com m icros e p eriférico s; e r m i n a i s sal de mesa para efeito de perspectiva. dial.
t

Problemas que o computador não resolve

Ronald G r a h a m , 4 6 , d o u to r e m m a t e ­ " M a s s e é i m p o r t a n t e p r o v a r q u e d em d e in d a g a ç õ e s p e s q u is a d a s por

l
mática dos a b o r a tó r io s d e p e s q u is a s da u m a s o lu ç ã o n ã o e x is t e , é ig u a lm e n t e R on ald G rah am :

i
s
Bell, se d is tin g u e n ã o só p or s e u s t ítu lo s im p o r ta n te a b e r q u e p r o b le m a s i m i l a ­ S e r á q u e n ú m e r o s d ê n tic o s, a t é a
s
(ganhou e m 6 3 o p r ê m io P o ly a , c o n d e ­ res a m b é m n & otèm so lu çã o e p r in c ip a l­ q u a d r a g é s im a ca sa d e c im a l, p o d e m ser
t

coração m á x im a n a á r e a d e a n á l i s e c o m ­ m e n t e q u a l é a d ife r e n ç a m ín im a q u e c o n sid e r a d o s ig u a is ou isto a c u m u la r á

binatória), m a s t a m b é m por s e u s t aba- p o d e s e r a l c a n ç a d a e n t r e a s o l u ç ã o na m e m ó r ia dos c o m p u ta d o r e s e r r o s in-
r

lhos eferen tes a p r o b le m a s e n v o lv e n d o e x a ta e a a p r o x im a d a ”, a firm o u o c ie n ­ d e se já v c is o q u e p oderão ser a t é m e s m o
r
f
números e x t r e m a m e n t e g r a n d e s . tista . p erig o so s para o u tu ro da h u m a n id a d e ?

D u r a n te r e c e n t e v i s i t a q u e fe z a o S o b r e p r o g r a m a ç ã o lin e a r , e m p r e ­

Brasil, ele e x p lic o u q u e o p e ss o a l d e i n ­ g a d a p or e x e m p l o p a r a p r o b le m a s de

form ática, h o je, d i s c u t e o i m p a c t o d e m i n i m i z a ç ã o d e c u s t o s , G r a h a m é de Qual a menor rede telefónica?

grandezas, cuja m a g n i t u d e é t a m a n h a o p in iã o q u e o m éto d o S im p le x (D a n tz ig

que m pede q u e m á q u i n a s p o s s a m s o l u ­ 1947) é p rático, m a s n ão é u n iv e r sa l, e
i

cioná-las. U m d e s s e s p r o b le m a s é o d a cito u o a lg o r itm o e lip so id a l d e K h a c ia n
4 pontos

"árvore de r a m if ic a ç õ e s m in i m a s ” q u e e S h o r "que n ã o é p r á tic o ” e o de Kar- comprimento total

t
se d e s tin a a i n t e r l i g a r p o n t o s q u a i s ­ m a r k a is q u e "é m u ito b o m ”, en d o g a ­ dos segmentos - 3

quer, com u m m ín im o d e c o m p r im e n t o n h o o p rê m io d e S o c ie d a d e d e P e sq u is a

total. E a situ a ç ã o q u e o s p r o j e t is t a s d e O p era cio n a l.
4 pontos

e
l
rede n con tram p a ra o c a liz a r u m a c e n ­ A s e g u ir , e le falou dos n ú m e r o s pri­ comprimento total
tral te lefô n ic a e q u e foi e s t u d a d a p elo m o s, d izen d o q u e foi r e c e n te m e n te d e s ­ dos segmentos 2V 7 2,8

su íço J a c o b S t e i n e r ( 1 7 9 6 - 1 8 6 3 ) . O cob erto, a t r a v é s de u m te s te d e c o m p u ­

t
mesmo p rob lem a foi p o s t e r io r m e n t e g e ­ ta d o r d e g r a n d e porte do ipo C ray, q u e o
4 p o n t o s
t
(
neralizado por C a y le y , q u e p ro v o u e x i s ­ n ú m e r o 2 13* ' ') — 1 é prim o. E sse ipo de c o m p r i m e n t o to t a l
i
s
u
i
tir ma q u a n tid a d e n f in it a d e p o s s ib ili­ p r o b le m a e o u tro s correlatos ã o m p o r­ d o s s e g m e n t o s 1 + \f5 2,1
c
dades de solu ção. t a n t e s p a ra d e s e n v o lv e r m éto d o s rip to­
— Ao se t e n t a r r e s o lv e r u m p r o b le ­ g rá fico s, com o o e s q u e m a RSI, do In sti­ A terceira solução dá o menor caminho

ma é sa b e r se e l e p o s s u i u m a s o lu ç ã o tu to d e T e c n o lo g ia de M a s s a c h u s s e ts — total da interligação e envolve dois

m atem ática fin a l. C a s o n ã o t e n h a , d e ­ M IT. pontos de Steiner.

ve-se p e r g u n ta r e n t ã o s e u m a s o lu ç ã o E m r e la ç ã o a g r a n d e s n ú m e r o s —

ap roxim ad a ( h e u r í s t i c a ) s e r á s a t i s f a ­ u m a e s p e c ia lid a d e do c ie n tis ta da B ell

t
s
tória ou e o p r o b le m a p o d e s e r r e s tr ito a — e le a p r e s e n to u u m n ovo ipo de n o ta ­ O c ie n tis ta p rev ê q u e d e n tr e d e 2 a 3

s
uma olução p a r tic u la r . E x i s t e m m i l h a ­ ção p a ra a e x p o n e n c ia ç á o n u m é r ic a , em a n o s d e v e m s u r g ir n o v a s d e s c o b e r t a s

res de p r o b le m a s q u e s ã o d o t ip o N P q u e a t n = a n. D ep o is e le m ostrou que r e v o lu c io n á r ia s e m re la ç ã o a o s p ro b le­

(
e
complexo, sto é, r e c a e m e m s o lu ç ã o d e aft n e q u iv a le a a le v a d o ao e x p o e n te a, m a s N P ) d e p o lin ó m io s n ã o d e t e r m in ís ­
i
Polinóm ios N ã o D e t e r m in ís t ic o s — e x ­ por s u a v e z e le v a d o ao e x p o e n te a e a s ­ ticos co m p lex o s. S u a m e n s a g e m final:

plicou A rn a ld G r a h a m . s im s u c e s s iv a m e n t e n v e z e s c o n se c u ti­ — O s p r o b l e m a s d a c l a s s e N P s ã o

I n f e l i z m e n t e , t o d o s o s a l g o r i t m o s v a s. F in a lm e n t e , in d icou q u e a n otação q u a se im p o s s ív e is d e r e so lv e r , m e s m o s

j
d e s tin a d o s a r e s o l v e r p r o b l e m a s N P at t t tn á nos coloca n o u tro m u n d o , e m com p o d e r o síssim o s c o m p u ta d o r e s, p o is

com plexos, l e v a m u m t e m p o e x p o n e n ­ te r m o s d e q u a n tid a d e , a lg o q u e c o m p u ­ a o c r e s c e r e m o s i t e n s d a q u e s t ã o e m

cial p ara s e r e m s o l u c i o n a d o s . M e s m o ta d o r e s d if ic ilm e n t e p od erão alcan çar, apreço, a s so lu ç õ e s ó tim a s r a p id a m e n t e

com um c o m p u ta d o r q u e fa ç a 1 m ilh ã o n a p rá tica . s e t o r n a m e m r e s o lu ç ã o e x p o n e n c i a l.

t
de operações por s e g u n d o , s e r ã o n e c e s ­ M a s n ã o é a p e n a s e s s e ip o de p ro b le­ U m e x e m p lo p rático: n u n c a s e s a b e r á

sários sé cu lo s p a ra r e s o lv e r c e r to s p r o ­ m a q u e p r e o c u p a m a s c iê n c ia s q u e li­ p r o j e t a r c o m s e g u r a n ç a " u m c h i p

i
blemas. D ev id o a isto r e c o r r e -se ao u so d a m c o m g r a n d e s n ú m e r o s , t a is co m o ó tim o ”, pois a s p o ss ib ilid a d e s de n t e r li­

s
t
das so lu çõ es q u a s e ó t i m a s q u e , n o e n ­ p a r a c á lc u lo s d e p r e v isã o m eteo ro ló g ico g a ç õ e s ã o a n ta s , q u e se recai n u m tipo
tanto, c o stu m a m d ife rir b a s t a n t e e n t r e ou p a ra o r e c o n h e c im e n to de c o n fig u r a ­ d e p r o b le m a N P , q u e co m o v im o s n ã o

si. ç õ e s por robôs. A se g u ir , u m a o u tr a or- te m so lu ç ã o glob al.