Download Programa

TALLER DE INGENIERÍA
Ing. Felipe Torres
INDUSTRIAL
Clase 7: Algorítmica y programación
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 binario
V. Neumann y la EDVAC
Modelo de Von Newton
MEMORIA
UNIDAD CENTRAL DE
PROCESAMIENTO
UNIDAD DE
ENTRADA
Unidad de Control
UNIDAD DE
SALIDA
Registros
Unidad Aritmética Lógica

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)
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 algoritmo sencillo

Algoritmo para hacer una tasa de té
Inicio
Tomar la tetera
Llenarla de agua
Encender el fuego
Mientras no hierva el agua
Esperar
Introducir una bolsa de té en la tetera
Vaciar 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
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;
]
}
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
resultado = resultado + b;
return resultado;
}
a) Algoritmo en C
(+)
b) Ejemplo
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 ordenados
Celdas
C1
C2
C3
C4
C5 C6
C7
C8
C9 C10 C11 C12
1 5 7 11 22 23 34 35 38 42 43 44
1 5 7 11 22 23 34 35 38 42 43 44
Búsqueda secuencial X=42
Paso 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!)
Búsqueda binaria X=42
Paso 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 = 10
Comparaciones = 4
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))
O(1)
O(log n)
O(n)
O(n log n)
O(nm)
O(2n) ó O(n!)
Nombre
constante
logarítmica
lineal
n log n
polinomial
exponencial
Complejidad
asintótica de los
algoritmos
Complejidad, notación big-oh

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=10
f(10)=3.6x106; se ejecuta en 3.6 ms
Caso cuando n=20
f(20)=2.4x1018; se ejecuta en 77 años!
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 Viajero
Heurística de visita del vecino mas cercano
E
A
B
C
D
E
A
0
80
65
85
95
B
80
0
85
135
160
C
65
85
0
50
90
D
85
135
50
0
45
E
95
160
90
45
0
A
D
C
B
a) Topología (ciudades)
b) Matriz de distancias entre las ciudades
E
E
A
A
D
D
C
B
C
B
c) Primer paso
d) Segundo paso
Problema del Agente Viajero
Heurística de visita del vecino mas cercano (cont)
E
E
A
A
D
D
C
C
B
B
e) Tercer paso
f) Cuarto paso
E
A
D
C
B
g) Quinto paso
Problema del Agente Viajero
Heurística de inserción del vecino mas lejano
E
E
A
E
A
A
D
D
D
C
C
C
B
B
B
b) Primer paso
a) Topología (ciudades)
c) Segundo paso
E
E
A
A
D
D
C
C
B
B
d) Tercer paso
e) Cuarto paso
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 Viajero
Heurística de visita del vecino mas cercano
E
E
E
A
A
A
D
D
D
C
C
C
B
B
B
b) Primer paso
a) Topologíal (ciudades)
c) Segundo paso
E
E
A
A
D
D
C
C
B
B
d) Tercer paso
e) Cuarto paso
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.
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 del
control y administración de los
recursos de cómputo
 Software
 Permiten
de aplicación (Ej. Excel)
a la computadora realizar
actividades específicas de
procesamiento 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
Lenguajes
de bajo nivel
Son
directamente
inteligibles por
la computadora
(0 y 1)
Sus instrucciones
son mas sencillas
de recordar, pero
necesitan ser
traducidas al
lenguaje máquina.
Ensamblador
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.
C++
VisualBasic
Fortran
Pascal
Ejemplo de instrucciones: suma y resta
Lenguaje de alto
nivel
Lenguaje de
bajo nivel
(Ensamblador)
Lenguaje
máquina
+
ADD
100101
_
SUB
010011
Lenguajes de programación

