Amb quina rapidesa milloren els algorismes? | Notícies del MIT


Els algorismes són com els pares d’un ordinador. Expliquen a l’ordinador com donar sentit a la informació perquè, al seu torn, puguin fer-ne alguna cosa útil.

Com més eficient sigui l’algorisme, menys feina ha de fer l’ordinador. Malgrat tot el progrés tecnològic en el maquinari informàtic i la durada de la vida molt debatuda de la Llei de Moore, el rendiment de l’ordinador és només una cara de la imatge.

Entre bastidors s’està produint una segona tendència: els algorismes s’estan millorant, de manera que al seu torn es necessita menys potència de càlcul. Tot i que l’eficiència algorítmica pot tenir menys protagonisme, sens dubte notareu si el vostre motor de cerca de confiança es va convertir de sobte en una desena part més ràpid, o si moureu-vos per grans conjunts de dades semblava passar pel fang.

Això va fer que els científics del Laboratori d’Informàtica i Intel·ligència Artificial (CSAIL) del MIT es preguntessin: Amb quina rapidesa milloren els algorismes?

Les dades existents sobre aquesta qüestió eren en gran part anecdòtiques, i consistien en estudis de cas d’algorismes particulars que es suposava que eren representatius de l’abast més ampli. Davant d’aquesta manca d’evidències, l’equip va començar a analitzar les dades de 57 llibres de text i més de 1.110 articles de recerca, per rastrejar la història de quan els algorismes van millorar. Alguns dels treballs d’investigació van informar directament de la bona qualitat dels algorismes nous, i d’altres van haver de ser reconstruïts pels autors mitjançant “pseudocodi”, versions abreujades de l’algorisme que descriuen els detalls bàsics.

En total, l’equip va analitzar 113 “famílies d’algoritmes”, conjunts d’algoritmes que resolien el mateix problema que s’havia destacat com a més important pels llibres de text d’informàtica. Per a cadascun dels 113, l’equip va reconstruir la seva història, fent un seguiment cada vegada que es proposava un nou algorisme per al problema i fent especial nota dels que eren més eficients. Amb un rendiment variat i separats per dècades, des dels anys quaranta fins ara, l’equip va trobar una mitjana de vuit algorismes per família, dels quals un parell va millorar la seva eficiència. Per compartir aquesta base de dades de coneixement reunida, l’equip també va crear Algorithm-Wiki.org.

Els científics van traçar la rapidesa amb què havien millorat aquestes famílies, centrant-se en la característica més analitzada dels algorismes: la rapidesa amb què podrien garantir la resolució del problema (en ordinador: “complexitat temporal en el pitjor dels casos”). El que va sorgir va ser una enorme variabilitat, però també una visió important sobre com ha estat la millora algorítmica transformadora per a la informàtica.

Per a grans problemes informàtics, el 43 per cent de les famílies d’algoritmes tenien millores interanuals iguals o superiors als guanys tan proclamats de la Llei de Moore. En el 14 per cent dels problemes, la millora del rendiment dels algorismes en gran mesura superat els que provenen de maquinari millorat. Els guanys de la millora de l’algoritme van ser especialment importants per als problemes de grans dades, de manera que la importància d’aquests avenços ha crescut en les últimes dècades.

El canvi més gran que van observar els autors es va produir quan una família d’algoritmes va passar de la complexitat exponencial a la polinomial. La quantitat d’esforç que es necessita per resoldre un problema exponencial és com una persona que intenta endevinar una combinació en un pany. Si només teniu un únic marcatge de 10 dígits, la tasca és fàcil. Amb quatre dials com un pany de bicicleta, és prou difícil que ningú et robi la bicicleta, però encara és concebible que puguis provar totes les combinacions. Amb 50, és gairebé impossible: caldrien massa passos. Els problemes que tenen una complexitat exponencial són com els dels ordinadors: a mesura que es fan grans, superen ràpidament la capacitat de l’ordinador per gestionar-los. Trobar un algorisme polinomial sovint soluciona això, fent possible abordar els problemes d’una manera que cap millora del maquinari pot.

A mesura que els rumors de la Llei de Moore que s’acaben ràpidament impregnen les converses globals, els investigadors diuen que els usuaris d’informàtica hauran de recórrer cada cop més a àrees com els algorismes per millorar el rendiment. L’equip diu que les troballes confirmen que històricament, els guanys dels algorismes han estat enormes, de manera que el potencial hi és. Però si els guanys provenen d’algoritmes en lloc de maquinari, tindran un aspecte diferent. La millora del maquinari a partir de la llei de Moore es fa sense problemes amb el pas del temps, i per als algorismes els guanys es produeixen en passos que solen ser grans però poc freqüents.

“Aquest és el primer article que mostra la rapidesa amb què milloren els algorismes en una àmplia gamma d’exemples”, diu Neil Thompson, científic investigador del MIT a CSAIL i a la Sloan School of Management i autor principal de el nou paper. “A través de la nostra anàlisi, vam poder dir quantes tasques més es podrien fer amb la mateixa quantitat de potència de càlcul després que un algorisme millorés. A mesura que els problemes augmenten a milers de milions o bilions de punts de dades, la millora algorítmica esdevé substancialment més important que la millora del maquinari. En una època en què la petjada ambiental de la informàtica és cada cop més preocupant, aquesta és una manera de millorar les empreses i altres organitzacions sense els inconvenients”.

Thompson va escriure el document juntament amb l’estudiant visitant del MIT Yash Sherry. El document es publica a la Actes de l’IEEE. El treball va ser finançat per la fundació Tides i la Iniciativa del MIT sobre l’economia digital.