Elementos de la teoría del algoritmo.

Algoritmo - El concepto relacionado con los conceptos básicos fundamentales de la informática. Surgió mucho antes de la aparición de computadoras y es uno de los conceptos básicos de las matemáticas.

Palabra "algoritmo" sucedió en nombre de un científico medieval sobresaliente MUHAMED IBN MUSA AL-KHOREZMI(Ixvek Ad), abreviado Al-khorezmi. En la traducción latina de una de las obras de Al-Khorezmi, las reglas para realizar acciones comenzaron en palabras. DIXIT. Algorizmi. (Dijo Algoriza), en otro autor de traducciones al latín fue llamado Algoritmo. (Algoritmo).

A la noción "algoritmo" no claro, inequívoco. definiciones en sentido matemático. Solo se puede dar descripción (Explicación) de este concepto. Para explicar el concepto "algoritmo" la definición de concepto "Algoritmo del artista" . El algoritmo está formulado en un intérprete específico.

Algoritmo - Guía de acción para el artista, por lo que el significado de la palabra "algoritmo" está cerca del significado de las palabras "Nota" o "Prescripción".

Algoritmo - Comprensible y preciso. prescripción(nota) El contratista para hacer una cierta secuencia de acciones para lograr este objetivo o resolver la tarea.

Algoritmo - un orden preciso que establece un proceso de computación, comenzando con una fuente arbitraria dada de un cierto conjunto de datos posibles para esto, destinado a obtener el resultado totalmente definido por estos datos de origen.

Está claro que dicho no es una definición en el sentido matemático, pero solo refleja la comprensión intuitiva del algoritmo (no hay concepto de "prescripción" en las matemáticas, no está claro qué debería ser la precisión de que tal "comprensión", etc.).

Las principales propiedades del algoritmo.

Misisidad.

El algoritmo tiene un cierto número de valores de entrada: los argumentos especificados antes del inicio de la ejecución. El propósito de la ejecución del algoritmo es obtener el resultado (resultados) que tenga una relación completamente definida con los datos iniciales. El algoritmo indica una secuencia de operaciones para el procesamiento de datos de origen en resultados. Para el algoritmo, puede seleccionar varios conjuntos de datos de entrada de una pluralidad de datos permitidos para este proceso, es decir, Puede aplicar el algoritmo para resolver toda una clase de tareas del mismo tipo, difiriendo en los datos de origen. Esta propiedad del algoritmo se llama generalmente. miseria . Sin embargo, hay algoritmos aplicables solo a un único conjunto de datos. Se puede decir que para cada algoritmo está su propia clase de objetos permisibles como los datos de origen. Entonces propiedad miseria indica la aplicabilidad del algoritmo a todos los objetos de esta clase.

Constabilidad.

Para que se realice el algoritmo, debe entenderse por el contratista. Algoritmo de conveniencia significa el conocimiento del intérprete sobre lo que se debe hacer para ejecutar este algoritmo.

Discreción.

El algoritmo se representa como una secuencia final de pasos (el algoritmo tiene discreto la estructura) y su ejecución se desmembrenan en la ejecución de pasos individuales (la ejecución del siguiente paso comienza después de la finalización del anterior).

Miembro.

La ejecución del algoritmo termina después de la ejecución. número final de pasos . Al realizar un algoritmo, algunos de sus pasos pueden repetirse repetidamente. En matemáticas, hay procedimientos computacionales que tienen un carácter algorítmico, pero no poseer una propiedad miembro .

Certeza.

Cada paso del algoritmo debe ser definido clara e inequívocamente y no debe permitir una interpretación arbitraria por parte del contratista. En consecuencia, el algoritmo está diseñado para ejecución mecánica pura . Exactamente definición el algoritmo le permite cargarlo. autómata .

Eficiencia.

Cada paso del algoritmo debe realizarse con precisión y para el tiempo final. En este sentido, dicen que el algoritmo debe ser eficaz . Las acciones del artista en cada paso de la ejecución del algoritmo deben ser lo suficientemente simples para que puedan realizarse con precisión y para el momento final. Por lo general, se llaman instrucciones individuales en el artista contenidas en cada paso del algoritmo. equipos . Por lo tanto, la efectividad del algoritmo se asocia con la posibilidad de realizar cada comando por la hora final. Una combinación de equipos que pueden ser ejecutados por un intérprete específico llamado sistema de comandos del intérprete. . Por lo tanto, el algoritmo debe formularse para contener solo aquellos comandos que se incluyen en el sistema de comando del artista. Además, la eficiencia significa que el algoritmo se puede realizar, no solo para la final, sino para razonable el tiempo final.

