• Problemas, algoritmos y programas
• Paradigmas y Lenguajes de programación
• Desarrollo sistemático de aplicaciones
• Un modelo de computador
MSc Jaime Soto
Universidad Rafael Urdaneta
Escuela de Ingeniería de Computación
¿En qué consiste la programación?
Es la planificación, proyección o ejecución de una
tarea o proceso
Para nosotros, describir lo que debe hacer la
computadora para resolver un problema concreto
utilizando un lenguaje de programación
¿Qué es un programa?
Secuencia de instrucciones que indica las acciones
que han de ser ejecutadas por una computadora
Fases para la resolución de problemas con una computadora:
1. Análisis: comprender y definir el problema
2. Desarrollo de la solución (algoritmo): secuencia lógica de pasos
para resolver el problema
3. Trascripción de la solución: a un lenguaje de programación
4. Prueba: seguir los pasos para verificar que la solución resuelve
verdaderamente el problema
.
¿Qué es un problema?
Planteamiento de una situación cuya respuesta desconocida
debe obtenerse a través de métodos científicos
Tipos de problemas:
Sin solución
Determinado: Con una solución, o más de una en número
fijo.
Indeterminado: Con indefinido número de soluciones.
.
Establecimiento del problema
Análisis: Consiste en conocer de manera exacta y
precisa en qué consiste el problema
Especificación: descripción precisa del problema
Datos de partida
Resultado
.
lenguaje natural
lenguajes formales
puede resultar impreciso
lógica, matemáticas
Descripción:
Ejemplo
Problema: División euclídea
Especificación:
Datos
2 enteros, dividendo y divisor (D,d)
d no nulo
Resultado
2 enteros, cociente y resto (C,R)
0 R < d, tal que D = d * C + R
Etimología
Alhuarizmí: sobrenombre del árabe Muhamed ibn Musa (al-
Jwarizmi), matemático persa
Definición de Algoritmo
(I) Procedimiento paso a paso para resolver un problema en una
cantidad finita de tiempo
(II) Una secuencia de instrucciones paso a paso para realizar
alguna tarea (normalmente un cálculo)
.
Características de los algoritmos
Precisión:
Orden de cada paso
Operación que se realiza en cada paso
Definición o determinismo:
El algoritmo responderá de la misma forma en las mismas
condiciones
Finitud
En el número de pasos
En el tiempo de ejecución
.
Características de los algoritmos
La definición de un algoritmo debe describir tres
partes:
Entrada: datos necesarios
Proceso: instrucciones
Salida: resultados
.
Entrada SalidaProceso
Ejemplo: Suma
baccba
NNN
,
Lenguajes algorítmicos
Sirven para describir algoritmos
Son más precisos que el lenguaje natural pero menos rígidos
que un lenguaje de programación
Son un paso intermedio en la descripción de algoritmos
Ejemplos: pseudocódigo, diagramas de flujo
.
Ejemplo de algoritmo en pseudocódigo: Suma lenta
Suma lenta: consiste en ir pasando de a a b una unidad cada vez, de forma que cuando a=0, el resultado será el valor de b
.
1. Sean a, b N
2. Leer a y b b b+1
3. Mientras a 0 hacer
4. Escribir b a a-1
Definición formal de algoritmo
Es una cuádrupla que contiene los siguientes
elementos:
Conjunto de los estados que se pueden presentar
en cada momento
Identificación de estados iniciales
Identificación de estados finales
Función de transición entre estados
.
Un estado está definido por cuatro elementos:
Marca de la posición del algoritmo en la que se
define el estado
Valores de las variables que entran en juego
Datos de entrada
Resultados emitidos
.
Ejemplo: Estados de cómputo del algoritmo suma-
lentaPosición Entrada Salida Valores de los datos
a b
1 [2 3 ] [] 2 3
2 [] [] 2 3
3 [] [] 1 3
4 [] [] 1 4
5 [] [] 0 4
6 [] [] 0 5
7 [] [5] 0 5
Aspectos de un algoritmo:
Necesarios:
Corrección: respecto a las especificaciones.
Complejidad: recursos que un algoritmo necesita
Deseables:
Generalidad: es deseable que sirva para una clase
de problemas lo más amplia posible
Eficiencia: será más eficiente cuanto menos pasos
necesite
Dado un determinado problema, pueden
existir varios algoritmos que lo resuelvan
Ejemplo: suma de dos números enteros
No todos los problemas tienen solución
algorítmica
Ejemplo: problema de parada (consistente en
encontrar un algoritmo que determine si otro
algoritmo finaliza o no con unos determinados
datos de entrada)
¿Qué es un programa?
Conjunto de instrucciones precisas escritas en
un lenguaje entendible por una computadora
¿Qué es la programación?
Es el proceso de construcción de programas.
En general consta de las siguientes fases:
Análisis del problema
Solución conceptual del problema
Escritura del algoritmo a un lenguaje de programación
Comprobación de resultados
Ejemplo: Suma-lenta en PascalPROGRAM SumaLenta (input,output);
{Se suman dos enteros positivos,
pasando unidades de uno a otro}
VAR
a,b:integer;
BEGIN
Readln(a,b);
WHILE a <> 0 DO BEGIN
a:=a-1;
b:=b+1
END; {while}
Writeln(b)
END. {SumaLenta}
Definición de lenguaje de
programación:
Lenguaje artificial, diseñado para representar
algoritmos de forma inteligible por el
computador
Los lenguajes de programación son más
rigurosos que el lenguaje natural y además
tienen una sintaxis y semántica más sencilla
Las características más relevantes son:
Sintaxis
Semántica
Traducción y ejecución
Errores y cómo subsanarlos
Especifica inequívocamente la forma de construir los programas en un determinado LP
La especificación de la sintaxis se realiza mediante: Gramáticas BNF
Diagramas sintácticos
Número entero
+
-
Entero sin signo
• Asigna un significado a cada tipo de construcción
de un LP
• Formas de especificación:
– Definiciones formales
– Ejemplos en los manuales
Write(‘hola’);
Write(‘hola’);
Produce en pantalla:holahola
Y no:hola
hola
El lenguaje de programación debe traducirse al
lenguaje de la máquina
Las formas de traducción son:
Compilación:
Todo el código fuente (en un archivo) se traduce al
código ejecutable (y se guarda en otro archivo)
El archivo ejecutable queda listo para su ejecución
Programa Fuente
Programa Objeto
Compilación
Código fuente Código ejecutable
Interpretación:
Se traduce una instrucción de código fuente
Se ejecuta dicha instrucción
Se repiten estos dos pasos con todas las instrucciones del
código fuente
Errores de compilación Surgen durante la traducción (compilación) del código
fuente
Son errores sintácticos, de tipo, etc
Errores de ejecución Surgen al ejecutar el código
Son operaciones ilegales (división por cero), de tipo lógico, etc
Los motores que impulsan el desarrollo de los
lenguajes de programación son:
Abstracción
Encapsulación
Modularidad
Jerarquía
Abstracción
Proceso mental por el que el ser humano extrae las
características esenciales de algo, e ignora los detalles
superfluos.
Encapsulación
Proceso por el que se ocultan los detalles de las
características de una abstracción
Modularización
Proceso de descomposición de un sistema en un
conjunto de elementos poco acoplados (independientes)
y cohesivos
Jerarquía
Proceso de estructuración por el que se organizan un
conjunto de elementos en diferentes niveles atendiendo
a unos criterios determinados
Leng. o código máquina
Leng. Ensamblador
Leng de alto nivel
Prog. Estructurada
Prog. Modular
Prog. Con TAD’s (Tipos Abstractos de Datos)
Prog. Orientada a Objetos
Tiempo
Se define como una colección de patrones
conceptuales que moldean la forma de
razonar sobre problemas, de formular
algoritmos y de estructurar programas
Paradigmas:
Programación imperativa
Programación funcional
Programación lógica
Basada en comandos que actualizan variables que están en almacenamiento
Permite cierto nivel de abstracción: variables, expresiones, instrucciones
Para programar:
declarar las variables necesarias
Diseñar una secuencia (algoritmo) adecuada de instrucciones (asignaciones)
Ejemplo: Mayor de dos números en Pascal.PROGRAM mayorDeDosNumeros;
VAR x,y, mayor;
BEGIN
Read (x,y);
if x > y then
mayor := x
else
mayor := y;
Write (mayor);
END.
• Tiene su base en el concepto de función matemática:f: dominio rango
• Para programar:
– Se construyen funciones sencillas
– Se construyen funciones más complejas a partir de las sencillas
– Se evalúan las funciones sobre los datos de entrada
Ejemplo: Mayor de tres números en funcional
• Definición de funciones max2 y max3:
max2(x,y) := if x > y then x else y
max3(x,y,z) := max2(max2(x,y),z)
NOTA: “:=“ en este caso significa “se define como”
• Tiene su base en cálculo de predicados de primer orden:
Para programar:– Se definen hechos (o predicados básicos)
– Se diseñan implicaciones para definir predicados complejos
– Se determina la veracidad de los predicados para individuos concretos
Ejemplo: Parentescosmadre(ana,luis)
padre(josé,ana)
abuelo(X,Z):-padre(X,Y),padre(Y,Z)
abuelo(X,Z):-padre(X,Y),madre(Y,Z)
Consultas:
?- abuelo(josé,luis).
SI
?- abuelo(josé,ana).
NO
?- abuelo(X,luis)
X=josé
Prog.
Imperativa
Prog.
Lógica(P.Declarativa)
Prog.
Funcional(P.Declarativa)
Prog. orientada a objetos
Prolog++
CLOS
Smalltalk
C++
Java Eiffel
Prog.Concurrente
Ada-95
Haskel
Dephi
LISP
Prolog
Pascal FC
C
PASCAL
Fortran
COBOL
Ada
Hope
Ciao-Prolog
Definición-1 (Bauer, 1969):
el establecimiento y uso de principios robustos
de la ingeniería a fin de obtener
económicamente software que sea fiable y que
funcione eficientemente sobre máquinas reales
Definición-2 (IEEE, 1993):
la aplicación de un enfoque sistemático,
disciplinado y cuantificable hacia desarrollo,
operación y mantenimiento de software
• Planificación
• Análisis
• Diseño
• Codificación
• Validación
• Mantenimiento
Evaluación del interés del proyecto
Valoración de los recursos técnicos y humanos
Predicción del coste económico y del tiempo de
ejecución
Resultado: aprobar o descartar el proyecto
Establecimiento de las funciones que debe cumplir la aplicación
Planificación del trabajo conjunto de los diferentes módulos
Elaboración de un sistema de pruebas para detección de errores
Resultado: especificaciones del funcionamiento general del
software
Diseño de los bloques
División en partes
Asignación de tareas a equipos de trabajo
Resultado: algoritmos escritos en lenguaje algorítmico
Escritura del algoritmo en un lenguaje de programación
Resultado: algoritmos escritos en lenguaje algorítmico
• Aplicación del sistema de pruebas a:
– los módulos
– las conexiones entre los módulos (prueba de integración)
– la aplicación completa (prueba de validación)
• Resultado: generación de la aplicación corregidos
todos los errores detectados
Redacción de la documentación actualizada para usuario y
programador
Inicio de la explotación de la aplicación
Detección y corrección de errores no detectados en las fases
anteriores
Resultado: explotación de la aplicación
Unidad Central de
Proceso (UCP o CPU)
Memoria Principal
Dispositivos
Periféricos
BUS
Dispositivo de
almacenamiento
Instrucciones
Datos de entrada
Datos de salida
Elementos:
Dirección
Información
Dispositivo de procesamiento
Operaciones de control
Operaciones artiméticas y lógicas
Elementos:
Unidad de control
Unidad Arimético - Lógica
• Dispositivos periféricos: Intercambio de información con el exterior
– De entrada: Teclado, ratón, scanner …
– De salida: Pantalla, impresora, …
– De estrada/salida: Disco duro, Pendrive, LAN, …
• BUS: comunicación de los elementos internos