Algoritmo
El algoritmo es el conjunto de reglas y técnicas que intervienen en la definición y diseño de algoritmos, es decir, proceso sistemático de resolución de un problema para describir los pasos a obtener el resultado. En otras palabras, un algoritmo es una secuencia finita e instrucción inequívoca para dar una respuesta a un problema.
Si las instrucciones de un algoritmo se ejecutan uno tras otro, el algoritmo es secuencial, si se están ejecutando al mismo tiempo, es paralelo. Si el algoritmo opera tareas que se ejecutan en una red de procesadores hablamos de algoritmo distribuido, o distribuido.
La palabra «algoritmo» proviene del nombre del matemático Al Khwarizmi (latinizado la Edad Media en Algoritmi), que en el siglo IX escribió el primer libro sobre la solución sistemática de ecuaciones lineales y cuadráticas.
Estudio sistemático algoritmo
El primero en ser algoritmos sistematizados es el matemático árabe al-Khwarizmi, activo entre 813 y 833. En su libro Compendio de cálculo por reintegración y comparación, estudió todas las ecuaciones cuadráticas y da la resolución por medio de algoritmos generales. Utiliza métodos similares a los de los babilonios, pero se distingue por sus explicaciones sistemáticas donde los babilonios sólo mostro ejemplos.
El sabio árabe Averroes (1126-1198) describe un método de razonamiento que la tesis se refina paso a paso de forma iterativa hasta cierta convergencia y está de acuerdo con la realización de un algoritmo. Al mismo tiempo, en el siglo XII, el monje Adelardo de Bath introdujo el término Algorismus América, con el nombre de Al Khwarizmi.
En el siglo XVII, se podría apuntar a alguna alusión al método algorítmico a René Descartes en el método general propuesto por el Discurso del método (1637), sobre todo cuando, en la segunda parte, el lógico francés propone «dividir cada una de las dificultades yo examinemos en tantas partes como podamos, y que se requeriría para una mejor resolución. «Sin mencionar explícitamente el concepto de bucle, iteración o dicotomía, el enfoque de Descartes predispone lógica para acoger el concepto de programa.
El uso del término algoritmo es notable acerca de Ada Lovelace, hija de Lord Byron y ayudante de Charles Babbage (1791-1871).
Sustantivo algorítmico se refiere al método que utiliza algoritmos. El término también se usa como un adjetivo.
Un algoritmo establece una resolución en la forma de una serie de operaciones a realizar. La implementación del algoritmo consiste en la escritura de estas operaciones en un lenguaje de programación y forma entonces el bloque básico de un programa de ordenador.
Los profesionales de TI a menudo usan para describir el anglicismo. Escribiendo en lenguaje informático también se refiere con frecuencia como «codificación», que no tiene relación aquí criptografía, pero en referencia al término «código fuente» para referirse al texto, lenguaje de programación, que constituye el programa de estudios. El algoritmo será más o menos detallado dependiendo del nivel de abstracción del lenguaje utilizado, así como una receta para ser más o menos detallada dependiendo de la experiencia del cocinero.
Sin entrar en detalles matemáticos, el cálculo de la eficiencia de un algoritmo (la complejidad computacional) consiste en la búsqueda de dos grandes cantidades. La primera cantidad es la evolución del número de instrucciones en términos de la cantidad de datos a procesar (por ejemplo, un algoritmo de clasificación, que es el número de datos para ser clasificados), que se prefiere el tiempo de ejecución se mide en segundos (porque este último depende de la máquina en la que el algoritmo se ejecuta). La segunda cantidad estimada es la cantidad de memoria necesaria para realizar los cálculos. Basando el cálculo de la complejidad de un algoritmo en el tiempo o la cantidad real de memoria de un ordenador en particular es realizar dicho algoritmo no tiene en cuenta la estructura interna del algoritmo, o la característica del PC: de acuerdo con su carga de trabajo, la velocidad de su procesador, la velocidad de acceso a datos, la ejecución del algoritmo (que puede implicar la probabilidad) o su organización de la memoria, el tiempo de ejecución y la cantidad de memoria no será el mismo.
A menudo nos fijamos en el rendimiento «peor», es decir, en configuraciones tales como el tiempo de ejecución (o memoria) es el más grande. Hay también otro aspecto de la evaluación de la eficiencia de un algoritmo: «promedio» rendimiento. Para ello es necesario contar con un modelo de la distribución estadística de los datos del algoritmo, mientras que la aplicación de técnicas analíticas implica métodos combinatorios bastante delgados y evaluación asintótica, utilizando en particular los sistemas de generación y métodos de análisis complejos avanzados. Todos estos métodos se agrupan bajo el nombre de la combinatoria analítica.
Enfoques prácticos algoritmo
Los algoritmos desarrollados tienen estrategias para resolver problemas:
Algoritmo voraz: un primer algoritmo a menudo puede ser sugerido por el estudio del problema de forma muy gradual: resolvemos cada sub-problema esperando localmente que todos sus resultados consisten así una solución del problema global. Esto se llama algoritmo voraz. El algoritmo codicioso es a menudo un primer paso para escribir un algoritmo más eficiente.
Divide y vencerás: para mejorar el rendimiento de los algoritmos, una técnica común es dividir los datos de un problema en subconjuntos de tamaños más pequeños, para obtener datos que el algoritmo se puede tratar caso por caso. Un segundo paso en estos algoritmos es de «fusionar» los resultados parciales en una solución global. Estos algoritmos se asocian a menudo con la recursividad.
Búsqueda exhaustiva (o combinatoria): un método que utiliza la enorme potencia de cálculo de los ordenadores es de mirar a todos los casos posibles. Esto es tan lejos posible en casos especiales (combinatoria es a menudo más fuerte que el enorme poder de las computadoras, tan enorme como lo es)
aleatoria o por ensayo y error: algunos algoritmos utilizan registros al azar, o aproximaciones sucesivas, dando mejores resultados (en promedio) que la investigación directa o explícita.
Descomposición de arriba hacia abajo / abajo hacia arriba: la descomposición de arriba hacia abajo son para tratar de romper el problema en sub-problemas para resolver sucesivamente su descomposición hasta problemas triviales más fáciles de resolver. El algoritmo en general se da entonces por los algoritmos compuesto definido durante la descomposición. El enfoque de abajo arriba es el enfoque opuesto, que se basa en algoritmos simples, la solución de una sola fase del problema, tratando de componer para un algoritmo global.
Pre procesamiento / post-procesamiento: a veces algunos algoritmos tienen una o dos fases identificadas como pre-tratamientos (que hacer antes de que el algoritmo principal) o post-procesado (que hacer después de que el algoritmo principal), para simplificar escritura del algoritmo general.
Heurística
Para algunos problemas, los algoritmos tienen una complejidad muy grande para sacar un buen resultado en un tiempo razonable, incluso si pudiéramos utilizar un potencial de cálculo fenomenal. Por tanto, es necesario buscar la solución que más se aproxime a una solución óptima de un proceso de ensayo y error. Puesto que todas las combinaciones no pueden ser probadas, se deben hacer algunas decisiones estratégicas. Estas elecciones de las de cisiones constituyen lo que se llama una heurística. El propósito de una heurística no es tratar todas las combinaciones posibles de encontrar una que se encuentra con el problema, pero encontrar una solución aproximada adecuada (que puede ser cierto en algunos casos) en un plazo razonable. Así, el programa de ajedrez o juego de go (por nombrar sólo algunos) llamar heurística tan comunes que modelan la experiencia de un jugador. Algunos programas antivirus también se basan en la heurística para reconocer los virus informáticos que no figuran en su base, sobre la base de similitudes con los virus conocidos.