Se pueden desarrollar varios algoritmos diferentes para resolver el mismo problema. Por tanto, surge la tarea de elegir los algoritmos más eficaces. Tenga en cuenta que evaluar con precisión la eficacia de los algoritmos es una tarea muy difícil y, en cada caso concreto, requiere una investigación especial.

La parte de la teoría de los algoritmos que se ocupa de estimar las características de los algoritmos se llama métrica. Se puede dividir en descriptivo (cualitativo) y métrico (cuantitativo). El primero examina los algoritmos desde el punto de vista de la correspondencia que establecen entre los datos de entrada y los resultados. El segundo examina los algoritmos desde el punto de vista de la complejidad tanto de los algoritmos mismos como de los “cálculos” que especifican, es decir, los procesos de transformación secuencial de objetos estructurales. Es importante enfatizar que la complejidad de los algoritmos y los cálculos se puede determinar de varias maneras, y puede resultar que con un método el algoritmo A será más difícil EN, y con el otro método es al revés.

La mayoría de las veces, los algoritmos se evalúan según la memoria requerida, la cantidad de operaciones realizadas, el tiempo de solución o el error computacional. Estas características a menudo dependen de los parámetros (dimensiones) del problema y no son lineales. Por lo tanto, en la teoría de los algoritmos existe una dirección para evaluar la efectividad de los algoritmos mediante estimaciones asintóticas de funciones: memoria requerida, tiempo de cálculo, etc. En este caso, se determina el parámetro más significativo de la función y se estudia el comportamiento de la función a medida que aumentan los valores de los parámetros. En el curso del estudio, intentan determinar la naturaleza de la dependencia de los valores de las características del algoritmo considerado del parámetro. Puede ser lineal (es decir, proporcional al parámetro n), logarítmico (es decir, proporcional a log n), cuadrático (es decir, proporcional a n 2), etc. Al comparar las estimaciones asintóticas de algoritmos que resuelven el mismo problema, se puede elegir un algoritmo más eficiente. Dicen que el valor de algún parámetro T(n) es de orden n x si hay constantes positivas k y n o tales que para todo n³n o se cumple la desigualdad T(n) ≤ k n x.

Supongamos que n es la cantidad de datos numéricos recibidos en la entrada de varios algoritmos diferentes (A 1, A 2, A 3, A 4, A 5), que realizan cálculos a la misma velocidad: 1000 operaciones por segundo, pero tienen diferentes estimaciones asintóticas. La Tabla 1.8 muestra los valores de n que estos algoritmos pueden procesar en 1 segundo, 1 minuto y 1 hora (los valores se redondean hacia abajo al número entero más cercano). Los datos de la Tabla 1.3 muestran claramente que el rendimiento del algoritmo (es decir, el número de datos procesados ​​por unidad de tiempo) depende significativamente de la naturaleza de la función de evaluación asintótica.

Las pruebas de los algoritmos desarrollados generalmente se llevan a cabo con valores pequeños del parámetro n. Dichas pruebas le permiten ganar confianza en el rendimiento del algoritmo, pero no garantizan en absoluto la finalización de la tarea para valores grandes de n. Es posible que simplemente no tengamos suficiente memoria en la computadora o tiempo para resolver un problema real. Las estimaciones asintóticas son importantes en el sentido de que permiten estimar la suficiencia de los recursos informáticos para cálculos prácticos con límites de cambio conocidos en el parámetro n.

Eficiencia del algoritmo es una propiedad de un algoritmo que está asociada con los recursos computacionales utilizados por el algoritmo. El algoritmo debe analizarse para determinar los recursos requeridos por el algoritmo. La eficiencia del algoritmo puede considerarse análoga a la productividad de fabricación de procesos repetitivos o continuos.

Para lograr la máxima eficiencia, queremos reducir el uso de recursos. Sin embargo, diferentes recursos (como el tiempo y la memoria) no se pueden comparar directamente, por lo que cuál de los dos algoritmos se considera más eficiente a menudo depende de qué factor es más importante, como el requisito de alta velocidad, el uso mínimo de memoria u otra medida de eficiencia.

Fondo

Ada Lovelace enfatizó la importancia de la eficiencia con énfasis en el tiempo de ejecución en 1843 con respecto a la máquina analítica mecánica de Charles Babbage:

“En casi toda la informática, existe una gran variedad de configuraciones posibles para completar con éxito el proceso, y diferentes convenciones deberían influir en la elección a efectos de realizar el cálculo. Lo esencial es elegir una configuración que permita minimizar el tiempo necesario para realizar el cálculo."

Las primeras computadoras electrónicas eran muy limitadas tanto en velocidad como en memoria. En algunos casos, se ha descubierto que existe un equilibrio entre tiempo y memoria, en el que una tarea debe utilizar una gran cantidad de memoria para alcanzar una alta velocidad o utilizar un algoritmo más lento que utiliza una pequeña cantidad de memoria de trabajo. En este caso se utilizó el algoritmo más rápido para el cual la memoria disponible era suficiente.

Las computadoras modernas son mucho más rápidas que las primeras y tienen mucha más memoria (gigabytes en lugar de kilobytes). Sin embargo, Donald Knuth destaca que la eficiencia sigue siendo un factor importante:

"En disciplinas de ingeniería establecidas, una mejora del 12% es fácilmente alcanzable y nunca se ha considerado prohibitiva, y creo que lo mismo debería ser cierto en la programación".

Revisar

Un algoritmo se considera eficiente si su consumo de recursos (o costo de recursos) está en un nivel aceptable o por debajo de él. En términos generales, "aceptable" aquí significa "el algoritmo se ejecutará durante un período de tiempo razonable en una computadora disponible". Debido a que ha habido un aumento significativo en la potencia de procesamiento y la memoria disponible de las computadoras desde la década de 1950, el "nivel aceptable" actual no lo era ni siquiera hace 10 años.

Los fabricantes de computadoras lanzan periódicamente nuevos modelos, a menudo más potentes. Precio software puede ser bastante grande, por lo que en algunos casos es más fácil y económico obtener un mejor rendimiento comprando una computadora más rápida que sea compatible con su computadora actual.

Hay muchas formas de medir los recursos utilizados por un algoritmo. Las dos medidas más utilizadas son la velocidad y la memoria utilizada. Otras medidas pueden incluir velocidad de transferencia, uso temporal del disco, uso del disco a largo plazo, consumo de energía, costo total de propiedad, tiempo de respuesta a señales externas, etc. Muchas de estas mediciones dependen del tamaño de los datos de entrada del algoritmo (es decir, las cantidades que requieren procesamiento de datos). Las mediciones también pueden depender de la forma en que se presentan los datos (por ejemplo, algunos algoritmos de clasificación funcionan mal con datos ya ordenados o cuando los datos se clasifican en orden inverso).

En la práctica, existen otros factores que influyen en la eficacia del algoritmo, como la precisión y/o fiabilidad requerida. Como se explica a continuación, la forma en que se implementa un algoritmo también puede tener un efecto significativo en el rendimiento real, aunque muchos aspectos de la implementación son cuestiones de optimización.

Análisis teorico

EN Análisis teorico En algoritmos, es una práctica común estimar la complejidad de un algoritmo en su comportamiento asintótico, es decir, reflejar la complejidad del algoritmo en función del tamaño de la entrada. norte Se utiliza la notación O grande. Esta estimación es generalmente bastante precisa para grandes norte, pero puede llevar a conclusiones incorrectas en valores pequeños norte(Por lo tanto, la clasificación por burbujas, que se considera lenta, puede ser más rápida que la clasificación rápida si solo necesita ordenar unos pocos elementos).

Pruebas de verificación: medición del rendimiento

Para nuevas versiones de software o para comparar con sistemas rivales, a veces se utilizan puntos de referencia para comparar el rendimiento relativo de los algoritmos. Si, por ejemplo, se lanza un nuevo algoritmo de clasificación, se puede comparar con sus predecesores para garantizar que el algoritmo sea al menos tan eficiente en datos conocidos como los demás. Los usuarios pueden utilizar pruebas de rendimiento para comparar productos de diferentes fabricantes y evaluar qué producto se adaptará mejor a sus necesidades en términos de funcionalidad y rendimiento.

Algunas pruebas de referencia proporcionan un análisis comparativo de diferentes lenguajes de compilación e interpretación, como PC Benchmark Collection de Roy Longbottom y El juego de puntos de referencia del lenguaje informático compara el rendimiento de implementaciones de tareas típicas en algunos lenguajes de programación.

Problemas de implementación

