Lenguaje de Diseño - Departamento de Informática · algoritmos escritos en él. Lenguaje de...

1

Lenguaje de Diseño

Primera Parte

Segundo Cuatrimestre 2018

Fund. de la Informática – Int. a la Programación – Int. a la Computación

Resolución de Problemas y Algoritmos

2

Etapas en el proceso de resolver un problema:

1- Comprender el problema:

4 Descomposición del problema.

2- Concebir un plan: Definir una abstracción

4 Determinar un algoritmo. 4 Codificar ese algoritmo.

4- Visión Retrospectiva: perfeccionar la solución

4 Ejecutar el algoritmo bosquejado. 4 Corregir (depurar) el algoritmo.

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

3- Ejecutar el plan: 4 Comprobar cada uno de los pasos. 4 Énfasis en la habilidad de ejecutar el plan trazado y no en realizar los cálculos en sí.

Timba

3

No obstante: El algoritmo expresado en el lenguaje del problema NO es comprensible para la entidad procesadora (COMPUTADORA).

Deben traducirse las acciones a un conjunto de instrucciones elementales entendibles por dicha entidad procesador (CODIFICAR).

CODIFICAR las acciones en el lenguaje que entiende la computadora.

Acción de codificar = PROGRAMACIÓN.

LENGUAJE DE PROGRAMACIÓN. Inconvenientes:

4 Complejo. 4 Alto nivel de detalle. 4 Específico.

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

4

Algoritmo Lenguaje del Problema

Lenguaje de Programación

Codificación

Proceso de resolución de un problema:

Algoritmo Lenguaje del Problema

Lenguaje de Programación Lenguaje de Diseño

Codificación

Se redefine:

4 Complementar el proceso de resolución. 4 Ofrecer una visión global del proceso. 4 Independizarse de cualquier procesador especifico. 4 Simplificar la tarea de codificación.

Objetivo:

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

5

El objetivo fundamental de un lenguaje de diseño es ser comprensible para las personas que van a interpretar los algoritmos escritos en él.

Lenguaje de Diseño vs Lenguaje de Programación

El fin último de un lenguaje de programación es ser comprensible por la computadora que va a ejecutar el programa.

Lo primero a considerar en el proceso de resolución de problemas es la formalización de su ambiente. Donde se definen un conjunto de reglas que permitirán describir, con precisión y sin ambigüedad, los objetos del universo de un problema.

6

Variable

Atributos Nombre

Tipo de Datos

Funcionalidad Almacena un dato temporalmente

Es posible cambiar su contenido durante el ciclo de vida de un proceso

Lenguaje de Diseño

Una constante es un objeto cuyo valor no puede cambiar

t3 – al objeto NUMERO lo inicializo con el valor 1 Por ejemplo

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

7

Lenguaje de Diseño

El tipo entero, consiste de un conjunto finito de valores de los números enteros. La cardinalidad de este conjunto es la del conjunto de los enteros.

El tipo real, consiste de un conjunto finito de valores de los números reales. La cardinalidad de este conjunto es la del conjunto de los reales.

El tipo lógico, también llamado tipo booleano, es el conjunto de los valores de verdad: VERDADERO y FALSO.

El tipo caracter es el conjunto finito y “ordenado” de caracteres que el procesador puede reconocer.

Tipos de datos primitivos

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

8

² las letras mayúsculas del abecedario . ² las letras minúsculas del abecedario. ² los dígitos decimales del 0...9. ² el caracter de espacio blanco, caracteres especiales tales como: *, +, -, _, /,(, ), , , , $, ^, %, $, < ,>, “, .

Lenguaje de Diseño

El tipo caracter es el conjunto finito y “ordenado” de caracteres que el procesador puede reconocer.

Tipos de datos primitivos

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

9

t1 – definir el objeto NUMERO del tipo entero Por ejemplo

NUMERO : entero

<nombre de varible> [, <nombre de variable>]* : <tipo>

Lenguaje de Diseño

Variables

Toda variable debe definirse indicando el tipo de valores que la misma puede

tomar.

t1 – definir los objetos NUMERO, POTENCIA del tipo entero

NUMERO, POTENCIA: entero Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

Un procesador debe ser capaz de manipular los objetos del ambiente de un algoritmo.

10

Debe poder realizar cálculos

Expresan con EXPRESIONES

Lenguaje de Diseño

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

11

Expresiones Aritméticas:

Lenguaje de Diseño

Expresiones

Tipos:

Las expresiones están conformadas por Operandos y Operadores.

Aritméticas. Lógicas. Relacionales.

//

Operador Significado + suma - resta * producto / división

potencia ↑

resto

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

12

Orden de evaluación (precedencia) :

, //

Orden de precedencia Operadores Significado 1 potenciación (se aplica

de derecha a izquierda) 2 *, / Multiplicación, división

y resto (se aplican de izquierda a derecha)

3 +, - suma y resta (se aplican de izquierda a derecha)

↑

Lenguaje de Diseño

Expresiones Aritméticas

Ejemplo 1: 8 + 7 * 3 + 4 * 5 * 4

21 20 8 +

29

4 *

80 +

109 Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

13

Orden de evaluación (precedencia) :

, //

Orden de precedencia Operadores Significado 1 potenciación (se aplica

de derecha a izquierda) 2 *, / Multiplicación, división

y resto (se aplican de izquierda a derecha)

3 +, - suma y resta (se aplican de izquierda a derecha)

↑

Lenguaje de Diseño

Expresiones Aritméticas

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

14

Asignación Aritmética:

t31 - dar a AGREGO el valor 1

AGREGO ← 1

Lenguaje de Diseño

Sentencia de Asignación

Por ejemplo

<nombre de varible> <valor constante> ←

La acción AGREGO ← 1 significa asignar a la variable de nombre AGREGO, el valor 1.

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

15

Lenguaje de Diseño

Sentencia de Asignación

Por ejemplo

La acción A ← B significa dar a la variable de nombre A, el valor de la variable B.

A ← B

6 A

7 B

7 A

7 B

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

16

Lenguaje de Diseño

Sentencia de Asignación

Por ejemplo

La acción SUM ← E, siendo E una expresión, significa dar a la variable de nombre A, el resultado de la evaluación de la expresión E.

SUM ← 3.5 + 4.0 * (-7.2)

-25.3 SUM

E

3.5 + 4.0 * (-7.2) = -25.3

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

17

Lenguaje de Diseño

Sentencia de Asignación

Por ejemplo

La acción A ← A + X, siendo X un valor constante, significa incrementar en X el valor de A y guardarlo en la variable A.

A ← A + X

5.6 A

6.6 A

X= 1.0

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

18

Lenguaje de Diseño

Ejemplo

Enunciado: dados dos números enteros positivos, digamos m y n, encontrar el algoritmo que determine la potencia n-ésima de m. Con n > 1.

Procesador: computadora. Acciones primitivas:

4 Dar un valor a un objeto. 4 Calcular la suma de dos números. 4 Calcular el producto de dos números. 4 conjunto repetitivo de acciones expresado: Mientras <condición> Hacer

<acciones-primitivas> Repetir.

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

19

Análisis del problema:

•  Si se tiene que m representa el valor 4 y n representa el valor 3, entonces se calcula: 43 = 4 x 4 x 4 = 64. •  Si se tiene que m representa el valor 2 y n representa el valor 6, entonces se calcula: 26 = 2 x 2 x 2 x 2 x 2 x 2 = 64.

Generalizando

mn = m x m x … x m

Variables

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

(mn-1 x m)

(mn-2 x m)

(mn-3 x m)

(m2 x m) (m x m)

n veces se repite m

•  Cuantas veces se realizó la operación? •  Cada operación es igual a la anterior?

Si mn = m x m x … x m

mn =

Variables

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

21

8 x 82

8

8 x 81

83 = 8 x 8 x 8

Número a multiplicar (base de la potencia)

Cálculo previo a ser reutilizado

Número de veces que se realizó la multiplicación

Realizar: 83

2

83

3 índice de la potencia

Variables

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

22

Determinación de las variables que contienen información necesaria: 1- objeto conteniendo el entero positivo al cual se le

calcula la potencia (base de la potencia).

2- objeto conteniendo el entero positivo que indica la potencia (exponente de la potencia).

3- objeto que determine cuantas multiplicaciones se deben realizar. 4- objeto que mantenga los cálculos previos para poder

realizar los nuevos cálculos.

Ambiente: 4 variables

Variables

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

Versión 2: t1 - Determinar nombres y tipos de las variables. t2 - Dar valores iniciales a las variables. t31 - Comenzar con el entero 1. t32 - Para todo entero positivo menor que el valor indicado como índice, multiplicar el número dado por el resultado anterior.

