Algoritmo

Na Galipedia, a Wikipedia en galego.

Algoritmo
Subclase de procedemento obra
Eponimo Al-Khwarizmi
Estudado por teoria da computacion ciencia da informacion analise de algoritmos teoria da complexidade computacional
Parte de ciencias da computacion algoritmica matematicas
Caracterizado por complexidade computacional algorithmic efficiency (en) estabilidade algoritmica (pt)
Identificadores Freebase /m/0jpv MeSH D000465 MathWorld Algorithm OpenAlex C106516650 e C11413529
Fontes e ligazons Descrito pola fonte Enciclopedia sovietica armenia, volume 1 pp. 149-150 The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3rd edition (en) pp. 1-9 Pequeno Dicionario Enciclopedico de Brockhaus e Efron "Q24730825 " Dicionario Enciclopedico Granat "Q118378286 " Dicionario Enciclopedico Brockhaus e Efron "Q24329781 " Gujin Tushu Jicheng "Q96593950 " Enciclopedia de Otto "Algorithmus"
Wikidata C:Commons

Un algoritmo^[1] e un conxunto ordenado e finito de operacions sinxelas que conducen a resolucion dun problema, como por exemplo a formulacion programatica paso a paso para producir unha serie de resultados nun programa en informatica. Mais especificamente, en matematicas, constitue o conxunto de procesos (e simbolos que os representan) para efectuar un calculo.

A palabra algoritmo ten orixe no alcume Al-Khwarizmi, do matematico persa do seculo IX, Abu Yafar Mohammed Abenmusa,^[2] cuxas obras foron traducidas no occidente cristian no seculo XII, recibindo unha delas o nome "Algorithmi de numero indorum", sobre os algoritmos usando o sistema de numeracion decimal (indiano). Outros autores, con todo, defenden a orixe da palabra en Al-goreten (raiz - concepto que se pode aplicar aos calculos).

O concepto de algoritmo e frecuentemente ilustrado co exemplo dunha receita, ainda que moitos algoritmos son mais complexos. Eles poden repetir pasos (facer interaccions) ou necesitar decisions (tales como comparacions ou loxica) ata que a tarefa sexa completada. Un algoritmo correctamente executado non resolvera un problema se o algoritmo fose incorrecto ou non fose apropiado ao problema.

Un algoritmo non representa, necesariamente, un programa de computador, e si os pasos necesarios para realizar unha tarefa. A sua posta en funcionamento pode ser feita por un computador, por outro tipo de automata ou mesmo por un ser humano. Diferentes algoritmos poden realizar a mesma tarefa usando un conxunto diferenciado de instrucions en mais ou menos tempo, espazo ou esforzo que outros. Por exemplo, un algoritmo para se vestir pode especificar que vostede vista primeiro as medias e os zapatos antes de vestir o pantalon, en canto outro algoritmo especifica que vostede debe primeiro vestir o pantalon e despois as medias e os zapatos. Fica claro que o primeiro algoritmo e mais dificil de executar que o segundo.

O vocabulo algoritmo ten as suas raices na latinizacion do nisba, que indica a orixe xeografica, do nome do matematico persa Muhammad ibn Musa al-Khwarizmi como algorismus.^[3][4] Al-Khwarizmi (lkhwrzmy c. 780-850) foi un matematico, astronomo, xeografo e estudoso da Casa da Sabedoria de Bagdad,^[5] e o seu nome significa "natural de Khwarazm", rexion que facia parte do Grande Iran e actualmente pertence a Uzbekistan.^[6][7]

Arredor de 825, al-Khwarizmi escribiu un tratado en arabe sobre o sistema de numeracion indoarabigo, que foi traducido ao latin durante o seculo XII. O manuscrito comeza coa frase Dixit Algorizmi ("Asi falou Al-Khwarizmi"), onde "Algorizmi" foi a latinizacion do nome de Al-Khwarizmi que fixo o tradutor.^[8] Al-Khwarizmi foi o matematico mais lido en Europa a finais da idade media, especialmente por outro dos seus libros, Alxebra.^[9] No latin medieval final, algorismus significaba simplemente "sistema de numeracion decimal".^[10] No seculo XV, pola influencia da palabra grega arithmos (arithmos), "numero", a palabra latina alterouse a algorithmus. O vocabulo ingles algorithm foi recollido no seculo XVII e o sentido moderno da expresion deuselle no seculo XIX.^[11]