Los problemas de implementación también pueden afectar el desempeño real. Esto incluye la elección del lenguaje de programación y la forma en que se codifica realmente el algoritmo, la elección del traductor para el lenguaje elegido o las opciones del compilador utilizadas, e incluso el tipo de Sistema operativo. En algunos casos, un lenguaje implementado como intérprete puede ser significativamente más lento que un lenguaje implementado como compilador.

Hay otros factores que pueden afectar el tiempo o el uso de la memoria que están fuera del control del programador. Esto incluye alineación de datos, detallando, recolección de basura , paralelismo a nivel de instrucción y llamada a subrutinas .

Algunos procesadores tienen la capacidad de realizar operaciones vectoriales, lo que permite que una operación procese múltiples operandos. Puede que sea fácil o no utilizar dichas funciones a nivel de programación o compilación. Los algoritmos diseñados para computación secuencial pueden requerir un rediseño completo para adaptarse a la computación paralela.

Otro problema puede surgir con la compatibilidad del procesador, donde las instrucciones pueden implementarse de manera diferente, de modo que las instrucciones en algunos modelos pueden ser relativamente más lentas en otros modelos. Esto puede ser un problema para el compilador de optimización.

Medición del uso de recursos

Las medidas suelen expresarse en función del tamaño de la entrada. norte.

Las dos dimensiones más importantes son:

• Tiempo: Cuánto tiempo tarda el algoritmo en la CPU.
• Memoria: Cuánta memoria de trabajo (normalmente RAM) se necesita para el algoritmo. Hay dos aspectos de esto: la cantidad de memoria para el código y la cantidad de memoria para los datos con los que opera el código.

Para ordenadores que funcionan con baterías (como los portátiles) o para cálculos muy largos/grandes (como los superordenadores), resulta interesante un tipo diferente de medición:

• Consumo directo de energía: Energía necesaria para hacer funcionar una computadora.
• Consumo de energía indirecto: Energía necesaria para refrigeración, iluminación, etc.

En algunos casos, se necesitan otras medidas menos comunes:

• Tamaño del engranaje: El ancho de banda puede ser el factor limitante. La compresión se puede utilizar para reducir la cantidad de datos transferidos. Mostrar un gráfico o una imagen (como el logotipo de Google) puede generar la transferencia de decenas de miles de bytes (48 K en este caso). Compare esto con la transmisión de los seis bytes de la palabra "Google".
• Memoria externa: Memoria requerida en un disco u otro dispositivo de almacenamiento externo. Esta memoria se puede utilizar para almacenamiento temporal o para uso futuro.
• Tiempo de respuesta: Esta configuración es especialmente importante para aplicaciones en tiempo real donde la computadora debe responder rápidamente a eventos externos.
• Costo total de la propiedad: El parámetro es importante cuando se pretende ejecutar un solo algoritmo.

Tiempo

Teoría

Este tipo de prueba también depende significativamente de la elección del lenguaje de programación, del compilador y de sus opciones, por lo que los algoritmos comparados deben implementarse en las mismas condiciones.

Memoria

Esta sección trata del uso de la memoria principal (a menudo RAM) que necesita el algoritmo. Al igual que con el análisis de tiempo anterior, el análisis de un algoritmo normalmente utiliza complejidad espacial del algoritmo para estimar la memoria de tiempo de ejecución requerida en función del tamaño de entrada. El resultado suele expresarse en términos de "O" grande.

Hay cuatro aspectos del uso de la memoria:

• La cantidad de memoria necesaria para almacenar el código del algoritmo.
• La cantidad de memoria requerida para los datos de entrada.
• La cantidad de memoria necesaria para cualquier salida (algunos algoritmos, como las clasificaciones, reorganizan con frecuencia la entrada y no requieren memoria adicional para la salida).
• La cantidad de memoria requerida por el proceso computacional durante el cálculo (esto incluye variables con nombre y cualquier espacio de pila requerido para llamadas a subrutinas, lo que puede ser significativo cuando se usa recursividad).

Las primeras computadoras electrónicas y las computadoras domésticas tenían capacidades de memoria de trabajo relativamente pequeñas. Así, en 1949 el EDSAC tenía una memoria de trabajo máxima de 1024 palabras de 17 bits, y en 1980 se lanzó el Sinclair ZX80 con 1024 bytes de memoria de trabajo.

