Post on 13-Nov-2015
Introduccin a la ProgramacinGrado en Ingeniera Informtica
Teora - Curso 2010-2011
Contenido 2 Problemas, Algoritmos y Programas
Contenido 2.- Problemas, Algoritmos y Programas2.1.- Algoritmos.
2.1.1.- Concepto de algoritmo.2.1.2.- Ejemplos de diseo de un algoritmo.
2.2.- Proceso de creacin de un Programa.2.3.- Datos, tipos de datos y operaciones primitivas.
2.3.1.- Datos numricos.2.3.2.- Datos lgicos (booleanos).2.3.3.- Datos tipo carcter y tipo cadena.
2
2.3.3.- Datos tipo carcter y tipo cadena.2.4.- Variables y expresiones.
2.4.1.- Constantes y variables.2.4.2.- La operacin de asignacin.2.4.3.- Evaluacin de expresiones. Precedencia de operadores.2.4.4.- Entrada y salida.
2.5.- Descripcin de algoritmos.2.5.1.- Lenguaje natural.2.5.2.- Diagrama de Flujo.2.5.3.- Pseudocdigo.2.5.4.- Diagrama N-S.
Contenido 2.- Problemas, Algoritmos y Programas
2.1 Algoritmos
2.2.1.- CONCEPTO DE ALGORITMO
Secuencia de pasos que describen el mtodo para resolver un problema
La ejecucin de un algoritmo implica la ejecucin de cada uno
3
La ejecucin de un algoritmo implica la ejecucin de cada uno de sus pasos
La resolucin de un problema exige el diseo del algoritmo adecuado
Contenido 2.- Problemas, Algoritmos y Programas
2.1 Algoritmos
2.2.1.- CONCEPTO DE ALGORITMO
Pasos para resolver un problema en un ordenador:1. Anlisis del problema 2. Diseo del algoritmo
4
3. Codificacin4. Traduccin, Validacin y Ejecucin
El ALGORITMO (paso 1) es independiente de: El lenguaje de programacin (paso 3) El ordenador (paso 4)
Contenido 2.- Problemas, Algoritmos y Programas
2.1 Algoritmos
2.2.1.- CONCEPTO DE ALGORITMOREQUISITOS de un ALGORITMO:
Acciones bien definidas Secuencia finita de operaciones en un orden determinado Debe acabar en un tiempo finitoUn algoritmo es una secuencia finita de operaciones bien definidas
5
Un algoritmo es una secuencia finita de operaciones bien definidas que resuelven un problema, cada una de las cuales requieren una cantidad finita de memoria y se realiza en un tiempo finito.
BONDAD de un ALGORITMO:Factores que la determinan: Tiempo Recursos de memoria
Contenido 2.- Problemas, Algoritmos y Programas
2.1 Algoritmos
2.2.1.- Ejemplos de diseo de un algoritmoUn cliente realiza un pedido a una fbrica. La fbrica examina laficha del cliente, para comprobar si este es o no solvente antes deenviar el pedido.
6
1. Inicio.2. Leer el pedido.3. Examinar la ficha del cliente.4. Si el cliente es solvente, aceptar pedido;5. en caso contrario, rechazar pedido.6. Fin.
Contenido 2.- Problemas, Algoritmos y Programas
2.1 Algoritmos
2.2.1.- Ejemplos de diseo de un algoritmoSuma de los nmeros pares entre 2 y 1000.
2+4+6+8+...+1000. SUMA y NUMERO 1. Inicio.2. Inicializar SUMA a 0.
7
3. Inicializar NUMERO a 2.4. Sumar NUMERO a SUMA. El resultado ser el nuevo valor de
SUMA.5. Incrementar NUMERO en 2 unidades.6. Si NUMERO
2.2.- Proceso de Creacin de un Programa1. Planteamiento y anlisis del problema
Definicin Representacin de los datos
Entradas Salidas
2. Diseo del Algoritmo Descomposicin en subproblemas Diseo descendente Refinamientos sucesivos
Optimizacin y Depuracin
8
Optimizacin y Depuracin3. Implementacin
Eleccin del lenguaje Adaptacin al problema Conocimientos Disponibilidad de rutinas Herramientas de desarrollo Entorno de la aplicacin
Codificacin (normas de estilo)4. Ejecucin
Traduccin Prueba y Depuracin
Contenido 2.- Problemas, Algoritmos y Programas
2.3.- Datos, Tipos de Datos y Operaciones Primitivas
Datos: Objetos con los cules opera un ordenadorDatos de entrada Instrucciones Datos de salida
El diseo de la estructura de datos es tan importante como eldiseo del algoritmo
Tipos de datos:
9
Tipos de datos: Simples
numrico entero real
lgico carcter
Estructurados
Contenido 2.- Problemas, Algoritmos y Programas
2.3.- Datos, Tipos de Datos y Operaciones Primitivas
2.3.2.- Datos numricos
Enteros: subconjunto finito de los enteros ( Rango : de 32768 a 32768)
Reales: subconjunto de los nmeros reales
10
Reales: subconjunto de los nmeros realesNotacin exponencial o cientfica:
367520100000000000000 3.675201 x 1020
.0000000000302579 3.02579 x 10-11
36.75201 x 1018 36.75201 mantisa 18 exponente
Contenido 2.- Problemas, Algoritmos y Programas
2.3.- Datos, Tipos de Datos y Operaciones Primitivas
2.3.2.- Datos lgicos (booleano)Posibles valores:
Verdadero (true) Falso (false)
2.3.3.- Datos tipo carcter
11
2.3.3.- Datos tipo carctercaracteres alfabticos (A, B, C, ..., Z) (a, b, c, ..., z)caracteres numricos (1, 2, 3, ..., 9, 0)caracteres especiales (+, -, *, /, ^, ., ;, $, ...)
En algunos lenguajes existe el tipo cadena como tipo de dato simple Ej/ Hola
Contenido 2.- Problemas, Algoritmos y Programas
2.4.- Variables y Expresiones
2.4.1.- Variables y ConstantesConstante: objeto que contiene un valor que no vara durante la ejecucin del programa.
Identificador : nombre que identifica a una constanteTipo : Determinado por el valor que almacena.
12
Tipo : Determinado por el valor que almacena.enteras, reales, carcter y lgicas Ej/ 20, 1.44, B, Pepe.
Definicin:const
PI = 3.1416
Contenido 2.- Problemas, Algoritmos y Programas
2.4.- Variables y Expresiones
2.4.1.- Variables y Constantes
Variable: objeto que contiene un valor que puede variar durante la ejecucin del programa
Identificador : nombre que identifica a la variable. Ej /notasTipo : No cambia. Determina el tipo del valor que almacenar la
13
Tipo : No cambia. Determina el tipo del valor que almacenar la variable y la operaciones que se pueden realizar con ella.
enteras, reales, carcter y lgicas
Definicinvar
entero: notas
Contenido 2.- Problemas, Algoritmos y Programas
2.4.- Variables y Expresiones
2.4.2.- La operacin de asignacinSe utiliza para darle valor a una variableSe representa por Formato
Identificador_de_variable expresinNotas 8
14
Notas 8Notas 5
El valor que tuviera la variable antes de la operacin de asignacindesapareceEvaluacin en dos pasos
1.-Se obtiene el valor de la expresin del lado derecho2.-Se almacena ese valor en la variable cuyo identificador est a la
derecha del operador.
Contenido 2.- Problemas, Algoritmos y Programas
2.4.- Variables y Expresiones
2.4.2.- La operacin de asignacinEjemplos
var entero: x, y
......
x 2
15
x 2y x + 2
var entero : n........
n 2n n + 1
Contenido 2.- Problemas, Algoritmos y Programas
2.4.- Variables y Expresiones
2.4.2.- La operacin de asignacinEjemplos
Asignacin aritmticavar
entero : x
16
entero : x.......
x 3 + 4 * 8
Contenido 2.- Problemas, Algoritmos y Programas
2.4.- Variables y Expresiones
2.4.2.- La operacin de asignacinEjemplos
Asignacin lgicavarlogico: x........
17
........
x 8< 5
Asignacin de cadenavarcadena: cad......
cad Hola que tal
Contenido 2.- Problemas, Algoritmos y Programas
2.4.- Variables y Expresiones
2.4.3.- Evaluacin de Expresiones. Precedencia de Operadores.Expresin: combinacin de variables, constantes, operadores, nombrede funciones y parntesis, que indican el orden de clculo.
Ejemplo: ( )( ) 3*5*32/4*)8( dpcuadrado +
18
Segn el tipo de datos de los elementos de la expresin, sta puedeser: aritmtica, cuyo resultado es de tipo numrico; lgica, cuyoresultado es de tipo lgico y carcter, siendo su resultado de tipocarcter.
Contenido 2.- Problemas, Algoritmos y Programas
2.4.- Variables y Expresiones
2.4.3.- Evaluacin de Expresiones. Precedencia de Operadores.
Expresiones Aritmticas
Operador Significado
19
+ suma- resta* multiplicacin/ divisin realdiv divisin enteramod resto (mdulo)
Contenido 2.- Problemas, Algoritmos y Programas
2.4.- Variables y Expresiones
2.4.3.- Evaluacin de Expresiones. Precedencia de Operadores. Reglas de prioridad para las operaciones aritmticas:1. Se evalan primero todas las operaciones que se encuentran entre parntesis.
Si aparecen parntesis anidados, es decir unos dentro de otros, se evalan primero las operaciones dentro de los parntesis ms internos.
2. El orden de precedencia para los operadores aritmticos que aparecen en las
20
El orden de precedencia para los operadores aritmticos que aparecen en las operaciones ser:
1. operador unario -2. operadores *, /, div, mod (todos tienen la misma prioridad)3. operadores +, - (ambos presentan la misma prioridad)4. Si en una expresin, encerrada o no entre parntesis, aparece ms de un
operador con la misma prioridad se evaluar de izquierda a derecha.
Contenido 2.- Problemas, Algoritmos y Programas
2.4.- Variables y Expresiones
2.4.3.- Evaluacin de Expresiones. Precedencia de Operadores.
Ejemplos de evaluacin de operaciones aritmticas:
a) 2 * 5 + 4*3 b) 3 + 2 *6 8 / 2 c) 4 / 2 * 2 3 + 5
21
a) 2 * 5 + 4*3 b) 3 + 2 *6 8 / 2 c) 4 / 2 * 2 3 + 510 + 4*3 3 + 12 8 / 2 2 * 2 3 + 5 10 + 12 3 + 12 4 4 3 + 522 15 4 7 + 5
11 2
Contenido 2.- Problemas, Algoritmos y Programas
2.4.- Variables y Expresiones
2.4.3.- Evaluacin de Expresiones. Precedencia deOperadores.
Expresiones lgicas:
22
Se combinan constantes lgicas, variables lgicas y otras expresiones lgicas, utilizando los operadores lgicos y los operadores relacionales.
Contenido 2.- Problemas, Algoritmos y Programas
2.4.- Variables y Expresiones2.4.3.- Evaluacin de Expresiones. Precedencia de Operadores. Expresiones lgicas:Operadores relacionalesComparaciones entre valores de tipo numrico, carcter o lgico, y el resultado ser verdadero o falso. Con estos operadores se pueden expresar condiciones en los algoritmos, de las cuales depender la
23
expresar condiciones en los algoritmos, de las cuales depender la realizacin de ciertas tareas.
Formato general:expresin1 operador_de_relacin expresin2
Contenido 2.- Problemas, Algoritmos y Programas
2.4.- Variables y Expresiones2.4.3.- Evaluacin de Expresiones. Precedencia de Operadores. Expresiones lgicas:Operadores relacionales
Operador Significado
< menor que> mayor que
24
> mayor que= igual que menor o igual que
mayor o igual que distinto de
Ejemplos:4 > 2 verdadero(3+1) < (8-3) verdadero
Contenido 2.- Problemas, Algoritmos y Programas
2.4.- Variables y Expresiones2.4.3.- Evaluacin de Expresiones. Precedencia de Operadores.Prioridad de los Operadores relacionales Las comparaciones de datos de tipo numrico, siguen la ordenacin habitual que se emplea en
matemticas. Cuando se aplican los operadores relacionales a datos de tipo lgico, la constante falso es
menor que la constante verdadero. Si en la expresin aparecen caracteres alfabticos en minsculas, stos siguen la ordenacin
alfabtica: a < b < c < < h < < z.Si en la expresin aparecen caracteres alfabticos en maysculas, stos siguen la ordenacin
25
Si en la expresin aparecen caracteres alfabticos en maysculas, stos siguen la ordenacinalfabtica: A < B < C < < H < < Z.
Los caracteres que representan a los dgitos decimales guardan su orden. Es decir: 0 < 1 < 2< < 8 < 9.
Pero si aparecen caracteres especiales , =, *, +, ), /, &, %, $, #, \, ..., entonces habra queconsultar el cdigo normalizado.
Estas agrupaciones se encuentran en orden decreciente, de esta forma sera:* < 1 < < 9 < A < < Z < a < < z. Sin embargo, sera recomendable consultar el
cdigo de caracteres de su ordenador: ASCII (American Standar Code for InformationInterchange) o bien el EBCDIC (Extended Binary-Coded Decimal Interchange Code).
Contenido 2.- Problemas, Algoritmos y Programas
2.4.- Variables y Expresiones2.4.3.- Evaluacin de Expresiones. Precedencia de Operadores. Expresiones lgicas:Operadores lgicos
Operador lgico Significado Expresin lgicano negacin de p no py conjuncin de p y q p y q
26
y conjuncin de p y q p y q disyuncin de p y q p q
Tablas de verdad:no:
p no pverdadero falsofalso verdadero
Contenido 2.- Problemas, Algoritmos y Programas
2.4.- Variables y Expresiones2.4.3.- Evaluacin de Expresiones. Precedencia de Operadores. Expresiones lgicas: Operadores lgicosTablas de verdad:Y:
p q p y qverdadero verdadero verdaderoverdadero falso falsofalso verdadero falsofalso falso falso
27
falso falso falso
p y q es verdadero slo si p y q son verdadero.
:p q p q verdadero verdadero verdaderoverdadero falso verdaderofalso verdadero verdaderofalso falso falso
p q son verdadero cuando p, q o ambas son verdadero.
Contenido 2.- Problemas, Algoritmos y Programas
2.4.- Variables y Expresiones2.4.4.- Operaciones de E/S bsicas. Lectura
Leer (variable_entrada)Ejemplo:leer(a) leer un valor de la entrada y lo almacenar en la variable a.
Escritura
28
EscrituraEscribir(cadena)
Ejemplos:escribir(Hola, que tal) escribir la cadena: Hola, que tal escribir(El valor de la variable a es: , a), suponiendo que el valor almacenado
en la variable a sea igual a 3, visualizar: El valor de la variable a es 3.
Contenido 2.- Problemas, Algoritmos y Programas
2.5.- Descripcin de algoritmos
Mtodos de descripcin de algoritmos
Lenguaje Natural. Pseudocdigo.
29
Pseudocdigo. Diagrama de Flujo. Diagrama de Nassi-Schneiderman.
Contenido 2.- Problemas, Algoritmos y Programas
2.5.- Descripcin de algoritmos
2.5.1.- Lenguaje Natural
Similar al lenguaje hablado. No sigue ninguna norma ni estructura en su representacin.
30
No es adecuado por su ambigedad y falta de precisin.
Contenido 2.- Problemas, Algoritmos y Programas
2.5.- Descripcin de algoritmos
2.5.2.- Pseudocdigo Parecido al lenguaje natural, pero est sujeto a determinadas reglas Estructura es similar a la de un programa, lo que facilita su traduccin a lenguaje de
alto nivel.
Es un punto intermedio entre el lenguaje natural y el lenguaje de alto nivel.Es bastante apropiado si se utiliza un lenguaje de programacin estructurado por la
31
Es bastante apropiado si se utiliza un lenguaje de programacin estructurado por lasimilitud que existe entre ellos.
Esta herramienta de diseo de algoritmos permite la posibilidad de describir tipos dedatos, constantes, variables y cualquier tipo de expresin, adems de instruccionesde entrada y salida e instrucciones de control.
Contenido 2.- Problemas, Algoritmos y Programas
2.5.- Descripcin de algoritmos2.5.2.- Pseudocdigo. Estructura
// Comentarios que faciliten la comprensin del algoritmo, por ejemplo, objetivos // del algoritmo, datos del programador, datos de entrada y datos de salida.
Algoritmo Nombre_algoritmoconst
//Seccin de definicin de constantestipos
//Seccin de definicin de tipos creados por el programador
32
//Seccin de definicin de tipos creados por el programadorvar
//Seccin de declaracin de variablesinicio
//Inicializacin de variablesAccin 1Accin 2
.
. //Cuerpo del algoritmoAccin n
fin_algoritmo
Contenido 2.- Problemas, Algoritmos y Programas
2.5.- Descripcin de algoritmos
2.5.3.- Diagrama de Flujo
Claridad en la comprensin Dificultad en la actualizacin Se usan unos smbolos que contienen las instrucciones del algoritmo,
estos smbolos se enlazan mediante flechas que indican el flujo, el ordeno secuencia en el que deben ir realizndose las operaciones.
33
o secuencia en el que deben ir realizndose las operaciones. Diagrama del Sistema u Organigrama: muestra un esquema de la
aplicacin segn los datos de E/S y los soportes donde se encuentran Diagrama de Detalles u Ordinograma: Se describe toda la secuencia de
operaciones que resuelven el problema. Se debe expresar el Comienzo, el fin, las operaciones y la secuencia.
Contenido 2.- Problemas, Algoritmos y Programas
2.5.- Descripcin de algoritmos
2.5.3.- Diagrama de Flujo
REGLAS DE CONSTRUCCIN DE ORDINOGRAMAS: El indicador de comienzo y fin del algoritmo slo puede aparecer una vez. El comienzo del algoritmo debe estar en la parte superior. El flujo de informacin debe aparecer de arriba hacia abajo y de izquierda a
derecha.
34
derecha. Las lneas de flujo no deben cruzarse, para ello se utilizan los conectores o
bien para la misma pgina o bien para pginas distintas. No pueden existir cruces de lneas de flujo entre operaciones unidas por
conectores, stas tambin se unen con conectores. No debe hacerse mucho uso de comentarios.
Contenido 2.- Problemas, Algoritmos y Programas
2.5.- Descripcin de algoritmos
2.5.3.- Diagrama de Flujo
Terminal. Indica el comienzo (inicio) y el final (fin) de un algoritmo.
Entrada/Salida. Representa la introduccin de datos o bien devolucin de resultados.
35 Contenido 2.- Problemas, Algoritmos y Programas
SI
NO
Proceso. Cualquier tipo de operacin entre los datos.
Decisin. Indica operaciones lgicas o relacionales entre los datos
2.5.- Descripcin de algoritmos
2.5.3.- Diagrama de FlujoConector. Se usa para conectar dos puntos cualesquiera de un ordinograma en la misma pgina. Hay que incluir un conector en la entrada y otro en la salida.
Conector. Se usa para la conexin entre dos puntos cualesquiera de un ordinograma en diferentes pginas.
36 Contenido 2.- Problemas, Algoritmos y Programas
Lnea de flujo. Indica en el sentido en el que se van a realizar las operaciones.
Llamada a subrutina. Se usa para hacer una llamada a un subalgoritmo.
Lnea conectora. Se usa para unir dos objetos.
2.5.- Descripcin de algoritmos
2.5.4.- Diagrama de Nassi-Schneiderman
Combinacin de pseudocdigo y diagrama de flujo Las instrucciones se sitan en rectngulos
Poco usado
Nombre del algoritmo
37 Contenido 2.- Problemas, Algoritmos y Programas
Nombre del algoritmo
Accin 1
Accin 2
.
.
.
Accin n
Fin_algoritmo
Ejemplo Ilustrativo
Siguiendo los pasos para la realizacin de un programa y utilizandotodos los mtodos de descripcin de algoritmos estudiados sedesea resolver el siguiente problema:
38
Realiza un programa que dado un valor para el radio escriba lalongitud de la circunferencia, el rea del crculo y el volumen de laesfera.
Contenido 2.- Problemas, Algoritmos y Programas
Ejemplo Ilustrativo1.- Planteamiento y anlisis del problema
Definicin: programa que dado un valor para el radio escriba la longitud de la circunferencia, el rea del crculo y el volumen de la esfera.
Representacin de los datos Entradas
39
Entradas Variables: Radio (Tipo real) Constantes: PI 3.1416
Salidas Variables: Longitud, rea y Volumen (Tipo real)
Recursos: Longitud= 2Radio rea= Radio2 Volumen: 4/3Radio3
Contenido 2.- Problemas, Algoritmos y Programas
Ejemplo Ilustrativo2.- Diseo del Algoritmo
Descripcin en Lenguaje Natural1) Inicio.2) Leer Radio.3) Calcular Longitud, Superficie y Volumen4) Escribir resultados.
40
4) Escribir resultados.5) Fin.
Descomposicin en subproblemas Diseo descendente Refinamientos sucesivos Optimizacin y Depuracin
Contenido 2.- Problemas, Algoritmos y Programas
Ejemplo Ilustrativo2.- Diseo del Algoritmo
Descripcin en Lenguaje Natural
1) Inicio.2) Leer Radio.3) Calcular Longitud
41
3) Calcular Longitud4) Calcular Superficie5) Calcular Volumen6) Escribir Longitud, Superficie y Volumen.7) Fin.
Contenido 2.- Problemas, Algoritmos y Programas
Ejemplo Ilustrativo2.- Diseo del Algoritmo
Descripcin en Lenguaje Natural
1) Inicio.2) Leer Radio.3) Longitud= 2*3.1416*Radio
42
3) Longitud= 2*3.1416*Radio4) Superficie = 3.1416*(Radio*Radio)5) Volumen= 4/3*3.1416*(Radio*Radio*Radio)6) Escribir Longitud, Superficie y Volumen.7) Fin.
Contenido 2.- Problemas, Algoritmos y Programas
Ejemplo Ilustrativo2.- Diseo del Algoritmo
Descripcin en Diagrama de FlujoInicio
leer(radio)
43 Contenido 2.- Problemas, Algoritmos y Programas
Longitud = 2* 3.1416* Radio
escribir(La Longitud es, longitud, El rea es , rea, El Volumen es, Volumen)
Fin
rea = 3.1416* Radio*Radio
Volumen = 4/3* 3.1416* Radio*Radio*Radio
Ejemplo Ilustrativo2.- Diseo del Algoritmo
Descripcin en Diagrama de Nassi-Schneiderman
Longitud = 2* 3.1416* Radio
Leer (radio)
Inicio
44 Contenido 2.- Problemas, Algoritmos y Programas
escribir(La Longitud es, longitud, El rea es , rea, El Volumen es, Volumen
Volumen = 4/3* 3.1416* Radio*Radio*Radio
rea = 3.1416* Radio*Radio
Fin
Ejemplo Ilustrativo2.- Diseo del Algoritmo Descripcin en Pseudocdigo
//Algoritmo que calcula la longitud de una circunferencia,//el rea del crculo y el volumen de la esfera.Algoritmo Clculosconst
PI= 3.1416var
45
varreal: radio, longitud, area, volumen
inicioleer(radio)longitud 2* PI*radioarea 2* PI* (radio* radio)volumen (4/3) * PI *(radio*radio*radio)escribir(La longitud de la circunferencia es igual a, longitud, El rea del crculo es, area, El volumen de la esfera es, volumen)
fin_algoritmo
Contenido 2.- Problemas, Algoritmos y Programas
Ejemplo Ilustrativo3.- Implementacin del Algoritmo Lenguaje C/*Algoritmo que calcula la longitud de una circunferencia,el rea del crculo y el volumen de la esfera.*/#include #define PI 3.1416int main(){
46
{float radio, longitud, area, volumen;printf(Introduzca el radio);scanf(%f,&radio);longitud = 2* PI*radio;area = 2* PI* (radio* radio);volumen= 4/3 * PI *(radio*radio*radio);printf(La longitud de la circunferencia es igual a %f, El rea del crculo es %f y El volumen de la esfera es %f, longitud, area, volumen);
}
Contenido 2.- Problemas, Algoritmos y Programas