Destacat »

21 juny 2018 – 12:00

La junta del Col·legi Oficial d’Enginyeria en Informàtica de Catalunya ha aprovat la creació de la comissió Dones-COEINF amb l’objectiu de fer el seguiment de l’escletxa de gènere a l’enginyeria informàtica.

Read the full story »
Col·legi

el Col·legi, informació rellevant sobre el COEINF, activitats, relacions i varis

Formació

formació continuada i orientació professional, convenis de formació amb altres entitats

Esdeveniments

tots els esdeveniments rellevants del sector TIC

Informes

informes, estudis, enquestes, … relacionats amb les tecnologies de la informació

Professió

món laboral, emprenedors, enginyers en informàtica, entrevistes, certificacions, deontologia, carreres professionals, …

Home » Notícies

Guardó per al matemàtic que es va rendir davant els ordinadors

Submitted by on 14 gener 2016 – 17:00No Comment
Share Button

Stephen Cook guanya el Premi Fronteres del Coneixement de Tecnologies de la Informació

Alan Turing va descriure per primera vegada en 1936 el concepte de computabilitat i va detallar quins problemes pot resoldre o no un ordinador. A aquesta idea, el matemàtic Stephen Cook (Nova York, 1939) va afegir l’eficiència: saber si un problema es pot resoldre en un temps assumible -i el temps és la clau- és essencial per decidir si val la pena insistir en solucionar-ho o resignar- i buscar una conclusió aproximada. Amb aquesta idea, el matemàtic ha guanyat el Premi Fronteres del Coneixement de Tecnologies de la Informació, atorgat per la Fundació BBVA.

Cook

Stephen Cook ha aconseguit el guardó per determinar que hi ha problemes que els ordinadors no poden resoldre de manera eficient. “En aquest cas, el més intel·ligent és deixar de intentar-ho. Això permet als programadors assajar estratègies molt més útils”, explica Cook.

En concret, el matemàtic va dividir els problemes en dues categories: els que poden ser resolts en un temps raonable, als quals va cridar P, i aquells que implicarien tant de temps que “el sol s’apagaria abans”, als quals va anomenar NP.

Per a aquests últims va definir una subclasse: els problemes NP-complets. En aquesta categoria hi ha els enigmes més difícils que, a més, són equivalents, és a dir, que si es trobés una solució per a un d’ells, significaria que hi ha una solució per a tots els altres.

Actualment, hi ha milers de problemes NP-complets en àmbits molt diversos: biologia, física, economia, teoria de nombres, lògica … Un exemple és la forma en què les proteïnes adquireixen la seva estructura tridimensional, un problema essencial en biologia. Un altre és el famós enigma del viatjant: trobar la ruta més eficient que ha de seguir un repartidor per arribar a tots els destinataris.

Stephen Cook planteja amb aquesta investigació un dels grans Problemes del Mil·lenni, els principals enigmes sense resoldre de les matemàtiques la solució està recompensada amb un milió de dòlars: hi ha una solució eficient per als problemes NP-complets?

Els 45 anys d’esforços combinats d’informàtics i matemàtics no han servit per a trobar la solució. La immensa majoria dels experts creu que no hi ha un algoritme que resolgui els problemes NP. El Problema del Mil·lenni que va plantejar Cook es diu P versus NP, és a dir, enigmes que tenen solució contra els que no la tenen.

Per exemple, en la qüestió del viatjant, l’única manera de trobar la ruta més ràpida per visitar a tots els comerciants és calcular totes les trajectòries possibles: cal fer tants càlculs que, en la pràctica, és irresoluble. El Problema del Mil·lenni plantejat per Cook es pregunta si de debò no hi ha cap manera més ràpida, cap drecera brillant, que permeti resoldre aquests problemes NP-complets.

Si algú descobrís la fórmula màgica que solucionés un enigma NP-complet, podria solucionar tots. Això comprometria, per exemple, els sistemes de xifrat i la seguretat dels bancs i Internet, on s’utilitzen problemes NP-complets -que fins ara no es poden resoldre- per mantenir les claus i les rutes d’accés sota màxima seguretat.

Stephen Cook és catedràtic de Ciències de la Computació a la Universitat de Toronto (Canadà). Va publicar el seu estudi més influent en 1971, en què analitzava i intentava resoldre un problema NP qualsevol. En aquest moment no era conscient de quants enigmes d’aquest tipus existien. Només un any després, un altre investigador va publicar una llista amb 300 problemes NP més. El matemàtic sabia que el concepte amb el qual estava treballant era interessant, “però no tenia ni idea que seria tan important”, explica Cook.

Font: El País

Etiquetes: ,

Aquesta web utilitza 'cookies' pròpies i de tercers per oferir-te una millor experiència i servei. Al navegar o utilitzar els nostres serveis, acceptes l'ús que fem de les 'cookies'. De tota manera, pots canviar la configuració de 'cookies' en qualsevol moment ACEPTAR
Aviso de cookies
Check Our FeedVisit Us On LinkedinVisit Us On TwitterVisit Us On Facebook