Ejemplos del programa “Hola Mundo”
Lenguaje de alto nivel (C++)
#include <stdio.h>
main();
{
printf("hola Mundo");
}
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
Lenguaje ensamblador (Assembler)
STACK
SEGMENT STACK
DW 64 DUP (?)
STACK ENDS
DATA
SEGMENT
SALUDO
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 21H
CODE
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 PROCEDURAL
procedimiento nombre_completo {
$persona['nombre'] = “Juan”;
imprimir $persona['nombre'] +
$persona[’apellido']
$persona['apellido'] = “Perez”;
$persona['edad'] = “25”
}
Procedimiento es_mayor {
nombre_completo;
si $persona['edad'] > 18
imprimir “es mayor de edad”
sino
imprimir “es menor de edad”
}
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 OOP
class Persona {
variable $nombre;
variable $apellido;
variable $edad;
$persona = new Persona('Juan', 'Perez', 25);
echo $persona->nombre_completo();
si ($persona->es_mayor) {
imprimir " es mayor de edad.";
método Persona($nombre, $apellido, $edad) {
$this->nombre = $nombre;
} sino {
$this->apellido = $apellido;
$this->edad = $edad;
}
método nombre_completo() {
retornar $this->nombre . ' ' . $this->apellido;
}
método es_mayor($persona) {
retornar $this->edad >= 18;
}
}
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
función inicializar($nombre, $apellido, $edad) {
$p = inicializar('Juan', 'Perez', 25);
$persona['nombre'] = $nombre;
echo nombre_completo($p);
$persona['apellido'] = $apellido;
Si (es_mayor($p)) {
$persona['edad'] = $edad;
return $persona;
imprimir " es mayor de edad.";
} Sino{
}
imprimir " es menor de edad.";
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 persona
Requiere:
Modelado mínimo
Proceso simple
Herramientas simples
Ingeniería de Software

Construcción de una casa para una familia
Construida eficientemente y en un tiempo
razonable por un equipo
Requiere:
Modelado complejo
Proceso bien definido
Herramientas más sofisticadas
Ingeniería de Software

Construcción
de rascacielos
¿ Qué es el la Ingeniería de Software?
44




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
Universidad Nacional de Colombia
3004582 - I.S
Actividades a desarrollar
Diseño
modular
Análisis
Codificación y pruebas
de unidades
Diseño
Programación
Pruebas de
integración
Pruebas
Mantenimiento
Modelos del proceso del software
46




Modelo lineal o cascada
Modelo de construcción de prototipos
Modelos evolutivos: incremental, espiral, de
desarrollo concurrente
Otros
Universidad Nacional de Colombia
3004582 - I.S
Modelo lineal secuencial o en cascada
47
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
Universidad Nacional de Colombia
3004582 - I.S
Modelo lineal secuencial o en cascada
48
Definición
Análisis
Diseño
Programación
Pruebas
Mantenim.
Se concentra en cuatro características básicas:
Estructura de datos
Arquitectura del software
Representaciones de interfaz
Detalle procedimental (algoritmo)
Universidad Nacional de Colombia
3004582 - I.S
Modelo lineal secuencial o en cascada
49
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
Universidad Nacional de Colombia
3004582 - I.S
Modelo lineal secuencial o en cascada
50
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
Universidad Nacional de Colombia
3004582 - I.S
Modelo lineal secuencial o en cascada
51
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
Universidad Nacional de Colombia
3004582 - I.S
Modelo de Construcción de Prototipos
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.
3004582 - I.S
Universidad Nacional de Colombia
52
Modelo Incremental
53




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
Análisis
Diseño
Código
Pruebas
Incremento 2
Análisis
...
Diseño
...
Código
...
Pruebas
...
Incremento n
Análisis
Diseño
Código3004582 - Pruebas
Universidad
Nacional de Colombia
I.S
Modelo Incremental



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).
3004582 - I.S
Universidad Nacional de Colombia
54
Modelo Espiral


Utilización de ciclos en lugar de sucesión de actividades.
Facilita el desarrollo rápido de versiones incrementales de
software.
3004582 - I.S
Universidad Nacional de Colombia
55