Software - Algoritmos
-
Upload
mikkezavala -
Category
Documents
-
view
224 -
download
0
description
Transcript of Software - Algoritmos
Informatica I
Software - Algoritmo
Alejandro Furfaro
Marzo 2011
Introduccion Algoritmos Estcucturas de Programacion Programacion estructurada Conclusiones
Temario
1 Introduccion.
2 Algoritmo.
3 Estructuras de programacion.
4 Programacion estructurada
5 Conclusiones
Alejandro Furfaro
Software - Algoritmo
Introduccion Algoritmos Estcucturas de Programacion Programacion estructurada Conclusiones
Primeros conceptos
Protodefinicion
Cita Nº1“La solucion a cualquier problema de computo involucra unaserie de acciones ejecutadas en un orden especıfico” (Deitel)
Cita Nº2“Informalmente, un algoritmo es un procedimiento de calculobien definido que toma un cierto valor, o conjunto de valores,como entrada y produce un cierto valor, o conjunto de valores,como salida. Un algoritmo es, entonces, una secuencia depasos computacionales que transforman la entrada en unasalida.”(Cormen)
Alejandro Furfaro
Software - Algoritmo
Introduccion Algoritmos Estcucturas de Programacion Programacion estructurada Conclusiones
Primeros conceptos
Protodefinicion
Cita Nº1“La solucion a cualquier problema de computo involucra unaserie de acciones ejecutadas en un orden especıfico” (Deitel)
Cita Nº2“Informalmente, un algoritmo es un procedimiento de calculobien definido que toma un cierto valor, o conjunto de valores,como entrada y produce un cierto valor, o conjunto de valores,como salida. Un algoritmo es, entonces, una secuencia depasos computacionales que transforman la entrada en unasalida.”(Cormen)
Alejandro Furfaro
Software - Algoritmo
Introduccion Algoritmos Estcucturas de Programacion Programacion estructurada Conclusiones
Primeros conceptos
Protodefinicion
Cita Nº1“La solucion a cualquier problema de computo involucra unaserie de acciones ejecutadas en un orden especıfico” (Deitel)
Cita Nº2“Informalmente, un algoritmo es un procedimiento de calculobien definido que toma un cierto valor, o conjunto de valores,como entrada y produce un cierto valor, o conjunto de valores,como salida. Un algoritmo es, entonces, una secuencia depasos computacionales que transforman la entrada en unasalida.”(Cormen)
Alejandro Furfaro
Software - Algoritmo
Introduccion Algoritmos Estcucturas de Programacion Programacion estructurada Conclusiones
Primeros conceptos
Protodefinicion
Cita Nº1“La solucion a cualquier problema de computo involucra unaserie de acciones ejecutadas en un orden especıfico” (Deitel)
Cita Nº2“Informalmente, un algoritmo es un procedimiento de calculobien definido que toma un cierto valor, o conjunto de valores,como entrada y produce un cierto valor, o conjunto de valores,como salida. Un algoritmo es, entonces, una secuencia depasos computacionales que transforman la entrada en unasalida.”(Cormen)
Alejandro Furfaro
Software - Algoritmo
Introduccion Algoritmos Estcucturas de Programacion Programacion estructurada Conclusiones
Primeros conceptos
Protodefinicion
Cita Nº1“La solucion a cualquier problema de computo involucra unaserie de acciones ejecutadas en un orden especıfico” (Deitel)
Cita Nº2“Informalmente, un algoritmo es un procedimiento de calculobien definido que toma un cierto valor, o conjunto de valores,como entrada y produce un cierto valor, o conjunto de valores,como salida. Un algoritmo es, entonces, una secuencia depasos computacionales que transforman la entrada en unasalida.”(Cormen)
Alejandro Furfaro
Software - Algoritmo
Introduccion Algoritmos Estcucturas de Programacion Programacion estructurada Conclusiones
Primeros conceptos
Operaciones en un orden determinado
Para resolver un problema mediante un algortimo se debedeterminar
1 Acciones a ejecutar2 El orden en que las acciones se deben ejecutar
Alejandro Furfaro
Software - Algoritmo
Introduccion Algoritmos Estcucturas de Programacion Programacion estructurada Conclusiones
Escribiendo Algoritmos
¿Como escribo un algoritmo si no se aun nada deprogramacion?
Una forma es usando PseudocodigoO sea, usando un lenguaje artificial, informal, dirıamos...es casi como “escribir el algoritmo con nuestras palabras”Primer ejemplo... ¿Generan el mismo resultado?
Ir a la Facultad (Opcion 1)
Levantarme de la camaDarme una duchaVestirmeDesayunarCaminar hasta la parada del microTomar el micro indicado
Ir a la Facultad (Opcion 2)
Levantarme de la camaDarme una duchaDesayunarCaminar hasta la parada del microVestirmeTomar el micro indicado
Es bastante poco probable que con el algoritmo de la opcion 2 lleguemos a la Facultad
Alejandro Furfaro
Software - Algoritmo
Introduccion Algoritmos Estcucturas de Programacion Programacion estructurada Conclusiones
Escribiendo Algoritmos
¿Como escribo un algoritmo si no se aun nada deprogramacion?
Una forma es usando PseudocodigoO sea, usando un lenguaje artificial, informal, dirıamos...es casi como “escribir el algoritmo con nuestras palabras”Primer ejemplo... ¿Generan el mismo resultado?
Ir a la Facultad (Opcion 1)
Levantarme de la camaDarme una duchaVestirmeDesayunarCaminar hasta la parada del microTomar el micro indicado
Ir a la Facultad (Opcion 2)
Levantarme de la camaDarme una duchaDesayunarCaminar hasta la parada del microVestirmeTomar el micro indicado
Es bastante poco probable que con el algoritmo de la opcion 2 lleguemos a la Facultad
Alejandro Furfaro
Software - Algoritmo
Introduccion Algoritmos Estcucturas de Programacion Programacion estructurada Conclusiones
Escribiendo Algoritmos
¿Como escribo un algoritmo si no se aun nada deprogramacion?
Una forma es usando PseudocodigoO sea, usando un lenguaje artificial, informal, dirıamos...es casi como “escribir el algoritmo con nuestras palabras”Primer ejemplo... ¿Generan el mismo resultado?
Ir a la Facultad (Opcion 1)
Levantarme de la camaDarme una duchaVestirmeDesayunarCaminar hasta la parada del microTomar el micro indicado
Ir a la Facultad (Opcion 2)
Levantarme de la camaDarme una duchaDesayunarCaminar hasta la parada del microVestirmeTomar el micro indicado
Es bastante poco probable que con el algoritmo de la opcion 2 lleguemos a la Facultad
Alejandro Furfaro
Software - Algoritmo
Introduccion Algoritmos Estcucturas de Programacion Programacion estructurada Conclusiones
Escribiendo Algoritmos
¿Como escribo un algoritmo si no se aun nada deprogramacion?
Una forma es usando PseudocodigoO sea, usando un lenguaje artificial, informal, dirıamos...es casi como “escribir el algoritmo con nuestras palabras”Primer ejemplo... ¿Generan el mismo resultado?
Ir a la Facultad (Opcion 1)
Levantarme de la camaDarme una duchaVestirmeDesayunarCaminar hasta la parada del microTomar el micro indicado
Ir a la Facultad (Opcion 2)
Levantarme de la camaDarme una duchaDesayunarCaminar hasta la parada del microVestirmeTomar el micro indicado
Es bastante poco probable que con el algoritmo de la opcion 2 lleguemos a la Facultad
Alejandro Furfaro
Software - Algoritmo
Introduccion Algoritmos Estcucturas de Programacion Programacion estructurada Conclusiones
Formalizacion de un algoritmo
Erase una vez, 4 estrcuturas
1 Secuencia
2 Decision (o seleccion)
3 Iteracion
4 Salto Incondicional
Alejandro Furfaro
Software - Algoritmo
Introduccion Algoritmos Estcucturas de Programacion Programacion estructurada Conclusiones
Formalizacion de un algoritmo
Estructura de Secuencia
Se llaman de este modo ya que no son otra cosa queordenes que se ejecutan en secuencia respecto de laanterior.Se ejecutan una a continuacion de la otra en el orden enque estan escritas.El Algoritmo de ejemplo anterior no es otra cosa que unasucesion de estructuras de secuencia.
Alejandro Furfaro
Software - Algoritmo
Introduccion Algoritmos Estcucturas de Programacion Programacion estructurada Conclusiones
Formalizacion de un algoritmo
Estructura de Secuencia
Se llaman de este modo ya que no son otra cosa queordenes que se ejecutan en secuencia respecto de laanterior.Se ejecutan una a continuacion de la otra en el orden enque estan escritas.El Algoritmo de ejemplo anterior no es otra cosa que unasucesion de estructuras de secuencia.
Alejandro Furfaro
Software - Algoritmo
Introduccion Algoritmos Estcucturas de Programacion Programacion estructurada Conclusiones
Formalizacion de un algoritmo
Estructura de Decision
Permiten elegir entre diversos cursos de accion.Veamos nuevamente el algoritmo “Ir a trabajar”
Ir a trabajar:Levantarme de la camaDarme una DuchaVestirmeSi estoy a tiempo
DesayunarCaminar hasta la parada del microTomar el micro indicado
Alejandro Furfaro
Software - Algoritmo
Introduccion Algoritmos Estcucturas de Programacion Programacion estructurada Conclusiones
Formalizacion de un algoritmo
Estructura de Decision
La estructura de Decision evalua una condicion.En el caso anterior la condicion contesta la pregunta:“¿estoy a tiempo?”Si la evaluacion de la condicion es verdadera (es decir,tengo tiempo suficiente), entonces ejecuta el bloque deinstrucciones contenidas por la seleccion. En nuestro casoDesayunar.
Alejandro Furfaro
Software - Algoritmo
Introduccion Algoritmos Estcucturas de Programacion Programacion estructurada Conclusiones
Formalizacion de un algoritmo
Estructura de Decision
Una pequena mejora al algoritmo “Ir a trabajar”Levantarme de la camaDarme una DuchaVestirmeSi estoy a tiempo
DesayunarSino
Llevar dos manzanas para el caminoCaminar hasta la parada del microTomar el micro indicado
Alejandro Furfaro
Software - Algoritmo
Introduccion Algoritmos Estcucturas de Programacion Programacion estructurada Conclusiones
Formalizacion de un algoritmo
Estructura de Decision
Correspondencia con el lenguaje formalLevantarme de la camaDarme una DuchaVestirmeif (estoy a tiempo)
Desayunarelse
Llevar dos manzanas para el caminoCaminar hasta la parada del microTomar el micro indicado
Alejandro Furfaro
Software - Algoritmo
Introduccion Algoritmos Estcucturas de Programacion Programacion estructurada Conclusiones
Formalizacion de un algoritmo
Estructura de Iteracion
Tambien denominada repeticion.Indica que un bloque de acciones se repite mientras unacondicion evaluada resulte verdadera.Supongamos que en nuestro algoritmo deseamosaprovechar el tiempo si nos levantasemos mastemprano. . .
Alejandro Furfaro
Software - Algoritmo
Introduccion Algoritmos Estcucturas de Programacion Programacion estructurada Conclusiones
Formalizacion de un algoritmo
Algritmo con iteracion
Lee el diario “mientras” tenga tiempoLevantarme de la camaDarme una DuchaVestirmeDesayunarMientras quede tiempo
Leer el diarioCaminar hasta la parada del microTomar el micro indicado
Alejandro Furfaro
Software - Algoritmo
Introduccion Algoritmos Estcucturas de Programacion Programacion estructurada Conclusiones
Formalizacion de un algoritmo
Algritmo con iteracion
Correspondencia con el lenguaje formalLevantarme de la camaDarme una DuchaVestirmeDesayunarwhile (quede tiempo)
Leer el diarioCaminar hasta la parada del microTomar el micro indicado
Alejandro Furfaro
Software - Algoritmo
Introduccion Algoritmos Estcucturas de Programacion Programacion estructurada Conclusiones
Formalizacion de un algoritmo
Salto incondicional
Permite alterar el flujo de instrucciones de maneraarbitraria.Incondicional implica que no se evalua una condicion porverdadero o falso para alterar la secuencia de nuestroalgoritmo, sino que simplemente se la altera, sin mas.
Alejandro Furfaro
Software - Algoritmo
Introduccion Algoritmos Estcucturas de Programacion Programacion estructurada Conclusiones
Antecedentes
Inicios de la Industria del Software
En la decada del ’60 los requerimientos a las aplicacioneseran muy fuertes, y la “mala calidad” del codigo escritoimpedıa su evolucion y su mantenimiento.Se trata de una industria muy joven que no habıa aundesarrollado normas de calidad para la elaboracion decodigo que sea mas facilmente legible, escalable, ymantenible.Por entonces habıa un consenso unanime tanto enambitos cientıficos como profesionales que la estructurade Salto Incondicional era la responsable del problema.
Alejandro Furfaro
Software - Algoritmo
Introduccion Algoritmos Estcucturas de Programacion Programacion estructurada Conclusiones
Antecedentes
1er. Paradigma de Programacion
En 1965 Bohm y Jacopini, publicaron en ACM (Associationof Computer Machinery) un trabajo en el que demostraronpor metodo cientıfico que cualquier algoritmo puede serescrito utilizando las tres primeras estructuras deprogramacion (dicho de otro modo prescindiendo de laestructura de Salto Condicional).Estas conclusiones provocaron la aparicion del 1er.PARADIGMA de Programacion conocido comoProgramacion Estructurada.
Alejandro Furfaro
Software - Algoritmo
Introduccion Algoritmos Estcucturas de Programacion Programacion estructurada Conclusiones
Metodologıa de resolucion de Algoritmos
Aproximacion top-down
Supongamos un problema de compejidad media:
“Calcular el promedio de los valores de temperatura leıdosdesde un archivo”
Dividamos esta tarea en una serie de tareas maspequenas...
inicializar variablesIngresa los datos llevando la cuenta de los mismos.Calcula el promedio y presenta en pantalla el resultado
Alejandro Furfaro
Software - Algoritmo
Introduccion Algoritmos Estcucturas de Programacion Programacion estructurada Conclusiones
Metodologıa de resolucion de Algoritmos
Bajemos mas a detalle (top - down)
Inicializa contador en 0Inicializa total en 0Abre el arcivo e inicializa su descriptorMientras no alcance fin del archivo (EOF)
Lee siguiente valor de temperaturaSuma el valor a totalIncrementa en 1 contador
Si contador no es igual a 0Divide total por contadorImprime el resultado en pantalla
SinoImprime en pantalla “No hay valores de temperatura
almacenados”
Alejandro Furfaro
Software - Algoritmo
Introduccion Algoritmos Estcucturas de Programacion Programacion estructurada Conclusiones
Metodologıa de resolucion de Algoritmos
Bajemos mas a detalle (top - down)
Inicializa contador en 0Inicializa total en 0Abre el arcivo e inicializa su descriptorMientras no alcance fin del archivo (EOF)
Lee siguiente valor de temperaturaSuma el valor a totalIncrementa en 1 contador
Si contador no es igual a 0Divide total por contadorImprime el resultado en pantalla
SinoImprime en pantalla “No hay valores de temperatura
almacenados”
Alejandro Furfaro
Software - Algoritmo
Introduccion Algoritmos Estcucturas de Programacion Programacion estructurada Conclusiones
Metodologıa de resolucion de Algoritmos
Bajemos mas a detalle (top - down)
Inicializa contador en 0Inicializa total en 0Abre el arcivo e inicializa su descriptorMientras no alcance fin del archivo (EOF)
Lee siguiente valor de temperaturaSuma el valor a totalIncrementa en 1 contador
Si contador no es igual a 0Divide total por contadorImprime el resultado en pantalla
SinoImprime en pantalla “No hay valores de temperatura
almacenados”
Alejandro Furfaro
Software - Algoritmo
Introduccion Algoritmos Estcucturas de Programacion Programacion estructurada Conclusiones
¿Que aprendimos?
Concepto de algoritmo como resultado de una ejecucionde paos en un orden determinadoEstructuras de programacion como la forma deimplementar un algoritmoConcepto de programacion estructurada como la forma dearganizar un programa dividiendolo en tareas, aplicando eldesarrollo top - downVimos que con pseudo codigo logramos explicitar nuestroalgoritmo y dejarlo listo para escribirlo en el lenguaje deprogramacion que mas preferamos.
Alejandro Furfaro
Software - Algoritmo