universo

A nuestros companeros y alumnos

Indice

Presentacion xix

Tema I Algoritmos e introduccion a Pascal 1

Captulo 1 Problemas, algoritmos y programas 3

1.1 Solucion de problemas mediante programas . . . . . . . . . . . . 3

1.2 Concepto de algoritmo . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2.1 Una definicion de algoritmo . . . . . . . . . . . . . . . . . 6

1.2.2 Una definicion formal de algoritmo . . . . . . . . . . . . . 8

1.3 Aspectos de interes sobre los algoritmos . . . . . . . . . . . . . . 11

1.3.1 Computabilidad . . . . . . . . . . . . . . . . . . . . . . . 11

1.3.2 Correccion de algoritmos . . . . . . . . . . . . . . . . . . 14

1.3.3 Complejidad de algoritmos . . . . . . . . . . . . . . . . . 15

1.4 Lenguajes algortmicos y de programacion . . . . . . . . . . . . . 16

1.5 Desarrollo sistematico de programas . . . . . . . . . . . . . . . . 18

1.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1.7 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1.8 Referencias bibliograficas . . . . . . . . . . . . . . . . . . . . . . 21

Captulo 2 El lenguaje de programacion Pascal 23

2.1 Introduccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.2 Otros detalles de interes . . . . . . . . . . . . . . . . . . . . . . . 24

2.3 Origen y evolucion del lenguaje Pascal . . . . . . . . . . . . . . . 24

2.4 Pascal y Turbo Pascal . . . . . . . . . . . . . . . . . . . . . . . . 25

Captulo 3 Tipos de datos basicos 27

3.1 Introduccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

viii Indice

3.2 El tipo integer . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.3 El tipo real . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.4 El tipo char . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.5 El tipo boolean . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.6 Observaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.7 El tipo de una expresion . . . . . . . . . . . . . . . . . . . . . . . 43

3.8 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

Captulo 4 Elementos basicos del lenguaje 47

4.1 Un ejemplo introductorio . . . . . . . . . . . . . . . . . . . . . . 47

4.2 Vocabulario basico . . . . . . . . . . . . . . . . . . . . . . . . . . 48

4.2.1 Constantes y variables . . . . . . . . . . . . . . . . . . . . 52

4.3 Instrucciones basicas . . . . . . . . . . . . . . . . . . . . . . . . . 52

4.3.1 Asignacion . . . . . . . . . . . . . . . . . . . . . . . . . . 52

4.3.2 Instrucciones de escritura . . . . . . . . . . . . . . . . . . 54

4.3.3 Instrucciones de lectura . . . . . . . . . . . . . . . . . . . 57

4.4 Partes de un programa . . . . . . . . . . . . . . . . . . . . . . . . 59

4.4.1 Encabezamiento . . . . . . . . . . . . . . . . . . . . . . . 59

4.4.2 Declaraciones y definiciones . . . . . . . . . . . . . . . . . 60

4.4.3 Cuerpo del programa . . . . . . . . . . . . . . . . . . . . . 62

4.4.4 Conclusion: estructura general de un programa . . . . . . 63

4.5 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

Captulo 5 Primeros programas completos 67

5.1 Algunos programas sencillos . . . . . . . . . . . . . . . . . . . . . 68

5.1.1 Dibujo de la letra C . . . . . . . . . . . . . . . . . . . . 68

5.1.2 Suma de dos numeros . . . . . . . . . . . . . . . . . . . . 69

5.2 Programas claros programas de calidad . . . . . . . . . . . . . 695.3 Desarrollo descendente de programas . . . . . . . . . . . . . . . . 71

5.4 Desarrollo de programas correctos . . . . . . . . . . . . . . . . . 73

5.4.1 Estado de los computos . . . . . . . . . . . . . . . . . . . 73

5.4.2 Desarrollo descendente con especificaciones . . . . . . . . 78

5.5 Observaciones finales . . . . . . . . . . . . . . . . . . . . . . . . . 79

5.6 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

Indice ix

Tema II Programacion estructurada 83

Captulo 6 Instrucciones estructuradas 85

6.1 Composicion de instrucciones . . . . . . . . . . . . . . . . . . . . 86

6.2 Instrucciones de seleccion . . . . . . . . . . . . . . . . . . . . . . 88

6.2.1 La instruccion if-then-else . . . . . . . . . . . . . . . . . 88

6.2.2 La instruccion case . . . . . . . . . . . . . . . . . . . . . 92

6.3 Instrucciones de iteracion . . . . . . . . . . . . . . . . . . . . . . 94

6.3.1 La instruccion while . . . . . . . . . . . . . . . . . . . . . 94

6.3.2 La instruccion repeat . . . . . . . . . . . . . . . . . . . . 98

6.3.3 La instruccion for . . . . . . . . . . . . . . . . . . . . . . 100

6.4 Diseno y desarrollo de bucles . . . . . . . . . . . . . . . . . . . . 103

6.4.1 Eleccion de instrucciones iterativas . . . . . . . . . . . . . 103

6.4.2 Terminacion de un bucle . . . . . . . . . . . . . . . . . . . 105

6.4.3 Uso correcto de instrucciones estructuradas . . . . . . . . 106

6.5 Dos metodos numericos iterativos . . . . . . . . . . . . . . . . . . 113

6.5.1 Metodo de biparticion . . . . . . . . . . . . . . . . . . . . 113

6.5.2 Metodo de Newton-Raphson . . . . . . . . . . . . . . . . 115

6.5.3 Inversion de funciones . . . . . . . . . . . . . . . . . . . . 117

6.6 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

Captulo 7 Programacion estructurada 123

7.1 Introduccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

7.2 Aspectos teoricos . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

7.2.1 Programas y diagramas de flujo . . . . . . . . . . . . . . . 125

7.2.2 Diagramas y diagramas propios . . . . . . . . . . . . . . . 126

7.2.3 Diagramas BJ (de Bohm y Jacopini) . . . . . . . . . . . . 130

7.2.4 Equivalencia de diagramas . . . . . . . . . . . . . . . . . . 135

7.2.5 Teoremas de la programacion estructurada . . . . . . . . 137

7.2.6 Recapitulacion . . . . . . . . . . . . . . . . . . . . . . . . 138

7.3 Aspectos metodologicos . . . . . . . . . . . . . . . . . . . . . . . 139

7.3.1 Seudocodigo . . . . . . . . . . . . . . . . . . . . . . . . . . 139

7.3.2 Diseno descendente . . . . . . . . . . . . . . . . . . . . . . 141

7.4 Refinamiento correcto de programas con instruccionesestructuradas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146

x Indice

7.4.1 Un ejemplo detallado . . . . . . . . . . . . . . . . . . . . 147

7.4.2 Recapitulacion . . . . . . . . . . . . . . . . . . . . . . . . 150

7.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151

7.6 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151


Tema III Subprogramas 155

Captulo 8 Procedimientos y funciones 157

8.1 Introduccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158

8.2 Subprogramas con parametros . . . . . . . . . . . . . . . . . . . . 162

8.2.1 Descripcion de un subprograma con parametros . . . . . . 162

8.2.2 Parametros formales y reales . . . . . . . . . . . . . . . . 165

8.2.3 Mecanismos de paso de parametros . . . . . . . . . . . . . 165

8.2.4 Consistencia entre definicion y llamada . . . . . . . . . . 168

8.3 Estructura sintactica de un subprograma . . . . . . . . . . . . . . 169

8.4 Funcionamiento de una llamada . . . . . . . . . . . . . . . . . . . 170

8.5 Ambito y visibilidad de los identificadores . . . . . . . . . . . . . 174

8.5.1 Tipos de identificadores segun su ambito . . . . . . . . . . 174

8.5.2 Estructura de bloques . . . . . . . . . . . . . . . . . . . . 175

8.5.3 Criterios de localidad . . . . . . . . . . . . . . . . . . . . 181

8.5.4 Efectos laterales . . . . . . . . . . . . . . . . . . . . . . . 181

8.6 Otras recomendaciones sobre el uso de parametros . . . . . . . . 183

8.6.1 Parametros por valor y por referencia . . . . . . . . . . . 183

8.6.2 Parametros por referencia y funciones . . . . . . . . . . . 183

8.6.3 Funciones con resultados multiples . . . . . . . . . . . . . 184

8.7 Desarrollo correcto de subprogramas . . . . . . . . . . . . . . . . 184

8.8 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186

Captulo 9 Aspectos metodologicos de la programacion consubprogramas 189

9.1 Introduccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189

9.2 Un ejemplo de referencia . . . . . . . . . . . . . . . . . . . . . . . 190

9.3 Metodologa de la programacion con subprogramas . . . . . . . . 192

9.3.1 Diseno descendente con subprogramas . . . . . . . . . . . 193

Indice xi

9.3.2 Programa principal y subprogramas . . . . . . . . . . . . 194

9.3.3 Documentacion de los subprogramas . . . . . . . . . . . . 195

9.3.4 Tamano de los subprogramas . . . . . . . . . . . . . . . . 196

9.3.5 Refinamiento con subprogramas y con instruccionesestructuradas . . . . . . . . . . . . . . . . . . . . . . . . . 197

9.4 Estructura jerarquica de los subprogramas . . . . . . . . . . . . . 199

9.5 Ventajas de la programacion con subprogramas . . . . . . . . . . 201

9.6 Un ejemplo detallado: representacion de funciones . . . . . . . . 203

9.7 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207

Captulo 10 Introduccion a la recursion 211

10.1 Un ejemplo de referencia . . . . . . . . . . . . . . . . . . . . . . . 212

10.2 Conceptos basicos . . . . . . . . . . . . . . . . . . . . . . . . . . 213

10.3 Otros ejemplos recursivos . . . . . . . . . . . . . . . . . . . . . . 216

10.3.1 La sucesion de Fibonacci . . . . . . . . . . . . . . . . . . 216

10.3.2 Torres de Hanoi . . . . . . . . . . . . . . . . . . . . . . . 216

10.3.3 Funcion de Ackermann . . . . . . . . . . . . . . . . . . . . 219

10.4 Correccion de subprogramas recursivos . . . . . . . . . . . . . . . 219

10.4.1 Principios de induccion . . . . . . . . . . . . . . . . . . . 220

10.5 Recursion mutua . . . . . . . . . . . . . . . . . . . . . . . . . . . 222

10.6 Recursion e iteracion . . . . . . . . . . . . . . . . . . . . . . . . . 226

10.7 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227


Tema IV Tipos de datos definidos por el programador 231

Captulo 11 Tipos de datos simples y compuestos 233

11.1 Tipos ordinales definidos por el programador . . . . . . . . . . . 234

11.1.1 Tipos enumerados . . . . . . . . . . . . . . . . . . . . . . 235

11.1.2 Tipo subrango . . . . . . . . . . . . . . . . . . . . . . . . 238

