Algoritme

Exemple d'un algoritme que permet de trobar lo pus pichon divisor comun de dos nombres.

Un algoritme es un ensemble finit d'operacions e d'instruccions definidas que permèton de resòuvre un problema. Lo tèrme ven de la latinizacion dau nom dau matematician arabi Al-Khwarizmi. Per aquò, un algoritme tracta de donadas d'intrada e provesís, s'es possible, de donadas de sortida. Ocupan una plaça importanta dins la societat modèrna car tènon un ròtle fondamentau dins lo foncionament deis ordinators, dei logiciaus o dei tecnicas de criptografia.

L'algoritmica es la disciplina qu'estúdia leis algoritmes.

Istòria

Tauleta babiloniana presentant un problema algoritmic.

Carta traucada utilizada per introdurre lei premiereis instruccions algoritmicas dins una maquina.

Leis algoritmes pus vièlhs que son coneguts a l'ora d'ara foguèron redigits per lei matematicians babilonians de l'Antiquitat. Depintavan de metòdes de calcul e de resolucion d'eqüacions. Puei, d'exemples d'algoritmes son estats identificats dins mai d'una region, especialament en Grècia amb l'algoritme d'Euclidi que permet de trobar lo pus grand divisor comun de dos nombres.

Lo matematician arabi Al-Khwarizmi (v. 780-850) foguèt lo premier qu'estudièt l'usatge sistematic deis algoritmes dins son tractat intitulat Abreujat dau calcul per la restauracion e la comparason. Dins lo quadre d'un estudi de la resolucion deis eqüacions quadraticas, prepausèt de metòdes de resolucion basadas sus una succession d'operacions simplas. Puei, au sègle XII, Averroès (1126-1198) afinèt lo trabalh de son predecessor. Son òbra se difusèt en Euròpa onte lo tèrme « algoritme » apareguèt a la meteissa epòca.

Au sègle XVII, dins son Discors dau metòde publicat en 1637, lo sabent francés René Descartes (1596-1650) comencèt d'introdurre l'usatge de la logica dins l'estudi deis algoritmes. Durant lei sègles seguents, apareguèron pauc a pauc lei nocions de bloca, d'iteracion o de dicotomia. En 1843, aquò menèt au desvolopament dau premier programa escrich sota forma d'algoritme per Ada Lovelace (1815-1852).

Au sègle XX, l'algoritmica venguèt una disciplina importanta amb lo desvolopament dei tecnologias de l'informacion e dei maquinas de Turing. D'efiech, aquelei sistèmas, a l'origina deis ordinators modèrnes, necessitan d'instruccions simplas per foncionar corrèctament. Leis algoritmes son ansin venguts lo supòrt dau desvolopament deis otís de l'informatica coma lei logiciaus. Trobèron tanben d'aplicacions importantas dins d'autrei sectors coma la criptografia, lo partiment d'informacions, lo tractament d'imatges e lo tractament de tèxtes.

Definicion generala

Un algoritme es un metòde generau per resòuvre un tipe de problemas. Es dich corrèct quand, per cada instància dau problema, s'acaba per la produccion de la bòna sortida (es a dire que permet de resòuvre lo problema considerat). Dins aqueu quadre, l'eficacitat de l'algoritme es mesurada per la durada dau calcul, la consumacion de memòria viva, la precision dei resultats obtenguts e son escabilitat. D'efiech, leis ordinators qu'executan leis algoritmes son pas infinidament rapids car, en despiech de l'aumentacion regulara dei performàncias deis ordinators, lo temps maquina demòra una ressorsa limitada. L'analisi de la complexitat d'un algoritme permet de preveire l'evolucion dau temps de calcul necessari per menar l'algoritme fins a sa fin en foncion de la quantitat de donadas de tractar.

De definicions pus tecnicas existisson. Permèton de descriure d'un biais pus reduch l'algoritme eu meteis. Segon lo matemacian estatsunidenc Donald Knuth, un algoritme es caracterizat per cinc proprietats :

• la finitud : un algoritme dèu s'acabar après un nombre finit d'etapas.
• la precision de sa definicion : cada etapa d'un algoritme dèu èsser definida d'un biais precís sensa ambigüitat.
• lei donadas d'intrada : un algoritme tracta un ensemble d'objèctes.
• lei donadas de sortida : un algoritme, se fonciona, produtz un ensemble d'objèctes aguent una relacion especifica amb lei donadas d'intrada.
• lo rendiment : totei leis operacions realizadas per un algoritme son pron simplas per èsser menadas en una durada finida per un èsser uman.

