ALGORITMOS YESTRUCTURAS DE DATOS

(ST–221)

Profesora: Ing. Irma Inga Serrano

2008-II

UNIVERSIDAD NACIONAL DE INGENIERIA

Facultad de Ingeniería Industrial y de Sistemas

Area de Sistemas Computación e Informática

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S

GENERALIDADES

DATOEs la representación simbólica de un hecho, atributo o característica de

una entidad.Ejm: nota de un alumno, nombre de un docente, color de un carro, etc.

INFORMACIONEs un dato útil.Ejm. El promedio final de un alumno para un curso, número de

aprobados en un examen, nombre de los primeros alumnos de cada especialidad por cada ciclo.

La información se obtiene mediante el procesamiento de los datos

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S

Procesador

Entrada Salida

Algoritmo

DATOS INFORMACION

Es realizado por el procesador el cual ejecuta un conjunto de

pasos previamente definidos (algoritmo)

El procesamiento de datos puede ser:

Manual

Mecanizada (uso de calculadora, sumadora, etc)

Automatizado (uso del computador)

PROCESAMIENTO DE DATOS

Operaciones que transforman datos en información

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S

PROCESAMIENTO DE DATOS AUTOMATIZADO

Entrada

DATOS

Salida

INFORMACION

Programa

Algoritmo

Procesador

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S Elementos del Computador

+

HARDWARE (elem.físicos)

SOFTWARE (programa)

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S HARDWARE (componentes físicos)

Unidades PeriféricasDe Entrada

Ejem.TecladoMouseEscaner, etc

UnidadesPeriféricasDe Salida

Ejm.ImpresoraMonitor,Parlantes, etc.

Unidades deAlmacenamiento.

Ejem. Disquete,Discos compactos,Discos duros, etc.

Unidad deControl

UnidadAritméticaY Lógica

Memoria PrincipalRAM y ROM

UNIDAD CENTRAL DE PROCESO

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S

SOFTWARE (Conjunto de Programas)

TIPOS DE SOFTWARE:

- Sistemas operativosEjm. DOS, Windows, Linux, etc.

- Aplicaciones de uso generalEjm. Word, Excel, Power Point,

etc.

- Aplicaciones de uso específico

Ejm. sistema de notas, sistema de facturación,etc)

Programa 1 Programa 2

Programa 3

MEMORIA RAM

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

SFASES PARA LA CONSTRUCCION DE UN PROGRAMA

SOLUCION DEL PROBLEMA

IMPLEMENTACIONEN LA

COMPUTADORA

Datos AlgoritmoPrograma

(Software)

Análisis del problema

Diseño del algoritmo

Verificación del algoritmoError de

lógicaOK

Codificación del algoritmo

(programa)

Ejecución del programa

Verificación del programa

Programa

Error

sintaxis

OK

Algoritmo

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S

ALGORITMO

Secuencia ordenada de pasos (acciones) para resolver un problema.

Se expresa en lenguaje natural

PROGRAMA

Es el algoritmo escrito en un lenguaje de programación para ser ejecutado por el computador.

Tipos de lenguajes de Programación:

Lenguaje de alto nivel: lenguaje similar al lenguaje natural. Son fáciles de escribir. Es el mas usado por los programadores.

Ejm. C++, Pascal, Basic, Prolog, Java, etc

Lenguaje de bajo nivel: lenguaje mnemotécnico.

Ejm. ADD M, N, P

Lenguaje de máquina: lenguaje binario (0 y 1) entendible directamente por el computador.

Ejm. 0110 1001 1010 1011

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S

TIPOS DE PROGRAMAS (según el Lenguaje de Programación)

PROGRAMA FUENTE (PF)

Programa escrito en lenguaje de alto o bajo nivel.

PROGRAMA OBJETO (PO):

Programa escrito en lenguaje de máquina. Es el que ejecuta el computador.

TRADUCTORES DE LENGUAJE

Programas que traducen programas fuente a lenguaje de máquina.

Programa Fuente

CompiladorProgramaObjeto

Programa Fuente Intérprete

Ejecución del Programa

Instrucción en leng.máq.

Ejecución de la Instrucción

Tipos de Traductores: Compiladores e Intérpretes

instrucción

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S

D A T O S

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S

Tipos de Datos (reconocidos por el computador):

DATOS

BASICOS COMPUESTOS

Numéricos Caracter Lógico Estático Dinámico

-Arreglos -Registros -Archivos

-Listas -Arboles -Grafos

-Enteros -Reales

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S

DATOS SIMPLES O DATOS BASICOS

DATOS NUMERICOS

Enteros y Reales

