Fundamentos y Estructuras de Programaci on - DECCcic.puj.edu.co/wiki/lib/exe/fetch.php?media=materias:fundestprog:... · 2 Noci on de Problema Un problema existe cuando el estado

Fundamentos y Estructuras de Programacion

Gerardo M. Sarria M.

Borrador de 21 de julio de 2011

Indice general

1. Introduccion 9

2. Nocion de Problema 112.1. Comienzos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.1.1. Calculo Lambda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.1.2. Maquina de Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.2. Problemas Tratables e Intratables . . . . . . . . . . . . . . . . . . . . . . . . 162.3. Solucion de Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262.4. Estrategias de Implementacion . . . . . . . . . . . . . . . . . . . . . . . . . 31

3. Nocion de Lenguaje 353.1. Historia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353.2. Estructura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383.3. Compiladores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413.4. Maquinas Virtuales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443.5. Depuracion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463.6. Excepciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523.7. Interfaces Graficas de Usuario (Eventos) . . . . . . . . . . . . . . . . . . . . 573.8. Referencias y Apuntadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . 603.9. Declaraciones y Tipos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

4. Nocion de Tipo Abstracto de Datos 734.1. Tipos Abstractos de Datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 734.2. Listas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

4.2.1. Diseno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 824.2.2. Implementaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 834.2.3. Analisis de Complejidad de las Implementaciones . . . . . . . . . . . 964.2.4. Utilizacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 964.2.5. Variantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

4.3. Pilas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1004.3.1. Diseno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1024.3.2. Implementaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1044.3.3. Utilizacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

4.4. Colas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1044.5. Tablas Hash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

3

Indice general

4.6. Arboles Binarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1044.7. Arboles N-arios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1044.8. Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

Indice de nociones 105

4

Indice de figuras

2.1. Maquina de Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.2. Estado inicial del sudoku . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262.3. Estado final del sudoku . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.4. Busqueda lineal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282.5. Busqueda lineal bidireccional . . . . . . . . . . . . . . . . . . . . . . . . . . 282.6. Un ejemplo de busqueda binaria . . . . . . . . . . . . . . . . . . . . . . . . 292.7. Busqueda con tabla hash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302.8. Ventana de una Calculadora . . . . . . . . . . . . . . . . . . . . . . . . . . . 322.9. Creacion de funciones en el modelo top-down . . . . . . . . . . . . . . . . . 332.10. Creacion de funciones en el modelo bottom-up . . . . . . . . . . . . . . . . 33

3.1. Evolucion de los lenguajes de alto nivel . . . . . . . . . . . . . . . . . . . . 373.2. Analisis para la asignacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403.3. Componentes superficiales de un compilador . . . . . . . . . . . . . . . . . . 413.4. Componentes intermedios de un compilador . . . . . . . . . . . . . . . . . . 423.5. Ejemplo de las fases de compilacion . . . . . . . . . . . . . . . . . . . . . . . 433.6. Jerarquıa de las maquinas virtuales . . . . . . . . . . . . . . . . . . . . . . . 453.7. Primer bug encontrado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463.8. Data Display Debugger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493.9. Editor Eclipse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503.10. Diagrama de contorno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 693.11. Diagrama de contorno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

4.1. Nodo con encadenamiento simple . . . . . . . . . . . . . . . . . . . . . . . . 834.2. Lista con encadenamiento simple . . . . . . . . . . . . . . . . . . . . . . . . 844.3. Nodo con doble encadenamiento . . . . . . . . . . . . . . . . . . . . . . . . 884.4. Lista con doble encadenamiento . . . . . . . . . . . . . . . . . . . . . . . . . 884.5. Lista circular encadenada simple . . . . . . . . . . . . . . . . . . . . . . . . 894.6. Lista circular doblemente encadenada . . . . . . . . . . . . . . . . . . . . . 904.7. Lista implementada con un vector . . . . . . . . . . . . . . . . . . . . . . . 914.8. Lista implementada con cursores . . . . . . . . . . . . . . . . . . . . . . . . 934.9. Ejemplo real de una pila . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

5

Indice de algoritmos

1. Imprime los numeros del 1 al 100 . . . . . . . . . . . . . . . . . . . . . . . . 172. Imprime los numeros del 1 al n . . . . . . . . . . . . . . . . . . . . . . . . . . 183. Imprime los numeros del n al 1 dividiendo por dos cada vez . . . . . . . . . . 194. Suma los elementos impares de un vector de enteros . . . . . . . . . . . . . . 215. Ordenamiento por el metodo burbuja . . . . . . . . . . . . . . . . . . . . . . 226. Descubre si el procesador tiene error . . . . . . . . . . . . . . . . . . . . . . . 487. Divide el numero 10 entre un numero dado por el usuario en C++ . . . . . . 538. Divide el numero 10 entre un numero dado por el usuario, usando un condi-

cional en C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539. Divide el numero 10 entre un numero dado por el usuario, usando una asercion

en C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5410. Divide el numero 10 entre un numero dado por el usuario, usando un mane-

jador de excepciones en C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . 5411. Divide el numero 10 entre un numero dado por el usuario, usando dos mane-

jadores de excepciones en C++ . . . . . . . . . . . . . . . . . . . . . . . . . . 5512. Divide el numero 10 entre un numero dado por el usuario, garantizando la

continuacion, alternativa 1 en C++ . . . . . . . . . . . . . . . . . . . . . . . 5613. Divide el numero 10 entre un numero dado por el usuario, garantizando la

continuacion, alternativa 2 en C++ . . . . . . . . . . . . . . . . . . . . . . . 5714. Imprime ’HolaMundo!’ en una ventana usando Gtk+ . . . . . . . . . . . . . 5915. Imprime ’HolaMundo!’ por lınea de comandos usando curses . . . . . . . . . 5916. Asigna cuatro variables en Python (analisis de referencias) . . . . . . . . . . 6017. Declara, asigna e imprime un entero y un apuntador a entero en C++ . . . . 6618. Asigna tres variables en Python (analisis de tipos) . . . . . . . . . . . . . . . 6719. Asigna tres variables en C++ (analisis de tipos) . . . . . . . . . . . . . . . . 6720. Cambio de tipo de una variable en Python . . . . . . . . . . . . . . . . . . . 6821. Definicion de dos bloques de ejecucion en Pascal . . . . . . . . . . . . . . . . 7022. Definicion de dos funciones que comparten una variable en Python . . . . . . 7123. Asignacion simple en Python . . . . . . . . . . . . . . . . . . . . . . . . . . . 7224. Dos identificadores con la misma referencia en una funcion en Python . . . . 72

7

1 Introduccion

9

2 Nocion de Problema

Un problema Problemaexiste cuando el estado en el que se encuentran las cosas difiere del estadoen que se desea que esten. La solucion al problema es una serie de pasos que llevan delestado en que estan al estado que se desean.

Existen muchos problemas en el mundo (mas de los que el hombre puede resolver).Una gran cantidad de dichos problemas pueden resolverse usando el computador comoherramienta.

En este capıtulo se mostrara como identificar problemas que son solucionables por mediodel computador y estrategias para resolverlos.

2.1. Comienzos

El estudio de los problemas que se pueden resolver por medios computacionales tiene suscomienzos en la decada de 1930, cuando D. Hilbert pretendıa crear un sistema matematicoformal completo y consistente, en el que todos los problemas pudieran plantearse conprecision. Ademas deseaba encontrar un algoritmo para determinar si una proposicion,dentro del sistema, era verdadera o falsa. Con este sistema cualquier problema bien definidose resolverıa aplicando dicho algoritmo.

Despues de varias investigaciones K. Godel demostro que el sistema planteado por Hilbertno era posible construirlo. Para ello publico el famoso Teorema de Incompletitud1.

Unos anos despues se mostro que existıan problemas que eran indecidibles Indecidibilidad, es decir,no hay algoritmos que resuelvan dichos problemas (A. Church y A. Turing probaron queel problema de Hilbert era indecidible). Aquı los problemas se dividieron en dos tipos:tratables e intratables.

Los estudios teoricos de los problemas siguieron cuando Church introdujo a las matemati-cas una notacion formal para las funciones calculables, que denomino calculo lambda. Laidea era transformar todas las formulas matematicas a una forma estandar, de tal maneraque la demostracion de teoremas se convertirıa en la transformacion de cadenas de sımbolossiguiendo un conjunto de reglas como en un sistema logico (vease [21]).

Por otro lado, Turing argumento que el problema de Hilbert podıa ser atacado con laayuda de una maquina. La Maquina de Turing podıa ser usada por una persona paraejecutar un procedimiento bien definido, mediante el cambio del contenido de una cinta

1Teorema de incompletitud : Ningun sistema deductivo que contenga los teoremas de la aritmetica, y conlos axiomas recursivamente enumerables puede ser consistente y completo a la vez.

11


ilimitada, dividida en cuadros que pueden contener un solo sımbolo de un conjunto dado(el alfabeto).

A continuacion se mostrara un poco mas en detalle los dos estudios anteriores.

2.1.1. Calculo Lambda

El calculo lambdaCalculo λ es un formalismo para especificar funciones que calculan valores apartir de sus argumentos. Las funciones se definen con el sımbolo λ seguido de su argu-mento (funciones con multiples argumentos pueden verse como la aplicacion de funcionesa funciones).

La notacion λx.P muestra una funcion cuyo cuerpo es P y cuyo argumento es x, demanera que la aplicacion de esta funcion con un argumento n se reduce a sustituir x porn en P . Lo anterior quiere decir que si se tiene

λx.fx

y se aplica con el argumento n, se tendra

(λx.fx)n = fn

La sintaxis abstracta del calculo puede verse en el cuadro 2.1. Se tienen solo variables,terminos lambda aplicados y abstracciones de terminos.

M ::= x (variables) | M1M2 (aplicación) | λx.M (abstracción)

Cuadro 2.1: Sintaxis del calculo lambda

Con el calculo lambda, las funciones calculables (i.e. la idea de computabilidad) puedenser expresadas [16]. En el ejemplo 2.1.1 se muestra la funcion suma de numeros naturalesen el calculo lambda.

Ejemplo 2.1.1Supongamos que queremos usar el calculo lambda para sumar numeros naturales, es decir,saber si la suma de numeros naturales es una funcion computable (i.e. puede ser imple-mentada en un computador). Lo primero que debemos hacer es representar los numerosen este calculo ya que como se vio en el cuadro 2.1 no hay numeros, pero ¿como crearuna representacion, dentro de un sistema que solo soporta sımbolos (y no numeros), quepermita contar, sumar, multiplicar y hacer todo lo que se puede hacer con numeros?

12

2.1 Comienzos

La idea es crear una representacion funcional lo mas cercana posible a los numerosnaturales. Representar el numero cero y crear una funcion sucesor para encontrar los demasnumeros, es basico.

Los numeros naturales en el calculo lambda pueden ser representados como una funcioncon dos parametros (Numeros de Church):

λf.λx.〈algo〉

El primer parametro f , es la funcion sucesor. El segundo parametro, x, es el valor querepresenta el cero. De allı que el 0 sea representado como:

0 ≡ λf.λx.x

Cuando la funcion anterior es aplicada, siempre retornara el valor que representa el cero.El numero de Church para el uno aplica la funcion sucesor al valor que representa el cero,exactamente una vez:

1 ≡ λf.λx.fx

Los numeros de Church siguentes se encuentran aplicando la funcion sucesor mas veces:

2 ≡ λf.λx.f(fx)3 ≡ λf.λx.f(f(fx))4 ≡ λf.λx.f(f(f(fx)))5 ≡ λf.λx.f(f(f(f(fx))))

...n ≡ λf.λx.fnx

Para representar la suma se tomara la aproximacion mas sencilla: sumar dos numeros ny m, es tomar m y sumarle uno (1) n veces, es decir, encontrar el n-avo sucesor de m; ası,3 + 5 es hallar el 3er sucesor de 5. Si el conjunto de sucesores de 5 es {6, 7, 8, 9, . . .}, eltercer sucesor es 8.

De manera mas formal, y siguiendo con la idea de que solo se puede representar el cero, ylos demas numeros se trabajan como sucesores del cero. La funcion sucesor podrıa definirseası:

S ≡ λn.λf.λx.f(nfx)

De esta manera el numero 2 surge de aplicar la funcion sucesor al numero 1.

S 1 ≡ (λn.λf.λx.f(nfx)) (λf.λx.fx)→ λf.λx.f((λz.λw.zw)fx)→ λf.λx.f((λw.fw)x)→ λf.λx.f(fx)≡ 2

13


Entonces la suma se representarıa de esta manera:

+ ≡ λn.λmλf.λx.fn(fmx)

+ n m ≡ λf.λx.nf(mfx)

Ası, la suma de 2 + 1 sera:

+ 2 1 ≡ λf.λx.(λf2.λx2.f2(f2x)) f ((λf1.λx1.f1x) f x)→ λf.λx.f (f ((λf1.λx1.f1x) f x)→ λf.λx.f (f (f x)→ 3

? ? ?

2.1.2. Maquina de Turing

Una maquina de TuringMaquina de Turing es un concepto abstracto creado para demostrar las limitacionesde la computacion. Ella trabaja por medio de estados, en el que cada estado es un pasodonde se realiza una accion. Aunque la maquina de Turing es un concepto abstracto, en lafigura 2.12 puede verse una representacion de ella.

Cabeza Máquina

Cinta

Símbolos

Figura 2.1: Maquina de Turing

2Para comprender mejor el concepto de la maquina de Turing se ha creado un software llamado JFLAPque puede descargarse gratis de http://www.jflap.org/

14

2.1 Comienzos

Una maquina de Turing esta conformada por:

1. Un cinta infinita donde seran escritos o leıdos los sımbolos del alfabeto.

2. Una cabeza para realizar la lectura y la escritura.

3. Un tabla de acciones que muestra las posibles transiciones que se pueden realizar.

4. Un registro de estados que almacena lo que ha pasado en la maquina.

En el ejemplo 2.1.2 se muestra una maquina de Turing.

Ejemplo 2.1.2Se tiene un alfabeto {0, 1 y #}, siendo # el sımbolo de espacio.

La cinta de la maquina arranca ası (la cabeza esta ubicada en el elemento subrayado):

# # 1 1 1 #

es decir, arranca con el numero 7 en binario, y se espera que se forme el numero 10 enbinario, es decir, el numero 1010.El conjunto de estados es {s1, s2}, y el estado inicial es s1. La tabla de acciones es lasiguiente:

Estado Simbolo Simbolo Nuevo

Actual Leido a Escribir Movimiento Estado

------ ------- ----------- ---------- ------

s1 # -> 1 Der. s2

s1 0 -> 1 Der. s2

s1 1 -> 0 Izq. s1

s2 # -> # Izq. s1

s2 0 -> 0 Der. s2

s2 1 -> 1 Der. s2

El computo de esta maquina de Turing podrıa resumirse en el siguiente registro de estados(la cabeza esta ubicada en la posicion del sımbolo subrayado):

15


Paso Estado Cinta

---- ------ -----

1 s1 ##111#

2 s1 ##110#

3 s1 ##100#

4 s1 ##000#

5 s2 #1000#

6 s2 #1000#

7 s2 #1000#

8 s2 #1000#

9 s1 #1000#

10 s2 #1001#

11 s1 #1001#

12 s1 #1000#

13 s2 #1010#

-- para --

? ? ?

Turing uso su maquina para demostrar que existen funciones que no son calculables pormedio de metodos definidos y en particular, que el problema de Hilbert era uno de esosproblemas. Ademas, demostro la equivalencia entre lo que se podıa calcular mediante unamaquina de Turing y lo que se podıa calcular con un sistema formal en general.

El resultado de las investigaciones de Church-Turing arrojo la existencia de algoritmosque con determinadas entradas nunca terminan (funciones totales) y ha servido como puntode partida para la investigacion de los problemas que se pueden resolver mediante unalgoritmo.

2.2. Problemas Tratables e Intratables

Los problemas denominados intratablesTratabilidad son aquellos que, con entradas grandes, no pue-den ser resueltos por ningun computador, no importa lo rapido que sea, cuanta memoriatenga o cuanto tiempo se le de para que lo resuelva. Lo anterior sucede debido a quelos algoritmos que existen para solucionar estos problemas tienen una complejidad muygrande.

La complejidadComplejidad de un algoritmo mide el grado u orden de crecimiento que tiene el tiempode ejecucion del algoritmo dado el tamano de la entrada que tenga.

Existen dos maneras rapidas de hallar la complejidad de un algoritmo (metodos masprofundos, formales y detallados pueden verse en [9]):

1. por conteo, o

16

2.2 Problemas Tratables e Intratables

2. por inspeccion o tanteo.

Para encontrar la complejidad de un algoritmo por conteo se debe tomar cada lınea decodigo y determinar cuantas veces se ejecuta. Luego se suman las cantidades encontradasy la complejidad sera del orden del resultado dado. Esta complejidad es una aproximacionde cuanto se demorarıa todo el algoritmo en ejecutarse.

Ejemplo 2.2.1Un primer ejemplo sencillo es el algoritmo 1 para imprimir los 100 primeros numerosnaturales.

void imprime100(){ int i = 1; while(i <= 100) { printf("%d",i); i++; }}

Algoritmo 1: Imprime los numeros del 1 al 100

El conteo de lıneas se puede realizar utilizando una tabla donde se numeren las lıneas decodigo y se determine el numero de veces que se ejecuta cada una:

Numero Lınea de codigo Numero dede lınea ejecuciones

1 void imprime100()

2 {

3 int i = 1; 14 while(i <= 100) 1015 {

6 printf("%d",i); 1007 i++; 1008 }

9 }

La lınea 3 se ejecuta una sola vez. La guarda del while (lınea 4) se ejecuta 101 vecesdebido a que verifica las 100 veces que se imprime el numero mas una vez adicional dondese determina que el ciclo ha terminado. Las lıneas internas del ciclo se ejecutan 100 veces.

La suma de las cantidades encontradas es3:3La lınea 1 no se tiene en cuenta ya que corresponde a los datos de referencia de la funcion (tipo de

17


Numero Total de Ejecuciones = 1 + 101 + 100 + 100 = 302

De allı que la complejidad del algoritmo es del orden de O(302). Por ser 302 una cons-tante, la complejidad se puede aproximar a O(1), esto es, afirmar que es una complejidadconstante.

? ? ?

Ejemplo 2.2.2El ejemplo anterior se puede generalizar modificando la funcion de manera que tenga comoparametro la cantidad de numeros naturales a imprimir, es decir, hasta que numero naturalse quiere escribir. Este nueva funcion se puede ver en el algoritmo 2.

void imprimeN(int n){ int i = 1; while(i <= n) { printf("%d",i); i++; }}

Algoritmo 2: Imprime los numeros del 1 al n

Se numeran las lıneas y se procede a contabilizar.


1 void imprimeN(int n)

2 {

3 int i = 1; 14 while(i <= n) n+ 15 {

6 printf("%d",i); n7 i++; n8 }

9 }

Al igual que el ejemplo 2.2.1, la lınea 3 se ejecuta una sola vez, la guarda del while (lınea4) se ejecuta n+ 1 veces y las lıneas internas del ciclo (lıneas 6 y 7) se ejecutan n veces.

retorno, nombre y parametros formales). Las lıneas 2, 5, 8 y 9 tampoco se tienen en cuenta ya que sonsimplmente delimitadores de bloque.

18


Ahora la suma de las cantidades encontradas es:

Numero Total de Ejecuciones = 1 + (n+ 1) + n+ n = 3n+ 2

En el caso en que n fuera un numero extremadamente grande, se puede ver que

3n+ 2 ≈ n

De esta manera la complejidad del algoritmo anterior es del orden de n, es decir, es O(n).

? ? ?

Ejemplo 2.2.3Otro ejemplo cuyo codigo es muy simple pero su analisis es de cuidado es el algoritmo 3.

void imprime_mitad(int n){ int i = n; while(i >= 0) { printf("%d",i); i = i / 2; }}

Algoritmo 3: Imprime los numeros del n al 1 dividiendo por dos cada vez

En primera instancia se podrıa decir que el programa deberıa imprimir los numeros desden hasta 0, pero dentro del ciclo el contador i se divide entre 2. Entonces en realidad seimprimiran los numeros n, n/2, n/4, n/8, . . .. De allı que el numero de veces que se ejecutanlas instrucciones dentro del ciclo van disminuyendo exponencialmente:

En la iteracion 1 se disminuye en 2.

En la iteracion 2 se disminuye en 4, es decir, 22.



...

En la iteracion k se disminuye en 2k.

Como se necesita saber cuantas veces se repite el ciclo y el contador cambia su valordesde 0 a n, entonces se requiere llegar al punto donde n = 2k, siendo k el numero queindica en que iteracion esta la ejecucion del algoritmo.

19


Para hallar el valor de k, se utilizan las propiedades de los logaritmos:

n = 2k

log2n = log22k

log2n = k

Luego el numero de iteraciones que se realizan es log2 n.


1 void imprime_mitad(int n):

2 {

3 int i = n; 14 while(i >= 0) log2 n+ 15 {

6 cout << i; log2 n7 i = i / 2; log2 n8 }

9 }

La suma de las cantidades encontradas es:

Numero Total de Ejecuciones = 1 + (log2n+ 1) + log2n+ log2n= 2 + 3log2n≈ log2n

Por lo tanto, la complejidad del algoritmo es O(log2n), que normalmente se expresa comoO(log n).

? ? ?

Ejemplo 2.2.4Cuando analizamos algoritmos con condicionales hay que tener en cuenta que el conteose hace considerando si las guardas de los condicionales se cumplen o no. La complejidaden estos algoritmos se halla en el peor de los casos (cuando se asume que las guardas delos condicionales siempre se cumplen), el caso promedio (cuando se asume que las guardasalgunas veces se cumplen y otras veces no) y el mejor de los casos (cuando se asume quelas guardas no se cumplen).

20


El algoritmo 4 suma los elementos impares de un vector de enteros.

int sumaVector(int *v, int n){ int i = 0; int sum = 0; while(i < n) { if(v[i] % 2 != 0) sum = sum + v[i]; i++; } return sum;}

Algoritmo 4: Suma los elementos impares de un vector de enteros



1 int sumaVector(int *v, int n)

2 {

3 int i = 0; 14 int sum = 0; 15 while(i < n) n+ 16 {

7 if(v[i] % 2 != 0) n8 sum = sum + v[i]; ?9 i++; n10 }

11 return sum;

12 }

La cantidad de veces que se ejecuta la lınea 8 es indefinida debido a que depende de sila guarda del condicional es verdadera o falsa. Por esta razon tenemos que analizar estasituacion desde los tres casos:

En el mejor de los casos ningun elemento del vector es impar por lo que la lınea 8 nose ejecutarıa nunca.

En el caso promedio, aproximadamente la mitad de los elementos sera impar y laotra mitad par. En este caso la lınea se ejecutarıa n/2 veces.

21


En el peor de los casos todos los elementos del vector son impares por lo que siempreque se ejecute la lınea 7 se ejecutara la lınea 8. Luego esta lınea se ejecutara n veces.

La suma de las cantidades encontradas es entonces:

En el mejor de los casos:

Numero Total de Ejecuciones = 1 + 1 + (n+ 1) + n+ 0 + n= 3 + 3n

En el caso promedio:

Numero Total de Ejecuciones = 1 + 1 + (n+ 1) + n+ n/2 + n= 3 + 7(n/2)

En el peor de los casos:

Numero Total de Ejecuciones = 1 + 1 + (n+ 1) + n+ n + n= 3 + 4n

Por lo tanto, la complejidad del algoritmo es, en este algoritmo particular, O(n).

? ? ?

Ejemplo 2.2.5Otro ejemplo, un poco mas complejo, es un algoritmo de ordenamiento de un vector deenteros:

void burbuja(int *v, int n){ int i = 0; while(i < n) { int j = i + 1; while(j < n) { if(v[i] > v[j]) { int temp = v[i]; v[i] = v[j]; v[j] = temp; } j++; } i++; }}

Algoritmo 5: Ordenamiento por el metodo burbuja

22




1 void burbuja(int *v, int n)

2 {

3 int i = 0; 14 while(i < n) n+ 15 {

6 int j = i+1; n7 while(j < n)

∑nk=1 k

8 {

9 if(v[i] > v[j]) (∑n

k=1 k)− n10 {

11 int temp = v[i]; (∑n

k=1 k)− n12 v[i] = v[j]; (

∑nk=1 k)− n

13 v[j] = temp; (∑n

k=1 k)− n14 }

15 j++; (∑n

k=1 k)− n16 }

17 i++; n18 }

19 }

La lınea 3 se ejecutara una sola vez. Solamente asigna el valor 0 a la variable i.Si el tamano del vector es n, entonces la guarda del ciclo externo (lınea 4) va ejecutarse

n+ 1 veces, ya que la variable i comienza el ciclo con el valor 0 y se incrementa en 1 cadaiteracion hasta que llegue al valor n, cuando se termina el ciclo. Sin embargo las lıneas 6y 17 se ejecutan n veces, es decir, uno menos que la lınea 4. Lo anterior debido a que sedebe verificar la guarda del ciclo una vez adicional para saber que ya no debe entrar masal ciclo.

La guarda del ciclo interno (lınea 7) se ejecutara un numero de veces que depende dela variable i, que en el ultimo ciclo tendra el valor del tamano del vector menos uno. Masen detalle, en la primera iteracion del ciclo externo la variable i es igual a 0, por lo quela guarda del ciclo interno se ejecuta n veces; en la segunda iteracion del ciclo externo lavariable i es igual a 1, por lo que la lınea 7 se ejecuta n− 1 veces; ası sucesıvamente hastala ultima iteracion del ciclo externo, donde la variable i es igual a n − 1 y la guarda delciclo interno se ejecuta 1 vez. Todo esto da como resultado una sumatoria del numero deejecuciones de la lınea 7, desde 1 hasta n.

Si consideramos el peor de los casos, al igual que paso con la lınea 6, la guarda del ify las asignaciones internas (lıneas 11–13) se ejecutan una vez menos que la guarda el ciclo

23


interno, es decir, la sumatoria del numero de ejecuciones desde 1 hasta n menos n (en cadaiteracion dichas lıneas se ejecutan 1 vez menos y en total son n iteraciones).

Por teorıa matematica, se tiene que

n∑i=1

i =n× (n+ 1)

2

De allı que es posible expresar el numero de ejecuciones solo en terminos de n:

Numero Total de Ejecuciones = (1) + (n+ 1) + (n) +(n×(n+1)

2

)+ . . .

. . .+ 5(n×(n+1)

2 − n)

+ (n)

= 2 + n+ 3n2

≈ n2

Y ası se puede decir que la complejidad del algoritmo burbuja es del orden de n2, esdecir, es O(n2).

? ? ?

Por otro lado, hallar la complejidad por inspeccion o tanteo, es mas rapida pero imprecisay, si no se cuenta con la suficiente experiencia, poco confiable.

Simplemente se mira la estructura del algoritmo y se siguen las tres siguientes reglas:

1. La complejidad de una asignacion es O(1).

2. La complejidad de un condicional es 1 mas el maximo entre la complejidad del cuerpodel condicional cuando la guarda es positiva y el cuerpo del condicional cuando laguarda es negativa.

3. La complejidad de un ciclo es el numero de veces que se ejecuta el ciclo multiplicadopor la complejidad del cuerpo del ciclo.

En el algoritmo 5 (burbuja) se puede observar que el ciclo externo tiene n iteraciones(siendo n el tamano del vector), el ciclo interno, en la primera iteracion del ciclo externo,tiene n iteraciones, y el condicional tiene como cuerpo tres asignaciones. Por todo esto, lacomplejidad del algoritmo serıa

O(1 + n× (2 + n× ((1 + 3) + 1))) = O(1 + 2n+ 5n2) ≈ O(n2).

Ahora, si las asignaciones internas y la condicion del if (las lıneas 5-8 juntas) tomaran unsegundo en ejecutarse, en el peor de los casos (cuando siempre se ejecute lo que esta dentrodel if) se tendrıa:

24


Tamano del vector Tiempo de ejecucion (seg.)

10 10020 40050 2500100 100001000 1000000

El cuadro anterior muestra que un algoritmo con complejidad O(n2) puede ser rapidopara tamanos de entrada pequenos, pero a medida que crece la entrada, se va volviendoineficiente.

En el cuadro 2.2 se muestran algunos ejemplos de complejidades que pueden encontrarseen los analisis de algoritmos, para un problema de tamano n, desde la mas rapida hastala mas ineficiente. Se dice que un problema es tratable si su complejidad es polinomial omenor.

Complejidad Nombre

O(1) Constante

O(log n) Logarıtmica

O(n) Lineal

O(n log n)

O(n2) Cuadratica

O(n3) Cubica

O(nc), c > 3 Polinomial

O(2n)

O(3n)

O(cn), c > 3 Exponencial

O(n!) Factorial

O(nn)

Cuadro 2.2: Complejidades

A partir de una complejidad O(2n), los problemas para los cuales hay un algoritmo condicha complejidad son intratables.

Existen otros problemas llamados “NP-Completos” NP-Completitud, cuya complejidad es desconocida.Se dice que son “NP” ya que se presume que los algoritmos que los solucionen son No-Polinomiales; sin embargo, no existe ninguna prueba que demuestre lo contrario, es decir,que sean “P” (Polinomiales)4. Los cientıficos creen que los problemas NP-Completos sonintratables, debido a que si existiera un algoritmo que resolviera alguno en un tiempopolinomial, entonces todos los problemas NP-Completos podrıan ser resueltos en un tiempo

4Aunque Vinay Deolalikar de los laboratorios de Hewlett Packart en el segundo semestre del 2010 com-partio una version preliminar de una prueba [10].

25


polinomial. Lo anterior llevo a los investigadores a plantear una de las mas importantespreguntas en las ciencias de la computacion [8]:

¿P = NP?

Es decir, ¿las clases de complejidades Polinomiales y las No-Polinomiales son equivalen-tes? El instituto de Matematicas Clay, en Cambridge, esta ofreciendo 1 millon de dolaresa quien de una demostracion formal de que P = NP o que P 6= NP.

2.3. Solucion de Problemas

Un problema en ciencias de la computacion se puede definir como un vacıo, que no hasido llenado, entre un estado inicial y un estado objetivo. Es decir, se esta en una situaciony se quiere llegar a otra, pero no se conoce el camino a ella. El ejemplo 2.3.1 muestra unproblema cotidiano.

Ejemplo 2.3.1Se tiene un estado inicial del juego Sudoku5, como en la figura 2.2.

68

2

1 43 5

56

1

86

7

4 7

9 1

63

4

57

42 65 8

29

7

Figura 2.2: Estado inicial del sudoku

El sudoku tiene una sola regla: Llenar la grilla de tal manera que cada fila, columna ycuadro de 3× 3 contenga los dıgitos del 1 al 9.

Aunque hay numeros en la grilla, no hay matematica envuelta. El problema se podrıaresolver con razonamiento y logica.

El estado final del problema serıa el mostrado en la figura 2.3.

? ? ?

Entonces surge la pregunta ¿como solucionar un problema?. La primera aproximaciones: “¡ como se pueda !”. Aunque esta respuesta es un poco rapida y brusca, es muy usada

5http://www.sudoku.com/

26

2.3 Solucion de Problemas

9 6 31 7 82 5 4

1 7 43 2 56 8 9

2 5 86 4 97 3 1

8 2 14 9 67 3 5

4 3 78 5 29 6 1

5 9 63 1 78 2 4

5 8 93 1 76 4 2

7 1 32 4 65 9 8

4 6 29 8 51 7 3

Figura 2.3: Estado final del sudoku

en estudiantes principiantes en la programacion quienes apenas reciben el problema loprimero que hacen es prender el computador y empezar a programar. Lo malo de estaaproximacion es que puede resultar en algoritmos muy ineficientes (con una complejidadde O(2n) o mayor).

G. Polya en [17] introdujo cuatro fases para solucionar un problema, y aunque fueronconcebidos para resolver problemas matematicos, no hay duda en la relacion directa quehay entre las matematicas y la computacion y su interes comun en la resolucion de muchosproblemas. Las cuatro fases son:

1. Entender el problema

2. Disenar un plan

3. Ejecutar el plan

4. Recapitular

Para entender el problema se deben hacer preguntas, pensar e investigar. Se debe pre-guntar por ejemplo quien propuso el problema, por que, de donde salio, a donde se quierellegar, cual es el objetivo. Se debe pensar para tener una idea mejor del problema como untodo y empezar a divisar la solucion. Por ultimo se debe investigar para saber quien masha trabajado en ese problema o quien esta trabajado en algo parecido, hay que leer libros,revistas y artıculos, pero en la solucion hay que referenciar todo lo que se investigo.

Ya entendido el problema se debe abordar el problema y disenar un plan para solucio-narlo. Si no es evidente un plan, se pueden seguir las siguientes estrategias:

Dividir el problema en subproblemas y atacar cada subproblema. Estrategia llamadadividir y conquistar, original de los romanos.

Si el problema es muy abstracto, tratar de examinar un ejemplo concreto (e.g. si nose sabe cuantas veces se ejecuta una lınea de codigo para una entrada n, se le puededar un valor: n = 10).

27


Tratar de resolver un problema mas general. Estrategia llamada la paradoja del in-ventor : entre mas ambicioso sea el plan mas opciones de exito.

Relajar un poco el problema de manera que se pueda encontrar una solucion facil-mente aunque no lleve a un plan correcto. El plan resultante sera una heurıstica, esdecir, una aproximacion que puede dar ideas o puede dar una solucion muy cercanaa la correcta.

Una vez tenga un plan para resolver el problema, es necesario buscar alternativas, esdecir, otros planes para llegar a la solucion. Usualmente existen varias alternativas desolucion, solo que es necesario analizar el problema de diferentes maneras (vease el ejemplo2.3.2). Muchas veces la alternativa mas ingenua puede ser la mas rapida y consisa. Despuesde tener una baraja de planes se puede escoger el mas acertado (la mejor solucion).

Ejemplo 2.3.2Se desea encontrar un numero e en una lista ordenada de numeros. ¿Como lograrlo?

La aproximacion mas ingenua es recorrer toda la lista, desde el primer elemento hastael final, buscando el numero e dado (vease la figura 2.4). Si el tamano de la lista esn, se puede ver que la implementacion de este metodo tomarıa un tiempo de O(n)en el peor de los casos (cuando el numero dado sea el ultimo elemento de la lista ono este en ella).

3 6 13 16 45 57. . . . . .

1 2 n-1 n

Figura 2.4: Busqueda lineal

Se puede optimizar la idea anterior haciendo dos recorridos, uno desde el principioy otro desde el final de la lista (vease la figura 2.5). De esta manera, el peor de loscasos serıa cuando el numero estuviera en la mitad de la lista. La busqueda entoncesno mejorarıa mucho, serıa O(n/2), que en el caso en que n fuera extremadamentegrande serıa equivalente a O(n).

3 6 13 16 45 57. . . . . .

1 2 n-1 n

Figura 2.5: Busqueda lineal bidireccional

28

2.3 Solucion de Problemas

Una idea mucho mas eficiente es la de hacer una busqueda binaria. Se parte la listaen dos (por la mitad), quedando una sublista con los numeros menores o iguales a unk y otra sublista con los numeros mayores a k. Entonces se hace la pregunta ¿e < k?Si la respuesta es positiva se procede a partir la sublista con los menores a k; de locontrario se hace lo mismo pero con la sublista con los mayores a k. De esta formase tiene una lista con una logitud igual a la mitad de la lista original y un nuevonumero k correspondiente al elemento de la mitad de la nueva lista. Se realiza elproceso anterior hasta que quede una lista con un solo elemento, el numero e queestaba buscando.

Un ejemplo de una busqueda binaria puede verse graficamente como en la figura 2.6.Se busca el numero 8.

1 3 5 6 8 9 10 14 16 20 30 45

1 3 5 6 8 9 10 14 16 20 30 45

1 3 5 6 8 9

6 8 9

6 8

Figura 2.6: Un ejemplo de busqueda binaria

Al partir la lista a la mitad cada vez, se reduce la busqueda primero en 2, luego en 4,en 8, en 16, y ası sucesivamente. Es decir que la complejidad del algoritmo terminasiendo O(log n).

Un ultimo metodo (de los muchos metodos posibles que hay y que no se veran aquı)para hacer la busqueda es convirtiendo la lista en una estructura de datos un pocomas compleja donde se manejen ındices para que, por medio de una llave, se llegue aun valor. Esta estructura de datos es llamada tabla hash y se vera mas a fondo en el

29


capıtulo 4.

Cada valor va a tener un ındice asociado. Dicho ındice es encontrado mediante unallave. Lo anterior indica que teniendo una funcion (denominada funcion hash) yaplicandola con la llave como argumento se devuelve el valor correspondiente, co-mo se muestra en la figura 2.7.

01

305

1920

6445

5657

8016

.

.

.

.

.

.

.

.

.

.

.

.

Índice ValorLlave

64

5

80

Figura 2.7: Busqueda con tabla hash

Para hacer mas facil el entendimiento de este metodo, es bueno pensar en como sebusca una empresa en las paginas amarillas del directorio telefonico. Teniendo lallave (que en este caso es el nombre de la empresa) se busca en el ındice la pagi-na correspondiente al negocio de la empresa (aseguradoras de riesgos profesionales,por ejemplo) y llendo a dicha pagina, allı se encuentra rapidamente los datos de laempresa.

La complejidad de los algoritmos de busqueda por medio de tablas hash es de O(1),es decir, es constante. Esto es debido a que la operacion para hallar el dato sola-mente aplica la funcion hash, esta halla el ındice, quien apunta directamente al datorequerido.

? ? ?

Finalmente se debe transformar la solucion potencial en un resultado mediante la ejecu-cion del plan y se debe recapitular para saber, entre otras cosas, como se puede mejorarla solucion descrita, si esta solucion puede usarse en otro problema, o para conocer lasdebilidades de la solucion.

30

2.4 Estrategias de Implementacion

Dentro de la teorıa de ingenierıa de software, cada una de las cuatro fases tiene unaetapa asociada en el ciclo de vida del software (vease [20]):

1. Analisis – Donde se levantan los requerimientos que debe satisfacer el sistema, sedebe estudiar la viabilidad del proyecto, y formalizar un acuerdo con el cliente.

2. Diseno – Donde se divide el problema en subproblemas o funciones, se identifican lassoluciones tecnologicas para cada una de las funciones, se asignan recursos ellas, y seajustan las especificaciones.

3. Implementacion – Donde se genera la solucion, se integran las funciones y se validala solucion mediante unas pruebas.

4. Mantenimiento – Donde se asegura el uso del sistema y se realiza la conservacion delsoftware.

2.4. Estrategias de Implementacion

Una vez se hace el analisis y el diseno de los algoritmos, la implementacion de los mismospuede ser abordado de dos maneras distintas:

Top-Down

Bottom-Up

En el modelo top-down se hace un manejo completo del sistema sin entrar en detalles.Se comienza sistema como un todo y cada una de sus partes son “cajas negras” que debenser abiertas poco a poco, a medida que se vaya internando en los detalles especıficos delproyecto. La gran ventaja de este modelo es que se divide el proyecto en subproyectos desdeel inicio de la implementacion. La desventaja es que no se pueden hacer pruebas a ningunaparte del proyecto casi que hasta el final.

En contraste, el modelo bottom-up las partes mas especiıficas del sistema son abordadasdesde el comienzo, y ellas, al irse enlazando, van forman el sistema completo. Al contrariodel modelo anterior, la ventaja de bottom-up es que puede hacerse un plan de pruebas desdeel inicio de la implementacion. La desventaja es que puede perderse de vista el objetivofinal del proceso.

El ejemplo 2.4.1 muestra el trabajo de realizar una aplicacion para la ensenanza delteorema del binomio desde los dos modelos.

Ejemplo 2.4.1Se desea crear una calculadora basica, es decir, con las operaciones aritmeticas fundamen-tales. A continuacion se vera el proceso de implementacion de la aplicacion desde los dosmodelos:

31


Top-DownSe comienza mirando la aplicacion como un todo. Si se piensa hacer una GUI (interfazgrafica de usuario), esta sera el paso inicial a realizar. Una posible interfaz graficapuede verse en la figura 2.8.

Archivo Ayuda

Calculadora X

7 8 9

4 5 6

1 2 3

.

/

*

-

+0

C

=

12345.67890

Figura 2.8: Ventana de una Calculadora

Se debe pensar en la especificacion del comportamiento esperado del programa: que ti-po de interfaz va a tener (grafica o texto), cuales seran las entradas al problema, cualesmenus habran en la ventana, si se hace click en algun lado de la ventana que va apasar, como va a estar dividida la ventana (si se piensa en dividirla como en la figura),que tipos de mensajes sacara la aplicacion (para comunicarse con el usuario), comorealizara las operaciones matematicas, etc.

La estructura de los modulos de la aplicacion, a grosso modo, podrıa ser como en lafigura 2.9.

Puede verse que el modulo principal de la aplicacion contiene la funcion para crear laventana. La ventana tiene las funciones de creacion de una barra de tıtulo, una barrade menus y un area de trabajo. Y continua profundizando hasta llegar a la funcionmas basica: MostrarTexto.

Bottom-UpSe comienza mirando cuales son las funciones mas sencillas que ayudaran a construirfunciones mas complejas.

Se debe pensar en las primitivas de bajo nivel y posibles operaciones a nivel dehardware que sean importantes y relevantes al problema: la funcion MostrarTexto esla operacion mas basica en este problema (dejando a un lado las operaciones graficasbasicas), las operaciones aritmeticas, la creacion de botones, la visualizacion de losmismos, los componentes de la ventana, las interrupciones de hardware y software,etc.

32

2.4 Estrategias de Implementacion

Principal

CrearVentana

CrearBarradeTitulo CrearBarradeMenu CrearEspaciodeTrabajo

CrearMenuArchivo CrearMenuAyuda

MostrarAyudaCrearMenuItemSalir

Salir

CrearBotonesCrearCampodeTexto

MostrarTexto

CrearBoton1 CrearBoton+ CrearBoton=. . . . . .

CalcularResultadoOperacionSuma

Figura 2.9: Creacion de funciones en el modelo top-down

La estructura de los modulos de la aplicacion, sin mucho detalle, podrıa ser como enla figura 2.10

Principal

CrearVentana

CrearBarradeTitulo CrearBarradeMenu CrearEspaciodeTrabajo

CrearMenuArchivo CrearMenuAyuda

MostrarAyudaCrearMenuItemSalir

Salir

CrearBotones

CrearCampodeTexto

MostrarTexto

CrearBoton1

CrearBoton+

CrearBoton=

. . . . . .

CalcularResultado

OperacionSumaMostrar1 Mostrar9 OperacionDivisión

CrearBoton+. . . . . .

CrearBoton9. . .

Figura 2.10: Creacion de funciones en el modelo bottom-up

? ? ?

33

3 Nocion de Lenguaje

“Un computador es un conjunto integrado de algoritmos y estructuras dedatos capaz de almacenar y ejecutar programas.”

En la definicion anterior (tomada de [18]), la cual es un poco diferente a la definicion decomputador que todos conocen, se destacan tres conceptos que forman la famosa ecuacionde Wirth:

programas = algoritmos + estructuras de datos

Un programa Programaes la implementacion de un algoritmo dados unos datos de entrada estruc-turados. Dicho algoritmo es desarrollado en un lenguaje de programacion.

Un lenguaje de programacion Lenguaje de Programacion, al igual que cualquier lenguaje, es un mecanismo de comu-nicacion compuesto por un vocabulario y un conjunto de reglas gramaticales. Su propositoes ordenarle al computador que realice una tarea especıfica.

Los lenguajes de programacion pueden hacer el desarrollo de programas mas facil o masdifıcil, dependiendo del nivel de abstraccion que requiera y la cantidad de conocimiento deltrabajo interno del computador que sea necesario para escribir los programas. Entre masfamiliar sea el lenguaje que se use para resolver los problemas, su nivel sera mas alto.

En este capıtulo se presentara una descripcion de la teorıa de los lenguajes que permitenla especificacion de la solucion de los problemas en terminos relativamente mas cercanos alos usados por las personas, y en particular el lenguaje C++, el cual sera usado en el restodel documento.

3.1. Historia

La historia de los lenguajes de programacion se ha dividido en cuatro generaciones1:

Primera Generacion Lenguajes de maquina, que se reduce a secuencias de numeros bina-rios.

Segunda Generacion Lenguajes ensambladores, que tienen instrucciones de bajo nivel,bastante basicos pero menos abstracto que el lenguaje de maquina. (en la figura 3.5se muestra un ejemplo de codigo en lenguaje ensamblador).

1Algunos autores hablan de una quinta generacion de lenguajes, los cuales son usados para resolver proble-mas mediante la especificacion de programas con restricciones o formulas logicas en vez de algoritmos.Ejemplos de estos lenguajes son: MoZArt, Prolog y Mercury.

35


Tercera Generacion Lenguajes de alto nivel, con sintaxis mas cercana al lenguaje natural.Algunos de estos lenguajes pueden verse en la figura 3.1.

Cuarta Generacion Lenguajes disenados para desarrollar aplicaciones requeridas en am-bientes empresariales y de negocios. SQL, Oracle Reports, Mathematica, MATLAB,son algunos de estos lenguajes.

En los anos 50’s, cuando la tecnologıa permitio el desarrollo de computadores mas fami-liares, J. Backus creo el lenguaje de programacion FORTRAN (FORmula TRANslation).Este lenguaje es considerado el primer lenguaje de alto nivel y aun es usado por matemati-cos y cientıficos.

La evolucion de los lenguajes de programacion se ha debido a cinco influencias principales[18]:

1. El hardware y los sistemas operativos – El hardware es cada vez mas facil de usar(PC’s y Tablets) y los sistemas operativos mas graficos y amigables (basados enventanas).

2. Las aplicaciones – Desde las militares, cientıficas, de negocios e industriales, hastalos juegos, personales y de todo tipo de actividades humanas.

3. Las metodologıas – Para desarrollar programas mas complejos y con nuevos disenos.

4. Los estudios teoricos – Nuevos metodos formales matematicos que soporten las ca-racterısticas de los lenguajes.

5. Las estandarizaciones – La posibilidad de implementar los lenguajes en cualquiersistema y permitir transportar los programas de un computador a otro.

En la figura 3.12 se puede apreciar la evolucion de los mas conocidos lenguajes de pro-gramacion de alto nivel, desde FORTRAN hasta C#.

B. Kinnersley ha hecho un listado de mas de 25003 lenguajes de programacion, que hansido desarrollados a lo largo de la historia. Muchos de estos lenguajes ya no se usan mientrasque otros como FORTRAN y LISP siguen siendo utilizados constantemente. Terrece Pratten [18] describe las caracterısticas que enmarcan los lenguajes en usados y no usados:

Claridad – La sintaxis del lenguaje debe ser facil para leer, escribir, probar, entendery modificar los programas que se escriban en el.

Aplicacion – El lenguaje debe proveer estructuras de datos, operaciones y estructurasde control para resolver uno o varios tipos especıficos de problemas.

2Una version mas detallada de la evolucion de los lenguajes ha sido creada por Eric Levenez y puede verseen http://www.levenez.com/lang/history.html.

3El listado puede consultarse en http://people.ku.edu/~nkinners/LangList/Extras/langlist.htm.

36

http://www.levenez.com/lang/history.html

http://people.ku.edu/~nkinners/LangList/Extras/langlist.htm

3.1 Historia

FORTRAN 1954

1958

1959

1962

1964

1968

1969

1970

1971

1973

1975

1977

1978

1979

1982

1983

1984

1986

1987

1988

1989

1991

1993

1995

1996

1999

2000

LISP ALGOL

COBOL

SNOBOL

BASIC SIMULA

LOGO FORTH

SMALLTALK SH

PROLOGPASCAL

C

ML

SCHEME MS BASIC MODULA

ICON

AWK

ADA

MIRANDA POSTSCRIPT

C++

COMMON LISP

EIFFEL

HASKELL CAML PERL

TURBO PASCAL TCL/TK

OZCLOS

VISUAL BASIC PYTHON

RUBY

DELPHI JAVA JAVASCRIPT PHP

OCAML

MOZART

C#

Figura 3.1: Evolucion de los lenguajes de alto nivel

37


Soporte – Se debe ayudar al programador a solucionar problemas mediante el lenguajecon API’s (interfaces para programar aplicaciones) y grupos de desarrollo.

Verificacion – La posibilidad de verificar la correctitud de un programa mediantevarias tecnicas.

Ambiente – Un ambiente de programacion (con editor y paquetes de depuracion)puede acelerar la creacion de programas.

Costo – De uso, ejecucion, traduccion, creacion, pruebas y mantenimiento de losprogramas.

Portabilidad – El transporte de los programas, del computador donde fue creado aotros sistemas.

3.2. Estructura

Los lenguajes de programacion de alto nivel tienen seis caracterısticas:

1. Datos - Tipos de datos

2. Operaciones primitivas

3. Secuencias de control

4. Datos de control

5. Almacenamiento

6. Interaccion con el ambiente

Al igual que cualquier lenguaje (como el espanol), los lenguajes de programacion tienenuna sintaxis y una semantica. La sintaxis es la forma en que los programas son escritosmientras que la semantica es el significado dado a las construcciones sintacticas.

Cada lenguaje de programacion tiene una sintaxis y una semantica particular. Por ejem-plo, mientras en Pascal la deficion de una variable de tipo lista de reales es

var V: array [1..10] of real;

en C es

float V[10];

La sintaxisSintaxis de un lenguaje, esta definida entonces como la escongencia y organizacion devarios elementos sintacticos basicos. Dichos elementos pueden ser caracteres, identificado-res, operadores, palabras reservadas, comentarios, espacios en blanco y delimitadores.

38

3.2 Estructura

Los elementos forman expresiones, declaraciones y, en general, la estructura de un progra-ma. Formalmente, la organizacion de esos elementos construyen la gramatica del lenguaje,que consta de un conjunto de definiciones (llamadas reglas o producciones) que especifi-can el orden particular en que deben estar ubicados los elementos para que un programaeste bien escrito.

La forma mas usada para especificar la gramatica de un lenguaje es la BNF (Backus-Naur Form), desarrollada por J. Backus en 1960. La BNF define un lenguaje de una maneradirecta. Por ejemplo para describir una variable o identificador en C++, se lista la estruc-tura4:

identificador ::= (letra | "_")

| identificador (letra | "_")

| identificador digito

letra ::= mayusculas | minusculas

minusculas ::= "a"..."z"

mayusculas ::= "A"..."Z"

digito ::= "0"..."9"

Un identificador en C++ es la composicion de una letra o una raya (el sımbolo ” ”,tambien llamado underscore), con cero o varias letras, digitos o rayas. Una letra puede sermayuscula o minuscula. Las minusculas, mayusculas y los dıgitos estan allı.

Si se fuera a definir una asignacion simple (solo con enteros y expresiones aritmeticasbasicas), se tendrıa:

asignacion ::= identificador "=" exp_aritmetica ";"

exp_aritmetica ::= entero | identificador

| exp_aritmetica "+" exp_aritmetica

| exp_aritmetica "-" exp_aritmetica

| exp_aritmetica "*" exp_aritmetica

| exp_aritmetica "/" exp_aritmetica

entero ::= digitos_sin_cero digito* | "0"

digitos_sin_cero ::= "1"..."9"

4La descripcion completa de la BNF de C++ puede encontrarse en http://www.nongnu.org/hcb/

39

http://www.nongnu.org/hcb/


Al igual que en cualquier lenguaje, para asegurar que una expresion esta bien escrita,lo que se debe hacer es seguir la BNF de forma estricta. El ejemplo 3.2.1 muestra unaasignacion y su analisis correspondiente.

Ejemplo 3.2.1¿La expresion W = Y * 10 + V; es sintacticamente correcta?

La figura 3.2 muestra el analisis dada la gramatica anterior.

W = Y * 10 + V

identificador identificador identificador

exp_aritmetica

entero

digitodigito_sin_cero

exp_aritmetica

asignacion

;

exp_aritmetica

exp_aritmetica

exp_aritmetica

Figura 3.2: Analisis para la asignacion

Por lo tanto, sı es correcta la expresion.

? ? ?

Por otro lado, la semanticaSemantica del lenguaje hace otro tipo de verificacion. Ella chequeaprincipalmente:

1. Los tipos – Se verifica que los operadores sean aplicados a los operandos correctos;por ejemplo, la division entre una lista y un entero no tiene sentido.

40

3.3 Compiladores

2. El control de flujo – Se asegura que los comandos que causan un rompimiento en elflujo de control (como el comando break) transfieran el flujo a otro lugar.

3. La unicidad – No deben haber variables y etiquetas diferentes con el mismo identifi-cador.

3.3. Compiladores

Los lenguajes de programacion se implementan mediante traductores o compiladores Compiladorque

convierten el codigo fuente en un codigo objetivo (que puede ser un codigo intermedio ocodigo de maquina). En la figura 3.3 (figura tomada de [1]) se puede ver la forma superficialde un compilador.

códigofuente

mensajesde error

códigoobjetivocompilador

Figura 3.3: Componentes superficiales de un compilador

Para hacer la traduccion del programa, varias etapas deben ser superadas, las cualespueden verse como los componentes intermedios del compilador. Dichas etapas son el pre-procesamiento, el compilador como tal, el ensamblador y los enlazadores y cargadores.

Como el codigo fuente puede estar dividido en varios archivos diferentes o modulos, ypueden haber macros y extensiones necesarias para el programa, todos estos componentesdeben ser recolectados para tener un unico programa fuente. Esta etapa es denominadapreprocesamiento.

El codigo ensamblador es una version menos abstracta del codigo de maquina, que esel entendido por el procesador del computador. Este codigo trabaja directamente con di-recciones de memoria de la RAM, los registros del procesador, la pila del programa y lasinterrupciones del sistema operativo. Cada procesador tiene un conjunto de instruccionesque constituyen el lenguaje ensamblador. En [4] puede verse las instrucciones para losprocesadores Intel desde el 8086 hasta el 80486 (las generaciones antes de los Pentium).

Los enlazadores y cargadores realizan las funciones de cargar y enlazar codigo intermedioy librerıas ya creadas (e.g. archivos *.dll en windows, o *.so y *.a en linux) al programaque se esta traduciendo.

41


El sistema de procesamiento de compilacion (los componentes intermedios del compila-dor) puede verse en la figura 3.4 (figura adaptada de [1]).

preprocesador

compilador

ensamblador

enlazadorcargador

módulos de programa fuente

programa fuente

programa ensamblador

código objeto

código de máquina

libreríascódigo objeto

Figura 3.4: Componentes intermedios de un compilador

Una vez pasado el ensamblador, el codigo objeto generado puede usarse como librerıapara otros programas. Esto es posible debido a que los componentes intermedios del compi-lador son separables, es decir, el proceso de compilacion puede hacerse paso a paso, tomandocada uno de los componentes como aplicaciones separadas y trabajandolos manualmente.

Conceptualmente, el proceso de transformar el programa fuente en un programa en-samblador se puede descomponer en seis fases: analisis lexico, analisis sintactico, analisissemantico, generacion de codigo intermedio, optimizacion y generador de codigo.

42

3.3 Compiladores

W = Y * 10 + V;

Analizador Léxico

Analizador Sintáctico

Analizador Semántico

Generador de Código Intermedio

Generador de Código

Optimizador

id1 = id2 * 10 + id3

id1

id2

id3

=

+

*

10

id1

id2

id3

=

+

*

10

temp1 = 10temp2 = id2 * temp1temp3 = id3 + temp2id1 = temp3

temp = id2 * 10id1 = id3 + temp

MOV AL, id2MOV BL, 10MUL BLMOV CL, id3ADD AL, CLMOV id1, AL

Figura 3.5: Ejemplo de las fases de compilacion

43


En el analisis lexico se hace un escaneo de los caracteres que tiene el programa en busca desımbolos que no hacen parte del alfabeto del lenguaje. Una vez que un grupo de caracteresque conforman un elemento sintactico basico es escaneado y aprobado, dicho elemento espasado como un token al analizador sintactico. Los espacios en blanco que separan lostokens son eliminados en esta fase.

El analizador sintactico se encarga de crear un arbol con cada uno de los tokens paracomparar las expresiones con la BNF del lenguaje. Un ejemplo de arbol es el de la figura3.2.

Como se vio anteriormente la fase de analisis semantico chequea el programa fuente paraencontrar errores de tipos de datos, de control de flujo y de unicidad.

Una vez las fases de analisis son superadas, algunos compiladores generan un codigointermedio. Este codigo sirve para que el compilador decida el orden de operacion de laslıneas de codigo y para generar nombres temporales que mantengan su valor calculado porcada instruccion.

La fase de optimizacion intenta mejorar el codigo intermedio para obtener mejores re-sultados en rendimiento.

La ultima fase es la generacion del codigo objetivo, que usualmente consiste en codigoensamblador.

La figura 3.5 (adaptada de [1]) muestra un ejemplo de una compilacion de la expresiondel ejemplo 3.2.1.

Comienza el analizador lexico transformando la expresion inicial en una expresion ba-sada en tokens, luego el analizador sintactico construye el arbol de sintaxis, en seguida elanalizador semantico hace la verificacion (en este caso no hay errores semanticos por loque queda igual), entonces el generador de codigo intermedio pone los nombres temporalesy ordena las operaciones, acto seguido el optimizador reduce el numero de operaciones, ypor ultimo el generador de codigo retorna el codigo ensamblador correspondiente.

3.4. Maquinas Virtuales

El codigo objetivo de un compilador es ejecutado en interpretadores los cuales puedenser hardware o maquinas reales, o software en cuyo caso son llamadas maquinas virtualesMaquina Virtual .

Las maquinas virtuales son ambientes de ejecucion que emulan o actuan como interfaz deun computador o programa. Ellas proveen las instrucciones para comunicarse directamentecon el computador o programa que esten emulando.

Los interpretadores tienen una maquina virtual del computador local donde ejecutan losprogramas sin necesidad de crear archivos ejecutables. De esta manera, la maquina virtualse encarga de tomar el codigo intermedio y hacer la traduccion al codigo de maquina delcomputador fısico y devolver el resultado. Ası las maquinas virtuales podrıan verse comowrappers o funciones envolventes que encapsulan las instrucciones reales de los computado-res o programas que emulan.

44

3.4 Maquinas Virtuales

Algunos lenguajes de programacion interpretados son Java, Forth, Fortran, Perl, Lisp,Scheme, Smalltalk y Python.

Por otro lado, lenguajes de programacion como Java poseen una maquina abstracta peroal nivel del sistema operativo5. Esto da pie al concepto de portabilidad. Una de las grandesventajas de Java es que el codigo fuente que se escribe en el puede ser compilado y ejecutadoen cualquier sistema operativo, ya sea Linux, Windows, MacOS, Solaris, o algunos otros.La desventaja es que el hecho de que ya sean dos capas que tienen que emularse (sistemaoperativo y hardware) tiene repercusiones en el rendimiento de los programas. De allı quemuchos programadores evitan programar en Java, ya que los programas les corren maslento que en lenguajes compilados como C.

Computador Físico (Hardware)

Sistemas Operativos

Lenguaje deProgramación

Programa

Datos deEntrada

Datos deSalida

Figura 3.6: Jerarquıa de las maquinas virtuales

La figura 3.6 (adaptada de [18]) muestra la jerarquıa de maquinas virtuales. Ademas delas maquinas virtuales al nivel del hardware y el sistema operativo, los lenguaje de progra-

5Existen programas que emulan todo el sistema operativo. En Linux, por ejemplo, programas como wine(http://www.winehq.org/) y crossover (http://www.codeweavers.com/) pueden correr programas he-chos en Windows, mientras que vmware (http://www.vmware.com/) puede lanzar todo el sistema ope-rativo Windows encima de Linux.

45

http://www.winehq.org/

http://www.codeweavers.com/

http://www.vmware.com/


macion y los programas que se escriben pueden verse tambien como maquinas virtuales. Ellenguaje de programacion funciona como interfaz entre lo que el programador quiere hacery el sistema operativo, mientras que el programa funciona como interfaz entre el usuario yel lenguaje de programacion.

3.5. Depuracion

DepuracionDepuracion es el proceso de encontrar y reducir el numero de bugs, es decir, errores,faltas, fallas o equivocaciones, en un programa.

El termino bug tiene su origen en la marina de Estados Unidos en 1945, cuando seencontro una polilla que causaba un corto circuito en las pruebas que se le hacıan al panelde un computador electromecanico. Los operadores incluyeron el insecto en su bitacora depruebas que puede verse en la figura 3.7.

Figura 3.7: Primer bug encontrado

46

3.5 Depuracion

B. Beizer en [3] categoriza los bugs en:

1. Suaves – Solo ofenden esteticamente. Mala indentacion, mala ortografıa, entre otros.

2. Moderados – Salidas redundantes que generan un impacto leve en el rendimiento delsistema.

3. Molestos – El comportamiento del sistema, por culpa del bug, es desagradable.

4. Perturbantes – Se rechazan operaciones normales.

5. Serios – Se pierde el rastro de las operaciones.

6. Muy serios – El bug causa que el sistema haga operaciones erradas.

7. Extremos – Los problemas anteriores ocurren frecuentemente y arbitrariamente, y nosolo en casos aislados.

8. Intolerables – La base de datos empieza a tener datos corruptos e irreparables. Seconsidera seriamente bajar el sistema.

9. Catastroficos – El sistema falla completamente.

10. Infecciosos – La falla del sistema tiene repercusiones en otros sistemas.

El proceso de depuracion puede dividirse en cinco etapas:

Reconocer que el bug existe:

Si el error causa que el programa termine de forma abrupta, entonces es obvia la existen-cia del bug. Sin embargo, a medida que el error sea menos serio, la dificultad de detectarlo esmucho mayor, llegando al punto de pasar desapercibido. Por ejemplo, en 1994, T. Nicely dela Universidad de Lynchburg descubrio un error en los procesadores Intel. El se dio cuentaque algunas divisiones siempre devolvıan un valor errado. Inicialmente Intel nego el error,pero otras personas confirmaron el problema rapidamente y mas tarde Intel tuvo que sus-tituir todos los procesadores defectuosos (algunos modelos del Pentium con una frecuencia

47


de menos de 100 MHz). Para comprobar el error se puede ejecutar el algoritmo 6.

#include <stdio.h>

int main(void){ float x = 8391667.0; float y = 1572863.0; if(x - (x / y) * y != 0) printf("Procesador con el error de division del Pentium."); else printf("Procesador sin el error de division del Pentium."); return 0;}

Algoritmo 6: Descubre si el procesador tiene error

Se deben identificar entonces, los sıntomas del bug, observar el problema y bajo que con-diciones es detectado.

Aislar la fuente del bug :

Se debe identificar que parte del codigo genera el bug. Esto puede resultar muy difıcilde hacer debido a que, por ejemplo, creyendo que una lınea de codigo tiene el problema,puede que dicha lınea genera el problema como resultado de errores en una funcion queesta en otro modulo del programa.

Los programadores menos experimentados deben seguir la ejecucion del programa pasoa paso, lınea a lınea, reconociendo en el flujo del programa una discontinuidad, compor-tamiento errado, o discrepancia. Los programadores habiles pueden reconocer a priori enque area del codigo puede estar el problema (basado en previas situaciones similares).

Para lograr aislar el bug se debe mirar el codigo como algo nuevo. Un error comun quecometen los programadores es pasar por alto secuencias, asignaciones, etc. ya que conocenmuy bien el codigo y asumen la correctitud de ciertas partes. Ademas, el uso de instruc-ciones como print, assert y el cambiar pequenos detalles del programa pueden ayudarbastante (hay que tener en cuenta que se debe cambiar una cosa a la vez y volver atras loscambios que no tengan efecto).

Identificar la causa del bug :

Si ya se sabe donde esta el bug, se debe investigar la causa del mismo. El buen cono-cimiento del programa, tanto es su funcionamiento como en su estructura interna es muyimportante para descubrir la causa del bug. Un programador que no este familiarizado conel codigo puede gastar muchas horas inutilmente mientras el creador del programa podrıadecidir rapidamente que la causa es externa al codigo.

Existen herramientas para ayudar a descubrir las causas de un bug. Una de ellas es DDD6,

6http://www.gnu.org/software/ddd/

48

http://www.gnu.org/software/ddd/

3.5 Depuracion

un software que actua como front-end para depuradores de diferentes lenguajes como C,Perl, Python, y Java. La idea de este tipo de debuggers es usar breakpoints o puntos clavedel programa donde se necesite hacer un seguimiento detallado de variables, funciones oestructuras (este seguimiento se hace mediante watchers). La figura 3.8 (figura tomada dehttp://www.gnu.org/software/ddd/) muestra la ventana de DDD con un programa paramanejar listas hecho en C.

Figura 3.8: Data Display Debugger

Idealmente se debe prevenir cualquier posibilidad de bugs, es decir, diagnosticar y deter-

49

http://www.gnu.org/software/ddd/


minar los errores pre-mortem. Para ello es bueno trabajar con bitacoras (archivos log), demanera que se tenga un rastro de los cambios realizados. Tambien es recomendable usarun sistema de control de versiones (CVS7 o Subversion8, por ejemplo) para que ası seaposible regresar a versiones anteriores estables cuando se requiera. Adicionalmente, para lamayorıa de los compiladores actuales existen editores que ayudan a la prevencion de erroressintacticos y semanticos, mediante el coloreo de palabras reservadas, variables, funcionesy demas estructuras, el chequeo automatico e incluso la opcion de depuracion. Un editormuy usado para Java y C/C++ es Eclipse9 (que puede verse en la figura 3.9).

Figura 3.9: Editor Eclipse

Determinar una correccion para el bug :

La tarea de encontrar como corregir un bug no es sencilla por varias razones:

7http://www.nongnu.org/cvs/8http://subversion.tigris.org/9http://www.eclipse.org/

50

http://www.nongnu.org/cvs/

http://subversion.tigris.org/

3.5 Depuracion

Se puede alterar significativamente el sistema, tanto en su funcionamiento como ensu rendimiento.

Se pueden destapar errores mucho mas profundos o complicados.

Se pueden crear nuevos errores.

Los errores logicos son los mas sencillos de corregir debido a que son equivocaciones enla implementacion. Los errores que son resultado de un mal diseno del software puedenacarrear no una correccion sino una reimplementacion parcial o completa del programa.

En programas que son hechos de forma modular o con carga dinamica, es posible crearlos denominados patches. Gracias a ellos no es necesario recompilar todo el programa sinosimplemente un modulo o librerıa. De esta manera, lo que se hace es reemplazar los archi-vos necesarios sin alterar todo el sistema.

Aplicar la correccion y hacer pruebas:Cuando se aplica la correccion al problema es necesario crear un plan de pruebas riguroso

y llevarlo a cabo para asegurarse que dicha correccion ha tratado el bug de forma correcta.Se pueden usar tres diferentes aproximaciones para demostrar que un programa esta libre

de bugs [3]:

Prueba Funcional - Se debe pensar en todas las entradas posibles y blindar el programapara que soporte las entradas y produzca la salida correcta para cada una de ellas(un resultado o un mensaje de texto). Desafortunadamente, incluso teoricamente,es imposible conocer todas las entradas posibles ya que son infinitas, de allı que noes posible realizar una prueba funcional completa, por lo que se debe minimizar elnumero de entradas que se dejen por fuera de la prueba.

La prueba funcional es tambien llamada prueba de caja negra, ya que el ingeniero depruebas solo tiene acceso al software mediante las mismas interfaces que el usuarionormal.

Prueba Estructural - Se miran los detalles de implementacion, es decir, el estilo de pro-gramacion, los metodos de control, el codigo fuente, el diseno de la base de datos, yla estructura general.

La prueba estructural es denominada prueba de caja blanca. El desarrollador tieneacceso al codigo fuente y puede modificar el codigo para realizar dichas pruebas.

Prueba de Correctitud - Los requerimientos del programa son declarados en un lenguajeformal (matematico) de manera que puedan hacerse demostraciones inductivas paraproducir los resultados de todas las posibles entradas.

Cada funcion en el programa tiene una precondicion y un postcondicion, expresadasen terminos logicos. Adicionalmente, en los ciclos se tiene una invariante (un conjuntode caracterısticas que nunca cambia mientras se desarrolla el ciclo). Lo que se hace

51


es que se toma la precondicion y, mediante una serie de pasos, la entrada dada y lasinvariantes que puedan existir, se debe llegar a la postcondicion (para mas detallesse puede ver [7]).

Las caracterısticas de las pruebas y la madurez del programa llevan a dos fases o versionesen el ciclo de vida del software antes de ser liberado: alpha y beta.

Mientras los desarrolladores estan creando el programa y hacen pruebas solo ellos, elprograma esta en su version alpha. Las pruebas que se realizan aquı normalmente son decaja blanca, aunque por inspeccion tambien se hacen pruebas de caja negra. En esta etapa,el software es peligroso para usuarios finales.

Una vez se tenga cierta estabilidad en el programa, el desarrollo entra en la fase beta. Sellaman a los ingenieros de prueba a que realicen pruebas de caja negra. Adicionalmente,un grupo de personas es escogido (usuarios finales pero con un nivel un poco mas alto)para que usen el programa y reporten bugs.

Algunas personas han considerado una tercera fase denominada gamma. En esta faseel software tiene la madurez para ser liberado pero puede contener errores (aun esta enpruebas). De hecho muchas aplicaciones son lanzadas en etapa gamma ya sea porque se creeque esta libre de bugs o porque los mismos programadores han escogido a sus compradoresy clientes para que prueben el software mientras lo usan. Algunas de las grandes empresasde software han usado esta ultima estrategia para sus productos.

3.6. Excepciones

Los manejadores de excepcionesExcepcion son construcciones disenadas para tratar la ocurrencia desituaciones que cambian el flujo normal de la ejecucion de un programa. Las excepciones sonla analogıa en software de lo que son las interrupciones10 en hardware. Ellas se dividen ensıncronas y asıncronas. Las excepciones sıncronas son aquellas que son planeadas, mientraslas asıncronas son aquellas inesperadas.

Las excepciones mas comunes en programacion son la division por cero, los nombres nodefinidos, la incompatibilidad de tipos y la ausencia de archivos, directorios o paginas web.

El algoritmo 7 en C++ muestra un pequeno programa que divide el numero 10 entre unnumero dado por el usuario.

10Las interrupciones son senales que emiten algunos dispositivos y que causan que el procesador haga unapausa en la ejecucion, salve el estado y comience una nueva ejecucion.

52

3.6 Excepciones

#include <iostream>using namespace std;

int main(){ int numero,resultado;

cout << "Entre el divisor: "; cin >> numero; resultado = 10/numero; cout << resultado << endl;

return 0;}

Algoritmo 7: Divide el numero 10 entre un numero dado por el usuario en C++

Si el usuario ingresa el cero, entonces la division se vuelve imposible y una excepcionsurgira. La primera forma posible para evitar este inconveniente es usar un condicional. Elalgoritmo 8 muestra como quedarıa.



cout << "Entre el divisor: "; cin >> numero; if(numero != 0) { resultado = 10/numero; cout << resultado << endl; } else { cerr << "Division por cero" << endl; return 1; } return 0;}

Algoritmo 8: Divide el numero 10 entre un numero dado por el usuario, usando uncondicional en C++

Tambien podemos hacer uso de las aserciones. El algoritmo 9 muestra su uso. La macroassert no retorna nada pero tiene un argumento de tipo entero que representa la pruebaque se realizara. Si la prueba falla entonces un mensaje de error surge y el programa

53


termina, de lo contrario el flujo de ejecucion continua normalmente.

#include <iostream>#include <cassert>using namespace std;


cout << "Entre el divisor; "; cin >> numero; assert(numero != 0); resultado = 10/numero; cout << resultado << endl;

return 0;}

Algoritmo 9: Divide el numero 10 entre un numero dado por el usuario, usando unaasercion en C++



cout << "Entre el divisor: "; cin >> numero; try { if(numero == 0) throw 1; resultado = 10/numero; cout << resultado << endl; } catch(int) { cerr << "Division por cero" << endl; } return 0;}

Algoritmo 10: Divide el numero 10 entre un numero dado por el usuario, usando unmanejador de excepciones en C++

Sin embargo contemplar todos los posibles errores que puedan suceder (no solo de estetipo) es una tarea dispendiosa que atrasa la programacion y desvıa al programador de suobjetivo. Ademas, los metodos anteriores no permiten una gestion apropiada de los erroresgenerados. Ası que el codigo tambien podrıa ser modificado con mecanismos de manejo de

54

3.6 Excepciones

excepciones, como en el algoritmo 10.

El bloque try ... catch ... define un espacio de prueba y una alternativa de salidaa una falla. Si el codigo que esta en el bloque try no lanza una excepcion (por medio delcomando throw) entonces el programa continua saltandose el catch; En caso contrario, sedesecha lo que se hizo dentro del try, se ejecuta el bloque del catch y continua el programa.

La pregunta natural que surge entonces es ¿cuando se usan las excepciones? Aunque losmanejadores de excepciones pueden ser usados para tratar con errores normales e inclusopara depuracion, muchos programadores estan deacuerdo en que a menos que no se tengauna muy buena razon para atrapar una excepcion, no se haga. Esto es debido a dos razones,primero se supone que las excepciones son “excepcionales”, lo que implica que no se debellenar el codigo de excepciones, y segundo, cuando se ejecuta el codigo, cada vez que seimplementa un manejador de excepciones, el procesador guarda el estado del programa enese momento para poder continuar la ejecucion de cualquier manera.



cout << "Entre el divisor: "; cin >> numero; try { if(numero == 0) throw 1; if(numero == 134514992) // No es un numero throw string("letra"); resultado = 10/numero; cout << resultado << endl; } catch(int) { cerr << "Division por cero" << endl; } catch(string) { cerr << "No entro un numero" << endl; } return 0;}

Algoritmo 11: Divide el numero 10 entre un numero dado por el usuario, usando dosmanejadores de excepciones en C++

Otras razones para tener en cuenta cuando se usen las excepciones son:

Muchas veces los errores que atrapan los manejadores de excepciones pueden sercorregidos cuando se esta escribiendo el programa. Por ejemplo, si un archivo va aser modificado pero este es de solo lectura, una excepcion ocurrira en el programa.

55


Este error es facilmente corregible simplemente cambiando los permisos del archivo.

Se debe proveer la mayor informacion posible cuando una excepcion ocurre. Porejemplo, cuando se intenta acceder a una pagina web y falla, se puede dar detallesacerca de por que fallo: DNS invalido, time out, usuario no autorizado.

Es bueno implementar manejadores de excepciones especıficos. De esta manera elcompilador esta optimizado para tratar con la excepcion dada: de valor, de ejecucion,de tipo, de nombre, de entrada/salida, etc. Si en el ejemplo de la division por cerose entra una cadena o un letra (representando un identificador) en vez de un numerohabran otros tipos de excepciones que pueden ser manejados separadamente como enel algoritmo 11.

Hay que asegurarse de que el codigo siga ejecutandose aun si ocurren errores. En elcodigo de la division entre cero puede asegurarse la continuacion de dos maneras:creando un ciclo que pida el numero de nuevo cada vez que se entre un cero, o susti-tuyendo el cero por un numero por defecto. Los algoritmos 12 y 13 muestran las dosalternativas.

// Alternativa 1:#include <iostream>using namespace std;

void division() { int numero,resultado;

cout << "Entre el divisor: "; cin >> numero; try { if(numero == 0) throw 1; resultado = 10/numero; cout << resultado << endl; } catch(int) { cerr << "Division por cero" << endl; division(); }}

int main() { division(); return 0;}

Algoritmo 12: Divide el numero 10 entre un numero dado por el usuario, garantizandola continuacion, alternativa 1 en C++

56

3.7 Interfaces Graficas de Usuario (Eventos)

// Alternativa 2:#include <iostream>using namespace std;

int main() { int numero,resultado;

cout << "Entre el divisor: "; cin >> numero; try { if(numero == 0) throw 1; } catch(int) { cout << "Division por cero. Se reemplazo el 0 por 1." << endl; numero = 1; } resultado = 10/numero; cout << resultado << endl; return 0;}

Algoritmo 13: Divide el numero 10 entre un numero dado por el usuario, garantizandola continuacion, alternativa 2 en C++

3.7. Interfaces Graficas de Usuario (Eventos)

Para trabajar con un computador es necesario tener control y poder realizar operacionessobre los estados del sistema computacional. Lo anterior es logrado mediante una interfaz Interfaz,es decir, un espacio donde ocurre la interaccion entre el sistema y el usuario.

Desde los anos 50’s, cuando se disenaron los primeros teclados para computador, hastafinales de los anos 80’s el metodo de interaccion mas usado eran los comandos (antes delos 50’s se usaban las tarjetas perforadas). Ellos son ejecutados escribiendo en el shell11 elnombre del comando y pulsando la tecla enter.

Los ejemplos de codigo que se han visto hasta ahora han sido creados con interfacespor lınea de comandos (CLI). Cada vez que se ejecutan estos programas se pide al usuarioque se entre un dato, este debe escribirlo y pulsar enter. El flujo del programa en laprogramacion por comandos es unico y solo es cambiado de curso en algunos puntos.

Desde los anos 80’s los sistemas operativos graficos (como Windows y MacOS) y losentornos como el X Window System hicieron que muchos programadores cambiaran su pa-

11Un shell puede verse como la interfaz entre un programa y el usuario. Este programa puede ser un sistemaoperativo, un interpretador o una aplicacion. Ejemplos de shells incluyen los Unix (sh, csh, bash, zsh,tcsh, etc.) el de DOS (command.com), el de Python y el de Tcl/Tk (wish).

57


radigma para crear interfaces graficas de usuario (GUI). Una GUI representa la informaciony acciones que estan disponibles al usuario. Los componentes de una GUI son comunmenteagrupados en el llamado WIMP (siglas en ingles de Ventana, Icono, Menu, Dispositivoapuntador).

Existen muchas librerıas conocidas para crear GUIs. Algunas de ellas estan disenadaspara un sistema operativo especıfico, por ejemplo el Windows API se usa en Windows,Cocoa se usa en MacOS y Motif se usa en Unix. Otras librerıas para varias plataformasincluyen:

GTK+Pagina oficial: http://www.gtk.org/Algunas aplicaciones hechas con Gtk+: Google Chrome, Gimp, Abiword, Gnumeric.

wxWidgets (antes llamado wxWindows)Pagina oficial: http://wxwidgets.org/Algunas aplicaciones hechas con wxWidgets: BitTorrent, Audacity.

QtPagina Oficial: http://www.qtsoftware.com/productsAlgunas aplicaciones hechas con Qt: Adobe Photoshop, Google Earth, KDE, Mathe-matica, VLC.

Swing:Pagina oficial: http://java.sun.com/javase/6/docs/technotes/guides/swing/Algunas aplicaciones hechas con Swing: Limewire, Netbeans, Morpheus, JM Studio.

Un ejemplo del uso de estas librerıas puede verse en el algoritmo 14, el cual crea el famoso“Hola Mundo” con Gtk+ en el lenguaje C.

Algunas CLIs proveen funcionalidades que en las GUIs son muy difıciles de expresar.Por ejemplo, en los shells de DOS y Unix, los resultados de la ejecucion de un comandopueden ser usados por otro comando (utilizando el caracter pipe ’|’). Lo que hacen losprogramadores que solo utilizan CLIs es usar una librerıa para consola (llamada ncursesen Linux y PDCurses en Windows), con la cual pueden embellecer la interfaz texto me-diante el uso de caracteres especiales. El algoritmo 15 muestra el “Hola Mundo” con curses.

58

http://www.gtk.org/

http://wxwidgets.org/

http://www.qtsoftware.com/products

http://java.sun.com/javase/6/docs/technotes/guides/swing/

3.7 Interfaces Graficas de Usuario (Eventos)

#include <gtk/gtk.h>

int main(int argc, char *argv[]){ GtkWidget *window; GtkWidget *label;

gtk_init(&argc, &argv); window = gtk_window_new (GTK_WINDOW_TOPLEVEL); gtk_window_set_title (GTK_WINDOW (window), " "); g_signal_connect (G_OBJECT (window), "delete-event", gtk_main_quit, NULL); label = gtk_label_new ("Hola Mundo!"); gtk_container_add (GTK_CONTAINER (window), label); gtk_widget_show_all (window); gtk_main(); return 0;}

Algoritmo 14: Imprime ’HolaMundo!’ en una ventana usando Gtk+

#include <ncurses.h>

int main(){ initscr(); printw("Hola Mundo!"); refresh(); getch(); endwin(); return 0;}

Algoritmo 15: Imprime ’HolaMundo!’ por lınea de comandos usando curses

Como los programas con GUI no pueden esperar a que el usuario pulse enter paraejecutar operaciones, ya que las operaciones pueden llamarse por medio de otros dispositivosde entrada como el mouse, la interaccion se realiza por medio de eventos Evento. Los eventos sonhechos que suceden y son generados por interrupciones tanto de software como de hardware.Ejemplos de eventos son: tarjetas de red requiriendo un servicio, la presion de un botondel mouse, el cron del sistema cuando llega a algun momento especıfico, un drag-and-drop en el sistema operativo, el pulso de un boton del teclado. El funcionamiento de unprograma creado por eventos esta basado en un proceso llamado el event-loop, quien

59


es el encargado de estar pendiente de los eventos que sucedan y llamar al manejador deeventos respectivo (despacha el evento). En el codigo de arriba el event-loop se llama conla funcion gtk-main().

En la actualidad los dispositivos moviles como PDAs, tablets y celulares estan cambiandolas GUI, debido a que las interfaces WIMP no son optimas para trabajar con programasinteractivos que tengan un continuo flujo de senales de entrada o con programas interac-tivos 3D. Las nuevas GUIs son llamadas post-WIMP. Ejemplos de dispositivos que usanpost-WIMPs son los iPods, iPads, las nuevos cajeros automaticos y los celulares que corrensistemas como Android.

3.8. Referencias y Apuntadores

Implıcitamente cuando se hace una asignacion a una variable, en realidad lo que serealiza por debajo es tomar un identificador y denotar en el la direccion de una ubicacionmutable en la memoria. Dicha direccion es llamada una referenciaReferencia , y es el contenido dedicha referencia el que es modificado por la asignacion de la variable [12].

a = 5b = ac = 7b = 3

Algoritmo 16: Asigna cuatro variables en Python (analisis de referencias)

Suponga que se tiene el algoritmo 16. La primera lınea crea una referencia a una ubicaciondonde estara contenido el numero 5. La direccion de dicha ubicacion la tiene la variable a.En la segunda lınea, una nueva referencia a la ubicacion que contiene el 5 es creada con lavariable b. En la tercera lınea se crea otra referencia con la asignacion de c. Por ultimo, alhacer la asignacion de b se cambia la referencia que tenıa dicha variable a otra ubicacioncuyo contenido sera 3.

En el ejemplo 3.9.1 se ve graficamente los cambios en las referencias de otro codigo enPython. Al lado izquierdo de cada figura puede verse la evolucion del programa mientrasque en el lado derecho se muestra las referencias que se van creando o modificando y susrespectivas ubicaciones con los valores a los cuales hacen referencia.

Ejemplo 3.9.1Primero se crea la variable s y se le asigna el valor "MURCIELAGO".

>>> s = "MURCIELAGO">>>

s "MURCIELAGO"

Luego se crea la variable t y se le asigna el valor "LAGO".

60

3.8 Referencias y Apuntadores

>>> s = "MURCIELAGO">>> t = "LAGO">>>

s "MURCIELAGO"

"LAGO"t

Despues se crea la variable i y se le asigna el resultado de aplicar la funcion find a lavariable s con t como parametro. Inmediatamente despues se imprime el valor de i. Estaultima instruccion (print i) no altera las referencias ni los valores de las ubicaciones.

>>> s = "MURCIELAGO">>> t = "LAGO">>> i = s.find(t)>>> print i6>>>

s "MURCIELAGO"

"LAGO"

6i

t

Acto seguido se asigna t a s. Esto significa que la referencia que tenıa t a la segundaubicacion de nuestra memoria se pierde. t ahora hace referencia a la primera ubicacion, aligual que s.

>>> s = "MURCIELAGO">>> t = "LAGO">>> i = s.find(t)>>> print i6>>> t = s>>>

s "MURCIELAGO"

"LAGO"

6i

t

En el momento en que se pierde la referencia a la segunda ubicacion, el garbage collector Garbage Collector

(proceso que elimina la informacion que no se volvera a usar) libera ese espacio para unposterior uso.

>>> s = "MURCIELAGO">>> t = "LAGO">>> i = s.find(t)>>> print i6>>> t = s>>>

s "MURCIELAGO"

6i

t

Si en este momento se quiere conocer el valor asociado a una variable que no ha sidoasignada previamente, sale un error. Sin embargo, la memoria del ejemplo no cambia, nose hace una reserva anterior, es decir, no se tiene en cuenta que dicha variable puede serdeclarada posteriormente.

61


>>> s = "MURCIELAGO">>> t = "LAGO">>> i = s.find(t)>>> print i6>>> t = s>>> aTraceback (most recent call last): File "<pyshell#16>", line 1 , in -toplevel- aNameError: name 'a' is not defined>>>

s "MURCIELAGO"

6i

t

Ahora se asigna la variable s al dato "CIELO". Esto hace que se cree una nueva referencia ala segunda ubicacion de la memoria del ejemplo. No obstante, la referencia de t no se pierde,y al hacer un print a dicha variable, el resultado sera, efectivamente, "MURCIELAGO".

>>> s = "MURCIELAGO">>> t = "LAGO">>> i = s.find(t)>>> print i6>>> t = s>>> aTraceback (most recent call last): File "<pyshell#16>", line 1 , in -toplevel- aNameError: name 'a' is not defined>>> s = "CIELO">>> print t"MURCIELAGO">>>

s "MURCIELAGO"

"CIELO"

6i

t

En el momento en que se borre la variable t, la referencia y el dato en la memoria tambienson eliminados.

>>> s = "MURCIELAGO">>> t = "LAGO">>> i = s.find(t)>>> print i6>>> t = s>>> aTraceback (most recent call last): File "<pyshell#16>", line 1 , in -toplevel- aNameError: name 'a' is not defined>>> s = "CIELO">>> print t"MURCIELAGO">>> del t>>>

s

"CIELO"

6i

62


Por ultimo, en el momento en que se intente acceder a la variable t de nuevo, un errorsurgira, tal y como paso con la variable a.

>>> s = "MURCIELAGO">>> t = "LAGO">>> i = s.find(t)>>> print i6>>> t = s>>> aTraceback (most recent call last): File "<pyshell#16>", line 1 , in -toplevel- aNameError: name 'a' is not defined>>> s = "CIELO">>> print t"MURCIELAGO">>> del t>>> print tTraceback (most recent call last): File "<pyshell#16>", line 1 , in -toplevel- tNameError: name 't' is not defined>>>

s

"CIELO"

6i

? ? ?

El manejo de variables con listas y otras estructuras de datos (que se veran en el proximocapıtulo) es un poco mas complicado. Lo anterior debido a que las referencias llevan todala informacion sobre lo que se referencian y el conjunto de operaciones que son posibles conella. Esto hace que si se igualan dos variables que hacen referencia a la misma estructurade datos, el cambio al dato de una de ellas afecta al dato de la otra.

En el ejemplo 3.9.2 se muestra un manejo de listas en Python y los cambios que vansucediendo.

Ejemplo 3.9.2Primero se crea la variable L1 y se le asigna el valor [2,4].

>>> L1 = [2, 4]>>>

L1 [2, 4]

Luego se agrega un nuevo elemento a la lista L1.

63


>>> L1 = [2, 4]>>> L1.append(5)>>>

L1 [2, 4, 5]

Despues se crea una nueva variable L2 y se le asigna la misma referencia de L1.

>>> L1 = [2, 4]>>> L1.append(5)>>> L2 = L1>>>

L1 [2, 4, 5]

L2

Si se agrega un elemento nuevo a la lista L2, se ve afectada tambien la lista L1, ya que ambasvariables son referencias a la misma lista. La impresion de ambas variables sera identica.

>>> L1 = [2, 4]>>> L1.append(5)>>> L2 = L1>>> L2.append(7)>>> print L1[2, 4, 5, 7]>>> print L2[2, 4, 5, 7]>>>

L1 [2, 4, 5, 7]

L2

La eliminacion de un elemento en una de las variables afecta ambas.

>>> L1 = [2, 4]>>> L1.append(5)>>> L2 = L1>>> L2.append(7)>>> print L1[2, 4, 5, 7]>>> print L2[2, 4, 5, 7]>>> del L2[1]>>>

L1 [2, 5, 7]

L2

Sin embargo, es posible hacer copias de la lista para que las dos variables L1 y L2 no seafecten mutuamente cuando se realice un cambio a alguna de ellas.

64


>>> L1 = [2, 4]>>> L1.append(5)>>> L2 = L1>>> L2.append(7)>>> print L1[2, 4, 5, 7]>>> print L2[2, 4, 5, 7]>>> del L2[1]>>> L2 = L1[:]>>> L1 == L2True>>>

L1 [2, 5, 7]

[2, 5, 7]L2

Se cambia la lista L1, no se afecta la otra lista (no son la misma lista).

>>> L1 = [2, 4]>>> L1.append(5)>>> L2 = L1>>> L2.append(7)>>> print L1[2, 4, 5, 7]>>> print L2[2, 4, 5, 7]>>> del L2[1]>>> L2 = L1[:]>>> L1 == L2True>>> L1.reverse()>>> L1 == L2False>>>

L1 [7, 5, 2]

[2, 5, 7]L2

? ? ?

Los apuntadores Apuntadores, al igual que las referencias, son variables que contienen la direccionde memoria de un dato. Sin embargo, ellos se diferencian de las referencias en que sonmas flexibles y mas generales. Adicionalmente, los apuntadores no permiten un procesoautomatico de garbage collection.

El manejo de apuntadores y referencias esta ligado al lenguaje de programacion. Porejemplo, Python y Java manejan referencias, mientras que C y C++ manejan apuntadores.El algoritmo 17 muestra un ejemplo de como se manejan apuntadores en C++.

Si se compilara y ejecutara el programa anterior se mostrarıa por pantalla los valores delas variables algunNumero y ptrAlgunNumero. El primero es 12345 mientras que el segundoes un numero hexadecimal12 que es, en efecto, la direccion de memoria donde se encuentrael valor de algunNumero.

12No se puede decir exactamente el valor porque este depende de muchos factores entre los cuales seencuentra momento en que se compile el programa, el estado de la memoria y el compilador que se use.

65



int main(){ int algunNumero = 12345; int *ptrAlgunNumero = &algunNumero;

cout << "algunNumero = " << algunNumero << endl; cout << "ptrAlgunNumero = " << ptrAlgunNumero << endl;

return 0;}

Algoritmo 17: Declara, asigna e imprime un entero y un apuntador a entero en C++

Muchos programadores afirman que el manejo de referencias es mucho mas seguro queel manejo de apuntadores (en cuanto a errores y uso malicioso). Sobre esto hay que hacernotar que la seguridad depende mucho de la implementacion de los tipos de datos y delcompilador del lenguaje de programacion.

3.9. Declaraciones y Tipos

Los lenguajes de programacion de alto nivel permiten crear y usar identificadores paralos nombres de funciones y variables, es decir, permiten introducir las funciones y variablescomo nombres para algun valor. En el caso especial de las variables, ellas tienen cuatrocaracterısticas:

Tipos de datos:

Las variables que pueden declararse en un algoritmo son asignadas a valores. Dichosvalores estan dentro de un dominio de valores y los dominios son llamados los tipos dedatosTipo de dato . Por ejemplo, cuando una variable x es de tipo entero, esto quiere decir que eldominio de valores que puede asignarsele a x es el de los numeros enteros. Ademas, lasfunciones a las cuales puede aplicarse la variable x deben tener una semantica sensible a losenteros (e.g. funcion abs(), que devuelve el valor absoluto de un numero, tiene significadoal aplicarse con la variable x, sin embargo la funcion strlen(), que devuelve el tamano deuna cadena no puede tener como argumento a x).

Los lenguajes que no restringen los dominios de las variables son denominados lenguajesno tipados. En estos lenguajes las variables no tienen tipo, lo que quiere decir que se lespuede asignar cualquier valor. Los lenguajes tipados pueden ser explıcitos, cuando los tiposson parte de la sintaxis del lenguaje, o implıcitos. Python, por ejemplo, es un lenguaje deprogramacion tipado implıcito.

El sistema de tipos de un lenguaje determina, en gran parte, el comportamiento de un

66

3.9 Declaraciones y Tipos

programa, es decir, la presencia o ausencia de errores.

Existen dos clases de errores de tipos:

Atrapados. Los que causan que la ejecucion pare inmediatamente, por ejemplo ladivision por cero.

No atrapados. Los que permiten que siga la ejecucion pero puede llevar a comporta-mientos inesperados, por ejemplo un salto a una direccion de memoria desconocida.

Un programa es seguro si no presenta errores no atrapados [6]. Un lenguaje es segurosi no permite crear programas con un mal comportamiento, es decir, solo permite crearprogramas seguros. La seguridad tiene un costo en tiempo debido a que tiene que hacervarios chequeos y analisis que pueden ser complejos. El ejemplo 3.8.1 muestra la diferenciaentre lenguajes seguros e inseguros.

Ejemplo 3.8.1El algoritmo 18 muestra un programa hecho en Python.

x = 5y = "37"z = x + y

Algoritmo 18: Asigna tres variables en Python (analisis de tipos)

El algoritmo 18 sacara un error en Python ya que en realidad se esta tratando de sumarun entero con una cadena de caracteres. Tal vez fue una equivocacion del programador ypor eso lenguajes como Visual Basic tienen definidas funciones para hacer un casting dedatos, es decir, un cambio de tipos para asegurar que el flujo de ejecucion continue. Ahora,el algoritmo 19 muestra un programa hecho en C++.


int main(void){ int x = 5; char y[] = "37"; char *z = x + y;

return 1;}

Algoritmo 19: Asigna tres variables en C++ (analisis de tipos)

El algoritmo 19 no suma las variables x y y. Por el contrario asigna a z la direccionde memoria 5 ubicaciones despues de la direccion de memoria de y. Como no se sabe que

67


datos hay en esa direccion, el uso de la variable z es peligroso y puede llevar un terminacionbrusca del programa.

? ? ?

Los lenguajes de programacion que no permiten la ejecucion de una operacion con tiposerrados son llamados lenguajes fuertemente tipados. En el ejemplo 3.8.1 se mostro quePython es un lenguaje fuertemente tipado mientras que Visual Basic no lo es.

El chequeo de tipos puede ser estatico o dinamico. En el chequeo estatico, el analisises realizado en tiempo de compilacion mientras que en el chequeo dinamico, se realiza entiempo de ejecucion. En el chequeo dinamico las variables pueden tener un tipo dependiendode la direccion del flujo de ejecucion

En Python es posible un programa como el del algoritmo 20, donde primero se asigna ala variable m un valor de tipo entero y luego se le asigna un valor de tipo lista de enteros.

m = 5m = [1, 2, 3]

Algoritmo 20: Cambio de tipo de una variable en Python

Sin embargo, lenguajes como C/C++ no permitirıan un programa ası ya que en tiempode compilacion se tendrıa que declarar la variable m como entero, asignarle el valor 5 y enla siguiente lınea se le asignarıa un valor diferente de tipo lista.

El cuadro 3.1 muestra algunos de los lenguajes de programacion que se vieron en lafigura 3.1 y su caracterizacion: si son de chequeo estatico o dinamico, fuerte o debilmentetipados, y seguros o inseguros.

Alcance:

El alcanceAlcance de una variable es la region dentro de la cual las referencias a la variable seasocian con el identificador de la variable. La region excluye cualquier otra region interiorque contengan declaraciones que usan el mismo identificador.

El concepto de alcance tiene sentido cuando se piensa en la cantidad reducida de iden-tificadores que se usan para las variables (e.g. x es el nombre de variable por excelencia,mientras que i es el identificador tıpico para los ındices de una lista y para los contadores).

La manera de manejar varias ocurrencias de variables se determina de dos maneras:

Alcance Estatico – La variable siempre se refiere a su contorno mas cercano. Los contornosson cuadros que delimitan las regiones. La figura 3.10 muestra un programa en Pythondonde la variable x que se encuentra en el contorno mas interior se refiere a la x quese pasa como argumento a la funcion f3, mientras que la x de la ultima lınea se refierea la x que se pasa como argumento a la funcion f1.

La figura 3.11 muestra un programa en Python un poco mas complejo. Se definen doscontornos al interior del contorno exterior que son independientes entre ellos. Puede

68


Lenguaje Estatico/Dinamico Fuerte/Debil Seguro/Inseguro

ADA Estatico Fuerte Seguro

BASIC Estatico Debil Seguro

C Estatico Debil Inseguro

C++ Estatico Fuerte Inseguro

C# Estatico Fuerte Ambos13

FORTRAN Estatico Fuerte Seguro

HASKELL Estatico Fuerte Seguro

JAVA Estatico Fuerte Seguro

JAVASCRIPT Dinamico Debil Seguro

LISP Dinamico Fuerte Seguro

ML Estatico Fuerte Seguro

PASCAL Estatico Fuerte Seguro

PERL Dinamico Debil Seguro

PHP Dinamico Debil Seguro

PYTHON Dinamico Fuerte Seguro

RUBY Dinamico Fuerte Seguro

SCHEME Dinamico Debil Seguro

SMALLTALK Dinamico Fuerte Seguro

VISUAL BASIC Hıbrido Hıbrido Seguro

Cuadro 3.1: Lenguajes de programacion y tipos de datos

print x+y

def f3(x):

return x

def f2(y):

def f1(x):

Figura 3.10: Diagrama de contorno

verse tambien que los nombres de las funciones, por ser identificadores, pueden pasarsecomo parametros de otras funciones.

Alcance Dinamico – Se tiene una pila14 para cada identificador en la que se introducen lasvariables con un nombre especıfico cada vez que se encuentra una. De esta manera

14El concepto de pila se puede ver en el siguiente capıtulo.

69


return a+c

def f7(a):

a(f7, b)

def f6(a, b, c):

def f5(z):

def f8(f, x):

f(z, x)

Figura 3.11: Diagrama de contorno

cuando el flujo de ejecucion sale de los alcances se van eliminando los elementos dela pila (la variable que se evalua siempre es la que esta en el tope de la pila).

Para crear un alcance dinamico usualmente se definen bloques que permiten delimi-tar claramente un alcance. Cada lenguaje de programacion tiene su forma de definirbloques: en Python los bloques se identifican por la indentacion que tengan las ex-presiones, en C se tienen las llaves { } para los bloques, mientras que en Pascal setienen las palabras reservadas begin y end.

procedure Principal();var x : integer;begin x := 1; while x <= 10 do begin writeln(x); x := x + 1; end;end;

Algoritmo 21: Definicion de dos bloques de ejecucion en Pascal

El algoritmo 21, escrito en Pascal, define dos bloques: el bloque de la definicion de lafuncion y el bloque de la estructura while.

Ligadura:

LigaduraLigadura se refiere a la asociacion de valores con identificadores. Mientras que una asig-nacion cambia el valor asociado a un identificador, la ligadura crea dicha asociacion.

70


Cuando un identificador esta ligado a un valor se dice que es una referencia a ese valor.Dicha referencia puede ser considerada como la direccion de memoria donde se encuentraalojado el valor asociado al identificador, es decir, es un dato que contiene la llave parallegar a otro dato.

Al crear una variable, se reserva un espacio en la memoria donde se alojara el valorasociado al identificador de la variable. El tamano del espacio depende del tipo de dato dela variable.

Cuando una ligadura es compartida por varias funciones, un cambio que realice una fun-cion puede ser vista por todas las demas. En el algoritmo 22 se muestran dos funciones pare impar, escritas en Python, que comparten la variable x. Puede verse que la comunicacionentre las dos funciones no se realiza pasando datos explıcitamente sino cambiando el estadode la variable que comparten.

def par(impar): if x == 0: return True else: return impar(x-1)

def impar(x): if x == 0: return False else: return par(impar, x-1)

Algoritmo 22: Definicion de dos funciones que comparten una variable en Python

El tiempo durante el cual se caracteriza la ligadura de una variable es llamado el tiempode ligadura. Existen cuatro diferentes tiempos de ligadura [18]:

1. Tiempo de ejecucion

2. Tiempo de compilacion

3. Tiempo de implementacion del lenguaje

4. Tiempo de definicion del lenguaje

Cuando se hace una simple asignacion en Python como en el algoritmo 23, se puedenidentificar los diferentes tiempos de ligadura para las caracterısticas de la variable. Elconjunto de posibles tipos para la variable x (e.g. entero, flotante, binario, caracter) sefijan en el tiempo de definicion del lenguaje. El tipo de la variable x se fija en el tiempode compilacion o ejecucion dependiendo del lenguaje (para Python es en ejecucion). Elconjunto de posibles valores para x en el tiempo de implementacion del lenguaje. El valorde x se define en el tiempo de ejecucion. La representacion de la constante 10 se hace en el

71


tiempo de definicion del lenguaje. Por ultimo, la propiedades para el operador + se escogenen el tiempo de definicion del lenguaje.

x = x + 10

Algoritmo 23: Asignacion simple en Python

Visibilidad:Una variable es visibleVisibilidad en un subprograma si el identificador asociado a ella es parte del

ambiente de ese subprograma. Si el identificador existe pero no es parte del ambiente delsubprograma que se encuentra actualmente en ejecucion, se dice entonces que la variableasociada esta escondida de ese subprograma.

Durante su “tiempo de vida” una variable puede tener mas de un nombre o identificador;esto es, existen muchas asociaciones en diferentes ambientes, cada una con un diferentenombre para la variable. El algoritmo 24 es un programa que muestra un caso en el queen una misma funcion (fun1) se tienen dos identificadores que hacen referencia a la mismavariable (j por ser parametro e i por ser variable global).

i = 0

def fun1(j): print j

def fun2(): fun1(i)

fun2()

Algoritmo 24: Dos identificadores con la misma referencia en una funcion en Python

El paso de una variable como parametro a una funcion se puede realizar de dos formas:por valor o por referencia. En el paso de parametros por valor se crea un nueva referenciapara cada parametro formal de la funcion, es decir, las asignaciones dentro de la funcionson locales y no afectan la variable fuera del alcance de la funcion. Por el contrario, elpaso de parametros por referencia implica que la variable con la que se hace la llamadaa la funcion pueda cambiar su contenido. Lo anterior significa que en los llamados porreferencia se envıa la direccion de memoria de la variable mientras que en los llamados porvalor, como su nombre lo indica, se envıa el contenido de la direccion de memoria. En elprograma anterior, la variable i dentro de la funcion fun2 la variable i es pasada por valora fun1.

72

4 Nocion de Tipo Abstracto de Datos

4.1. Tipos Abstractos de Datos

Un tipo abstracto de datos (TAD), es la conjuncion de variables, operaciones y aserciones(ademas de documentacion) que modela un dominio de datos.

Un TAD se diferencia de un tipo de dato en que es especificado de forma precisa ydisenado independiente de cualquier implementacion (en algunos casos los TADs no puedenser implementados en un hardware o software especıfico).

Los lenguajes de programacion traen de forma nativa un conjunto de tipos que son utilespero desafortunadamente insuficientes para resolver todo tipo problemas. Por ejemplo, sise quiere tomar los datos de todos los empleados de una empresa y realizar consultas yreportes, resulta muy ineficiente (y dispendioso) crear una variable para cada dato de cadaempleado (e.g. nombre, cedula, codigo, cargo, etc.)

La definicion de un TAD debe ser independiente de un lenguaje, no obstante ella esmuy descriptiva y se ajusta bastante a las necesidades del disenador. Por ello no es raroencontrar diferentes definiciones de listas, colas, arboles, etc. Todas las definiciones debentener tres componentes comunes: la estructura del TAD (la representacion), una coleccionde operadores y un conjunto de axiomas (para el TAD y cada una de las operaciones).

Un tipo abstracto de datos se especifica formalmente de la siguiente manera1:

TAD 〈nombre〉〈Objeto Abstracto〉{inv : 〈Invariante del TAD〉}Operaciones Primitivas:

• 〈Operacion 1〉 : 〈entradas〉 → 〈salida〉• . . .• 〈Operacion n〉 : 〈entradas〉 → 〈salida〉

El TAD debe llamarse con un nombre unico que lo identifique plenamente; debe expresar-se el objeto que se esta modelando de una manera matematica o grafica (entre mas formalmejor), pero que muestre claramente el objeto y que pueda ser usado para referenciarlo enlas notaciones y formalismos de las operaciones; debe establecerse una serie de condicio-nes que no varıan nunca al interior del TAD; y deben listarse las operaciones que pueden

1Esta es la misma aproximacion de J. Villalobos en [23].

73


realizarse con los objetos del tipo del TAD. Las operaciones se especifican con las entradasa ellas y la salida que retornara el proceso (se escribe el tipo de dato de cada entrada yde la salida, tal como el contrato que se da como paso inicial de la receta para disenarprogramas en [11]). Adicionalmente para cada una de las operaciones se debe escribir sucomportamiento a manera de aserciones: una para mostrar que se debe cumplir antes deejecutar la operacion (precondicion) y otra para decir como queda el mundo despues determinar el proceso (postcondicion).

〈prototipo de la operacion〉”〈breve descripcion de la operacion〉”

{pre : . . .}{post : . . .}

La precondicion y la postcondicion deben ser lo mas formal posible por dos razones:

1. El formalismo describe el proposito de la operacion sin lugar a ambiguedades y conmucha exactitud.

2. La formalidad acerca el diseno a la implementacion, es decir, entre mas formal sea eldiseno del TAD mas facil sera concretizarlo en algun lenguaje de programacion.

Los siguientes ejemplos muestran diferentes TADs y sus especificaciones.

Ejemplo 4.1.1Suponga que una companıa tiene la informacion de Nombre, Foto, Documento de identidad,Cargo, y Sueldo por cada empleado. Si se quisiera almacenar estos datos serıa desastrosousar una variable por cada dato o empleado (imagine una empresa con 1500 empleados).Una forma eficiente es crear un tipo de dato Empleado para guardar la informacion:

TAD Empleado

Graficamente:

Foto

NombreCédulaCargoSueldo

Textualmente:

Empleado = {Nombre : 〈nombre〉, Cedula : 〈cedula〉,Cargo : 〈cargo〉, Sueldo : 〈sueldo〉, Foto : 〈foto〉}

74

4.1 Tipos Abstractos de Datos

{inv : Empleado.Sueldo ≥ 535600}Operaciones Primitivas:

• CrearEmpleado: → Empleado• AgregarNombre: Empleado× Texto → Empleado• AgregarCedula: Empleado× Texto → Empleado• CambiarSalario: Empleado× Entero → Empleado• CambiarCargo: Empleado× Texto → Empleado• CambiarFoto: Empleado× Imagen → Empleado• InfoSalario: Empleado → Entero• InfoCargo: Empleado → Texto• TieneFoto: Empleado → Booleano

CrearEmpleado()“Crea un nuevo empleado con los datos vacıos”

{pre : TRUE}{post : emp = {Nombre : ””, Cedula : ””, Cargo : ””, Sueldo : 535600,

Foto = 2}}

AgregarNombre(emp, n)“Asigna un nombre a un empleado sin nombre”

{pre : emp = {Nombre : ””, . . .}, n ∈ Texto}{post : emp.Nombre = n}

AgregarCedula(emp, c)“Asigna una cedula a un empleado sin cedula”

{pre : emp = {. . . , Cedula : ””, . . .}, c ∈ Texto}{post : Emp.Cedula = c}

CambiarSalario(emp, s)“Cambia el salario de un empleado”

{pre : emp = {. . . , Salario : 〈salario〉, . . .}, s ∈ Entero, s ≥535600}{post : emp.Salario = s}

CambiarCargo(emp, c)“Cambia el cargo de un empleado”

{pre : emp = {. . . , Cargo : 〈cargo〉, . . .}, c ∈ Texto}{post : emp.Cargo = c}

75


CambiarFoto(emp, f)“Cambia la foto de un empleado”

{pre : emp = {. . . , Foto : 〈foto〉}, f ∈ Imagen}{post : emp.Foto = f}

InfoSalario(emp)“Retorna el salario de un empleado”

{pre : emp = {. . . , Salario : 〈salario〉, . . .}}{post : 〈salario〉}

InfoCargo(emp)“Retorna el cargo de un empleado”

{pre : emp = {. . . , Cargo : 〈cargo〉, . . .}}{post : 〈cargo〉}

TieneFoto(emp)“Informa si un empleado tiene foto”

{pre : emp = {. . . , Foto : 〈foto〉} o emp = {. . . , Foto : 2}}{post : True si emp.Foto = 〈foto〉 ∨ False si emp.Foto = 2}

? ? ?

Ejemplo 4.1.2Se quiere disenar un tipo abstracto de datos para modelar un conjunto de valores binariosy sus operaciones principales.

TAD Binario

b1b2 . . . bn

{inv : bi ∈ {1, 0}, n ≥ 1}

76


Operaciones Primitivas:

• CrearBin: Entero → Binario• CorrimientoDer: Binario → Binario• CorrimientoIzq: Binario → Binario• Not: Binario → Binario• And: Binario×Binario → Binario• Or: Binario×Binario → Binario• SumarBin: Binario×Binario → Binario• Complementoa2: Binario → Binario• bin2Dec: Binario → Entero• esBin: Binario → Booleano

CrearBin(e)“Construye un numero binario a partir de un numero entero”

{pre : e ∈ Entero+}{post : b1b2 . . . bn−1bn |

(b1 × 2n) + (b2 × 2n−1) + . . .+ (bn−1 × 21) + (bn × 20) = e}

CorrimientoDer(bin)“Realiza un corrimiento a la derecha (un solo bit) de un numero binario”

{pre : bin = b1b2 . . . bn−1bn}{post : bin = b1b2 . . . bn−1}

CorrimientoIzq(bin)“Realiza un corrimiento a la izquierda (un solo bit) de un numero bina-rio”

{pre : bin = b1b2 . . . bn−1bn}{post : bin = b1b2 . . . bn−1bn x | x = 0}

Not(bin)“Modifica un numero binario con su negacion”

{pre : bin = b1b2 . . . bn}

{post : bin = b′1b′2 . . . b

′n | ∀i b′i =

{0 si bi = 11 si bi = 0

1 ≤ i ≤ n}

77


And(bin1, bin2)“Retorna la conjuncion de dos numeros binarios”

{pre : bin1 = b1b2 . . . bn, bin2 = c1c2 . . . cn}{post : bin1 and bin2 = d1d2 . . . dn |

∀i di =

{1 si bi = ci = 10 en otro caso

1 ≤ i ≤ n}

Or(bin1, bin2)“Retorna la disjuncion de dos numeros binarios”

{pre : bin1 = b1b2 . . . bn, bin2 = c1c2 . . . cn}{post : bin1 or bin2 = d1d2 . . . dn |

∀i di =

{0 si bi = ci = 01 en otro caso

1 ≤ i ≤ n}

SumarBin(bin1, bin2)“Retorna la suma de dos numeros binarios”

{pre : bin1 = b1b2 . . . bn, bin2 = c1c2 . . . cn}{post : bin1 + bin2 = d0d1d2 . . . dn |

∀i di = bi + ci + carryi+1

donde se cumple que

bi + ci =

0 (carryi = 0) si bn = cn = 01 (carryi = 0) si bn = 1 ∧ cn = 01 (carryi = 0) si bn = 0 ∧ cn = 10 (carryi = 1) si bn = cn = 1

Complementoa2(bin)“Retorna el complemento a 2 (la suma de su negacion con el numero 1)de un numero binario”

{pre : bin = b1b2 . . . bn−1bn}{post : Not(bin) + 1}

bin2Dec(bin)“Retorna el numero entero correspondiente un numero binario”

{pre : bin = b1b2 . . . bn−1bn}{post : e | e = (b1 × 2n) + (b2 × 2n−1) + . . .+ (bn−1 × 21) + (bn × 20)}

78


esBin(bin)“Informa si un numero es binario”

{pre : bin}{post : True si bin = b1b2 . . . bn ∧ ∀i bi = {0, 1} 1 ≤ i ≤ n

False de lo contrario}

? ? ?

Las operaciones primitivas se dividen en dos grupos: principales y secundarios. El grupoprincipal esta compuesto por las operaciones:

Constructoras Encargadas de crear las estructuras internas del tipo abstracto de datos. Enlos ejemplos anteriores las operaciones CrearEmpleado y CrearBin son constructoras.

Modificadoras Son aquellas operaciones que alteran el estado de los elementos del TAD.Las operaciones modificadoras en los ejemplos son:

AgregarNombre, AgregarCedula, CambiarSalario, CambiarCargo, CambiarFoto,para el TAD Empleado

CorrimientoDer, CorrimientoIzq y Not, para el TAD Binario

Analizadoras Operaciones que consultan el estado de los elementos y retornan informacion(no cambian los estados). Las operaciones analizadoras en los ejemplos son:

InfoSalario, InfoCargo y TieneFoto, para el TAD Empleado

And, Or, SumarBin, Complementoa2, bin2Dec y esBin, para el TAD Binario

El grupo secundario esta compuesto por las operaciones:

Destructoras Son operaciones que eliminan por completo los elementos del objeto del tipodel TAD. Luego de ejecutar operaciones destructoras los objetos no pueden volver autilizarse.

Persistencia Con ellas se puede guardar en un dispositivo de memoria secundaria (discoduro, CD/DVD, USB, entre otros) la informacion de los objetos.

En los ejemplos 4.1.1 y 4.1.2 no hay operaciones destructoras ni de persistencia.Cualquier operacion que no sea primitiva es considerada una operacion adicional y no

pertenece al TAD. Las operaciones adicionales deben construirse a partir de las operacionesprimitivas.

A partir de la siguiente seccion se mostraran los disenos, implementaciones en lenguaje Cy ejemplos de uso de los principales tipos abstractos de datos. El diseno de estos TADs sonmodificaciones de los disenos propuestos por J. Villalobos en [23]. La implementacion delos TADs utilizara dos archivos diferentes, uno llamado el archivo de encabezado (header

79


file que comunmente tiene extension .h), y otro llamado el archivo fuente (source file conextension .c).

Los archivos de encabezado proveen una interfaz de las funciones y estructuras de datosespecıficas que la librerıa incluye. El siguiente es un ejemplo de un archivo de encabezadopara la librerıa libreria.h (se excluyo la mayor parte de la documentacion, es decir,aquella que muestra el autor de la librerıa, la version, forma de uso, changelog, etc):

#ifndef LIBRERIA H#define LIBRERIA H

/∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ LIBRERIAS NECESARIAS∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗/

#include <s t d i o . h>

/∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ESTRUCTURAS DE DATOS∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗/

struct a lgo {int uno ;f loat dos ;

} ;

/∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ OPERACIONES DEL TAD∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗/

/∗ CONSTRUCTORAS ∗/void operac ion1 ( ) ;

/∗ MODIFICADORAS ∗/int operac ion2 ( int ) ;

/∗ ANALIZADORAS ∗/f loat operac ion3 ( f loat ) ;

#endif

Las rutinas de preprocesamiento

#ifndef LIBRERIA H

#define LIBRERIA H

#endif

son necesarias para evitar las multiples declaraciones y errores potenciales con diferentesarchivos fuente. En cada librerıa se debe definir (si no esta definido) el nombre unico de ella.Las librerıas necesarias son aquellas requeridas por algunas funciones o que van a ser usadas;se incluyen por medio de la rutina de preprocesamiento #include. Las estructuras de datosdeclaran la armadura o configuracion de los datos, tıpicamente con la nocion de registrollamada struct. Por ultimo las operaciones del TAD son las funciones que manejan lasestructuras de datos. En este archivo solo se especificara las declaraciones de las funciones

80

4.2 Listas

y no la definicion de ellas, esto quiere decir que solo se coloca el prototipo de la operacioncomo una expresion (finaliza con punto y coma “;”).

El archivo fuente contiene las definiciones de las funciones declaradas en el archivo deencabezado. En este archivo solo se debe incluir el archivo de encabezado. El siguiente esun ejemplo de un archivo fuente libreria.c para libreria.h:

#include ” l i b r e r i a . h”

void operac ion1 ( ){

p r i n t f ( ” se construyo e l TAD” ) ;}

int operac ion2 ( int x ){

return x∗x ;}

f loat operac ion3 ( f loat y ){

return y /2 ;}

4.2. Listas

Una lista es una coleccion lineal de elementos del mismo tipo. Cada elemento se encuentraalmacenado en una ubicacion llamada nodo. Las ubicaciones estan numeradas de 1 hastan, siendo n la longitud de la lista, es decir, el numero de elementos que tiene.

Muchos lenguajes de programacion como Python, Ruby y Lisp, tienen incorporado eltipo de dato Lista de forma nativa. Sin embargo, en esta seccion se mostrara como disenarel TAD Lista de manera que se acomode a las necesidades del programador.

81


4.2.1. Diseno

TAD Lista

〈e1, . . . , en〉

∀i ei ∈ Elemento, n ≥ 0


• crearLista: → Lista• anxLista: Lista× Elemento → Lista• insLista: Lista× Elemento× Entero → Lista• elimLista: Lista× Entero → Lista• infoLista: Lista× Entero → Elemento• longLista: Lista → Entero• vaciaLista: Lista → Booleano

crearLista()“Construye una nueva lista, inicialmente vacıa”

{pre : TRUE}{post : 〈〉}

anxLista(lst, elem)“Inserta un elemento al final de la lista”

{pre : lst = 〈〉 o lst = 〈e1, . . . , en〉, elem ∈ Elemento}{post : lst = 〈elem〉 o lst = 〈e1, . . . , en, elem〉, respectivamente }

insLista(lst, elem, pos)“Inserta un elemento en la posicion dada”

{pre : lst = 〈e1, . . . , epos−1, epos, . . . , en〉, elem ∈ Elemento,1 ≤ pos ≤ n}

{post : lst = 〈e1, . . . , epos−1, elem, epos, . . . , en〉}

elimLista(lst, pos)“Elimina el elemento de la posicion dada”

{pre : lst = 〈e1, . . . , epos−1, epos, epos+1, . . . , en〉, 1 ≤ pos ≤ n}{post : lst = 〈e1, . . . , epos−1, epos+1, . . . , en〉}

82

4.2 Listas

infoLista(lst, pos)“Retorna el dato correspondiente a la posicion dada”

{pre : lst = 〈e1, . . . , epos, . . . , en〉, 1 ≤ pos ≤ n}{post : epos}

vaciaLista(lst)“Informa si la lista esta vacıa (i.e. no contiene elementos)”

{pre : lst = 〈〉 o lst = 〈e1, . . . , en〉}{post : True si lst = 〈〉

False si lst = 〈e1, . . . , en〉}

longLista(lst)“Retorna la longitud de la lista (i.e. numero de elementos)”

{pre : lst = 〈〉 o lst = 〈e1, . . . , en〉}{post : 0 si lst = 〈〉

n si lst = 〈e1, . . . , en〉}

4.2.2. Implementaciones

Estructuras Encadenadas Simples

La manera mas comun de implementar una lista es con estructuras encadenadas. Enesta aproximacion una lista es una coleccion de nodos encadenados de manera simple pormedio de referencias.

Cada nodo consta de la informacion del elemento (de cualquier tipo) y una referencia(o apuntador para algunos lenguajes de programacion) al siguiente nodo. Graficamente unnodo puede verse como la figura 4.1.

Información

Figura 4.1: Nodo con encadenamiento simple

El codigo para definir un nodo cuya informacion es un dato tipo entero es el siguiente :

struct nodo {int dato = 0 ;struct nodo∗ s i g = NULL;

} ;

83


La lista tiene un apuntador al primer nodo, y cada nodo “apunta” al siguiente hasta queel ultimo nodo apunta a un elemento nulo (NULL). Un ejemplo de una lista de enteros lstrepresentada con estructuras encadenadas simples puede verse en la figura 4.2.

12 24 36 48

lst

Figura 4.2: Lista con encadenamiento simple

Como resulta incomodo referirse a la lista como un struct nodo*, es recomendado (masno es un requerimiento) realizar una definicion de un nuevo apuntador al tipo de datostruct nodo*. Lo anterior se logra mediante el comando typedef de la siguiente manera:

typedef struct nodo∗ L i s ta ;

De esta forma siempre podremos referirnos a un dato de tipo struct nodo* como unaLista.

Para crear las listas se desarrolla una funcion constructura que solamente creara lavariable lst que apunta al primer nodo de la lista. Esta variable sera inicializada en NULL,ya que la lista esta vacıa cuando se crea. La funcion sera ası:

L i s ta c r e a r L i s t a ( ){

L i s ta l s t ;l s t = NULL;return l s t ;

}

La operacion para anexar un elemento al final de la lista se logra creando un nodo nuevo

donde esta contenido el nuevo dato y si la lista esta vacıa se actualiza la variable lst

apuntando a nuevo, de lo contrario se crea un apuntador temporal que se movera hasta elultimo nodo de la lista y se modifica haciendo el siguiente de este ultimo igual al nuevonodo.

L i s ta anxLista ( L i s t a l s t , int elem ){

L i s ta nuevo , tmp ;

nuevo = ( L i s t a ) mal loc ( s izeof ( struct nodo ) ) ;nuevo −> dato = elem ;nuevo −> s i g = NULL;

84

4.2 Listas

i f ( l s t == NULL)l s t = nuevo ;

else{

tmp = l s t ;while (tmp −> s i g != NULL)

tmp = tmp −> s i g ;

tmp −> s i g = nuevo ;}

return l s t ;}

Para crear un nuevo nodo se debe reservar la memoria necesaria para que todos loselementos de la estructura tengan un espacio. La funcion malloc permite realizar estaoperacion pasandole como parametro el tamano de la memoria que se va a reservar (eneste caso es el tamano de la estructura nodo). Dicha funcion retorna un apuntador alespacio de memoria. Como este apuntador que retorna es de tipo void* es deseable quese realice un casting, es decir, un cambio al tipo de dato que se hara referencia, de allı queantes del llamado a la funcion malloc se escriba “(Lista)”.

Insertar un elemento en una lista es posible creando un nodo nuevo donde este contenidoel nuevo dato y dependiendo de la posicion a insertar se realiza la insercion. Si la posiciona insertar es la primera entonces simplemente el nodo nuevo apuntara al primer nodo dela lista y luego se actualiza la variable lst para apuntar al nodo nuevo. Si la posicion esdiferente a la primera posicion de la lista, entonces se usa un apuntador temporal parallegar hasta la posicion y actualizar los apuntadores de los nodos entre dicha posicion.

L i s ta i n s L i s t a ( L i s t a l s t , int pos , int elem ){


nuevo = ( l i s t a ) mal loc ( s izeof ( struct nodo ) ) ;nuevo −> dato = elem ;nuevo −> s i g = NULL;

i f ( pos >= 1 && pos <= longL i s t a ( l s t ) ){

i f ( pos == 1){

nuevo −> s i g = l s t ;l s t = nuevo ;

}else{

tmp = l s t ;

for ( int i = 0 ; i < pos − 2 ; i++)tmp = tmp −> s i g ;

nuevo −> s i g = tmp −> s i g ;

85


tmp −> s i g = nuevo ;}

}

return l s t ;}

Es de notar que si se quiere insertar un elemento en la ultima posicion de una listacon elementos, o en una lista vacıa, debe usarse la operacion anxLista ya que usando laoperacion insLista es necesario tener una posicion valida (e.g. en listas vacıas no hayposiciones validas, en listas con elementos la ultima posicion hara que se inserte comopenultimo elemento).

Eliminar un elemento es la operacion contraria a insertar. Solo se verifica si la posiciones la primera u otra distinta y se actualizan los apuntadores de manera similar a insLista.

L i s ta e l imL i s t a ( L i s t a l s t , int pos ){

L i s ta tmp ;


i f ( pos == 1){

l s t = l s t −> s i g ;}else{

tmp = l s t ;


tmp −> s i g = tmp −> s i g −> s i g ;}

}return l s t ;

}

Para encontrar la informacion de un elemento dada su posicion en la lista primero segarantiza que la posicion dada sea una posicion correcta y luego con un apuntador temporal,se llega a la posicion y se retorna el dato.

int i n f o L i s t a ( L i s t a l s t , int pos ){

L i s ta tmp ;

tmp = l s t ;

for ( int i =1; i<pos ; i++)tmp = tmp −> s i g ;

return tmp −> dato ;

86

4.2 Listas

}

Saber si una lista esta vacıa es tan sencillo como preguntar si la variable lst es igual aNULL, es decir, tiene su valor por defecto.

int v a c i a L i s t a ( L i s t a l s t ){

return l s t == NULL;}

Es importante conocer la longitud de una lista para realizar ciertas operaciones adicio-nales. La longitud depende de si la lista esta vacıa o no. Si esta vacıa su longitud es cero,de lo contrario se debe realizar un ciclo con un apuntador temporal hasta que el nodocorrespondiente a dicho apuntador no tenga siguiente, es decir, su variable sig sea igual aNULL.

int l ongL i s t a ( L i s t a l s t ){

L i s ta tmp ;int cont ;

tmp = l s t ;cont = 0 ;

while (tmp −> s i g != NULL){

tmp = tmp −> s i g ;cont++;

}

return cont ;}

Estructuras Doblemente Encadenadas

Otra forma de implementar listas es con estructuras doblemente encadenadas. A dife-rencia de las listas encadenadas simples, en esta aproximacion cada nodo consta de lainformacion del elemento y dos referencias: una al siguiente nodo y otra al nodo anterior.Graficamente puede verse como la figura 4.3.

Al igual que las listas encadenadas simples, las listas doblemente encadenadas tienen unapuntador al primer nodo. Lo diferente esta en que cada nodo “apunta” al siguiente y alanterior de la lista. El primer nodo en su apuntador al anterior tendra un elemento nulo(NULL), al igual que ultimo nodo en su apuntador al siguiente. Un ejemplo de una listadoblemente encadenada puede verse en la figura 4.4.

El codigo para definir un nodo cambia. Se le agrega la variable apuntador al anterior.

87


Información

Figura 4.3: Nodo con doble encadenamiento

1 1 2

lst

3 5 8

Figura 4.4: Lista con doble encadenamiento

struct nodo {int dato = 0 ;struct nodo∗ s i g = NULL;struct nodo∗ ant = NULL;

} ;

Ni la funcion constructora de las listas, ni las operaciones analizadoras cambian en estaaproximacion. Solo las operaciones modificadoras tienen unos pequenos ajustes para ase-gurar que los apuntadores a los nodos anteriores se mantengan. A continuacion se muestrala operacion para insertar un elemento en una posicion dada, ya que es la operacion masrepresentativa (las otras dos operaciones se dejan como ejercicio para el estudiante):



nuevo = ( l i s t a ) mal loc ( s izeof ( struct nodo ) ) ;nuevo −> dato = elem ;nuevo −> s i g = NULL;nuevo −> ant = NULL;


i f ( pos == 1){

nuevo −> s i g = l s t ;l s t −> ant = nuevo ;l s t = nuevo ;

}else{

88

4.2 Listas

tmp = l s t ;


nuevo −> s i g = tmp −> s i g ;nuevo −> ant = tmp ;tmp −> s i g −> ant = nuevo ;tmp −> s i g = nuevo ;

}}

return l s t ;}

Es de notar que la secuencia de pasos para insertar un elemento (las ultimas 4 lıneasdel anterior algoritmo) no puede ser cualquiera. Si se realizan los pasos equivocados puederesultar en la perdida de elementos de la lista. Por ejemplo, si primero se realiza la asig-nacion tmp ->sig = nuevo, entonces no habra forma de llegar a los elementos siguientesa tmp y el garbage collector eventualmente los eliminara. Por esta razon primero se debenhacer las asignaciones del nodo nuevo y luego las de tmp.

Estructuras Circulares

En esta representacion, las listas (ya sean encadenadas simples o doblemente encadena-das) tienen la particularidad de no tener nodos con apuntadores a NULL.

En las listas circulares encadenadas simples el ultimo elemento de la lista en su variablesig tiene un apuntador al primer elemento de la lista. La figura 4.5 muestra un ejemplode una lista circular encadenada simple.

2 4 8 16

lst

Figura 4.5: Lista circular encadenada simple

Adicionalmente al apuntador del ultimo elemento al primero de las listas circulares en-cadenadas simples, en las listas circulares doblemente encadenadas el primer elemento dela lista en su variable ant tiene un apuntador al ultimo elemento. La figura 4.6 muestra unejemplo de una lista circular doblemente encadenada.

Cuando las listas son circulares, la definicion de los nodos y las operaciones constructorasno cambian. No obstante, la mayor parte de las demas funciones cambian de manera que

89


5 4 3

lst

2 1 0

Figura 4.6: Lista circular doblemente encadenada

no se alteren los apuntadores en los casos de insercion y eliminacion de los extremos dela lista, y para que no se quede en un ciclo infinito en el caso de anexar un elemento a lalista o saber cuantos elementos tiene la lista. A continuacion se mostrara la operacion paraeliminar un elemento en una lista circular doblemente encadenada.

L i s ta e l imL i s t a ( L i s t a l s t , int pos ){

L i s ta tmp ;


i f ( pos == 1){

tmp = l s t ;l s t = l s t −> s i g ;

}else{

i f ( pos == longL i s t a ( l s t ) ){

tmp = l s t −> ant ;}else{

tmp = l s t ;


}}tmp −> s i g −> ant = tmp −> ant ;tmp −> ant −> s i g = tmp −> s i g ;tmp −> s i g = NULL;tmp −> ant = NULL;

}

return l s t ;}

Para eliminar un elemento en una lista circular doblemente encadenada se debe realizarlo mismo que en una lista no circular doblemente encadenada con modificaciones cuando

90

4.2 Listas

se elimine el primero o el ultimo elemento.

Las dos ultimas lıneas del anterior algoritmo en teorıa no son necesarias ya que se el nodoque se elimina queda inaccesible por la lista entonces eventualmente el garbage collector laborrara de la memoria. Sin embargo por motivos de seguridad de la lista es mejor colocarlas.

Vectores

Un vector es un arreglo unidimensional de elementos con una longitud constante. Loselementos de un vector pueden ser accesados directamente mediante un ındice.

Un ejemplo de una lista implementada con vectores puede verse en la figura 4.7.

'b' 'a' 'p' . . .

0 1 2 3 4 MAX-1

Figura 4.7: Lista implementada con un vector

MAX es una constante cuyo valor es el numero maximo de elementos que puede contener lalista. Los elementos en el vector estan indexados por medio de un numero entre 0 y MAX-1.En el caso del ejemplo anterior puede verse que a partir de la posicion 3 no hay elementos.Esta es una caracterıstica importante en la implementacion de listas con vectores, loselementos siempre deben estar agrupados en las primeras posiciones (i.e. no deben haberposiciones vacıas entre dos elementos).

Debido a que el vector de por sı es una estructura completa, en esta aproximacion nose tienen nodos. La lista consta del vector y la constante MAX. Un vector es en realidad unapuntador a un espacio de memoria con un tipo de dato particular, de allı que podemosusar el operador typedef para seguir usando el tipo de dato Lista, por ejemplo para unalista de enteros se tendrıa:

typedef int∗ L i s ta ;

La constante MAX se puede definir mediante la rutina de preprocesamiento #define. Porejemplo se podrıa definir MAX con una valor de 1000 ası:

#define MAX 1000

La operacion constructora creara el vector y definira la constante2:

2Algunos lectores se preguntaran de que tamano debe crearse el vector o si se debe pedir al usuario dichotamano. Las respuestas a esas preguntas son sencillas: el tamano depende del problema que se piense

91



L i s ta l s t ;l s t = ( L i s t a ) mal loc (MAX∗ s izeof ( int ) ) ;for ( int i = 0 ; i < MAX; i++)

l s t [ i ] = NULL;return l s t ;

}

En la implementacion anterior, se definio el tamano maximo de la lista como 1000. Noteseque los elementos vacıos son aquellos en los cuales las ubicaciones en el vector contienenun NULL. De esta manera resulta muy facil la implementacion de varias operaciones: en laoperacion vaciaLista, solo hay que verificar si la primera posicion contiene un elementonulo, en las operaciones para anexar un elemento y para saber la longitud de la lista, sedebe recorrer el vector hasta encontrar un NULL, y realizar las acciones respectivas.

Para insertar un elemento se deben correr todos los elementos desde el final hasta llegarhasta la posicion donde se va a insertar y luego copiar elemento. A continuacion se muestrael codigo:


i f ( l ongL i s t a ( l s t ) != MAX){

int i = l ongL i s t a ( l s t ) − 1 ;while ( i > pos−2){

l s t [ i +1] = l s t [ i ] ;i−−;

}l s t [ i +1] = elem ;

}

return l s t ;}

Es de notar que el ciclo para correr todos los elementos arranca en longLista(lst)-1 ytermina en pos-2. Lo anterior es debido a que los vectores a diferencia de las listas que sehan disenado cuentan sus elementos de 0 a n−1 y por lo tanto hay que hacer la diferencia.

La operacion para eliminar un elemento puede verse como el opuesto de la operacionanterior, es decir, se deben correr los elementos hacia la posicion del elemento que se debeborrar. El lector debe estar en capacidad de desarrollarla.

resolver con la lista y no se le debe preguntar al usuario porque no se diseno la operacion constructoracon un parametro mas y por lo tanto hacer dicho pedido irıa en contra de la precondicion de la operacion.

92

4.2 Listas

Cursores

Para evitar el desplazamiento de los elementos en la implementacion con vectores sepuede separar la informacion en dos vectores: uno con los datos y otro con los ındices ocursores que muestran la ubicacion de los siguientes elementos. La gran ventaja esta en queinsertar o borrar elementos se reduce a cambiar algunos cursores, sin necesidad de moverelementos. La figura 4.8 muestra una lista representada con cursores.

'z' 'k' 'p' 'q'

0 1 2 3 4

. . .

MAX-15

'x'

6 7

2 6 1 3

0 1 2 3 4

. . .

MAX-15

4

6 7

DATOS

CURSORES

Figura 4.8: Lista implementada con cursores

El vector de cursores contiene el numero ındice de los siguientes elementos. Por ejemplo,para la figura 4.8, si el primer elemento esta en la posicion 0, entonces el segundo elementoesta en la posicion 2, el tercero esta en la posicion 1, el cuarto esta en la posicion 6 y elquinto esta en la posicion 4. Lo anterior quiere decir que la lista representada en dichafigura es la siguiente:

〈 ’z’, ’p’, ’k’, ’x’, ’q’ 〉

Notese que el utimo elemento de la lista (’q’), quien se encuentra en la posicion 4, tiene enel vector de cursores el numero 3. Esto significa que el siguiente elemento que se anexara ala lista quedara en la posicion 3 del vector de datos.

Al igual que la aproximacion con vectores, la constante MAX contiene el maximo numerode elementos que puede contener la lista. De esta manera, las listas con cursores tendranlos dos vectores, la constante MAX, y la posicion del primer elemento. Adicionalmente,para hacer mas eficiente la implementacion se tendra la posicion del ultimo elemento yla longitud de la lista como caracterıticas almacenadas. Por lo tanto, una lista de enterossera una estructura como la siguiente:

struct l i s t a{

int datos [MAX] , c u r s o r e s [MAX] ;int primero , ultimo , l ong i tud ;

} ;typedef struct l i s t a L i s t a ;

93


La operacion constructora inicializara todos los elementos de la estructura y las opera-ciones vaciaLista y longLista son evidentes.


L i s ta l s t ;for ( int i = 0 ; i < MAX; i++){

l s t . datos [ i ] = NULL;l s t . c u r s o r e s [ i ] = −1;

}l s t . primero = 0 ;l s t . u lt imo = 0 ;l s t . l ong i tud = 0 ;

return l s t ;}