23

Algoritmo: (Solución en Lenguaje de Problemas) Versión 1:

t1 - Determinar nombres y tipos de las variables. t2 - Dar valores iniciales a las variables. t3 - Contando desde 1, multiplico el entero por la potencia anterior, tantas veces como lo indica el índice de la potencia.

Variables

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

24

Determinar nombres y tipos a las variables.

Dar valores iniciales a las variables.

C

tomar el número y multiplicarlo por el resultado anterior. .

F

entero < índice pot.

Comenzar con el entero 1.

Tomar un nuevo entero.

V

F

Diagrama de Flujo

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

25

Bosquejo del algoritmo (en lenguaje de problemas): NUMERO, POTENCIA, PREVIO, VECES: entero NUMERO m (el que se desee) POTENCIA n (mayor que 1) PREVIO m VECES 1 MIENTRAS el valor de VECES sea menor que el valor de POTENCIA HACER

PREVIO NUMERO * PREVIO VECES VECES + 1

FINMIENTRAS

Lenguaje de Diseño

Ejemplo

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

26

¿Qué son las condiciones? ¿Cómo ante ciertas situaciones de conflicto se toma una decisión?

Expresiones Lógicas Expresiones Relacionales

Expresiones Lógicas

Operador Lógico Significado∧ y (and)∨ o (or)¬ no (not)

Lenguaje de Diseño

Expresiones

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

27

Lenguaje de Diseño

Expresiones Lógicas

V ← E

ü  es una asignación lógica si: ü  V, es una variable lógica. ü  E, es una constante lógica (VERDADERO, FALSO), una variable lógica, una expresión relacional o una expresión lógica.

Por ejemplo

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

28

Ejemplo:

Si A = VERDADERO, B = FALSO entonces la expresión A ∧ B ∨ (¬ B) dacomo resultado:

A ∧ B ∨ (¬ B)

V F V

F

VERDADERO Expresiones Relacionales

Dada cualquier expresión expresada por medio de los operadores relacionales, su evaluación debe darme como resultado un valor de verdad Verdadero o Falso.

Lenguaje de Diseño

Expresiones Lógicas

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

29

A >= 15 {Verdadero, Falso}

3 A

Predicado ValorA >= 15 FALSOA = 15 FALSOA < 15 VERDADERO

Predicado

Combinaciones (Expresiones lógicas y Relacionales)

• Sean X, K y Z tres variables enteras cuyos valores son 1, 3 y 2 respectivamente,

• sean los predicados elementales p = “X = 1”, q =“K < 2” y r = “Z >= 5”

• Y sea el siguiente predicado compuesto:

( X = 1 ∨ K < 2 ) ∧ Z = 5 Entonces para conocer su valor de verdad se puede construir la tabla de verdad correspondiente:

(p ∨ q) ∧ r

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

30

De ahora en más nos referiremos, cuando hablemos de predicados, a las CONDICIONES

Lenguaje de Diseño

Expresiones Lógicas

(X=1 ∨ K < 2) ∧ Z=5

Verdadero Falso Falso

Verdadero

Falso

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

31

Lenguaje de Diseño

Expresiones Lógicas

Bosquejo del algoritmo (en lenguaje de problemas): NUMERO, POTENCIA, PREVIO, VECES: entero NUMERO m (el que se desee) POTENCIA n (mayor que 1) PREVIO m VECES 1 MIENTRAS el valor de VECES sea menor que el valor de POTENCIA HACER

PREVIO NUMERO * PREVIO VECES VECES + 1

FINMIENTRAS

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

32

Lenguaje de Diseño

Expresiones Lógicas

Bosquejo del algoritmo en lenguaje de diseño: NUMERO, POTENCIA, PREVIO, VECES: entero NUMERO 8 POTENCIA 3 PREVIO 8 VECES 1 MIENTRAS VECES < POTENCIA HACER PREVIO NUMERO * PREVIO VECES VECES + 1 FINMIENTRAS

Inconveniente: Este algoritmo solamente calcula 83

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

33

Entrada/Salida de Datos/ Información

ESCRIBIR V

Llamaremos escritura a la acción primitiva que permite la salida de valores del ambiente a través de un dispositivo. Esta acción toma uno o más valores del ambiente y lo comunica al medio externo.

