hogar › Navegantes › Ejecución del algoritmo para una decisión del ejecutor específica. Informática y tecnología de la información. Formas de describir algoritmos

Ejecución del algoritmo para una decisión del ejecutor específica. Informática y tecnología de la información. Formas de describir algoritmos

Palabras clave:

algoritmo
propiedades del algoritmo
- discreción
- claridad
- certeza
- eficacia
- personaje de masas
ejecutor

características del artista
- gama de tareas a resolver
- Miércoles
- modo operativo
- sistema de comando
ejecución formal del algoritmo

3.1.1. Concepto de algoritmo

Cada persona en La vida cotidiana, en el estudio o en el trabajo, resuelve una gran cantidad de problemas de diversa complejidad. Los problemas complejos requieren mucha reflexión para encontrar una solución; Una persona resuelve tareas sencillas y familiares sin pensar, de forma automática. En la mayoría de los casos, la solución a cada problema se puede dividir en etapas (pasos) simples. Para muchas de estas tareas (instalación software, montar un gabinete, crear un sitio web, manejar un dispositivo técnico, comprar un billete de avión a través de Internet, etc.) ya han sido desarrollados y ofrecidos instrucciones paso a paso, que, cuando se ejecuta de forma coherente, puede conducir al resultado deseado.

Ejemplo 1. El problema “Encontrar la media aritmética de dos números” se resuelve en tres pasos:

piensa en dos números;
sume dos números en mente;
divide la cantidad resultante por 2.

Ejemplo 2. La tarea "Depositar dinero en su cuenta de teléfono" se divide en los siguientes pasos:

ir al terminal de pago;
seleccione un operador de telecomunicaciones;
Ingresa un número de teléfono;
comprobar que el número introducido sea correcto;
inserte un billete en el aceptador de billetes;
espere un mensaje sobre el dinero acreditado en su cuenta;
recibir un cheque.

Ejemplo 3. Las etapas para resolver el problema "Dibujar un erizo divertido" se presentan gráficamente:

Encontrar la media aritmética, depositar dinero en una cuenta telefónica y dibujar un erizo son, a primera vista, procesos completamente diferentes. Pero tienen una característica común: cada uno de estos procesos se describe mediante una secuencia de breves instrucciones, cuyo estricto cumplimiento permite obtener el resultado deseado. Las secuencias de instrucciones dadas en los ejemplos 1-3 son algoritmos para resolver los problemas correspondientes. El ejecutor de estos algoritmos es una persona.

El algoritmo puede ser una descripción de una determinada secuencia de cálculos (ejemplo 1) o pasos de naturaleza no matemática (ejemplos 2-3). Pero en cualquier caso, antes de su desarrollo, el condiciones iniciales(datos de entrada) y lo que se desea obtener (resultado). Podemos decir que un algoritmo es una descripción de la secuencia de pasos para resolver un problema, desde los datos iniciales hasta el resultado requerido.

En general, el diagrama de funcionamiento del algoritmo se puede representar de la siguiente manera (Fig. 3.1):

Arroz. 3.1.
Esquema general del algoritmo.

Los algoritmos son las reglas de suma, resta, multiplicación y división de números, reglas gramaticales, reglas de construcciones geométricas, etc., que se estudian en la escuela.