Xeralmente, os algoritmos describense informalmente nunha linguaxe proxima da lingua natural, mais facilmente comprendida por un ser humano que por un computador. Un algoritmo pode, na maior parte dos casos, ser aplicado en calquera linguaxe de programacion.

Un programa de computador e esencialmente un algoritmo que di ao computador os pasos especificos e en que orde eles deben ser executados, como por exemplo, os pasos a seren tomados para calcular as notas que seran impresas nos boletins dos alumnos dunha escola.

Para calquera proceso computacional, o algoritmo precisa estar rigorosamente definido, especificando como se comportara en todas as circunstancias. A correccion do algoritmo pode ser probada matematicamente, ben como a cantidade asintotica de tempo e espazo (complexidade) necesarios para a sua execucion. Estes aspectos dos algoritmos son materia da analise de algoritmos.

Hai hoxe unha gran variedade de linguaxes de programacion, cada unha con caracteristicas especificas que poden facilitar a aplicacion de determinados algoritmos ou atender a propositos mais xerais.

Os algoritmos non se ponen en funcionamento so como programas para computadores, senon que tamen se poden aplicar en circuitos electricos ou ata no noso cerebro cando executamos operacions aritmeticas. A analise de algoritmos e unha rama da ciencia da computacion que estuda as tecnicas de proxecto de algoritmos e os algoritmos de forma abstracta, sen estaren aplicados nunha linguaxe de programacion en particular ou dalgun outro modo. Un medio de exhibir un algoritmo e mostrar o seu pseudocodigo.

Un algoritmo pode concibirse como unha funcion que transforma os datos dun problema (entrada) nos datos dunha solucion (saida). Ainda mais, os datos poden representarse a sua vez como secuencias de bits, e en xeral, de simbolos calquera.^[12] Como cada secuencia de bits representa un numero natural, enton os algoritmos son en esencia funcions dos numeros naturais nos numeros naturais que si se poden calcular. E dicir que todo algoritmo calcula unha funcion ${\displaystyle f:\mathbf {N} \to \mathbf {N} }$ onde cada numero natural e a codificacion dun problema ou dunha solucion.

En ocasions os algoritmos son susceptibles de non rematar nunca, por exemplo, cando entran nun bucle infinito. Cando ocorre isto, o algoritmo nunca devolve ningun valor de saida, e podemos dicir que a funcion queda indefinida para ese valor de entrada. Por esta razon considerase que os algoritmos son funcions parciais, e dicir, non necesariamente definidas en todo o seu dominio de definicion.

Cando unha funcion pode ser calculada por medios algoritmicos, sen importar a cantidade de memoria que ocupe ou o tempo que se tarde, dise que esa funcion e computable. Non todas as funcions entre secuencias datos son computables. O problema da parada e un exemplo.

O problema consiste en atopar o maximo dun conxunto de numeros.

Dado un conxunto finito ${\displaystyle C}$ de numeros, tense o problema de atopar o numero mais grande. Sen perda de xeneralidade pode asumirse que ese conxunto non e baleiro e que os seus elementos estan numerados como ${\displaystyle c_{0},c_{1},\dots ,c_{n}}$.

E dicir, dado un conxunto ${\displaystyle C=\{c_{0},c_{1},\dots ,c_{n}\}}$ pidese atopar ${\displaystyle m}$ tal que ${\displaystyle x\leq m}$ para todo elemento ${\displaystyle x}$ que pertence ao conxunto ${\displaystyle C}$.

Para atopar o elemento maximo, asumese que o primeiro elemento (${\displaystyle c_{0}}$) e o maximo; despois, percorrese o conxunto e comparase cada valor co valor do maximo numero atopado ata ese momento. No caso no que un elemento sexa maior que o maximo, asignase o seu valor ao maximo. Cando se termina de percorrer a lista, o maximo numero que se atopou e o maximo de todo o conxunto.

O algoritmo pode ser escrito dunha maneira mais formal no seguinte pseudocodigo:

Atopar o maximo dun conxunto:

funcion max(${\displaystyle C}$) //${\displaystyle C}$ e un conxunto non baleiro de numeros// ${\displaystyle n}$ - ${\displaystyle |C|}$ //${\displaystyle |C|}$ e o numero de elementos de ${\displaystyle C}$// ${\displaystyle m}$ - ${\displaystyle c_{0}}$ para ${\displaystyle i}$ - ${\displaystyle 1}$ ata ${\displaystyle n}$ facer se ${\displaystyle c_{i}>m}$ enton ${\displaystyle m}$ - ${\displaystyle c_{i}}$

devolver ${\displaystyle m}$

Sobre a notacion:

• "-" representa unha asignacion: ${\displaystyle m}$ - ${\displaystyle x}$ significa que a variable ${\displaystyle m}$ toma o valor de ${\displaystyle x}$;
• "devolver" termina o algoritmo e da o valor a sua dereita (neste caso, o maximo de ${\displaystyle C}$).

En linguaxe C++:

Exemplo dun algoritmo que devolve a suma de dous valores (tamen conecidos como parametros ou argumentos) que son introducidos na chamada da funcion:

funcion SumaDeDousValores (A numerico, B numerico)
{
declara SUMA numerico
SUMA <-- A + B
retorna SUMA
}

Exemplo dun algoritmo (WinPseudo 1.4) que imprime todos os numeros menores que :

#-----------------------------------------
# Pseudocodigo para imprimir todos os
# numeros menores que
#-----------------------------------------

INICIO Programa1 - Imprime todos os numeros menores que

VAR
NUMERICO i
NUMERICO Limite
FIN-VAR

LER (Limite)
IMPRIMIR NL

i = 0
MENTRES (i < Limite)
IMPRIMIR ENTEIRO (i)
IMPRIMIR ", "
i = i + 1
FIN-MENTRES

FINAL

Wikimedia Commons ten mais contidos multimedia na categoria: Algoritmo

• Bellah, Robert Neelly (1985). Habits of the Heart: Individualism and Commitment in American Life. Berkeley: University of California Press. ISBN 978-0-520-25419-0.
• Berlinski, David (2001). The Advent of the Algorithm: The 300-Year Journey from an Idea to the Computer. Harvest Books. ISBN 978-0-15-601391-8.
• Chabert, Jean-Luc (1999). A History of Algorithms: From the Pebble to the Microchip. Springer Verlag. ISBN 978-3-540-63369-3.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction To Algorithms (3rd ed.). MIT Press. ISBN 978-0-262-03384-8.
• Harel, David; Feldman, Yishai (2004). Algorithmics: The Spirit of Computing. Addison-Wesley. ISBN 978-0-321-11784-7.
• Hertzke, Allen D.; McRorie, Chris (1998). "The Concept of Moral Ecology". En Lawler, Peter Augustine; McConkey, Dale. Community and Political Thought Today. Westport, CT: Praeger.
• Knuth, Donald E. (2000). Selected Papers on Analysis of Algorithms Arquivado 01 de xullo de 2017 en Wayback Machine.. Stanford, California: Center for the Study of Language and Information.
• Knuth, Donald E. (2010). Selected Papers on Design of Algorithms Arquivado 16 de xullo de 2017 en Wayback Machine.. Stanford, California: Center for the Study of Language and Information.
• Wallach, Wendell; Allen, Colin (November 2008). Moral Machines: Teaching Robots Right from Wrong. US: Oxford University Press. ISBN 978-0-19-537404-9.

• Algoritmo xenetico
• Ciencia da Computacion
• Estruturas de datos
• Exemplos de algoritmos en varias linguaxes

• Exemplos de algoritmos basicos
• Todo sobre algoritmos Arquivado 03 de maio de 2020 en Wayback Machine.

Obtido de <<https://gl.wikipedia.org/w/index.php?title=Algoritmo&oldid=7169722>>

Categorias:

• Algoritmos
• Enxenaria de software

Categorias agochadas:

• Artigos que toda Wikipedia deberia ter (mais de 10 kB)
• Artigos que toda Wikipedia deberia ter (Tecnoloxia)