Algorithmo

Algorithmo
subclasse de:procedure[*],work[*],software
parte de:Informatica,algorithmics[*],mathematica
Commons:Algorithms

Unalgorithmo(dellatinoalgorismus,nominate pro le inventator dealgebraMohamet ibn Musa al-Khwarizmi) es un serie de instructiones interpretabile e finite pro resolver contingentias e accomplir qualcunque carga que ha unstatofinal recognoscibile, puncto final, o resultato pro catadatopossibilemente introducite in illo. (Contrasta conheuristica.) Algorithmos sovente ha passositerateo requirente decisiones (usante lelogica booleaneinequalitates) usque al completion del carga.

In terminosmathematicformal, un algorithmo es considerate esser un qualcunque sequentia de operationes que pote esser exequite per unsystema de Turing complete.

Algorithmos differente pote compler le mesme carga con un differente serie de instructiones in plus o minus tempore, spatio, o effortio que alteres. Un recepta pro cocer es un exemplo de un algorithmo. Donate duo differente receptas pro facer salata de patatas, le un pote haber "pella le patata" ante "coce le patata in aqua" durante que le altere presenta le passos in ordine reverse; totevia ambes instrue a repeter iste passos pro tote le patatas usque le salata de patatas es preste pro esser mangiate.

Exequer un algorithmo correctemente non solvera un problema si le algorithmo es defecte o inappropriate al problema. Per exemplo, un execution del algorithmo pro salata de patatas fallira si il non ha patatas disponibile, mesmo si tote le motiones de preparar le salata es exequite como si le patatas esseva presente.

Algorithmos formal

Algorithmos es essential a fin quecomputatorestracta information, proque unprogramma computatoriales essentialmente un algorithmo que instrue a uncomputatorle passos specific a exequer (e lor ordine specific) a fin de exequer un carga specific, tal como le calculation del salario de empleatos o imprimer le cartas de reporto de studentes.

Normalmente, si un algorithmo es associate con le tractamento de information,datoses legite de un fonte o apparato pro introduction(entrata),scribite a un canal o apparato pro rendimento(sortita),e/o immagazinate pro uso futur.Datosimmagazinate es reguardate como parte delstato internedel entitate exequente le algorithmo.

Pro omne talprocessocomputational, le algorithmo debe esser definite rigorosemente: specificate de tal maniera que illo es applicabile a omne possibile circumstantias que poterea manifestar se. Isto es, omne passos conditional debe esser definite systematicamente, caso per caso; le criterios pro cata caso debe esser clar (e computabile).

Pro que un algorithmo es un lista precise de passos precise, le ordine de computation es quasi sempre essential a su functionamento. Instructiones es normalmente assumite de esser listate explicitemente, e es describite como initiante 'ab le summitate' e descendente 'al fundo', un idea que es describite plus formalmente como unfluxo de controlo.

Usque ora, iste discussion del formalisation de un algorithmo ha assummite le premissos delprogrammation imperative.Isto es le concepto le plus commun, e illo tenta de describer un carga de maniera discrete e 'mechanic'. Unic a iste concepto de algorithmos formalisate es leoperation de assignamento,que assigna un valor a un variabile. Illo deriva del intuition de 'memoria' como un bloco de notas. Infra se trova un exemplo de un tal assignamento.

Videprogrammation functionalpro un description alternative de un algorithmo.

Implementation de algorithmos

Quando un description formal ha essite obtenite, un algorithmo es un methodo o procedura ben definite pro solver un problemamathematico alteremente connexe al manipulation deinformation.

Algorithmos se implementa hodie le plus sovente comoprogrammas de computatorsed pote esser implementate per altere medios, tales comocircuitos electrico un machina. Algorithmos pote mesmo esser executate directemente perhumanos:pensa per exemplo de unabaco,o le execution dearithmeticacon penna e papiro o su equivalente mental – le majoritate del gente usa algorithmos apprendite in le juventute pro facer isto.

Leanalyse e studio de algorithmoses un disciplina central delinformatica,e se practica sovente abstractemente (sin uso de alcunlinguage de programmationspecific, designate pro implementation practic). In iste senso, illo resimila altere disciplinasmathematicin le quales le analyse se concentra super le principios fundamental del execution del algorithmo, e non super alcun implementation particular de illo. Le "codification" de algorithmos de tal maniera abstracte es appellate "scriberpseudocodice".

Alcun personas restringe le definition de "algorithmo" a proceduras con un fin. Alteres include proceduras que poterea exequer se pro sempre e continuemente, con le argumento que uncomputatorpote deber exequer un carga continue. In tal caso on usa altere exigentias que le existentia de unstatofinal pro determinar si le algorithmo comple un carga con successo.

Typos de algorithmos

Il ha plure methodos pro cassificar algorithmos, cata un con su proprie meritos.

Classification per campo de studio

Cata campo descientiahabe su proprie problemas que require algorithmos efficiente. Problemas relate in un campo es frequentemente studiate conjunctemente. Exemplos includealgorithmos de cercar,algorithmos de assortir,algorithmos de fusionar,algorithmos numeric,algorithmos graphic,algorithmos de series,algorithmos combinatorial,algorithmos de compression,ealgorithmos cryptographic.