Lectura, es toda acción que permite la entrada de uno o más valores del ambiente a través de un dispositivo. Una lectura es una asignación, en el sentido que toma valores del medio externo y lo asigna a las variables del ambiente. La operación de lectura es una acción primitiva.

LEER <nombre de la variable> LEER V

ESCRIBIR <nombre de la variable> ESCRIBIR V

Lenguaje de Diseño

Entrada/Salida

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

34

ALGORITMO “Potencia n de m” COMENZAR NUMERO, POTENCIA, PREVIO, VECES: entero LEER NUMERO LEER POTENCIA PREVIO NUMERO VECES 1 MIENTRAS VECES < POTENCIA HACER PREVIO NUMERO * PREVIO VECES VECES + 1 FINMIENTRAS ESCRIBIR PREVIO FIN

Por Ejemplo Lenguaje de Diseño

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

35

Lenguaje de Diseño

Estructuras de Control

•  Secuencial

•  Condicional

•  Repetición o Iteración

Es determinado por el orden en que se definen las sentencias: una debajo de la otra.

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

36

Estructuras de Control: Condicional

tarea i tarea j condición

V F

tarea j

condición V F

SI <condición> ENTONCES <alternativa verdadera> SINO <alternativa falsa> FINSI

SI <condición> ENTONCES <alternativa verdadera> FINSI

Lenguaje de Diseño

37

Estructuras de Control: Repetición

tarea i

Cond? F

V

MIENTRAS <condicion> HACER <secuencia de acciones>

FINMIENTRAS

Lenguaje de Diseño

Estructura de Control

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

38

ALGORITMO “Potencia n de m” COMENZAR NUMERO, POTENCIA, PREVIO, VECES: entero LEER NUMERO LEER POTENCIA PREVIO NUMERO VECES 2 MIENTRAS VECES <= POTENCIA HACER PREVIO NUMERO * PREVIO VECES VECES + 1 FINMIENTRAS ESCRIBIR PREVIO FIN

Por ejemplo

Lenguaje de Diseño

Repetición

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

39

Estructuras de Control: Repetición

tarea i

Cond? F

V

PARA <nombre de vble> DESDE Vi HASTA Vf CONPASO P HACER

<secuencia de acciones> FINPARA

Donde:

Lenguaje de Diseño

Repetición

•  Vi es el valor inicial que recibe <nombre de vble>

•  Vf es el valor final que tomará <nombre de vble>

•  P es el valor de incremento/decremento

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

40

Para paso P positivo Para paso P negativo MIENTRAS V <= Vf HACER MIENTRAS V >= Vf HACER <secuencia de acciones> <secuencia de acciones> REPETIR REPETIR

V ← Vi V ← Vi

V ← V + P V ← V - P

ALGORITMO “Potencia n de m” COMENZAR NUMERO, POTENCIA, PREVIO, VECES: entero LEER NUMERO LEER POTENCIA PREVIO NUMERO PARA VECES DESDE 2 HASTA POTENCIA CONPASO 1 HACER PREVIO NUMERO * PREVIO FINPARA ESCRIBIR PREVIO FIN

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

41

ALGORITMO “Ejercicio” X ←10 Y ←1 MIENTRAS X <> 10 ∨ Y <> 10 HACER

ESCRIBIR “Ingrese un numero AA” LEER AA ESCRIBIR “Ingrese un numero BB” LEER BB SI AA = BB ENTONCES CC ← FALSO FINSI Y ← Y + 1 X ← X + 2

FINMIENTRAS ESCRIBIR X, Y FIN

Ejercicio: ¿es un algoritmo? ¿es correcto el algoritmo?

Lenguaje de Diseño

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018

42

ALGORITMO “Ejercicio” X: entero Y: entero AA, BB: entero CC: logico X ←10 Y ←1 MIENTRAS X <> 10 ∨ Y <> 10 HACER

ESCRIBIR “Ingrese un numero AA” LEER AA ESCRIBIR “Ingrese un numero BB” LEER BB SI AA = BB ENTONCES CC ← FALSO FINSI Y ← Y + 1 X ← X + 2

FINMIENTRAS ESCRIBIR X, Y FIN

Lenguaje de Diseño

Fund. de la Informática -Introd.a la Computación -Introd.a la Programación (1er Cuatrimestre 2016)

Res. De Problemas y Algoritmos - F. de la Informática -Int.a la Computación -Int.a la Programación 2018