11.2 Definicion de tipos . . . . . . . . . . . . . . . . . . . . . . . . . . 240

11.2.1 Observaciones sobre la definicion de tipos . . . . . . . . . 242

11.3 Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244

11.3.1 Operaciones sobre el tipo conjunto . . . . . . . . . . . . . 245

11.3.2 Observaciones sobre el tipo conjunto . . . . . . . . . . . . 247

xii Indice

11.3.3 Un ejemplo de aplicacion . . . . . . . . . . . . . . . . . . 248

11.4 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250

Captulo 12 Arrays 253

12.1 Descripcion del tipo de datos array . . . . . . . . . . . . . . . . . 253

12.1.1 Operaciones del tipo array y acceso a sus componentes . . 257

12.1.2 Caractersticas generales de un array . . . . . . . . . . . . 260

12.2 Vectores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261

12.3 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263

12.4 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268

Captulo 13 Registros 271

13.1 Descripcion del tipo de datos registro . . . . . . . . . . . . . . . . 271

13.1.1 Manejo de registros: acceso a componentes y operaciones . 273

13.1.2 Registros con variantes . . . . . . . . . . . . . . . . . . . . 276

13.2 Arrays de registros y registros de arrays . . . . . . . . . . . . . . 279

13.3 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282

Captulo 14 Archivos 285

14.1 Descripcion del tipo de datos archivo . . . . . . . . . . . . . . . . 285

14.2 Manejo de archivos en Pascal . . . . . . . . . . . . . . . . . . . . 286

14.2.1 Operaciones con archivos . . . . . . . . . . . . . . . . . . 288

14.3 Archivos de texto . . . . . . . . . . . . . . . . . . . . . . . . . . . 294

14.4 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298

Captulo 15 Algoritmos de busqueda y ordenacion 301

15.1 Algoritmos de busqueda en arrays . . . . . . . . . . . . . . . . . 301

15.1.1 Busqueda secuencial . . . . . . . . . . . . . . . . . . . . . 302

15.1.2 Busqueda secuencial ordenada . . . . . . . . . . . . . . . 304

15.1.3 Busqueda binaria . . . . . . . . . . . . . . . . . . . . . . . 304

15.2 Ordenacion de arrays . . . . . . . . . . . . . . . . . . . . . . . . . 306

15.2.1 Seleccion directa . . . . . . . . . . . . . . . . . . . . . . . 307

15.2.2 Insercion directa . . . . . . . . . . . . . . . . . . . . . . . 309

15.2.3 Intercambio directo . . . . . . . . . . . . . . . . . . . . . . 310

15.2.4 Ordenacion rapida (Quick Sort) . . . . . . . . . . . . . . 312

15.2.5 Ordenacion por mezcla (Merge Sort) . . . . . . . . . . . . 316

Indice xiii

15.2.6 Vectores paralelos . . . . . . . . . . . . . . . . . . . . . . 318

15.3 Algoritmos de busqueda en archivos secuenciales . . . . . . . . . 320

15.3.1 Busqueda en archivos arbitrarios . . . . . . . . . . . . . . 321

15.3.2 Busqueda en archivos ordenados . . . . . . . . . . . . . . 321

15.4 Mezcla y ordenacion de archivos secuenciales . . . . . . . . . . . 322

15.5 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329


Tema V Memoria dinamica 333

Captulo 16 Punteros 335

16.1 Introduccion al uso de punteros . . . . . . . . . . . . . . . . . . . 336

16.1.1 Definicion y declaracion de punteros . . . . . . . . . . . . 337

16.1.2 Generacion y destruccion de variables dinamicas . . . . . 338

16.1.3 Operaciones basicas con datos apuntados . . . . . . . . . 339

16.1.4 Operaciones basicas con punteros . . . . . . . . . . . . . . 341

16.1.5 El valor nil . . . . . . . . . . . . . . . . . . . . . . . . . . 343

16.2 Aplicaciones no recursivas de los punteros . . . . . . . . . . . . . 344

16.2.1 Asignacion de objetos no simples . . . . . . . . . . . . . . 345

16.2.2 Funciones de resultado no simple . . . . . . . . . . . . . . 346

16.3 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348

Captulo 17 Estructuras de datos recursivas 351

17.1 Estructuras recursivas lineales: las listas enlazadas . . . . . . . . 351

17.1.1 Una definicion del tipo lista . . . . . . . . . . . . . . . . . 352

17.1.2 Insercion de elementos . . . . . . . . . . . . . . . . . . . . 353

17.1.3 Eliminacion de elementos . . . . . . . . . . . . . . . . . . 355

17.1.4 Algunas funciones recursivas . . . . . . . . . . . . . . . . 355

17.1.5 Otras operaciones sobre listas . . . . . . . . . . . . . . . . 358

17.2 Pilas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362

17.2.1 Definicion de una pila como lista enlazada . . . . . . . . . 363

17.2.2 Operaciones basicas sobre las pilas . . . . . . . . . . . . . 363

17.2.3 Aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . 365

17.3 Colas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370

17.3.1 Definicion del tipo cola . . . . . . . . . . . . . . . . . . . 371

xiv Indice

17.3.2 Operaciones basicas . . . . . . . . . . . . . . . . . . . . . 371

17.3.3 Aplicacion: gestion de la caja de un supermercado . . . . 374

17.4 Arboles binarios . . . . . . . . . . . . . . . . . . . . . . . . . . . 376

17.4.1 Recorrido de un arbol binario . . . . . . . . . . . . . . . . 378

17.4.2 Arboles de busqueda . . . . . . . . . . . . . . . . . . . . . 379

17.4.3 Aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . 383

17.5 Otras estructuras dinamicas de datos . . . . . . . . . . . . . . . . 387

17.6 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389


Tema VI Aspectos avanzados de programacion 393

Captulo 18 Complejidad algortmica 395

18.1 Conceptos basicos . . . . . . . . . . . . . . . . . . . . . . . . . . 396

18.2 Medidas del comportamiento asintotico . . . . . . . . . . . . . . 402

18.2.1 Comportamiento asintotico . . . . . . . . . . . . . . . . . 402

18.2.2 Notacion O mayuscula (una cota superior) . . . . . . . . 404

18.2.3 Notacion mayuscula (una cota inferior) . . . . . . . . . 405

18.2.4 Notacion mayuscula (orden de una funcion) . . . . . . 405

18.2.5 Propiedades de O, y . . . . . . . . . . . . . . . . . . 406

18.2.6 Jerarqua de ordenes de frecuente aparicion . . . . . . . . 407

18.3 Reglas practicas para hallar el coste de un programa . . . . . . . 408

18.3.1 Tiempo empleado . . . . . . . . . . . . . . . . . . . . . . 408

18.3.2 Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . 411

18.3.3 Espacio de memoria empleado . . . . . . . . . . . . . . . 417

18.4 Utiles matematicos . . . . . . . . . . . . . . . . . . . . . . . . . . 418

18.4.1 Formulas con sumatorios . . . . . . . . . . . . . . . . . . 419

18.4.2 Sucesiones de recurrencia lineales de primer orden . . . . 419

18.4.3 Sucesiones de recurrencia de orden superior . . . . . . . . 421

18.5 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422


Captulo 19 Tipos abstractos de datos 427

19.1 Introduccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428

19.2 Un ejemplo completo . . . . . . . . . . . . . . . . . . . . . . . . . 429

Indice xv

19.2.1 Desarrollo de programas con tipos concretos de datos . . 430

19.2.2 Desarrollo de programas con tipos abstractos de datos . . 431

19.2.3 Desarrollo de tipos abstractos de datos . . . . . . . . . . . 434

19.3 Metodologa de la programacion de TADs . . . . . . . . . . . . . 440

19.3.1 Especificacion de tipos abstractos de datos . . . . . . . . 440

19.3.2 Implementacion de tipos abstractos de datos . . . . . . . 441

19.3.3 Correccion de tipos abstractos de datos . . . . . . . . . . 443

19.4 Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446

19.5 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447


Captulo 20 Esquemas algortmicos fundamentales 449

20.1 Algoritmos devoradores . . . . . . . . . . . . . . . . . . . . . . . 450

20.1.1 Descripcion . . . . . . . . . . . . . . . . . . . . . . . . . . 450

20.1.2 Adecuacion al problema . . . . . . . . . . . . . . . . . . . 451

20.1.3 Otros problemas resueltos vorazmente . . . . . . . . . . . 452

20.2 Divide y venceras . . . . . . . . . . . . . . . . . . . . . . . . . . . 453

20.2.1 Equilibrado de los subproblemas . . . . . . . . . . . . . . 454

20.3 Programacion dinamica . . . . . . . . . . . . . . . . . . . . . . . 455

20.3.1 Problemas de programacion dinamica . . . . . . . . . . . 455

20.3.2 Mejora de este esquema . . . . . . . . . . . . . . . . . . . 457

20.3.3 Formulacion de problemas de programacion dinamica . . 460

20.4 Vuelta atras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462

20.4.1 Mejora del esquema de vuelta atras . . . . . . . . . . . . 466

20.5 Anexo: algoritmos probabilistas . . . . . . . . . . . . . . . . . . . 468

20.5.1 Busqueda de una solucion aproximada . . . . . . . . . . . 468

20.5.2 Busqueda de una solucion probablemente correcta . . . . 469

20.6 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470


Apendices 475

Apendice A Aspectos complementarios de la programacion 477

A.1 Subprogramas como parametros . . . . . . . . . . . . . . . . . . . 477

A.1.1 Ejemplo 1: derivada . . . . . . . . . . . . . . . . . . . . . 479

xvi Indice

A.1.2 Ejemplo 2: biparticion . . . . . . . . . . . . . . . . . . . . 480

A.1.3 Ejemplo 3: transformacion de listas . . . . . . . . . . . . 482

A.2 Variables aleatorias . . . . . . . . . . . . . . . . . . . . . . . . . . 482

A.2.1 Generacion de numeros aleatorios en Turbo Pascal . . . . 483

A.2.2 Simulacion de variables aleatorias . . . . . . . . . . . . . . 484

A.2.3 Ejemplos de aplicacion . . . . . . . . . . . . . . . . . . . . 486

A.3 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488

A.4 Referencias bibliograficas . . . . . . . . . . . . . . . . . . . . . . 490

Apendice B El lenguaje Turbo Pascal 491

B.1 Elementos lexicos . . . . . . . . . . . . . . . . . . . . . . . . . . . 492

B.2 Estructura del programa . . . . . . . . . . . . . . . . . . . . . . . 492

B.3 Datos numericos enteros . . . . . . . . . . . . . . . . . . . . . . . 492

B.4 Datos numericos reales . . . . . . . . . . . . . . . . . . . . . . . . 493

B.5 Cadenas de caracteres . . . . . . . . . . . . . . . . . . . . . . . . 494

