Presentación sobre el tema de la estructura de algoritmos. Estructuras de algoritmos básicos

Algoritmo y estructuras algorítmicas

Mosina A.Yu.

Algoritmo es una secuencia de acciones estrictamente definida al resolver un problema.

El algoritmo contiene varios pasos.

Paso del algoritmo es cada acción individual del algoritmo.

"Un algoritmo es un orden de acciones".

Ejecutor Es un objeto que realiza un conjunto específico de acciones.

El intérprete puede ser una persona, un robot, un animal o una computadora.

Sistema de comando ejecutor (ESQUÍ) es un conjunto de comandos que el ejecutante puede ejecutar.

Entorno del artista – el entorno en el que opera el artista.

• Desarrolla algoritmos: humanos.
• Los algoritmos son ejecutados por: personas y dispositivos: computadoras, robots, máquinas, satélites, complejos Accesorios, Juguetes de los niños.
• El intérprete resuelve el problema según un algoritmo determinado, siguiendo estrictamente las instrucciones (programa) sin ahondar ni discutir por qué lo hace.

Ejercicio: Nombra a los artistas intérpretes o ejecutantes de los siguientes tipos de trabajo:

Limpiar la basura en el patio.

Enseñar a los niños en la escuela.

Conducción de coche

La respuesta está en la pizarra.

Cocinando comida

Imprimir un documento en una impresora

Miembro– cada acción individual y el algoritmo en su conjunto deben poder completarse

Eficiencia– obtener resultados en un número finito de pasos

Discreción(discontinuidad, separación): dividir el algoritmo en pasos

Determinismo(certeza, precisión): cada acción debe definirse de forma estricta e inequívoca

Carácter masivo– uso de un algoritmo para resolver problemas similares

Propiedades del ALGORITMO

Clasificación de algoritmos por forma de presentación. :

Verbal

Tabular

Gráfico (diagramas de bloques)

Software

Diagrama de bloques – gráfico actuación algoritmo en forma de una secuencia de bloques funcionales interconectados ( elementos gráficos estándar ), cada uno de los cuales corresponde a la realización de una o más acciones.

Básico simbolos en diagramas de bloques

Símbolo

Propósito del bloqueo

Inicio o fin del algoritmo.

Entrada o salida de datos.

Dentro del bloque, los datos se enumeran separados por comas.

Proceso.

Las matemáticas están escritas dentro del bloque. Fórmulas y operaciones para el procesamiento de datos.

Comprobando el estado.

Las condiciones lógicas están escritas dentro del bloque. Tiene dos salidas Sí (+) y No (-).

Dirección.

Clasificación de algoritmos por estructura:

Lineal (siguiente)

Ramificado (rama, elección, alternativa)

Bucle (repetir)

Auxiliar

Conjunto

Algoritmo lineal

Algoritmo lineal Es un algoritmo cuyos pasos se realizan secuencialmente uno tras otro.

(Ejemplo: algoritmo de cobranza de cartera).

Estructura básica del algoritmo lineal:

Equipo Serie 1

Equipo Serie 2

Serie del equipo N

Tarea

Calcula el perímetro de un triángulo arbitrario basándose en sus tres lados.

Solución:

Nivel 1: Formulación del problema.

Datos iniciales: A, B, C – lados de un triángulo arbitrario

Producción: P – perímetro del triángulo.

Etapa 2: Modelo matemático.

P=A+B+C

Etapa 3: elaboración de un algoritmo

Comenzar

Ingresar

Conclusión

Fin

№ 1 Y usando el diagrama de flujo del algoritmo , calcular el valor de la función Y en X=2,

Comenzar

entrada: X

Z=8*X

• SOLUCIÓN:

• x=2
• Z = 8 * 2 = 16
• Z = √16 = 4
• Z = 4 – 1 = 3
• Y = 3 * 2 = 6
• Y = 6 / 3 = 2

Z = Z - 1

Y=3*X

Y=Y/Z

salida: Sí