Una funcion interesante es la insercion de un elemento en la posicion p. Lo que se debehacer es buscar una posicion vacıa diferente a la que hace referencia el ultimo elemento,copiar allı el nuevo elemento, colocar como su ındice la posicion del elemento de la listadonde se va a insertar (pos) y actualizar el ındice del elemento anterior (pos − 1). Porejemplo, si a la lista de la figura 4.8 se le va a insertar el elemento ’w’ en la posicion 4, elproceso se puede ver graficamente en el siguiente ejemplo:

Ejemplo 4.2.1Tenemos la siguiente lista:

'z' 'k' 'p' 'q'

0 1 2 3 4

. . .

MAX-15

'x'

6 7

2 6 1 3

0 1 2 3 4

. . .

MAX-15

4

6 7

DATOS

CURSORES

Para insertar el elemento ’w’ en la posicion 4 primero se inserta el elemento en una posicionvacıa.

'z' 'k' 'p' 'q'

0 1 2 3 4

. . .

MAX-1

'w'

5

'x'

6 7

2 6 1 3

0 1 2 3 4

. . .

MAX-15

4

6 7

DATOS

CURSORES

94

4.2 Listas

Luego se busca el cursor del elemento cuya posicion es 3 (marcado en la grafica con colorrojo).

'z' 'k' 'p' 'q'