B.5.1 Declaracion de cadenas . . . . . . . . . . . . . . . . . . . 494

B.5.2 Operadores de cadenas . . . . . . . . . . . . . . . . . . . . 495

B.5.3 Funciones de cadenas . . . . . . . . . . . . . . . . . . . . 496

B.5.4 Procedimientos de cadenas . . . . . . . . . . . . . . . . . 496

B.6 Tipos de datos estructurados . . . . . . . . . . . . . . . . . . . . 498

B.7 Instrucciones estructuradas . . . . . . . . . . . . . . . . . . . . . 498

B.8 Paso de subprogramas como parametros . . . . . . . . . . . . . . 499

B.9 Archivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 500

B.10 Memoria dinamica . . . . . . . . . . . . . . . . . . . . . . . . . . 501

B.11 Unidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501

B.11.1 Unidades predefinidas de Turbo Pascal . . . . . . . . . . . 502

B.11.2 Unidades definidas por el usuario . . . . . . . . . . . . . . 503

B.11.3 Modularidad incompleta de Turbo Pascal . . . . . . . . . 505

Apendice C El entorno integrado de desarrollo 507

C.1 Descripcion del entorno . . . . . . . . . . . . . . . . . . . . . . . 507

C.2 Desarrollo completo de un programa en Turbo Pascal . . . . . . 508

C.2.1 Arranque del entorno . . . . . . . . . . . . . . . . . . . . 508

C.2.2 Edicion del programa fuente . . . . . . . . . . . . . . . . . 510

C.2.3 Grabar el programa fuente y seguir editando . . . . . . . 510

Indice xvii

C.2.4 Compilacion . . . . . . . . . . . . . . . . . . . . . . . . . 512

C.2.5 Ejecucion . . . . . . . . . . . . . . . . . . . . . . . . . . . 514

C.2.6 Depuracion . . . . . . . . . . . . . . . . . . . . . . . . . . 514

C.2.7 Salida de Turbo Pascal . . . . . . . . . . . . . . . . . . . . 516

C.3 Otros menus y opciones . . . . . . . . . . . . . . . . . . . . . . . 517

C.3.1 Search (Busqueda) . . . . . . . . . . . . . . . . . . . . . . 517

C.3.2 Tools (Herramientas) . . . . . . . . . . . . . . . . . . . . . 517

C.3.3 Options (Opciones) . . . . . . . . . . . . . . . . . . . . . . 517

C.3.4 Window (Ventana) . . . . . . . . . . . . . . . . . . . . . . 519

C.3.5 Help (Ayuda) . . . . . . . . . . . . . . . . . . . . . . . . . 519

C.4 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519

C.5 Referencias bibliograficas . . . . . . . . . . . . . . . . . . . . . . 520

Bibliografa 521

Indice alfabetico 527

Presentacion

Este libro trata sobre metodos de resolucion de problemas mediante el desa-rrollo de algoritmos y estructuras de datos, desde el principio y paso a paso, ysu materializacion en programas de computador.

Desde luego, no es el primer libro sobre este tema; de hecho, ha habidoen los ultimos quince anos un gran aluvion de textos sobre algoritmos y sobreprogramacion. La razon para ello ha sido sin lugar a dudas doble: por unlado, la difusion que estos temas han tenido y siguen teniendo, integrandoseen los estudios mas diversos; por otro, la evolucion que esta experimentando eldesarrollo de algoritmos y programas, pasando de ser un arte (reinventado porcada programador a base de tecnicas personales, estrechamente vinculadas consu lenguaje de programacion) a una actividad mas cientfica, metodologica ydisciplinada.

Por consiguiente, resulta necesario aclarar cual es el enfoque adoptado en estelibro. Examinando la bibliografa existente actualmente sobre programacion aun nivel introductorio permite afirmar las siguientes conclusiones:

Una parte importante de los libros existentes han adoptado un enfoquepractico puro, no metodologico, que es el mas tradicional, y aun subsisteen demasiados libros. Se confunde la ensenanza de la programacion conla de un lenguaje concreto, ofreciendo muchas veces un mero manualde referencia del lenguaje elegido. Bajo el atractivo de los llamativosresultados inmediatos (programas que funcionan), este enfoque ignora labase conceptual y metodologica necesaria, y propicia los peores habitos deprogramacion, que son ademas difciles de erradicar.

Otra postura extrema se centra en el analisis y desarrollo de solucionesalgortmicas puras, de forma independiente de cualquier lenguaje de pro-gramacion. Esta independencia permite ignorar las peculiaridades de loslenguajes reales, yendo a los conceptos; sin embargo, esa independencia delos lenguajes de programacion es a nuestro entender innecesaria e inconve-niente en los primeros pasos, ya que obliga al aprendiz de la programaciona estudiar aparte los detalles concretos del lenguaje de programacion conque necesariamente debe desarrollar sus practicas.

xx Presentacion

En cambio, encontramos este enfoque interesante en niveles superiores dela ensenanza de la programacion, donde interesa concentrarse en los con-ceptos, mas difciles y donde ya no supone obstaculo alguno expresar lasideas en cualquier lenguaje de programacion.

El enfoque adoptado en este libro recoge ambos aspectos: por un lado, viene acubrir la necesidad de un enfoque metodologico en el aprendizaje y en el ejerciciode la programacion, pero tambien la necesidad de experimentar con programasconcretos, expresarlos en un lenguaje real y hacerlos funcionar con un traduc-tor concreto. En resumen, intentamos compaginar las ventajas de los enfoquesanteriores, presentando la base conceptual y metodologica necesaria para desa-rrollar los algoritmos de forma razonada y disciplinada, sin olvidar por ello laconveniencia de expresarlos en un lenguaje de programacion, materializandolosy experimentando con ellos, y que el lector ha de ser instruido tambien en estatarea.

En relacion con el enfoque metodologico que se impone actualmente, se con-sidera necesario atender a la correccion de los programas. El tratamiento quese le da en la literatura ha llevado nuevamente a dos posturas artificialmenteextremas:

Algunos autores ignoran completamente el estudio de la correccion, con-tentandose con algunas comprobaciones para deducir que un programa escorrecto.

En cambio, otros adoptan un tratamiento exhaustivo, utilizando tecnicasformales de especificacion o verificacion.

A nuestro entender, es incuestionable la importancia de garantizar que losprogramas desarrollados funcionaran de la forma deseada. Sin embargo, la ve-rificacion formal de los programas de cierto tamano es impracticable. Por ello,asumimos de nuevo una posicion intermedia y realista consistente en los siguien-tes planteamientos:

Plantear el desarrollo de programas correctos con el empleo de tecnicassemiformales.

Limitar el estudio de la correccion a los elementos que resulten delicados,bien por su dificultad o por su novedad.

Atender a la correccion de los algoritmos durante su desarrollo en lugar dea posteriori. Esta idea resulta ser una ayuda esencial en el aprendizaje dela programacion.

Presentacion xxi

En resumidas cuentas, este libro va dirigido a aquellos que desean introdu-cirse en la programacion, con una base solida, con una buena metodoga dediseno y desarrollo de programas correctos y con habitos disciplinados desde unaperspectiva realista y pragmatica. Se presentan las tecnicas con un cierto ni-vel de abstraccion para identificar los conceptos esenciales e independientes dellenguaje de programacion empleado, y al mismo tiempo se aterriza expresandoestas tecnicas en un lenguaje concreto.

El lenguaje escogido para estas implementaciones ha sido Pascal. Esta elec-cion se debe a que este lenguaje es simple y tiene una sintaxis sencilla, quehace que sea facil de aprender, y al mismo tiempo es lo bastante completo comopara plasmar las diferentes tecnicas y metodos necesarios en programas de com-plejidad media-alta. Esto lo hace una herramienta pedagogica idonea para elaprendizaje de la programacion. A todo esto hay que sumar las numerosas im-plementaciones existentes y su accesibilidad, as como su evolucion y continuapuesta al da para permitir tecnicas de programacion actuales (por ejemplo, mo-dular u orientada a los objetos) y su gran difusion y aceptacion en el ambitoacademico.

Organizacion del libro

El libro esta estructurado en siete partes. En cada una de ellas se estudianlas tecnicas y mecanismos nuevos, conceptualmente primero, detallando luegosu tratamiento en Pascal y, finalmente, compaginando ambas facetas con el as-pecto metodologico. Cada tema se ha dividido en varios captulos para evitaruna excesiva fragmentacion. En cada captulo se ha incluido una lista de ejerci-cios propuestos de dificultad aproximadamente creciente. Al final de cada temase desarrolla un ejemplo completo pensado para mostrar a la vez los aspectosmas destacados del mismo, as como unas pocas referencias comentadas que sesugieren como lecturas complementarias o de consulta.

Contenido

El contenido se ha seleccionado partiendo de las directrices senaladas en[DCG+89] y [Tur91]. Incluye los contenidos cursos CS1 y CS2 [GT86, KSW85]salvo los aspectos de organizacion de computadores, que se estudian en [PAO94],de los mismos autores que este libro.

En el primer tema se presentan, entre otros, los conceptos esenciales de algo-ritmo, dato y programa. Se introduce el lenguaje Pascal y la estructura de losprogramas escritos en el, as como los elementos basicos del lenguaje. Se incluyen

xxii Presentacion

algunos programas sencillos, y se adelantan la tecnica descendente de diseno deprogramas y algunos apuntes sobre la correccion.

El segundo tema se dedica a la programacion estructurada. Se pone espe-cial enfasis en el diseno descendente o por refinamientos sucesivos partiendo deespecificaciones escritas en pseudocodigo, y se muestra como compaginar estatecnica con la derivacion de programas correctos.

En el tercer tema se estudian los subprogramas. Al igual que en el temaanterior, se detalla como enfocar la correccion en el uso de esta tecnica. Seconcluye con un captulo de introduccion a la recursion.

En la mayora de los programas no basta con los tipos de datos basicos, sinoque es necesario que el programador defina otros mas complejos. A ello se dedicael cuarto tema.

El quinto tema estudia las tecnicas propias de la gestion de memoria dinamica.Se justifica su necesidad, y se presenta su principal aplicacion, que es la definicionde estructuras de datos recursivas.

El sexto tema introduce tres aspectos avanzados: la programacion con tiposabstractos de datos, el coste de los algoritmos y los principales esquemas dediseno de algoritmos. Aunque, ciertamente, su estudio en profundidad rebasa unprimer curso, es frecuente introducir o siquiera mencionar sus ideas basicas.Por supuesto, siempre es altamente recomendable consultar otras referencias(nosotros mismos las seleccionamos para cada tema), pero tambien es ciertoque el alumno se ve obligado con frecuencia a usar varios textos basicos paracubrir diferentes partes de la materia. Justamente, estos ultimos captulos seincluyen para que el lector interesado se pueda asomar a ellos sin verse obligadoa consultar los captulos introductorios de otros libros.