• Los algoritmos pueden describir los procesos de transformación de una amplia variedad de objetos. La palabra "algoritmo" en sí proviene de "algorithmi", la ortografía latina del nombre del destacado matemático del siglo IX al-Khwarizmi, quien formuló las reglas para realizar operaciones aritméticas.
• Algoritmo- un conjunto de comandos que describen el orden de acciones del ejecutante para lograr el resultado de resolver un problema en un número finito de acciones.

Propiedades de los algoritmos:

1. Discreción- el algoritmo debe representar el proceso de resolución de un problema como la ejecución secuencial de ciertos pasos simples. Donde cada paso del algoritmo requiere una cantidad finita de tiempo para completarse, es decir, la transformación de los datos fuente en resultados se realiza de forma discreta en el tiempo.

2. Determinismo (certidumbre). En cada momento, el siguiente paso de trabajo está determinado únicamente por el estado del sistema. Por tanto, el algoritmo produce el mismo resultado (respuesta) para los mismos datos iniciales.

3. Claridad- el algoritmo debe incluir solo aquellos comandos que estén disponibles para el ejecutante y estén incluidos en su sistema de comando.

4. Integridad (extremidad)- con datos iniciales correctamente especificados, el algoritmo debe completar su trabajo y producir un resultado en un número finito de pasos.

5. Carácter de masas (universalidad). El algoritmo debe ser aplicable a diferentes conjuntos de datos de entrada.

6. Efectividad- finalización del algoritmo con determinados resultados.

Formas de escribir algoritmos:

1. Método de grabación verbal

La forma verbal de escribir algoritmos es una descripción de las sucesivas etapas del procesamiento de datos. El algoritmo se especifica en una presentación arbitraria. en lenguaje natural .

Ejemplo

Como ejemplo de una forma verbal de escribir un algoritmo, considere un algoritmo para encontrar el área de un rectángulo.

donde S es el área del rectángulo; a, b – las longitudes de sus lados.

Obviamente, a, b deben especificarse de antemano; de lo contrario, el problema no se puede resolver.

Formas de escribir algoritmos

La forma verbal de escribir el algoritmo se ve así:

• El comienzo del algoritmo.
• Establezca el valor numérico del lado a.
• Establezca el valor numérico del lado b.
• Calcula el área S del rectángulo usando la fórmula S=a*b.
• Muestra el resultado de los cálculos.
• Fin del algoritmo.

Formas de escribir algoritmos

2. Método gráfico

Cuando se presenta gráficamente, el algoritmo se representa como una secuencia de bloques funcionales interconectados, cada uno de los cuales corresponde a la ejecución de una o más acciones.

Esta representación gráfica se llama diagrama de flujo o diagrama de flujo. En el diagrama de flujo, cada tipo de acción (ingresar datos iniciales, calcular los valores de las expresiones, verificar las condiciones, controlar la repetición de acciones, completar el procesamiento, etc.) corresponde a una figura geométrica representada como un símbolo de bloque. Los símbolos de bloque están conectados por líneas de transición que determinan el orden en que se realizan las acciones. Los siguientes son los símbolos más utilizados.

Formas de escribir algoritmos

Elemento de diagrama de flujo

Nombre

Bloque computacional (bloque computacional)

Acciones computacionales o secuencia de acciones.

Bloque lógico (bloque de condición)

Bloque de entrada/salida de datos

Elegir la dirección de ejecución del algoritmo dependiendo de alguna condición.

Designación general para entrada (salida) de datos (independientemente del medio físico)

Principio (final)

Principio o fin de un algoritmo, entrada o salida en una subrutina

Formas de escribir algoritmos

Elemento de diagrama de flujo

Nombre

Proceso de usuario (subrutina)

Cálculo utilizando un programa o subrutina estándar

Bloque de modificación

La función realiza acciones que cambian puntos (por ejemplo, el encabezado del bucle) del algoritmo.

Conector

Indicando la conexión mediante líneas discontinuas entre flujos de información.

Formas de escribir algoritmos

Ejemplo