El rango y precisión de los datos numéricos depende del lenguaje de programación que se utilice.

DATOS TIPO CARACTER

Conjunto de caracteres que el computador reconoce.

Se encuentran normalizados bajo el código ASCII o EBCDIC

Se tienen:

Caracteres alfabéticos: A - Z ; a - z

Caracteres numéricos: 0 - 9

Caracteres especiales: *, / , +, >, <, =, etc.

DATOS TIPO LOGICO

Conjunto formado por dos valores lógicos:

verdad, falso

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S Operaciones con los datos

OPERACIONES INTERVIENEN OPERADORES RESULTADO

ARITMETICAS Datos

Numéricos

Aritméticos

+, - , *, /,

resto, entero

Dato

Numérico

DE

COMPARACION

Datos del

mismo tipo

Relacionales

>, <, >=, <=, =

Dato

Lógico

LOGICAS Datos

lógicos

Lógicos

No, Y, O

Dato

lógico

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S

IMPORTANTE:

En operaciones aritméticas:

Muchos lenguajes cuentan con operadores adicionales a los

conocidos como los operadores para datos enteros:

entero (a/b): división entera de a/b

resto (a/b): resto de la división entera de a/b

Ejm. 10+ resto(5/3) Resultado: 12

En operaciones de Comparación:

En la comparación de datos tipo carácter se tiene:

‘0’<‘1’<‘2’<..<’9’<‘A’<‘B’<…<‘Z’<‘a’<‘b’<..<‘z’

En datos tipo lógico:

falso < verdad

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S Expresión de los datos

Un dato puede venir expresado como: constantes, variables, expresiones, funciones, etc.

CONSTANTE

Es un dato (de cualquier tipo) cuyo valor no cambia durante la ejecución del algoritmo o programa.

Tipos de constantes:

Literal: es un valor expresado en forma explícita.

Ejm. 3.1416

Simbólica: viene expresado bajo un nombre que guarda su valor

Ejm. Pi (Previamente se debe definir que Pi = 3.1416)

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S

VARIABLE

Es un objeto (porción de memoria) que almacena un dato

Para definir una variable es necesario:

- Darle un Nombre

- Indicar el tipo de dato que va almacenar

OJO: El valor de una variable puede cambiar

durante la ejecución del algoritmo.

Tipos de variables:

Entero: Ejm. nota, edad, examen,

Real: Ejm. promedio, sueldo, talla

Carácter: Ejm. sección, sexo,

Lógica: Ejm. Fin, encontrado, vale

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S

Operador de asignación

Se utiliza para almacenar un dato en una variable,

perdiéndose cualquier otro valor

previamente almacenado en ella.

Se representa con el símbolo

Ejem.

Nota 12.3

Nota Nota +2

12.3

Nota

Memoria RAM

14.3

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S

EXPRESIONES

Es una combinación de operandos y operadores

Tipos:

Expresiones aritméticas

Operando: constantes, variables y expres. numér.

Operadores: aritméticos

Resultado: numérico

Ejm. (EP + 2*EF + PP)/4

Expresiones lógicas

Operando: constantes, variables y expres. lógicas

Operadores: lógicos y relacionales

Resultado: lógico

Ejm. (PP>6.1 y PF>6.1)

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S FUNCIONES

Son programas predefinidas que:

- Tienen un nombre con el cual se les invoca y

- Aceptan datos y devuelven un resultado.

Generalmente los lenguajes de programación poseen funciones matemáticas, de cadenas y otros.

Ejm. En C++

Abs(X): devuelve el valor absoluto del número entero X

Sqrt(X): devuelve la raiz cuadrada del número X (X>=0)

Identificadores

Son los nombres que se le dan a las constantes simbólicas, variables, funciones y otros.

Constan de una cadena de caracteres que debe empezar con una letra.

Deben ser significativos sugiriendo lo que representa.

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S

ACUMULADOR

Es una variable cuyo valor aumenta o disminuye en una

cantidad variable cada vez que se produce un determinado

suceso o acción.

Debe ser inicializado

Ejm. Se desea acumular las notas de prácticas de un alumno

Sum 0 (el valor de sum es 0)

sum sum + 13 (el valor de sum es 13)

sum sum + 10 (el valor de sum es 23)

CONTADOR

Es un acumulador cuyo valor aumenta o disminuye en una

cantidad constante cada vez que se produce un determinado

suceso o acción.

Se usa para contar sucesos. Ejm. Contar número de aprobados

VARIABLES IMPORTANTES

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S

DISEÑO DE ALGORITMOS

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S

ALGORITMO