Las animaciones "Trabajar con un algoritmo", "Máximo común divisor", "Mínimo común múltiplo" (http://school-collection.edu.ru/) le ayudarán a recordar algunos algoritmos estudiados en las lecciones de lengua rusa y matemáticas.

Ejemplo 4. Algún algoritmo lleva al hecho de que de una cadena de caracteres se obtiene una nueva cadena de la siguiente manera:

Se calcula la longitud (en caracteres) de la cadena de caracteres de origen.
Si la longitud de la cadena original es impar, entonces el número 1 se agrega a la cadena original de la derecha; de lo contrario, la cadena no cambia.
Los símbolos se intercambian por parejas (el primero con el segundo, el tercero con el cuarto, el quinto con el sexto, etc.).
El número 2 se suma a la derecha de la cadena resultante.

La cadena resultante es el resultado del algoritmo.

Entonces, si la cadena inicial fue A#B, entonces el resultado del algoritmo será la cadena #A1B2, y si la cadena inicial fue ABC@, entonces el resultado del algoritmo será la cadena BA@B2.

3.1.2. Ejecutor de algoritmos

Cada algoritmo está diseñado para un artista específico.

Hay artistas formales e informales. Un ejecutante formal siempre ejecuta la misma orden de la misma manera. Un ejecutor informal puede ejecutar una orden de diferentes maneras.

Consideremos con más detalle el conjunto de intérpretes formales. Los ejecutores formales son extremadamente diversos, pero para cada uno de ellos se pueden especificar las siguientes características: la gama de tareas a resolver (propósito), el entorno, el sistema de mando y el modo de operación.

Gama de tareas a resolver.. Cada intérprete está creado para resolver una determinada gama de problemas: construir cadenas de símbolos, realizar cálculos, construir dibujos en un plano, etc.

Entorno del artista. El área, el entorno y las condiciones en las que opera el artista generalmente se denominan entorno de este artista. Los datos de origen y los resultados de cualquier algoritmo siempre pertenecen al entorno del ejecutante al que está destinado el algoritmo.

Sistema de comando ejecutor. Una instrucción a un ejecutante para que realice una acción completada por separado se llama comando. El conjunto de todos los comandos que puede ejecutar algún ejecutor forma el sistema de comandos para este ejecutor (SKI). El algoritmo se compila teniendo en cuenta las capacidades de un ejecutante específico, es decir, en el sistema de comandos del ejecutante que lo ejecutará.

Modos de funcionamiento del artista. Para la mayoría de los artistas, los modos de control directo y control de programa. En el primer caso, el ejecutante espera órdenes de una persona e inmediatamente ejecuta cada orden recibida. En el segundo caso, al ejecutante primero se le da una secuencia completa de comandos (programa), y luego ejecuta todos estos comandos en modo automatico. Varios artistas trabajan solo en uno de los modos nombrados.

Veamos ejemplos de artistas intérpretes o ejecutantes.

Ejemplo 5. Artista La tortuga se mueve en la pantalla de la computadora, dejando un rastro en forma de línea. El sistema de mando de Turtle consta de dos comandos:

Derecha m (donde m es un número entero): hace que la dirección del movimiento de la Tortuga cambie m grados en el sentido de las agujas del reloj.

Grabar repetir k [<Команда1> <Команда2> ... <Командаn>] significa que la secuencia de comandos entre paréntesis se repetirá k veces.

Piensa en qué figura aparecerá en la pantalla después de que la Tortuga complete el siguiente algoritmo.

Repetir 12 [Derecha 4 5 Adelante 20 Derecha 45]

Ejemplo 6. El sistema de comandos ejecutores La computadora consta de dos comandos, a los que se les asignan números:

El primero de ellos reduce el número en 1, el segundo aumenta el número 3 veces. Al escribir algoritmos, por brevedad, solo se indican los números de comando. Por ejemplo, el algoritmo 21212 significa la siguiente secuencia de comandos:

Usando este algoritmo, el número 1 se convertirá en 15: ((1-3-1)-3-1)-3 = 15.

Ejemplo 7. Performer Robot opera en un campo cuadriculado, entre celdas adyacentes puede haber paredes. El robot se mueve a lo largo de las celdas del campo y puede realizar los siguientes comandos, a los que se les asignan números:

Al ejecutar cada uno de estos comandos, el robot se mueve a una celda adyacente en la dirección indicada. Si hay una pared en esta dirección entre las celdas, entonces el Robot se destruye. ¿Qué pasará con el Robot si ejecuta la secuencia de comandos 32323 (aquí los números indican números de comando), comenzando a moverse desde la celda A? ¿Qué secuencia de comandos debe ejecutar el Robot para pasar de la celda A a la celda B sin colapsar al golpear las paredes?

Al desarrollar un algoritmo:

Se identifican los objetos que aparecen en el problema, las propiedades de los objetos, las relaciones entre objetos y posibles acciones con objetos;
se determinan los datos iniciales y el resultado requerido;
se determina la secuencia de acciones del ejecutante, asegurando la transición de los datos iniciales al resultado;
la secuencia de acciones se registra mediante comandos incluidos en el sistema de comando del ejecutor.

Podemos decir que un algoritmo es un modelo de la actividad del ejecutor del algoritmo.

3.1.3. Propiedades del algoritmo

No todas las instrucciones, secuencias de instrucciones o planes de acción pueden considerarse un algoritmo. Cada algoritmo tiene necesariamente las siguientes propiedades: discreción, comprensibilidad, certeza, eficacia y carácter masivo.

La propiedad de discreción significa que el camino para resolver un problema se divide en pasos (acciones) separados. Cada acción tiene una instrucción correspondiente (comando). Sólo después de ejecutar un comando el ejecutor puede comenzar a ejecutar el siguiente comando.

La propiedad de comprensibilidad significa que el algoritmo consta únicamente de comandos incluidos en el sistema de comandos del ejecutante, es decir, de comandos que el ejecutante puede percibir y según los cuales puede realizar las acciones requeridas.

La propiedad de certeza significa que el algoritmo no contiene comandos cuyo significado pueda ser interpretado de manera ambigua por el ejecutante; Las situaciones son inaceptables cuando, después de ejecutar el siguiente comando, el ejecutante no tiene claro qué comando ejecutar en el siguiente paso.

La propiedad de eficiencia significa que el algoritmo debe poder obtener un resultado después de un número finito, posiblemente muy grande, de pasos. En este caso, el resultado se considera no solo la respuesta determinada por el planteamiento del problema, sino también la conclusión sobre la imposibilidad de continuar resolviendo este problema por cualquier motivo.

La propiedad de producción en masa significa que el algoritmo debe brindar la posibilidad de su aplicación para resolver cualquier problema de una determinada clase de problemas. Por ejemplo, el algoritmo para encontrar las raíces de una ecuación cuadrática debería ser aplicable a cualquier ecuación cuadrática, el algoritmo para cruzar la calle debería ser aplicable en cualquier lugar de la calle, el algoritmo para preparar medicamentos debería ser aplicable para preparar cualquier cantidad del mismo, etc.

Ejemplo 8. Consideremos uno de los métodos para encontrar todos los números primos que no excedan n. Este método se llama “tamiz de Eratóstenes”, en honor al antiguo científico griego Eratóstenes que lo propuso.

Para encontrar todos los números primos no mayores que un número dado n, siguiendo el método de Eratóstenes, es necesario realizar los siguientes pasos:

anota todos los números enteros del 2 al n seguidos (2, 3, 4, ..., n);
cuadro 2: el primer número primo;
tache de la lista todos los números divisibles por el último número primo encontrado;
busque el primer número sin marcar (los números marcados son números tachados o números encerrados en un marco) y enciérrelo en un marco; este será otro número primo;
repita los pasos 3 y 4 hasta que no queden números sin marcar.

Puede hacerse una idea más visual del método para encontrar números primos utilizando la animación "El tamiz de Eratóstenes" (http://school-collection.edu.ru/).

La secuencia de acciones considerada es un algoritmo, ya que satisface las siguientes propiedades:

discreción: el proceso de encontrar números primos se divide en pasos;
comprensibilidad: cada comando es comprensible para un estudiante de noveno grado que realiza este algoritmo;
certeza: cada comando es interpretado y ejecutado por el ejecutante sin ambigüedades; hay instrucciones sobre el orden de ejecución de los comandos;
efectividad: después de una cierta cantidad de pasos, se logra el resultado;
carácter masivo: la secuencia de acciones es aplicable para cualquier n natural.

Las propiedades consideradas del algoritmo nos permiten dar una definición más precisa del algoritmo.

3.1.4. Posibilidad de automatización de las actividades humanas.

Desarrollar un algoritmo suele ser una tarea que requiere mucha mano de obra y que requiere que una persona tenga un conocimiento profundo, ingenio y mucho tiempo.

Resolver un problema utilizando un algoritmo ya preparado solo requiere que el ejecutante siga estrictamente las instrucciones dadas.

Ejemplo 9. De una pila que contiene un número de objetos superior a tres, dos jugadores se turnan para tomar uno o dos objetos cada uno. El ganador es aquel que puede recoger todos los elementos restantes en su próximo movimiento.

Consideremos un algoritmo mediante el cual el primer jugador seguramente se asegurará la victoria.

Si el número de objetos en la pila es múltiplo de 3, cede el paso al oponente; de lo contrario, comienza el juego.
En tu próximo movimiento, suma cada vez el número de objetos tomados por tu oponente a 3 (el número de objetos restantes debe ser múltiplo de 3).

El ejecutante no puede ahondar en el significado de lo que está haciendo y no razonar por qué actúa de esta manera y no de otra manera, es decir, puede actuar formalmente. La capacidad del ejecutante para actuar formalmente brinda la posibilidad de automatizar la actividad humana. Para esto:

el proceso de resolución de un problema se presenta como una secuencia de operaciones simples;
se crea una máquina ( dispositivo automático), capaz de realizar estas operaciones en la secuencia especificada en el algoritmo;
una persona se libera de las actividades rutinarias, la ejecución del algoritmo se confía a un dispositivo automático.

El más importante

Ejecutante: algún objeto (persona, animal, dispositivo técnico), capaz de ejecutar un conjunto específico de comandos. Un ejecutante formal siempre ejecuta la misma orden de la misma manera. Para cada ejecutante formal, puede especificar: la gama de tareas a resolver, el entorno, el sistema de mando y el modo de funcionamiento.

Un algoritmo es una descripción de una secuencia de acciones destinadas a un ejecutante específico que conduce desde los datos iniciales hasta el resultado requerido, que tiene las propiedades de discreción, comprensibilidad, certeza, efectividad y carácter masivo.

La capacidad del ejecutante para actuar formalmente brinda la posibilidad de automatizar la actividad humana.

Preguntas y tareas

¿Cómo se llama un algoritmo?
Encuentre sinónimos de la palabra “receta”.
Da ejemplos de algoritmos que estudiaste en la escuela.
¿Quién puede ser el ejecutor del algoritmo?
Dé un ejemplo de un artista formal. Dé un ejemplo cuando una persona actúa como intérprete formal.
¿Qué comandos debe realizar un robot como función: a) cajero en una tienda; b) un conserje; c) un guardia de seguridad?
¿Qué determina la gama de tareas realizadas por el ejecutante “computador”?
Considerar como intérprete procesador de textos, disponible en tu ordenador. Describa la gama de tareas resueltas por este ejecutante y su entorno.
¿Qué es un equipo, un sistema de órdenes de ejecución?
Enumere las principales propiedades del algoritmo.
¿A qué puede conducir la ausencia de cualquier propiedad en un algoritmo? Dar ejemplos.
¿Por qué es importante poder ejecutar formalmente un algoritmo?
La secuencia de números se construye de acuerdo con el siguiente algoritmo: los dos primeros números de la secuencia se toman iguales a 1; Se considera que cada número siguiente de la secuencia es igual a la suma de los dos números anteriores. Escribe los primeros 10 términos de esta secuencia.
Algún algoritmo obtiene una nueva cadena a partir de una cadena de caracteres de la siguiente manera. Primero, se escribe la cadena original de caracteres, luego se escribe la cadena original de caracteres en orden inverso, luego se escribe la letra que sigue en el alfabeto ruso después de la letra que estaba en el último lugar en la cadena original. Si el último lugar de la cadena original es la letra Z, entonces como siguiente letra se escribe la letra A. La cadena resultante es el resultado del algoritmo. Por ejemplo, si la cadena de caracteres original era DOM, entonces el resultado del algoritmo será la cadena DOMMODN. Se proporciona la cadena de caracteres COM. ¿Cuántas letras O habrá en la cadena de símbolos que se obtendrá si aplicas el algoritmo a esta cadena y luego aplicas el algoritmo nuevamente al resultado de su trabajo?
Encuentre una animación de los pasos del algoritmo de Eratóstenes en Internet. Utilice el algoritmo de Eratóstenes para encontrar todos los números primos que no excedan 50.
¿Cuál será el resultado de la ejecución del algoritmo por parte de Turtle (ver ejemplo 5)?
Escriba un algoritmo para el ejecutor de la Calculadora (ejemplo 6), que contenga no más de 5 comandos:
El sistema de comandos ejecutores El constructor consta de dos comandos, a los que se les asignan números:
Según el primero de ellos, se suma 2 al número de la derecha, según el segundo, el número se divide por 2. ¿Cómo se convertirá el número 8 si el ejecutante ejecuta el algoritmo 22212? Cree un algoritmo en el sistema de comandos de este ejecutor, según el cual el número 1 se convertirá en el número 16 (el algoritmo no debe contener más de 5 comandos).
¿En qué celda debe ubicarse el robot ejecutante (ejemplo 7) para regresar a él después de ejecutar el algoritmo 3241?