0 1 2 3 4

. . .

MAX-1

'w'

5

'x'

6 7

2 6 1 3

0 1 2 3 4

. . .

MAX-15

4

6 7

DATOS

CURSORES

Luego se coloca como ındice el mismo numero del cursor del elemento 3.

'z' 'k' 'p' 'q'

0 1 2 3 4

. . .

MAX-1

'w'

5

'x'

6 7

2 6 1 3

0 1 2 3 4

. . .

MAX-1

6

5

4

6 7

DATOS

CURSORES

Por ultimo se actualiza el ındice de la posicion 3.

'z' 'k' 'p' 'q'

0 1 2 3 4

. . .

MAX-1

'w'

5

'x'

6 7

2 5 1 3

0 1 2 3 4

. . .

MAX-1

6

5

4

6 7

DATOS

CURSORES

? ? ?

El codigo de la funcion es el siguiente:



for ( int i = 0 ; i < l ongL i s t a ( l s t ) − 1 ; i++){

i f ( l s t . datos [ i ] == NULL && l s t . c u r s o r e s [ l s t . u lt imo ] != i ){

l s t . datos [ i ] = elem ;break ;

}

95


}int postemp = l s t . primero ;for ( int j = 0 ; j < pos − 2)

postemp = l s t . c u r s o r e s [ postemp ] ;l s t . c u r s o r e s [ i ] = l s t . c u r s o r e s [ postemp ] ;l s t . c u r s o r e s [ postemp ] = i ;

}

