Elogi de l'algorisme: les matemàtiques del càlcul científic

Elogi de l’algorisme: les matemàtiques del càlcul científic

Elogi de l’algorisme: les matemàtiques del càlcul científic

Lliçó magistral llegida en el solemne acte

d’obertura del curs 2016-2017

Antonio Marquina Vila

2016

Aquesta publicació no pot ser reproduïda, ni totalment ni parcialment, ni enregistrada en, o transmesa per, un sistema de recuperació d’informació, en cap forma ni per cap mitjà, sia fotomecànic, fotoquímic, electrònic, per fotocòpia o per qualsevol altre, sense el permís previ de l’editorial.

© Del text: Antonio Marquina Vila 2016

© D’aquesta edició: Universitat de València, 2016

Maquetació: Publicacions de la Universitat de València

ISBN: 978-84-9134-028-7

Dedique aquesta lliçó a la memòria del meu molt admirat i benvolgut professor de matemàtiques del curs preuniversitari del Reial Col·legi de l’Escola Pia de València, Sr. Francisco Castaño Cerveró, que armat amb un tros de guix i una pissarra, va saber transmetre’m i regalar-me la seua passió per les matemàtiques, per la curiositat i pel descobriment.

Índex

PRÒLEG

L’ESPAI-TEMPS DELS ALGORISMES

LES EQUACIONS DIFERENCIALS I LES EQUACIONS MATRICIALS: LA MATEMÀTICA CONCRETA

LA IRRUPCIÓ DE LA NORMA L¹ EN LA CIÈNCIA DE LES DADES

EL CÀLCUL CIENTÍFIC EN EL DESCOBRIMENT DE LES ONES GRAVITATÒRIES

LA FACULTAT DE MATEMÀTIQUES DE LA UNIVERSITAT DE VALÈNCIA FA 50 ANYS

Excm. i Mgfc. Sr. Rector de la Universitat de València,

Excmes. i digníssimes autoritats,

companys i amics de la Universitat de València

PRÒLEG

Only those who will risk going too far can possibily find out how far one can go.

T. S. ELIOT

En aquesta lliçó he utilitzat en ocasions la primera i tercera persona del plural (nosaltres o ells, els matemàtics) per a expressar afirmacions i opinions en les quals no tots els matemàtics estarien d’acord, per això demane disculpes pel fet de prendre’m aquesta llicència retòrica. Els pronoms o substantius masculins emprats en aquesta lliçó no han d’interpretar-se amb una connotació de gènere.

L’objectiu d’aquesta exposició serà posar de manifest la intensa evolució que està tenint lloc en la recerca matemàtica del càlcul científic, per donar resposta als reptes del desenvolupament de moltes àrees de la ciència en general, la física, la química, la biologia i les enginyeries en particular, i les ciències de la informació especialment. No pretenem ser exhaustius ni cobrir totes les àrees de les matemàtiques del càlcul científic. En aquesta lliçó presentarem el càlcul científic des d’una perspectiva algorítmica i examinarem dues línies de recerca en les quals aquest autor ha tingut experiència investigadora durant un llarg període de temps, a saber: l’aproximació numèrica de les equacions diferencials en derivades parcials i el paper de la norma L¹ en la ciència de les dades.

L’ESPAI-TEMPS DELS ALGORISMES

Are you mathematically inclined? If math is all Greek to you, go to step 11, (i. e., you trust in me); otherwise go to step 10, (check formulas!)

DONALTH E. KNUTH (1938-)

The art of Computer Programming, vol. I

En el centre del càlcul científic resideix el concepte d’algorisme. Els matemàtics exigim tenir ben definits els conceptes que utilitzem. Un algorisme és una successió finita d’instruccions, dissenyades per a un propòsit específic, cadascuna d’aquestes eficientment realitzable en un temps finit per un dispositiu manual, mecànic o electrònic, i a més és capaç de llegir un volum de dades i escriure (i. e., produir) un volum de resultats. Així un algorisme és un ser virtual que és capaç de llegir i escriure amb determinades limitacions. Les limitacions estan associades a l’estructura i la grandària de les dades i a l’habilitat de produir els resultats en un temps útil per al propòsit per al qual va ser dissenyat.

Així un algorisme té els atributs següents:

1. Finitud: l’algorisme ha d’acabar sempre després d’un nombre finit de passos.

2. Definició: cada pas d’un algorisme ha de ser rigorosament precís i específicament no ambigu.

3. Entrades: l’algorisme té entrades que poden contenir zero o més dades (input).

4. Eixides: l’algorisme ha de retornar un o més resultats (output no buit).

5. Efectivitat: totes les operacions que cal executar han de ser suficientment bàsiques i realitzables en temps finit.

Els matemàtics han emprat l’abstracció com a eina essencial per al disseny d’algorismes. L’avantatge fonamental de l’abstracció és estalviar esforços. Solament des d’aquesta perspectiva s’entén la gegantesca contribució dels científics grecs a les matemàtiques, com és el cas d’Euclides. Els matemàtics grecs van posar ordre en la concepció dels nombres enters, van proporcionar una explicació clara i diferent de les propietats dels nombres primers, i van establir els primers algorismes associats a aquests. El primer requisit per a construir un bon algorisme és determinar el nivell d’abstracció necessari per a expressar una bona notació o formalisme amb el qual es puguen definir i relacionar els objectes i les estructures que els relacionen. Podríem afirmar que l’elaboració d’una bona notació és condició indispensable per a dissenyar un algorisme. Formalitza i venceràs. Però no és cert que la recerca en matemàtiques es reduïsca simplement a la notació o al formalisme, ja que, per exemple, el coneixement sobre la teoria de nombres per a dissenyar algorismes de descomposició en factors primers requereix una reflexió profunda sobre relacions que són més enllà del pur formalisme de la notació.

Els matemàtics podem analitzar les virtuts i les limitacions dels algorismes sense necessitat d’implementar-los en un codi numèric. Grosso modo els algorismes podem classificar-los en tres grans classes: els algorismes iteratius, els recursius i els directes. Els algorismes iteratius i recursius aconsegueixen un resultat després d’un nombre finit d’iteracions o crides al mateix algorisme en una quantitat que varia segons la grandària de les dades. Els algorismes directes aconsegueixen el seu objectiu després d’un nombre de passos independent de la grandària de les dades.

L’eficiència d’un algorisme és una característica essencial des del punt de vista pràctic. La mesura de l’eficiència d’un algorisme la tindrem definida com una funció del nombre de passos elementals del procés, en què més passos indica menys eficiència. Direm que l’eficiència és polinomial si aquesta funció és proporcional a una potència del nombre de passos, en què l’exponent és independent d’aquest nombre. La complexitat dels algorismes deterministes existents per a la descomposició en factors primers és superpolinòmica respecte al nombre de dígits del nombre que cal factoritzar, és a dir l’exponent depèn d’aquest nombre. Els algorismes amb una complexitat computacional molt alta, com els anteriorment esmentats, són de gran interès en criptografia. El codi RSA usat massivament per a l’encriptació en Internet es basa en la factorització de nombres semiprimers grans, i. e., productes d’exactament dos factors primers de grandària similar. Per exemple, RSA-500 indica que el codi d’encriptació es basa en la factorització d’un semiprimer de cinc-cents dígits que en els actuals computadors digitals pot portar mesos, anys o fins i tot segles.

D’altra banda, l’eficiència d’un algorisme es desitja alta per al possible ús en aplicacions quotidianes i amb resposta en temps real. El principi d’inducció és un dels axiomes bàsics de la teoria de conjunts i és una eina molt útil per a millorar l’eficiència dels algorismes.

Leonardo Fibonacci (1170-1250) va ser el matemàtic occidental més influent de l’edat mitjana. Gràcies al seu treball de comptable, va viatjar a ciutats d’Orient, va aprendre la notació indoaràbiga dels nombres, que va importar a la nostra cultura i va compendiar en la seua obra magna Liber Abaci. En aquesta obra s’examina una successió, actualment anomenada de Fibonacci, present en moltes observacions de la naturalesa. Aquesta successió està definida recursivament mitjançant la regla següent: cada terme d’aquesta successió és la suma dels dos anteriors. Aquesta successió és particularment interessant no sols perquè posseeix una quantitat innombrable d’aplicacions, sinó perquè planteja diversos problemes computacionals. Un problema computacional seria com calcular el terme enèsim de la successió de Fibonacci. Per a donar solució a problemes computacionals hem de fer-ho mitjançant algorismes eficients. Si desitgem calcular el terme enèsim de la successió de Fibonacci, iterant la fórmula, podem arribar a calcular aquest terme després de realitzar n sumes, per la qual cosa aquest algorisme tindria una complexitat lineal (polinomial de grau 1). Si desitgem calcular aquest terme cridant a la mateixa funció d’ordres inferiors mitjançant una estratègia recursiva es pot provar que aquest algorisme és exponencial (i. e., no polinòmic). No obstant això, aquesta no és tota la història. Si acudim a conceptes més avançats de les matemàtiques, com són els polinomis i les seues arrels, observem la mateixa definició de la successió, i podem classificar-la com una equació en diferències finites de segon ordre. Efectivament, ací podríem observar el germen discret del que posteriorment serien les equacions diferencials, la seua extensió natural al continu. En aquest punt, el problema computacional de Fibonacci podem resoldre’l mitjançant un algorisme del tipus que hem definit com a directe, ja que podem establir una fórmula tancada, el nombre d’operacions realitzables de la qual en un computador digital és finit i independent de la grandària del nombre que correspon a l’enèsim terme de Fibonacci. Per a això, observem l’equació, analitzem l’estructura de les seues solucions, i podem establir una fórmula explícita. Aquesta fórmula està donada en termes de les potències d’un nombre irracional (incommensurable!) com és la raó àuria d’un segment. Dos fets importants es deriven d’aquesta anàlisi. Primer, la solució tancada està connectada amb un problema de geometria mètrica clàssica i, segon, i més important, la fórmula inclou una operació no determinista, l’arredoniment. D’ací podem inferir que un ingredient no determinista pot millorar de manera substancial l’eficiència dels algorismes deterministes. Noteu que aquest algorisme directe no és tan avantatjós com sembla, ja que la seua precisió depèn del nombre de xifres decimals disponibles de la raó àuria.