| § 2.1. Algoritmos y ejecutores.

Lección 14
§ 2.1. Algoritmos y ejecutores.

Palabras clave:

Algoritmo
propiedades del algoritmo (discreción; comprensibilidad; certeza; efectividad; carácter masivo)
ejecutor
características del ejecutante (gama de tareas a resolver; entorno; modo de funcionamiento; sistema de mando)
ejecución formal del algoritmo

2.1.1. Concepto de algoritmo

Cada persona en la vida cotidiana, en el estudio o en el trabajo resuelve una gran cantidad de problemas de diversa complejidad. Los problemas complejos requieren mucha reflexión para encontrar una solución; Una persona resuelve tareas sencillas y familiares sin pensar, de forma automática. En la mayoría de los casos, la solución a cada problema se puede dividir en etapas (pasos) simples. Para muchas de estas tareas (instalar software, montar un gabinete, crear un sitio web, operar un dispositivo técnico, comprar un billete de avión a través de Internet, etc.), ya se han desarrollado y se ofrecen instrucciones paso a paso, las secuenciales cuya implementación puede conducir al resultado deseado.

Ejemplo 1. El problema “Encontrar la media aritmética de dos números” se resuelve en tres pasos:

1) piensa en dos números;
2) sumar dos números planificados;
3) divide la cantidad resultante entre 2.

Ejemplo 2. La tarea "Depositar dinero en su cuenta de teléfono" se divide en los siguientes pasos:

1) ir al terminal de pago;
2) elegir un operador de telecomunicaciones;
3) ingrese un número de teléfono;
4) comprobar que el número introducido sea correcto;
5) insertar un billete en el aceptador de billetes;
6) espere un mensaje sobre el dinero acreditado en su cuenta;
7) recibir un cheque.

Ejemplo 3. Las etapas para resolver el problema "Dibujar un erizo divertido" se presentan gráficamente:

El algoritmo puede ser una descripción de una determinada secuencia de cálculos (ejemplo 1) o pasos de naturaleza no matemática (ejemplos 2-3). Pero en cualquier caso, antes de su desarrollo se deben definir claramente las condiciones iniciales (datos iniciales) y lo que se quiere obtener (resultado). Podemos decir que un algoritmo es una descripción de la secuencia de pasos para resolver un problema, desde los datos iniciales hasta el resultado requerido.

En general, el diagrama de funcionamiento del algoritmo se puede representar de la siguiente manera (Fig. 2.1).

Arroz. 2.1. Esquema general del algoritmo.

Los algoritmos son las reglas de suma, resta, multiplicación y división de números que se estudian en la escuela, muchas reglas gramaticales, reglas de construcciones geométricas, etc.

Las animaciones “Trabajar con un algoritmo” (193576), “Máximo común divisor” (170363), “Mínimo común múltiplo” (170390) le ayudarán a recordar algunos algoritmos estudiados en las lecciones de lengua rusa y matemáticas (http://sc.edu. es /).

Ejemplo 4. Algún algoritmo lleva al hecho de que de una cadena de caracteres se obtiene una nueva cadena de la siguiente manera:

1. Se calcula la longitud (en caracteres) de la cadena de caracteres original.
2. Si la longitud de la cadena original es impar, entonces el número 1 se suma a la cadena original de la derecha; de lo contrario, la cadena no cambia.
3. Los símbolos se intercambian por parejas (el primero con el segundo, el tercero con el cuarto, el quinto con el sexto, etc.).
4. El número 2 se suma a la derecha de la cadena resultante.

La cadena resultante es el resultado del algoritmo.

Entonces, si la cadena inicial fue A#B, entonces el resultado del algoritmo será la cadena #A1B2, y si la cadena inicial fue ABC@, entonces el resultado del algoritmo será la cadena BA@B2.

2.1.2. Ejecutor de algoritmos

Cada algoritmo está diseñado para un artista específico.

Un ejecutor es un objeto (persona, animal, dispositivo técnico) capaz de ejecutar un determinado conjunto de comandos.

Distinguir artistas formales e informales. Un ejecutante formal siempre ejecuta la misma orden de la misma manera. Un ejecutor informal puede ejecutar una orden de diferentes maneras.

Gama de tareas a resolver.. Cada intérprete está creado para resolver una determinada gama de problemas: construir cadenas de símbolos, realizar cálculos, construir dibujos en un plano, etc.

Modos de funcionamiento del artista. Para la mayoría de los artistas, se proporcionan modos de control directo y control de programa. En el primer caso, el ejecutante espera órdenes de una persona e inmediatamente ejecuta cada orden recibida. En el segundo caso, al ejecutante primero se le da una secuencia completa de comandos (programa) y luego ejecuta todos estos comandos automáticamente. Varios artistas trabajan solo en uno de los modos nombrados.

Veamos ejemplos de artistas intérpretes o ejecutantes.

Ejemplo 5. Artista La tortuga se mueve en la pantalla de la computadora, dejando un rastro en forma de línea.

El sistema de comando Turtle consta de los siguientes comandos:

1. Adelante n (donde n es un número entero): hace que la Tortuga se mueva n pasos en la dirección del movimiento, en la dirección en la que miran su cabeza y su cuerpo;
2. Derecho m (donde m es un número entero): provoca un cambio en la dirección del movimiento de la Tortuga en t grados en el sentido de las agujas del reloj.
Registro Repetir k [<Команда1> <Команда2> ... <Командаn>] significa que la secuencia de comandos entre paréntesis se repetirá k veces.

Piensa en qué figura aparecerá en la pantalla después de que la Tortuga complete el siguiente algoritmo.
Repita 12 [Derecha 45 Adelante 20 Derecha 45]

Ejemplo 6. El sistema de comandos ejecutores La computadora consta de dos comandos, a los que se les asignan números:

1 - restar 1
2 - multiplicar por 3

multiplicar por 3
restar 1
multiplicar por 3
restar 1
multiplicar por 3

Usando este algoritmo, el número 1 se convertirá en 15:

((1 3 - 1) 3 - 1) 3 = 15.

Ejemplo 7. Performer Robot opera en un campo cuadriculado, entre celdas adyacentes puede haber paredes. El robot se mueve a lo largo de las celdas del campo y puede realizar los siguientes comandos, a los que se les asignan números:

1 de ventaja
2 - abajo
3 - derecha
quedan 4

Al ejecutar cada uno de estos comandos, el robot se mueve a una celda adyacente en la dirección indicada. Si hay una pared en esta dirección entre las celdas, entonces el Robot se destruye.

¿Qué pasará con el Robot si ejecuta la secuencia de comandos 32323 (aquí los números indican números de comando), comenzando a moverse desde la celda A? ¿Qué secuencia de comandos debe ejecutar el Robot para pasar de la celda A a la celda B sin colapsar al golpear las paredes?

Al desarrollar un algoritmo:

1) se identifican los objetos que aparecen en el problema, se establecen las propiedades de los objetos, las relaciones entre los objetos y las posibles acciones con los objetos;
2) se determinan los datos iniciales y el resultado requerido;
3) se determina la secuencia de acciones del ejecutante, asegurando la transición de los datos iniciales al resultado;
4) la secuencia de acciones se registra mediante comandos incluidos en el sistema de mando del ejecutante.

Podemos decir que un algoritmo es un modelo de la actividad del ejecutor del algoritmo.

2.1.3. Propiedades del algoritmo

Propiedad discreta significa que el camino para resolver un problema se divide en pasos separados (acciones). Cada acción tiene una instrucción correspondiente (comando). Sólo después de ejecutar un comando el ejecutor puede comenzar a ejecutar el siguiente comando.

Propiedad de comprensibilidad significa que el algoritmo consta únicamente de comandos incluidos en el sistema de comandos del ejecutante, es decir, de comandos que el ejecutante puede percibir y según los cuales puede realizar las acciones requeridas.