return l s t ;}

Esta funcion puede hacerse mas eficiente si se tiene una estructura de datos donde seencuentren las posiciones vacıas de la lista y, por lo tanto, no se necesite buscar una. Lasoperaciones de anxLista y elimLista se dejan como ejercicio para el estudiante.

4.2.3. Analisis de Complejidad de las Implementaciones

Al observar las diferentes aproximaciones que existen (las de las seccion anterior y mu-chas otras) la pregunta que surge es: ¿cual usar? La respuesta a esta pregunta dependemucho del computador donde se usara el TAD, el lenguaje de programacion en el que seimplementara y el uso que se le dara (su aplicacion).

Si se asume que se tiene una maquina con mucha memoria, es decir, no es importante estacondicion, y el lenguaje de programacion es C, o sea que disponemos de las herramientaspara desarrollar cualquier aproximacion, entonces la solucion solo depende del uso que se lede al TAD. De lo anterior se puede ver que el problema se reduce a analizar cada una de lasoperaciones. Es claro que las diferentes implementaciones del TAD Lista poseen diferentesalgoritmos, lo que conlleva a diferentes complejidades.

crearL anxL insL elimL infoL longL vaciaLEncadenadas Simple O(1) O(n) O(n) O(n) O(n) O(n) O(1)Doblemente Encadenadas O(1) O(n) O(n) O(n) O(n) O(n) O(1)Circulares Simple O(1) O(n) O(n) O(n) O(n) O(n) O(1)Circulares Dobles O(1) O(1) O(n/2) O(n/2) O(n/2) O(n) O(1)Vectores O(n) O(n) O(n) O(n) O(1) O(n) O(1)Cursores O(n) O(1) O(n) O(n) O(n) O(1) O(1)