Algoritmo para calcular el área de un rectángulo.

Formas de escribir algoritmos

3. Pseudocódigos

descripciones semiformalizadas de algoritmos en un lenguaje algorítmico condicional, incluidos elementos de un lenguaje de programación y frases en lenguaje natural, notaciones matemáticas generalmente aceptadas, etc.

No existe una definición única o formal de pseudocódigo, por lo que son posibles varios pseudocódigos, que se diferencian en el conjunto de palabras funcionales y construcciones básicas (básicas).

Formas de escribir algoritmos

Ejemplo

• Comenzar. Ir al punto 2.
• Ingresando los números a y b. Ir al punto 3.
• Calcule S=a*b. Ir al punto 4.
• Conclusión S. Pasar al punto 5.
• Fin.

Formas de escribir algoritmos

4. Método de software

Grabación del algoritmo en el lenguaje de programación seleccionado.

Ejemplo

Escribir('');

Writeln('S=', S);

Tipos de algoritmos

1. Algoritmo lineal

Este es un algoritmo en el que solo hay una estructura siguiente.

Siguiente- Esta es la disposición de acciones una tras otra.

Tipos de algoritmos

2. Algoritmo de ramificación (si... entonces... en caso contrario...)

Este es un algoritmo que tiene una estructura ramificada.

Derivación- esta es la elección de una acción en función del cumplimiento de alguna condición.

Tipos de algoritmos

3. Algoritmo cíclico

Este es un algoritmo que tiene una estructura de bucle.

Ciclo- Esta es la repetición repetida de cualquier acción.

Tipos de algoritmos

4. Algoritmo combinado

Un algoritmo que contiene varias estructuras simultáneamente.

Ancho de bloque píxeles

Copia este código y pégalo en tu sitio web

Títulos de diapositivas:

Algoritmos y estructuras de datos Literatura:

• D. Knut. El arte de la programación informática. T. 1-3, M.: Mir, 1978, 1995, etc.
• N. Wirth. Algoritmos y estructuras de datos. M.: Mir, 1989.

Concepto de tipo de datos

• Información que debe ser procesado en el ordenador es abstracción, mostrando algún fragmento del mundo real. Es decir, el fragmento que es el área temática del problema que se resuelve. Para resolverlo, primero construimos informativo, y en el caso general matemático modelo estudió área temática y se selecciona uno existente o se construye uno nuevo algoritmo resolviendo el problema.

• Información siempre se materializa, se representa en la forma mensajes. En general, un mensaje representa algo registrado señal fisica . Señal- Este cambio en el tiempo o el espacio de algún objeto, en particular, un parámetro de alguna cantidad física, por ejemplo, la inducción del campo magnético (al almacenar información, mensajes más precisamente en medios magnéticos) o el nivel de voltaje en el circuito eléctrico (en chips de procesador o RAM).

• Discreto un mensaje es una secuencia señales(valores de señal) de algunos final alfabeto(un conjunto finito de valores de parámetros de señal), en particular, para una computadora esto es una secuencia de caracteres del alfabeto binario, es decir, una secuencia de bits.

• Datos informáticos Estos son mensajes discretos que se presentan en una forma utilizable por una computadora. comprensible por computadora. Para un procesador de computadora, cualquier dato es no estructurado secuencia de bits (a veces se utiliza el término fluir bits).

• La interpretación específica de esta secuencia depende del programa, de formularios de presentación y estructuras de datos, que son seleccionados programador. Esta elección depende en última instancia del problema que se resuelve y de la conveniencia de realizar acciones sobre los datos.

• Significados inmediatos Este inmutable objetos de programa que se representan a sí mismos: números (25, 1.34E-20), símbolos ('A', '!'), cadenas ('Ingrese elementos de la matriz');
• Constantes son nombres asignados a ciertos valores (const pi=3.1415926).
• variables estos son objetos que pueden tomar un valor, guardarlo sin cambiarlo y cambiarlo cuando se realizan ciertas acciones (var k:integer, x:real, a:array).
• Valores de expresión y función. Las expresiones y funciones son reglas para calcular valores escritos de cierta manera: k*x+ sqrt(x).