Los comentarios anteriores explican concepto intuitivo de algoritmo. Pero este concepto en sí no se vuelve más claro y estricto. Sin embargo, en matemáticas durante mucho tiempo usó este concepto. Solo con la detección de tareas algorítmicamente intratables, es decir, Tareas, para resolver lo que es imposible construir un algoritmo, se ha aparecido una necesidad urgente de construir una definición formal de un algoritmo correspondiente a un concepto intuitivo conocido. El concepto intuitivo del algoritmo debido a su incertidumbre no puede ser objeto del estudio matemático, por lo tanto, para probar la existencia o la inexistencia del problema de resolver el problema, fue necesario definir estrictamente el algoritmo.

La construcción de una definición tan formal se lanzó desde la formalización de los objetos (operandos) del algoritmo, ya que en el concepto intuitivo del algoritmo, sus objetos pueden tener una naturaleza arbitraria. Pueden ser, por ejemplo, los números, indicaciones de sensores, fijando los parámetros del proceso de producción, piezas de ajedrez y posiciones, etc. Sin embargo, asumiendo que el algoritmo no importa con los objetos reales, sino con sus imágenes, podemos asumir que algoritmo de operandos - Palabras en un alfabeto arbitrario. Luego, resulta que el algoritmo convierte palabras en un alfabeto arbitrario en las palabras del mismo alfabeto. La formalización adicional del concepto del algoritmo se asocia con la formalización de la acción sobre los operandos y el procedimiento para estas acciones. Se propuso una de estas formalidades en 1936 por el matemático inglés a.Tining, que describió formalmente el diseño de alguna máquina abstracta ( máquinas tyurring ) Como algoritmo de artista y expresó la tesis principal de que cualquier algoritmo puede ser implementado por la máquina correspondiente de Turing. Al mismo tiempo, al mismo tiempo, el Matemático Americano E.Postus se propuso otro esquema algorítmico. poste de la máquina , y en 1954, las matemáticas soviéticas A.A. Markov desarrolló la teoría de las clases de algoritmos llamados algoritmos normales , y expresó la tesis principal de que se normaliza cualquier algoritmo.

Estos esquemas algorítmicos son equivalentes en el sentido de que los algoritmos descritos en uno de los esquemas también se pueden describir en el otro. Recientemente, estas teorías de los algoritmos están unidos por título. teaser del cerebro .

Las teorías lógicas de los algoritmos son bastante adecuadas para resolver problemas teóricos en la existencia o no existencia del algoritmo, pero no ayudan en los casos en que se requiere obtener un buen algoritmo adecuado para aplicaciones prácticas. El hecho es que desde el punto de vista de las teorías lógicas de los algoritmos, destinados a aplicaciones prácticas, son algoritmos en un sentido intuitivo. Por lo tanto, al aumentar los problemas que surgen en relación con la creación y el análisis de tales algoritmos, a menudo es necesario ser guiado solo por la intuición, y no una teoría matemática estricta. Por lo tanto, la práctica puso la tarea de crear una teoría significativa, cuyo objeto sería algoritmos, como tales, y lo que les permitiría evaluar su calidad, daría métodos prácticamente adecuados de su construcción, transformación equivalente, prueba de corrección, etc.

Subitativo (analítico) La teoría de los algoritmos fue posible solo debido al trabajo fundamental de los matemáticos en el campo de las teorías lógicas de los algoritmos. El desarrollo de tal teoría se asocia con la mayor y la expansión del concepto formal del algoritmo, que está demasiado reducido en el marco de las teorías lógicas. La naturaleza formal del concepto permitirá aplicar los métodos de investigación matemática, y su latitud debe proporcionar la posibilidad de cobertura de todos los tipos de algoritmos que tengan que tratar.

TEMA: Algoritmo. Propiedades del algoritmo.

Algoritmo - Esta es una receta clara y precisa al intérprete, realice la secuencia final de los pasos que llevan a los datos de origen al resultado deseado

Propiedades del algoritmo.

p. Discreción (interrumpir) - El algoritmo debe romperse en
secuencia de pasos realizados;

p. Nota (determinación, precisión) -algoritmo
debe ser definitivamente (seguro) implementado por el contratista.

p. Miseria - algoritmo compilado aplicable a la resolución
tareas similares con datos de origen diferentes.

p. Límite (efectividad)- Para el número final de pasos.
se debe obtener el resultado;

