1 Algoritmos y Programación Primavera de 2006 Javier M. Hernández FCFM Lectura 5: Diagramas de...

11

Algoritmos y ProgramaciónAlgoritmos y Programación Primavera de 2006 Primavera de 2006

Javier M. Hernández

FCFM

Lectura 5: Lectura 5: Diagramas de Flujo - AlgoritmosDiagramas de Flujo - Algoritmos

B. Universidad Autónoma de PueblaB. Universidad Autónoma de Puebla

22

Tópicos Tópicos

• El Ciclo de Desarrollo del SoftwareEl Ciclo de Desarrollo del Software

• Diagramas de FlujoDiagramas de Flujo– SelecciónSelección– SecuenciaSecuencia

– IteraciónIteración

• Cómo diagnosticar errores en sus programas?Cómo diagnosticar errores en sus programas?– Métodos para debugging Métodos para debugging – Métodos para pruebas Métodos para pruebas

33

Componentes del Proceso de Desarrollo del Software

Definir el problema claramenteAnalizar el problema

Diseñar un algoritmodiseño top-down

Documentar al sistema

Codificar (Usar) el algoritmoProbar el código

44

Ciclo de DesarrolloCiclo de Desarrollo

Análisis Diseño Implementar Probar

debugging y pruebas

55

Debugging y PruebasDebugging y Pruebas

Debugging: el proceso de encontrar y corregir los errores (a.k.a “bugs”)Pruebas: ejecutar el programa sobre un conjunto de datos de prueba

66

Tipos de ErroresTipos de Errores

• sintáctico: cómo se escriben las instrucciones

• semántico: qué representan

while (i=0; i < 5; i++){ printf(“%d\n”, i);}

Ejemplo 1:

for (i=0; i < 5; i++);{ printf(“%d\n”, i);}

Ejemplo 2:

if (choice = ‘Q’) { break;}

Ejemplo 3:

77

Diagramas de FlujoDiagramas de Flujo

• Representar el Representar el flujo del controlflujo del control del algoritmo: del algoritmo:– secuenciassecuencias– selecciónselección– IteraciónIteración

• Útil para:Útil para:– Encontrar errores semánticosEncontrar errores semánticos– Determinar el conjunto de datos de pruebasDeterminar el conjunto de datos de pruebas

88

Secuencia (revisión)Secuencia (revisión)

• Series de instrucciones que se realizarán en un Series de instrucciones que se realizarán en un orden secuencial fijoorden secuencial fijo

• Ejemplo 1: Ejemplo 1: Paso A:Paso A: número de entradanúmero de entradaPaso B:Paso B: añadir 1 al númeroañadir 1 al númeroPaso C: Paso C: número de salidanúmero de salida

99

Diagramas de Flujo: SecuenciaDiagramas de Flujo: Secuencia

Paso A: número entrada

Paso B: número + 1

Paso C: número salida

Instrucciónen una caja rectangular

Orden de ejecuciónindicado por flechas

• Representado por instrucciones concatenadas (usualmente de forma vertical)

1010

Paso A:Paso A: número de entradanúmero de entrada

Paso B:Paso B:

si número es negativo,si número es negativo,Entonces sumar -1 a Entonces sumar -1 a

númerosnúmerossino sumar 1 al númerosino sumar 1 al número

Paso C:Paso C: número de salida número de salida

Ejemplo 2:

un algoritmoinvolucra

“selección”

Paso A: número entrada

Paso C: número salida

Secuencia (cont)Secuencia (cont)

1111

Diagrama de Flujo: SelecciónDiagrama de Flujo: Selección

Paso APaso A

if ( condición if ( condición C1C1 ) )

{{

<secuencia <secuencia S1S1>>

}}

elseelse

{{

<secuencia <secuencia S2S2>>

}}

Paso CPaso C

Paso A

C1 verdad?

S2

Paso C

S1

SI NO

Flecha marcada con resultado deprueba condición

Prueba deCondición enun diamante

1212

entrada númeroentrada número

si número es negativo,si número es negativo,

entoncesentonces sumar -1 a sumar -1 a númeronúmeroó añadir 1 a númeroó añadir 1 a número

salida con númerosalida con número

introducir número

es númeronegativo?

sumar -1 a número

SI NO

sumar 1 a número

número de salida

Ejemplo: Algoritmo a Diag. FlujoEjemplo: Algoritmo a Diag. Flujo

1313

Diagrama de Flujo: IteraciónDiagrama de Flujo: Iteración (ciclo while) (ciclo while)

while ( condición C1 )while ( condición C1 )

{{

<secuencia S1><secuencia S1>

}}

C1 verdad?

S1

SI

NO

1414

Diagrama de Flujo: Iteración Diagrama de Flujo: Iteración (ciclo for)(ciclo for)

for ( inicio ; condición C1 ; incremento ) {

<secuencia S1>} C1 verdad?

S1

SI

NO

inicio

incremento

1515

Cómo elegir que iteración usar?Cómo elegir que iteración usar?

• Sabes exactamente cuantas veces hay que ejecutar el Sabes exactamente cuantas veces hay que ejecutar el ciclo?ciclo?– Si la respuesta es afirmativa, use FORSi la respuesta es afirmativa, use FOR

• Es posible que la secuencia nunca sea ejecutada?Es posible que la secuencia nunca sea ejecutada?Si la respuesta es afirmativa, use WHILESi la respuesta es afirmativa, use WHILE

1616

Ejemplo: Código a Diag. Flujo Ejemplo: Código a Diag. Flujo (Vea el error!)(Vea el error!)

for ( i=0; i<10; i++ ) { scanf(“%d\n”, &x); if ( x < 0 ) { break; }}

es i < 10 ?

valor inicial de x

SI

NO

poner i a 0

incremento i

es x < 0 ?NO SI

1717

Ejemplo: Código a Diag. Flujo Ejemplo: Código a Diag. Flujo (versión correcta)(versión correcta)

for ( i=0; i<10; i++ ) { scanf(“%d\n”, &x); if ( x < 0 ) { break; }}

es i < 10 ?

valor inicial de x

SI

NO

poner i a 0

incremento i

es x < 0 ?

NO

SI

1818

Algoritmo a Diagrama de FlujoAlgoritmo a Diagrama de FlujoEjemplo: Sumar NúmerosEjemplo: Sumar Números

input totalNumerosinput totalNumeros

poner suma to 0poner suma to 0

poner contador a 0poner contador a 0

mientras (contador < totalNumeros)mientras (contador < totalNumeros)

{{

input siguienteNuminput siguienteNum

sumar siguienteNum a sumasumar siguienteNum a suma

sumar 1 a contadorsumar 1 a contador

}}

salida “Suma es” sumasalida “Suma es” suma

salida “Media es” suma/contadorsalida “Media es” suma/contador

valor inicial de totalNumeros

poner suma a 0

poner contador a 0

1919

es contador< totalNumeros?

Algoritmo a Diagrama de FlujoAlgoritmo a Diagrama de FlujoEjemplo: Sumar Números (cont)Ejemplo: Sumar Números (cont)


poner suma a 0poner suma a 0



{{



sumar 1 to contadorsumar 1 to contador

}}



valor inicial de siguienteNum

SI

NO

incrementar contador

sumar siguienteNum a suma

2020

Algoritmo a Diag. de FlujoAlgoritmo a Diag. de FlujoEjemplo: SumarNumeros (cont)Ejemplo: SumarNumeros (cont)





{{




}}



valor de salida para suma

valor de salida para suma/contador

2121

Algoritmo a Diag. de FlujoAlgoritmo a Diag. de FlujoEjercicio: SumarNumeros (cont)Ejercicio: SumarNumeros (cont)





{{




}}

output “Suma es” sumaoutput “Suma es” suma

output “Media es” suma/contadoroutput “Media es” suma/contador

Qué tal si totalNumeros

es cero?

2222

• Modificar el diagrama de flujo para añadir una Modificar el diagrama de flujo para añadir una verificación extra de modo que envie la media a verificación extra de modo que envie la media a output sólo cuando el contador es positivooutput sólo cuando el contador es positivo

