introducci on a los computadores (cnm-130) algoritmos...

Introduccion Diagramas de flujo Ejercicios FreeDFD Pseudocodigo Referencias

Introduccion a los Computadores (CNM-130)Algoritmos computacionales

Alejandro Piedrahita H.

Instituto de MatematicasFacultad de Ciencias Exactas y Naturales

Universidad de Antioquia

Copyleft «2013. Reproduccion permitida bajo los

terminos de la licencia de documentacion libre GNU.

http://ciencias.udea.edu.co/


Contenido

1 Introduccion

2 Diagramas de flujo

3 Ejercicios en flujo en FreeDFD

4 Pseudocodigo

5 Referencias


Etapas en la resolucion de un problema

Definicion del problema: el enunciado completo del problema,¿que es lo que se pretende obtener?

Analisis del problema:

un conjunto de datos de entrada (la informacion dada)

un conjunto de datos de salida (lo que se desea obtener)

Relaciones que vinculen los datos de entrada y salida

Diseno de la solucion: se debe proponer o aplicar un modelo paralograr sistematizar la busqueda de la solucion.

Codificacion: en esta etapa se describen los pasos que se debenejecutar para resolver el problema (algoritmo).

Prueba: se verifica el funcionamiento de la solucion propuesta y sedetectan los errores que se presenten con la posterior correccion de losmismos (depuracion).


Ejemplo

Algoritmo para preparar “frıjoles con chicharron” para 8 raciones. Losdatos de entrada (ingredientes) son:

2 libras de frıjoles.

1 cucharada de aceite vegetal ode girasol.

1/4 de libra de tocino cortadoen trocitos.

2 zanahorias peladas.

2 cubos de caldo de carne.

1 cucharada de sal.

16 tazas de agua.

Algoritmo

1 Se lavan bien los frıjoles y se dejan remojando en el aguadesde la noche anterior.

2 Al dıa siguiente, se ponen en la olla a presion con el agua enque se remojaron, el aceite, el tocino y la zanahoria.

3 Se cocinan sin sal hasta que esten blandos, aproximadamente por1 hora.

4 Se licua una peque~na cantidad de los frıjoles con la zanahoria,los cubos de caldo y la sal, y se agrega a los frıjoles.

5 Se cocinan media hora mas con la olla destapada hasta queespesen.


Otros ejemplos

Muchos “algoritmos” no requieren de un computador para suejecucion:

Cambiar la llanta de un carro

Ir al banco a pagar una cuenta

Ir a un restaurante a comer

Determinar la cantidad de dinero que nos deben devolver al pagar el bus

Comprar una libra de azucar

En la practica, un algoritmo es solo una parte de las etapas requeridaspara resolver un problema:

Diseno del algoritmo.

Implementacion del algoritmo en un lenguaje de programacion adecuado(codificacion).

Ejecucion y validacion del programa por el computador.


Algoritmos

Definicion 1.1 (Algoritmo)

Un algoritmo es una secuencia finita de instrucciones, reglas o pasos quedescriben de modo preciso las operaciones que un computador debe realizarpara ejecutar una tarea determinada en un tiempo finito.

Cinco propiedades ampliamente aceptadas como requisitos para unalgoritmo (Knuth):

Finitud: Un algoritmo siempre debe terminar despues de un numerofinito de pasos.

Precision: cada paso de un algoritmo debe estar precisamente definidoy sin ambiguedades.

Entrada: un algoritmo tiene cero o mas entradas que le son dadas antesde que el algoritmo comience, o dinamicamente mientras corre.

Salida: un algoritmo tiene una o mas salidas.

Eficacia: las operaciones a realizar en un algoritmo deben sersuficientemente basicas como para que en principio puedan serrealizadas de manera exacta y en un tiempo finito por un hombreusando papel y lapiz.


Diseno de algoritmos

Herramientas utilizadas para disenar algoritmos

Diagramas de flujo: representacion esquematica de un algoritmo quemuestra graficamente los pasos a seguir para alcanzar la solucion de unproblema.

Pseudocodigos: forma generica de escribir un algoritmo, por medio deun lenguaje simple sin necesidad de conocer la sintaxis de un lenguajede programacion.

El diagrama de flujo se compone de figuras que ilustran los pasos oprocesos a seguir para alcanzar la solucion del problema.

Los sımbolos presentados permiten crear una estructura grafica flexibleque ilustra los pasos a seguir.

Un diagrama de flujo permite con facilidad la posterior escritura de unprograma en algun lenguaje de programacion.


Diagramas de flujo

Sımbolo utilizado para marcar el inicio y el fin deldiagrama de flujo.

Sımbolo utilizado para ingresar los datos de entrada(expresa lectura).

Sımbolo utilizado para representar un proceso. En suinterior se expresan asignaciones, operacionesaritmeticas, cambios de valor de celdas en memoria, etc.

Sımbolos utilizados para indicar la direccion del flujodel diagrama.

