Copyright © 2005 Pedro Álvarez , José Ángel Bañares, Pedro Latorre, Santiago Velilla

Tema 1. Conceptos Básicos de Programación

Departamento de Informática e Ingeniería de Sistemas C.P.S. Universidad de Zaragoza Última revisión: Septiembre, 2006

Conceptos Básicos de Programación

Problemas y soluciones Objetivos de la programación Noción de algoritmo El computador (hardware) Cuestiones generales sobre el Software Estilo de programación Lenguajes de Programación Elementos de un programa

Propiedades de los algoritmos Ciclo de vida de los programas Entorno de Programación

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

2

Problemas y soluciones

¿Cómo se resuelve un problema en general?

Datos

Resultados

Modelado o representación Datos (iniciales, intermedios, resultados) + algoritmos Visualización del modelo de resultados

Implementación en la plataforma de trabajo (codificación: Pascal, Java, C…)

Ejecución de los procesos

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

3

Objetivo de la programación.

• Problemas que se tratan de resolver en Programación • Cómputo o cálculo • Gestión comercial • Control • Tratamiento de la señal • Lúdicos • Inteligencia Artificial • E-bussines • Etc. • Problemas cuya solución puede ser llevada a cabo por un COMPUTADOR Computador: Herramienta que permite tratar de forma automática problemas de tratamiento de la información. Informática: Ciencia del tratamiento de la información.

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

4

Objetivo de la programación: - Construir programas

• Programa: texto formado por instrucciones para que una máquina las ejecute Los lenguajes de programación están diseñados de forma que sólo se requiere que los programadores establezcan sus intenciones explícitamente

• ¿Cómo transformar un problema en un programa ejecutable por un computador? Entre problema y programa hay algunos pasos importantes:

Análisis / Diseño

Problema Lenguaje Natural

Codificación

Algoritmo Lenguaje Algorítmico / pseudocódigo

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

Programa PASCAL, C, Ada, Basic, Fortran, COBOL, Java, C++, Lisp, ...

09/09/2004

5

Noción de algoritmo

• Acción: Es un acontecimiento producido por un actor (o ejecutante de una acción) que tiene lugar durante un periodo de tiempo finito y que tiene como consecuencia o resultado una nueva situación bien definida y previsible. • Estado: Es el conjunto de objetos (con sus circunstancias) disponibles en un instante determinado. • Algoritmo: Es la descripción de una sucesión finita de acciones que permite transformar el entorno del estado inicial dado en el final deseado.

Iremos calculando factorial de n = 1* 2 * ...*i * ... n para valores crecientes de i hasta n

Algoritmo en lenguaje algorítmico

Solución informal en lenguaje natural

Read(n);i:=1; factorial:=1; Mientras Que i < n hacer i:= i+1; factorial:= factorial * i FinMientrasQue;

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

6

Noción de Programa

• Programa: Es un algoritmo escrito en términos que pueda interpretar (ejecutar) un computador. A él se llega tras codificar el algoritmo en algún lenguaje de programación. i:=1;

lenguaje algorítmico

factorial:=1; Mientras Que i < n hacer i:= i+1; factorial:= factorial * i FinMientrasQue;

i:=1; factorial:=1; While i < n do begin

Pascal

i:= i+1; factorial:= factorial * i end; i=1; factorial=1;

C

While (i < n) factorial*=++i;

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

7

Cuestiones generales sobre el software

En los últimos años • El avance espectacular del hardware no ha ido acompañado por el software en cuanto a calidad y coste • Aumento de la demanda del software: cantidad, prestaciones, calidad • La capacidad de mantenimiento está amenazada por el mal diseño y el uso inadecuado de recursos • La parte principal del coste de una solución informática es el software • El efecto 2000. • ¿cómo pudo difundirse ese miedo? • Por falta de credibilidad Hacia una solución • Construcción sistemática frente a improvisada • Construcción usando componentes: reusabilidad, librerías • Uso de herramientas de alto nivel: que construyen programas.

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

8

Ciclo de vida de un programa

Especificación Análisis Diseño Codificación Pruebas Mantenimiento

Mantenimiento: En general el software sufrirá cambios: • Errores detectados • Aparición de nuevos requisitos: • Externos: periféricos, sistema operativo • Nuevas prestaciones

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

9

El computador (Hardware)

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

10

El computador (Hardware)

Periféricos

CPU (Central Process Unit)

Memoria

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

11

Memoria de un computador

Memoria • Se realiza mediante millones de transistores que se utilizan a modo de “interruptores” que pueden estar encendidos o apagados

Cada transistor contiene un bit de información

1

0

De teoría del lenguaje: La unidad mínima de información es el bit.

•

8 bits = 1 byte Podemos representar 256 valores del 0 al 255 en binario Base 10 Base 2 2562 = 2 * 10^3 1101= 1 * 2^3= 8 5 * 10^2 1 * 2^2= 4 6 * 10^1 0 * 2^1= 0 2 * 10^0 1 * 2^0= 1 13

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

12

Memoria

• Podemos representar en memoria información numérica y no numérica: 1101= 13 (Número 13)

Utilizar una codificación para los caracteres (ASCII) El 65 representa la a El 66 representa la b .... Agrupando caracteres representamos palabras ...

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

13

Dirección de memoria

Como almacenar y encontrar la información • En direcciones de memoria ia r o em .. em

sd e n io 3 4 c c

. . . . ..

re 2 i D 1

1

Palabra*

*Palabra del computador = Número de bytes del mínimo bloque direccionable

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

14

Memoria Principal/Memoria Secundaria

Tipos de memoria • Memoria Principal • RAM (Read Access Memory) • ROM (Read Only Memory)

• Memoria Secundaria • Acceso secuencial • Acceso directo

• La memoria secundaria solo se debe utilizar para almacenar datos: Vel. mem. primaria >>>> Vel. mem.secundaria

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

15

Cargando un programa en memoria

1. Inicializas el programa

2. La cabeza lectura/escritura del disco duro busca el programa

3. Se copia el programa en memoria(RAM)

4. Se ejecuta el programa (La CPU ejecuta las instrucciones del programa)

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

16

Funcionamiento del computador

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

17

Cuanta memoria se precisa...

• •

•

•

1 Byte: Bloque de bits. Es la unidad de medida de la capacidad de la memoria o de los discos 1 Kilobyte (KB o K) = 1,024 bytes. Desde el punto de vista de un computador es un número redondo (Los computadores representan información en base 2, y 1024 es 2^10. Como las personas pensamos en base 10, solemos redondear un k a 1000 bytes. • Un disco con 360KB de datos, puede representar unos 360.000 caracteres. 1 Megabyte (MB or M) es un kilobyte al cuadrado (1,024 veces 1,024), o aproximadamente un millón de bytes. Un disco con una capacidad de 1.44MB puede contener 1.440.000 caracteres. • 1.44MB es un tamaño estándar para los discos de 3 pulgadas de doble densidad. 1 Gigabyte y Terabyte El termino gigabyte (GB or G) significa un kilobyte al cubo (1,024 * 1,024 * 1,024), o aproximadamente mil millones de bytes. El termino terabyte (TB o T) significa un kilobyte a la cuarta (1,024^4), más de un billón de bytes. Por ahora no hay en el mercado discos duros de tamaño de terabyte a precio razonable.

• ¿Cuanta memoria se precisa?: • Hace unos pocos años los computadores se vendían de serie con 1MB de RAM. Hoy se ofrecen con 500 MB, 1 GB... o más. Los discos duros están en cientos de gigabytes. • Una página de texto típico contiene entre 2,500 y 3,000 caracteres. 1MB equivale aproximadamente a 400 paginas de texto.

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

18

Cuestiones generales sobre el software

• Estilo de Programación Programación imperativa • Lenguajes orientados a instrucciones • Programas = Receta • Se encadenan de forma explicita las instrucciones.

• Influenciado por la arquitectura de la máquina • VARIABLES: Direcciones de memoria. Datos • INSTRUCCIÓN BASICA: Asignación. Acción. (Dar valor a una variable) • COMPOSICIÓN SECUENCIAL DE ACCIONES.

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

19

Cuestiones generales sobre el software •

Metodología de Programación Programación Estructurada Conjunto de ideas gestadas en torno al grupo de trabajo WG2.3 (Programming Methodology) de IFIP:

• Utilización de mecanismos de abstracción (funcional y de datos) como herramienta para dominar la complejidad. • Utilización de una metodología de diseño descendente o por refinamientos sucesivos (abstracción funcional) • Reducido número de estructuras de control: • • •

Composición secuencial Composición condicional Composición iterativa

• Énfasis en los mecanismos de estructuración de datos. •

Se introduce la idea de tipo abstracto de dato: Separación de los aspectos ligados a la especificación de un tipo de los de la implementación.

• Definición de métodos que garanticen la corrección de programas (verificación formal) • Notación independiente del lenguaje de programación. Programas =

Algoritmos + Estructuras de datos

• Estructuras de datos = Abstracciones de la realidad que nos permiten representar el conjunto de situaciones esperables al resolver el problema. • Algoritmos = Esquemas de composición de instrucciones que permiten representar de forma no ambigua el flujo de control (El orden en el que se ejecutarán las instrucciones)

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

20

Lenguajes de Programación

• Jerarquía de Niveles de lenguajes de programación • Ejemplo del “Procesador” Tractor Oruga

MI

A

R

MD

A

R

1

1

0

1

1

0

Avanza 1 m

1

0

1

1

0

1

Retrocede 1 m

1

1

0

0

0

0

Gira Derecha 90 º

0

0

0

1

1

0

Gira Izquierda

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

21

Procesador tractor oruga

Problema El tractor se encuentra en A, mirando al norte, y tengo que llevarlo a B Algoritmo Sigue recto hasta el fondo Gira a la derecha Sigue recto hasta el fondo Programa MI A 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

R MD A R 0 1 1 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0

Lo lleva a I Lo direcciona hacia B Lo lleva a B

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

22

Lenguaje de Maquina

Es farragoso programar a nivel MAQUINA Para facilitar la programación nos inventamos: • Nemotécnicos AV Avanza GD Giro Derecha RE Retrocede GI Giro Izquierda Programa AV AV GD AV AV AV AV AV AV

•

Lo lleva a I Lo direcciona hacia B

Lo lleva a B

Esquemas de composición Programa Avanza 2 Derecha 1 Avanza 6

•

110110 110000 101101 000110

Avanza x AV x Derecha x GD x Izquierda x GI x Retrocede x RE x

Hemos mejorado en ABSTRACCION pero nos hemos alejado de lo que “interpreta la maquina”. NECESIDAD DE TRADUCCION

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

23

Lenguaje Maquina

• Supongamos otro procesador: Una maquina con un único motor que puede: Avanzar 1 m 0 1 Retroceder 1 m 1 0 Girar Izquierda 90 1 1 Problema: El mismo Algoritmo: El mismo Programa: 01 01 11 11 11 01 01 01 01 01 01 DISTINTO • Pero el programa, en alto nivel, puede ser el mismo, basta con el traductor adecuado 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 0 0 0 1 1 0 1 1 0 1 1 0 1 1 0

Programa

1 1 0 1 1 0

Avanza 2 Derecha 1 Avanza

Código para el primer tractor

1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0

6 010111 111101 0 1 0 10 1 01 01

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

Código para el tractor con Un solo giro 09/09/2004

24

Lenguaje Máquina / CPU / Memoria

ENSAMBLADOR

LENGUAJE MÁQUINA

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

25

Lenguaje Máquina / CPU / Memoria

<

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

26

Lenguaje Máquina / CPU / Memoria

<

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

27

Lenguaje Máquina / CPU / Memoria

<

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

28

Lenguaje Máquina / CPU / Memoria

<

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

29

Niveles de lenguajes de programacion

• Alto Nivel • Mas fáciles de programar • Independencia de la maquina • Necesidad de traductores compiladores • Menor coste de desarrollo • Mas fácilmente mantenibles • Detección de errores • Transportables • Son un compromiso entre eficiencia y manejabilidad • Bajo Nivel • Programas específicos para un tipo de máquina • Pueden permitir hacer cosas de forma más eficiente.

Maquina

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

30

Lenguajes de Programación

• • • •

• • • •

•

FORTRAN (1965): FORmula TRANslator. Calculo científico. COBOL (1959). Ideal para gestión: Pocas estructuras de control, muchas capacidades de manejo de dato. ALGOL (1960): Primer intento de formalizar la resolución de problemas. Programas estructurados con tipos de datos. Lisp (1960): Sigue en uso. Estructura de datos simple (La lista). Tratamiento simbólico de la información. Su éxito se debe a que soporta más estrategias de descomposición modular que cualquier otro lenguaje. BASIC (1965): Beginners All Purpose Symbolic Language. Lenguaje interpretado, sin énfasis en tipos de datos. PASCAL (1971): Desciende de ALGOL. Paradigma de la programación estructurada. C (1972): Desarrollado por Dennis Ritchie de AT&T Bell Laboratories para ofrecer un lenguaje de alto nivel en el cual se pudiera programar UNIX. Lenguajes orientados a objetos (C++, Eiffel, C#,…): A la hora de organizar el software se focaliza en las abstracciones de datos en lugar de en la funcionalidad. JAVA: ¡Lenguaje orientado a objeto, que se puede ejecutar en cualquier máquina! Idea de máquina virtual.

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

31

Lenguajes Interpretados/Compilados

•

Ejecución interpretada del programa fuente • Se iteran los siguientes pasos 1. Obtención de la siguiente instrucción a ejecutar del código fuente 2. Análisis de la instrucción y determinación de las acciones a ejecutar 3. Ejecución de las correspondientes acciones

•

Ejecución del programa compilado • Se realiza previamente la compilación del programa fuente en la versión equivalente del programa en lenguaje máquina. Esta versión se conoce como programa objeto. • El programa objeto se une, eventualmente, con los subprogramas de biblioteca descritos en el programa fuente para obtener el programa ejecutable. Esta operación se denomina edición de uniones (link en inglés).

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

32

Java, código objeto que se ejecuta en cualquier máquina • Un applet es un programa escrito en Java que anima una porción de la página Web • El usuario puede interaccionar con un applet, gracias a que se trata de un programa. • Un applet se ejecuta completamente en el cliente: • Una vez transmitido la velocidad de la interacción no depende de la red

• Si es necesario el applet comunicar con el servidor

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

se

puede

09/09/2004

33

Java, código objeto que se ejecuta en cualquier máquina • Una aplicación java debe poderse ejecutar en una amplia gama de plataformas con diferentes SO y procesadores. • Las aplicaciones Java se almacenan en un código intermedio independiente de la plataforma (el byte-code) Applet java Compilador de java

Bycodes

Verificador de Bytecode

Cargador de clase

Almacén de Applets

Servidor Intérprete de Java (JVM)

Plataforma

Cliente Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

MacOS UNIX Windows etc. 09/09/2004

34

Elementos de un Lenguaje

• Los elementos que definen un lenguaje son: • SIMBOLOS • • • •

Palabras clave = {IF, THEN, WHILE, …} Caracteres = {‘a’,..’z’,’A’..’Z’,’#’,’?’,……. } Dígitos = {0,..,9} Otros símbolos = {‘.’ , ’,’ , ‘;’ ,…}

• SINTAXIS • Conjunto de reglas sintácticas • Notaciones para expresar las reglas: Backus-Naur Grafo Sintáctico

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

35

Sintaxis

•

Grafos Sintácticos

•

Backus-Naur

A 1 B 2 letra digito

::= ‘A’ I ‘B’ I… I‘Z’

Z 9 alternativa

0 21 digito

::= ‘0’ I ‘1’ I… I‘9’ 9 identificador

letra

0 o más veces digito _

::= { I I’_’}

Ejemplos identificadores válidos: P3Q NUMERO_PI Ejemplo identificadores no válidos: 3PQ _numero Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

36

Sintaxis

sentencia IF

IF

expresión booleana

THEN

sentencia

ELSE

sentencia

0 o 1 vez ::= IF THEN [ELSE ]

sentencia W HILE

WHILE

expresión booleana

DO

sentencia

::= WHILE DO

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

37

Sintaxis

entero sin signo

numero sin signo entero sin signo

digito

+ .

digito

entero sin signo

E -

expresion constante

+

identificador constante

-

numero sin signo

constante

'

caracter

'

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

38

Propiedades de los algoritmos

• Condiciones Necesarias • Finitud • No ambigüedad • Propiedades deseables • Generalidad • Eficiencia • Independencia de la máquina

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

39

Sistema Operativo

• Sistema Operativo • Conjunto de programas que tienen por misión facilitar la utilización del computador • • • • •

Acceso a los usuarios autorizados Edición de ficheros de texto Puesta a punto y ejecución de programas Seguridad y protección Facturación y contabilidad de uso de recursos • Etc.

• Gestión óptima de la máquina • Gestión de memoria • Control de dispositivos periféricos • Acceso a ficheros • Asignación de recursos y ordenación de tareas • Etc.

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

40

Entorno de programación

• Entorno de trabajo: • Programa cuya misión es facilitar el desarrollo de programas utilizando un determinado lenguaje • Integra herramientas: • Edición e programas fuente (C, C++, Java, Pascal, Ada, ...) • Compilación de programas fuente • Depuración de programas • Ejecución y prueba de programas • Construcción de programas ejecutables y bibliotecas

Programación. Pedro Álvarez, José Ángel Bañares, Pedro Latorre, Santiago Velilla Tema 1. Conceptos Básicos de Programación

09/09/2004

41