Segon l'informatician francés Gérard Berry, una autre definicion possibla es de considerar un algoritme coma un biais de descriure, amb un maximom de detalhs, un procès permetent de realizar un pretzfach per permetre son execucion per una maquina numerica.

Concèptes

Generalitats

La logica formala a un ròtle important dins la redaccion e lo foncionament d'un algoritme. D'efiech, avans d'escriure una lista d'instruccions, es necessari de determinar la realitat de l'existéncia de l'algoritme cercat (calculabilitat e decidabilitat) e d'estudiar la durada de calcul dau processor (uman, mecanica...) necessària per produrre un resultat. Aquò permet de determinar la complexitat algoritmica d'un problema. L'interès d'aquela identificacion es d'establir la portada de l'algoritme car un algoritme capable de resòuvre un problema es capable de resòuvre totei lei problemas de la meteissa classa.

La decidibilitat e la calculabilitat

Lei nocions de la decidabilitat e la calculabilitat son doas nocions que permèton de determinar s'es possible de resòuvre un problema amb un algoritme. La decidabilitat depinta la possibilitat de determinar aisament, sensa demonstracion, s'una proposicion es veraia o faussa. Aquò es important car leis instruccions d'un algoritme dèvon permetre de produrre un resultat e lei situacions indecidablas pòdon donc pas èsser tractadas per un algoritme.

La calculabilitat es la branca dei matematicas que permet d'identificar lei classas d'objèctes susceptibles d'èsser calculats. En generau, un objècte es considerat coma calculable s'existís un metòde de calcul que permet de lo calcular. La durada dau calcul es tanben un critèri important car la calculabilitat despend fòrça dei capacitats dei processors, sovent d'ordinators, utilizats.

La complexitat deis algoritmes

Article principal : Analisi de la complexitat d'un algoritme.

Totei lei problemas tractats per d'algoritmes son pas equivalents. Segon leis instruccions utilizadas, certanei resolucions son pus aisadas o rapidas. Per simplificar lei recèrcas regardant lo tipe d'algoritme d'utilizar, lei problemas son organizats en classas e un algoritme permetent de resòuvre lo problema d'una classa donada permet de resòuvre totei lei problemas d'aquela classa. Pasmens, fau encara chausir l'algoritme pus adaptat a la resolucion d'un problema.

La classificacion dei solucions algoritmicas d'un problema permet de trobar de solucions per selecionnar l'algoritme pus eficaç. Sovent, aquela chausida es basada sus lo nombre d'operacions de realizar per obtenir lo resultat finau. Dins aquò, pòu egalament s'utilizar la natura dei donadas utilizadar, la velocitat d'execucion deis instruccions per lo processor o la durada de calcul. En generau, leis informaticians considèran qu'un algoritme que sa durada d'execucion aumenta d'un biais exponenciau es pas utilizable. En revènge, leis algoritmes de tipe polinomiau, que sa durada d'execucion seguís una foncion polinòmi, son considerats coma utilizables.

Annèxas

Liames intèrnes

• Algoritme adaptatiu.
• Algoritme d'approximacion.
• Algoritme emergent.
• Algoritme recursiu.
• Algoritme repartit.
• Algoritmica.
• Analisi de la complexitat d'un algoritme.
• Foncion.
• Art algoritmic.
• Correccion algoritmica.
• Informacion.
• Intelligéncia artificiala.
• Logica.
• Logiciau.
• Matematicas.
• Operacion.
• Ordinator.
• Procès.

Bibliografia

• (fr) Jean-Michel Autebert, Calculabilité et décidabilité, Dunod, 1992.
• (en) George Boolos, John P. Burgess e Richard Jeffrey, Computability and Logic, Cambridge, 2007.
• (fr) Olivier Carton, Langages formels, calculabilité et complexité, 2008.
• (en) S. Barry Cooper, Computability Theory, Chapman & Hall / CRC, 2004.
• (fr) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein (trad.), Algorithmique : Cours avec 957 exercices et 158 problèmes, Dunod, 2010.
• (en) Michael R. Garey e David S. Johnson, Computers and Intractability : A guide to the theory of NP-completeness, W.H. Freeman & Company, 1979.
• (fr) Patrice Hernert, Les algorithmes, Presses universitaires de France, coll. « Que sais-je ? », 2002.
• (en) Donald E. Knuth, Algorithmes, CSLI Publications, 2011.
• (fr) Donald Knuth (trad. P. Cégielski), Éléments pour une histoire de l'informatique, Librairie Eyrolles, 2011.
• (fr) Richard Lassaigne e Michel de Rougemont, Logique et Complexité, Hermes, 1996.