Propiedad de certeza significa que el algoritmo no contiene comandos cuyo significado pueda ser interpretado de manera ambigua por el ejecutante; Las situaciones son inaceptables cuando, después de ejecutar el siguiente comando, el ejecutante no tiene claro qué comando ejecutar a continuación. Gracias a esto, el resultado del algoritmo está determinado únicamente por el conjunto de datos iniciales: si el algoritmo se aplica varias veces al mismo conjunto de datos iniciales, la salida siempre produce el mismo resultado.

Propiedad de rendimiento significa que el algoritmo debe proporcionar un resultado después de un número finito, posiblemente muy grande, de pasos. En este caso, el resultado se considera no solo la respuesta determinada por el planteamiento del problema, sino también la conclusión sobre la imposibilidad de continuar resolviendo este problema por cualquier motivo.

Propiedad de carácter masivo. significa que el algoritmo debe brindar la posibilidad de su aplicación para resolver cualquier problema de una determinada clase de problemas. Por ejemplo, el algoritmo para encontrar las raíces de una ecuación cuadrática debería ser aplicable a cualquier ecuación cuadrática, el algoritmo para cruzar la calle debería ser aplicable en cualquier lugar de la calle, el algoritmo para preparar medicamentos debería ser aplicable para preparar cualquier cantidad del mismo, etc.

Ejemplo 8. Consideremos uno de los métodos para encontrar todos los números primos que no excedan algún número natural n. Este método se llama “tamiz de Eratóstenes” en honor al antiguo científico griego Eratóstenes (siglo III a. C.) quien lo propuso.

Para encontrar todos los números primos no mayores que un número dado n, siguiendo el método de Eratóstenes, es necesario realizar los siguientes pasos:

1) escriba en una fila todos los números naturales del 2 al n (2, 3, 4, ..., n);
2) cuadro 2: el primer número primo;
3) tachar de la lista todos los números divisibles por el último número primo encontrado;
4) busque el primer número sin marcar (los números marcados son números tachados o números encerrados en un marco) y enciérrelo en un marco; este será otro número primo;
5) repite los pasos 3 y 4 hasta que no queden números sin marcar.

Puede obtener una idea más visual del método para encontrar números primos utilizando la animación "Tamiz de Eratóstenes" (180279) publicada en la Colección Unificada de Recursos Educativos Digitales.

La secuencia de acciones considerada es un algoritmo, ya que satisface las siguientes propiedades:

discreción- el proceso de encontrar números primos se divide en pasos;
comprensibilidad- cada comando es comprensible para un estudiante de octavo grado que realiza este algoritmo;
certeza- cada comando es interpretado y ejecutado por el ejecutante de manera inequívoca; hay instrucciones sobre el orden de ejecución de los comandos;
eficacia- después de un cierto número de pasos se logra el resultado;
personaje de masas- la secuencia de acciones es aplicable para cualquier número natural n.

Las propiedades consideradas del algoritmo nos permiten dar una definición más precisa del algoritmo.

2.1.4. Posibilidad de automatización de las actividades humanas.

Desarrollar un algoritmo suele ser una tarea que requiere mucha mano de obra y que requiere que una persona tenga un conocimiento profundo, ingenio y mucho tiempo.

Resolver un problema utilizando un algoritmo ya preparado solo requiere que el ejecutante siga estrictamente las instrucciones dadas.

Ejemplo 9. De una pila que contiene un número de objetos superior a tres, dos jugadores se turnan para tomar uno o dos objetos cada uno. El ganador es aquel que puede recoger todos los elementos restantes en su próximo movimiento.

Consideremos un algoritmo mediante el cual el primer jugador seguramente se asegurará la victoria.

1. Si el número de objetos en la pila es múltiplo de 3, entonces cede el paso al oponente; de lo contrario, comienza el juego tomando 1 o 2 objetos para que el número de objetos restantes sea múltiplo de 3.
2. En tu próximo movimiento, cada vez suma a 3 el número de objetos tomados por tu oponente (el número de objetos restantes debe ser múltiplo de 3).

1) el proceso de resolución de un problema se presenta como una secuencia de operaciones simples;
2) se crea una máquina (dispositivo automático) que sea capaz de realizar estas operaciones en la secuencia especificada en el algoritmo;
3) una persona se libera de las actividades rutinarias, la ejecución del algoritmo se confía a un dispositivo automático.

EL MÁS IMPORTANTE

Ejecutor- algún objeto (persona, animal, dispositivo técnico) capaz de ejecutar un determinado conjunto de comandos.

Un ejecutante formal siempre ejecuta la misma orden de la misma manera. Para cada albacea formal se puede especificar: gama de tareas a resolver, entorno, sistema de mando y modo de funcionamiento.

Algoritmo- una descripción de la secuencia de acciones destinadas a un ejecutante específico que conduce desde los datos iniciales al resultado requerido, que tiene las propiedades de discreción, comprensibilidad, certeza, efectividad y carácter masivo.

Capacidad del intérprete para actuar. formalmente Proporciona la capacidad de automatizar las actividades humanas.

Preguntas y tareas

1. Lea los materiales de presentación del párrafo contenido en solicitud electrónica al libro de texto. ¿La presentación complementa la información contenida en el texto del párrafo? ¿Qué diapositivas podrías agregar a tu presentación?

2. ¿Qué se llama algoritmo?

3. Elija sinónimos de la palabra “receta”.

4. Da ejemplos de algoritmos que estudiaste en la escuela.

5. ¿Quién puede ser el ejecutor del algoritmo?

6. Dé un ejemplo de un artista formal. Dé un ejemplo cuando una persona actúa como intérprete formal.

7. ¿Qué determina la gama de tareas realizadas por el ejecutante “computador”?

8. Considere el procesador de textos de su computadora como ejecutor. Describa la gama de tareas resueltas por este ejecutante y su entorno.

9. ¿Qué es un equipo, un sistema de órdenes de ejecución?

10. ¿Qué comandos debe realizar un robot para las siguientes funciones?

a) cajero en una tienda;
b) un conserje;
c) un guardia de seguridad?

11. Enumere las principales propiedades del algoritmo.

