Entrades amb l'etiqueta ‘algorismes mandrosos’

El gran i el petit: potència i eficiència

divendres, 6/04/2018

L’any passat vaig assistir a una conferència d’en Bruno Levy en el marc d’un congrés científic d’informàtica. La seva xerrada va començar amb una referència a un dels ordinadors que va contribuir a revolucionar la informàtica ara fa uns 30 anys: el mític Macintosh 128K, anomenat així pels seus 128 KBytes de memòria RAM, amb disquetera de 3 polsades i mitja (disquets de 400KB de capacitat que permetien guardar una única foto de baixa resolució de les d’ara), pantalla monocromàtica de 512 x 342 píxels i que ens oferia, per damunt de tot, un sistema operatiu i una interfície absolutament intuïtiva, basada en icones, finestres i ratolí, que ara encara utilitzem. El recordo molt bé, perquè em va acompanyar tot un any mentre preparava la memòria per a concursar a la universitat. Per tenir una idea del que era aquell Macintosh, només cal fer una divisió: la capacitat de la seva memòria era cent vint-i-vuit mil vegades més petita que la dels nostres mòbils actuals de 16 GB.

Doncs bé, en Bruno Levy explica que aquell Macintosh, que havia de carregar cada vegada el sistema operatiu a partir d’un disquet específic de sistema, quan el connectaves, tardava 20 segons en estar llest i preparat per a interactuar amb les persones. En canvi, comenta que el seu portàtil actual, un milió de vegades més potent pel que fa a potència de càlcul, tarda entre 2 i 3 minuts. Comenta que, els ordinadors actuals (per exemple de 3GHz i de tipus quadcore), en 20 segons poden fer un total de 240 mil milions d’instruccions, i es pregunta què està fent el seu portàtil durant aquests inacabables dos minuts o més. Acaba dient que, si qualsevol ordinador actual no pot completar en 20 segons tot el necessari per a estar a punt, és que segurament hi ha un problema en el disseny del software. Podria ser més categòric, però en Bruno és prudent.

Parlem una mica d’eines de diagnosi en medicina. Els sistemes anomenats d’imatge mèdica, els aparells de TAC (tomografia axial per computador) i de ressonància, acaben generant imatges molt precises del que hi ha dins nostre que cada cop es fan més imprescindibles per a la diagnosi. Els algorismes de reconstrucció 3D i de visualització de volum dels darrers anys ens ofereixen la possibilitat d’entrar virtualment dins el cos dels pacients per a que els experts mèdics puguin veure, entendre i acabar sabent què passa. Doncs bé, amb aquests algorismes passa el contrari del que explicava en Bruno Levy. Fins fa poc, les visualitzacions de volum requerien ordinadors força potents de sobretaula. Després, les hem pogut ja veure als portàtils. I ara, les comencem a tenir directament als telèfons mòbils. Ho podeu veure, per exemple, en aquest vídeo (que mostra els resultats d’aquest article científic) i que és d’on he tret la imatge de dalt. En aquest cas, per sort per a tothom, estem anant del gran al petit, de l’ordinador potent al dispositiu que portem a la butxaca. Un mòbil és un ordinador, però de potència clarament inferior a la dels ordinadors de sobretaula. Per això, aquestes aplicacions per a mòbil han de ser fortament sofisticades i eficients, perquè passar del petit a màquines més potents és molt més fàcil que passar d’ordinadors d’altes prestacions a dispositius limitats per la seva mida i pel consum energètic. Quin és el truc? La solució es basa, entre altres coses, en l’ús algorismes mandrosos.

Les noves eines mèdiques per a la diagnosi basada en la visualització de volum en mòbils són a la base de la telemedicina i dels mitjans que aquesta ens pot oferir en zones rurals i força aïllades, on viuen més de dos mil milions de persones al món. Perquè són eines que permetran que els metges rurals puguin comunicar-se amb equips mèdics dels hospitals, fent sessions clíniques a distància en les que uns i altres podran veure les mateixes imatges mèdiques dels pacients, analitzar-les i discutir-les conjuntament, tot arribant a entendre els possibles problemes per a fer finalment una bona diagnosi.

Tot ho tenim massa fàcil, i això facilita que acabem agafant mal hàbits. No cal que ens preocupem gaire si tenim grans mitjans i ordinadors potents. Però moltes de les solucions que ens calen per ajudar tothom i per intentar assolir els objectius de desenvolupament sostenible 2030 de la ONU passen per sistemes eficients que puguin funcionar en dispositius d’ús global: els telèfons mòbils.

——

Per cert, en Bru Rovira diu que els temes estrella que tenen a veure amb l’emigració i la inseguretat són els que van decantant la balança cap al client-votant de dretes, clients que diu que són els que estan guanyant per noquejada la guerra bruta de la democràcia.

Els algorismes mandrosos

dimecres, 14/08/2013

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?