Secuencia ordenada de pasos o acciones o instrucciones que se debe ejecutar para realizar una tarea o para resolver un problema.

Es expresado en lenguaje natural utilizando herramientas estandarizadas.

Características de un algoritmo

Preciso: El algoritmo debe indicar el orden en que se debe realizar cada paso.

Finito: El algoritmo tiene un número finito de pasos y debe terminar en algún momento.

Bien definido: Si el algoritmo se prueba dos veces con los mismos datos de entrada, se debe obtener el mismo resultado.

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S TECNICA DE PROGRAMACION ESTRUCTURADA

Conjunto de técnicas para desarrollar algoritmos fáciles de escribir, leer, verificar y modificar.

Diseño Modular ( Top-down )

En problemas grandes y complejos: dividir el problema en subproblemas y diseñar un subprograma para resolver cada uno de ellos

Descomposición del programa en recursos abstractos

Descompone una acción compleja en acciones simples capaces de ser ejecutadas por un computador

( instrucciones )

Estructuras de control básicas

Un programa se escribe utilizando 3 estructuras de control:

EC Secuenciales, EC Selectivas, EC Repetitivas

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S

INSTRUCCIONES

Son las acciones que van a ser ejecutadas por el computador

para resolver el problema.

TIPOS :

Instrucciones de Inicio/Fin :

Indica el Inicio y el Fin del algoritmo

Instrucciones de lectura:

Solicita al usuario el ingreso de datos desde un dispositivo de

entrada por ejemplo el teclado.

Instrucciones de escritura:

Muestra los resultados a través de un dispositivo de salida por

ejemplo la pantalla, impresora, etc.

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S

Instrucciones de asignación:

Almacena un valor en una variable, perdiéndose cualquier

otro valor almacenado en ella.

Instrucciones selectivas:

Permiten ejecutar unas u otras tareas de acuerdo al resultado

de una expresión condicional

Instrucciones repetitivas:

Permiten la repetición de un grupo de instrucciones,

generando un bucle (lazo o loop).

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S

EJEMPLO DE ALGORITMO

Se cuenta con las notas del EP, EF y PP de un alumno.

Se sabe que el promedio final (PF) se calcula con la fórmula:

PF=(EP+ PP+2EF)/4

Si el alumno cumple con la siguiente condición: PP>6.1 y

PF> 6.1 tiene opción a rendir un examen sustitutorio (ES)

Escriba un algoritmo reciba las notas del alumno y luego

muestre un mensaje indicando si el alumno puede rendir o no

puede rendir el ES.

En el caso que ya no pueda rendir el ES, debe mostrar

también el PF

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S

Análisis

Datos de entrada: EP, EF, PP

Salida: mensaje y PF (si no puede rendir ES)

Algoritmo

Inicio del algoritmo

Ingresar las notas del alumno: EP, EF y PP

Calcular PF con la siguiente fórmula:

PF = (EP + 2EF + PP)/4

Si cumple la condición PP> 6.1 y PF>6.1entonces mostrar

el mensaje “Puede rendir el ES”

Si no cumple la condición entonces mostrar el mensaje “No

puede rendir ES” y mostrar PF

Fin del algoritmo.

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S

HERRAMIENTAS PARA LA REPRESENTACION DE ALGORITMOS

Para representar los algoritmos en forma estandarizada, existen herramientas como:

Diagrama de flujo

Técnica tipo gráfico

Pseudocódigo

Lenguaje de especificación (palabras reservadas) en lenguaje natural

Diagrama de Nassi-Scheneiderman

Es una combinación de las dos anteriores

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S DIAGRAMA DE FLUJO PSEUDOCODIGO

Símbolos Significado Palabras reservadas

Inicio / Fin

Lectura / Escritura

Proceso

Selectiva

Selectiva múltiple

Inicio / Fin

Dirección o flujo

Leer / Escribir

Si - entonces

+ - * /

Caso - sea

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S El algoritmo en Diagrama de Flujo

Inicio

Leer EP,EF, PP

PF=(EP+PP+2*EF)/4

PP>6.1 y PF>6.1

Escribir “Puede rendir ES”

Escribir “No puede

rendir ES”

Fin

Escribir “La nota final

es: “ , PF

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S

Escritura de un algoritmo en pseudocódigo

CABECERAContiene el nombre del algoritmo (opcional)

ConstantesNombre-constante = valor

VariablesTipo-dato: nombre de variables

BLOQUE DE DECLARACIONES

Se utilizan para asignar espacios en la RAMSe declaran: Constantes (opcional),

Variables (obligatorio),Otros definidos por el usuario (opc.)

