Post on 24-Feb-2016
description
transcript
TALLER DE INGENIERÍA INDUSTRIALClase 7: Algorítmica y programación
Ing. Felipe Torres
Maquinas de cálculo (mecánicas)
En 1642 Pascal crea una máquina mecánica capaz de sumar llamada la Pascalina. Usaba engranajes de ruedas dentadas. Realizaba operaciones de hasta 8 dígitos.
En 1670, Leibniz mejora la máquina inventada por Blaise Pascal, al agregarle capacidades de multiplicación, división y raíz cúbica. En 1679 crea y presenta el modo aritmético binario,
basado en 0 y 1 Charles Babbage diseñó la Máquina de Diferencias
(1821) aunque no la concluyó (era muy grande). Evaluaba polinomios
Maquinas de cálculo (mecánicas)
Posteriormente Charles Babbage diseñó la Máquina Analítica (1834) pero que Dispositivo de entrada de la información: tarjetas
metálicas perforadas en miles de combinaciones.
Unidad de almacenaje: tablero que contenía ejes y piñones que podían registrar dígitos.
Procesador: dispositivo con cientos de ejes verticales y miles de piñones.
Unidad de control: dispositivo en forma de barril con filamentos y ejes (como cuerdas de piano).
Dispositivo de salida: plantillas diseñadas para ser utilizadas en una prensa de imprenta.
Máquinas de cálculo (Electromecánicas)
En 1890 H. Hollerith consiguió realizar con su Máquina Censadora el censo de EE.UU. Usaba tarjetas perforadas para introducir
los datos. H. Hollerith fundó junto a T. Watson una
compañía para rentabilizar su máquina de la que saldría posteriormente la empresa IBM.
Máquina Censadora
Máquinas de cálculo (Electromecánicas)
En 1937 H. Aiken inició la construcción de la MARK I. Se completó en 1944. Las operaciones internas se realizaban con
relés y los contadores aritméticos eran mecánicos. Usaba cinta perforada para su programación.
Se usó durante la Segunda Guerra Mundial.
Se inspiró en las ideas de Babbage
MARK I
Máquinas de cálculo (Electrónicas)
La ENIAC (Electric Numeric Integrator And Calculator) fue construida entre 1943 y 1945 por J. Mauchly y J. P. Eckert. Fue la primera computadora electrónica de
propósito general totalmente operativa. Trabajaba en sistema decimal. Tenía grandes dimensiones
y utilizaba válvulas de vacío e interruptores.ENIAC
Máquinas de cálculo (Electrónicas)
En 1945, J. von Neumann, J. Mauchly y J. P. Eckert. constuyeron el EDVAC, otro ordenador de grandes dimensiones. La arquitectura de este ordenador costaba
de: Memoria principal Unidad de control Unidad aritmética Sistema de entrada y salida
Trabajaba en binarioV. Neumann y la EDVAC
Modelo de Von Newton
Todas las computadoras digitales se basan en ésta arquitectura, solo ha cambiado la tecnología utilizada para la construcción del hardware Bulbos » Transistores (1956) » Circuitos Integrados
(1964) » Microprocesadores (1974)
MEMORIA
UNIDAD DE ENTRADA
UNIDAD DE SALIDA
UNIDAD CENTRAL DE PROCESAMIENTO
Registros
Unidad de Control
Unidad Aritmética Lógica
Ej. Modelo Von Newton
RAM
Algoritmos “Secuencia finita de operaciones básicas
que permiten resolver un problema”. Características de un algoritmo
Preciso: Indicar el orden de realización de cada paso
Definido: Si se sigue un algoritmo dos veces, se debe obtener el mismo resultado cada vez.
Finito: Debe terminar el algún momento
Ejemplo de un algoritmosencillo Algoritmo para hacer una tasa de té
InicioTomar la teteraLlenarla de aguaEncender el fuegoMientras no hierva el agua
EsperarIntroducir una bolsa de té en la teteraVaciar el té en la taza
fin
Otros ejemplos de algoritmos• Las instrucciones o serie de pasos que sigues para
grabar un número telefónico en tu celular.• Las instrucciones que te dan para resolver un
examen.• Los pasos que sigues para prender el carbón para
una carne asada• El procedimiento que sigues para inscribirte • EL procedimiento para obtener tu pasaporte • La receta que sigues para preparar un pastel• Los pasos para invitar a alguien al cine
Algoritmos Ejemplo de algoritmo de multiplicación
por mediación y duplicación, método de Peasant Mediaciones Duplicaciones
18 24
9 48 (+)
4 96
2 192
1 384 (+)
• a=18 y b= 24• 24 18 = 48 9 = 48 (8+1) = 48 8 + 48
= 96 4 + 48 = 192 2 + 48 = 384 1 + 48
= 384 + 48 = 432
b) Ejemploa) Algoritmo en C
int mult (int a, int b) {
int resultado = 0;
while (a>1) {
if (a%2 != 0) {
resultado = resultado + b,
a=a-1;
] else {
b = b*2;
a = a/2;
]
}
resultado = resultado + b;
return resultado;
}
Complejidad Capacidad de procesamiento es un
recurso escaso Escoger siempre el algoritmo mas
eficiente. Complejidad del algoritmo:
Mayor numero de pasos posibles en cualquier instancia
Número esperado de pasos de acuerdo a una distribución de probabilidades
Complejidad Ej. Búsqueda de un arreglo de números
ordenados1 5 7 11 22 23 34 35 38 42 43 44
Búsqueda secuencial X=42Paso 1: ¿ 42 = 1 ? (no, siguiente)Paso 2: ¿ 42 = 5 ? (no, siguiente)Paso 3: ¿ 42 = 7 ? (no, siguiente)…Paso 9: ¿ 42 = 38 ? (no, siguiente)Paso 10: ¿ 42 = 42 ? (SI, encontrado!)
Comparaciones = 10
1 5 7 11 22 23 34 35 38 42 43 44
Búsqueda binaria X=42Paso 1: ¿ 42 >=< 23 ? (mayor, búsqueda binaria entre celdas C6 y C12)Paso 2: ¿ 42 >=< 38 ? (mayor, búsqueda binaria entre celdas C9 y C12) Paso 3: ¿ 42 >=< 43 ? (menor, búsqueda binaria entre celdas C9 y C11)Paso 4: ¿ 42 >=< 42 ? (igual, encontrado!)
Comparaciones = 4
CeldasC1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11C12
Complejidad, notación big-oh Notación big-oh es una medida
asintótica para medir el desempeño de los algoritmos Algoritmo corre en O(f(n)) si el tiempo
requerido para encontrar solución en el peor caso es “c x f(n)” donde c es el tiempo de ejecución de cada paso y n el numero de elementos.O(f(n)) NombreO(1) constanteO(log n) logarítmicaO(n) linealO(n log n) n log nO(nm) polinomialO(2n) ó O(n!) exponencial
Complejidad asintótica de los algoritmos
Ejemplo, Tiempo de ejecución de cada paso 10-9 seg, algoritmo que requiere n! pasos. f(n)=n! ; c= 10-9
Caso cuando n=10f(10)=3.6x106; se ejecuta en 3.6 ms
Caso cuando n=20f(20)=2.4x1018; se ejecuta en 77 años!
Complejidad, notación big-oh
Complejidad exponencial Los problemas con algoritmos de tiempo
exponencial no tienen solución práctica exacta Tiempo limitado Se utilizan algoritmos heurísticos eficientes
Ej. Problema del Agente Viajero: Encontrar la ruta mas corta para visitar exactamente una vez cada cuidad en una lista dada y regresar a la partida El único algoritmo exacto se basa en la enumeración
exhaustiva de todas las soluciones factibles, es decir un algoritmo de tiempo exponencial
Problema del Agente ViajeroHeurística de visita del vecino mas cercano
0459016095E
4505013585D
905008565C
16013585080B
958565800A
EDCBA
b) Matriz de distancias entre las ciudades
A
B
D
C
E
a) Topología (ciudades)
A
B
D
C
E
c) Primer paso
A
B
D
C
E
d) Segundo paso
Problema del Agente ViajeroHeurística de visita del vecino mas cercano (cont)
A
B
D
C
E
e) Tercer paso
A
B
D
C
E
f) Cuarto paso
A
B
D
C
E
g) Quinto paso
Problema del Agente ViajeroHeurística de inserción del vecino mas lejano
A
B
D
C
E
a) Topología (ciudades)
A
B
D
C
E
c) Segundo paso
A
B
D
C
E
b) Primer paso
d) Tercer paso
A
B
D
C
E
e) Cuarto paso
A
B
D
C
E
Se inicia seleccionando las dos ciudades mas alejadas entre si y formando un circuito con la ciudad cuya menor distancia a cualquiera de ellas es máxima.Luego se incorpora al circuito la cuidad cuya distancia mínima a cualquier otra ciudad del circuito sea máxima.
Problema del Agente ViajeroHeurística de visita del vecino mas cercano
Este algoritmo selección en cada paso la arista con menor longitud, que no construya un circuito y se detiene cuando se han incorporado todos los nodos al arbol.
A
B
D
C
E
b) Primer paso c) Segundo paso
A
B
D
C
E
d) Tercer paso
A
B
D
C
E
A
B
D
C
E
e) Cuarto paso
A
B
D
C
E
a) Topologíal (ciudades)
Programación Hardware, son los componentes físicos que
constituyen una computadora Software, son los programas que flexibilizan
y hacen accesible el uso de las computadoras Software de sistema (Ej. Windows)
Programas que se encargan delcontrol y administración de los recursos de cómputo
Software de aplicación (Ej. Excel) Permiten a la computadora realizar
actividades específicas deprocesamiento de la información
Programas vs Programación Programa: es la unión de una secuencia de
instrucciones que una computadora puede interpretar y ejecutar y una (o varias) estructuras de datos que almacena la información independiente de las instrucciones que dicha secuencia de instrucciones maneja.
Programación : Describir lo que debe hacer la computadora para resolver 1 problema concreto utilizando 1 determinado lenguaje de programación
Lenguajes de programación La clasificación de lenguajes de acuerdo a su generación
(1ra gen., 2da gen., etc.) tiene sentido ya que: Mientras más alta sea la generación, mayor es el nivel de
abstración y menor es la dependencia de la arquitectura de la máquina.
Un programa debería ser escrito más fácilmente en un lenguaje de mayor generación que en uno de menor generación.
Clasificación de los lenguajes: Primera – lenguaje de máquina Segunda – lenguaje de ensamblaje Tercera – lenguaje procedimentales (tales como Basic, Cobol o
C) y orientados a objetos (tales como C++ y Java) Cuarta – lenguajes funcionales y declarativos (tales como Lisp,
Prolog, SQL y VRML) Quinta – lenguajes naturales (tales como el Español o el Inglés)
Lenguajes de Programación
Lenguajes máquina
Son directamente
inteligibles por la
computadora (0 y 1)
Lenguajes de alto nivel
Sus instrucciones son muy fáciles de
recordar pero necesitan
traducirse a lenguaje máquina por medio de un
compilador o intérprete.
Lenguajes de bajo nivel
Sus instrucciones
son mas sencillas de
recordar, pero necesitan ser traducidas al
lenguaje máquina.Ensamblador C++
VisualBasicFortranPascal
Ejemplo de instrucciones: suma y resta
Lenguaje de alto nivel
Lenguaje de bajo nivel
(Ensamblador)
Lenguaje máquina
+ ADD 100101
_ SUB 010011
Lenguaje de máquina (Binario)c7 3c 2a 3c 2a 2b 2a 5c 3c 28 5c 2a 2b 2a 5c 3c 28 5c 2a 2b 2a 5c 3c 28 5c 2a 2b 2a 5c 3c 28 5c 2a 2b 2a 5c 3c 28 5c 2a 2b 2a 5c 3c 28 5c 2a 2b 2a 5c 3c 28 5c 2a 2b 2a 5c 3c 28 5c 2a 2b 2a 5c 3c 28 5c 2a 2b 2a 5c 3c 28 5c 2a 2b 2a 5c 3c 28 5c 2a 2b 2a 5c 3c 28 5c 2a 2b 2a 5c 3c 28 5c 2a 2b 2a 00 00 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 64 48 65 6c 6c 6f 2c 20 57 6f 72 6c 64 21 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Lenguajes de programación Ejemplos del programa “Hola Mundo”Lenguaje de alto nivel (C++)#include <stdio.h>main(); {printf("hola Mundo");}
Lenguaje ensamblador (Assembler)STACK SEGMENT STACK DW 64 DUP (?)STACK ENDS DATA SEGMENTSALUDO DB "Hola mundo!!",13,10,"$"DATA ENDS CODE SEGMENT ASSUME CS:CODE, DS:DATA, SS:STACK INICIO: MOV AX,DATA MOV DS,AX MOV DX,OFFSET SALUDO MOV AH,09H INT 21H MOV AH,4CH INT 21HCODE ENDS END INICIO
Fuente: http://www.roesler-ac.de/wolfram/hello.htm
Clasificación de acuerdo al paradigma de programación
Los paradigmas de programación son enfoques alternativos para construir programas.
Tradicionalmente, los paradigmas más importantes son los siguientes: Procedural Orientado a objetos Funcional Declarativo
Paradigma procedural Los programas consisten de rutinas que
contienen instrucciones que son ejecutadas mayormente en secuencia.
Las estructuras de control, tales como decisiones y ciclos, y las llamadas a subprogramas (rutinas) son usadas para alterar la secuencia.
Debido a esto último, la programación imperativa también se conoce como estructurada y también como procedimental.
Paradigma procedural (cont) El estado de un programa puede ser
determinado observando los valores de las variables.
El paradigma imperativo está muy arraigado al concepto de arquitectura Von Neumann. Esto es visto por muchos como un aspecto negativo que dificulta la programación.
Lenguajes como Basic, C, Cobol, Fortran y Pascal pertenecen a este paradigma.
Ejemplo PROCEDURALprocedimiento nombre_completo { imprimir $persona['nombre'] + $persona[’apellido']}Procedimiento es_mayor { si $persona['edad'] > 18
imprimir “es mayor de edad” sino
imprimir “es menor de edad”}
$persona['nombre'] = “Juan”;$persona['apellido'] = “Perez”;$persona['edad'] = “25”
nombre_completo;
es_mayor;
Paradigma orientado a objetos Los programas consisten de objetos que
interactúan entre sí por medio de mensajes. Los objetos consisten de datos y de
operaciones para manipular esos datos. Cada objeto pertenece a una clase y todos los
objetos de la misma clase tienen la misma estructura.
Es posible diseñar objetos que contengan otros objetos (composición) y objetos que se deriven de objetos previamente creados (herencia).
Paradigma orientado a objetos (cont)
La idea principal de la orientación a objetos es maximizar la reutilización de código y la abstracción.
La mayoría de los lenguajes modernos de programación son orientados a objetos.
Lenguajes como C++, C#, Java y Smalltalk pertenecen a este paradigma.
Algunos lenguajes imperativos tienen extensiones que permiten la programación orientada a objetos, tales como Pascal (Turbo Pascal, Delphi) y Basic (Visual Basic .Net).
Ejemplo OOPclass Persona { variable $nombre; variable $apellido; variable $edad; método Persona($nombre, $apellido, $edad) { $this->nombre = $nombre; $this->apellido = $apellido; $this->edad = $edad; } método nombre_completo() { retornar $this->nombre . ' ' . $this->apellido; } método es_mayor($persona) { retornar $this->edad >= 18; }}
$persona = new Persona('Juan', 'Perez', 25);echo $persona->nombre_completo();si ($persona->es_mayor) { imprimir " es mayor de edad.";} sino { imprimir " es menor de edad.";}
Paradigma funcional Los programas consisten de fuciones que
reciben como argumentos los resultados de otras funciones.
Las funciones en estos lenguajes pueden aceptar funciones como parámetros y también pueden devolver funciones como resultados. (Las funciones son valores de primera clase.)
En la mayoría de los lenguajes funcionales, las listas dinámicas son un tipo de datos provisto. Por lo tanto, el programador cuenta con operaciones prehechas para manejarlas.
Paradigma funcional (cont) En los lenguajes funcionales puros, no existe el
enunciado de asignación. Esto evita que las funciones puedan ocasionar efectos secundarios tales como modificar una variable global o devolver resultados por medio de parametros por referencia.
En cuanto a las estructuras de control, estos lenguajes proveen estructuras de decisión pero no de ciclos. Las repeticiones se hacen usando recursión.
Lisp es el lenguaje funcional por excelencia. Otros lenguajes en esta categoría son Scheme (un
dialecto de Lisp), Haskell y ML.
Ejemplo FUNCIONAL$p = inicializar('Juan', 'Perez', 25);echo nombre_completo($p);Si (es_mayor($p)) { imprimir " es mayor de edad.";} Sino{ imprimir " es menor de edad.";}
función inicializar($nombre, $apellido, $edad) { $persona['nombre'] = $nombre; $persona['apellido'] = $apellido; $persona['edad'] = $edad; return $persona;}función nombre_completo($persona) { retornar $persona['nombre'] . ' ' .$persona['apellido'];}función es_mayor($persona) { retornar $persona['edad'] >= 18;}
Paradigma declarativo Los programas consisten de declaraciones
donde se indican las carácterísticas del problema que se quiere resolver, pero no se indica el algoritmo para resilverlo.
El nivel de abstracción es bien alto ya que el algoritmo es determinado por el traductor.
Normalmente los lenguajes declarativos no son de propósito general.
Lenguajes como Prolog (bases de datos deductivas y manejos de listas), SQL (bases de datos relacionales) y VRML (graficas en 3D) son declarativos.
Paradigma lógico Los lenguajes lógicos son un tipo de
lenguajes declarativos. En estos lenguajes se utilizan hechos y
reglas que permiten deducir otros hechos y de esta manera resolver el problema deseado.
Prolog es el lenguaje lógico por excelencia y utiliza la lógica proposicional.
Ingeniería de Software Construcción de una casa para nuestro
perro “Fido”Puede hacerlo una sola personaRequiere:
Modelado mínimoProceso simpleHerramientas simples
Ingeniería de Software Construcción de una casa para una
familiaConstruida eficientemente y en un tiempo razonable por un equipoRequiere:
Modelado complejoProceso bien definidoHerramientas más sofisticadas
Ingeniería de Software Construcció
n de rascacielos
Universidad Nacional de Colombia
44
3004582 - I.S
¿ Qué es el la Ingeniería de Software?
Metodología seguida por una organización para el desarrollo del software
Esta metodología incluye todas las fases del ciclo de vida clásico
Este proceso se define de manera general para todas las aplicaciones de una organización
Igualmente se definen tareas especificas a cada aplicación en particular
Actividades a desarrollar
Análisis
Diseño
Programación
Pruebas
Mantenimiento
Pruebas de integración
Diseño modular
Codificación y pruebas de unidades
Universidad Nacional de Colombia
46
3004582 - I.S
Modelos del proceso del software Modelo lineal o cascada Modelo de construcción de prototipos Modelos evolutivos: incremental, espiral,
de desarrollo concurrente Otros
Universidad Nacional de Colombia
47
3004582 - I.S
Definición Análisis
Diseño Programación
Pruebas Mantenim.
Definición de requisitos:• Las restricciones y metas del sistema se definen a partir de la
interacción con el interesado.• Se comprende la naturaleza de la aplicación y el dominio de
información, así como su funcionalidad, rendimiento e interconexión • Se reúnen todos los requisitos que debe cumplir el software
Modelo lineal secuencial o en cascada
Universidad Nacional de Colombia
48
3004582 - I.S
Definición Análisis
Diseño Programación
Pruebas Mantenim.
Se concentra en cuatro características básicas:Estructura de datosArquitectura del softwareRepresentaciones de interfazDetalle procedimental (algoritmo)
Modelo lineal secuencial o en cascada
Universidad Nacional de Colombia
49
3004582 - I.S
Definición Análisis
Diseño Programación
Pruebas Mantenim.
• Se llama también Implementación o desarrollo• Generación de código entendible por la máquina• Actualmente se investiga mucho sobre la manera
de generar código automáticamente
Modelo lineal secuencial o en cascada
Universidad Nacional de Colombia
50
3004582 - I.S
Definición Análisis
Diseño Programación
Pruebas Mantenim.
• Proceso de depuración de programas• Chequear la validez de las sentencias• Pruebas para detectar errores, asegurando que a
partir de los datos de entrada si se genere la salida deseada
Modelo lineal secuencial o en cascada
Universidad Nacional de Colombia
51
3004582 - I.S
Definición Análisis
Diseño Programación
Pruebas Mantenim.
• Corrección de errores no detectados en la etapa de pruebas
• Posibles mejoras funcionales debidas a nuevos requerimientos del cliente
• En esta fase se vuelven a aplicar todas las etapas anteriores sobre el software existente
Modelo lineal secuencial o en cascada
Universidad Nacional de Colombia
523004582 - I.S
Comienza con una recolección inicial de requisitos para pasar a un diseño rápido y finalmente a la construcción de un prototipo de la solución.
Modelo de Construcción de Prototipos
Universidad Nacional de Colombia
53
3004582 - I.S
Aplica el enfoque lineal secuencial escalonadamente
Incrementos parciales de la herramienta completa (versiones)
Cada incremento agrega funcionalidad adicional o mejorada sobre el sistema
Cada etapa debe cumplir con los requisitos de las desarrolladas
Incremento 2
Incremento n ... ... ... ...
Análisis Diseño Código PruebasAnálisis Diseño Código Pruebas
Análisis Diseño Código Pruebas
Modelo Incremental
Universidad Nacional de Colombia
543004582 - I.S
Ventajas: Los clientes no tienen que esperar hasta que el sistema
se entregue completamente para comenzar a hacer uso de él.
Los clientes pueden usar los incrementos iniciales como prototipo para precisar los requerimientos posteriores del sistema.
Minimización del riesgo de falla en el proyecto porque los errores se van corrigiendo progresivamente.
Problemas: Adaptación de los requisitos del cliente para lograr
incrementos pequeños (no mas de 20.000 líneas de código) que añadan funcionalidad al sistema.
Nota: Una evolución de este enfoque se conoce como Programación Extrema (XP-Extreme Programming).
Modelo Incremental
Universidad Nacional de Colombia
553004582 - I.S
Utilización de ciclos en lugar de sucesión de actividades.
Facilita el desarrollo rápido de versiones incrementales de software.
Modelo Espiral