• Author / Uploaded
• molivares87

• Categories
• Algoritmos
• Lenguaje de programación
• Puntero (Programación de computadora)
• Programación de computadoras
• Objeto (informática)

Citation preview

Algoritmos Avanzados

Tema 1

1.1

RESOLUCIÓN DE PROBLEMAS

La habilidad de programar ordenadores constituye una de las bases necesarias de todo profesional de las ciencias de la computación. Pero, por encima del nivel de programación, la característica fundamental de un profesional del área es su capacidad para resolver problemas. La resolución de problemas informáticos en la vida real implica otras muchas mas habilidades que únicamente saber programar –habilidades que distinguen a un ingeniero de un simple programador. Implica comprender y analizar las necesidades de los problemas, saber modelarlos de forma abstracta diferenciando lo importante de lo irrelevante, disponer de una variada batería de herramientas conceptuales que se puedan aplicar en su resolución, trasladar un diseño abstracto a un lenguaje y entorno concretos y, finalmente, ser capaz de evaluar la corrección, prestaciones y posibles inconvenientes de la solución planteada. Las herramientas que surgen en el desarrollo de programas son esencialmente de dos clases: estructuras de datos y algoritmos. Las estructuras de datos representan la parte estática de la solución al problema, el componente almacenado, donde se encuentran los datos de entrada, de salida y los necesarios para posibles cálculos intermedios. Los algoritmos representan la parte dinámica del sistema, el componente que manipula los datos para obtener la solución. Algoritmos y estructuras de datos se relacionan de forma muy estrecha: las estructuras de datos son manipuladas mediante algoritmos que añaden o modifican valores en las mismas; y cualquier algoritmo necesita manejar datos que estarían almacenados en cierta estructura. La idea se puede resumir en la fórmula magistral de Niklaus Wirth:

Algoritmos + Estructuras de datos = Programas

En ciertos ámbitos de aplicación predominara la componente algorítmica –como, por ejemplo, en problemas de optimización y cálculo numérico - y en otros la componente de estructuras –como en entornos de bases de datos y sistemas de información, pero cualquier aplicación requerirá siempre de ambos. Esta dualidad aparece en el nivel abstracto: un tipo abstracto esta formado por un dominio de valores (estructura abstracta) y un conjunto de operaciones (algoritmos abstractos). Y la dualidad se refleja también en el nivel de implementación: un módulo (en lenguajes estructurados) o una clase (en lenguajes orientados a objetos) están compuestos por una estructura de atributos o variables, y una serie de procedimientos de manipulación de los anteriores. Antes de entrar de lleno en el estudio de los algoritmos y las estructuras de datos, vamos a analizar los pasos que constituyen el proceso de resolución de problemas.

Lic. Carmen Mollinedo

1

Algoritmos Avanzados

1.1.1 ANÁLISIS DE REQUISITOS DE PROBLEMA El proceso de resolución de problemas parte siempre de un problema, de un enunciado más o menos claro que alguien plantea. El primer paso es la comprensión del problema, entender las características y peculiaridades de lo que se necesita. Este análisis de los requisitos del problema puede ser, de por si, una de las grandes dificultades; sobre todo en grandes aplicaciones, donde los documentos de requisitos son ambiguos, incompletos y contradictorios. El análisis debe producir como resultado un modelo abstracto del problema. El modelo abstracto es un modelo conceptual, una abstracción del problema, que reside exclusivamente en la mente del individuo y donde se desechan todas las cuestiones irrelevantes para la resolución del problema. Supongamos, por ejemplo, los dos siguientes problemas, con los cuales trabajaremos en el resto de los puntos. Ejemplo 1 El problema de las cifras. Dado un conjunto de seis números enteros, que pueden ser del 1 al 10, 25, 50, 75 ó 100, encontrar la forma de conseguir otro entero dado entre 100 y 999, combinando los números de partida con las operaciones de suma, resta, producto y división entera. Cada uno de los seis números iniciales sólo se puede usar una vez.

Ejemplo 2 El problema de detección de caras humanas. Dada una imagen en color en un formato cualquiera (por ejemplo, bmp, jpeg o gif) encontrar el número de caras humanas presentes en la misma y la posición de cada una de ellas

Lic. Carmen Mollinedo

2

Algoritmos Avanzados

Ambos enunciados representan categorías de problemas muy distintas. El problema 1 tiene un enunciado más o menos claro, aunque cabrían algunas dudas. Es de tipo matemático, se puede modelar formalmente y es previsible que exista un algoritmo adecuado. El problema 2 tiene un enunciado más corto pero mucho más ambiguo, no está claro exactamente lo que se pide. Es más, incluso teniéndolo bien claro, el problema parece más adecuado para ser resuelto por un humano, pero difícil de implementar en un ordenador. Aun así, ambos problemas tienen algo en común: son de interés, así que necesitamos resolverlos de la mejor forma que podamos.

1.1.2 MODELADO DEL PROBLEMA Y ALGORITMOS ABSTRACTOS El primer paso sería crear un modelo abstracto, en el que nos quedamos con lo esencial del problema. Normalmente, este modelo se crea a través de una analogía con algo conocido previamente. Por ejemplo, para enseñar a un alumno inexperto lo que es un algoritmo (concepto para él desconocido) se utiliza la analogía con una receta de cocina, y las estructuras de datos se asimilan con la disposición de armarios, cajones y recipientes donde se guardan los ingredientes y el bizcocho resultante.

1.1.3. DISEÑO DE LA SOLUCIÓN Una vez que tengamos un modelo completo y adecuado, significará que hemos entendido bien el problema. Como hemos visto en los ejemplos, el modelo conlleva también un algoritmo informal, que no es más que una vaga idea de cómo resolver el problema. El siguiente paso de refinamiento consistiría en diseñar una solución. Usando otra analogía, el diseño de un programa es equivalente a los planos de un arquitecto: el diseño describe el aspecto que tendrá el programa, los materiales que se necesitan y dónde y cómo colocarlos. El diseño es siempre un paso previo a la implementación, pero que se olvida muy a menudo por los programadores primerizos. Un ingeniero informático debería ser tan consciente del error de programar sin partir de un buen diseño previo, como lo es un arquitecto del fallo de hacer un puente sin tener antes los planos. El diseño de un programa consta de dos clases de elementos: tipos de datos y algoritmos. Los tipos de datos usados a nivel de diseño son tipos abstractos, en los cuales lo importante son las operaciones que ofrecen y no la representación en memoria. Los algoritmos son una versión refinada de los algoritmos abstractos del paso anterior. No obstante, son aún algoritmos en pseudocódigo, donde se dan cosas por supuestas. Definir los tipos de datos para almacenar la solución suele ser mucho más difícil que definirlos para los datos de entrada. Además, modificaciones en los algoritmos pueden requerir cambios en los tipos de datos y viceversa.

1.1.4. IMPLEMENTACIÓN DEL DISEÑO El siguiente paso en la resolución del problema es la implementación. La implementación parte del diseño previo, que indica qué cosas se deben programar, cómo se estructura la solución del problema, dónde colocar cada funcionalidad y qué se espera en concreto de cada parte en la que se ha descompuesto la solución. Esta descripción de lo que debe hacer cada parte es lo que se conoce como la especificación. Una implementación será

Lic. Carmen Mollinedo

3

Algoritmos Avanzados correcta si cumple su especificación. La dualidad tipos/algoritmos del diseño se traslada en la implementación a estructuras/ algoritmos. Para cada uno de los tipos de datos del diseño, se debe elegir una estructura de datos adecuada. Por ejemplo, los dos ejemplos de problemas analizados necesitan listas. Una lista se puede representar mediante una variedad de estructuras: listas enlazadas con punteros o cursores, mediante celdas adyacentes en un array, enlazadas simple o doblemente, con nodos cabecera o no, etc. La elección debe seguir los criterios de eficiencia –en cuanto a tiempo y a uso de memoria– que se hayan especificado para el problema. En cada caso, la estructura más adecuada podrá ser una u otra.

1.1.5. VERIFICACIÓN Y EVALUACIÓN DE LA SOLUCIÓN La resolución de un problema no acaba con la implementación de un programa. Los programas deberían ser comprobados de forma exhaustiva, verificando que se ajustan a los objetivos deseados, obtienen los resultados correctos sin provocar fallos de ejecución. En la práctica, hablamos de un proceso cíclico de desarrollo: implementar, verificar, corregir la implementación, volver a verificar, volver a corregir, etcétera. En cierto momento, puede que tengamos que cambiar el diseño, e incluso puede que lo que esté fallando sea el modelo abstracto. Cuanto más atrás tengamos que volver, más tiempo habremos perdido haciendo cosas que luego resultan inútiles.

Ciclo del desarrollo del software

1.2 ALGORITMOS Como ya hemos visto, los algoritmos junto con las estructuras de datos constituyen los dos elementos imprescindibles en el proceso de resolución de problemas. Los primeros definen el componente manipulador y los segundos el componente almacenado, y se combinan estrechamente para crear soluciones a los problemas. No está de más recordar que la historia de los algoritmos es mucho anterior a la aparición de los ordenadores. De hecho, podríamos datar la aparición de los algoritmos al primer momento en que los seres humanos se plantearon resolver problemas de forma genérica. Históricamente uno de los primeros algoritmos inventados, para la resolución de problemas de tipo matemático, es el algoritmo de Euclides de Alejandría, Egipto, propuesto alrededor del año 300 a.C. Euclides propone el siguiente método para calcular el máximo común divisor de dos números enteros.

Lic. Carmen Mollinedo

4

Algoritmos Avanzados Ejemplo 3 Algoritmo de Euclides para calcular el máximo común divisor de dos números enteros, a y b, siendo a > b. 1. Hacer r= a módulo b 2. Si r = 0 entonces el máximo común divisor es b 3. En otro caso: 3.1. Hacer a= b 3.2. Hacer b= r 3.3. Volver al paso 1 Pero el honor de dar nombre al término algoritmo lo recibe el matemático árabe del siglo IX Muhammad ibn Musa al-Khwarizmi (que significa algo así como Mohamed hijo de Moisés de Khorezm, en Oriente Medio). Sus tratados sobre la resolución de ecuaciones de primer y segundo grado ponen de relieve la idea de resolver cálculos matemáticos a través de una serie de pasos predefinidos. Por ejemplo, para resolver ecuaciones de segundo grado del tipo: x2 + bx = c, define la siguiente serie de pasos7. Ejemplo .4 Algoritmo de al-Khwarizmi para resolver la ecuación x2 + bx = c. Se muestra el ejemplo x2 + 10x = 39, el mismo que al-Khwarizmi utiliza en su libro “Hisab al-jabr w’al-muqabala” (“El cálculo de reducción y restauración”), sobre el año 825 d.C. 1. Tomar la mitad de b. (En el ejemplo, 10/2 = 5) 2. Multiplicarlo por sí mismo. (En el ejemplo, 5 * 5 = 25) 3. Sumarle c. (En el ejemplo, 25 + 39 = 64) 4. Tomar la raíz cuadrada. (En el ejemplo,√64 = 8) 5. Restarle la mitad de b. (En el ejemplo, 8 − 10/2 = 8 − 5 = 3) El resultado es , expresado algorítmicamente. El matemático bagdad es también considerado como el introductor del sistema de numeración arábigo en occidente, y el primero en usar el número 0 en el sistema posicional de numeración.

1.2.1. DEFINICIÓN Y PROPIEDADES DE ALGORITMO En la siguiente figura se destaca la concepción de algoritmo como caja negra

Interpretación de los algoritmos como cajas negras A continuación se presentan dos definiciones formales de algoritmos:

Lic. Carmen Mollinedo

5

Algoritmos Avanzados

Definición 1 Un algoritmo es una serie de reglas que dado un conjunto de datos de entrada (posiblemente vacío) produce unos datos de salida (por lo menos una) y cumple las siguientes propiedades:
Definibilidad. El conjunto de reglas debe estar definido sin ambigüedad, es decir, no pueden existir dudas sobre su interpretación.
Finitud. El algoritmo debe constar de un número finito de pasos, que se ejecuta en un tiempo finito y requiere un consumo finito de recursos.

Definición 2: “Un algoritmo es un conjunto de instrucciones sencillas, claramente especificadas, que se debe seguir para resolver un problema. Una vez que se da un algoritmo para un problema y se decide que es correcto, un paso importante es determinar la cantidad de recursos, como tiempo o espacio, que requerirá”

DEFINICIÓN DE KNUTH Una definición más formal de algoritmo se puede encontrar en el libro de Knuth: Definición 1.1 Un método de cálculo es una cuaterna (Q, I,W,f) donde: Q es un conjunto que contiene a I y W, y f : Q → Q con f(w) = w para todo w perteneciente a W. Q es el conjunto de estados del cálculo, I es el conjunto de estados de entrada, W es el conjunto de estados de salida y f es la regla de cálculo. Definición 1.2 Una secuencia de cálculo es x0, x1, x2; . . . donde x0 ∈ I y ∀ k ≥ 0 f(xk) = xk+1. La secuencia de cálculo acaba en n pasos si n es el menor entero con xn ∈ W.

Veamos cómo esta definición formal de algoritmo (el método de cálculo) cumple las propiedades que debe de cumplir un algoritmo: • • •

Se cumplirá el concepto de finitud si toda secuencia de cálculo a la que pueda dar lugar el método de cálculo es finita. Existe un conjunto de posibles entradas, que es I en la definición. Existe un conjunto de posibles salidas, que es W en la definición.

Lic. Carmen Mollinedo

6

Algoritmos Avanzados • •

En cuanto a la definibilidad, el algoritmo está definido con el método de cálculo, pero, dado un método de cálculo, ¿se puede hacer un programa?,¿en qué lenguaje?, ¿en un tiempo razonable? El método de cálculo será eficiente si el valor de n en cada secuencia de cálculo un valor "razonable".

No todo lo que aparece en informática son algoritmos. Un ejemplo típico de algo que no es un algoritmo es un sistema operativo. El sistema operativo consta de una serie de instrucciones, pero no se le prevé una ejecución finita, sino que debería poder ejecutarse mientras no se requiera lo contrario. Algoritmos deterministas y no deterministas Según un algoritmo produzca o no siempre los mismos valores de salida para las mismas entradas, clasificamos los algoritmos en dos tipos: Algoritmos deterministas. Para los mismos datos de entrada producen siempre los mismos datos de salida. Algoritmos no deterministas. Para los mismos datos de entrada pueden producir diferentes salidas. El no determinismo puede chocar un poco con la idea de definibilidad. Sin embargo, ambas propiedades no son contradictorias. Por ejemplo, el resultado de un algoritmo paralelo, que se ejecuta en distintos procesadores, puede depender de cuestiones de temporización que no forman parte de los datos del problema. La existencia del no determinismo hace que un algoritmo no siempre se pueda ver como una función –en sentido matemático de la forma f : ENTRADA → SALIDA.

1.3 LA DISCIPLINA DE LA ALGORÍTMICA Si bien, como hemos visto, la historia de los algoritmos se remonta muy atrás, el estudio de los algoritmos no se concibió como una disciplina propia hasta bien entrada la mitad del pasado siglo XX. Actualmente, entendemos la algorítmica como la disciplina, dentro del ámbito de la informática, que estudia técnicas para construir algoritmos eficientes y técnicas para medir la eficiencia de los algoritmos. En consecuencia, la algorítmica consta de dos grandes áreas de estudio: el análisis y el diseño de algoritmos. Pero, ¿cuál es el objetivo último de la algorítmica?, ¿qué es lo que motiva su estudio? El objetivo último es dado un problema concreto ser capaz de resolverlo de la mejor forma posible, de forma rápida, corta, elegante y fácil de programar. Y recordemos que en esta resolución entran también en juego las estructuras de datos, que son manejadas por los algoritmos. En definitiva, todos los ejemplos, técnicas, métodos y esquemas que vamos a estudiar tienen como finalidad última servir de herramientas útiles en el momento de afrontar la resolución de un problema completamente nuevo y desconocido. La Algoritmia nos permite evaluar el efecto de los diversos factores externos sobre los algoritmos disponibles, de tal modo que sea posible seleccionar el que más se ajusta a nuestras circunstancias particulares; también es la ciencia que nos indica la forma de diseñar un nuevo algoritmo para una tarea concreta.

Lic. Carmen Mollinedo

7

Algoritmos Avanzados

La algoritmia es uno de los pilares de la programación y su relevancia se muestra en el desarrollo de cualquier aplicación, más allá de la mera construcción de programas. Este es un texto introductorio sobre análisis y diseño de algoritmos que pretende exponer al lector las técnicas básicas para su diseño e implementación, así como presentar unas herramientas que le permitan medir su efectividad y eficiencia.

1.4 PARADIGMAS DE LA PROGRAMACION Un paradigma está constituido por los supuestos teóricos generales, las leyes y las técnicas para su aplicación que adoptan los miembros de una determinada comunidad científica.

Las leyes explícitamente establecidas y los supuestos teóricos. Por ejemplo, las leyes de movimiento de Newton forman parte del paradigma newtoniano y las ecuaciones de Maxwell forman parte del paradigma que constituye la teoría electromagnética clásica. El instrumental y las técnicas instrumentales necesarios para hacer que las leyes del paradigma se refieran al mundo real. La aplicación en astronomía del paradigma newtoniano requiere el uso de diversos telescopios, junto con técnicas para su utilización y diversas técnicas para corregir los datos recopilados. Un componente adicional de los paradigmas lo constituyen algunos principios metafísicos muy generales que guían el trabajo dentro del paradigma. Todos los paradigmas, además, contienen prescripciones metodológicas muy generales tales como: "Hay que intentar seriamente compaginar el paradigma con la naturaleza".

Podemos decir que, los paradigmas son marcos de referencia que imponen reglas sobre cómo se deben hacer las cosas, indican qué es válido dentro del paradigma y qué está fuera de sus límites. Un paradigma distinto implica nuevas reglas, elementos, límites y maneras de pensar, o sea implica un cambio. Los paradigmas pueden ser considerados como patrones de pensamiento para la resolución de problemas. Desde luego siempre teniendo en cuenta los lenguajes de programación, según nuestro interés de estudio. Los paradigmas de Programación representan un enfoque particular o filosofía para la construcción del software. No es mejor uno que otro sino Lic. Carmen Mollinedo

8

Algoritmos Avanzados que cada uno tiene ventajas y desventajas. También hay situaciones donde un paradigma resulta más apropiado que otro. Generalmente los autores clasifican los paradigmas de modos similares, siempre destacan el imperativo, el orientado a objetos, el funcional y el lógico. Algunos autores o profesores, mencionan paradigmas heurísticos, concurrentes, procedimentales, declarativos y demostrativos.

1.4.1 PARADIGMA FUNCIONAL Modelo matemático de composición funcional donde el resultado de un cálculo es la entrada del siguiente, y así sucesivamente hasta que una composición produce el valor deseado. El paradigma funcional está representado por la familia de lenguajes LISP, en particular Scheme o Haskell.

1.4.2 PARADIGMA IMPERATIVO El paradigma imperativo es considerado el más común y está representado, por ejemplo, por el C o por BASIC. El Paradigmas Imperativo es un modelo abstracto que consiste en un gran almacenamiento de memoria donde la computadora almacena una representación codificada de un cálculo y ejecuta una secuencia de comandos que modifican el contenido de ese almacenamiento. Algoritmos + Estructura de Datos = Programa.

1.4.3 PARADIGMA ORIENTADO A OBJETOS Disciplina de ingeniería de desarrollo y modelado de software que permite construir más fácilmente sistemas complejos a partir de componentes individuales. Objetos + Mensajes = Programa.

Lic. Carmen Mollinedo

9

Algoritmos Avanzados

Tema 2

2.1. INTRODUCCIÓN El análisis de algoritmos es la parte de la algorítmica que estudia la forma de medir la eficiencia de los algoritmos. Pero ¿cuándo decimos que un algoritmo es más o menos eficiente? Utilizando un punto de vista empresarial, podemos definir la eficiencia como la relación entre recursos consumidos y productos obtenidos. Se trata, por lo tanto, de una nueva formulación de la bien conocida ley del mínimo esfuerzo: maximizar los resultados, minimizando el esfuerzo. Los resultados que ofrece un algoritmo pueden ser de distintos tipos:
Un algoritmo puede resolver el problema de forma muy precisa, si es de tipo matemático, o garantizar el óptimo, en problemas de optimización, o encontrar siempre la solución, si es de satisfacción de restricciones.
Otro algoritmo puede ser que sólo encuentre soluciones aproximadas, o más o menos cercanas al óptimo, pero siempre encuentre alguna.
Finalmente, otro algoritmo puede que encuentre soluciones sólo en determinados casos, buenas o malas, y en otros casos acabe sin devolver ninguna respuesta. Por otro lado, los recursos que consume un algoritmo pueden ser de distintos tipos. Entre los más importantes tenemos:    

Tiempo de ejecución, desde el inicio del programa hasta que acaba. Utilización de memoria principal. Número de accesos a disco, a la red o a otros periféricos externos. Número de procesadores usados, en el caso de los algoritmos paralelos, etc.

En aplicaciones distintas puede que el recurso crítico sea diferente. En la mayoría de los casos, el recurso clave es el tiempo de ejecución, por lo que muchas veces se asocia eficiencia con tiempo. Pero, recordemos, ni el tiempo es el único recurso, ni el tiempo por sí solo mide la eficiencia, si no que se debe contrastar con los resultados obtenidos. En conclusión, un algoritmo será mejor cuanto más eficiente sea. No obstante, el sentido común nos dice que habrán otros muchos criterios para decidir lo bueno que es un algoritmo. Por ejemplo, será importante: que sea fácil de entender y de programar, que sea corto en su extensión, que sea robusto frente a casos extraños, que se pueda reutilizar en otros problemas, que se pueda adaptar, etc. Lic. Carmen Mollinedo

10

Algoritmos Avanzados

2.2 FACTORES EN LA MEDICIÓN DE RECURSOS Supongamos el siguiente algoritmo sencillo, que realiza una búsqueda secuencial dentro de un array de enteros. La cuestión que se plantea es ¿cuántos recursos, de tiempo de ejecución y memoria, consume el algoritmo? Ejemplo 1 operación BusquedaSec (x, n: entero; a: array [1..n] de entero): entero i= 0 repetir i:= i + 1 hasta a[i] = x or ib Tienen un T(n)=1, donde n es el tamaño (no conocido en este ejemplo) de la entrada 2.5 NOTACIONES PARA EXPRESAR LA COMPLEJIDAD EN TIEMPO Una medida asintótica es un conjunto de funciones que muestran un comportamiento similar cuando los argumentos toman valores muy grandes. Las medidas asintóticas se definen en términos de una función de referencia f. T(n) tiempo de ejecución de un programa con una entrada de tamaño n Notación Ω() Una función T(n) es Ω(g(n)) sí y solo sí existen unas constantes c y n0 tales que cg(n) ≤ T(n) cuando n0≤n Notación θ() Una función T(n) es θ(h(n)) sí y solo sí se cumple que existen unas constantes positivas c1, c2 y n0 independientes de n tales que: c1g(n) ≤ T(n) ≤ c2g(n) ∀ n0≤n

Lic. Carmen Mollinedo

13

Algoritmos Avanzados

Notación O(): De manera formal se dice que una función f(n) es de orden O(g(n)) sii se cumple que existen unas constantes positivas c y n0 , ambas independientes tales que: f(n) ≥ c g(n) , ∀ n ≥ n0 donde decidir que f(n) es O(g(n)) supone que cg(n) es una cota superior del tiempo de ejecución del algoritmo Las notaciones se interpretan también de la siguiente forma: O(T): Orden de complejidad de T. Ω(T): Orden inferior de T, u omega de T. Θ(T): Orden exacto de T.

2.5.1 PROPIEDADES DE LA NOTACIÓN O() Para cualquier par de funciones f(n) y g(n) se verifican las siguientes propiedades: Pr1: cO(f(n)) es O(f(n)), donde c es una constante Pr2: Regla de la suma: O(f(n) + g(n)) es max(O(f(n)), O(g(n)) Pr3: O(f(n)) + O(g(n)) es O(f(n)+g(n)) Pr4: O(f(n))O(g(n)) es O(f(n)g(n)) Pr5: O(O(f(n))) es O(f(n)) Lo que buscamos es determinar matemáticamente la cantidad de recursos

Ejemplo 2 Determine O(g(n)) T(n)=2n es O(n), donde 2 es una constante T(n)=n3 + n2 + log n es O(n3) puesto que n3 es el mayor T(n)=nm+n es O(nm), si la entrada depende de n y m O(O(n3)) es O(n3) T(n) = 2n2/5 + 3π/2; T(n) ∈ O(n2). O T(n) e O(n) Ejemplo 3 a) Sea el segmento de algoritmo X=1 . . . . . .1 Z=6 . . . . . . 1

El tiempo de ejecución es T(n)= 1+1= 2 aplicando la “regla de la suma” lo cual es O(1) por la propiedad Pr3

Lic. Carmen Mollinedo

14

Algoritmos Avanzados

Ejemplo 4 Sea el segmento de algoritmo For i=1 to 10 do Begin x=x+1 ..............1 y=y/i.................1 end T(n)=T(for)*T(instrucciones internas del for)=10*2=12 por la propiedad de la multiplicación y es O(1) por Pr 2

2.5.2 ORDENES DE COMPLEJIDAD

donde: O(1) ⊂ O(log n) ⊂ O(√n ) ⊂ Ì O(n) ⊂ O(n log n) ⊂ O(n2) ⊂ O(n3) ⊂ ... ⊂ O(nk) ⊂ ...O(2n ) ⊂ O(n!) 2.6 ANÁLISIS DE ALGORITMOS A continuación se enumeran algunas reglas importantes para el análisis de programas. a) Ciclos for El tiempo de ejecución de un ciclo for, es a lo más el tiempo de ejecución de las instrucciones que están en el interior del ciclo for (incluyendo las condiciones), por el número de iteraciones. Generalmente se usa el símbolo de sumatoria Ejemplo 5 for i:=1 to n do x:=x+1;

Lic. Carmen Mollinedo

15

Algoritmos Avanzados n

Ta (n) = T(for_i) * T(instr_internas) = ∑1 = n i =1

b) Ciclos for anidados Analizar de adentro hacia fuera. El tiempo de ejecución total de una proposición dentro del grupo, de ciclos for anidados es el tiempo de ejecución de la proposición multiplicada por el producto de los tamaños de todos los ciclos for. T(For/nivel1)*T(For/Nivel2)* . . . *T(For/nivelN)

Ejemplo 6 for i:=1 to n do for j:=1 to n do for k:=1 to n do x:=x+1; n  n  n  n  n  n Ta ( n) = T(for_i) * T(for_j) * T(for_k) * 1 = ∑  ∑  ∑1  = ∑  ∑ n  = ∑ (n * n ) = n * n * n = n 3 i =1  j =1  k =11   i =1  j =1  i =1

que es O(n3) orden cúbico

c) Para If / Else

T(IF_THEN) = T(condición)+T(Then) T(IF_THEN_ELSE) = T(condición)+max(T(Then),T(Else))

Ejemplo 7 i) if N mod 2 = 0 then for i:=1 to n do x:=x+1;

ii) if N> 0 then x:=x+N; else

Lic. Carmen Mollinedo

Ta(n)= T(if_then)=T(condición)+T(then) n

= 1 + ∑ 1 = 1 + n es O(n)orden lineal i =1

Tb(n)= T(if_then_else) = T(condición)+max(T(then),T(else)) = 1 + max(1,2) = 1 + 2 = 3 es O(1)orden lconstante

16

Algoritmos Avanzados

begin N=N+100 Z=z+N Endélse La noción de esta estructura selectiva se puede extender al uso del CASE (selección múltiple)

d) While Se realiza generalmente un análisis inductivo exhaustivo mediante una variable axiliar t cuya misión es contar el tiempo del while. Además se realiza el análisi del peor de los casos de entrada al bucle. Ejemplo 8 ¿Cuántas multiplicaciones realiza el siguiente algoritmo para calcular potencias, en el peor de los casos? Funcion potencia1(y : num; z : nat): nat p := 1 1 mientras z > 0 hacer p := p * y 1 z := z –1 1 z+1 fmientras función Analizando solamente la sentencia mientras se tiene

t=0 mientras z > 0 hacer z = z -1 t = t +1

z 4 3 2 1 0

t 0 1 2 3 4

El tiempo del mientras (while) es: z +1 la ctte 1 se adiciona debido a la última pregunta de condición del while

Finalmente: Tpotencia1(z) = 1 + (z+1)2 = 1 + 2z + 2 = 3 + 2z que es O(z) orden lineal

Lic. Carmen Mollinedo

17

Algoritmos Avanzados

2.7 LLAMADAS A PROCEDIMIENTOS Y FUNCIONES Si se tiene un programa con procedimientos no recursivos es posible calcular el tiempo de ejecución de los distintos procedimientos, uno a la vez partiendo de aquellos que no llaman a otros. Las siguientes formulas serán útiles para la resolución de ejercicios y algunas serán usadas en esta sección n

a) ∑1 = n i =1 n

b)∑ 1 = (n − a + 1). i=a n

c )∑ i = i =1

n(n + 1) . 2

n

d )∑ i 2 = i =1 n

e) ∑ i r = i =1

Lic. Carmen Mollinedo

n(n + 1)(2n + 1) 6 n r +1 (r + 1) + p r (n)

18

Algoritmos Avanzados

2.8 EJERCICIOS RESUELTOS

Mediante la notación asintótica, obténganse los tiempos de ejecución del peor caso supuesto para cada uno de los procedimientos siguientes como una función de n Ejercicio 1 i:=1; while I 1

Sc tiene a=4 v b=2 d(n)=n función Motriz. d(2)=8 Abora Comparemos con los tres casos se tiene que a>d( 2) => 4 T(n)= O(8logn) Por propiedades de log se tiene O(n3)

Lic. Carmen Mollinedo

28

Algoritmos Avanzados

Tema 3

Para procesar información en un computador es necesario hacer una abstracción de los datos que tomamos del mundo real. Se hace una selección de los datos más representativos de la realidad a partir de los cuales pueda trabajar el computador para obtener unos resultados.




RECUERDE abstracción en el sentido de que se ignoran algunas propiedades de los objetos reales, es decir, se simplifican

El objetivo de las Estructuras de Datos, es el estudio de la representación de la información (datos) que permitan obtener un algoritmo lo más sencillo posible. Identificar y desarrollar de modo formal las entidades y las operaciones que definen la información que se trata, así como determinar qué tipos de problemas pueden resolverse utilizando estas operaciones y entidades. Determinar la representación más idónea de estas estructuras abstractas e implementarlas.

3.1 CONCEPTOS FUNDAMENTALES 3.1.1 TIPOS DE DATOS Cualquier lenguaje suministra una serie de tipos de datos simples, como son los números enteros, caracteres, números reales. En realidad suministra un subconjunto de éstos, pues la memoria del ordenador es finita. Los punteros (si los tiene) son Lic. Carmen Mollinedo

23

Algoritmos Avanzados también un tipo de datos. El tamaño de todos los tipos de datos depende de la máquina y del compilador sobre los que se trabaja. En principio, conocer la representación interna de estos tipos de datos no es necesaria para realizar un programa, pero sí puede afectar en algunos casos al rendimiento. Por otra parte es posible definir otros tipos de estructuras de datos compuestos, entre las cuales se encuentran los arreglos, registros y otros.

Los lenguajes de programación (LP) proporcionan herramientas para manejar distintos tipos de datos. • Tipos predefinidos o proporcionados por el LP o sólo nos preocupamos de su uso • Tipos definidos por el usuario o S puede elegir y definir una estructura de datos de las proporcionadas por el LP para su representación o Se debe elegir y definir operaciones de manipulación o Se debe garantizar el correcto comportamiento del tipo

3.1.2 ESTRUCTURA DE DATOS Se trata de un conjunto de variables de un determinado tipo agrupadas y organizadas de alguna manera para representar un comportamiento. Lo que se pretende con las estructuras de datos es facilitar un esquema lógico para manipular los datos en función del problema que haya que tratar y el algoritmo para resolverlo. En algunos casos la dificultad para resolver un problema radica en escoger la estructura de datos adecuada. Y, en general, la elección del algoritmo y de las estructuras de datos que manipulará estarán muy relacionadas. Según su comportamiento durante la ejecución del programa distinguimos estructuras de datos: o o

Estáticas: su tamaño en memoria es fijo. Ejemplo: arrays. Dinámicas: su tamaño en memoria es variable. Ejemplo: listas enlazadas con punteros, ficheros, etc.

Las estructuras de datos que trataremos aquí son los arrays, las pilas y las colas, los árboles, y algunas variantes de estas estructuras.

3.1.3 TIPOS ABSTRACTOS DE DATOS

Lic. Carmen Mollinedo

24

Algoritmos Avanzados

Los tipos abstractos de datos (TAD) permiten describir una estructura de datos en función de las operaciones que pueden efectuar, dejando a un lado su implementación. Los TAD mezclan estructuras de datos junto a una serie de operaciones de manipulación. Incluyen una especificación, que es lo que verá el usuario, y una implementación (algoritmos de operaciones sobre las estructuras de datos y su representación en un lenguaje de programación), que el usuario no tiene necesariamente que conocer para manipular correctamente los tipos abstractos de datos. Se caracterizan por el encapsulamiento. Es como una caja negra que funciona simplemente conectándole unos cables. Esto permite aumentar la complejidad de los programas pero manteniendo una claridad suficiente que no desborde a los desarrolladores. Además, en caso de que algo falle será más fácil determinar si lo que falla es la caja negra o son los cables. Por último, indicar que un TAD puede definir a otro TAD. Por ejemplo, en próximos apartados se indicará como construir pilas, colas y árboles a partir de arrays y listas enlazadas. De hecho, las listas enlazadas también pueden construirse a partir de arrays y viceversa. 3.2 RECURSIVIDAD La recursión es una técnica para resolver problemas. Muchas veces resulta más fácil desarrollar un algoritmo recursivo que uno iterativo. Definición: Una función f es recursiva si en su cuerpo contiene una aplicación de f, es decir, si se puede activarse a si misma.

Si la llamada sucede dentro de la propia función se dice que es directamente recursiva. En cambio si la función llama a otra y esta a su vez llama a la primera se dice que es recursión indirecta. El objetivo del programa recursivo, es realizar una serie de llamadas hasta que la secuencia se define en un punto. Las directrices para una función recursiva son: Cada vez que se hace una llamada recursiva en una función, el programa deberá comprobar que se satisface una condición básica con un determinado parámetro puesto al valor mínimo. Cada vez que se hace la llamada a la función, los parámetros enviados a la misma, deberán ser de algún modo más “simple”, es decir, su valor debe tender a la condición básica. Además por lo general en las funciones recursivas se suelen identificar dos casos: Caso base, que implica el caso de parada de la recursión Caso base, que implica realizar las llamadas recursivas

Lic. Carmen Mollinedo

25

Algoritmos Avanzados

Ejemplo La función Factorial puede ser desarrollada iterativamente o recursivamente1.

Matemáticamente de define como: 1 n!=  n(n − 1)

si n = 0 ó 1 si n > 1

Análogamente su expresión funcional será la siguiente: si n = 0 ó 1 1 fac(n) =  n * fac (n − 1) si n > 1 Codificación Como función la codificación es la siguiente: Private Function factorial(ByVal n As Integer) As Integer If n = 1 Then factorial = 1 Else factorial = n * factorial(n - 1) End If End Function

Prueba Para N=5 Llamadas recursiva Factorial(5)=factorial(4)*5 Factorial(4)=factorial(3)*4 Factorial(3)=factorial(2)*3 Factorial(2)=factorial(1)*2 Factorial(1)=1

Lic. Carmen Mollinedo

Evaluación de resultados Factorial(1)=1 Factorial(2)=factorial(1)*2 = Factorial(3)=factorial(2)*3 = Factorial(4)=factorial(3)*4 = Factorial(5)=factorial(4)*5 =

1*2 =2 2*3 =6 6*4 =24 24*5 =120

26

Algoritmos Avanzados

Como procedimiento se tiene la siguiente codificación:

Private Sub fac(ByVal n As Integer, ByRef resul As Integer) Dim resp_aux As Integer If n = 1 OR n = 0 Then resul = 1 Else fac n - 1, resp_aux resul = resp_aux * n End If

Ejemplo: Otro ejemplo clásico es la secuencia de fibonacci cuyos términos son 1, 1, 2, 3, 5, 8, ... los cuales se determinan por la función:

Expresión funcional si n = 1 ó 2 1 fib(n) =   fib(n − 1) + fib(n − 2) si n > 2

Codificación Private Integer

Function

fibonacci(ByVal

n

As

Integer)

As

If n = 0 Or n = 1 Then fibonacci = 1 Else fibonacci = fibonacci(n - 1) + fibonacci(n 2) End If End Function

Lic. Carmen Mollinedo

27

Algoritmos Avanzados

Lic. Carmen Mollinedo

28

Algoritmos Avanzados

Prueba Para fib(5) se tienen las siguientes entradas y salidas.

Llamadas recursiva Fibonacci(5)=fibonacci(4)+ fibonacci(3) Fibonacci(4)=fibonacci(3)+ fibonacci(2) Fibonacci(3)=fibonacci(2)+ fibonacci(1) Fibonacci(2)=1 Fibonacci(1)=1

Evaluación de resultados Fibonacci(1)=1 Fibonacci(2)=1 Fibonacci(3)=fibonacci(2)+ fibonacci(1)=1+1=2 Fibonacci(4)=fibonacci(3)+ fibonacci(2)=2+1=3 Fibonacci(5)=fibonacci(4)+ fibonacci(3)=3+2=5

En este caso se puede observar que la solución planteada de fibonacci es impracticable para valores de n grandes. Cada fibonacci() realiza dos llamadas, por lo que el número de llamadas aumenta en proporción geométrica.

¿ Conviene usar recursión siempre?¿ Qué pasa con la memoria? Veamos el caso de implementar la misma secuencia de fibonacci iterativamente: Private Function fiboRec(ByVal n As Integer) As Integer Dim a As Integer, b As Integer, c As Integer, i As Integer a = 0 b = 1 c = 1 Print c For i = 2 To n c = a + b

Print c a = b b = c Next i fiboRec = c EL lector podrá verificar la eficiencia de la versión recursiva con respecto de la iterativa

Lic. Carmen Mollinedo

29

Algoritmos Avanzados

3.2.1 EJERCICIOS RESUELTOS Ejercicio 1 Multiplicar dos números por sumas sucesivas Solución Como es sabido, “la multiplicación es una suma abreviada”, en tal sentido se puede realizar la operación de la siguiente forma: A*B = A+A+A+ . . . . . . . . . +A , Es decir sumar A, B veces Entonces para el caso general: B −1

A * B = Multi( A, B) = ∑i =1 A = ∑i =1 A + A B

Es decir A*B se puede expresar como la sumatoria desde 1 hasta B de A, lo cual si se saca de la expresión al último termino, el resto continua siendo sumatoria. El caso base es mucho más simple, nos preguntamos cuál es el valor más qequeño que puede toma B, para que el resultado sea trivial, es posible elegir entre las siguientes alternativas

O

A*B=A cuando B=1 A*B=0 cuando B=0

Cualquiera de estas expresiones puede representar al caso base.

Expresión funcional si B = 1 A Multi( A, B) =  Multi( A, B − 1) + A

si B > 1

Algoritmo Private Function multiplica(ByVal A As Integer, ByVal B As Integer) As Integer If B = 1 Then multiplica = A Else multiplica = multiplica(A, B - 1) + A End If End Function

Lic. Carmen Mollinedo

30

Algoritmos Avanzados

Codificación completa

Option Explicit Dim num As Integer Dim num2 As Integer Private Function multiplica(ByVal A As Integer, ByVal B As Integer) As Integer If B = 1 Then multiplica = A Else multiplica = multiplica(A, B - 1) + A End If End Function Private Sub Command1_Click() num = Val(Text1.Text) num2 = Val(Text2.Text) MsgBox "El resulatdo es " & multiplica(num, num2), vbCritical, "RESULTADO" End Sub Private Sub Command2_Click() End End Sub Private Sub Text1_KeyPress(KeyAscii As Integer) Select Case KeyAscii Case 13 Text2.SetFocus Case Asc(0) To Asc(9) Case Else KeyAscii = 0 End Select End Sub

Lic. Carmen Mollinedo

31

Algoritmos Avanzados

Private Sub Text2_KeyPress(KeyAscii As Integer) Select Case KeyAscii Case 13 Command1.SetFocus Case Asc(0) To Asc(9) Case Else KeyAscii = 0 End Select

End Sub

Ejercicio 2 intercalar los dígitos de dos números, los números tiene la misma longitud. Solución La función modulo nos permite sacar el último digito de cada número y componer un nuevo numero, cuando numA y numB sean de un solo dígito, es decir menores a 10 se habrá llegado al caso base. Expresión funcional si A < 10 ó B < 10 A *10 + B Intercala( A, B) =   Intercala( Adiv10, Bdiv10) * 100 + ( A mod 10) * 10 + ( B mod 10) eoc Algoritmo Private Function intercala(ByVal numA As Integer, ByVal numB As Integer) As Double Dim ma As Integer, mb As Integer, nuevoNum As Integer If numA < 10 Then intercala = numA * 10 + numB Else ma = numA Mod 10 mb = numB Mod 10 nuevoNum = ma * 10 + mb intercala = intercala(numA \ 10, numB \ 10) * 100 + nuevoNum End If

Lic. Carmen Mollinedo

32

Algoritmos Avanzados

Prueba Intercala(345,796) = Intercala(34,79)*100 + 56 =3749*100 + 56 = 374956 Intercala(34,79) Intercala(3,7)

= Intercala(3,7)*100 + 49 = 37*100 +49 = 3749 = 37

Ejercicio 3 Hallar la sumatoria de los N primero números pares Solución La sumatoria de los n primero números pares está dada por: SumaPares(n) = 2 + 4 + 6 + . . . . . .+ 2*(n-1) + 2*n Sacando el ultimo elemento de la sumatoria, logramos identificar el caso general: SumaPares(n) = SumaPares(n-1)+ 2*n Para el caso general, se considera que valor debe tomar n para generar el primer numero par.

Algoritmo Private Function sumaPares(n As Integer) If n = 1 Then sumaPares = 2 Else sumaPares = sumaPares(n - 1) + 2 * n End If End Function

Codificación completa

Lic. Carmen Mollinedo

33

Algoritmos Avanzados

Option Explicit Dim num As Integer Private Function sumaPares(ByVal n As Integer) As Integer If n = 1 Then sumaPares = 2 List1.AddItem 2 Else sumaPares = sumaPares(n - 1) + 2 * n List1.AddItem (2 * n) End If End Function

Private Sub Form_Load() Option1.Value = False Option2.Value = True End Sub Private Sub Option1_Click() num = Val(Text1.Text) MsgBox sumaPares(num), vbExclamation End Sub Private Sub Option2_Click() Text1 = "" List1.Clear End Sub Private Sub Option3_Click() End End Sub

Lic. Carmen Mollinedo

34

Algoritmos Avanzados

Ejercicio 4 Dado un número entero generar otro número solo compuesto por los números naturales. Ejemplo: N=1 genera 1 N=2 genera 12 N=3 genera 123 Expresión funcional si n = 1 1 Genera(n) =  Genera(n − 1) *10 + n si n > 1

Algoritmo

Prueba

Private Function genera(ByVal n As Integer) As Double If n = 1 Then genera = 1 Else genera = genera(n - 1) * 10 + n End If End Function

Para n=5 Llamadas recursiva genera(5) = genera(4) * 10 + 5 genera(4) = genera(3) * 10 + 4 genera(3) = genera(2) * 10 + 3 genera(2) = genera(1) * 10 + 2 genera(1) = 1

Evaluación de resultados genera(1) = 1 genera(2) = genera(1) * 10 + 2 = 1*10+2 = 12 genera(3) = genera(2) * 10 + 3 = 12*10+3=123 genera(4) = genera(3) * 10 + 4 = 123*10+4=1234 genera(5) = genera(4) * 10 + 5 = 1234*10+5= .....................12345

Ejercicio 5 Invertir un vector Solución in

fi 1 2 3 4 5 6 7

Lic. Carmen Mollinedo

35

Algoritmos Avanzados

La solución consiste en cambiar el primer V(ini) y último V(fin) elementos usando un auxiliar: aux = v(ini) v(ini) = v(fin) v(fin) = aux luego realizar la llamada recursiva de manera de cambiar el segundo V(ini+1) con el penúltimo V(fin-1) elemento: Invierte ini + 1, fin - 1 el proceso se repite mientras ini sea menor o igual que fin. Algoritmo Private Sub Invierte(ByVal ini As Integer, ByVal fin As Integer) Dim aux As Integer If ini < fin Then aux = v(ini) v(ini) = v(fin) v(fin) = aux Invierte ini + 1, fin - 1 End If End Sub Codificación completa

Dim tam As Integer Dim v(1 To 10) As String Private Sub LlenaVector(ByVal n As Integer) Dim i As Integer List1.Clear For i = 1 To n v(i) = InputBox("Ingrese el elemento V[" & i & "] =>", "Ingreso de datos al Vector", 0) List1.AddItem v(i) Next End Sub Private MostrarLista2(ByVal n As Integer) Lic. CarmenSub Mollinedo 36 Dim i As Integer List2.Clear For i = 1 To n List2.AddItem v(i)

Algoritmos Avanzados

Private Sub Command2_Click() Invierte 1, tam MostrarLista2 tam End Sub Private Sub Command3_Click() End End Sub

3.3 ARREGLOS Supongamos que nos enfrentamos a un problema como este: “Una empresa que cuenta con 150 empleados, desea establecer una estadística sobre los salarios de sus empleados, y quiere saber cual es el salario promedio, y también cuantos de sus empleados gana entre $1250.00 y $2500.00”. Si tomamos la decisión de tratar este tipo de problemas con datos simples, pronto nos percataríamos del enorme desperdicio de tiempo, almacenamiento y velocidad. Es por eso que para situaciones de este tipo la mejor solución son los datos estructurados. Lic. Carmen Mollinedo

37

Algoritmos Avanzados

Un arreglo puede definirse como un grupo o una colección finita, homogénea y ordenada de elementos. Los arreglos pueden ser de los siguientes tipos: o De una dimensión. o De dos dimensiones. o De tres o más dimensiones

3.4 PILAS Una pila (stack) es una colección ordenada de elementos en la cual se pueden insertar nuevos elementos por un extremo y se pueden retirar otros por el mismo extremo; ese estremos se llama ``la parte superior'' de la pila. Si tenemos un par de elementos en la pila, uno de ellos debe estar en la parte superior de la pila, que se considera ``el más alto'' en la pila que el otro. En la figura 3.1 el elemento F es el más alto de todos los elementos que están en la pila. El elemento D es el más alto de los elementos A,B,C, pero es menor que los elementos E y F.

Figura 3.1: Pila con 6 elementos

Lic. Carmen Mollinedo

38

Algoritmos Avanzados

Para describir cómo funciona esta estructura, debemos agregar un nuevo elemento, el elemento G. Después de haber agregado el elemento G a la pila, la nueva configuración es la que se muestra en la figura 3.2

Figura 3.2: Operación de insertar el elemento G en la pila P De acuerdo con la definición, existe solamente un lugar en donde cualquier elemento puede ser agregado a la pila. Después de haber insertado el nuevo elemento, G ahora es el elemento en la cima. Debemos aclarar en qué pila deseamos insertar elementos, puesto que es posible tener más de una pila al mismo tiempo. Cuando se desea retirar un elemento de la pila, solo basta ordenar que sea retirado un elemento; no podemos decir ``retira C de la pila'', porque C no está en la cima de la pila y solamente podemos retirar el elemento que está en la cima. Para que la sentencia ``retira C de la pila'' tenga sentido, debemos replantear las órdenes a algo como: Retira de la pila hasta que el elemento retirado sea C. Y solamente se puede sacar un elemento a la vez. Siguiendo nuestro ejemplo, ahora deseamos retirar de la pila P. La configuración global de la pila es como se muestra en la figura 3.3

Figura 3.3: Operación de retirar de la pila P

Lic. Carmen Mollinedo

39

Algoritmos Avanzados

El concepto de pila es muy importante en computación y en especial en teoría de lenguajes de programación. En lenguajes procedurales como Pascal o C, la pila es una estructura indispensable, debido a las llamadas a función. Resulta que el flujo de instrucciones va de arriba hacia abajo, y cuando ocurre una llamada a alguna función, el estado global del sistema se almacena en un registro y éste en una pila. Así que la pila va a contener todas las llamadas a procedimientos que se hagan. Cuando se termina de ejecutar algún procedimiento, se recupera el registro que está en la cima de la pila. En ese registro están los valores de las variables como estaban antes de la llamada a la función, o algunas pueden haber cambiado si valor, dependiendo del ámbito de las variables. Cada elemento en la pila que es retirado, significa que se ha terminado de ejecutar alguna función. Cuando se termina de ejecutar el programa, la pila de llamadas a subprogramas debe haber quedado en 0 también, de otro modo podría causar algun tipo de error. La manera en cómo entran los datos a la estructura de datos y cómo salen, se denomina fifo, que viene del ingés first in first out (primero en entrar, primero en salir). 3.5 COLAS Las colas son una estructura de datos similar a las pilas. Recordemos que las pilas funcionan en un depósito en donde se insertan y se retiran elementos por el mismo extremo. En las colas sucede algo diferente, se insertan elementos por un extremo y se retiran elementos por el otro extremo. De hecho a este tipo de dispositivos se les conoce como dispositivos ``fifo'' (first in, first out) porque funcionan como una tubería, lo que entra primero por un extremo, sale primero por el otro extremo. En una cola hay dos extremos, uno es llamado la parte delantera y el otro extremo se llama la parte trasera de la cola. En una cola, los elementos se retiran por la parte delantera y se agregan por la parte trasera.

Figura 3.4: Dinámica de una cola. a) estado actual con una cola con tres elementos a,b,c; b) estado de la cola cuando se agrega el elemento d; c) estado de la cola cuando se elimina el elemento a del frente de la cola

Lic. Carmen Mollinedo

40

Algoritmos Avanzados

En la figura 3.4 se muestra una actividad típica de la cola, en donde se muestra que se agregan datos por la parte trasera de la cola y se eliminana datos por el frente de la cola. Si Q es una cola y x es un elemento, se pueden hacer tres operaciones básicas con las colas: o insert(Q,x), que inserta el elemento x en la parte trasera de la cola Q. o x=remove(Q), que almacena en x el valor del elemento retirado de la parte frontal de la cola Q. o empty(Q), que es un predicado de valor booleano, y es true cuando la cola Q tiene 0 elementos, y es false cuando la cola Q tiene al menos un elemento, en cuyo caso, ese único elemento es la parte frontal y la parte trasera de la cola al mismo tiempo. Teóricamente no hay límite para el tamaño de la cola, asi que siempre se debería poder insertar elementos a una cola, sin embargo, al igual que las pilas, normalmente se deja un espacio de memoria para trabajar con esta estructura. Por el contrario, la operación remove solamente se puede hacer si la cola no está vacía. 3.6 LISTAS Una lista es una estructura de datos secuencial.

Una manera de clasificarlas es por la forma de acceder al siguiente elemento: o lista densa: la propia estructura determina cuál es el siguiente elemento de la lista. Ejemplo: un array. o lista enlazada: la posición del siguiente elemento de la estructura la determina el elemento actual. Es necesario almacenar al menos la posición de memoria del primer elemento. Además es dinámica, es decir, su tamaño cambia durante la ejecución del programa. Una lista enlazada o encadenada es una colección de elementos ó nodos, en donde cada uno contiene datos y un enlace o liga.

Lic. Carmen Mollinedo

41

Algoritmos Avanzados

Un nodo es una secuencia de caracteres en memoria dividida en campos (de cualquier tipo). Un nodo siempre contiene la dirección de memoria del siguiente nodo de información si este existe. Un apuntador es la dirección de memoria de un nodo La figura siguiente muestra la estructura de un nodo:

El campo liga, que es de tipo puntero, es el que se usa para establecer la liga con el siguiente nodo de la lista. Si el nodo fuera el último, este campo recibe como valor NIL (vacío). A continuación se muestra el esquema de una lista :

3.7 ÁRBOLES 3.7.1 ÁRBOLES BINARIOS A los árboles ordenados de grado dos se les conoce como árboles binarios ya que cada nodo del árbol no tendrá más de dos descendientes directos. Las aplicaciones de los árboles binarios son muy variadas ya que se les puede utilizar para representar una estructura en la cual es posible tomar decisiones con dos opciones en distintos puntos. 3.7.1.1 Representación

La representación gráfica de un árbol binario es la siguiente:

Hay dos formas tradicionales de representar un árbol binario en memoria:

o Por medio de datos tipo punteros también conocidos como variables dinámicas o listas.

Lic. Carmen Mollinedo

42

Algoritmos Avanzados

o Por medio de arreglos. Sin embargo la más utilizada es la primera, puesto que es la más natural para tratar este tipo de estructuras. Los nodos del árbol binario serán representados como registros que contendrán como mínimo tres campos. En un campo se almacenará la información del nodo. Los dos restantes se utilizarán para apuntar al subarbol izquierdo y derecho del subarbol en cuestión. Cada nodo se representa gráficamente de la siguiente manera:

3.7.1.2 Clasificación de Árboles Binarios

Existen cuatro tipos de árbol binario:. a. b. c. d.

B. Distinto. B. Similares. B. Equivalentes. B. Completos.

A continuación se hará una breve descripción de los diferentes tipos de árbol binario así como un ejemplo de cada uno de ellos. a. A. B. DISTINTO Se dice que dos árboles binarios son distintos cuando sus estructuras son diferentes. Ejemplo:

b. A. B. SIMILARES Dos árboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus nodos es diferente. Ejemplo:

Lic. Carmen Mollinedo

43

Algoritmos Avanzados

c. A. B. EQUIVALENTES Son aquellos árboles que son similares y que además los nodos contienen la misma información. Ejemplo:

d. A. B. COMPLETOS Son aquellos árboles en los que todos sus nodos excepto los del ultimo nivel, tiene dos hijos; el subárbol izquierdo y el subárbol derecho. 3.7.1.3 Recorrido de un Arbol Binario Hay tres manera de recorrer un árbol : en inorden, preorden y postorden. Cada una de ellas tiene una secuencia distinta para analizar el árbol como se puede ver a continuación: INORDEN Recorrer el subarbol izquierdo en inorden. Examinar la raíz. Recorrer el subarbol derecho en inorden. PREORDEN Examinar la raíz. Recorrer el subarbol izquierdo en preorden. recorrer el subarbol derecho en preorden. POSTORDEN Recorrer el subarbol izquierdo en postorden. Recorrer el subarbol derecho en postorden. Examinar la raíz. A continuación se muestra un ejemplo de los diferentes recorridos en un árbol binario. Inorden: GDBHEIACJKF Preorden: ABDGEHICFJK Postorden: GDHIEBKJFCA

Lic. Carmen Mollinedo

44

Algoritmos Avanzados

3.7.1.4 Árboles Enhebrados Existe un tipo especial de árbol binario llamado enhebrado, el cual contiene hebras que pueden estar a la derecha o a la izquierda. El siguiente ejemplo es un árbol binario enhebrado a la derecha.

ARBOL ENHEBRADO A LA DERECHA. Este tipo de árbol tiene un apuntador a la derecha que apunta a un nodo antecesor. ARBOL ENHEBRADO A LA IZQUIERDA. Estos árboles tienen un apuntador a la izquierda que apunta al nodo antecesor en orden. 3 .7.1.5 Árboles binarios de búsqueda Un árbol de búsqueda binaria es una estructura apropiada para muchas de las aplicaciones que se han discutido anteriormente con listas. La ventaja especial de utilizar un árbol es que se facilita la búsqueda. Un árbol binario de búsqueda es aquel en el que el hijo de la izquierda (si existe) de cualquier nodo contiene un valor más pequeño que el nodo padre, y el hijo de la derecha (si existe) contiene un valor más grande que el nodo padre. Un ejemplo de árbol binario de búsqueda es el siguiente:

Lic. Carmen Mollinedo

45

Algoritmos Avanzados

3.7.2 ÁRBOLES GENERALES Los árboles representan las estructuras no lineales y dinámicas de datos más importantes en computación . Dinámicas porque las estructuras de árbol pueden cambiar durante la ejecución de un programa. No lineales, puesto que a cada elemento del árbol pueden seguirle varios elementos. Los árboles pueden ser construidos con estructuras estáticas y dinámicas. Las estáticas son arreglos, registros y conjuntos, mientras que las dinámicas están representadas por listas. La definición de árbol es la siguiente: es una estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos; uno de los cuales es conocido como raíz. además se crea una relación o parentesco entre los nodos dando lugar a términos como padre, hijo, hermano, antecesor, sucesor, ansestro, etc.. Formalmente se define un árbol de tipo T como una estructura homogénea que es la concatenación de un elemento de tipo T junto con un número finito de arboles disjuntos, llamados subarboles. Una forma particular de árbol puede ser la estructura vacía.

La figura siguiente representa a un árbol general.

Se utiliza la recursión para definir un árbol porque representa la forma más apropiada y porque además es una característica inherente de los mismos. Los árboles tienen una gran variedad de aplicaciones. Por ejemplo, se pueden utilizar para representar fórmulas matemáticas, para organizar adecuadamente la información, para construir un árbol genealógico, para el análisis de circuitos eléctricos y para numerar los capítulos y secciones de un libro. 3.7.2.1 Terminología La terminología que por lo regular se utiliza para el manejo de arboles es la siguiente:

Lic. Carmen Mollinedo

46

Algoritmos Avanzados

o HIJO. X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice que X es descendiente directo de Y. o PADRE. X es padre de Y sí y solo sí el nodo X apunta a Y. También se dice que X es antecesor de Y. o HERMANO. Dos nodos serán hermanos si son descendientes directos de un mismo nodo. o HOJA. Se le llama hoja o terminal a aquellos nodos que no tienen ramificaciones (hijos). o NODO INTERIOR. Es un nodo que no es raíz ni terminal. o GRADO. Es el número de descendientes directos de un determinado nodo. o GRADO DEL ARBOL Es el máximo grado de todos los nodos del árbol. o NIVEL. Es el número de arcos que deben ser recorridos para llegar a un determinado nodo. Por definición la raíz tiene nivel 1. o ALTURA. Es el máximo número de niveles de todos los nodos del árbol. o PESO. Es el número de nodos del árbol sin contar la raíz. o LONGITUD DE CAMINO. Es el número de arcos que deben ser recorridos para llegar desde la raíz al nodo X. Por definición la raíz tiene longitud de camino 1, y sus descendientes directos longitud de camino 2 y así sucesivamente. 3.7.2.2 Transformación de un Árbol Gral. en un Árbol Binario. En esta sección estableceremos los mecanismos necesarios para convertir un árbol general en un árbol binario. Para esto, debemos seguir los pasos que se describen a continuación: o Enlazar los hijos de cada nodo en forma horizontal (los hermanos). o Enlazar en forma vertical el nodo padre con el nodo hijo que se encuentra más a la izquierda. Además, debe eliminarse el vínculo de ese padre con el resto de sus hijos. o Rotar el diagrama resultante aproximadamente 45 grados hacia la izquierda, y así se obtendrá el árbol binario correspondiente 3.8 GRAFOS Un grafo dirigido G consiste en un conjunto de vértices V y un conjunto de arcos o aristas A. Los vertice se denominan también nodos o puntos. Un arco, es un par ordenado de vértices(V,W) donde V es el vértice inicial y W es el vértice terminal del arco. Un arco se expresa como: V-->W y se representa de la siguiente manera:

Los vértice de un grafo pueden usarse para representar objetos. Los arcos se utilizan para representar relaciones entre estos objetos. Las aplicaciones más importantes de los grafos son las siguientes:

Lic. Carmen Mollinedo

47

Algoritmos Avanzados

o Rutas entre ciudades. o Determinar tiempos máximos y mínimos en un proceso. o Flujo y control en un programa. 3.8.1 TERMINOLOGIA

o La terminología que manejaremos regularmente para el uso de grafos es la siguiente: o o o o o o o o o

o o

o o o o o

CAMINO.Es una secuencia de vértices V1, V2, V3, ... , Vn, tal que cada uno de estos V1->V2, V2->V3, V1->V3. LONGITUD DE CAMINO. Es el número de arcos en ese camino. CAMINO SIMPLE. Es cuando todos sus vértices, excepto tal vez el primero y el último son distintos. CICLO SIMPLE. Es un camino simple de longitud por lo menos de uno que empieza y termina en el mismo vértice. ARISTAS PARALELAS. Es cuando hay más de una arista con un vértice inicial y uno terminal dados. GRAFO CICLICO. Se dice que un grafo es cíclico cuando contiene por lo menos un ciclo. GRAFO ACICLICO. Se dice que un grafo es aciclíco cuando no contiene ciclos. GRAFO CONEXO. Un grafo G es conexo, si y solo si existe un camino simple en cualesquiera dos nodos de G. GRAFO COMPLETO ó FUERTEMENTE CONEXO.Un grafo dirigido G es completo si para cada par de nodos (V,W) existe un camino de V a W y de W a V (forzosamente tendrán que cumplirse ambas condiciones), es decir que cada nodo G es adyacente a todos los demás nodos de G. GRAFO UNILATERALMENTE CONEXO.Un grafo G es unilateralmente conexo si para cada par de nodos (V,W) de G hay un camino de V a W o un camino de W a V. GRAFO PESADO ó ETIQUETADO. Un grafo es pesado cuando sus aristas contienen datos (etiquetas). Una etiqueta puede ser un nombre, costo ó un valor de cualquier tipo de dato. También a este grafo se le denomina red de actividades, y el número asociado al arco se le denomina factor de peso. VERTICE ADYACENTE. Un nodo o vértice V es adyacente al nodo W si existe un arco de m a n. GRADO DE SALIDA.El grado de salida de un nodo V de un grafo G, es el número de arcos o aristas que empiezan en V. GRADO DE ENTRADA.El grado de entrada de un nodo V de un grafo G, es el número de aristas que terminan en V. NODO FUENTE.Se le llama así a los nodos que tienen grado de salida positivo y un grado de entrada nulo. NODO SUMIDERO.Se le llama sumidero al nodo que tiene grado de salida nulo y un grado de entrada positivo.