Finalmente se incluyen tres apendices: en el primero se introducen un parde aspectos complementarios para un primer curso de programacion (el pasode subprogramas como parametros y el uso de variables aleatorias); el segundoes un prontuario de uso del entorno integrado de desarrollo Turbo Pascal; y eltercero indica algunos detalles de Turbo Pascal en que se separa del estandar,pero que son de uso frecuente.

Notacion empleada

En la lectura de este texto se encontraran fragmentos escritos en distintoslenguajes:

En castellano puro, donde se ha usado este tipo de letra.

En Pascal, para lo que se ha elegido el teletipo, salvo las palabras reser-vadas, que van en negrita.

Presentacion xxiii

Tambien se ha empleado el teletipo para indicar las salidas y entradas dedatos, porque es el tipo de letra mas parecido al que aparece en el monitor.

En seudocodigo, que se expresa con letra cursiva.

En lenguaje matematico, en que se usan los smbolos usuales.

Otros smbolos especiales:

El espacio en blanco (vease la pagina 206); Uno o mas pasos al evaluar una expresion (vease la pagina 30) Fin de archivo (vease la pagina 57) Fin de lnea (vease la pagina 57)

Advertencia para el alumno

No existe un metodo general para resolver problemas mediante algoritmos;por ello, es de gran importancia estudiar las tecnicas de forma gradual, yendode lo facil a lo difcil y vinculandolas con situaciones ampliamente conocidas.

Nosotros pretendemos haber cumplido con este objetivo, proporcionandoejemplos de facil comprension y ejercicios a la medida de lo explicado. Y eso eslo bueno. Lo malo es que el alumno puede percibir la sensacion de comprenderlotodo a la velocidad que lee. . . y aqu reside el peligro. Porque una mera lecturadel texto, o incluso una lectura atenta, no basta para asimilarlo, adquiriendo lastecnicas necesarias para resolver otros problemas de dificultad similar a la de losplanteados. Es preciso adoptar una actitud crtica durante la lectura, trabajarminuciosamente con los problemas propuestos e incluso tatar de imaginar solu-ciones alternativas a los ejemplos dados. Y cuanto antes se acepte esa realidad,mejor que mejor.

Agradecimientos

Muchas personas han contribuido de diferentes maneras a que este libro sealo que es. En primer lugar, debemos a nuestros alumnos de estos anos su ayuda,aun sin saberlo, porque ellos han sido la razon de que emprendieramos estetrabajo, y porque sus preguntas y comentarios, da a da, tienen una respuestaen las paginas que siguen. En segundo lugar, debemos a muchos de nuestroscompaneros su aliento y apoyo, tan necesario cuando uno se enfrenta a un trabajode esta envergadura. Y por ello, lo dedicamos a ambos, alumnos y companeros.

De un modo muy especial, deseamos expresar nuestro agradecimiento a JuanFalgueras Cano, Luis Antonio Galan Corroto y Yolanda Ortega y Mallen porsu cuidadosa lectura de la primera version completa del manuscrito, y por sus

xxiv Presentacion

valiosos comentarios y sugerencias. No podemos olvidar tampoco la ayuda deManuel Enciso Garca-Oliveros en los ultimos retoques, as como su proximidady apoyo durante todo el tiempo que nos ha ocupado este trabajo.

Por ultimo, deseamos expresar nuestra gratitud y carino a Jose Luis GalanGarca, que ha dejado en este libro muchas horas.

Tema I

Algoritmos e introduccion aPascal

Captulo 1

Problemas, algoritmos y programas

1.1 Solucion de problemas mediante programas . . . . . . 3

1.2 Concepto de algoritmo . . . . . . . . . . . . . . . . . . . 5

1.3 Aspectos de interes sobre los algoritmos . . . . . . . . 11

1.4 Lenguajes algortmicos y de programacion . . . . . . . 16

1.5 Desarrollo sistematico de programas . . . . . . . . . . 18

1.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1.7 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1.8 Referencias bibliograficas . . . . . . . . . . . . . . . . . . 21

En este primer captulo se trata la resolucion de problemas por medio deun computador. Puesto que este no es mas que un mero ejecutor de tareas, esfundamental conocer un metodo de resolucion del problema en cuestion, estoes, un algoritmo. La escritura de este algoritmo como un conjunto de ordenescomprensibles por el computador es lo que se llama programa.

1.1 Solucion de problemas mediante programas

Los computadores desempenan una gran variedad de tareas, liberando asal hombre de tener que realizarlas personalmente. Para ello, es preciso ensenaral computador cual es su trabajo y como llevarlo a cabo, esto es, programarlo,

4 Captulo 1. Problemas, algoritmos y programas

dandole instrucciones precisas (programas) en un lenguaje que comprenda (Pas-cal, Modula-2, C, etc.). Una vez aprendido el programa, el computador seguiraciegamente sus instrucciones cuantas veces sea requerido.

Precisamente, la tarea de la programacion consiste en describir lo que debehacer el computador para resolver un problema concreto en un lenguaje de pro-gramacion. Sin embargo, el programa es solamente el resultado de una serie deetapas que no se pueden pasar por alto. Hablando en terminos muy amplios, seidentifican de momento las siguientes fases:

1. Analisis del problema, estableciendo con precision lo que se plantea.

2. Solucion conceptual del problema, describiendo un metodo (algoritmo) quelo resuelva.

3. Escritura del algoritmo en un lenguaje de programacion.

En la primera fase es corriente partir de un problema definido vagamente, yel analisis del mismo consiste en precisar el enunciado, identificando los datosde partida y los resultados que se desean obtener. La descripcion precisa de unproblema se llama especificacion. Con frecuencia, el lenguaje natural no bastapara lograr la precision deseada, por lo que se recurre en mayor o menor medidaa lenguajes formales, como la logica o las matematicas. Supongamos por ejemploque se plantea el problema de dividir dos numeros. En primer lugar, se necesitasaber si se trata de la division entera o de aproximar el resultado con decimalesy, en ese caso, hasta donde. Pongamos por caso que interesa la division eucldea.Una descripcion precisa debera tener en cuenta que los datos son dos enteros(llamemosles dividendo y divisor, como es usual), de los que el segundo es nonulo. El resultado es tambien un par de enteros (llamemosles cociente y resto,como siempre) tales que

dividendo = divisor cociente+ resto

Pero eso no es todo: si nos contentamos con ese enunciado, para todo par deenteros (dividendo, divisor), el par (0, dividendo) siempre es una solucion. Poreso, hay que anadir que resto debe ser ademas tal que 0 resto < divisor.

Con este pequeno ejemplo se pretende resaltar la importancia de analizarbien el problema planteado, definiendo con precision los requisitos que debenverificar los datos y las condiciones en que deben estar los resultados.

Sin embargo, en esta fase solo se ha estudiado que se desea obtener, y nocomo lograrlo. Este es el cometido de la segunda etapa: describir un metodo(algoritmo) tal que partiendo de datos apropiados lleve sistematicamente a los re-sultados descritos en la especificacion. Del concepto de algoritmo nos ocupamos

1.2. Concepto de algoritmo 5

1

Principio 2

Esta abierto elplazo de matrcula?

s 4 no 3

Esperara manana

2

Comprar impresosde matriculacion

5

Leer instrucciones.Tengo alguna duda?

s 6 no 7

Preguntar dudasen Secretara

7

Rellenar el sobrey pagar en el banco

8Entregar el sobre

9 Fin

2

4 5

3

6

987

Figura 1.1.

en el siguiente apartado. Es evidente que solo se puede confiar en un algoritmosi ha superado con exito determinado control de calidad: la primera e inexcusa-ble exigencia es que sea correcto; esto es, que resuelva el problema especificado.Cuando un problema admita varios algoritmos como solucion, convendra dispo-ner de criterios para escoger; y cuando un problema no tenga solucion, no resultasensato buscar un algoritmo para resolverlo. Estos aspectos los estudiamos en elapartado 1.3.

Finalmente, para que un computador resuelva problemas hay que escribir elalgoritmo en un lenguaje de programacion; de ello hablaremos en el apartado1.4.

1.2 Concepto de algoritmo

Los conceptos de algoritmo y de metodo son parecidos: los metodos paraefectuar procesos forman parte de las costumbres o rutinas que el hombre aprendeun da y luego repite de manera inconsciente, sin reparar ya en las acciones, massencillas, que integran el proceso (por ejemplo andar, leer o conducir). Por esoel concepto de algoritmo suele compararse a otros como metodo o rutina deacciones.

La secuencia de pasos de la figura 1.1 describe un metodo para efectuar lamatrcula en la universidad.

Sin embargo, el termino algoritmo tiene connotaciones mas formales quecualquier otro debido a su origen: se trata de una acomodacion al castellano del


nombre de Muh. ammad ibn Musa al-Jwarzm, matematico persa que popularizosu descripcion de las cuatro reglas (algoritmos) de sumar, restar, multiplicar ydividir.

1.2.1 Una definicion de algoritmo

Hablando informalmente, un algoritmo es la descripcion precisa de los pasosque nos llevan a la solucion de un problema planteado. Estos pasos son, en gene-ral, acciones u operaciones que se efectuan sobre ciertos objetos. La descripcionde un algoritmo afecta a tres partes: entrada (datos), proceso (instrucciones)y salida (resultados).1 En este sentido, un algoritmo se puede comparar a unafuncion matematica:

+ : ZZ ZZ ZZ(algoritmo) (entrada) (proceso) (salida)

Incluso en algoritmos no matematicos es facil identificar las tres partes: entra-da, proceso y salida. As ocurre, por ejemplo, en las instrucciones para hacer ladeclaracion de la renta.

Caractersticas de los algoritmos

La descripcion de algoritmo que se ha dado es algo imprecisa. Una caracte-rizacion mas completa debera incluir ademas los siguientes requisitos:

1. Precision

Un algoritmo debe expresarse de forma no ambigua. La precision afectapor igual a dos aspectos:

(a) Al orden (encadenamiento o concatenacion) de los pasos que han dellevarse a cabo.

(b) Al contenido de las mismas, pues cada paso debe saberse realizarcon toda precision, de forma automatica.

Por lo tanto, una receta de cocina puede ser considerada como un metodo,pero carece de la precision que requieren los algoritmos debido al uso deexpresiones como anadir una pizca de sal, porque que debe entenderse poruna pizca?

1Es habitual llamar datos a la entrada y resultados a la salida, aunque el concepto de datoes mas amplio, y abarca a toda la informacion que maneja un algoritmo, ya sea inicialmente o asu termino, as como tambien durante el transcurso de su utilizacion.


Principio a = 0a a a-1

b

Fin

b b+1b1 2 3 4 5

6

7

SI

NO

Figura 1.2. Diagrama de flujo de la suma lenta.

