Algoritme : Diferéncia entre lei versions
Contengut suprimit Contengut apondut
→Top : +modèl:Referéncia Harvard sens parentèsis →Bibliografia : +modèl:Obratge: "1987" (first ed.) → "2011". "Computbility" → "Computability" +oclc |
Cap resum de modificació |
||
Linha 1 :
{{1000 fondamentals}}
{{Dialècte Provençau}}
[[Fichièr:Euclid flowchart.svg|thumb|right|Exemple d'un algoritme que permet de trobar lo pus pichon divisor comun de dos [[nombre]]s.]]
<references/>▼
Un '''algoritme''' es un ensemble finit d'[[operacion (matematica)|operacion]]s e d'instruccions definidas que permèton de resòuvre un problema. Lo [[mot|tèrme]] ven de la [[latin]]izacion dau nom dau [[matematicas|matematician]] arabi [[Muhammad ibn Musa al-Khwarizmi|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 [[ordinator]]s, dei [[logiciau]]s o dei [[Tecnologia|tecnicas]] de [[criptografia]].
== Bibliografia ==▼
L'[[algoritmica]] es la disciplina qu'estúdia leis algoritmes.
== Istòria ==
[[Fichièr:Cuneiform tablet- fragment of a mathematical problem text MET ME86 11 404.jpg|thumb|right|Tauleta [[Babilònia (reialme)|babiloniana]] presentant un problema algoritmic.]]
[[Fichièr:115 Museu Tèxtil de Terrassa.jpg|thumb|right|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 [[matematicas|matematicians]] [[Babilònia (reialme)|babilonians]] de l'[[Antiquitat]]. Depintavan de metòdes de calcul e de resolucion d'[[eqüacion]]s<ref>'''(en)''' Donald Knuth, « Ancient Babylonian Algorithms », ''Communications of the ACM'', vol. 15, n°7, julhet de 1972.</ref>. 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 [[matematicas|matematician]] arabi [[Muhammad ibn Musa al-Khwarizmi|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üacion]]s quadraticas, prepausèt de metòdes de resolucion basadas sus una succession d'[[operacion (matematica)|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 [[França|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)<ref>'''(en)''' Betty Alexandra Toole, ''Ada, the enchantress of numbers, prophet of the computer age : a pathway to the 21st century'', Strawberry Press, Mill Valley (Calif.), 1998.</ref>.
Au sègle XX, l'[[algoritmica]] venguèt una disciplina importanta amb lo desvolopament dei [[tecnologias de l'informacion]] e dei [[maquina de Turing|maquinas de Turing]]. D'efiech, aquelei sistèmas, a l'origina deis [[ordinator]]s 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 [[logiciau]]s. Trobèron tanben d'aplicacions importantas dins d'autrei sectors coma la [[criptografia]], lo partiment d'informacions, lo [[Tractament d'imatge|tractament d'imatges]] e lo [[Tractament de tèxte|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 [[ordinator]]s qu'executan leis algoritmes son pas infinidament rapids car, en despiech de l'aumentacion regulara dei performàncias deis [[ordinator]]s, 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 [[matematicas|matemacian]] [[USA|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'[[tecnologias de l'informacion|informatician]] [[França|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|logica formala]] a un ròtle important dins la redaccion e lo foncionament d'un algoritme. D'efiech, avans d'[[escritura|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 ([[Homo sapiens|uman]], [[maquina|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 matematica|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'[[ordinator]]s, 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'[[operacion (matematica)|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 [[tecnologias de l'informacion|informaticians]] considèran qu'un algoritme que sa durada d'execucion aumenta d'un biais [[Foncion exponenciala|exponenciau]] es pas utilizable. En revènge, leis algoritmes de tipe polinomiau, que sa durada d'execucion seguís una [[Aplicacion (matematicas)|foncion]] [[polinòmi]], son considerats coma utilizables.
== Annèxas ==
=== Liames intèrnes ===
<div style="-moz-column-count:3; column-count:3;">
* [[Algoritmica]].
* [[Analisi de la complexitat d'un algoritme]].
* [[Aplicacion (matematicas)|Foncion]].
* [[Correccion algoritmica]].
* [[Informacion]].
* [[Intelligéncia artificiala]].
* [[Logica]].
* [[Logiciau]].
* [[Matematicas]].
* [[Operacion (matematica)|Operacion]].
* [[Ordinator]].
* [[Procès (qualitat)|Procès]].
</div>
▲=== 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.
=== Nòtas e referéncias ===
<div style="-moz-column-count:3; column-count:3;">
▲<references/>
</div>
[[Category:Algoritme]]
| |||