p. Formalidad -propiedad que significa que cualquier artista,
por ejemplo, una computadora actúa formalmente, es decir, estrictamente
realiza instrucciones proporcionadas por el desarrollador.
algoritmo.

p. Constabilidad – el algoritmo debe contener solo esos comandos,
quien entiende un intérprete específico.

Diagrama de flujo Se llama la imagen gráfica de la estructura lógica del algoritmo, en la que cada etapa del proceso de procesamiento del proceso se representa como caracteres geométricos (bloques) que tienen una configuración específica según la naturaleza de las operaciones realizadas.

Con toda la variedad de algoritmos para resolver problemas en ellos, puede asignar tres tipos principales de procesos informáticos:

· Lineal;

· Branching;

· Ciclístico.

Lineal Este proceso de cómputo se llama, en el que todas las etapas de resolver el problema se realizan en el orden natural de la grabación de estas etapas.

Derivación Este proceso computacional se llama, en el que la elección del procesamiento de la información depende de los datos de origen o intermedios (a partir de los resultados de la verificación de la condición lógica).

Ciclo Se llama un área de computación repetida multiplicada. El proceso de computación que contiene uno o más ciclos se llama cíclico .

Responder preguntas de prueba

1.K. Las propiedades principales del algoritmo incluyen ...

a) brevedad, certeza, lealtad, masa, formalidad

b) discreción, importancia, desempeño, lealtad, formalidad

c) precisión, intermitencia, rendimiento, generalización, formalidad

d) tía, importancia, rendimiento, masa

2. La descripción gráfica del algoritmo es una descripción con ...

un diagrama

b) ... marcas de flujo

c) ... gráficos

d) ... todos los métodos enumerados anteriormente

3. A qué propiedad del algoritmo se refiere a la definición.

El artista, sin comprender el significado del algoritmo y establecer la tarea, realizar la corrección de cada equipo, puede obtener el resultado correcto.

a) masiness

b) rendimiento

c) formalidad

d) fiabilidad

4. La descripción del algoritmo en el lenguaje algorítmico es un medio para escribir un algoritmo.

a) ... en forma teórica

b) ... en forma de esquemas

c) ... en forma analítica

d) ... en una forma especial

5. La propiedad del algoritmo que determina el carácter paso a paso del algoritmo se llama ...

una actuación

b) inequívoco

c) discreción

d) masistitud

e) todas las propiedades determinan el carácter paso a paso del algoritmo

6. El algoritmo se llama lineal si ...

a) se elabora para que su implementación involucre la repetición múltiple de las mismas acciones;

b) La secuencia de ejecución de sus comandos depende de la verdad de ciertas condiciones;

c) Sus equipos se realizan en el orden de su seguimiento natural entre sí, independientemente de cualquier condición;

d) Incluye algoritmo auxiliar;

e) Su registro se presenta en forma de una línea.

7. Y las propiedades principales del algoritmo no se aplican ...

a) corrección;

b) certeza

c) Misisidad

d) rendimiento

El concepto del algoritmo. Propiedades del algoritmo. Tipos de algoritmos. Métodos para describir algoritmo.

El algoritmo es la receta exacta y comprensible por parte del contratista para hacer una secuencia de acciones dirigidas a resolver la tarea. La palabra "algoritmo" ocurre en nombre de Matemáticas por Al Khorezmi, que formuló las reglas para realizar la acción aritmética. Inicialmente, el algoritmo entendió solo las reglas para realizar cuatro acciones aritméticas sobre números. En el futuro, este concepto comenzó a utilizar en general para designar una secuencia de acciones que resultan en resolver cualquier tarea. Hablando sobre el algoritmo del proceso de computación, es necesario entender que los objetos a los que se usó el algoritmo son datos. El algoritmo para resolver un problema computacional es una combinación de las reglas para convertir los datos de origen en el resultado.

Básico propiedades El algoritmo es:

1. Determinismo (certeza). Implica obtener un resultado inequívoco de TRANSCA computacional para obtener datos de origen específicos. Debido a esta propiedad, el proceso de realizar el algoritmo es mecánico;
2. Actuación. Indica la presencia de dichos datos de origen para los cuales el proceso computacional implementado de acuerdo con el algoritmo especificado debe detener y emitir un resultado deseado;
3. Misisidad. Esta propiedad asume que el algoritmo debe ser adecuado para resolver todas las tareas de este tipo;
4. Discreción. Indica el desmembramiento del proceso computacional determinado por el algoritmo a etapas separadas, la posibilidad de ejecutar la cual el intérprete (computadora) es sin duda.