Cuadro 4.1: Comparacion de complejidades en las implementaciones del TAD Lista

4.2.4. Utilizacion

En esta seccion se mostraran varios ejemplos de desarrollo de funciones adicionales ha-ciendo uso de las operaciones primitivas del TAD Lista. Estas operaciones adicionalesresuelven problemas utilizando las operaciones de listas (no importa que implementacionya que como se vio, todas las funciones tienen el mismo prototipo) y, aunque no hacenparte del TAD, enriquecen el uso de las listas.

96

4.2 Listas

Ejemplo 4.2.2 (Buscar un elemento)Se desea buscar un elemento en una lista y retornar su posicion. Una forma de resolvereste problema es realizando un recorrido por la lista desde el primer elemento hasta que seencuentre o se termine la lista (en este ultimo caso se retornara -1 haciendo entender queno se encuentra en la lista). En caso de haber elementos repetidos, se retorna la posiciondel primer elemento que se encuentre. La complejidad de este algoritmo es O(n) donde nes el tamano de la lista.

{pre : lst = 〈e1, . . . , ei, . . . , en〉, elem ∈ Elemento}{post : i si ∃i | ei = elem, −1 de lo contrario}

int busca rL i s ta ( L i s t a l s t , int elem ){

int pos = −1;for ( int i = 1 ; i <= longL i s t a ( l s t ) ; i++){

i f ( i n f o L i s t a ( l s t , i ) == elem ){

pos = i ;break ;

}}return pos ;

}