12. ¿A qué puede conducir la ausencia de alguna propiedad en un algoritmo? Dar ejemplos.

13. ¿Cuál es la importancia de poder ejecutar formalmente un algoritmo?

14. La secuencia de números se construye de acuerdo con el siguiente algoritmo: los dos primeros números de la secuencia se toman iguales a 1; Se considera que cada número siguiente de la secuencia es igual a la suma de los dos números anteriores. Escribe los primeros 10 términos de esta secuencia. Descubre cómo se llama esta secuencia.

15. Cierto algoritmo obtiene una nueva cadena a partir de una cadena de caracteres de la siguiente manera. Primero, se escribe la cadena original de caracteres, luego se escribe la cadena original de caracteres en orden inverso, luego se escribe la letra que sigue en el alfabeto ruso después de la letra que estaba en el último lugar en la cadena original. Si la letra "I" está en el último lugar de la cadena original, entonces la letra "A" se escribe como la siguiente letra. La cadena resultante es el resultado del algoritmo. Por ejemplo, si la cadena de caracteres original era "CASA", entonces el resultado del algoritmo será la cadena "DOMMODN". Se proporciona la cadena de caracteres "COM". ¿Cuántas letras “O” habrá en la cadena de caracteres que se obtendrá si aplicas el algoritmo a esta cadena y luego aplicas el algoritmo nuevamente al resultado de su trabajo?

16. Encuentra una animación de los pasos del algoritmo de Eratóstenes en Internet. Utilice el algoritmo de Eratóstenes para encontrar todos los números primos que no excedan 50.

17. ¿Cuál será el resultado de la ejecución del algoritmo por parte de Turtle (ver ejemplo 5)?

18. Escriba un algoritmo para el ejecutor de la Calculadora (ver ejemplo 6), que contenga no más de 5 comandos:

a) recibir del número 3 el número 16;
b) recibir del número 1 el número 25.

19. Sistema de comandos del ejecutante El constructor consta de dos comandos, a los que se les asignan números:

1 - asignar 2
2 - dividir por 2

Según el primero de ellos, se suma 2 al número de la derecha, según el segundo, el número se divide por 2. ¿Cómo se convertirá el número 8 si el ejecutante ejecuta el algoritmo 22212? Cree un algoritmo en el sistema de comandos de este ejecutor, según el cual el número 1 se convertirá en el número 16 (el algoritmo no debe contener más de 5 comandos).

20. ¿En qué celda debe ubicarse el robot ejecutante (ejemplo 7) para poder regresar a él después de ejecutar el algoritmo 3241?

Software libre:

Sistema KuMir: conjunto de mundos educativos (descargue el archivo del programa del sitio web) o visite la página de KuMir ((http://www.niisi.ru/kumir/)

Suspenda AdBlock en este sitio.

En esta lección veremos algunos conceptos teóricos que formalizan el concepto de programación. Al mismo tiempo, formularemos con mayor precisión la tarea principal de su formación.

Para empezar te sugiero que juegues un poco con el siguiente juguete infantil. Complete las primeras cinco tareas, regrese y continúe leyendo la lección.

Fig.1 Captura de pantalla del campo de juego en code.org

Espero que todo te haya salido bien. Ahora, usando este ejemplo, describiremos varios conceptos básicos:

ejecutor;
sistema de comandos del ejecutante;
algoritmo.

En el juguete controlamos un pájaro rojo. El objetivo de cada etapa es llevar el pájaro al cerdo. El pájaro puede ejecutar ciertos comandos, por ejemplo: avanzar, girar a la izquierda, girar a la derecha, etc.

Se llama ejecutor a una persona, máquina o dispositivo que puede ejecutar algunas órdenes. En este juguete, obviamente, el intérprete es un pájaro. El conjunto de comandos que el ejecutante comprende y puede ejecutar se llama sistema de comandos ejecutores.

La secuencia de comandos que un ejecutante debe ejecutar para resolver un problema se llama algoritmo.

Es necesario centrarse en varios puntos.

El ejecutor puede ejecutar sólo aquellos comandos que están incluidos en su sistema de comando.

Esto significa, por ejemplo, que no puedes escribirle al pájaro intérprete: "¡Ve al cerdo!" Puedes escribirlo con mayor precisión, pero no pasará nada, porque... el ejecutante de tales comandos no lo sabe.

Podrás anotar los comandos disponibles en el orden que consideres correcto. Su tarea como programador es dividir una tarea grande y compleja en pequeños pasos individuales, cada uno de los cuales será comprensible para el ejecutante. El principio de “divide y vencerás” está nuevamente en vigor.

El intérprete hace exactamente lo que el algoritmo le dice que haga.

El artista del pájaro es muy confiado. Ella no cuestiona lo que escribes en el programa. Si, por ejemplo, te olvidas de girar el pájaro, se estrellará contra la pared. Por lo tanto, debes controlar todo tú mismo.

Sus programas futuros a menudo no funcionarán como esperaba. Los errores le suceden a todo el mundo. Aquí es importante entender que no es la computadora la que es estúpida, sino que cometiste un error en el algoritmo. No seas como los malos programadores, para quienes el programa siempre tiene la culpa de todo.

Pasemos ahora del ejemplo ilustrativo a la realidad informática. Escribimos programas para la computadora, lo que significa que la computadora en nuestro caso es la ejecutora. El sistema de comando son funciones y construcciones estándar del lenguaje C.

¿Cuál es el objetivo principal de su enseñanza de los conceptos básicos de programación? Domina la habilidad del pensamiento algorítmico. Es decir, aprender a escribir la solución a varios problemas en forma de algoritmo para un ejecutante específico (en nuestro caso, una computadora).

Entonces, para resumir:

Programa de computadora– un algoritmo para resolver un problema, escrito en un lenguaje de programación.

Un algoritmo es una descripción precisa del orden de acciones que un ejecutante debe realizar para resolver un problema.

Un ejecutor es una persona o algún dispositivo que puede comprender y ejecutar un determinado conjunto de comandos.

La palabra "algoritmo" proviene del nombre del matemático árabe del siglo IX al-Khwarizmi, quien formuló las reglas para realizar operaciones aritméticas.

Algoritmo– una instrucción precisa y comprensible para el ejecutante para ejecutar la secuencia final de comandos que van desde los datos iniciales hasta el resultado inicial.

Ejemplos: rutina diaria, orden de cocción, instrucciones, etc.)

Ejecutor de algoritmos– este es quien ejecuta el algoritmo (persona, animal, máquina, computadora).

Sistema de comando ejecutor- este es el conjunto completo de comandos que el ejecutante sabe ejecutar (entiende). El algoritmo sólo se puede construir a partir de comandos incluidos en el sistema de comandos ejecutores.

Por ejemplo, ejecutante El robot puede ejecutar comandos hacia adelante, atrás, izquierda, derecha, pintar. Se mueve a través de un campo celular delimitado por una pared y que contiene paredes. El robot no puede atravesar la pared.

Propiedades del algoritmo:

1.Rendimiento (extremidad)– la capacidad de obtener un resultado a partir de los datos iniciales en un número finito de pasos. (Por ejemplo, al ejecutar el algoritmo para sumar 2 números, se debe obtener la suma).

2.Carácter masivo– la capacidad de aplicar el algoritmo a una gran cantidad de datos de origen diferentes. (Por ejemplo, puedes sumar 2 números cualesquiera, conociendo el algoritmo de suma).

3.Determinismo(certeza, precisión): cada comando debe determinar de forma única la acción del ejecutante.

4.Comprensibilidad– el comando debe estar escrito en un lenguaje comprensible para la computadora.

5.Discreción– dividir el algoritmo en comandos separados.

Formas de escribir el algoritmo:

1) En lenguaje natural: grabación en forma de comandos separados en un lenguaje comprensible para los humanos.

