miniatura|Diagrama de fluxo do algoritmo de Euclides. Un algoritmo é un conxunto ordenado e finito de operacións sinxelas que conducen á resolución dun problema, como por exemplo a formulación programática paso a paso para producir unha serie de resultados nun programa en informática. Máis especificamente, en matemáticas, constitúe o conxunto de procesos (e símbolos que os representan) para efectuar un cálculo. Partindo dun estado inicial e unha entrada determinada, a aplicación dos pasos sucesivos dun algoritmo conduce a un estado final que proporciona unha solución ao problema exposto. Os algoritmos utilízanse como especificacións para realizar cálculos e procesamento de datos. Os algoritmos máis avanzados poden empregar condicións para desviar a execución do código por diversas rutas (o que se coñece como toma de decisións automatizada) e deducir inferencias válidas (o que se coñece como razoamento automatizado).
Pola contra, unha heurística é un método para resolver problemas sen resultados correctos ou óptimos ben definidos.David A. Grossman, Ophir Frieder, Information Retrieval: Algorithms and Heuristics, 2nd edition, 2004, Por exemplo, aínda que os sistemas de recomendación das redes sociais adoitan denominarse "algoritmos", en realidade baséanse en heurísticas, xa que non existe unha recomendación verdadeiramente "correcta".
A palabra algoritmo ten orixe no alcume Al-Khwarizmi, do matemático persa do século IX, Abu Yafar Mohámmed Abenmusa,https://portaldaspalabras.gal/lexico/mira-que-din/algoritmo/ cuxas obras foron traducidas no occidente cristián no século XII, recibindo unha delas o nome "Algorithmi de numero indorum", sobre os algoritmos usando o sistema de numeración decimal (indiano). Outros autores, con todo, defenden a orixe da palabra en Al-goreten (raíz - concepto que se pode aplicar aos cálculos).
O concepto de algoritmo é frecuentemente ilustrado co exemplo dunha receita, aínda que moitos algoritmos son máis complexos. Eles poden repetir pasos (facer interaccións) ou necesitar decisións (tales como comparacións ou lóxica) ata que a tarefa sexa completada. Un algoritmo correctamente executado non resolverá 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 súa posta en funcionamento pode ser feita por un computador, por outro tipo de autómata ou mesmo por un ser humano. Diferentes algoritmos poden realizar a mesma tarefa usando un conxunto diferenciado de instrucións en máis 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 pantalón, en canto outro algoritmo especifica que vostede debe primeiro vestir o pantalón e despois as medias e os zapatos. Fica claro que o primeiro algoritmo é máis difícil de executar que o segundo.
Como método eficaz, un algoritmo pode expresarse nun espazo e un tempo finitos"Calquera algoritmo matemático clásico, por exemplo, pode describirse cun número finito de palabras en inglés" (Rogers 1987:2). e nun linguaxe formal ben definidoBen definido no que respecta ao axente que executa o algoritmo: "Existe un axente computacional, normalmente humano, capaz de reaccionar ante as instrucións e realizar os cálculos." (Rogers 1987:2). para calcular unha función."un algoritmo é un procedemento para calcular unha «función» (en relación cunha notación determinada para os números enteiros)... esta limitación (ás funcións numéricas) non supón ningunha perda de xeneralidade", (Rogers 1977:1). Partindo dun estado inicial e unha entrada inicial (quizais baleira),"Un algoritmo ten cero ou máis entradas, é dicir, cantidades que se lle proporcionan inicialmente antes de que o algoritmo comece" (Knuth 1973:5). As instrucións describen un cálculo que, ao executarse, desenvólvese ao longo dun número finito de pasos"Un procedemento que reúna todas as características dun algoritmo, salvo que posiblemente careza de finitud, pode denominarse «método computacional»." (Knuth 1971:5). unha serie de estados sucesivos ben definidos, que finalmente dan lugar a un "resultado""Un algoritmo ten unha ou máis saídas, é dicir, magnitudes que gardan unha relación determinada coas entradas" (Knuth 1973:5). e que termina nun estado final. A transición dun estado ao seguinte non é necesariamente determinista; algúns algoritmos, coñecidos como algoritmos aleatorios, incorporan entradas aleatorias.É discutible se un proceso con procesos internos aleatorios (sen incluír a entrada) constitúe ou non un algoritmo. Rogers opina que: "o cálculo leva a cabo de forma discreta e por pasos, sen utilizar métodos continuos nin dispositivos analóxicos... e desenvólvese de maneira determinista, sen recorrer a métodos ou dispositivos aleatorios, por exemplo os dados". (Rogers 1987:2).
O estudo dos algoritmos constitúe o obxecto central da algoritmia. Definición Unha definición informal é "un conxunto de regras que define con precisión unha secuencia de operacións", o que incluiría todos os programas informáticos (incluídos os que non realizan cálculos numéricos) e calquera procedemento burocrático establecido como unha receita dun libro de cociña. En xeral, un programa é un algoritmo só se finalmente se deténStone esixe que "debe concluír nun número finito de pasos"" (Stone 1973:7–8).—aínda que os bucles infinitos ás veces poidan resultar desexables. Boolos e Jeffrey definen un algoritmo como un conxunto explícito de instrucións para determinar un resultado, que pode seguir tanto unha máquina computacional como un ser humano capaz unicamente de realizar operacións elementais específicas sobre símbolos. Etimoloxía miniatura|150px|esquerda|Muḥammad ibn Mūsā al-Khwārizmī: O matemático do século IX cuxo nome é a orixe da palabra 'algoritmo'. O vocábulo algoritmo ten as súas raíces na latinización do nisba, que indica a orixe xeográfica, do nome do matemático persa Muhammad ibn Musa al-Khwarizmi como algorismus. Al-Khwārizmī (الخوارزمی c. 780–850) foi un matemático, astrónomo, xeógrafo e estudoso da Casa da Sabedoría de Bagdad, e o seu nome significa "natural de Khwarazm", rexión que facía parte do Grande Irán e actualmente pertence a Uzbekistán.
Arredor de 825, al-Khwarizmi escribiu un tratado en árabe sobre o sistema de numeración indoarábigo, que foi traducido ao latín durante o século XII. O manuscrito comeza coa frase Dixit Algorizmi ("Así falou Al-Khwarizmi"), onde "Algorizmi" foi a latinización do nome de Al-Khwarizmi que fixo o tradutor. Al-Khwarizmi foi o matemático máis lido en Europa a finais da idade media, especialmente por outro dos seus libros, Álxebra.Foremost mathematical texts in history , segundo Carl B. Boyer. No latín medieval final, algorismus significaba simplemente "sistema de numeración decimal". No século XV, pola influencia da palabra grega ἀριθμός (arithmos), "número", a palabra latina alterouse a algorithmus. O vocábulo inglés algorithm foi recollido no século XVII e o sentido moderno da expresión déuselle no século XIX.Oxford English Dictionary, Third Edition, 2012 s.v. Historia Algoritmos antigos Desde a antigüidade documentáronse procedementos paso a paso para resolver problemas matemáticos. Entre eles inclúense os da matemática babilónica (ao redor do 2500 a. C.), matemáticas exipcias (cara ao ano 1550 a. C.), matemáticas indias (arredor do ano 800 a. C. e posteriores),Hayashi, T. (1 de xaneiro de 2023). Brahmagupta. Encyclopedia Britannica. o oráculo de Ifá (arredor do ano 500 a. C.), matemáticas gregas (arredor do ano 240 a.C.), matemáticas chinesas (arredor do ano 200 a. C. e posteriores), e matemáticas árabes (arredor do ano 800 d.C.).
A evidencia máis antiga de algoritmos atópase nas matemáticas da antiga Mesopotamia. Unha táboa de arxila sumeria atopada en Shuruppak preto de Bagdad e datada no describe o algoritmo de división máis antigo. Durante a dinastía Hammurabi , as táboas de arxila de Babilonia describían algoritmos para calcular fórmulas. Os algoritmos tamén se empregaron na astronomía babilónica. As táboas de arxila babilónicas describen e empregan procedementos algorítmicos para calcular o tempo e o lugar de eventos astronómicos significativos.
Os algoritmos para a aritmética tamén se atopan nas matemáticas do antigo Exipto, que se remontan ao papiro matemático de Rhind. . Os algoritmos empregáronse posteriormente nas antigas matemáticas helenísticas. Dous exemplos son a criba de Eratóstenes, que foi descrita na Introdución á aritmética de Nicómaco, e o algoritmo euclidiano, que foi descrito por primeira vez nos Elementos de Euclides (). Algúns exemplos de matemáticas da antiga India son os Shulba Sutras, a Escola de Kerala e o Brāhmasphuṭasiddhānta.
Algoritmos e linguaxes de programación de computadores Xeralmente, os algoritmos descríbense informalmente nunha linguaxe próxima da lingua natural, máis facilmente comprendida por un ser humano que por un computador. Un algoritmo pode, na maior parte dos casos, ser aplicado en calquera linguaxe de programación.
Formalizando algoritmos Un programa de computador é esencialmente un algoritmo que di ao computador os pasos específicos e en que orde eles deben ser executados, como por exemplo, os pasos a seren tomados para calcular as notas que serán impresas nos boletíns dos alumnos dunha escola.
Para calquera proceso computacional, o algoritmo precisa estar rigorosamente definido, especificando como se comportará en todas as circunstancias. A corrección do algoritmo pode ser probada matematicamente, ben como a cantidade asintótica de tempo e espazo (complexidade) necesarios para a súa execución. Estes aspectos dos algoritmos son materia da análise de algoritmos.
Posta en funcionamento Hai hoxe unha gran variedade de linguaxes de programación, cada unha con características específicas que poden facilitar a aplicación de determinados algoritmos ou atender a propósitos máis xerais.
Os algoritmos non se poñen en funcionamento só como programas para computadores, senón que tamén se poden aplicar en circuítos eléctricos ou ata no noso cerebro cando executamos operacións aritméticas. A análise de algoritmos é unha rama da ciencia da computación que estuda as técnicas de proxecto de algoritmos e os algoritmos de forma abstracta, sen estaren aplicados nunha linguaxe de programación en particular ou dalgún outro modo. Un medio de exhibir un algoritmo é mostrar o seu pseudocódigo.
Algoritmos como funcións miniatura|Esquema dun algoritmo que soluciona un problema de ciclo hamiltoniano.|400 px Un algoritmo pode concibirse como unha función que transforma os datos dun problema (entrada) nos datos dunha solución (saída). Aínda máis, os datos poden representarse á súa vez como secuencias de bits, e en xeral, de símbolos calquera. Como cada secuencia de bits representa un número natural, entón os algoritmos son en esencia funcións dos números naturais nos números naturais que si se poden calcular. É dicir que todo algoritmo calcula unha función onde cada número natural é a codificación dun problema ou dunha solución.
En ocasións os algoritmos son susceptibles de non rematar nunca, por exemplo, cando entran nun bucle infinito. Cando ocorre isto, o algoritmo nunca devolve ningún valor de saída, e podemos dicir que a función queda indefinida para ese valor de entrada. Por esta razón considérase que os algoritmos son funcións parciais, é dicir, non necesariamente definidas en todo o seu dominio de definición.
Cando unha función pode ser calculada por medios algorítmicos, sen importar a cantidade de memoria que ocupe ou o tempo que se tarde, dise que esa función é computable. Non todas as funcións entre secuencias datos son computables. O problema da parada é un exemplo.
Exemplo de algoritmo O problema consiste en atopar o máximo dun conxunto de números.
Descrición de alto nivel