• Los datos de los programas incluyen:

• El tipo de datos es la característica más importante que determina:

• conjunto de valores válidos;
• muchas operaciones que se pueden realizar sobre un valor;
• estructura de valores (escalar, vectorial, etc.);
• un método de representación mecánica del significado.

• Para mostrar las características de la representación informática de datos de diversa naturaleza en la informática, las disciplinas informáticas utilizan los más importantes. concepto de tipo de datos.

• El tipo de constante, variable o expresión se puede determinar mediante apariencia(de la imagen) o de la descripción sin realizar ningún cálculo.
• Cualquier operación o función requiere argumentos y devuelve un resultado de un tipo muy específico. Los tipos de argumentos y resultados de las operaciones se determinan según reglas bien definidas del lenguaje.

• Principios básicos del concepto de tipo de datos.
• en lenguajes de programación:

• Variedades de tipos y estructuras de datos.

• La informática utiliza una gran cantidad de diferentes tipos, varios estructuras de datos, que se utilizan para modelado objetos encontrados en los problemas bajo consideración.

• Si la estructura de un algoritmo dado no cambia durante la ejecución, entonces dicha estructura se considera estático , Estructuras de datos estáticas. existir sin cambios durante todo el tiempo de ejecución del algoritmo.

• Significado escalar(simple, atómico) tipo presentado liso uno componente (ejemplo: tiempo, temperatura).

• Estructuras dinámicas son creados, modificados y destruidos según sea necesario en cualquier momento durante la ejecución del algoritmo.

• Significado estructurado(compuesto) tipo presentado más cómo uno componente (ejemplo: vector, matriz, tabla, etc.).

• Hay tipos predefinidos (predefinidos): estándar y definidos por programa. Para estándar Los tipos en la descripción de un lenguaje de programación definen todas sus características: un conjunto de valores, un conjunto de operaciones, estructura y representación mecánica de un valor. Para recién definido tipos, el lenguaje proporciona un mecanismo para especificar un conjunto de valores en un programa y la estructura del valor. Por lo general, se construye un nuevo tipo sobre la base de los estándar existentes. Por lo tanto, muchas operaciones y la representación mecánica de dichos tipos están fijadas en la descripción del lenguaje.

• tipos escalares (simples, atómicos):
• entero;
• real;
• lógico (booleano);
• simbólico;
• tipos estructurados (compuestos):
• formación;
• grabación;
• archivo (secuencia);
• un montón de;
• tipo de objeto (clase);
• todas las combinaciones posibles de tipos escalares y estructurados;
• tipo de referencia.

• Tipos estáticos (estructuras de datos)

• Los tipos escalares predefinidos más utilizados son: entero ( entero), real ( real), simbólico ( carbonizarse), booleano( booleano).

• Valores enteros exactos. Ejemplos: 73, -98, 5, 19674.
• Representación de la máquina: formato de punto fijo. El rango de valores está determinado por la longitud del campo. Operaciones: +, -, *, div, mod,=,<, и т.д.

• Tipo entero

• Aproximaciones no enteras. Ejemplos: 0,195, -91,84, 5,0
• Representación de la máquina: formato de punto flotante. El rango y la precisión de los valores están determinados por la longitud del campo. Operaciones: +, -, *, /, =,<, и т.д.

• Tipo real

• Caracteres de texto únicos. Ejemplos: 'a', '!', '5'.
• Representación de la máquina: formato ASCII. El conjunto de valores está determinado por la tabla de códigos y las capacidades del teclado. Operaciones: +, =,<, и т.д.

• Tipo carbonizarse

• Dos valores booleanos falso y verdadero. Es más, falso
• Representación de la máquina ─ valor de cero y un bit: falso se codifica 0, verdadero ─ 1. Operaciones: , , , =,< и т.д.

• Tipo booleano

• Mecanismos básicos para la construcción de nuevos tipos discretos escalares: enumeración, restricción. en definicion transferible tipos, se fija una lista de todos los valores posibles, muchas operaciones se definen de antemano en el lenguaje. en definicion limitado tipos como un conjunto de valores válidos es fijo subconjunto un conjunto de valores de algún tipo discreto, que en este caso se denomina tipo base en relación al definido.

• Hay tipos escalares discretos y continuos. Múltiples significados discreto tipo finito o contable. Múltiples significados continuo tipo más que contable. Los tipos estándar discretos incluyen números enteros, de caracteres y lógicos. Los tipos estándar continuos incluyen reales.

• Los tipos estructurados (compuestos) se caracterizan por: el número y el tipo posible de componentes de valor, así como la forma en que se accede a un componente de valor individual.

• Las estructuras similares a vectores y matrices en informática suelen denominarse matrices. Todos los elementos de la matriz deben ser una y las mismas tipo.

• Matriz o tipo regular

• Para acceder (consultar) a un elemento de matriz individual, se utilizan uno o varios índices (w; w; A). Los índices pueden ser expresiones cuyos valores pueden variar arbitrariamente dentro de límites predefinidos. Por lo tanto, dicen que los elementos de la matriz tienen acceso directo.

• Las estructuras similares a las filas de una tabla se denominan registros. Los componentes de los registros generalmente se denominan campos. Se pueden crear varios campos (columnas de tabla). diferente tipos. Para acceder a campos individuales de un registro, son fijos e inmutables nombres. Por ejemplo: Dia de Victoria. Mes:= mayo. Los campos se pueden seleccionar para su procesamiento en cualquier orden, por lo que se dice que el acceso a los componentes del registro es derecho.

• Tipo récord o combinado

• Dia de Victoria:

• Archivo (secuencia)

• La principal estructura de datos que se utiliza para almacenar información en dispositivos externos (discos magnéticos, cintas, etc.) es archivos o secuencias. Se considera que el archivo siempre está en el dispositivo externo. En este caso, se desconoce la cantidad de componentes del archivo; todos los componentes deben ser del mismo tipo. Acceso a componentes ─ coherente.

• El vuelo de Gagarin:

• Un montón de

• En muchos problemas matemáticos y de información existe la necesidad de utilizar directa o indirectamente el objeto matemático principal. conjuntos. El tipo de datos correspondiente a un conjunto está por definición estructurado, ya que en el caso general un conjunto puede constar de más de un elemento, y al mismo tiempo las operaciones deben realizarse con todos los elementos del conjunto como un todo. El número de elementos de un conjunto no se determina de antemano y puede cambiar con el tiempo. Todos los elementos del conjunto deben ser del mismo tipo. Acceso a elementos individuales del conjunto No. Sólo puedes saber si un elemento pertenece a un conjunto o no, incluir un elemento en el conjunto o excluirlo del conjunto. También se proporcionan operaciones estándar sobre conjuntos: unión, intersección, resta, etc.

• X1 X5 X4

• Estructuras de datos dinámicas

• Datos con una estructura dinámica en el tiempo. cambios sí misma estructura, y no solo la cantidad de elementos, como archivos o secuencias. Las estructuras de datos dinámicas básicas son:

• un objeto;
• lista lineal;
• árbol;
• grafico.

• En una lista lineal, cada elemento está relacionado con el anterior. Para una lista lineal, sabemos qué elemento está al principio de la lista, cuál está al final y también qué elemento viene antes del actual. En una lista lineal, puede pasar del elemento actual al siguiente únicamente utilizando conexiones específicas entre elementos vecinos.

• lista lineal

• Por lo general se obtiene una cadena de elementos en los que se puede buscar, en la que se pueden insertar elementos o excluirlos.

• Muchos otros tipos de estructuras dinámicas se organizan sobre la base de una lista lineal. Esto es en particular: anillos, colas, cubiertas Y pilas.

• Estructura de anillo

• La diferencia entre un anillo y una lista lineal es que un anillo tiene una conexión entre el último elemento de la lista y su primer elemento.

• Para una lista lineal y un anillo, es posible acceder a cualquier elemento de la estructura. Para hacer esto, debe pasar secuencialmente de un elemento a otro. En muchas situaciones del mundo real, dicho acceso ausente. Puedes interactuar solo con el primer y último elemento, o solo con uno de ellos. Se utilizan colas, mazos y pilas para modelar dichos objetos.

• Estructura de cola

• El final de la cola está disponible para su inclusión y el comienzo está disponible para su exclusión (selección). El elemento que llegó antes a la cola y al que se le da servicio primero. Dicen que una cola es una estructura con disciplina de servicio FIFO (F primero I norte, F primero oh ut) ─ “el primero en llegar, el primero en irse”.

• Estructura de cubierta

• La baraja tiene ambos extremos disponibles, tanto para inclusión como para muestreo. Así, podemos decir que Dec ─ es cola de dos vías.

• Estructura de pila

• Una pila tiene sólo un extremo de la estructura disponible para la interacción: la parte superior de la pila. Tanto la inclusión de un nuevo elemento en la pila como la selección del último elemento previamente incluido pasa por la parte superior de la pila. Por lo tanto, el artículo que llegó último se procesa primero. Dicen que un stack es una estructura con una disciplina de mantenimiento LIFO (l ast I norte, F primero oh ut) ─ “el último en llegar, el primero en irse”.

• ¡GRACIAS POR SU ATENCIÓN!

Estructuras básicas de los algoritmos. Impongamos algunas restricciones a
estructura del diagrama de flujo.
Construiremos un algoritmo usando solo
tres fragmentos de cierto
configuraciones.
Llamémoslas estructuras básicas.
algoritmos.

La primera estructura básica es la siguiente.
Consiste en una cadena de bloques sin
ramificaciones.

Derivación

Sí
No
condición

Un caso especial de ramificación.
condición

La ramificación se utiliza en los casos en que
cuando necesitas elegir uno de
dos formas de resolver el problema.

Ciclo

El ciclo se utiliza en los casos en que
para resolver el problema es necesario
repetir las mismas cosas una y otra vez
comportamiento.

Bucle con poscondición

Bucle con condición previa

Ciclo paramétrico

Ciclo paramétrico controlado
parámetro.
Un parámetro de bucle es una variable.
que cambia monótonamente en el ciclo,
y el criterio de salida depende de ello
ciclo.

yo:= en
Cuerpo
ciclo
yo:= yo + di
No
Sí
yo > ik

yo:=en
yo>ik
Cuerpo
ciclo
i:=i+di

Diseño de algoritmos complejos

Método de diseño de algoritmos de arriba hacia abajo

El método consta de los siguientes pasos:
la tarea original se divide en subtareas,
conectado por algún algoritmo;
este algoritmo está siendo depurado;
cada subtarea se considera como
tarea;
el proceso continúa hasta
la tarea original no será completamente
resuelto.

Ejemplo

Dada la ecuación ax2 + bx + c = 0 y la función
f(x).
Si una ecuación tiene dos reales
raíces x1 y x2, construye una tabla de valores
función en el segmento que consta de n
puntos.

Algoritmo de nivel superior
Entrada a,b,c
Solución
ecuaciones
No
x1, x2
encontró
Sí
Ingrese n
Construcción
mesas
no hay ninguna decisión
DETENER

Algoritmo que implementa el subproblema de solución.
ecuación cuadrática
d:=b2 – 4ac
No
D>0
Sí
X1=(- b + √ d)/2/a
X2= (- b - √ d)/2/a

Algoritmo para construir una tabla de valores.
funciones
h=(x2-x1)/(n-1)
x = x1
yo=1
Salida x, f(x)
x=x+h
yo = yo +1
Sí
No
yo>n

Así, la solución al problema
El problema consta de un algoritmo superior.
nivel y dos subtareas.
Algoritmo que vincula subtareas
Solución
ecuaciones
Construcción
tablas f(x)