BLOQUE DE INSTRUCCIONES• Inicio/Fin• Lectura

Leer ( lista de variables)• Escritura

Escribir ( resultado)• Asignaciónnombre de la variable valor ó expresión

•Comentarios (no se ejecutan)Sirven para escribir información interna para facilitar el mantenimiento del algoritmo. Formato: // comentario

aAlgoritmo nombre del algoritmo

Inicio

instrucciones

Fin

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S El algoritmo en Pseudocódigo

Algoritmo PROMEDIO

Variables

entero: EP, EF

real: PP, PF

Inicio

Leer (EP, EF, PP)

PF (EP+PP+2*EF)/4 // Calcula PF

Si (PP>6.1 y PF>6.1)

Escribir ( “Puede rendir el ES”)

sino

Escribir (“No puede rendir el ES”)

Escribir (“La nota final es: “, PF)

Fin-si

Fin

Cabecera del algoritmo

Bloque de declaraciones

Bloque de Instrucciones

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S ESTRUCTURAS DE CONTROL

Un algoritmo debe ser escrito utilizando tres estructuras

de control:

E.C. Secuencial

Simple

E.C. Selectiva Doble

Múltiple

Desde

E.C. Múltiple Mientras

Repetir - hasta

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S

Estructura SECUENCIAL

Las acciones del algoritmo se ejecutan en el orden que se

encuentran escritos.

acción 1

acción 2

acción 3

-------

-------

acción n

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S Estructuras SELECTIVAS

Permiten ejecutar unas acciones u otras dependiendo del resultado de una condición

TIPOS DE ESTRUCTURAS SELECTIVAS

1. SELECTIVA SIMPLE

Las acciones se ejecutan si la condición es verdadera .

condición

acciones

V

F

Pseudocódigo

Si (condición)

acción1

acción 2

………

acción n

fin-si

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S

2. SELECTIVA DOBLE

Si la condición es Verdadera se ejecutan unas acciones.

Si la condición es Falsa se ejecutan otras acciones

condición

Acciones-F Acciones-V

VF

Pseudocódigo

Si (condición)

acciones 1

Sino

acciones 2

Fin-si

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S 3.- SELECTIVA MULTIPLE (Caso-sea)

Se utiliza para seleccionar una de entre múltiples alternativas. El

selector (variable, expresión o función ) se evalúa y compara

con cada una de las alternativas de Caso. El valor del selector

debe ser escalar (número entero o carácter).

Pseudocódigo

Caso selector sea

alt 1: acciones 1

alt 2: acciones 2

. ….

alt n: acciones n

Sino (opcional)

acciones F

Fin-caso

Selector

Acciones 1 Acciones 2 Acciones n

….Alt. 1 Alt. 2 Alt. n

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S Estructuras REPETITIVAS

Permiten repetir una o mas acciones un cierto número de veces.

Un BUCLE (loop, en inglés) es un trozo de algoritmo cuyas

instrucciones se repiten un cierto número de veces, mientras

o hasta que se cumpla una cierta condición.

La condición será evaluada en cada iteración (repetición) del

bucle.

Estructura repetitiva

acciones 1

acciones 2

….

acciones n

Fin-estructura repetitiva

Cuerpo del bucle

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S

TIPOS DE ESTRUCTURAS REPETITIVAS

1. DESDE - HASTA

Las acciones del bucle se repite un determinado número de

veces

Pseudocódigo

Desde con Vi hasta Vf (inc/dec) k

acción1

acción 2

………

acción n

fin-desdei

Con Vi

Con ≤ Vf

acciones

V

F

Con con +k

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S

2. MIENTRAS - HACER (estructura de entrada controlada)

Las acciones del bucle se ejecutan cuando la condición es V.

Las acciones se pueden ejecutar 0 o mas veces

Pseudocódigo

Mientras (condición) hacer

acción1

acción 2

………

acción n

fin-mientras

acciones

F

Condición

V

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S

3.a. REPETIR - HASTA (estructura de salida controlada)

Las acciones del bucle se ejecutan si la condición es F.

Las acciones se ejecutan 1 o mas veces

Pseudocódigo

Repetir

acción1

acción 2

………

acción n

Hasta (condición)

acciones

Condición

V

F

Un

ive

rsid

ad

Na

cio

na

l d

e I

ng

en

ierí

aFII

S

3.b. REPETIR - MIENTRAS (estructura de salida controlada)

Las acciones del bucle se ejecutan si la condición es V.

Las acciones se ejecutan 1 o mas veces

Pseudocódigo

Repetir

acción1

acción 2

………

acción n

Mientras (condición)

acciones

Condición

F

V