Las computadoras modernas pueden tener cantidades relativamente grandes de memoria (quizás gigabytes), por lo que comprimir la memoria utilizada por un algoritmo en una cantidad determinada de memoria es menos necesario que antes. Sin embargo, es significativa la existencia de tres categorías diferentes de memoria:

• Caché (a menudo RAM estática): se ejecuta a velocidades comparables a las de la CPU
• Memoria física principal (a menudo RAM dinámica): funciona ligeramente más lento que la CPU
• Memoria virtual (a menudo en disco): da la ilusión de una memoria enorme, pero funciona miles de veces más lento que la RAM.

Un algoritmo cuya memoria requerida cabe en la memoria caché de la computadora es mucho más rápido que un algoritmo que cabe en la memoria principal, que, a su vez, será mucho más rápido que un algoritmo que utiliza espacio virtual. Para complicar las cosas, algunos sistemas tienen hasta tres niveles de caché. Diferentes sistemas tienen diferentes cantidades de estos tipos de memoria, por lo que el efecto de la memoria en un algoritmo puede variar significativamente de un sistema a otro.

En los primeros tiempos de la informática electrónica, si un algoritmo y sus datos no cabían en la memoria principal, no se podía utilizar. Hoy en día, el uso de memoria virtual proporciona una memoria masiva, pero a costa del rendimiento. Si el algoritmo y sus datos caben en la caché, se puede lograr una velocidad muy alta, por lo que minimizar la memoria requerida ayuda a minimizar el tiempo. Un algoritmo que no encaja completamente en el caché, pero proporciona localidad de enlaces, puede funcionar relativamente rápido.

Ejemplos de algoritmos efectivos

Críticas al estado actual de la programación

Los programas se vuelven más lentos más rápidamente de lo que las computadoras se vuelven más rápidas.

En sistemas generalizados, reducir a la mitad la ejecución de instrucciones puede duplicar la duración de la batería, y los macrodatos brindan una oportunidad para mejores algoritmos: reducir el número de operaciones de N x N a N x log(N) tiene un fuerte efecto para N grandes... Para N =30 mil millones, estos cambios son similares a 50 años de mejoras tecnológicas.

Competencia por el mejor algoritmo.

Los siguientes concursos invitan a participar en el desarrollo de los mejores algoritmos, cuyos criterios de calidad son determinados por los jueces:

ver también

• La codificación aritmética es un tipo de codificación de entropía. con longitud de código variable para una compresión de datos eficiente
• Una matriz asociativa es una estructura de datos que puede volverse más eficiente cuando se usa. árboles PATRICIA o matrices judy
• Prueba de rendimiento: un método para medir el tiempo de ejecución comparativo en ciertos casos
• Mejor, peor y promedio de los casos- convenciones para estimar el tiempo de ejecución para tres escenarios
• La búsqueda binaria es una técnica sencilla y eficaz para buscar en una lista ordenada
• mesa auxiliar

Enviar su buen trabajo en la base de conocimientos es sencillo. Utilice el siguiente formulario

Los estudiantes, estudiantes de posgrado y jóvenes científicos que utilicen la base de conocimientos en sus estudios y trabajos le estarán muy agradecidos.

Aún no existe una versión HTML de la obra.
Puedes descargar el archivo de la obra haciendo clic en el siguiente enlace.

Documentos similares

Descripción del modelo formal del algoritmo basado en funciones recursivas. Desarrollo de un modelo analítico y de programa de un algoritmo para una máquina de reconocimiento de Turing. Desarrollo de un modelo analítico del algoritmo utilizando algoritmos normales de Markov.

trabajo del curso, añadido el 07/07/2013


El concepto de algoritmo y análisis de estimaciones teóricas de la complejidad temporal de los algoritmos de multiplicación de matrices. Análisis comparativo de la estimación de la complejidad temporal de algunas clases de algoritmos utilizando programación convencional y programación utilizando tecnología Open MP.

tesis, añadido el 12/08/2017


Concepto general algoritmo y medidas de su complejidad. Complejidad temporal y capacidad de los algoritmos. Métodos y técnicas básicos de análisis de complejidad. Optimización asociada con la elección del método para construir un algoritmo y con la elección de métodos para presentar datos en el programa.

resumen, añadido el 27/11/2012


El problema de mejorar la calidad de las huellas dactilares para aumentar la eficiencia de los algoritmos de autenticación biométrica. Revisión de algoritmos de procesamiento de imágenes de huellas dactilares. Análisis de un algoritmo basado en el uso de la transformada de Gabor.

tesis, agregada el 16/07/2014


Métodos para organizar el proceso informático en sistemas con múltiples procesadores. Desarrollo de un programa basado en algoritmos para sistemas multiprocesador para procesamiento por lotes de tareas. Cálculo de indicadores clave de rendimiento para cada algoritmo.

trabajo del curso, añadido el 21/06/2013


Estimación de la complejidad computacional del programa. Implementación del algoritmo de codificación de información de Huffman. Codificación de la prueba en árboles binarios y de Huffman. Código de caracteres binarios. El símbolo y frecuencia de su aparición en el texto. Cálculo de la complejidad del algoritmo.

prueba, agregada el 16/12/2012


La transición de una formulación verbal informal a una formulación matemática de este problema. Evaluar varias opciones para seleccionar las estructuras de datos y algoritmos de procesamiento más eficientes. Implementación de algoritmos en uno de los lenguajes de programación.

trabajo del curso, añadido el 25/06/2013

Principios fundamentales para crear algoritmos eficaces.

Cualquiera que desarrolle algoritmos debe dominar algunas técnicas y conceptos básicos. Cualquiera que alguna vez se enfrentara a una tarea difícil se enfrentaba a la pregunta: "¿Por dónde empezar?" Una forma posible es revisar su stock de métodos algorítmicos comunes para ver si alguno de ellos puede usarse para formular una solución a un nuevo problema. Bueno, si no existe tal reserva, ¿cómo se puede desarrollar un buen algoritmo? ¿Dónde empezar? Todos hemos tenido la experiencia frustrante de mirar una tarea y no saber qué hacer. Veamos tres técnicas generales de resolución de problemas que son útiles para desarrollar algoritmos.

Primer método asociado con la reducción de una tarea difícil a una secuencia de tareas más simples. Por supuesto, la esperanza es que los problemas más simples sean más fáciles de procesar que el problema original, y también que se pueda derivar una solución al problema original a partir de soluciones a estos problemas más simples. Este procedimiento se llama método de objetivos privados. Este método parece muy razonable. Pero como la mayoría de los métodos generales para resolver problemas o diseñar algoritmos, no siempre es fácil trasladarlos a un problema específico. Tomar decisiones inteligentes sobre problemas más fáciles es más un arte o una intuición que una ciencia. No existe un conjunto general de reglas para definir la clase de problemas que pueden resolverse utilizando este enfoque. Pensar en cualquier problema específico comienza con hacer preguntas. Se pueden establecer objetivos específicos cuando se responden las siguientes preguntas:

• 1. ¿Es posible solucionar parte del problema? ¿Es posible solucionar el resto del problema ignorando algunas condiciones?
• 2. ¿Es posible solucionar el problema para casos especiales? ¿Es posible desarrollar un algoritmo que produzca una solución que satisfaga todas las condiciones del problema, pero cuyos datos de entrada se limiten a algún subconjunto de todos los datos de entrada?
• 3. ¿Hay algo relacionado con el problema que no se comprende bien? Si intentamos profundizar en algunas de las características del problema, ¿podremos aprender algo que nos ayude a abordar una solución?
• 4. ¿Existe alguna solución conocida para un problema similar? ¿Es posible modificar su solución para solucionar el problema considerado? ¿Es posible que este problema sea equivalente a un problema conocido sin resolver?

Segundo método El desarrollo de algoritmos se conoce como método de elevación. El algoritmo de elevación comienza haciendo una suposición inicial o calculando una solución inicial al problema. Entonces comienza el movimiento ascendente más rápido posible desde la solución inicial hacia mejores soluciones. Cuando el algoritmo alcanza un punto desde el cual ya no es posible avanzar hacia arriba, se detiene. Desafortunadamente, no siempre es posible garantizar que la solución final obtenida por el algoritmo de elevación sea óptima. Esta situación suele limitar el uso del método de elevación.

En general, los métodos de elevación se clasifican como “bruscos”. Recuerdan algún objetivo e intentan hacer todo lo que pueden, donde pueden, para acercarse a él. Esto los vuelve algo “miopes”. La miopía del método de elevación queda bien ilustrada con el siguiente ejemplo. Supongamos que necesitamos encontrar el máximo de una función. en =/(X), presentado por el gráfico (Fig. 2.15). Si el valor inicial del argumento x = un, entonces el método de ascenso dará aspiración a la meta más cercana, es decir, al valor de la función en el punto x = b, mientras que el verdadero máximo de esta función está en = c. En este caso

Arroz. 2.15. Una ilustración del método de elevación El método de elevación encuentra un máximo local, pero no global. Ésta es la "aspereza" del método de elevación.

Tercer método conocido como trabajando de nuevo, aquellos. El trabajo de este algoritmo comienza con un objetivo o solución a un problema y luego avanza hacia la formulación inicial del problema. Luego, si estas acciones son reversibles, se retrocede desde el planteamiento del problema hasta la solución.

Veamos los tres métodos en problema del jeep. Supongamos que necesita cruzar un desierto de 1.000 kilómetros en un jeep, utilizando un mínimo de combustible. El volumen del tanque de combustible del jeep es de 500 litros, el combustible se consume de manera uniforme, 1 litro por kilómetro. Al mismo tiempo, en el punto de partida hay un depósito de combustible ilimitado. Como no hay depósitos de combustible en el desierto, deberás instalar tus propios depósitos y llenarlos con combustible del depósito del coche. Entonces, la idea del problema es clara: hay que partir desde el punto de partida con el tanque lleno una cierta distancia, montar allí el primer almacén, dejar allí una cierta cantidad de combustible del tanque, pero suficiente para volver. En el punto de partida se vuelve a repostar todo el combustible y se intenta trasladar el segundo almacén hacia el desierto. Pero ¿dónde deberían instalarse esos almacenes y cuánto combustible debería almacenarse en cada uno de ellos?

Abordemos este problema utilizando el método de trabajo hacia atrás. ¿A qué distancia del final puedes cruzar el desierto con exactamente la misma cantidad de combustible? A tanques? Consideremos esta pregunta por A= 1,2, 3,... hasta que encontremos tal número entero PAG, Qué PAG Los tanques llenos te permiten cruzar todo el desierto de 1000 kilómetros. Para A= 1 respuesta es 500 km = 500 l (punto EN), como se muestra en la figura. 2.16.

Arroz. 2.16.

Puedes repostar tu coche en el punto EN y cruzar los 500 km restantes de desierto. Se fijó un objetivo especial porque el problema original no se puede resolver de inmediato.

