Els algorismes mandrosos

GoogleMaps.jpg Hi ha moltes maneres de resoldre problemes. Pensem per exemple en l’alimentació, un dels problemes bàsics dels éssers vius. Hi ha animals que ataquen i salten sobre les seves preses, mentre que alguns insectes com les formigues van recollint constantment el que troben. Els uns han d’esmerçar molta energia mentre que els altres són lents i segurs. Finalment és clar que tots se’n acaben sortint, perquè el què observem és que les espècies no s’han extingit. Però les seves estratègies són ben diferents, oi?

Pensem ara en un problema d’aritmètica. Suposem que volem calcular la suma de tots els nombres entre l’1 i el 2000. Si ho fem de la manera més directa, amb el “conte de la vella”, anirem sumant un a un els nombres i al cap d’una estona veurem que el resultat és 2.001.000, si no ens hem equivocat. Però hi ha maneres molt més eficients, per a resoldre aquest problema. Coneixeu l’anècdota de Carl Friedrich Gauss? Quan Gauss tenia set anys i era a l’escola, el mestre els va posar un problema semblant (però sumant només tots els nombres entre l’1 i el 100) per tal de tenir-los entretinguts una estona. Els seus companys van començar a fer sumes, però Gauss, al cap de pocs segons, va dir que ja ho tenia. Havia trobat el resultat correcte: 5050. Gauss només va haver de pensar una mica per a trobar un bon algorisme, una estratègia sàvia i intel·ligent. De fet, aquest dia a l’escola, als set anys, Gauss va descobrir l’algorisme òptim per a sumar progressions aritmètiques. La seva idea va ser senzilla i elegant. Mentalment, va agrupar els nombres en parelles. En el nostre cas, agruparíem l’1 amb el 2000, el 2 amb el 1999, el 3 amb el 1998, i així successivament. La clau de tot plegat és que totes les parelles sumen el mateix: 1+2000=2001, 2+1999=2001, 3+1998=2001 etc. Només cal fer una suma, la de l’1 amb el 2000, i veure que tenim 1000 parelles. Multipliquem 2001 per 1000 i ja tenim el resultat, que fins i tot podem calcular mentalment (en el cas dels 100 primers nombres, tindríem 50 parelles i cada parella sumaria 101).

Podem sumar tots els nombres entre l’1 i el 2000 fent dues mil sumes, però podem obtenir el mateix resultat fent només una suma i una multiplicació. També podem utilitzar un ordinador, per a que sigui ell qui faci les dues mil sumes. El primer algorisme és lent i una pèrdua de temps, mentre que el segon és savi i eficient. La tercera solució és ràpida, però mata mosques a canonades. És la solució “quick and dirty“, com diuen els anglesos. Arribem a la solució sense pensar gaire i utilitzant més recursos i energia del que cal. Malauradament, ens hi trobem massa sovint. S’utilitzen grans recursos informàtics per a resoldre problemes que, pensant una mica, es podrien resoldre de manera eficient en ordinadors petits i domèstics.

Donat qualsevol problema, el podem resoldre ràpidament, amb potència informàtica i sense pensar gaire, o bé utilitzant la nostra matèria gris per descobrir algorismes que el podran resoldre bé en màquines molt més petites i gastant molta menys energia. Són els algorismes savis i eficients, els que fan cas a allò que diuen que val més manya que força. Però en alguns casos, sobretot en aplicacions interactives en dispositius petits i mòbils, els millors són els algorismes que ho fan ben fet i sense presses. Són els algorismes mandrosos, que són savis, eficients i lents.

Podríem dir, tot exagerant, que els algorismes mandrosos segueixen aquella dita Siciliana que diu “no facis avui el que puguis deixar per demà”. No és ben cert perquè de fet fan tot el que poden; però el que no tenen temps de fer avui, això sí que ho deixen per l’endemà. Aquesta pàgina web en dóna algun exemple en aplicacions específiques.

Cada cop hi ha més dades, a Internet. Tenim mapes i imatges de satèl·lit de tot el món. És molta informació, és allò que ara se’n diu “Big data“. Des de fa pocs anys, tenim la possibilitat de “navegar-hi” des d’el nostre telèfon mòbil. El problema de la navegació interactiva no és trivial. Però gràcies a la persistència de les imatges en la nostra retina, podem reduir-lo a un problema molt més concret: el de generar un mínim de 30 imatges per segon. Tot i així, el problema continua essent molt complex perquè volem aconseguir la màxima qualitat visual en ordinadors molt petits i en telèfons mòbils. L’usuari, amb el moviment dels seus dits sobre la pantalla, demana anar a una certa zona, apropar-s’hi fent “zoom“, saltar a un altre lloc. L’aplicació, constantment ha d’improvisar. Ha de demanar la zona desitjada del mapa al servidor, l’ha de rebre per la xarxa i l’ha de pintar amb bona qualitat visual, tot en menys d’un trentè de segon. Cal un algorisme que podríem anomenar de tipus “entrepà” perquè les dificultats li venen tant de dalt com de baix. En un temps limitat (els seus “dies” són trentès de segon) ha de cercar, trobar i rebre el trosset de mapa que interessa dins una biblioteca digital gegant de mapes de tot el món, i l’ha de pintar el millor possible en una màquina de visualització molt petita. És fàcil veure que es tracta d’una variant del clàssic problema de la motxilla. En aquest problema suposem que tenim molts objectes, cada un d’ells amb un valor determinat, i volem omplir una motxilla de manera que al final la suma de valors dels objectes que hi hem posat sigui màxima, sense sobrepassar la capacitat total de la motxilla (en el nostre cas, la capacitat de la motxilla és el trentè de segon, i el valor és la qualitat visual que obtenim). El problema de la motxilla és un dels 21 problemes NP-complets de Richard Karp, impossibles de resoldre en temps raonable – fins i tot en grans ordinadors – i exposats en el seu article de 1972. En casos com aquest, sabem que cal pensar en solucions bones però aproximades. I una bona solució per a la visualització interactiva en telèfons mòbils són els algorismes mandrosos i golafres. La idea és pintar primer els trossets de mapa més interessants, mentre tinguem temps i no acabem el trentè de segon. Quan se’ns acaba el temps, deixem la resta per a més endavant.

És com pintar un quadre. El nostre telèfon, quan estem navegant i mirant mapes, pinta quadres. Pinta un quadre cada dia, en una escala de temps en la que els seus dies són trentès de segon per a nosaltres. Cada dia ens pinta el que li demanem, i ho fa començant pel més important per tal d’assegurar que el resultat final sigui el millor possible. I quan acaba la jornada, deixa la resta per l’endemà. Si l’endemà veu que continuem demanant el mateix, posa més detalls en el quadre que tenia a mitges i el millora. Si s’adona que hem canviat d’opinió, el deixa inacabat i comença a pintar un nou quadre, el quadre de la nova zona del mapa que hem decidit investigar. Cada dia comença per les parts més interessants, fa la feina que pot, i deixa pendent la resta.

Tot plegat té una certa relació amb el desig d’immediatesa. Sembla que avui en dia, tot ho hem de resoldre i aconseguir ràpidament. Però la física ens diu que la reacció immediata és infinitament cara i necessita moltíssima energia. És clar que en alguns cassos de risc cal actuar ràpid i esmerçar tota l’energia que calgui. Però l’habitual és poder esperar. En molts casos podem arribar a solucions acceptables amb algorismes savis i més lents, amb algorismes mandrosos. És el moviment “slow” aplicat als algorismes i a la resolució de problemes. És el que fan (i fem) tots els animals quan arriba la nit i hem de descansar perquè ja hem gastat massa energia. El que no hem pogut fer, ho deixem per l’endemà. Els éssers vius optimitzen l’energia. Els algorismes mandrosos, també.

Per cert, i si ens indignem contra les retallades en ciència, recerca, educació i sanitat?

1 comentari

  • Carme

    21/08/2013 10:32

    Tan interessant com sempre, Pere!
    Quan en faràs la recopilació en un llibre?
    Seria una molt amena aproximació al món científic, tan vilipendiat aquests dies. Una aproximació “mandrosa i slow” en el millor sentit, és a dir, atractiva i entenedora fins i tot per als mandrosos i slows ;-).

Comenta

*

(*) Camps obligatoris

L'enviament de comentaris implica l'acceptació de les normes d'ús