Algoritmo a Diag. de FlujoAlgoritmo a Diag. de FlujoEjercicio: SumarNumeros (cont)Ejercicio: SumarNumeros (cont)

2323

Uso de Diagramas de Flujo Uso de Diagramas de Flujo

• Pseudo-código Pseudo-código diagrama de flujo diagrama de flujo

• Diagrama de flujo Diagrama de flujo código código

2424

Bases de DebuggingBases de Debugging

• Conocer el lenguaje (C, Fortran,…) bienConocer el lenguaje (C, Fortran,…) bien

printf(“%d\n”, &num);

Ejemplos:

scanf(“%s”, &name);

if (i < N);{ scanf(“%d\n”, &i);}

float x, y, z = 3.5;

scanf(“%f”, x);

2525

• Poner atención a los errores del compilador y Poner atención a los errores del compilador y mensajes de advertenciamensajes de advertencia

Ejemplos:

if (ch = ‘Q’){ break;}

Bases de Debugging (cont)Bases de Debugging (cont)

“Possible incorrect assignment”

int N;

… scanf(“%d”, N);

“Possible use of ‘N’ before declaration”

2626

TrazadoTrazado

• Ejecución trazada de un programa:Ejecución trazada de un programa:– locación en el programalocación en el programa– estatus/contenido de variablesestatus/contenido de variables

• Herramientas:Herramientas:– Ambiente de programación Ambiente de programación

» EE..gg,,. “step”, “breakpoints”, “watch”. “step”, “breakpoints”, “watch”– Declaraciones de debuggingDeclaraciones de debugging

» EE..g.g.,, valores de output de las variables, valores de output de las variables, marcadores en lugares marcadores en lugares específicos, etcespecíficos, etc

2727

Ejemplo: Declaraciones de Ejemplo: Declaraciones de Debugging Debugging

...for (i=0; i<N; i++){

scanf(“%s”, name);

}

2828

Ejemplo: Declaraciones de Ejemplo: Declaraciones de Debugging (cont) Debugging (cont)

TIP: hacer declaraciones de debug condicionales sobre variable booleana

const int debugging = 1;...for (i=0; i<N; i++){


if (debugging) {

printf("for: i=%d, name=%s\n", i, name);}

}

2929

Ejemplo: Declaraciones debugging Ejemplo: Declaraciones debugging (alternativo) (alternativo)

#define DEBUG 1int main()...for (i=0; i<N; i++){


#if DEBUG printf("for: i=%d, name=%s\n", i, name);

#endif}

3030

Técnicas de PruebaTécnicas de Prueba

• Datos de prueba deberán probar “completamente” al Datos de prueba deberán probar “completamente” al programa programa

• Todos los caminos lógicos del programa deberán ser Todos los caminos lógicos del programa deberán ser caminados (i.e., cada línea del código deberán ser caminados (i.e., cada línea del código deberán ser ejecutados una vez al menos)ejecutados una vez al menos)

• Use el diseño representado por el diagrama de flujoUse el diseño representado por el diagrama de flujo

TIP: contruya programas incrementalmente, probando componentes pequeños en serie

3131

Ejemplo: mejorCal Ejemplo: mejorCal

Problema:Problema:

• Escribir un programa que lea una lista de Escribir un programa que lea una lista de calificaciones, e imprima la mejor calificaciones, e imprima la mejor

• Ejemplo:Ejemplo:– Input:Input: 18 56 65 96 24 3018 56 65 96 24 30

– Output:Output: Mejor calificacion es 96Mejor calificacion es 96

3232

Ejemplo: mejorCal (cont)Ejemplo: mejorCal (cont)

poner mejorCal a 0poner mejorCal a 0looploop{{ input calificacioninput calificacion if (fin de input)if (fin de input) then salir ciclothen salir ciclo

}}output “Mejor calificacion“, mejorCaloutput “Mejor calificacion“, mejorCal

Algoritmo

3333

Ejemplo: mejorCal (cont) Ejemplo: mejorCal (cont)

poner mejorCal a 0poner mejorCal a 0looploop{{ input markinput mark if (end of input)if (end of input) then exit loopthen exit loop

if (calificacion > mejorCal)if (calificacion > mejorCal) thenthen {{ poner mejorCal a calificacionponer mejorCal a calificacion }}}}output “Mejor calificacion es“, mejorCaloutput “Mejor calificacion es“, mejorCal