pretendamos que A= 2, es decir Hay dos depósitos llenos (1000 l). Esta situación se ilustra en la Fig. 2.16. ¿Cuál es el valor máximo de jCj tal que, partiendo de 1000 litros de combustible desde el punto (500 - Xj), sea posible llevar suficiente combustible hasta el punto para completar el viaje, como en A= 1. Una forma de determinar un valor aceptable X ( es como sigue. Repostamos en el punto (500 - Xj), vamos X ( kilómetros al punto EN y verter todo el combustible en el depósito, excepto la parte que se requiere para regresar al punto (500 - Xj). En este punto el tanque queda vacío. Ahora llenamos el segundo tanque, conducimos Xj kilómetros hasta EN, recoger en EN combustible que queda allí, y de EN Nos vamos a C con el tanque lleno. La distancia total recorrida consta de tres segmentos a lo largo X ( kilómetros y un segmento Sol 500 kilómetros de largo. Por tanto, de la ecuación 3x t + 500 = 1000 encontramos su solución Xj = 500/3. Así, dos depósitos (1000 l) permiten recorrer Z > 2 = 500 +x( = 500(1+1/3) kilómetros.

Consideremos k = 3. ¿Desde qué punto se puede salir con 1500 litros de combustible para que el jeep entregue 1000 litros al punto (500 - x))? Encontremos el mayor valor de x 2 tal que, saliendo con 1500 litros de combustible del punto (500 - Xj - x 2), podamos entregar 1000 litros al punto (500 - Xj). Salimos del punto (500 - Xj - x 2), conducimos hasta (500 - x), trasvasamos todo el combustible menos x 2 litros y volvemos al punto (500 - Xj - x 2) con el depósito vacío. Repitiendo este procedimiento gastaremos 4x 2 litros en el recorrido y dejaremos (1000 - 4x 2) litros en el punto (500 - x L). Ahora en el punto (500 - Xj - x 2) quedan exactamente 500 litros. Repostamos los últimos 500 litros y nos dirigimos al punto (500 - Xj), habiendo gastado x 2 litros en este.

Estando en el punto (500 - Xj), gastamos 5x 2 litros de combustible en viaje. Aquí quedan un total de (1500 - 5x 2) litros. Esta cantidad debe ser igual a 1000 l, es decir x2 = 500/5. De esto concluimos que 1500 litros te permiten conducir.

Continuando el proceso de trabajar hacia atrás inductivamente, obtenemos que PAG Los tanques de combustible nos permiten pasar. Dn kilómetros, donde Dn = 500(1 +1/3 + 1/5 + ... + 1/(2PAG - 1)).

Necesitamos encontrar el valor más pequeño. PAG, en el cual Dn> 1000. Cálculos simples muestran que para norte = 7 tenemos ¿D?= 997,5 km, es decir siete depósitos, o 3.500 litros, de combustible te permitirán viajar

• 977,5 kilómetros. Un octavo depósito lleno: sería más que necesario para transportar 3.500 litros desde el punto A a un punto situado en
• 22,5 km (1000 - 977,5) desde A El lector tiene la oportunidad de comprobar de forma independiente que 337,5 litros son suficientes para suministrar 3500 litros de combustible hasta la marca de 22,5 km. Así, para cruzar el desierto de I a C en coche, se necesitan 3.837,5 litros de combustible.

Ahora el algoritmo de transporte de combustible se puede presentar de la siguiente manera. Empezamos desde A, teniendo 3837,5 litros. Aquí hay suficiente combustible para transportar gradualmente 3.500 litros hasta la marca.

22,5 km, donde el jeep acabará con el depósito vacío y con combustible suficiente para 7 repostajes completos. Este combustible es suficiente para transportar 3.000 litros hasta un punto situado a 22,5 + 500/13 km de A, donde el depósito del coche volverá a quedar vacío. El transporte posterior llevará el jeep a un punto situado a 22,5 + 500/13 + 500/11 km de A, con el depósito del coche vacío y 2500 l en almacén.

Siguiendo así avanzamos gracias al análisis realizado trabajando hacia atrás. Pronto el jeep recorrerá los 500 (1 - 1/3) kilómetros con 1.000 litros de combustible. Luego transportaremos 500 litros de combustible hasta el punto EN, Echemoslos en el tanque del auto y conduzcamos hasta el punto sin parar. CON(Figura 2.17).

Arroz. 2.17.

Para aquellos familiarizados con series infinitas, tenga en cuenta que D Hay PAG-ésima suma parcial de una serie armónica impar. Dado que esta serie diverge, el algoritmo permite cruzar cualquier desierto. Intente modificar este algoritmo para dejar suficiente combustible en varios puntos del desierto para regresar al punto A.

Surge la pregunta de si es posible recorrer 1.000 km con menos de 3.837,5 litros de combustible. Resulta que no puedes. La prueba de esta afirmación es bastante compleja. Sin embargo, se puede presentar el siguiente argumento, bastante plausible. Obviamente estamos actuando la mejor manera Para A= 1. Cuando A= 2 planes utilizados para A= 1 y luego se activa el segundo tanque de combustible para estar lo más lejos posible del punto EN. La premisa de partida para A tanques es que sabemos cómo actuar mejor en el caso de (A - 1) tanques, y retroceda lo más posible con la ayuda OMS tanque.

Entonces, en el problema considerado, el método de trabajar hacia atrás es que el problema se resuelve como si fuera desde el final; el método de los objetivos parciales es que no resuelven todo el problema de una vez, sino, por así decirlo, en partes; y, finalmente, el método de ascenso se manifiesta en el hecho de que la solución no se encuentra de inmediato, sino de forma secuencial, como acercándose a ella.

PREGUNTAS DE CONTROL

• 1. Definir un objeto, clase, sistema, modelo.
• 2. Nombra los principales tipos de modelos.
• 3. ¿Qué es el modelado de simulación?
• 4. ¿Qué clasificaciones de modelos existen?
• 5. Indique las principales etapas del modelado.
• 6. ¿Qué es un algoritmo?
• 7. Enumere las propiedades del algoritmo.
• 8. ¿Qué etapas se realizan en la construcción completa del algoritmo?
• 9. ¿Qué es un diagrama de flujo de un algoritmo?
• 10. Defina un bloque de funciones.
• 11. ¿Qué algoritmo se llama estructural?
• 12. Nombra los principios fundamentales que subyacen a la creación de algoritmos eficaces.