El algoritmo debe formalizarse de acuerdo con algunas reglas a través de fondos visuales concretos. Estos incluyen los siguientes métodos de grabación de algoritmos: verbal, fórmula-verbal, gráfica, lenguaje de esquemas de operador, lenguaje algorítmico.

La mayor distribución debido a su claridad recibió un método gráfico (circuito de bloques) de los algoritmos de grabación.

Diagrama de flujo Se llama la imagen gráfica de la estructura lógica del algoritmo, en la que cada etapa del proceso de procesamiento del proceso se representa como caracteres geométricos (bloques) que tienen una configuración específica según la naturaleza de las operaciones realizadas. La lista de caracteres, su nombre, mostrado por ellos, forma y dimensiones están determinados por las GTales.

Con toda la variedad de algoritmos para resolver problemas en ellos, se pueden distinguir tres tipos principales de procesos informáticos:

• lineal;
• derivación;
• cíclico

Lineal Este proceso de cómputo se llama, en el que todas las etapas de resolver el problema se realizan en el orden natural de la grabación de estas etapas.

Derivación Este proceso computacional se llama, en el que la elección del procesamiento de la información depende de los datos de origen o intermedios (a partir de los resultados de la verificación de la condición lógica).

El ciclo se denomina área de computación repetida multiplicada. El proceso de computación que contiene uno o más ciclos se llama cíclico . En términos del número de ciclos de realización se dividen en ciclos con un número determinado (predeterminado) de repeticiones y ciclos con un número indefinido de repeticiones. El número de repeticiones recientes depende de la observancia de una determinada condición que establece la necesidad de realizar un ciclo. Al mismo tiempo, la condición se puede verificar al comienzo del ciclo, luego estamos hablando de un ciclo con la condición previa, o al final, este es un ciclo con una Onda posterior.

Significado de la palabra algoritmo Muy similar al significado de las palabras. receta, Instrucción. Sin embargo, cualquier algoritmo, en contraste con la receta o método, necesariamente tiene las siguientes propiedades.

1. La ejecución del algoritmo se divide en una secuencia de pasos completos. Solo realizando una acción (comando), puede proceder a la ejecución de lo siguiente. Esta propiedad del algoritmo se llama. discreción. Hacer que cada acción separada por parte del contratista prescribe una indicación especial en el registro del algoritmo (comando).

2. Constabilidad - El algoritmo no debe contener las prescripciones, cuyo significado puede ser percibido por el intérprete ambiguo, es decir, El registro del algoritmo debe ser tan claro y completo para que el contratista no tenga ninguna necesidad de tomar decisiones independientes. El algoritmo siempre está diseñado para realizar "no reflexionar" por el artista.. El algoritmo está formado por equipos incluidos en esquí.

Considere un ejemplo bien conocido de un algoritmo "hogar" del algoritmo de transición callejera: "Mire hacia la izquierda. Si no hay autos, llegas a la mitad de la calle. Si hay, espere hasta que vayan, etc. ". Imagina la situación: hay un automóvil a la izquierda, pero no va, ella tiene una rueda. Si cree que el ejecutante del algoritmo debe esperar, entendió este algoritmo. Si decides que es posible cruzar la calle, considerando que el algoritmo se corregirá debido a las circunstancias imprevistas (¡en su opinión), entonces no promedió el concepto del algoritmo.

3. Determinismo (no definición). Cada comando de algoritmo define la acción del actor único, y debe definirse de forma única qué comando se realiza de la siguiente manera. Es decir, si el algoritmo se aplica repetidamente al mismo conjunto de datos de origen, entonces, en la salida, recibe cada vez que el mismo resultado.

4. Actuación - La ejecución del algoritmo debe resultar en un número finito de pasos, y se debe obtener el resultado de la resolución de problemas. Como uno de los posibles resultados, puede ser el establecimiento del hecho de que la tarea de las soluciones no tiene.

Las propiedades de la efectividad contienen una propiedad. miembro - Finalización del algoritmo para un número finito de pasos.

5. Miseria - El algoritmo es adecuado para resolver cualquier tarea de una cierta clase de tareas, es decir, El algoritmo funciona correctamente en un determinado conjunto de datos de origen, que se denomina área de aplicabilidad del algoritmo.

Las propiedades de la masa definen la calidad del algoritmo, y no se relacionan con las propiedades obligatorias (como discreción, comprensibilidad, etc.). Hay algoritmos, cuya aplicabilidad se limita al único conjunto de datos de entrada o incluso la ausencia de tal (por ejemplo, obteniendo un número fijo de números fieles del número P). Es más correcto decir que el algoritmo debe ser aplicable a cualquier información de su campo de definición y la palabra miseria No siempre es adecuado para describir esta propiedad.

El concepto de algoritmo

Resumiendo lo anterior, formulamos lo siguiente. concepto Algoritmo.

Algoritmo - una receta comprensible y precisa por parte del contratista para realizar la secuencia final de acciones que llevan a los datos de origen al resultado deseado.

La definición anterior no es una definición en el sentido matemático de la palabra, es decir. Esta no es una definición formal (definición formal del algoritmo, consulte el artículo " Teoría del algoritmo”).

Tenga en cuenta que para todos ejecutante Un conjunto de acciones permisibles (esquí) siempre es limitado, el intérprete no puede existir, para lo cual se permita ninguna acción. El razonamiento de la prafrassed I.Kanta justifica la declaración formulada de la siguiente manera: "Si ese intérprete que existiera, entre sus acciones permisibles sería crear tal piedra que no pudiera aumentar. Pero esto es contrario a la admisibilidad de "criar cualquier piedra".

Es interesante que haya tareas de que una persona que generalmente puede decidir sin conocer el algoritmo de su decisión. Por ejemplo, frente a una persona son imágenes de gatos y perros. La tarea es determinar que el gato o el perro se muestre en una foto específica. Una persona resuelve esta tarea, pero escribir un algoritmo para resolver esta tarea sigue siendo extremadamente difícil.

Por otro lado, hay tareas para las que generalmente es imposible construir un procedimiento de solución. Además, este hecho puede ser estrictamente probado. Puedes leer sobre ello en el artículo " Problemas algorítmicamente intratables.” 2.

Resuelve la tarea de encontrar la corriente máxima en la red de transporte. El algoritmo no es un caso especial del algoritmo Ford Falkerson. Implementado sin mejoras especiales, el algoritmo se realiza durante el tiempo. Algunas mejoras siguen siendo ... Wikipedia

Algoritmos de búsqueda local El grupo de algoritmos en los que la búsqueda se lleva a cabo solo sobre la base del estado actual, y los estados aprobados previamente no se tienen en cuenta y no se recuerdan. El objetivo principal de la búsqueda no es encontrar la forma óptima de ... ... Wikipedia

Este término tiene otros valores, vea Marte. Marte creado: 1998 Publicado: 1998 Tamaño clave ... Wikipedia

Este término tiene otros valores, vea Marte. Marte creado: 1998 ... Wikipedia

Este término tiene otros valores, vea el algoritmo (valores). Para mejorar este artículo, es deseable.: Reciclar el registro de acuerdo con las reglas ... Wikipedia

Este artículo incluye material de esta versión del artículo correspondiente de la Wikipedia británica. Transformación operativa (OP) es una tecnología para respaldar una serie de oportunidades funcionales para la cooperación en sistemas avanzados ... ... Wikipedia

Grafa Search Algorithms A * B * Algorithm Bellman Ford Búsqueda Bidireccional Algorithm Daekstra Algorithm Johnson Búsqueda Ancho Búsqueda Búsqueda profunda Búsqueda Límite de profundidad Búsqueda en la primera mejor coincidencia Floyd WorkiJella Buscar ... Wikipedia

Este es un algoritmo para simplificar los elementos de la lista. En el caso de que el elemento de la lista tenga varios campos, un campo que sirve como un criterio de pedido se denomina clave de clasificación. En la práctica, un número a menudo viene como una llave, y en el resto de los campos ... ... Wikipedia

BMW (BMW Blue Midnight Wish) Función de hash criptográfica (HF) con una salida a N bit, donde n \u003d 224,256, 384 o 512. Las funciones de hash están diseñadas para crear "impresiones" o "digiertos" de mapas de bits arbitrarios. .... .. Wikipedia

Este artículo debe ser VICO. Por favor, consúltelo de acuerdo con las reglas de los artículos. Este término tiene otros significados, vea el té (valores) ... Wikipedia

Libros

• Lógica de Lukasevich y números simples, A. S. Karpenko, por primera vez en la literatura mundial en un estudio monográfico, se establece una conexión directa entre las lógicas y los números simples. Aunque la lógica multivaluada de Lukasevich fue el resultado de la refutación ... Categoría: Lógica Editor: LiBOK,
• Lógica en asuntos y respuestas. Tutorial, Kobzar Vladimir Ivanovich, el libro de texto está escrito de acuerdo con el programa de la lógica formal tradicional (general, filosófica). Abordó las formas principales y los métodos de actividad mental, su ... Categoría: