Algoritmos Generalidades de Ing. Software El lenguajes Fortran

´ n para Fundamentos de Programacio Ingenier´ıa: ˜o y Algoritmos Disen Luis E. Sierra1 Universidad Industrial de Santander Escuela Ingenier´ıa de Petr´ oleos

Bucaramanga 30 Abr 2008

1

MSc. [email protected] Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Introducci´on

Los ordenadores se utilizan hoy d´ıa en innumerables ´areas cient´ıficas para resolver problemas, aunque desgraciadamente, son incapaces de resolver el problema por s´ı mismos. Es necesario que una persona (el programador) sea capaz de analizar el problema a resolver y dise˜ ne un programa.

Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

Algoritmo t´ermino empleado por el matem´atico persa al-Jwarizmi del siglo IX, Hopcroft y Ullman (1969) basan la descripci´ on de algoritmo en la de procedimiento; definen un procedimiento como: ”una secuencia finita de instrucciones que pueden realizarse mec´anicamente . Un procedimiento que siempre termina es un algoritmo” Algoritmo es una secuencia ordenada de pasos que conduce a la soluci´on de un problema concreto, sin ambiguedad alguna, en un tiempo finito. Los algoritmos son independientes tanto del lenguaje de programaci´on en que se expresan como del ordenador que los ejecuta.

Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

Caracter´ısticas de un algoritmo

1

Car´ acter finito. ”Un algoritmo siempre debe terminar despu´es de un n´ umero finito de pasos”

2

Precisi´ on. ”Cada paso de un algoritmo debe estar precisamente definido; las operaciones a llevar a cabo deben ser especificadas de manera rigurosa y no ambigua para cada caso” Entrada. ”Un algoritmo tiene cero o m´as entradas”

3 4

5

Salida. ”Un algoritmo tiene una o m´as salidas: cantidades que tienen una relaci´ on espec´ıfica con las entradas” Eficacia. ”en el sentido de que todas las operaciones a realizar en un algoritmo deben ser suficientemente b´asicas como para que en principio puedan ser hechas de manera exacta y en un tiempo finito por un hombre usando l´apiz y papel”

Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

Resoluci´on de un problema

La resoluci´on de problemas es el motivo de la programaci´on. Para programar cualquier tarea antes hay que encontrar el camino y dar los pasos para resolverla. ”Un gran descubrimiento resuelve un gran problema, pero hay en toda soluci´on a cualquier problema un grano de descubrimiento. Nuestro problema puede ser modesto, pero si es un reto a nuestra curiosidad y pone en juego nuestras facultades inventivas y, si lo resolvemos por nuestros propios medios, podremos experimentar la tensi´on y el disfrute del triunfo de un gran descubrimiento.” G Polya

Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

Fases de resoluci´ on

Compresi´on del problema Encontrar las conexiones Llevar a cabo el plan Examinar la soluci´ on obtenida

Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

Fases de resoluci´on a. Comprensi´ on del problema

Cu´ales son las incognitas? Cu´ales son los datos? Cu´ales las condiciones? Es posible satisfacer las condicones? Son suficientes las condiciones para satisfacer las inc´ognitas? o insuficientes? o redundantes? o contradictorias?

Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

Fases de resoluci´on b. Encontrar conexiones

Tienes que encontrar la conexi´ on entre datos e inc´ognitas. Si no encontramos una conexi´ on inmediata, no tendremos m´s remedio que considerar problemas auxiliares . Lo hemos visto antes? Quiz´as lo hayamos visto pero en una forma ligeramente distinta? Conoces alg´ un problema relacionado con este? Conoces alg´ un teorema que nos pueda ser util? Podr´ıa replantear el problema? Podr´ıa replantear el problema? Podr´ıamos a´ un replantearlo de una manera incluso diferente? Replantear los principios Has utilizado todos los datos? Has utilizado todas las condiciones? Has tenido en cuenta todas las nociones esenciales involucradas en el problema? Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

Fases de resoluci´on c. Llevar a cabo el plan

Al realizar nuestro plan debemos comprobar cada paso. Puedes comprobar con claridad que el paso es correcto? Puedes demostrar que es correcto?

Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

Fases de resoluci´on d. Examinar la soluci´ on obtenida

Puedes comprobar la soluci´ on obtenida? Puedes comprobar los argumentos empleados? Puedes derivar el resultado de otra forma? Puedes verlo de una ojeada? Podr´ıa utilizar el resultado, o el m´etodo para alg´ un otro problema?

Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

Estrategias en la soluci´on de problemas la soluciones a problemas m´as complejos pueden requerir muchos m´as pasos. Las estrategias seguidas usualmente a la hora de encontrar algoritmos para problemas complejos son: Partici´ on o divide y vencer´ as: consiste en dividir un problema grande en unidades m´as peque˜ nas que puedan ser resueltas individualmente. Ejemplo: Podemos dividir el problema de limpiar una casa en labores m´as simples correspondientes a limpiar cada habitaci´on. Resoluci´ on por analog´ıa: Dado un problema, se trata de recordar alg´ un problema similar que ya est´e resuelto. Los dos problemas an´alogos pueden incluso pertenecer a ´areas de conocimiento totalmente distintas. Ejemplo: El c´alculo de la media de las temperaturas del departamento de santander y las media de las notas de los alumnos de una clase se realiza del mismo modo. Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

Verificaci´on del Algoritmo

consiste b´asicamente en recorrer todos los caminos posibles del algoritmo comprobando en cada caso que se obtienen los resultados esperados. Se realiza una ejecuci´ on manual del algoritmo con datos significativos que abarquen todo el posible rango de valores y comprobaremos que la salida coincide con la esperada en cada caso.

Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

lenguaje natural puede ser ambiguo e impreciso Se necesita disponer de un lenguaje algor´ıtmico

Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

Diagrama de flujo es una herramienta gr´afica para descripci´ on de algoritmos Un diagrama de flujo muestra la l´ogica del algoritmo, acentuando los pasos individuales y sus interconexiones. Un diagrama de flujo debe reflejar : El comienzo del programa Las operaciones que el programa realiza El orden en que se realizan El final del programa Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

Diagrama de Flujo: Simbolos2

a. Indican el inicio y el fin del algoritmo. Del primero s´ olo puede salir una l´ınea y al segundo s´ olo puede llegar una l´ınea. b. Indica una acci´ on a realizar. Tiene una u ´nica l´ınea de entrada y otra de salida. c. Indica una acci´ on de entrada (lectura de datos desde el teclado) o salida (escritura de un dato por pantalla). Tiene una u ´nica l´ınea de entrada y otra de salida. d. Se usan para tomar una decisi´ on, dependiendo de cierta condici´ on. Tiene una l´ınea de entrada y dos de salidas (una por la cual salir, si la condici´ on es cierta, y otra, si es falsa). e. Se usan para conectar los s´ımbolos anteriores y especifican el flujo del algoritmo. f. Se usan para conectar distintos puntos de los diagramas de flujo, evitando cruces de flechas.

2 han sido normalizados por las organizaciones ANSI (American National Standard Institute) y por ISO (International Sta Organization) Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Luis E. Sierra

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

Estructuras comunes

Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

Diagrama de flujo: algunas reglas

El comienzo del programa figurar´a en la parte superior del diagrama. Los s´ımbolos de comienzo y fin deber´an aparecer una u ´nica vez. El flujo de las operaciones ser´a de arriba a abajo y de izquierda a derecha. Se debe guardar cierta simetr´ıa en la representaci´on de bifurcaciones y bucles. Se evitar´an los cruces de l´ıneas de flujo, utilizando conectores.

Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

Ventajas de los diagramas de flujo

Favorecen la comprensi´ on del proceso a trav´es de mostrarlo como un dibujo. El cerebro humano reconoce f´acilmente los dibujos. Un buen diagrama de flujo reemplaza varias p´aginas de texto. Permiten identificar los problemas y las oportunidades de mejora del proceso. Se identifican los pasos redundantes, los flujos de los reprocesos , los conflictos de autoridad, las responsabilidades, los cuellos de botella, y los puntos de decisi´ on. Muestran las interfases cliente-proveedor y las transacciones que en ellas se realizan, facilitando a los empleados el an´alisis de las mismas. Son una excelente herramienta para capacitar a los nuevos empleados y tambi´en a los que desarrollan la tarea, cuando se realizan mejoras en el proceso

Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

Pasos para un diagrama de flujo 1

Establecer el alcance del proceso a describir. De esta manera quedar´a fijado el comienzo y el final del diagrama. Frecuentemente el comienzo es la salida del proceso previo y el final la entrada al proceso siguiente.

2

Identificar y listar las principales actividades/subprocesos que est´an incluidos en el proceso a describir y su orden cronol´ogico.

3

Si el nivel de destalle definido incluye actividades menores, listarlas tambi´en. Identificar y listar los puntos de decisi´ on.

4 5

6

Construir el diagrama respetando la secuencia cronol´ogica y asignando los correspondientes s´ımbolos. Asignar un t´ıtulo al diagrama y verificar que est´e completo y describa con exactitud el proceso elegido.

Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

Diagrama de flujo: ejemplos Qu´e hace?, esta bien planteado?

Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

Serie de Fibonacci

Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

Ejercicios

1

Sumar n n´ umeros pedidos por teclado

2

Dados los coeficientes de una Ecuaci´ on de 2do Grado, calcular y mostrar x1 y x2.

3

Dados 5 n´ umeros, ordenarlos de menor a mayor. (t´ecnicas de ordenamiento)

Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

Pseudoc´odigo

Es un lenguaje algor´ıtmico que permite representar las construcciones b´asicas de los lenguajes de programaci´on, pero a su vez, manteni´endose pr´ oximo al lenguaje natural.

Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

Principales ventajas pseudoc´ odigos

1

Podemos centrarnos sobre la l´ ogica del problema olvid´andonos de la sintaxis de un lenguaje concreto.

2

Es f´acil modificar el algoritmo descrito.

3

Es f´acil traducir directamente a cualquier lenguaje de programaci´on el algoritmo obtenido.

Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

Definic´on de estructuras de control Cada autor usa su propio pseudoc´ odigo con sus respectivas convenciones. Por ejemplo, considere la instrucci´ on ”Reemplace el valor de la variable x por el valor de la variable y”; algunas de las posibles ˜ ser: sintaxis para indicar lo anterior podrAan x←y x:=y x=y

Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

Pseudoc´odigo Estructuras de control:

Selectiva Si P entonces instruccion 1 instruccion 2 Fin Si

Secuencial Instrucion 1 Instrucion 2 . . . . Instrucion n

Selectiva doble (alternativa) Si P entonces Instruccion 1 Si No Instruccion 2 Fin Si Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

Pseudoc´odigo Estructuras de control:

Selectiva multiple-casos

Selectiva m´ ultiple

seleccionar Indicador

Si Condicion1 entonces

caso Valor1:

Instrucciones 1 Si No Si [Condicion2] entonces

Instrucciones1 caso Valor2:

Instrucciones 2 . Si No Si Condicion entonces

Instrucciones2 caso Valorn-1:

Instrucciones n-1

Instruccionesn-1

Si No

[ en otro caso:

Instrucciones n

Instruccionesn]

Fin Si

Fin seleccionar Indicador

Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

Pseudoc´odigo Estructuras de control:

Iterativa

Ciclo para

mientras P hacer Instrucciones fin mientras

para i=x hasta n hacer instrucciones fin para equivalente a:

-------hacer instrucciones mientras P

Luis E. Sierra

i=x mientras iLi+1 entonces intercambiar(Li, Li+1) intercambio=verdadero fin si fin para mientras intercambio=verdadero fin procedimiento Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

Pseudoc´odigo Estructuras de control:

Funciones funci´ on potencia (a,n) c Este algoritmo sirve para calcular a^n c cuando a y n son n´ umeros naturales i=n; r=1 ; x=a mientras i > 0 hacer si i es impar entonces r=r*x fin si x=x*x i=i/2 Fin mientras devolver r fin funci´ on Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

Ejemplo

ALGORITMO SumaN´ umeros c Lee por teclado

Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

Ejemplo

Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

Concepto Su funci´ on en la soluci´ on de problemas Representaci´ on de Algoritmos

Ejercicios

´ Realizar el pseudocdigo para los ejemplos y ejercicios planteados en diagrama de flujo

Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos

Algoritmos Generalidades de Ing. Software El lenguajes Fortran

” No se nos otorgar´a la libertad externa m´as que en la medida exacta en que hayamos sabido, en un momento determinado, desarrollar nuestra libertad interna” Mahatma Gandh

Creado con LaTex/Beamer

Luis E. Sierra

Fund. Progr. para Ing. : Dise˜ no y algoritmos