Sımbolo utilizado para representar la estructuraselectiva si entonces; en su interior se almacena unacondicion que determina el flujo del diagrama.

Sımbolo utilizado para representar la estructuraselectiva si entonces/sino; en su interior se almacenauna condicion que determina el flujo del diagrama.


Diagramas de flujo

Sımbolo utilizado para representar una decisionmultiple. En su inetrior se almacena un selector ydependiendo de su valor, se sigue por una de las ramas.

Sımbolo utilizado para representar la impresion de unresultado (expresa escritura).

Sımbolo utilizado para expresar conexion dentro deuna misma pagina.

Sımbolo utilizado para expresar conexion entrepaginas diferentes.

Sımbolo utilizado para expresar un modulo de unproblema: para continuar con el flujo normal deldiagrama es necesario primero resolver el subproblemaenunciado en su interior.


Diagramas de flujo

Esquema general de un diagrama de flujo


Reglas para la construccion de diagramas de flujo

Todo diagrama de flujo debe tener un inicio y un fin.

Las lineas utilizadas para indicar la direccion del flujo del diagramadeben ser rectas verticales y horizontales y no se deben cruzar.


Reglas para la construccion de diagramas de flujo

Todas las lineas utilizadas para indicar la direccion del flujo deldiagrama deben estar conectadas.

El diagrama de flujo debe ser constuido de arriba hacia abajo(top-down) y de izquierda a derecha (left-right).

La notacion empleada en el diagrama de flujo debe ser independientedel lenguaje de programacion.

Si el diagrama de flujo requiere mas de una hoja para su construccion,se debe utilizar conectores adecuados y enumerar las paginasconvenientemente.

A un sımbolo del diagrama (excepto lıneas) no puede llegar mas de unalınea.


Diagramas de flujo en FreeDFD

Editor e interprete de diagramas de flujo

Permite editar, ejecutar y depurar algoritmos representados comodiagramas de flujo

Es software libre distribuido bajo la licencia publica GNU (GPL)

Lo puede descargar y ejecutar en Linux por medio de Wine mientrassale una version para GNU/Linux

Fue desarrollado por estudiantes de la Universidad de Magdalena


Interfaz de FreeDFD

Barra de menus

Permite crear y guardar diagramas de flujos (archivos .dfd)

Barra de herramientas

Objetos: permiten crear un diagrama de flujo

Ejecucion: permite ejecutar, detener y pausar un diagrama de flujo

Area de trabajo


Objetos en FreeDFD

(a) Inicio (b) Lectura (c) Asignacion

(d) Condicional (e) Ciclo para (f) Ciclo mientras

(g) Salida (h) Llamada (i) fin


Ejercicios en FreeDFD

Ejercicio 3.1

Realice un diagrama de flujo tal que dado los datos A, B, C y D querepresentan numeros, escriba los mismos en orden inverso.

Ejercicio 3.2

Modifique el diagrama de flujo del ejercicio anterior (3.1) para que los datosde salida:

1 se impriman separados por espacios

2 se impriman separados por comas



Ejercicio 3.3

Realice un diagrama de flujo que reciba como datos de entradas dos numerosm y n y escriba el resultado de la suma y el producto de los mismos.

Ejercicio 3.4

Modifique el diagrama de flujo del ejercicio anterior (3.3) para que en lugarde imprimirse el valor de la suma y el producto, se impriman los mensajes:

1 “La suma de ♦ y � es 4” y

2 “El producto de ♦ y � es ♥”

donde ♦ representa el valor de m, � el valor de n, 4 el valor de la suma y♥ el valor del producto.



Ejercicio 3.5

A un estudiante obtiene 5 calificaciones a lo largo del semestre. Realice undiagrama de flujo que reciba como datos de entrada las calificaciones delestudiante e imprima el promedio de sus calificaciones. Se debe imprimir unmensaje que diga “El promedio de las calificaciones es . . . ”

Ejercicio 3.6

Desarrolle un diagrama de flujo tal que dado como datos la base y la alturade un rectangulo, calcule su perımetro y area.



Ejercicio 3.7

Implemente un diagrama de flujo tal que dado el costo de un artıculovendido y la cantidad de dinero entregada por el cliente, calcule e imprimael cambio que se debe entregarsele.

Ejercicio 3.8

Realice un diagrama de flujo que reciba como datos el nombre de undinosaurio, su peso (en toneladas) y su altura (en pies), y que escriba elnombre del dinosaurio, su peso en kilogramos y su altura en metros.



Ejercicio 3.9

En una gasolinera las maquinas registran el combustible surtido en galonespero el precio de la gasolina esta fijado en litros. Realice un diagrama deflujo que calcule e imprima el valor que hay que cobrarle al cliente.

Ejercicio 3.10

Implemente un diagrama de flujo que reciba como datos el radio y la alturade un cilindro y calcule e imprima su area y volumen.



Ejercicio 3.11

Desarrolle un diagrama de flujo que calcule e imprima el numero desegundos que hay en un determinado numero de dıas.

Ejercicio 3.12

Se desea conocer cuantos meses han transcurrido entre enero de 1949 yenero de 2002. Realice un diagrama de flujo que resuelva dicho problema.

Ejercicio 3.13

Se desea determinar los meses transcurridos entre los inicios de dos anoscualesquiera. Realice un diagrama de flujo que resuelva dicho problema.


Terminologıa basica

Programa: conjunto de instrucciones que ejecuta un computador paraalcanzar un resultado especıfico (Von Neumann, 1946).

Un programa se escribe en un lenguaje de programacion a partir deun diagrama de flujo disenado con anterioridad.

Los lenguajes de programacion estan constituidos por un conjunto de

Reglas sintacticas: especifican la formacion (sintaxis) de instruccionesvalidas.

Reglas semanticas: especifican el significado de las instruccionesvalidas.

Pasos en la resolucion de un problema:

1 Desarrollo de un algoritmo (solucion general).

2 Construccion de un diagrama de flujo.

3 Construccion de un programa en un lenguaje de programacion.

Previo al paso (3), utilizaremos un “lenguaje” llamado pseudocodigo:

Es independiente de cualquier lenguaje de programacion.

Carece del rigor expresados en las reglas sintactias y semanticas.


Instrucciones en pseudocodigo

Lectura de datos:

Leer A, VEL, C

Proceso:

Hacer TEMP = TEMP + 1

Escritura:

Escribir A, VEL


Ejemplos

Programa en pseudocodigo para el diagrama de flujo del ejercicio (3.1)

INVERTIR DATOS

{ Dado un conjunto de datos de entrada elprograma invierte el orden de los mismos ylos imprime }

{ A, B, C y D son variables de tipo entero }1 Leer A, B, C, D

2 Escribir D, C, B, A

Observaciones

Todo programa tiene un nombre (en este ejemplo INVERTIR DATOS)que lo define y que se elige teniendo en cuenta las reglas para laconstruccion de identificadores.

Entre llaves {· · · } van comentarios que indican la funcion del programa.

Escribir un programa es sencillo cuando se conoce las instrucciones delpseudocodigo. La “tarea intelectual” consiste en la construccion deldiagrama de flujo.


Ejemplos


CALCULA

{ Dado dos enteros m y n, el programacalcula el resultado de la suma y el productode los mismos }

{ m y n son variables de tipo real, al igualque las variables sum y prod }

1 Leer m, n

2 Hacer sum = m + n

3 Hacer prod = m×n

4 Escribir sum, prod


Ejemplos


CALCULA

{ Dado el radio r y la altura h de un cilindro,el programa calcula el area y el volumen delcilindro }

{ r y h son variables de tipo real, al igual quelas variables area y vol }

1 Leer r, h

2 Hacer pi = 3.1416

3 Hacer area = 2× pi× r2 + 2× pi× r× h

4 Hacer vol = pi× r2× h

5 Escribir area, vol


Bibliografıa I

J.W. Brown, D.J. MurdochA First Course in Statistical Programming With RCambridge University Press, 1th edition , 2008

D. BurtonElementary Number TheoryMcGraw Hill Higher Education, 5th edition, 2002

O. CairoMetodologıa de la programacionSegunda edicion. Alfaomega Grupo Editor, S.A., 2005

M.A. CriadoProgramacion en lenguajes estructuradosAlfaomega Grupo Editor, S.A. de C.V. Primera Edicion, 2006

H.P. LangtangenA Primer on Scientific Programming with PythonSpringer, 2011


Bibliografıa II

O. Jones, R. Maillardet, A. RobinsonIntroduction to Scientific Programming and Simulation Using RChapman and Hall/CRC; 1 edition, 2009

D.E. KnuthThe Art of Computer ProgrammingVolume 1, Fundamental AlgorithmsAddison Wesley Longman, 1997

S. LipschutzSchaum’s Outline of Essential Computer MathematicsMcGraw-Hill, 1th edition, 1982

Ch.F. Van LoanIntroduction to Scientific ComputingPrentice-Hall, Inc., 1997

C.B. MolerNumerical Computing with MatlabSIAM, 2004


Bibliografıa III

H.M. Mora EscobarIntroduccion a C y a metodos numericosUniversidad Nacional de Colombia (Sede Bogota), 2004

A. Quarteroni, F. SalieriCalculo cientıfico con MATLAB y OctaveSpringer-Verlag Italia, 2006

S.M. RossSimulationElsevier Inc., 2006

R. SeroulProgramming for MathematiciansSpringer, 2000

E. ScheinermanC++ for Mathematicians: An Introduction for Students andProfessionalsTaylor & Francis Group, LLC, 2006


Bibliografıa IV

A. ShenAlgorithms and ProgrammingSpringer Undergraduate Texts in Mathematics and Technology, 2010

P. TymannSchaum’s Outline of Principles of Computer ScienceMcGraw-Hill, 1th edition, 2008

introducci on a los computadores (cnm-130) algoritmos...

Documents