Le campos differente frequentemente coincide con alteres, e advantias in algorithmos in un campo pote meliorar le solutiones de problemas in altere, a vices non totalmente distincte, campos. Per exemplo, leprogrammation dynamicesseva inventate pro le optimisation del consumption de ressoures industrial, sed hodie illo es usate pro resolver plure categorias in plure campos.

Classification per complexitate

Algorithmos pote esser classificate per le quantitate de tempore que illos require pro completer, comparate al dimension de su entrata. Iste es suordine de computation.Il ha un varietate large; alcun algorithmos se complete intempore linearrelative al dimension del entrata, sed alteres haordine exponentialo pejor, e alcunnunquam fini.Additionalmente, alcun problemas ha plure algorithmos de differente ordines de computation, sed altere problemas ha nulle algorithmo efficiente -- o simplemente nulle algorithmo. Gratias a isto, e al intersection de campos, on crede que il es melior de classificar le problams in categorias de equivalentia, basate super le complexitate maxime del algorithmo possibile inter illos.

Exemplo

Ecce un exemplo simple de un algorithmo.

Imagina haber un lista non assortite de numeros qualcunque. Nostre objectivo es de trovar le numero le plus grande in iste lista. Un prime pensata super le solution rende obvie que cata numero in le lista debe esser examinate. Plus de reflexion revela que il non es necessari de reguardar cata numero plus de un vice. Con isto in consideration, ecce un algorithmo simple pro accomplir isto:

1. Assume que le prime numero in le lista es le numero le plus grande.
2. Reguarda le sequente numero, e compara lo con iste numero le plus grande.
3. Solmente si iste proxime numero es plus grande, retene illo con le nove numero le plus grande.
4. Repete passos 2 e 3 usque tote le lista ha essite percurrite.

Ecce un codification plus formal del algorithmo in unpseudocodicesimile al majoritate dellinguages de programmation:

Date: un listaListade longorLongor

contator = 1
leplusgrande = Lista[contator]
durante contator <= Longor:
si Lista[contator] > leplusgrande:
leplusgrande = Lista[contator]
contator = contator + 1
imprime leplusgrande

Notas super le notation:

• =como usate hic significa un assignamento. Isto es, le valor al dextra del expression es assignate al receptaculo (o variabile) al sinistra del expression.
• Lista[contator]como usate hic significa le elemento numerocontatorin le lista. Per exemplo: si le valor decontatores 5, aloralist[contator]refere al 5te elemento del lista.
• <=como usate hic significa "minus de o equal a".

In le practica, le majoritate de personas qui implementa algorithmos vole saper quanto un particular ressource (tal como tempore o immagazination) un algorithmo donate require. Il ha essite disveloppatemethodospro leanalyse de algorithmospro obtener taldatosquantitative, e quando vos ha legite iste section, vos determinara que iste algorithmo ha un requirimente temporal de O(n), ubi lenotation de O majusculeesseva usate enrepresenta le longor del lista.

Historia

Le parolaalgorithmoproveni del anglesealgorithmque es un modification dealgorismedellatino medievalque proveniva del nomine delmathematicopersianMohamet ibn Musa al-Khwarizmi(ca.780- ca.845). Ille esseva le autor dellibroKitab al-jabr w'al-muqabala (Regulas de restauration e de reduction)que introduceva lealgebraal genteoccidental.Originalmente le parola refereva solmente al regulas de exequerarithmeticaconnumerales arabesed finalmente evolveva a includer omne procedura definite pro resolver problemas o exequer cargas. Le parolaalgebramesme proveni deal-Jabrdel titulo dellibro.

Le prime caso de un algorithmo scribite pro uncomputatoresseva le notas super le motor analytic deAda Lovelacescribite in1842,le quales la ha donate le titulo de primeprogrammatordel mundo.

Le manco de rigormathematicin le definition "procedura ben definite" de algorithmos poneva alcun difficultates almathematicose allogicosdelseculo 19e del initio delseculo 20.Iste problema esseva pro le major parte resolvite con le description delmachina de Turing,un modello abstracte de uncomputatordescribite perAlan Turing,e le demonstration que omnemethodopro describer "proceduras ben definite" trovate usque hodie per alteremathematicospoterea esser emulate in unmachina de Turing(un declaration cognoscite como lethese de Church-Turing).

Hodie, un criterio formal pro un algorithmo es que illo es un procedura implementabile in unmachina de Turingcompletemente specificate o in un del formalismos equivalente. Le interesse initial deTuringesseva in leproblema de haltar,i.e. de decider quando un algorithmo describe un procedura que ha un fin. In terminos practic, letheoria de complexitate computationalimporta plus: illo include le problema mysteriose del algorithmos appellateNP-complete,que es generalmente presumite de prender un quantitate de tempore plus que polynomial.

Nota

Traduction incomplete

Iste pagina es untraduction incompleteabWikipedia in anglese.Le articulo original se trova in leversion 2206762deen:Algorithm,e es usate secundo le mandatos del licentia de Wikipedia. Nos te invita cordialmente acompletar le traductionpro meliorarWikipedia in interlingua.