? ? ?

Ejemplo 4.2.3 (Invertir una lista)El problema de invertir una lista requiere recorrer la lista de entrada desde el ultimo ele-mento hasta el primero anexando cada elemento en otra lista. Su complejidad es O(n),donde n es el tamano de la lista.

{pre : lst = 〈e1, e2, . . . , en〉}{post : 〈en, . . . , e2, e1〉}

L i s ta i n v e r t i r L i s t a ( L i s t a l s t ){

L i s ta tmp = c r e a r L i s t a ( ) ;for ( int i = l ongL i s t a ( l s t ) ; i > 0 ; i−−)

tmp = anxLista (tmp , i n f o L i s t a ( l s t , i ) )return tmp ;

}

? ? ?

Ejemplo 4.2.4 (Equivalencia de listas)

97


Saber si dos listas son equivalentes requiere hacer un ciclo verificando si cada par de ele-mentos de las dos listas, en la misma posicion, son iguales. Esto trae consigo la condicionde que las listas deben tener el mismo tamano. Su complejidad es O(n), donde n es eltamano de la lista.

{pre : lst1 = 〈e1, . . . , ei, . . . , en〉 ∧ lst2 = 〈f1, . . . , fi, . . . , fm〉}{post : True si n = m ∧ ∀i ei = fi, 1 ≤ i ≤ n}

int i g u a l e s L i s t a s ( L i s t a l s t 1 , L i s t a l s t 2 ){

i f ( l ongL i s t a ( l s t 1 ) == longL i s t a ( l s t 2 ) ){

for ( int i = 1 ; i <= longL i s t a ( l s t 1 ) ; i++){

i f ( i n f o L i s t a ( l s t 1 , i ) != i n f o L i s t a ( l s t 2 , i ) )return 0 ;

}return 1 ;}else

return 0 ;}

? ? ?

Ejemplo 4.2.5 (Palındromes)Una lista es palındrome si puede leerse igual de derecha a izquierda o de izquierda a de-recha. Existen diversas formas de conocer si una lista es palındrome. En este ejemplo seusaran las operaciones que se han desarrollado anteriormente, es decir, primero invirtiendola lista y luego preguntando si la inversa es igual a la original. Su complejidad es O(2n),donde n es el tamano de la lista.

{pre : lst1 = 〈e1, . . . , ei, . . . , en〉}{post : True si ∀i ei = e(n+1)−i, 1 ≤ i ≤ n}

int palindrome ( L i s t a l s t ){

L i s ta tmp = i n v e r t i r L i s t a ( l s t ) ;i f ( i g u a l e s L i s t a s (tmp , l s t ) )

return 1 ;else

return 0 ;}

? ? ?

98

4.2 Listas

4.2.5. Variantes

En esta seccion se presentara una variante del TAD Lista mas especializada llamadaTAD Lista Ordenada.

Lista Ordenada

Una lista ordenada es una lista que cumple con la condicion de que para cada elemento dela lista, el siguiente es mayor y el anterior es menor. Adicionalmente no existen elementosrepetidos. A continuacion se muestra el diseno del TAD (la implementacion queda comoejercicio al estudiante).

TAD Lista Ordenada

� e1, . . . , en �

∀i ei < ei+1, ei ∈ Elemento 1 ≤ i < n, n ≥ 0


• crearListaOrd: → Lista• anxListaOrd: Lista× Elemento → Lista• elimListaOrd: Lista× Elemento → Lista• infoListaOrd: Lista× Entero → Elemento• estaListaOrd: Lista× Elemento → Booleano• longListaOrd: Lista → Entero• vaciaListaOrd: Lista → Booleano

crearListaOrd()“Construye una nueva lista ordenada, inicialmente vacıa”

{pre : TRUE}{post :��}

anxListaOrd(lst, elem)“Inserta un elemento en la lista ordenada”

{pre : lst =�� o lst =� e1, . . . , en �, elem ∈ Elemento}{post : lst =� elem� o lst =� e1, . . . , ei, elem, ei+1, . . . , en �

ei < elem < ei+1, respectivamente }

99


elimListaOrd(lst, elem)“Elimina el elemento dado de la lista ordenada”

{pre : lst =� e1, . . . , ei−1, ei, ei+1, . . . , en �}{post : lst =� e1, . . . , ei−1, ei+1, . . . , en � si ei = elem}

infoListaOrd(lst, pos)“Retorna el dato correspondiente a la posicion dada”

{pre : lst =� e1, . . . , epos, . . . , en �, 1 ≤ pos ≤ n}{post : epos}

estaListaOrd(lst, elem)“Informa si un elemento esta en la lista ordenada”

{pre : lst =� e1, . . . , ei, . . . , en �, 1 ≤ i ≤ n}{post : True si ∃i | ei = elem

False de lo contrario }

vaciaListaOrd(lst)“Informa si la lista esta vacıa (i.e. no contiene elementos)”

{pre : lst =�� o lst =� e1, . . . , en �}{post : True si lst =��

False si lst =� e1, . . . , en �}

longListaOrd(lst)“Retorna la longitud de la lista (i.e. numero de elementos)”

{pre : lst =�� o lst =� e1, . . . , en �}{post : 0 si lst =��

n si lst =� e1, . . . , en �}

4.3. Pilas

Una pila es una estructura de datos lineal tipo LIFO (Last In, First Out) ya que el ordende la secuencia de sus elementos es analogo a una pila de platos en una cafeterıa dondeel ultimo plato en ser colocado en la pila es usualmente el primero en ser usado. Entoncesen una pila, a diferencia de las listas, los elementos son adicionados y eliminados en unextremo, el cual es llamado el tope de la pila. Este tope es el unico elemento accesible dela pila.

100

4.3 Pilas

Las pilas son bastante usadas en computacion. Entre sus usos tenemos: para mantenerun registro de acciones en muchos programas y poder “deshacer” algunas o todas ellas(usualmente con el comando Ctrl-Z), en navegadores de internet con las direcciones recien-temente visitadas, para implementar recursion y backtracking, para evaluar de expresionesaritmeticas y en la ejecucion de algoritmos para mantener un rastro de los llamados afunciones y retornos y conocer el alcance de las variables.

Para visualizar mejor esta estructura de datos, se puede pensar en un recipiente comoel de las papas Pringles R© (ver figura 4.9). En dicho recipiente la unica papa visible es laque esta en el tope y ella es la unica que puede sacarse de la pila. Si se introduce unapapa al recipiente ella se convertira en el tope. De lo anterior se deduce que no es posibleconocer la cantidad de elementos que contiene una pila, para saberlo hay que sacar todoslos elementos y contarlos.

Figura 4.9: Ejemplo real de una pila

A continuacion se muestra el diseno formal del TAD Pila.

101


4.3.1. Diseno

TAD Pila

en...e1

∀i ei ∈ Elemento, n ≥ 0


• crearPila: → Pila• Push: Pila× Elemento → Pila• Pop: Pila → Pila• Peek: Pila → Elemento• vaciaPila: Pila → Booleano

crearPila()“Construye una nueva pila, inicialmente vacıa”

{pre : TRUE}{post : pil = }

Push(pil, elem)“Inserta un elemento en el tope de la pila”

{pre : pil =

en...e1

, elem ∈ Elemento}

{post : pil =

elemen...e1

}

102

4.3 Pilas

Pop(pil)“Elimina el elemento tope de la pila”

{pre : pil =

enen−1

...e1

}

{post : pil =

en−1...e1

}

Peek(pil)“Retorna el dato correspondiente al tope de la pila”

{pre : pil =

en...e1

}

{post : en}

vaciaPila(pil)“Informa si la pila esta vacıa (i.e. no contiene elementos)”

{pre : pil = o pil =

en...e1

}

{post : True si pil =

False de lo contrario }

103


4.3.2. Implementaciones

4.3.3. Utilizacion

4.4. Colas

4.5. Tablas Hash

4.6. Arboles Binarios

4.7. Arboles N-arios

4.8. Grafos

104

Indice alfabetico

Alcance, 68Apuntadores, 65

Calculo λ, 12Compilador, 41Complejidad, 16

Depuracion, 46

Evento, 59Excepcion, 52

Garbage Collector, 61

Indecidibilidad, 11Interfaz, 57

Lenguaje de Programacion, 35Ligadura, 70

Maquina de Turing, 14Maquina Virtual, 44

NP-Completitud, 25

Problema, 11Programa, 35

Referencia, 60

Semantica, 40Sintaxis, 38

Tipo de dato, 66Tratabilidad, 16

Visibilidad, 72

105

Bibliografıa

[1] Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques,and Tools. Addison Wesley, 1986.

[2] David M. Beazley. Python Essential Reference. Sams, 3rd edition, 2006.

[3] Boris Beizer. Software Testing Techniques. Van Nostrand Reinhold Company, 1983.

[4] Barry B. Brey. The Intel Microprocessors 8086/8088, 80186, 80286, 80386 and 80486.Architecture, Programming and Interfacing. Prentice Hall, 3rd edition, 1994.

[5] Osvaldo Cairo and Silvia Guardati. Estructuras de Datos. McGraw-Hill, 3rd edition,2006.

[6] Luca Cardelli. Type Systems, chapter 103. Handbook of Computer Science and Engi-neering. CRC Press, 1997.

[7] Rodrigo Cardoso. Verificacion y Desarrollo de Programas. Ediciones Uniandes, 1991.

[8] Stephen A. Cook. The complexity of theorem-proving procedures. In 3rd AnnualACM Symposium on the Theory of Computing, pages 151–158, 1971.

[9] Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction toAlgorithms. Mc Graw Hill, 1990.

[10] Vinay Deolalikar. P 6= NP. HP Research Labs, Palo Alto, August 2010.

[11] Matthias Felleisen, Robert Bruce Findler, Matthew Flatt, and Shriram Krishnamurthi.How to Design Programs: An Introduction to Programming and Computing. The MITPress, 2001.

[12] Daniel P. Friedman, Mitchell Wand, and Christopher T. Haynes. Essentials of Pro-gramming Languages. The MIT Press, second edition, 2001.

[13] Yedidyah Langsam, Moshe J. Augenstein, and Aaron M. Tenenbaum. Data StructuresUsing C and C++. Prentice Hall, 2nd edition, 1995.

[14] Zbigniew Michalewicz and David B. Fogel. How To Solve It: Modern Heuristics.Springer, 2000.

107

Bibliografıa

[15] Bradley N. Miller and David L. Ranum. Problem Solving With Algorithms And DataStructures Using Python. Franklin, Beedle & Associates, Inc., 2006.

[16] Roger Penrose. The Emperor’s New Mind. Oxford University Press, 1989.

[17] George Polya. How to Solve It: A New Aspect of Mathematical Method. PrincetonUniversity Press, 1945.

[18] Terrence W. Pratt and Marvin V. Zelkowitz. Programming Languages: Design andImplementation. Prentice Hall, 1984.

[19] Bruno R. Preiss. Data Structures and Algorithms with Object-Oriented Design Pat-terns in Java. Wiley, 1999.

[20] Roger S Pressman. Software Engineering: A Practitioner’s Approach. McGraw-Hill,2004.

[21] Stuart M. Shieber. Course notes for cs152 principles of programming languages, No-vember 1995.

[22] Guido van Rossum. Python Tutorial. Python Software Foundation, Release 2.5, 19thSeptember 2006.

[23] Jorge A. Villalobos. Diseno y Manejo de Estructuras de Datos en C. Mc Graw Hill,1996.

108

Documents

Fundamentos y Estructuras de Programaci on - DECCcic.puj.edu.co/wiki/lib/exe/fetch.php?media=materias:fundestprog:... · 2 Noci on de Problema Un problema existe cuando el estado