2) Gráfico – en el lenguaje de los diagramas de flujo, utilizando formas geométricas (óvalo, rectángulo, paralelogramo, rombo).

3) En un lenguaje algorítmico: un lenguaje para escribir algoritmos para enseñar programación. Los comandos están escritos en ruso.

4) En un lenguaje de programación: un programa. Lenguajes de programación: Basic, Pascal, C, Visual Basic.

B7.Estructuras algorítmicas básicas: seguimiento, ramificación, bucle; imagen en diagramas de bloques. Dividir las tareas en subtareas. Algoritmos auxiliares.

Diseños algorítmicos. Dentro de los algoritmos, se pueden distinguir grupos de pasos que difieren en su estructura interna: construcciones algorítmicas.

Construcciones algorítmicas básicas Son secuencias lineales de pasos (o siguientes), ramificaciones y bucles.

Un algoritmo en el que los comandos se ejecutan secuencialmente uno tras otro se llama algoritmo lineal.

Así es como se ve un algoritmo lineal en lenguaje de diagrama de bloques:

Ejemplo: algoritmo para encender la computadora:

Encienda la computadora (presione el botón en Protector contra sobretensiones).
Encienda el monitor y la impresora.
Hacer clic Botón de encendido en unidad del sistema.
Esperar a cargar Sistema operativo y la apariencia del Escritorio.
Ponte a trabajar.

En este algoritmo, todas las acciones deben realizarse secuencialmente una tras otra: no puede comenzar a trabajar si la alimentación o el monitor no están encendidos.

En la estructura algorítmica " derivación" incluido condición, dependiendo de la veracidad de la condición, se ejecuta una u otra secuencia de comandos (serie).

Una condición es una afirmación que puede ser verdadera o falsa. En la condición, dos números, dos cadenas, dos variables o expresiones de cadena se comparan entre sí mediante operadores de comparación (>,<, =, >=, <=).

Grabación en lenguaje algorítmico: IfCondition Then Serie 1 (If Condición cierto, entonces cierto Episodio 1, Si Condición falso, entonces no se ejecuta nada). Ejemplo: Si hoy es domingo, entonces no es necesario ir a la escuela. Forma completa de ramificación.

En estructuras algorítmicas ciclo Incluye una serie de comandos que se ejecutan repetidamente. Esta secuencia de comandos se llama cuerpo del bucle.

Hay dos tipos de estructuras algorítmicas cíclicas:

bucles contrarrestados, en el que el cuerpo del bucle se ejecuta un determinado número de veces;
bucles condicionales, en el que el cuerpo del bucle se ejecuta siempre que se cumpla la condición.

Bucle con contador– se utiliza cuando se sabe de antemano cuántas repeticiones del cuerpo del bucle deben realizarse.

Algoritmo y sus propiedades.

Algoritmo- una instrucción clara y precisa al ejecutante para ejecutar la secuencia final de comandos que van desde los datos iniciales hasta el resultado deseado.

Ejecutor de algoritmos- este es el objeto o sujeto cuyo control está diseñado para el algoritmo.

El sistema de comando del ejecutante (SCS) es el conjunto completo de comandos que el ejecutante puede ejecutar.

Propiedades del algoritmo: comprensibilidad, precisión, finitud.

Claridad: el algoritmo se compone únicamente de comandos incluidos en el SKI del ejecutor.

Exactitud: Cada comando del algoritmo de control determina la acción inequívoca del ejecutante.

Acabado (o rendimiento): La ejecución del algoritmo debe conducir a un resultado en un número finito de pasos.

Entorno del intérprete: el entorno en el que opera el intérprete.

Una determinada secuencia de acciones del ejecutante siempre se aplica a algún datos fuente. Por ejemplo, para preparar un plato según una receta culinaria, se necesitan los productos adecuados (datos). Para resolver un problema matemático (resolver una ecuación cuadrática), necesita datos numéricos iniciales (coeficientes de ecuación).

Conjunto de datos completo: un conjunto de datos necesario y suficiente para resolver la tarea (obtener el resultado deseado).

Métodos para escribir algoritmos.

Los métodos más comunes son: gráfico, verbal y en la forma programas de computador.

Método gráfico Implica el uso de ciertos símbolos gráficos: bloques.

Nombre del bloque	Designación de bloque	Contenido
Proceso		Procesamiento de datos
Toma de decisiones		Un bloque lógico para comprobar la verdad o falsedad de una determinada condición.
Transferencia de datos		Entrada o salida de información
empezar, parar		Inicio o fin del programa
Modificación		Organización de un proceso cíclico - encabezado del ciclo

La colección de bloques forma el llamado diagrama de flujo del algoritmo.