Algoritmo

3434

Ejemplo: mejorCal (cont) Ejemplo: mejorCal (cont)

poner mejorCal a 0poner mejorCal a 0looploop{{ input calificacioninput calificacion if (end of input)if (end of input) then salir loopthen salir loop

if (calificacion > mejorCal)if (calificacion > mejorCal) thenthen {{ poner mejorCal a calificacionponer mejorCal a calificacion }}}}output “Mejor calificacion“, mejorCaloutput “Mejor calificacion“, mejorCal

Algoritmo

Cómo validola entrada?

3535

Clases de Datos de Prueba Clases de Datos de Prueba

• Datos válidos Datos válidos

• Datos válidos límites Datos válidos límites

• Casos especiales o no usuales Casos especiales o no usuales

• Datos no válidos Datos no válidos

3636

Datos de Prueba: Datos VálidosDatos de Prueba: Datos Válidos

• Datos razonables para el problemaDatos razonables para el problema

• Ejemplo: mejorCalEjemplo: mejorCal– Prueba de qué es?Prueba de qué es?– Si la calificación es sobre 100, datos válidos de Si la calificación es sobre 100, datos válidos de

prueba son prueba son 75, 65, 5575, 65, 55

3737

D. P.: Datos Válidos LímitesD. P.: Datos Válidos Límites

• Datos con valores extremosDatos con valores extremos

• Ejemplo: mejorCalEjemplo: mejorCal– mínimo de 0mínimo de 0– máximo de 100máximo de 100

• Condiciones de selección de pruebaCondiciones de selección de prueba

• Condiciones de salida de iteraciónCondiciones de salida de iteración

• Probar primer y último elementos de arregloProbar primer y último elementos de arreglo

3838

Datos de Prueba: Casos Datos de Prueba: Casos Especiales Especiales

• Ejemplo: mejorCalEjemplo: mejorCal– Qué sucede si alguien se ausentó o la calificación no es Qué sucede si alguien se ausentó o la calificación no es

correcta (consideración especial)?correcta (consideración especial)?

input calificacionif (calificacion es “Aus” o “CE”) { output “No calificacion para este

estudiante” poner calificacion a 0 } else {

poner calificacion a valor númerico de calificacion }

3939

Datos de Entrada: Datos no Datos de Entrada: Datos no validosvalidos

• Un dato no valido esUn dato no valido es– de un tipo no correcto, ode un tipo no correcto, o– fuera del intervalo esperadofuera del intervalo esperado

• Use las características del lenguaje de programación Use las características del lenguaje de programación para asegurar el tipo correcto de datospara asegurar el tipo correcto de datos

– Ejemplo: mejorCalEjemplo: mejorCal» calificación se puede restringir a un entero calificación se puede restringir a un entero int mark;int mark;scanf(“%d”, &mark);scanf(“%d”, &mark);

4040

Datos de Prueba: Datos No Datos de Prueba: Datos No Válidos (cont)Válidos (cont)

...if ((mark < 0) or (mark > 100)){ output “Calif debe estar entre 0 y 100”}

input calificacion...poner mark a un valor numerico de

calificacion if (no puedo tener numero de

calificacion)

{ output “entrada no valida”}

4141

loop{ set mejorCal to 0 input markEntered if (end of input) break loop if ( markEntered is “Aus” or “CE” ) { output “No hay calificacion para este estudiante” } else { set mark a valor numerico de markEntered if (cannot get number from markEntered)

{ output “Invalid input” } else if ((mark < 0) or (mark > 100))

{ output “Mark tiene que estar entre 0 y 100” } else /* entrada valida! */

{ if (mark > mejorCal) poner mejorCal a mark

}}

}output “Mejor Calificacion es “, mejorCal

Algoritmo: mejorCal Algoritmo: mejorCal

mejor1

4242

Ejemplo Ejemplo

int x,y; int x,y; scanf("%d %d", &x, &y);scanf("%d %d", &x, &y);if (x > 2) if (x > 2) { { while (x > y) while (x > y) { { printf("S1,"); printf("S1,"); x--; x--; } } printf("S2,"); printf("S2,"); } } else if (x < y)else if (x < y){ { printf("S3,"); printf("S3,"); }}printf("S4"); printf("S4");

SI NOx>2?

Input x,y

NO

output S2

x<y?

output S4

SI

output S3

NO

SI

x>y?

output S1

decremento x

4343

Ejemplo (cont) Ejemplo (cont)

int x,y; int x,y; scanf("%d %d", &x, &y);scanf("%d %d", &x, &y);if (x > 2) if (x > 2) { { while (x > y) while (x > y) { { printf("S1,"); printf("S1,"); x--; x--; } } printf("S2,"); printf("S2,"); } } elseelse if (x < y) if (x < y){ { printf("S3,"); printf("S3,"); }}printf("S4"); printf("S4");

SI NOx>2?

Input x,y

4444

int x,y; int x,y; scanf("%d %d", &x, &y);scanf("%d %d", &x, &y);if (x > 2) if (x > 2) { { while (x > y) while (x > y) { { printf("S1,"); printf("S1,"); x--; x--; } } printf("S2,");printf("S2,"); else if (x < y)else if (x < y){ { printf("S3,"); printf("S3,"); }}printf("S4"); printf("S4");

SI NOx>2?

Input x,y

SI

x>y?

output S1

decremento x


4545

int x,y; int x,y; scanf("%d %d", &x, &y);scanf("%d %d", &x, &y);if (x > 2) if (x > 2) { { while (x > y) while (x > y) { { printf("S1,"); printf("S1,"); x--; x--; } } printf("S2,");printf("S2,"); } } else else if (x < y)if (x < y){ { printf("S3,"); printf("S3,"); }}printf("S4"); printf("S4");

SI NOx>2?

Input x,y

x<y?

output S4

SI

output S3

NO

SI

x>y?

output S1

decremento x


4646

int x,y; int x,y; scanf("%d %d", &x, &y);scanf("%d %d", &x, &y);if (x > 2) if (x > 2) { { while (x > y) while (x > y) { { printf("S1,"); printf("S1,"); x--; x--; } } printf("S2,");printf("S2,"); } } else if (x < y)else if (x < y){ { printf("S3,"); printf("S3,"); }}printf("S4");printf("S4");

SI NOx>2?

Input x,y

NO

output S2

x<y?

output S4

SI

output S3

NO

SI

x>y?

output S1

decremento x

Ejemplo (cont)Ejemplo (cont)

4747

Ejemplo (cont): Datos Válidos Ejemplo (cont): Datos Válidos

• Qué líneas del código indican los datos válidos?Qué líneas del código indican los datos válidos?

int x,y;

scanf("%d %d\n", &x, &y);

• Datos Válidos son cualquier entero:–positivo, –negativo, o–cero

4848

Ejemplo (cont): Datos de prueba Ejemplo (cont): Datos de prueba para todos los caminos lógicospara todos los caminos lógicos

• Qúe hacemos para Qúe hacemos para cada input?cada input?

int x,y; scanf("%d %d", &x, &y);if (x > 2) { while (x > y) { printf("S1,"); x--; } printf("S2,"); } else if (x < y){ printf("S3,"); }printf("S4");

Qué decimos acerca de la salida ?

S4 debe ser la salida al final de cada vez

4949

int x,y; scanf("%d %d", &x, &y); if (x > 2) { while (x > y) { printf("S1,"); x--; } printf("S2,"); } else if (x < y){ printf("S3,"); }printf("S4");

Ejemplo (cont): Datos de prueba Ejemplo (cont): Datos de prueba para todos los caminos lógicospara todos los caminos lógicos

SI

SI NOx>2?

Input x,y

NO

output S2

x<y?

output S4

output S3

NO

SI

x>y?

output S1

decremento x

HACER: Probar todos los caminos desde “Input” a “Salida S4”

5050

Ejemplo (cont): Puntos elegidos Ejemplo (cont): Puntos elegidos

SI NOx>2?

Input x,y

NO

output S2

x<y?

output S4

SIoutput S3

NO

SI

x>y?

output S1

decremento x

Trayectorias se determinan por puntos elegidos

5151


• Cuáles son los puntos Cuáles son los puntos elegidos de nivel más elegidos de nivel más alto?alto?

int x,y; scanf("%d %d", &x, &y); if (x > 2){ while (x > y) { printf("S1,"); x--; } printf("S2,"); } else if (x < y){ printf("S3,"); }printf("S4");

5252


SI

SI NOx>2?

Input x,y

NO

output S2

x<y?

output S4

output S3

NO

SI

x>y?

output S1

decremento x

int x,y; int x,y; scanf("%d %d", &x, &y); scanf("%d %d", &x, &y); if (x > 2)if (x > 2){ { while (x > y) while (x > y) { { printf("S1,"); printf("S1,"); x--; x--; } } printf("S2,");printf("S2,"); } } else else if (x < y)if (x < y){ { printf("S3,"); printf("S3,"); }}printf("S4");printf("S4");

5353


Datos de Prueba Caso 1: NO (x>2), NO (x<y)

Output: S4

Valores específicos: x==2, y == 2

SI NOx>2?

Input x,y

NO

output S2

x<y?

output S4

SIoutput S3

NO

SI

x>y?

output S1

decremento x

5454


Datos Prueba Caso 2: NOT (x>2), x<y

Output: S3, S4

Valores espcíficos: x==2, y == 3

SI NOx>2?

Input x,y

NO

output S2

x<y?

output S4

SIoutput S3

NO

SI

x>y?

output S1

decremento x

5555


int x,y; scanf("%d %d", &x, &y); if (x > 2) { while (x > y) { printf("S1,"); x--; } printf("S2,"); } else if (x < y){ printf("S3,"); }printf("S4");

SI NOx>2?

Input x,y

NO

output S2

x<y?

output S4

SIoutput S3

NO

SI

x>y?

output S1

decremento x

5656


Datos de prueba Caso 3(cuerpo ciclo no ejecutado):

x > 2, NOT(x > y)

Output: S2, S4


SI NOx>2?

Input x,y

NO

output S2

x<y?

output S4

SIoutput S3

NO

SI

x>y?

output S1

decremento x

5757


Datos de prueba Caso 4(ejecución cuerpo de ciclo):

x > 2, x > y

Output: S1, S2, S4


SI NOx>2?

entrada x,y

NO

output S2

x<y?

output S4

SIoutput S3

NO

SI

x>y?

output S1

decremento x

5858

Notas sobre ciclos de prueba Notas sobre ciclos de prueba

• Es posible que un ciclo nunca termine?Es posible que un ciclo nunca termine?– sólo si el algoritmo es incorrectosólo si el algoritmo es incorrecto

• Ejemplo:Ejemplo:

while (x > y) { printf("S1,"); x++; }

while (x > y) { printf("S1,"); x--; }

5959

Ejercicio: Cambiando el Algoritmo Ejercicio: Cambiando el Algoritmo

/* Paso 1 */ while (x > 0){ /* Paso 2 */ if (y == 2) { /* Paso 2a */ } else { /* Paso 2b */ } /* Paso 3 */ } /* Paso 4 */

• Cómo asegurar que el ciclo Cómo asegurar que el ciclo siempresiempre termine? termine?

dado un conjunto de datos de prueba:

válidosválidos límiteno válidos

6060

Sumario Sumario

• Probar es una parte importante de proceso de Probar es una parte importante de proceso de desarrollo del softwaredesarrollo del software

• Considerar todos los casos de datos de prueba puede Considerar todos los casos de datos de prueba puede conducir a un cambio en el algoritmoconducir a un cambio en el algoritmo

• Los Diagramas de Flujo se pueden usar para diseñar Los Diagramas de Flujo se pueden usar para diseñar el conjunto de datos de pruebael conjunto de datos de prueba

1 Algoritmos y Programación Primavera de 2006 Javier M. Hernández FCFM Lectura 5: Diagramas de...

Documents

Transcript of 1 Algoritmos y Programación Primavera de 2006 Javier M. Hernández FCFM Lectura 5: Diagramas de...