3.8.2

EJEMPLOS DE GRAFOS

081.- Grafo regular: Aquel con el mismo grado en todos los vértices. Si ese grado es k lo llamaremos k-regular. Por ejemplo, el primero de los siguientes grafos es 3-regular, el segundo es 2regular y el tercero no es regular

Lic. Carmen Mollinedo

48

Algoritmos Avanzados

2.- Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto Ejemplo.- de los dos grafos siguientes el primero es bipartito y el segundo no lo es

3.- Grafo completo: Aquel con una arista entre cada par de vértices. Un grafo completo con n vértices se denota Kn. A continuación pueden verse los dibujos de K3, K4, K5 y K6

Todo grafo completo es regular porque cada vértice tiene grado |V|-1 al estar conectado con todos los otros vértices. Un grafo regular no tiene por qué ser completo.

Lic. Carmen Mollinedo

49

Algoritmos Avanzados

4.- Un grafo bipartido regular se denota Km,n donde m, n es el grado de cada conjunto disjunto de vértices. A continuación ponemos los dibujos de K1,2, K3,3, y K2,5

Lic. Carmen Mollinedo

50

Algoritmos Avanzados

3.8.3 REPRESENTACION DE GRAFOS

Lic. Carmen Mollinedo

51

Algoritmos Avanzados

4 TECNICAS DE DISEÑO DE ALGORITMOS 4.1 DIVIDE Y VENCERÁS Consiste en descomponer el caso que hay que resolver en subcasos más pequeños, resolver independientemente los subcasos y por último combinar las soluciones de los subcasos para obtener la solución del caso original. 4.1.1 ALGORITMO GENERAL

Consideremos un problema arbitrario, y sea A un algoritmo sencillo capaz de resolver el problema. A debe ser eficiente para casos pequeños y lo denominamos subalgoritmo básico. El caso general de los algoritmos de divide y vencerás es como sigue: función DV(x) si x es suficientemente pequeño o sencillo entonces devolver A(x) descomponer x en casos más pequeños x1, x2, x3 , ... , xl para i ← 1 hasta l hacer yi ← DV(xi) recombinar los yi para obtener una solución y de x devolver y

El número de subejemplares l suele ser pequeño e independiente del caso particular que haya que resolverse.

Para aplicar la estrategia “divide y vencerás” es necesario que se cumplan tres condiciones: • • •

Tiene que ser posible descomponer el caso en subcasos y recomponer las soluciones parciales de forma eficiente. Los subcasos deben ser en lo posible aproximadamente del mismo tamaño. En la mayoría de los algoritmos de DV el tamaño de los l subcasos es aproximadamente m/b, para alguna constante b, en donde m es el tamaño del caso (o subcaso) original (cada subproblema es aproximadamente del tamaño 1/b del problema original).

4.1.2 COMPLEJIDAD

El análisis de tiempos de ejecución para estos algoritmos es el siguiente:

Lic. Carmen Mollinedo

50

Algoritmos Avanzados

Sea g(n) el tiempo requerido por DV en casos de tamaño n, sin contar el tiempo necesario para llamadas recursivas. El tiempo total t(n) requerido por este algoritmo de divide y vencerás es parecido a: t(n) = l t(n/b) + nk para 1 ≥ l y 2 ≥ b

siempre que n sea suficientemente grande. Si existe un entero k ≥ 0. Donde además: l: Número de llamadas recursivas b: En cuanto se divide el problema

4.1.3. EJEMPLOS

Ejemplo 1. BÚSQUEDA DEL MÁXIMO Y MÍNIMO

Estudiaremos el ejemplo del cálculo del máximo y mínimo de los elementos almacenados en un array. Este ejemplo es muy sencillo y sólo tiene interés para hacer un estudio detallado de los tiempos de ejecución. a) Método directo Un algoritmo para resolver el problema sin aplicar la técnica divide y vencerás puede ser: Cálculo del máximo y mínimo, método directo, compilado en Delphi 5 PROCEDURE MaxMin(a:TVector ;VAR max,min:integer); VAR i:INTEGER; BEGIN max := a[1]; min := a[1]; FOR i := 2 TO n DO BEGIN IF a[i] < min THEN min := a[i]; Lic. Carmen Mollinedo

51

Algoritmos Avanzados

IF a[i] > max THEN max := a[i]; END; END; Analizando el algoritmo, observamos que el número de comparaciones es TMaxMin(n) = T(for)*(T(if-then)+ T(if-then)) = (n-1)*(2+2) = 4n-4 Entonces es: O(n) de orden lineal

b) Aplicando Divide y Vencerás dividimos el vector en 2 hasta llegar a un solo elemento que se considera el caso base PROCEDURE maxminDV(v:TVector;i,j:INTEGER;VAR may,min:INTEGER); VAR med,amay,bmay,amin,bmin:INTEGER; BEGIN IF i=j THEN BEGIN may:=v[i]; min:=v[i]; END ELSE BEGIN med:=(i+j)DIV 2; maxminDV(V,i,med,amay,amin); maxminDV(V,med+1,j,bmay,bmin); IF amay>bmay THEN may:=amay ELSE may:=bmay; IF amin1 El problema se divide en dos 2 llamadas recursivas aplicando la fórmula general tenemos: l=2 b=2 k=0

donde 2>20

entonces

T(n) es Θ( n log 2 2 ) ≡ Θ( n)

Ejemplo 2. BÚSQUEDA BINARIA

Sea T[1..n] un arreglo ordenado por orden no decreciente, esto es, T[i] ≤ T[ j], siempre que 1 ≤ i ≤ j ≤ n. Sea x un elemento que no necesariamente se encuentra en T. El problema consiste en buscar en que posición se encuentra x en el arreglo T, si es que se encuentra. Formalmente, se desea encontrar el índice i tal que 1 ≤ i ≤ n+1 La aproximación evidente es examinar secuencialmente el arreglo hasta que se encuentre el elemento buscado o hasta llegar al final del arreglo, sin embargo el lector podrá observar que esta es la alternativa más costosa, puesto que en el peor de los casos. Indudablemente la Búsqueda Binaria es más beneficiosa. En la siguiente figura buscamos el número 25

Lic. Carmen Mollinedo

53

Algoritmos Avanzados

Ini

fin

medio x

1 5 5 6

8 8 6 6

4 6 6

25

A continuación se presenta el algoritmo codificado en Vbasic Function BusquedaBinaria(ByVal x As Integer) As Integer Dim Ini, Fin, Centro As Integer Ini = 1 Fin = Val(Text1) Centro = Int((Ini + Fin) / 2) Do While Ini Val(Text1) Then Exit Do Centro = Int((Ini + Fin) / 2) Loop ‘fin del do while If x = Vec(Centro) Then Busqueda=Centro Else Busqueda= -1 End If End Function La ejecución del algoritmo será de la siguiente forma:

Lic. Carmen Mollinedo

54

Algoritmos Avanzados

El algoritmo DV es el siguiente:

Private Function BusquedaBinariaDV(ByVal x As Integer, ini As Integer, _ fin As Integer) As Integer Dim Centro As Integer If ini = fin Then If x = V(ini) Then BusquedaBinariaDV = ini Else BusquedaBinariaDV = -1 End If Else Centro = Int((ini + fin) / 2) If V(Centro) = x Then BusquedaBinariaDV = Centro Else If V(Centro) < x Then BusquedaBinariaDV = BusquedaBinariaDV(x, Centro + 1, fin) Else BusquedaBinariaDV = BusquedaBinariaDV(x, ini, Centro - 1) End If End If End If End Function

Análisis

• • • •

¿Es diferente el comportamiento del algoritmo recursivo vs. el iterativo? NO en el contexto general del tiempo de ejecución… La complejidad de tiempo es diferente, pero por un valor constante Por lo tanto, el orden es el mismo: O(log n), veamos:

Lic. Carmen Mollinedo

55

Algoritmos Avanzados

T(n) = 3 cuando n=1, en el caso base

T(n) = 1T(n/2)+ d cuando n>1, d es ctte El problema se divide en dos 1 llamadas recursiva, puesto que se ejecuta solamente la llamada then o la llamada else aplicando la fórmula general tenemos: l=1 b=2 k=0

donde 1=20

entonces

T(n) es Θ( n 0 log n) ≡ Θ(log n)

Ejemplo 3 MATRIZ BOOLEANA

El problema consiste en generar una matriz de la siguiente forma:

Algoritmo void BooleDV(int m[][20], int ini, int fin, int col) {int medio,i; if(ini==fin-1) { m[ini][col]=0; m[fin][col]=1;} else {

Lic. Carmen Mollinedo

56

Algoritmos Avanzados

medio=(ini+fin)/2; for(i=ini;i