Grabación verbal Los algoritmos se centran principalmente en el intérprete humano y permiten registrar diferentes instrucciones, pero la grabación debe ser bastante precisa.

Al escribir algoritmos en la forma programas Las computadoras utilizan lenguajes de programación: sistemas para codificar instrucciones y reglas para su uso. La escritura de algoritmos en forma de programas se caracteriza por un alto grado de formalización.

Algoritmos para trabajar con cantidades. Estructuras algorítmicas básicas.

Una cantidad es un único objeto de información que tiene un nombre, un valor y un tipo.

El ejecutante de algoritmos para trabajar con cantidades puede ser una persona o un dispositivo técnico especial, como una computadora. Tal artista debe tener memoria para almacenar cantidades.

Las cantidades pueden ser constantes o variables.

Valor constante (constante) no cambia su valor durante la ejecución del algoritmo. Una constante puede indicarse por su propio valor (números 10, 3,5) o por un nombre simbólico (número).

Valor variable Puede cambiar el valor durante la ejecución del algoritmo. Una variable siempre se designa con un nombre simbólico (X, A, R5, etc.).

Tipo de cantidad define el conjunto de valores que puede tomar un valor y el conjunto de acciones que se pueden realizar con ese valor. Tipos básicos de cantidades: enteras, reales, simbólicas, lógicas.

Expresión- un registro que define la secuencia de acciones sobre cantidades. Una expresión puede contener constantes, variables, signos de operación y funciones. Ejemplo:

A+B; 2*XY; K + L - pecado(X)

Un comando de asignación es un comando del ejecutor que da como resultado que una variable reciba un nuevo valor. Formato de comando:

nombre de variable>:=expresión>

El comando de asignación se ejecuta en el siguiente orden: primero se calcula y luego el valor resultante se asigna a una variable.

Ejemplo. Dejemos que la variable A tenga el valor 6. ¿Qué valor recibirá la variable A después de ejecutar el comando: A:= 2 * A - 1?
Solución. Calcular la expresión 2*A - 1 con A=6 dará como resultado el número 11. Esto significa que el nuevo valor de la variable A será igual a 11.

En lo que sigue se supondrá que el ejecutante de algoritmos para trabajar con cantidades es una computadora. Cualquier algoritmo se puede construir a partir de comandos. asignaciones, aporte, producción, derivación Y ciclo.

Comando de entrada- un comando mediante el cual se configuran valores de variables a través de dispositivos de entrada (por ejemplo, un teclado).

Ejemplo: aporte A: ingresar el valor de la variable A desde el teclado de la computadora.

Comando de salida: comando que muestra el valor de una cantidad en un dispositivo de salida de computadora (como un monitor).

Ejemplo: conclusión X: el valor de la variable X se muestra en la pantalla.

comando de rama- divide el algoritmo en dos caminos dependiendo de alguna condición; luego la ejecución del algoritmo pasa a la continuación general. La ramificación puede ser completa o incompleta. Descripción de ramificaciones en diagramas de bloques y en lenguaje algorítmico:

Aquí, una serie significa uno o más comandos secuenciales; kv - final de la ramificación.

Comando de bucle asegura la ejecución repetida de una secuencia de comandos (cuerpo del bucle) en función de alguna condición.

Bucle con condición previa- un bucle cuya ejecución se repite hasta que la condición del bucle sea verdadera:

Bucle con parámetro- ejecución repetida del cuerpo del bucle mientras el parámetro entero recorre el conjunto de todos los valores desde el inicial (In) hasta el final (Ik):

Ejemplo. Se dan dos fracciones simples. Crea un algoritmo para obtener una fracción que sea el resultado de su división.
Solución. En forma algebraica, la solución al problema es la siguiente:
a/b: c/d = a*d/b*c = m/n
Los datos iniciales son cuatro cantidades enteras: a, b, c, d. El resultado son dos números enteros my n.

alg dividir fracciones
intacto a, b, c, d, m, n
iniciar entrada a B C D
m:=a*d
n:=b*c
salida "Numerador=", m
salida "Denominador=", n
koi

Tenga en cuenta que para generar texto (cualquier secuencia de caracteres), debe escribirse entre comillas en el comando conclusión.

Efimova O., Morozov V., Ugrinovich N. Curso de tecnología informática con los conceptos básicos de la informática. Tutorial para la escuela secundaria. - M.: LLC "Editorial AST"; ABF, 2000
Libro-taller de problemas en informática. En 2 volúmenes/Ed. I. Semakina, E. Henner. - M.: Laboratorio de Conocimientos Básicos, 2001.
Ugrinovich N. Ciencias de la Computación y tecnologías de la información. 10-11 grados - M.: Laboratorio de conocimientos básicos, JSC "Libros de texto de Moscú", 2001

Tareas y pruebas sobre el tema "Algoritmos y ejecutores".

Dibujante de gestión de artistas - Algoritmos 6to grado
Lecciones: 4 Asignaciones: 9 Pruebas: 1
2 Tareas: 9 Pruebas: 1

¡Querido estudiante!

El conocimiento del tema "Algoritmos y ejecutores" es necesario principalmente para seguir estudiando la programación. Se eligió el lenguaje de programación QBasic como base para estudiar programación. Abandonamos la idea de incluir Visual Basic o cualquier otro lenguaje de programación orientado a objetos en nuestro curso, ya que este enfoque aún no se ha utilizado ampliamente en la mayoría de las escuelas secundarias de la Federación de Rusia. Además, la programación orientada a objetos se basa en los principios de la programación clásica de Dos.

Nuestro curso está diseñado para el programa de educación general. Al prepararse para los exámenes de ingreso en tecnología de la información a las universidades, debe familiarizarse con los detalles del estudio de programación en una universidad determinada. En algunos casos, es necesario un estudio en profundidad de varios temas, por ejemplo, "Arrays". Deberías prestar atención a esto cuando estudies literatura de programación; tal vez deberías usar recomendaciones metodológicas sobre preparación para los exámenes, que actualmente se publican en la mayoría de las instituciones de educación superior.

En conclusión, observamos que lograr "acrobacias aéreas" en la programación sólo es posible con práctica constante y resolviendo problemas aplicados específicos.

Popular en la categoría: