Algoritmo ( lat. algoritmi - en nombre del matemático de Asia Central Al-Khwarizmi [1] ) es un conjunto finito de reglas definidas con precisión para resolver una determinada clase de problemas o un conjunto de instrucciones que describen el procedimiento para que el ejecutante resuelva un problema específico. problema. En la interpretación anterior, se usaba la palabra "secuencia" en lugar de la palabra "orden", pero a medida que se desarrolló el paralelismo en el trabajo de las computadoras , la palabra "secuencia" comenzó a ser reemplazada por la palabra más general "orden". Las instrucciones independientes pueden ejecutarse en un orden arbitrario, en paralelo, si los ejecutores utilizados lo permiten.
Anteriormente en ruso escribieron "algori f m", ahora esta ortografía rara vez se usa, pero sin embargo, hay una excepción ( algoritmo normal de Markov ).
A menudo, una computadora actúa como ejecutor, pero el concepto de algoritmo no se refiere necesariamente a programas de computadora ; por ejemplo, una receta claramente descrita para preparar un plato también es un algoritmo, en cuyo caso el ejecutor es una persona (o tal vez algún mecanismo, por ejemplo, una tejeduría o un torno con control numérico ).
Es posible destacar los algoritmos computacionales (más adelante nos referiremos principalmente a ellos) y los de control . Los algoritmos computacionales, de hecho, transforman algunos datos iniciales en resultados, realizando el cálculo de alguna función. La semántica de los algoritmos de control puede diferir significativamente y reducirse a emitir las acciones de control necesarias en momentos determinados o como respuesta a eventos externos (en este caso, a diferencia de un algoritmo computacional, el algoritmo de control puede permanecer correcto para una ejecución infinita).
El concepto de algoritmo se refiere a los conceptos originales, básicos y básicos de las matemáticas. Los procesos computacionales de naturaleza algorítmica (operaciones aritméticas sobre números enteros, encontrar el máximo común divisor de dos números, etc.) son conocidos por la humanidad desde la antigüedad. Sin embargo, de forma explícita, el concepto de algoritmo se formó solo a principios del siglo XX.
La formalización parcial del concepto de algoritmo comenzó con los intentos de resolver el problema de resolución ( en alemán: Entscheidungsproblem ), que fue formulado por David Hilbert en 1928 . Los siguientes pasos de formalización fueron necesarios para definir el cálculo eficiente [2] o "método eficiente" [3] ; dichas formalizaciones incluyen las funciones recursivas de Gödel - Herbrran - Kleene de 1930 , 1934 y 1935 , el cálculo λ de Alonzo Church de 1936 , la Formulación 1 de Emil Post de 1936 y la máquina de Turing .
La definición formal moderna de un algoritmo computacional se dio en los años 30-50 del siglo XX en los trabajos de Turing , Post , Church ( tesis de Church-Turing ), N. Wiener , A. A. Markov .
La misma palabra "algoritmo" proviene del nombre del científico persa ( Khorezm y Maverannakhr ) al-Khorezmi . Alrededor de 825, escribió la obra Kitab al-jabr wal-muqabala ("El libro de la suma y la resta"), de cuyo título original proviene la palabra " álgebra " (al-jabr - finalización). En este libro, por primera vez, dio una descripción del sistema de numeración decimal posicional inventado en la India. El original persa del libro no ha sobrevivido. Al-Khwarizmi formuló las reglas para computar en el nuevo sistema y probablemente por primera vez usó el número 0 para indicar una posición faltante en la notación de un número (los árabes tradujeron su nombre indio como as-sifr o simplemente sifr , de ahí las palabras como "dígito" y "cifrado"). Casi al mismo tiempo, otros eruditos árabes comenzaron a usar números indios.
En la primera mitad del siglo XII, el libro de al-Khwarizmi en traducción latina penetró en Europa. El traductor, cuyo nombre no ha llegado hasta nosotros, le dio el nombre de Algoritmi de numero Indorum ("Algoritmos sobre el relato indio"); por lo tanto, el nombre latinizado del científico de Asia Central se colocó en el título del libro. Hoy se cree que la palabra "algoritmo" llegó a los idiomas europeos precisamente por esta traducción. Durante los siguientes siglos, aparecieron muchos otros trabajos dedicados al mismo tema: enseñar el arte de contar con números, y todos ellos tenían la palabra algoritmi o algorismi en el título .
Los autores posteriores no sabían nada sobre al-Khwarizmi, pero dado que la primera traducción del libro comienza con las palabras: "Dixit algorizmi: ..." ("Al-Khwarizmi dijo: ..."), todavía asociaron esta palabra con el nombre de una persona en particular. La versión sobre el origen griego del libro era muy común. En un manuscrito anglo-normando del siglo XIII , escrito en verso, leemos:
El algoritmo fue inventado en Grecia .
Esto es parte de la aritmética . Fue inventado por un maestro llamado Algorismo, quien le dio su nombre. Y como su nombre era Algorismo,
Llamó a su libro Algorismo.
Alrededor de 1250, el astrónomo y matemático inglés John of Sacrobosco escribió Algorismus vulgaris sobre aritmética , que se convirtió en el principal libro de texto sobre cálculos en notación posicional decimal en muchas universidades europeas durante siglos. En la introducción, Sacrobosco nombra a un sabio llamado Algus como el autor de la ciencia de contar . Y en el popular poema medieval " El romance de la rosa " (1275-1280) de Jean de Meun , el "filósofo griego Algus" se pone a la par con Platón , Aristóteles , Euclides y Ptolomeo . También hubo una ortografía del nombre Argus ( Argus ). Y aunque, según la mitología griega antigua, el barco Argo fue construido por Jason , la construcción del barco se atribuyó a este Argo.
El "maestro Algus" (o Argus) se convirtió en la personificación del arte de contar en la literatura medieval. Y en el ya mencionado “Romano de la Rosa”, y en el famoso poema italiano “La Flor”, escrito por Durante , hay fragmentos que dicen que ni el “mestre Argus” podrá contar cuantas veces los amantes se pelean y se pelean. hacer las paces. El poeta inglés Geoffrey Chaucer en el poema " El libro de la duquesa " ( 1369 ) escribe que incluso "el glorioso contador Argus" (noble countour Argu) no podrá contar los monstruos que aparecieron en visiones de pesadilla al héroe.
Sin embargo, con el tiempo, los matemáticos se interesaron cada vez menos por tales explicaciones, y la palabra algorismo (o algorismus ), que invariablemente estaba presente en los títulos de las obras matemáticas, adquirió el significado de una forma de realizar operaciones aritméticas utilizando números arábigos, que es, en papel, sin usar ábaco . Es en este sentido que entró en muchas lenguas europeas . Por ejemplo, marcado como "obsoleto". está presente en el diccionario representativo del idioma inglés Webster's New World Dictionary , publicado en 1957. El Diccionario Enciclopédico de Brockhaus y Efron ofrece la siguiente interpretación: el algoritmo (por cierto, antes de la revolución, se usaba la ortografía algoritmo , mediante fita ) se produce "de la palabra árabe Al-Goremm, que es raíz".
El algoritmo es el arte de contar con números, pero al principio la palabra "número" se refería solo a cero. El famoso truver francés Gautier de Coincy (Gautier de Coincy, 1177-1236) en uno de sus poemas utilizó las palabras algorismus-cipher (que significaba el número 0) como metáfora para caracterizar a una persona absolutamente inútil. Obviamente, la comprensión de tal imagen requirió la preparación adecuada de los oyentes, lo que significa que el nuevo sistema numérico ya era bastante conocido por ellos.
Durante muchos siglos, el ábaco fue en realidad el único medio para los cálculos prácticos; fue utilizado por comerciantes, cambistas y científicos. Los méritos de los cálculos en un tablero de conteo fueron explicados en sus escritos por un pensador tan destacado como Herbert de Avrilaksky (938-1003), quien se convirtió en Papa en 999 con el nombre de Silvestre II. Lo nuevo se abrió camino con gran dificultad, y la historia de las matemáticas incluyó una obstinada oposición entre los campos de los algorismistas y los abacistas (a veces llamados herbekists), que defendían el uso del ábaco en lugar de los números arábigos para los cálculos. Curiosamente, el famoso matemático francés Nicolás Chuquet (Nicolas Chuquet, 1445-1488) fue inscrito en el registro de contribuyentes de la ciudad de Lyon como algorítmico (algoriste). Pero pasó más de un siglo antes de que finalmente se estableciera el nuevo método de conteo, por lo que se requirió mucho tiempo para desarrollar notaciones generalmente reconocidas, mejorar y adaptar los métodos de cálculo para escribir en papel. En Europa occidental, a los profesores de aritmética se les siguió llamando “maestros del ábaco” hasta el siglo XVII , como, por ejemplo, el matemático Niccolò Tartaglia (1500-1557).
Así, los escritos sobre el arte de contar se llamaron Algoritmos . De los muchos cientos, se pueden destacar algunos tan inusuales como el tratado Carmen de Algorismo (latín carmen y significa poesía) escrito en verso por Alexander de Villa Dei (m. 1240) o el libro de texto del astrónomo y matemático vienés George Purbach ( Georg Peurbach, 1423-1461) Opus algorismi jocundissimi ("Un ensayo muy divertido sobre el algoritmo").
Poco a poco, el significado de la palabra se amplió. Los científicos comenzaron a aplicarlo no solo a procedimientos puramente computacionales, sino también a otros procedimientos matemáticos. Por ejemplo, alrededor de 1360, el filósofo francés Nicolaus Oresme (1323/25-1382) escribió el tratado matemático Algorismus proporcioneum ("Cálculo de proporciones"), en el que utilizó por primera vez potencias con exponentes fraccionarios y, de hecho, se acercó a la idea de logaritmos Cuando el ábaco fue sustituido por la llamada cuenta sobre las líneas, numerosos manuales sobre él comenzaron a denominarse Algorithmus linealis , es decir, las reglas para contar sobre las líneas.
Puede prestar atención al hecho de que después de un tiempo la forma original algorismi perdió la última letra, y la palabra adquirió una forma más conveniente para la pronunciación europea algorism . Más tarde, a su vez, sufrió una distorsión, muy probablemente asociada con la palabra aritmética .
En 1684, Gottfried Leibniz , en Nova Methodvs pro maximis et minimis, itemque tangentibus... , utilizó por primera vez la palabra "algoritmo" ( Algorithmo ) en un sentido aún más amplio: como una forma sistemática de resolver problemas de cálculo diferencial.
En el siglo XVIII , en uno de los diccionarios matemáticos alemanes, el Vollstandiges mathematisches Lexicon (publicado en Leipzig en 1747 ), el término algoritmo se sigue explicando como el concepto de cuatro operaciones aritméticas. Pero este significado no era el único, pues la terminología de la ciencia matemática en aquellos días aún se estaba formando. En particular, la expresión algoritmo infinitesimal se aplicó a formas de realizar operaciones en valores infinitesimales. La palabra algoritmo también fue utilizada por Leonard Euler , una de cuyas obras se titula “Usando un nuevo algoritmo para resolver el problema de Pell” ( De usu novi algoritmoi in problemate Pelliano solvendo ). Vemos que la comprensión de Euler del algoritmo como sinónimo del método de resolución del problema ya es muy cercana a la moderna.
Sin embargo, pasaron casi dos siglos más para que todos los significados antiguos de la palabra cayesen en desuso. Este proceso se puede rastrear con el ejemplo de la penetración de la palabra "algoritmo" en el idioma ruso.
Los historiadores fechan una de las listas del antiguo libro de texto de aritmética rusa, conocido como "Contar sabiduría", en 1691 . Esta obra se conoce en muchas versiones (las más antiguas son casi cien años más antiguas) y se remonta a manuscritos aún más antiguos del siglo XVI. Según ellos, se puede rastrear cómo el conocimiento de los números arábigos y las reglas para manejarlos se extendieron gradualmente en la Rus. El título completo de este libro de texto es “Este libro, hablado en aritmética helénica y griega, y en algorismo alemán, y en sabiduría de conteo numérico ruso”.
Por lo tanto, la palabra "algoritmo" fue entendida por los primeros matemáticos rusos de la misma manera que en Europa occidental. Sin embargo, no estaba en el famoso diccionario de V. I. Dahl , ni cien años después en el Diccionario explicativo de la lengua rusa, editado por D. N. Ushakov (1935). Pero la palabra "algoritmo" se puede encontrar en el popular Diccionario Enciclopédico prerrevolucionario de los hermanos Granat , y en la primera edición de la Gran Enciclopedia Soviética (BSE), publicada en 1926. Tanto allí como allí se interpreta de la misma manera. manera: por regla general, según el cual esto o aquello de cuatro operaciones aritméticas en el sistema numérico decimal. Sin embargo, a principios del siglo XX. para los matemáticos, la palabra "algoritmo" ya significaba cualquier proceso aritmético o algebraico realizado de acuerdo con reglas estrictamente definidas, y esta explicación también se da en ediciones posteriores de la TSB.
Los algoritmos se convirtieron en el tema de la creciente atención de los científicos, y gradualmente este concepto ocupó uno de los lugares centrales en las matemáticas modernas. En cuanto a las personas que están lejos de las matemáticas, a principios de los años cuarenta solo podían escuchar esta palabra mientras estudiaban en la escuela, en la combinación "Algoritmo de Euclides". A pesar de esto, el algoritmo todavía se percibía como un término puramente técnico, lo que se confirma por la ausencia de artículos relevantes en publicaciones menos voluminosas. En particular, ni siquiera está en la Pequeña Enciclopedia Soviética de diez volúmenes (1957), por no hablar de los diccionarios enciclopédicos de un volumen. Pero diez años después, en la tercera edición de la Gran Enciclopedia Soviética (1969), ya se caracteriza al algoritmo como una de las principales categorías de las matemáticas, “al no tener una definición formal en términos de conceptos más simples, y abstraído directamente de la experiencia. " Como podemos ver, ¡la diferencia incluso con la interpretación de la primera edición de la TSB es llamativa! Desde hace cuarenta años, el algoritmo se ha convertido en uno de los conceptos clave de las matemáticas, y la inclusión de la palabra ya no estaba en las enciclopedias, sino en los diccionarios. Por ejemplo, está presente en el Diccionario académico de la lengua rusa (1981) precisamente como un término del campo de las matemáticas.
Simultáneamente con el desarrollo del concepto de algoritmo, se produjo gradualmente su expansión desde las matemáticas puras a otras áreas. Y comenzó con la llegada de las computadoras, gracias a las cuales la palabra "algoritmo" entró en 1985 en todos los libros de texto escolares de informática y ganó una nueva vida. En general, podemos decir que su fama actual está directamente relacionada con el grado de distribución de los ordenadores. Por ejemplo, en el tercer volumen de la "Enciclopedia infantil" (1959), se habla mucho de las computadoras, pero aún no se han convertido en algo familiar y se perciben más bien como una especie de atributo de un futuro brillante, pero bastante lejano. En consecuencia, los algoritmos nunca se mencionan en sus páginas. Pero ya a principios de los 70. del siglo pasado, cuando las computadoras dejaron de ser una curiosidad exótica, la palabra "algoritmo" se está utilizando rápidamente. Esto está registrado con sensibilidad por las publicaciones enciclopédicas. En la " Enciclopedia de cibernética " (1974) en el artículo "Algoritmo" ya está asociado con la implementación en computadoras, y en la "Enciclopedia militar soviética" (1976) incluso un artículo separado "Algoritmo para resolver un problema en una computadora " aparece
Durante la última década y media o dos décadas, la computadora se ha convertido en un atributo integral de nuestra vida, el vocabulario informático se está volviendo cada vez más familiar. La palabra "algoritmo" es probablemente conocida por todos en estos días. Ingresó con confianza incluso al habla coloquial, y hoy en día a menudo nos encontramos en los periódicos y escuchamos en los discursos de los políticos expresiones como "algoritmo de comportamiento", "algoritmo de éxito" o incluso "algoritmo de traición". El académico N. N. Moiseev llamó a su libro "Algoritmos de desarrollo", y el famoso médico N. M. Amosov lo llamó "Algoritmo de salud" y "Algoritmos mentales". Y esto significa que la palabra vive, enriqueciéndose con nuevos significados y matices semánticos.
Varias definiciones del algoritmo, explícita o implícitamente, contienen el siguiente conjunto de requisitos generales:
Diversos problemas teóricos de las matemáticas y la aceleración del desarrollo de la física y la tecnología ponen en el orden del día una definición precisa del concepto de algoritmo.
Los primeros intentos de clarificar el concepto de algoritmo y su investigación fueron realizados en la primera mitad del siglo XX por Alan Turing , Emil Post , Jacques Herbrand , Kurt Gödel , A. A. Markov , Alonzo Church . Se desarrollaron varias definiciones del concepto de algoritmo, pero posteriormente se encontró que todas definen el mismo concepto (ver la tesis de Church-Turing ) [6]
El matemático ruso, el fundador de la lingüística estructural en la Unión Soviética V. A. Uspensky creía que el concepto de algoritmo apareció por primera vez en Emil Borel en 1912, en un artículo sobre una integral definida. Allí escribió sobre “cálculos que realmente se pueden realizar”, al tiempo que subraya: “Dejo de lado deliberadamente la actividad más o menos práctica; la esencia aquí es que cada una de estas operaciones es factible en un tiempo finito con la ayuda de un método confiable e inequívoco” [7] .
Máquina de TuringLa idea básica detrás de la máquina de Turing es muy simple. Una máquina de Turing es una máquina abstracta (autómata) que funciona con una cinta de celdas individuales en las que se escriben caracteres. La máquina también tiene un cabezal para escribir y leer caracteres de las celdas, que pueden moverse a lo largo de la cinta. En cada paso, la máquina lee un carácter de la celda a la que apunta el cabezal y, basándose en el carácter leído y el estado interno, da el siguiente paso. En este caso, la máquina puede cambiar su estado, escribir otro carácter en la celda o mover la cabeza una celda a la derecha oa la izquierda. [ocho]
A partir del estudio de estas máquinas, se planteó la tesis de Turing (principal hipótesis de los algoritmos):
Existe algún algoritmo para encontrar los valores de una función dados en algún alfabeto si y solo si la función es evaluable por Turing, es decir, cuando se puede calcular en una máquina de Turing.
Esta tesis es un axioma, un postulado, y no puede probarse por métodos matemáticos, ya que el algoritmo no es un concepto matemático exacto.
Funciones recursivasCada algoritmo se puede asociar con una función que calcula. Sin embargo, surge la pregunta de si es posible asociar una máquina de Turing con una función arbitraria y, de no ser así, ¿para qué funciones existe un algoritmo? La investigación sobre estos temas condujo a la creación en la década de 1930 de la teoría de las funciones recursivas [9] .
La clase de funciones computables se escribió en una imagen que se asemejaba a la construcción de alguna teoría axiomática basada en un sistema de axiomas. Primero, se eligieron las funciones más simples, cuyo cálculo es obvio. Luego se formularon las reglas (operadores) para construir nuevas funciones a partir de las existentes. La clase necesaria de funciones consta de todas las funciones que se pueden obtener de la aplicación más simple de operadores.
Similar a la tesis de Turing en la teoría de las funciones computables, se planteó una conjetura, que se denomina tesis de Church :
Una función numérica es algorítmicamente evaluable si y solo si es parcialmente recursiva.
La demostración de que la clase de funciones computables coincide con las funciones calculables de Turing se realiza en dos pasos: primero, se prueba el cálculo de las funciones más simples en una máquina de Turing, y luego el cálculo de las funciones obtenidas mediante la aplicación de operadores.
Así, informalmente, un algoritmo puede definirse como un sistema claro de instrucciones que define un proceso determinista discreto que conduce desde los datos iniciales (en la entrada) hasta el resultado deseado (en la salida), si existe, en un número finito de pasos; si el resultado deseado no existe, el algoritmo nunca termina o llega a un callejón sin salida.
Algoritmo normal (algoritmo) MarkovUn algoritmo normal (algoritmo en la escritura del autor) de Markov es un sistema de sucesivas aplicaciones de sustituciones que implementan ciertos procedimientos para obtener nuevas palabras a partir de las bases, construidas a partir de los caracteres de un determinado alfabeto. Al igual que una máquina de Turing, los algoritmos normales no realizan los cálculos por sí mismos: solo realizan transformaciones de palabras reemplazando letras de acuerdo con reglas dadas [10] .
Una función normalmente computable es una función que puede implementarse mediante un algoritmo normal. Es decir, un algoritmo que convierte cada palabra del conjunto de datos válidos de la función en sus valores iniciales [11] ..
El creador de la teoría de los algoritmos normales A. A. Markov presentó una hipótesis, que se denominó principio de normalización de Markov:
Para encontrar los valores de una función dada en algún alfabeto, si y solo si hay algún algoritmo, cuando la función es normalmente enumerable.
Al igual que las tesis de Turing y Church, el principio de normalización de Markov no puede probarse por medios matemáticos.
Sin embargo, la definición formal anterior del algoritmo puede ser demasiado estricta en algunos casos. A veces es necesario utilizar variables aleatorias [12] . Un algoritmo cuyo funcionamiento está determinado no solo por los datos iniciales, sino también por los valores obtenidos del generador de números aleatorios se denomina estocástico (o randomizado, del inglés random algoritmo ) [13] . Los algoritmos estocásticos suelen ser más eficientes que los deterministas y, en algunos casos, la única forma de resolver un problema [12] .
En la práctica, en lugar de un generador de números aleatorios, se utiliza un generador de números pseudoaleatorios .
Sin embargo, se debe distinguir entre algoritmos estocásticos y métodos que dan un resultado correcto con una alta probabilidad. A diferencia del método , el algoritmo da resultados correctos incluso después de un largo plazo.
Algunos investigadores admiten la posibilidad de que el algoritmo estocástico dé un resultado incorrecto con alguna probabilidad predeterminada. Entonces los algoritmos estocásticos se pueden dividir en dos tipos [14] :
Para algunas tareas, las formalizaciones mencionadas anteriormente pueden dificultar la búsqueda de soluciones y la realización de investigaciones. Para superar los obstáculos, se desarrollaron ambas modificaciones de los esquemas "clásicos" y se crearon nuevos modelos del algoritmo. En particular, se puede nombrar:
Los tipos de algoritmos como medios lógicos y matemáticos reflejan los componentes indicados de la actividad humana y las tendencias, y los propios algoritmos, según el objetivo, las condiciones iniciales del problema y las formas de resolverlo. Cabe destacar la diferencia fundamental entre los algoritmos de naturaleza computacional que convierten algunos datos de entrada en datos de salida (es su formalización que las mencionadas máquinas de Turing, Post, PAM, algoritmos normales de Markov y funciones recursivas) y los algoritmos interactivos (Turing ya tiene una máquina C, de la opción inglesa , una opción que espera influencia externa, en contraste con la máquina A clásica, donde todos los datos iniciales se dan antes del comienzo del cálculo y los datos de salida no están disponibles hasta el final de el cálculo). Estos últimos están diseñados para interactuar con algún objeto de control y están diseñados para asegurar la correcta emisión de acciones de control dependiendo de la situación actual, reflejadas por las señales provenientes del objeto de control [15] [16] . En algunos casos, el algoritmo de control no prevé en absoluto la finalización del trabajo (por ejemplo, mantiene un ciclo interminable de espera de eventos ante los que se emite una reacción adecuada), a pesar de que esto es completamente correcto.
Los algoritmos también se pueden distinguir:
La numeración de los algoritmos juega un papel importante en su estudio y análisis [18] . Dado que cualquier algoritmo se puede especificar como una palabra finita (representada como una secuencia finita de símbolos de algún alfabeto), y el conjunto de todas las palabras finitas en un alfabeto finito es contable , entonces el conjunto de todos los algoritmos también es contable. Esto significa la existencia de un mapeo uno a uno entre el conjunto de números naturales y el conjunto de algoritmos, es decir, la posibilidad de asignar un número a cada algoritmo.
La numeración de algoritmos es al mismo tiempo la numeración de todas las funciones calculadas algorítmicamente, y cualquier función puede tener una cantidad infinita de números.
La existencia de la numeración hace posible trabajar con algoritmos de la misma forma que con números. La numeración es especialmente útil en el estudio de algoritmos que funcionan con otros algoritmos.
La formalización del concepto de algoritmo permitió investigar la existencia de problemas para los que no existen algoritmos de solución. Posteriormente, se demostró la imposibilidad de cálculo algorítmico de soluciones a una serie de problemas, lo que imposibilita su resolución en cualquier dispositivo informático. Una función se llama computable si hay una máquina de Turing que calcula el valor de todos los elementos del conjunto de definición de la función. Si tal máquina no existe, se dice que la función no es computable. La función se considerará no computable incluso si hay máquinas de Turing capaces de calcular un valor para un subconjunto del conjunto completo de entradas [19] .
El caso en que el resultado de la evaluación de una función es la expresión lógica "verdadero" o "falso" (o el conjunto {0, 1}) se denomina problema que puede ser solucionable o irresoluble, dependiendo de la computabilidad de la función [19] .
Es importante especificar con precisión el conjunto permitido de datos de entrada, ya que un problema puede ser solucionable para un conjunto e irresoluble para otro.
Uno de los primeros problemas en los que se demostró la insolubilidad es el problema de la detención . Está formulado de la siguiente manera:
Dada una descripción del programa para una máquina de Turing, se requiere determinar si el programa termina en un tiempo finito o se ejecuta indefinidamente dada alguna entrada. [veinte]
La prueba de la insolubilidad del problema de la detención es importante porque a ella se pueden reducir otros problemas. Por ejemplo, un simple problema de detención puede reducirse a un problema de detención en una línea vacía (cuando necesita determinar para una máquina de Turing dada si se detendrá cuando se inicia en una línea vacía), demostrando así la indecidibilidad de esta última. [19] .
Junto con la difusión de la tecnología de la información, ha aumentado el riesgo de fallas en el software. Una de las formas de evitar errores en los algoritmos y sus implementaciones es probar la corrección de los sistemas por medios matemáticos.
El uso de aparatos matemáticos para el análisis de algoritmos y sus implementaciones se denomina métodos formales. Los métodos formales implican el uso de especificaciones formales y, por lo general, un conjunto de herramientas para analizar y probar las propiedades de las especificaciones. La abstracción de los detalles de implementación le permite establecer las propiedades del sistema independientemente de su implementación. Además, la precisión y unicidad de los enunciados matemáticos permite evitar la ambigüedad y la inexactitud de los lenguajes naturales [21] .
Según la hipótesis de Richard Mace, "evitar el error es mejor que eliminarlo" [22] . Según la conjetura de Hoare, "la prueba de programas resuelve el problema de corrección, documentación y compatibilidad" [23] . La prueba de la corrección de los programas nos permite revelar sus propiedades en relación con toda la gama de datos de entrada. Para ello, se dividió el concepto de corrección en dos tipos:
Durante la prueba de corrección, el texto del programa se compara con la especificación de la proporción deseada de datos de entrada y salida. Para las pruebas de tipo Hoare, la especificación toma la forma de declaraciones, que se denominan condiciones previas y posteriores. Junto con el propio programa, también se denominan triples Hoare . Estas declaraciones están escritas como
{P}Q{S}donde P son las condiciones previas que deben ser verdaderas antes de ejecutar el programa Q y S son las condiciones posteriores que son verdaderas después de que finaliza el programa.
Los métodos formales se han aplicado con éxito a una amplia gama de problemas, en particular: el desarrollo de circuitos electrónicos, inteligencia artificial, sistemas automáticos en el ferrocarril, verificación de microprocesadores , especificación de estándares y especificación y verificación de programas [24] .
Un criterio común para evaluar algoritmos es el tiempo de ejecución y el orden en que crece el tiempo de ejecución según la cantidad de datos de entrada. [25]
Para cada tarea específica, componen un cierto número, que se llama su tamaño. Por ejemplo, el tamaño de la tarea de calcular el producto de matrices puede ser el tamaño más grande de los factores de matriz, para tareas en gráficos, el tamaño puede ser el número de bordes del gráfico.
El tiempo que dedica un algoritmo en función del tamaño de la tarea se denomina complejidad temporal de ese algoritmo T ( n ). La asintótica del comportamiento de esta función a medida que aumenta el tamaño del problema se llama complejidad de tiempo asintótica, y se usa la notación "O" grande para denotarla . Por ejemplo, si un algoritmo procesa los datos de entrada en el tiempo cn² , donde c es una constante , entonces se dice que la complejidad temporal de dicho algoritmo es O ( n² ).
La complejidad asintótica es importante porque es una característica del algoritmo, y no de su implementación particular: al "optimizar" las operaciones, sin cambiar el algoritmo, solo se puede cambiar el coeficiente multiplicativo c , pero no las asintóticas. Como regla general, es la complejidad asintótica el factor principal que determina el tamaño de las tareas que el algoritmo puede procesar.
A menudo, durante el desarrollo de un algoritmo, se intenta reducir la complejidad del tiempo asintótico para los peores casos. En la práctica, hay casos en los que un algoritmo que "normalmente" se ejecuta rápido es suficiente.
En términos generales, el análisis de la complejidad del tiempo asintótico promedio se puede dividir en dos tipos: analítico y estadístico. El método analítico da resultados más precisos, pero es difícil de usar en la práctica. Pero el método estadístico le permite analizar rápidamente problemas complejos [26] .
La siguiente tabla enumera las complejidades asintóticas comunes con comentarios [27] .
Complejidad | Comentario | Ejemplos |
---|---|---|
( 1 ) | El tiempo de ejecución sostenible no depende del tamaño de la tarea | Tiempo de búsqueda esperado en una tabla hash |
O ( iniciar sesión ) | Crecimiento muy lento del tiempo requerido | Tiempo de ejecución esperado de una búsqueda de interpolación de n elementos |
O ( iniciar sesión ) | Crecimiento logarítmico: duplicar el tamaño de una tarea aumenta el tiempo de ejecución en una cantidad constante | Cálculo x n ; Búsqueda binaria en un arreglo de n elementos |
O ( n ) | Crecimiento lineal: duplicar el tamaño de la tarea duplicará el tiempo requerido | Suma/resta de números de n dígitos; Búsqueda lineal en un arreglo de n elementos |
O ( n registro n ) | Crecimiento lineal: duplicar el tamaño de la tarea duplicará ligeramente el tiempo requerido | Ordenar por combinación o un grupo de n elementos; ordenar el límite inferior haciendo coincidir n elementos |
O ( n² ) | Crecimiento cuadrático: duplicar el tamaño de la tarea cuadruplica el tiempo requerido | Algoritmos de clasificación elementales |
O ( n³ ) | Crecimiento cúbico: duplicar el tamaño de la tarea aumenta ocho veces el tiempo requerido | Multiplicación de matrices ordinarias |
O ( c n ) | Crecimiento exponencial: aumentar el tamaño de la tarea en 1 conduce a un aumento de c veces en el tiempo requerido; duplicar el tamaño de la tarea eleva al cuadrado el tiempo requerido | Algunos problemas del viajante de comercio , algoritmos de búsqueda de fuerza bruta |
Un algoritmo es una instrucción definida con precisión, aplicándola secuencialmente a los datos iniciales, puede obtener una solución al problema. Para cada algoritmo, existe un determinado conjunto de objetos que se pueden utilizar como datos de entrada. Por ejemplo, en el algoritmo para dividir números reales, el dividendo puede ser cualquier cosa y el divisor no puede ser igual a cero.
El algoritmo sirve, por regla general, para resolver no un problema específico, sino una cierta clase de problemas. Entonces, el algoritmo de suma es aplicable a cualquier par de números naturales. Esto expresa su propiedad de masa, es decir, la capacidad de aplicar repetidamente el mismo algoritmo para cualquier tarea de la misma clase.
Para el desarrollo de algoritmos y programas, se utiliza la algoritmización , el proceso de compilación sistemática de algoritmos para resolver problemas aplicados. La algoritmización se considera una etapa obligatoria en el proceso de desarrollo de programas y resolución de problemas en una computadora. Es para los algoritmos y programas aplicados que el determinismo, la eficiencia y el carácter masivo, así como la corrección de los resultados de resolver las tareas establecidas, son fundamentalmente importantes.
Un algoritmo es una instrucción clara y precisa para que el ejecutante realice una secuencia de acciones destinadas a lograr el objetivo.
Formas de notación de algoritmos:
Por lo general, al principio (a nivel de idea), el algoritmo se describe con palabras, pero a medida que se acerca a la implementación, adquiere más y más esquemas formales y formulación en un lenguaje comprensible para el ejecutante (por ejemplo, código de máquina ).
Aunque la definición del algoritmo requiere solo un número finito de pasos necesarios para lograr un resultado, en la práctica, la implementación de un gran número de pasos conduce a la ejecución a largo plazo de los programas y, por lo general, existen otras restricciones (sobre el tamaño de el programa, sobre las acciones permitidas). En este sentido, se introducen conceptos tales como la complejidad del algoritmo ( tiempo , tamaño del programa, computacional y otros).
Para cada tarea, puede haber muchos algoritmos que conduzcan a la meta. Aumentar la eficiencia de los algoritmos es uno de los problemas de la informática , desde la década de 1940, en relación con esto, se han construido una serie de algoritmos más asintóticamente eficientes para problemas tradicionales (por ejemplo, algoritmos de multiplicación rápida , algoritmo de Chudnovsky para calcular el número ).
El algoritmo de Euclides es un método eficiente para calcular el máximo común divisor (mcd). Nombrado en honor al matemático griego Euclides; uno de los algoritmos más antiguos todavía en uso [28] .
Descrito en los "Comienzos" de Euclides (alrededor del 300 a. C.), es decir, en los libros VII y X. En el séptimo libro, se describe un algoritmo para números enteros, y en el décimo, para la longitud de los segmentos.
Hay varias variantes del algoritmo, a continuación se muestra una versión recursiva escrita en pseudocódigo :
nodo de función (a, b) si b = 0 devuelve a de lo contrario devuelve nodo (b, a mod b)GCD de los números 1599 y 650:
Paso 1 | 1599 = 650*2 + 299 |
Paso 2 | 650 = 299*2 + 52 |
Paso 3 | 299 = 52*5 + 39 |
Paso 4 | 52 = 39*1 + 13 |
Paso 5 | 39 = 13*3 + 0 |
diccionarios y enciclopedias | ||||
---|---|---|---|---|
|