Gólem i algorismes

Sovint es diu que els primers algorismes coneguts van ser les fórmules i els passos per resoldre-les que van deixar escrits els matemàtics babilonis. Altres exemples clàssics d’algorismes són el sedàs d'Erastòtenes, un grec del segle III aC  que permet trobar els nombres primers. El mateix mot algorisme prové del nom d'un àrab que es deia Abu Abdullah Muhammad bin Musa al-Khwarizmi  que va escriure uns compendis de "receptes" de com fer certs càlculs matemàtics. També es diu que la primera programadora va ser Ada Lovelace, ja que va deixar escrits certes instruccions per la màquina analítica de Babbage per calcular els nombres de Bernoulli. Es considera que ningú abans havia posat per escrit un seguit d'instruccions senzilles per ser seguides per una màquina complexa per aconseguir cert objectiu.

Hi ha, però, a parer meu un cas previ de programador, que molta gent no té en compte. I aquest és en Leib, el rabí de l'obra "El gólem" d'Isaac Bashevis. O, més ben dit, la seva dona. 

Un exemple d'algorisme en aquest cas podrien ser les ordres que i dona el rabí al seu gólem:
    "Porta’m aigua del riu"

L'errada que conté aquest algorisme, i que s'explica en el llibre, és que el gólem interpreta que ha de fer la instrucció rebuda fins que li diguin que s'aturi. En el cas del llibre, això provoca certs problemes i ens serveix per il·lustrar el que és un bon algorisme.

El que hauria d'haver dit el bon rabí seria:

    "Porta aigua del riu en un recipient fins que la tina estigui plena, llavors aturat"

Que en forma més formal d’expressar-ho podria ser així:

1. Vés al riu i omple la galleda 
2. Torna amb la galleda plena fins al dipòsit
3. Aboca l'aigua de la galleda al dipòsit
4. Si el dipòsit no està ple, torna al pas 1. Si està ple, has acabat.

Crèdit de la imatge: Philippe Semeria (www.philippe-semeria.com) [CC BY 3.0], via la Wikimedia Commons

Aquest algorisme és força millor que el primer: no farà que el gólem buidi el riu de la ciutat i provoqui la inundació de Praga, i sí que farà que el rabí tingui el dipòsit ple.

Pensar, dissenyar i implementar algorismes és la feina que fan els matemàtics, físics, informàtics, etc. i que els nostres ordinadors s'encarreguen d'executar. Com que les instruccions que pot seguir un ordinador són molt senzilles (de l'estil, guarda aquesta xifra a un cert lloc, suma'l amb la xifra guardada al lloc tal o compara aquest nombre amb aquest altre) els algorismes que en surten acostumen a ser força llargs i complexos. Hi ha tot un camp de la informàtica que està especialitzada en l'estudi d'aquests algorismes, classificar-los, estudiar-ne la complexitat (l'algorisme A és més ràpid d'acabar que l'algorisme B?, quanta memòria li cal a A? i a B?, l’algorisme és correcte?.).

Aquesta branca d'estudi, podríem dir que la van iniciar tres persones més o menys al mateix temps i més o menys per separat: Alan Turing, Alonzo Church i Kurt Godel. Cadascú va enfocar els seus estudis d'una forma diferent, arribant a les mateixes conclusions. Anem a veure una mica tot plegat:

• Turing va estudiar unes màquines imaginàries molt similars al que serien els ordinadors actuals i va estudiar les propietats d’aquestes màquines i va demostrar certes propietats dels algorismes.
• Church va desenvolupar un sistema similar a un llenguatge de programació per estudiar què són les funcions i el càlcul en general. 
• Godel va estudiar els algorismes sota l’òptica de la lògica formal 

Amb la feina de tots tres, es va poder iniciar l’estudi sistemàtic dels algorismes i conèixer quines limitacions tindrien els ordinadors. Cal remarcar que tota aquesta feina inicial es va fer abans de la segona guerra mundial, abans inclús que es fessin els primers ordinadors!

Turing es va imaginar una màquina que podia processar dades d’una forma força rudimentària i va analitzar què podia i què no podria fer. Aquesta màquina va resultar ser una idealització del que després serien els nostres ordinadors moderns. Aquest estudi es basa a comptar de forma genèrica quantes passes ha de fer la màquina per resoldre el problema.

Tornant a l’algorisme del gólem, el nombre de vegades que caldrà fer els passos és directament proporcional a la quantitat d’aigua que cap a la tina i la quantitat d’aigua que cap a la galleda que fa servir el gólem. Per tant, direm que l’algorisme és d’ordre n, que escrivim O(n). La n dependrà de la quantitat d’aigua que hem dit. Així, podem fer una taula per veure-ho:

Com a primera idea d’aquest estudi (no farem aquí un curs sobre el tema) podem introduir els problemes P i els NP. Els problemes P (de polinòmics) són els problemes que es poden resoldre amb un temps polinòmic.

Altres algorismes de classe P són els més senzills, com operacions matemàtiques amb matrius (O(n)), inserir o treure un element a una llista (O(1)), ordenar una llista alfabèticament (O(n^2) o  O(n log n)), etc.

Els algoritmes dins de la classe NP són més complexos i la seva complexitat acostuma a créixer molt ràpidament, tot i que comprovar que el resultat és correcte és un problema P. Per exemple, obtenir els factors primers d’un número qualsevol és un problema que es creu que és de tipus NP (no s’ha pogut demostrar que ho sigui, però no tenim cap algorisme P que ho faci). 

Altre exemple de problema de tipus NP és el de trobar el camí òptim per un transportista que ha de portar paquets a diferents llocs. Es coneix com el problema del viatjant de comerç i ja es va estudiar al segle XIX.

El problema amb aquest tipus d’algorismes doncs, és que el seu temps d’execució creix molt ràpidament segons augmenta la mida de la seva entrada. Així, és possible trobar els factors primers d’un nombre petit, però esdevé totalment impracticable intentar-ho amb un número força gran. De fet, la base última de la criptografia actual es basa en què, a la pràctica, no es pot factoritzar nombres molt grans (un ordinador actual tardaria milers d'anys en aconseguir-ho).

El mateix podem dir de l’algorisme del viatjant de comerç, potser es pot calcular la ruta per pocs punts de repartiment, però quan aquests passen a ser uns quants centenars el temps de calcular la millor ruta podria tardar milers d’any a calcular-se.

Tot i això, amb les millores en còmput en paral·lel i, sobretot, amb la propera aparició dels ordinadors quàntics tots aquests algorismes es podran executar de forma molt més ràpida i la classe NP serà, per fi, manejable pels nostres (futurs) ordinadors. Això però, és una altra història.

Per saber-ne més

• Complexitat computacional (viquipèdia)