2. Determinismo

Todo algoritmo debe responder del mismo modo ante las mismas condicio-nes.

Por lo tanto, la accion de barajar un mazo de cartas no es un algoritmo,ya que es y debe ser un proceso no determinista.

3. Finitud

La descripcion de un algoritmo debe ser finita.

Un primer ejemplo

Consideremos el ejemplo que, expresado graficamente,2 aparece en la fi-gura 1.2. El algoritmo descrito tiene por objetivo sumar dos cantidades enteras.Si se anotan esas cantidades inicialmente en sendas casillas (a las que llamaremosa y b para abreviar), este metodo consiste en ir pasando de a a b una unidadcada vez, de forma que, cuando a = 0, el resultado sera el valor de b.

Vemos un ejemplo de su funcionamiento con los datos 2 y 3 en la figura 1.3.(Los numeros se han incluido para seguir mejor la evolucion de los calculos.)

Se observa que la descripcion del algoritmo que se ha dado es, en efecto,precisa (cada paso esta exento de ambiguedad, as como el orden en que se debeefectuar) y determinista (el efecto de cada paso es siempre el mismo para unosdatos concretos cualesquiera). Estas dos caractersticas son una consecuenciadel lenguaje escogido para expresar el algoritmo.

2El lenguaje empleado es el de los diagramas de flujo, que estudiaremos en el captulo 7,apartado 7.2.1. Esperamos que, debido a su sencillez, el funcionamiento de este ejemplo resultecomprensible directamente.


Posicion Datos pendientes Resultados emitidos Var a Var b

1 [2, 3] [ ] ? ?2 [3] [ ] 2 ?3 [ ] [ ] 2 34 [ ] [ ] 2 35 [ ] [ ] 1 33 [ ] [ ] 1 44 [ ] [ ] 1 45 [ ] [ ] 0 43 [ ] [ ] 0 56 [ ] [ ] 0 57 [ ] [5] 0 5

Figura 1.3. Ejecucion de la suma lenta con los datos 2 y 3.

En cambio, si bien es cierto que, con los datos del ejemplo, se ha obtenidouna solucion, si se examina con detenimiento se vera que ese algoritmo nosiempre termina para dos cantidades enteras cualesquiera (v. g. 3 y 1).De hecho, la terminacion es una caracterstica escurridiza de la que hablaremosmas tarde (vease el apartado 1.3.1).

1.2.2 Una definicion formal de algoritmo

La caracterizacion hecha hasta ahora de los algoritmos es satisfactoria a efec-tos practicos. Mas concreta aun resulta a la vista de un lenguaje algortmicocomo el de los diagramas de flujo, que deja entrever dos aspectos:

El mantenimiento de unas variables (a y b) y de unas posiciones (1, . . . , 7),a lo que llamamos estado. Por ejemplo, cada fila de la tabla de la figura 1.3representa un estado en la evolucion del algoritmo 1.2.

La descripcion de transiciones entre estados, que vienen dadas por el propiodiagrama.

Estos aspectos de los algoritmos estan ausentes de la primera definicion,por lo que puede resultar aun algo incompleta; surge pues la necesidad de unadefinicion mas formal:

Definicion: Un algoritmo es una cuadrupla que comprende los siguientes ele-mentos:

1. El conjunto de los estados (llamemosle E) que pueden presentarse en todomomento durante el calculo.


Un estado viene dado por una tupla, incluyendo:

los valores de las variables que entran en juego; los datos sin leer y los resultados emitidos, y la marca, identificando la posicion del algoritmo en la que se da este

estado de los calculos.

Es decir, un estado se puede expresar as:

2. La identificacion de los estados iniciales, I E, o estados posibles alcomienzo del algoritmo.

3. La identificacion de los estados finales, F E, como posibles estados alterminar el algoritmo.

4. Una funcion de transicion entre estados,

t : E E

que describe el efecto de cada paso del computo asociado al algoritmo.Esta funcion debera:

Estar definida dentro de E, esto es, para cualquier e E debemostener que t(e) E. As, las transiciones entre estados son precisas ydeterministas.

A partir de cualquier estado inicial, la funcion de transicion t debellevar a un estado final en un numero finito de pasos, formalmente:para cualquier e I existe un k IN tal que

t se aplica k veces t(t( t(e) )) F

y, ademas, no tiene efecto alguno sobre los estados finales, es decir:para cualquier e F ocurre que t(e) = e. De aqu se obtiene lacaracterstica de finitud.

Siguiendo con el algoritmo del diagrama de flujo de la figura 1.2, identificamoslos siguientes estados:

E = { < 1 ; [d1, d2] ; [ ] ; >< 2 ; [d2] ; [ ] ; a a0 >< p ; [ ] ; [ ] ; a a0, b b0 >< 7 ; [ ] ; [r] ; > }


donde d1, d2, a, b, r IN, p {3, . . . , 6}, y siendo

I = {< 1; [d1, d2]; [ ]; >}

yF = {< 7; [ ]; [r]; >}.

La funcion de transicion t es la siguiente:

t(< 1; [d1, d2]; [ ]; >) = < 2; [d2]; [ ]; a d1 >t(< 2; [d2]; [ ]; a d1 >) = < 3; [ ]; [ ]; a d1, b d2 >t(< 3; [ ]; [ ]; a a0, b b0 >) =

{< 6; [ ]; [ ]; b b0 > si a = 0< 4; [ ]; [ ]; a a0, b b0 > si a 6= 0

t(< 4; [ ]; [ ]; a a0, b b0 >) = < 5; [ ]; [ ]; a a0 1, b b0 >t(< 5; [ ]; [ ]; a a0, b b0 >) = < 3; [ ]; [ ]; a a0, b b0 + 1 >t(< 6; [ ]; [ ]; b b0 >) = < 7; [ ]; [b0]; >t(< 7; [ ]; [r]; >) = < 7; [ ]; [r]; >

Desde el punto de vista del usuario de un algoritmo, se puede considerar unalgoritmo como una caja opaca cuyos detalles internos se ignoran, aflorando solola lectura de los datos y la escritura de los resultados. Estos aspectos observablesdesde el exterior se llaman frecuentemente la interfaz externa. No obstante, elmecanismo interno interesa al autor de algoritmos, esto es, al programador. Paraatender esta necesidad, algunos entornos de programacion permiten trazarprogramas, con lo que el programador puede ver evolucionar el estado internodurante la marcha de su programa con el grado de detalle que desee (veanselos apartados 5.4.1 y C.2.6). Esta posibilidad es interesante para depurar losprogramas, esto es, para buscar los posibles errores y subsanarlos.

Para terminar este apartado, debemos decir que el esquema de funciona-miento descrito a base de transiciones entre estados se conoce con el nombre demodelo de von Neumann (vease el apartado 7.2.1 de [PAO94]). Se dice que estemodelo es secuencial, en el sentido de que los pasos se efectuan uno tras otro. Dehecho, no es posible acelerar el proceso efectuando mas de un paso a un tiempo,porque cada paso tiene lugar desde el estado dejado por el paso anterior. Estecuello de botella es un defecto propio de las maquinas de von Neumann.

Cualidades deseables de un algoritmo

Es muy importante que un algoritmo sea suficientemente general y que seejecute eficientemente. Veamos con mas detalle que se entiende por general ypor eficiente:

1.3. Aspectos de interes sobre los algoritmos 11

1. Generalidad

Es deseable que un algoritmo sirva para una clase de problemas lo masamplia posible. Por ejemplo, la clase de problemas resolver una ecuacionde segundo grado, a + bx + cx2 = 0 es mas general que la consistenteen resolver ecuaciones de primer grado, a + bx = 0.

2. Eficiencia

Hablando en terminos muy generales, se considera que un algoritmo estanto mas eficiente cuantos menos pasos emplea en llevar a cabo su come-tido. Por ejemplo, para hallar la suma de dos numeros naturales, la reglatradicional que se aprende en ensenanza primaria es mas eficiente que elrudimentario procedimiento de contar con los dedos, de uno en uno. Estetema se revisara en el apartado 1.3.3, y sera tratado con mayor detalle enel captulo 18.

Estas dos cualidades no son siempre conciliables, por lo que frecuentementehay que optar por una solucion en equilibrio entre ambas cuando se disena unalgoritmo. Por ejemplo, un algoritmo que estudia y resuelve sistemas de ecua-ciones es mas general que uno que resuelve sistemas de ecuaciones lineales, yeste a su vez es mas general que otro que solo considera sistemas de dos ecua-ciones lineales con dos incognitas. Sin embargo, a mayor generalidad se tienetambien una mayor complejidad puesto que hay que tratar mas casos y no sepueden aplicar algoritmos especficos. Por consiguiente, si un buen numero desituaciones puede resolverse con un algoritmo rapido aunque poco general, espreferible adoptar este.

1.3 Aspectos de interes sobre los algoritmos

1.3.1 Computabilidad

Con el aumento de potencia y el abaratamiento de los computadores, cada vezse plantean aplicaciones mas sorprendentes y de mayor envergadura, capaces deresolver problemas mas generales. Da la impresion de que cualquier problema quese plantee ha de ser computable (esto es, ha de tener una solucion algortmica),sin otra limitacion que la potencia de la maquina ejecutora.

Sin embargo, esto no es as. Por rotunda que pueda parecer esta afirmacion,se debe aceptar que

hay problemas no computables

La cuestion que se plantea es algo delicada: adviertase que, si no se conocealgoritmo que resuelva un problema planteado, solo se puede asegurar que no


se conoce algoritmo que resuelva ese problema; en cambio, establecer que unproblema no es computable requiere demostrar que nunca se podra encontrarningun algoritmo para resolver el problema planteado.

Los siguientes son ejemplos de problemas no computables:

Decimo problema de Hilbert.Resolver una ecuacion diofantica con mas de una incognita.

Esto significa encontrar soluciones enteras de una ecuacion de la formaP (x1, x2, . . .) = 0, donde P es un polinomio con coeficientes enteros.

Problema de la parada.Determinar si un algoritmo a finaliza o no cuando opera sobre una entradade datos d:

Stop(a, d) =

S si a(d)

No si a(d) donde a(d) (resp. a(d) ) expresa que el algoritmo a, aplicado al dato d,s para (resp. no para).

Examinaremos con mas atencion el problema de la parada, y despues veremoscuan escurridizo puede resultar determinar si un algoritmo particular para o noconsiderando un sencillo ejemplo. Claro esta que esto no demuestra nada salvo,en todo caso, nuestra incapacidad para analizar este algoritmo en concreto. Porello, incluimos seguidamente una demostracion de que es imposible hallar unalgoritmo capaz de distinguir entre los algoritmos que paran y los que no.

Observese que se plantea aqu estudiar algoritmos que operan sobre algorit-mos, vistos como datos. Por extrano que parezca al principio, en Computacionse desarrollan frecuentemente programas que manejan otros programas con di-versos fines.

El problema de la parada no es computable

El problema de la parada, definido mas arriba, se puede expresar como sigue:se puede examinar cualquier algoritmo y decidir si para? Demostraremos queno existe, ni puede existir, el algoritmo Stop que distinga si un algoritmo a paracuando se aplica a los datos d.

Procederemos por reduccion al absurdo: Suponiendo que existe ese algoritmo(descrito mas arriba como Stop), a partir de el es posible construir otro similar,Stop, que averigue si un algoritmo a para cuando se aplica a su propio texto:

Stop(p) = Stop(p, p) =

{S si p(p) No si p(p)


Y entonces, tambien se puede definir el siguiente algoritmo a partir del an-terior:

Raro(p) =

{ si Stop(p) = S

No si Stop(p) = No

}=

{ si p(p)

No si p(p)

Veamos que el algoritmo Raro tiene un comportamiento verdaderamenteextrano cuando se aplica a s mismo:

Raro(Raro) =

{ si Stop(Raro) = S

No si Stop(Raro) = No

=

{ si Raro(Raro)

No si Raro(Raro) lo que resulta obviamente imposible.

La contradiccion a que hemos llegado nos lleva a rechazar la hipotesis inicial(la existencia de un algoritmo para el problema de la parada), como queramosdemostrar.

Numeros pedrisco

Como ejemplo de la dificultad de examinar un algoritmo y decidir si concluiratarde o temprano, consideremos la siguiente funcion t: IN IN:

t(n) =

3n+ 1 si n es impar

n/2 si n es par

Partiendo de un numero natural cualquiera, le aplicamos t cuantas veces seanecesario, hasta llegar a 1. Por ejemplo,

3t 10 t 5 t 16 t 8 t 4 t 2 t 1

Esta sencilla sucesion genera numeros que saltan un numero de veces impre-decible,

27t111 1

de manera que cabe preguntarse si todo natural n alcanza el 1 tras una cantidadfinita de aplicaciones de t, o por el contrario existe alguno que genera terminosque saltan indefinidamente.3

Se ha comprobado, por medio de computadores, que la sucesion llega a 1 sise comienza con cualquier numero natural menor que 240 ' 1012, pero aun no seha podido demostrar para todo n.

3Este problema tambien se conoce como problema 3n+1.


1.3.2 Correccion de algoritmos

El aspecto de la correccion es de crucial importancia para quien desarrolla unalgoritmo. Sin embargo, es imposible detectar los posibles errores de una formasistematica. Con frecuencia, la busqueda de errores (depuracion) consiste en lacomprobacion de un algoritmo para unos pocos juegos de datos. Sin embargo, esono garantiza nada mas que el buen funcionamiento del algoritmo para esos juegosde datos y no para todos los posibles. Volviendo al algoritmo de la suma lenta, lacomprobacion con los juegos de datos [2, 3] y [3, -1] ofrecera resultados correctos,y sin embargo el algoritmo unicamente termina cuando el primer sumando es (unentero) positivo.

Frente a la comprobacion, la verificacion consiste en la demostracion del buenfuncionamiento de un algoritmo con respecto a una especificacion. Esto es, laverificacion trata de garantizar que, para todos los datos considerados (descritosen la especificacion), el algoritmo lleva a los resultados (tambien descritos en laespecificacion) deseados. Por eso, aunque frecuentemente se habla de correccionde un algoritmo, sin mas, en realidad hay que decir correccion de un algoritmocon respecto a una especificacion.

Por lo general, la verificacion se basa en establecer aserciones (propiedades)del estado de la maquina en cada paso del algoritmo. Se profundizara en estaidea a lo largo de todo el texto. Por ejemplo, para verificar el funcionamiento delalgoritmo de suma lenta, consideremos que se hace funcionar sobre dos enterosgenericos m y n. Claramente, al llegar a la posicion 3 por vez primera, a = m yb = n. Por otra parte, en la posicion 3 se tiene invariablemente la propiedad

a+ b = m+ n

independientemente de las vueltas que se den y de las modificaciones que seefectuen sobre a y b,4 ya que cada unidad que se reste a a se le suma a b. Ahorabien, cuando se pasa de la posicion 3 a la 6 es por ser a = 0, con lo que se tiene,simultaneamente, el invariante a+ b = m+ n y a = 0, es decir:

b = m+ n

lo que asegura que la salida es correcta. . . cuando esta se produzca. Un algoritmoque ofrece una solucion correcta cuando para, pero del que no sepamos si parao no, se dice parcialmente correcto. Ese es el caso de la suma lenta de numerosenteros.

Ademas, si inicialmente a es un numero natural, es seguro que el algoritmopara, ya que la operacion a a 1 lo llevara a cero, precisamente en a vueltasdel bucle. Si se asegura que un algoritmo es parcialmente correcto y que para

4Por ello, esta propiedad se conoce como invariante.


en un tiempo finito, se dice que el algoritmo es (totalmente) correcto. Ese es elcaso de la suma lenta de pares de numeros, siendo el primero de ellos entero ypositivo.

La verificacion de algoritmos no es una tarea facil. Al contrario, verificarcompletamente un algoritmo involucra el uso de logica matematica, y con fre-cuencia resulta incluso mas complicado que desarrollarlo. De ah el interes quetiene esmerarse, desde el principio, en escribir algoritmos correctos, adquiriendoun buen estilo y esforzandose en emplear metodologas apropiadas para ello.

1.3.3 Complejidad de algoritmos

Resulta de gran interes poder estimar los recursos que un algoritmo necesitapara resolver un problema. En maquinas secuenciales, estos recursos son eltiempo y la memoria.5

Muchas veces, un algoritmo tarda tanto en ofrecer el resultado que resulta,en realidad, inutil. Un ejemplo de esta situacion se da en sistemas de controlde procesos, en donde la respuesta a determinadas circunstancias debe dispararmecanismos de seguridad en un tiempo crtico (por ejemplo, en centrales nu-cleares). Analogamente para el espacio, es posible que la maquina en que hade funcionar un programa disponga de una capacidad de memoria limitada ynos veamos obligados a elegir algoritmos que usen poca memoria. Por lo tanto,existen situaciones en las que si disponemos de varios algoritmos para un mismoproblema, deberemos decidir cual es el mas rapido o el que menos cantidad dememoria requiere. En el captulo 18 se ahondara en esta idea.

Como el tiempo requerido por los programas depende en gran medida de lapotencia de la maquina ejecutora, es frecuente medir en pasos (de coste fijo)el coste del algoritmo correspondiente. Para concretar un poco, y siguiendo conel ejemplo de la suma lenta, consideremos que cada bloque o caja del diagramaes un paso y, por tanto, cuesta una unidad. Entonces, es facil deducir que sumarlos naturales m y n lleva 3m+ 4 pasos.

En efecto, llamando tm al coste de sumar m y n, se tiene que

t0 = 4 pasos

tm = tm1 + 3, si n 1

pues para sumar 0 y n hay que realizar cuatro pasos (vease la figura 1.2) y sim 6= 0 hay que realizar tres pasos para reducir m en una unidad; resumiendo

t0 = 4

5En los ultimos anos, tambien esta interesando medir el numero de procesadores en maquinasde procesamiento en paralelo (vease el apartado 3.5 de [PAO94]).


t1 = t0 + 3 = 4 + 3 1t2 = t1 + 3 = 4 + 3 2...

......

tm = tm1 + 3 = 4 + 3 m

independientemente de n.

Por otra parte, es frecuente concentrar el interes en el coste para datos gran-des estudiando el comportamiento asintotico. De este modo, es posible redon-dear el tiempo despreciando terminos dominados por otros:

3m+ 4m 3m

Tambien es frecuente despreciar factores de proporcionalidad, absorbidos porlas velocidades de proceso de maquinas con distinta potencia, con lo cual

3m m

de manera que, en resumen, se dira que el algoritmo estudiado tiene coste li-neal. Naturalmente, podemos encontrarnos algoritmos con coste constante, lo-gartmico, lineal, cuadratico, exponencial, etc.

Hallar el coste de un algoritmo no es en general una tarea facil. Con fre-cuencia requiere una fuerte base matematica. Sin embargo, tambien es utilcomprender, desde el principio, que la potencia de los computadores no es ilimi-tada, y que la ejecucion de los programas consume sus recursos. Ese es el interesde que merezca la pena esforzarse por estudiar y encontrar algoritmos eficientes,aunque ello requiere muchas veces sacrificar su simplicidad.

1.4 Lenguajes algortmicos y de programacion

La descripcion de un algoritmo incluye organizar los datos que intervienenen el mismo, as como las acciones que se deben llevar a cabo sobre ellos. Unavez ideado el algoritmo, el modo mas natural e inmediato (y tambien el menosformal) de expresar esa organizacion es redactandolo con palabras y frases dellenguaje cotidiano. En el extremo opuesto se situan, por su rigidez, los lenguajesde programacion.

Entre la libertad, flexibilidad y ambiguedad de los lenguajes naturales y laprecision, rigidez y limitaciones de expresividad de los lenguajes de programacionse situan los lenguajes algortmicos. Estos tienen las siguientes cualidades:

1. Tienden un puente entre la forma humana de resolver problemas y suresolucion mediante programas de computador.

1.4. Lenguajes algortmicos y de programacion 17

2. Tienen cierta independencia de los lenguajes de programacion particulares,de modo que estan libres de sus limitaciones y as los algoritmos escritosen ellos se pueden traducir indistintamente a un lenguaje de programacionu otro.

Por ello, los lenguajes algortmicos constituyen una herramienta expresivacon una libertad y flexibilidad proxima a la de los naturales y con el rigor de losde programacion.

En realidad, las unicas restricciones que deberan imponerse a estos lenguajesproceden de las caractersticas que tienen los algoritmos: expresar sus acciones(que deben realizar y cuando) con la precision necesaria, y que estas accionessean deterministas.

Por consiguiente, todo lenguaje algortmico debe poseer mecanismos con queexpresar las acciones as como el orden en que han de llevarse a cabo. Lasacciones, se expresan mediante instrucciones (tambien llamadas ordenes o sen-tencias), que son comparables a verbos en infinitivo: asignar. . , leer. . , escribir. . .y otras. La concatenacion de las instrucciones expresa en que orden deben suce-derse las acciones; esto es, como se ensamblan unas tras otras. Los modos masusados para ensamblar ordenes son la secuencia, la seleccion y la repeticion, ylos estudiaremos en el captulo 7.

A la vista de las observaciones anteriores es logico cuestionar que los lenguajesnaturales sean algortmicos (debido sobre todo a la ambiguedad que es inherentea ellos). Ademas, resulta mas practico utilizar medios de expresion normalizados,facilitandose la comunicacion entre disenadores y usuarios de los algoritmos ylas personas que los desarrollan.

Los diagramas de flujo constituyen uno de los lenguajes algortmicos quemayor difusion han alcanzado, aunque su uso esta menguando drasticamente enlos ultimos anos en favor de otros metodos mas apropiados desde el punto devista formativo.6 Entre ellos, debe citarse el seudocodigo, que aportara valiosasideas para la adquisicion de un buen estilo de programacion y, en definitiva, paraaprender como enfocar la resolucion de problemas complicados. Seguidamente,describimos el algoritmo de la suma lenta mediante seudocodigo:

Sean a, b ZZLeer a y b

Mientras a 6= 0, hacer{a a 1b b+ 1

Escribir b

6De hecho, nosotros desaconsejamos su uso como lenguaje de desarrollo de algoritmos, limi-tando su estudio a mostrar, precisamente, lo que no es la programacion estructurada (vease elapartado 7.2.1).


En la practica, el seudocodigo se usa como un medio expresivo de caminohacia un lenguaje de programacion concreto. Por tanto, es logico que los algorit-mos seudocodificados tengan un parecido notorio con los programas escritos enese lenguaje. En concreto, comparese por ejemplo el seudocodigo anterior con elprograma siguiente, escrito en Pascal:

Program SumaLenta (input, output);{Se suman dos enteros, pasando unidades de uno a otro}{PreC.: input = [m n], enteros}vara, b: integer;

beginReadLn (a, b);

{Inv.: a + b = m + n}while a 0 do begina:= a-1;

b:= b+1

end; {while}WriteLn(b)

end. {SumaLenta}

1.5 Desarrollo sistematico de programas

En los ultimos anos, las aplicaciones comerciales se han hecho cada vez masgrandes y complejas y, por tanto, su desarrollo resulta cada vez mas caro, lentoy sujeto a numerosos errores. Este problema fue tremendamente importantehacia los anos sesenta (se hablaba entonces de crisis del software), y paratratar de solucionarlo surgio entonces la Ingeniera del software, que considerael desarrollo de programas y aplicaciones como un proceso productivo donde seaplican tecnicas de ingeniera. El desarrollo del software se organiza en fases,que en conjunto se conocen como el ciclo de vida.7 Son las siguientes:

Planificacion: En esta fase inicial hay que constatar la verdadera necesidad delproducto que se va a desarrollar y valorar los recursos humanos y tecnicosque precisa su desarrollo. Esta valoracion se traduce en coste economico ytiempo de elaboracion. Si se aprueba el proyecto, se pasa a la fase siguiente.

7La organizacion de estas fases da lugar a diversas variantes del ciclo de vida, siendo uno delos mas aplicados el conocido como ciclo de vida clasico. Existen crticas importantes a este,basicamente por su caracter secuencial y por la dificultad de establecer inicialmente todas lasespecificaciones. En respuesta a estas crticas se han creado otros modelos de desarrollo como sonla utilizacion de prototipos y de lenguajes de cuarta generacion (4GL) y el llamado modelo enespiral.

1.5. Desarrollo sistematico de programas 19

Analisis: En la fase de analisis se establecen cuales deben ser la funciones quedebe cumplir la aplicacion y como debe realizarse el trabajo conjunto de losdiferentes modulos en que se va a dividir. Dentro de esta fase se determinaun sistema de pruebas que permita detectar los posibles errores y asegurarel funcionamiento correcto de la aplicacion y las condiciones para unir losmodulos de forma fiable. Como resultado de esta fase se redactan lasespecificaciones detalladas del funcionamiento general del software.

Diseno: En esta fase se disena el conjunto de bloques, se dividen en partes yse asignan a los equipos de programadores. Cada equipo elabora su parte,escribiendola en un lenguaje algortmico y probandola de forma manual.Como resultado de esta fase se obtienen algoritmos escritos en lenguajealgortmico.

Codificacion: La fase de codificacion se confunde muchas veces con la pro-gramacion y consiste en escribir los algoritmos en un lenguaje de progra-macion. Es un proceso casi automatico.

Validacion: La fase de validacion consiste en aplicar el sistema de pruebas a losmodulos, a las conexiones entre ellos (prueba de integracion) y, por ultimo,a la totalidad de la aplicacion (prueba de validacion). Como resultadode esta fase se genera la aplicacion habiendo corregido todos los erroresdetectados en las pruebas.

Mantenimiento: En la fase de mantenimiento se redacta la documentacionactualizada, tanto para el programador como para el usuario. Se iniciala explotacion de la aplicacion y se detectan y corrigen los errores y de-ficiencias no advertidas en las fases anteriores, lo que puede suponer uncoste anadido importante. El resultado de esta fase es una aplicacion enexplotacion.

Evidentemente, en un curso como este, los programas que vamos a desarro-llar no requieren, por su reducido tamano, la ejecucion de todas estas fases. Sinembargo, conviene advertir que la tarea de la programacion no consiste en lacodificacion (escritura de un programa) directa, ni siquiera para programas sen-cillos, sino que incluye otras fases: es necesario comprender primero el problemaque se plantea; si se puede dividir en subproblemas, esto reduce la complejidad,aunque en ese caso hace falta acoplar los diferentes modulos (por el momento,digamos que se trata de fragmentos de programa); y, por supuesto, es ineludibleque el programa sea correcto, de forma que este requisito necesario merece todanuestra atencion.


1.6 Conclusion

La importancia de los algoritmos y de los lenguajes algortmicos reside ensu capacidad para expresar procesos, encaminados a ofrecer la solucion a pro-blemas planteados, con independencia de los lenguajes de programacion, y aunde la maquina, siendo as posible el desarrollo de algoritmos para computado-res todava no creados: de hecho, muchos de los programas actuales respondena algoritmos concebidos mucho antes de que apareciera el primer computador:considerese por ejemplo el metodo que ideo Euclides en el siglo iv a. C. parahallar el maximo comun divisor de dos numeros naturales. Los lenguajes deprogramacion son tambien importantes, ya que permiten materializar los algo-ritmos, razon por la que se ha avanzado tanto en el estudio de estos en las ultimasdecadas.

Por otra parte, tratar el metodo (algoritmo) como objeto de estudio suponeun salto de nivel en la resolucion de problemas, ya que ahora no solo se requiere laaplicacion de un determinado procedimiento de resolucion, sino que cobra impor-tancia la invencion y descripcion del mismo. Es decir, para resolver un problemahabra que identificar que acciones conducen a la solucion, y como describirlas yorganizarlas.

En otras palabras, en este captulo, nuestro modus operandi ha consistido en:

1. Disponer de un problema y un metodo.

2. Resolverlo; es decir, aplicar el metodo al problema.

mientras que, a partir de ahora, solo disponemos de un problema y no del metodoque debemos aplicar, por lo que deberemos disenar y desarrollar el mismo parapoder aplicarlo al problema planteado. En resumidas cuentas, la resolucion deun problema general requerira:

1. Disenar un algoritmo apropiado.

2. Escribir el programa correspondiente en un lenguaje de computador.

3. Ejecutar el programa correspondiente para el juego de datos del problema.

1.7 Ejercicios

1. Considere la relacion de problemas:

(i) Resolver una ecuacion de primer grado de la forma a+ bx = 0.

(ii) Sumar dos fracciones.

(iii) Interpretar una partitura al violn.

1.8. Referencias bibliograficas 21

(iv) Hacer la cuenta atras, desde 10 hasta 0.

Para cada uno de ellos, se pide que:

(a) Identifique cuales son los datos y los resultados.

(b) Describa un problema mas general y, si se puede, otro menos general.

(c) Distinga cuales de esos problemas pueden resolverse mediante algoritmos ycuales no.

(d) Esboce, con sus propias palabras o en seudocodigo, un algoritmo para losproblemas (i), (ii) y (iv).

2. El problema de restar dos enteros positivos se puede resolver por un procedimientoanalogo al de la suma lenta: en vez de pasar unidades de una cantidad a la otra,

(2, 3) (1, 4) (0, 5) 5

se van restando unidades a ambas a la vez:

(9, 2) (8, 1) (7, 0) 7

Se pide que:

(a) Escriba un diagrama de flujo para este problema.

(b) Examine como evoluciona para el calculo de 5 2.(c) Estudie su complejidad.

(d) Estudie su correccion.

(e) Exprese el algoritmo en seudocodigo.

(f) Redacte el programa correspondiente en Pascal basandose en el programapresentado para la suma lenta.

1.8 Referencias bibliograficas

Muchos de los conceptos que se estudian en este captulo (y en algunas otras partesde este libro) pueden consultarse tambien en [GL86], que ofrece una introduccion claray amena a diversos aspectos teoricos y practicos sobre los algoritmos y programas, sudesarrollo y ejecucion, as como sus implicaciones sociales. La formalizacion de losalgoritmos dada aqu es una adaptacion de la presentada en [FS87].

El apartado de los lenguajes algortmicos se ampla un poco en el captulo 7 deeste mismo libro, donde se introducen el seudocodigo y los diagramas de flujo. Debeadvertirse sin embargo que esta referencia no anima al lector a estudiar los diagramasde flujo ahora, sino mas bien a esperar su momento y limitar su estudio al cometido conque all se introducen.

A pesar del ttulo del epgrafe lenguajes algortmicos y de programacion, no se hadicho mucho sobre estos ultimos: en realidad, la idea es establecer un primer vnculoentre ellos. Para ampliar lo dicho aqu sobre los lenguajes de programacion, remitimosal captulo 5 de [PAO94] y a la bibliografa que all se refiere.

Captulo 2

El lenguaje de programacion Pascal

2.1 Introduccion . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.2 Otros detalles de interes . . . . . . . . . . . . . . . . . . 24

2.3 Origen y evolucion del lenguaje Pascal . . . . . . . . . 24

2.4 Pascal y Turbo Pascal . . . . . . . . . . . . . . . . . . . . 25

En este breve captulo se presenta el lenguaje de programacion Pascal, resal-tando algunas de sus caractersticas mas importantes, como la sencillez de susinstrucciones, la estructuracion de estas y su capacidad expresiva, que permiteimplementar algoritmos de muy diversa ndole. Estas caractersticas, entre otras,son las que justifican que Pascal sea el lenguaje de programacion utilizado eneste libro.

2.1 Introduccion

Pascal es un lenguaje de alto nivel : se parece mas al lenguaje natural hablado,o al matematico, que al lenguaje de maquina (vease el cap. 5 de [PAO94]). Estenivel se alcanza gracias a una pequena coleccion de mecanismos simples perode una gran potencia: unos permiten estructurar acciones (secuencia, seleccion eiteracion), otros datos (arrays, registros, ficheros), y otros hacen posible extenderel lenguaje, dotandolo en general con conceptos (datos y operaciones) semejantesa los empleados en el razonamiento humano sobre los problemas, como se mostroen el apartado 1.4.

24 Captulo 2. El lenguaje de programacion Pascal

La gran expresividad debida a la particular estructuracion de sus datos y desu pequena coleccion de instrucciones evita la necesidad de recurrir a otros meca-nismos (probablemente enrevesados, difciles de expresar y de analizar, como porejemplo la instruccion de bifurcacion incondicional goto); por todo esto decimosque es un lenguaje estructurado (vease el captulo 7). Por otra parte, permitecrear modulos que extienden el lenguaje (por lo que se dice que es modular ; verel captulo 9); esta caracterstica permite desarrollar programas dividiendolos enpartes (modulos o subprogramas) mas pequenas, independientes, que se puedendesarrollar por separado.

Una caracterstica positiva de Pascal es su reducido conjunto de instruc-ciones, lo que lo hace relativamente compacto y facil de aprender. En resumen,el lenguaje Pascal facilita la adquisicion de buenos habitos de programacion yproporciona los instrumentos que permiten adaptarse a los principales metodosde desarrollo de algoritmos: programacion estructurada y modular y definicion yuso de tipos de datos. Estas tecnicas han convertido en las ultimas decadas a laprogramacion en una actividad disciplinada y guiada por una cierta metodologa,y el lenguaje Pascal ha contribuido enormemente a su difusion y utilizacion. Porello, es ademas idoneo como primer lenguaje de programacion, facilitando elaprendizaje posterior de otros. As lo prueba su fuerte implantacion.

2.2 Otros detalles de interes

La mayora de los traductores del Pascal son compiladores (vease el apar-tado 5.3.1 de [PAO94]): el programa en Pascal se traduce de una sola vez alenguaje maquina antes de ser ejecutado, y en ese proceso se detectan gran can-tidad de errores de forma automatica, permitiendo al programador enmendarlosantes de la ejecucion. Como ejemplo de las verificaciones que se efectuan durantela compilacion, una de las mas importantes consiste en la compatibilidad de lostipos de los objetos.

Antes de la aparicion de Pascal existan lenguajes dirigidos a la programacioncientfica (como Fortran) y otros dirigidos a la de gestion (como Cobol). Ellenguaje Pascal trata de conciliar los dos tipos de programacion, por lo que sueledecirse que Pascal es un lenguaje de proposito general.

2.3 Origen y evolucion del lenguaje Pascal

Es obvio decir que Pascal toma el nombre del matematico frances BlaisePascal (16231662) que en 1642 invento la primera maquina de calcular paraayudar a su padre en su trabajo de tasador de impuestos.

2.4. Pascal y Turbo Pascal 25

El lenguaje Pascal fue concebido por Niklaus Wirth en 1968 y definido en1970 en el Instituto Politecnico de Zurich para ensenar la programacion a susalumnos. Desde que comenzo a utilizarse (1971), ha tenido un enorme desarrolloy difusion, adaptandose a la mayora de los computadores, grandes y pequenos.Actualmente es uno de los lenguajes mas usados en las universidades de muchospases del mundo. Gracias a esta difusion, junto con los compiladores de estelenguaje, se han desarrollado potentes entornos de programacion de gran calidady bajo precio.

Algunas de las implementaciones del lenguaje son Turbo Pascal c (que fun-ciona en computadores compatibles PC, bajo el sistema operativo DOS y bajoWindows), Macintosh Pascal c, VAX Pascal c, Microsoft Pascal c y Quick Pascal c.

Es un lenguaje estandarizado, estando recogido en el Pascal User Manual andReport de K. Jensen y N. Wirth [JW85]. Por lo general, las distintas versionesse adaptan al estandar y lo extienden. Por lo tanto, un programa escrito enPascal estandar (segun el Pascal User Manual and Report) debe funcionar en lamayora de las versiones; en cambio, si una version contiene extensiones, lo masprobable es que no funcione en las otras.

En cualquier caso, es ciertamente comprensible que las caractersticas pre-sentadas aqu, sin conocer el lenguaje, pueden sonar a hueco, ya que el momentoapropiado para una valoracion cabal es a posteriori , despues de un conocimientomas completo de este lenguaje e incluso otros: solo as puede apreciarse su ele-gancia conceptual, la enorme influencia que ha tenido en el desarrollo de otros, enla ensenanza de la programacion y en la metodologa de desarrollo de programasy, naturalmente, tambien sus limitaciones.

Quienes ya conozcan este lenguaje en mayor o menor medida, o quienesdeseen ampliar el contenido de este libro, pueden encontrar en [Wir93] una visionpanoramica, escrita por el propio Wirth.

2.4 Pascal y Turbo Pascal

La posicion que se adopta en este libro acerca del lenguaje de programacionutilizado es intermedia, entre el estandar ideado inicialmente (lo que es con-veniente para que los programas sean transportables) y un compilador real (loque tiene la ventaja de permitir la practica en el desarrollo de programas). Elcompilador concreto adoptado es Turbo Pascal, potente, rapido, de amplia di-fusion y dotado con un entorno muy bien desarrollado que facilita la tarea delprogramador.

El inconveniente consiste en que Turbo Pascal, como la mayora de los com-piladores existentes, incluye diferencias con respecto a Pascal estandar, aunque

26 Captulo 2. El lenguaje de programacion Pascal

estas son mnimas: debe decirse que casi no tiene limitaciones, y que en cambioofrece una gran cantidad de extensiones.

Nuestra decision ha sido trabajar con este compilador1 para que sea posibleal alumno desarrollar sus practicas, haciendo uso de las mnimas herramientasextendidas del mismo y senalando en todo caso las diferencias con respecto alestandar. Ademas se incluye un apendice sobre Turbo Pascal donde se presentanlas caractersticas y diferencias mas importantes con Pascal estandar.

1Para nuestros propositos es valida cualquier version de Turbo Pascal desde la 4.0 hasta la 7.0,as como Turbo Pascal para Windows y Borland Pascal.

Captulo 3

Tipos de datos basicos

3.1 Introduccion . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.2 El tipo integer . . . . . . . . . . . . . . . . . . . . . . . . 28

3.3 El tipo real . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.4 El tipo char . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.5 El tipo boolean . . . . . . . . . . . . . . . . . . . . . . . . 36

3.6 Observaciones . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.7 El tipo de una expresion . . . . . . . . . . . . . . . . . . 43

3.8 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

Es preciso adquirir desde el principio el concepto de dato, puesto que losalgoritmos (y por lo tanto los programas) los manejan constantemente,1 desdela entrada (que puede considerarse como la coleccion inicial de datos) hasta lasalida (o conjunto de datos resultantes), pasando frecuentemente por un sinfn deresultados provisionales que intervienen en los calculos intermedios (tales comolas cifras de acarreo en una operacion de multiplicar).

Este captulo se dedica al estudio de los tipos de datos elementales de Pascal,explicando sus dominios y operaciones, as como la construccion de expresionescon datos de dichos tipos.

1De hecho, en un algoritmo se organizan dos aspectos inseparables: acciones y datos.

28 Captulo 3. Tipos de datos basicos

3.1 Introduccion

Un dato es simplemente la representacion de un objeto mediante smbolosmanejables por el computador.

El uso de numeros (enteros y reales), caracteres y valores logicos es corrienteen programacion. De hecho, casi todos los lenguajes disponen de ellos a priori,por lo que se les llama tambien tipos de datos predefinidos o tambien estandar.

Ciertamente, es posible ampliar nuestro lenguaje con otros objetos a la me-dida de los problemas que se planteen, tales como vectores o conjuntos (veanselos captulos 11 y 12). Estos se construyen usando los datos predefinidos comolas piezas mas elementales, por lo que tambien se les llama tipos de datos basicosa los tipos de datos predefinidos.

Sin embargo, lo cierto es que, en principio, solo se puede contar con los tiposde datos mencionados, que en Pascal se llaman respectivamente integer, real,char y boolean, y que estudiamos a continuacion.2

Los tipos de datos se caracterizan mediante sus dominios (conjuntos de va-lores) y las operaciones y funciones definidas sobre esos dominios.

3.2 El tipo integer

Dominio

Su dominio, denotado Z, incluye valores enteros positivos o negativos. De-bido a las limitaciones de representacion (vease el apartado 2.2.3 de [PAO94]),el dominio de integer esta acotado por la constante predefinida MaxInt, propiade cada version: en Turbo Pascal por ejemplo, MaxInt vale 32767, y el dominiode integer es {-32768,..., 32767}. Los numeros integer se escriben lite-ralmente sin espacios ni puntos entre sus cifras, posiblemente precedidos por elsigno mas o menos, por ejemplo: 174, -273, +17, etc. El diagrama sintactico(vease apartado 5.2.1 de [PAO94]) de la figura 3.1 resume estos detalles.

Operaciones y funciones

Asociadas al tipo integer, se tienen las siguientes operaciones aritmeticas:

2En adelante, usaremos letra de molde para escribir el texto en Pascal, excepto las palabrasreservadas (vease el apartado 4.2) que apareceran en negrilla.

3.2. El tipo integer 29

Entero sin signo

+

Nmero Entero

Entero sin signo

--

Dgito

Dgito

0 1 9

...

...

...

Figura 3.1.

30 Captulo 3. Tipos de datos basicos

+ suma- resta* multiplicacion

div division enteramod resto de la division entera

Su funcionamiento es similar al que tienen en Matematicas: son operacionesbinarias (tienen dos argumentos, salvo la operacion -, usada tambien para hallarel opuesto de un entero) e infijas (en las expresiones, se situan entre sus dosargumentos). Emplearemos la notacion matematica

div : Z Z Z

para expresar que los dos argumentos son de tipo entero y su resultado tambien loes. Todas las operaciones presentadas responden a este esquema. Las operacionesdiv y mod expresan respectivamente el cociente y el resto de la division entera:3

7 div 2 ; 37 div -2 ; -3-7 div 2 ; -3-7 div -2 ; 3

7 mod 2 ; 17 mod 2 ; 17 mod 2 ; 17 mod 2 ; 1

Observese que verifican la conocida regla:

dividendo = divisor cociente + resto

Ademas, existen las siguientes funciones predefinidas:

Abs valor absoluto del enteroSqr cuadrado del enteroPred entero predecesorSucc entero sucesor

que son monarias (se aplican a un argumento unico) y se aplican en forma prefija(preceden a su argumento, dado entre parentesis).

Estas operaciones y funciones son internas, puesto que convierten argumentosinteger en integer:

Abs : Z Z

Sin embargo, debe observarse que las limitaciones que pesan sobre el tipointeger afectan a las operaciones y funciones, cuyo resultado sera correcto solocuando no rebase los lmites del dominio.

3Usaremos el smbolo ; para expresar la evaluacion de una operacion o funcion.

3.2. El tipo integer 31

Expresiones

Al ig

universo

Documents

Transcript of universo