4. Estructuras de Datos 1
Arreglos y listas enlazadas
La memoria RAM
• una secuencia de caracteres (bytes) en donde
se encuentran las instrucciones y datos a los
que se accede directamente a través del
procesador del computador.
Dirección
Datos
Estructuras de datos
• Son sistemas o métodos de organización de datos
que permiten un almacenamiento eficiente de la
información en la memoria del computador
• Constituyen las piezas básicas para la construcción de
algoritmos complejos, y permiten implementarlos de
manera eficiente.
• Algunos Ejemplos: Arreglos, listas enlazadas,
árboles
Ejemplos
•
•
•
•
•
•
•
•
•
•
3n = O(n)
2 = O(1)
2 = O(n)
3n + 2 = O(n)
An2+ Bn + C = O(n2)
Alog n + Bn + C nlog n + Dn2 = ?
3 = Ω(1)
3n = Ω(n)
3n = Ω(1)
3n + 2 = Ω(n)
Θ (n)
Ecuaciones de Recurrencia
• Son ecuaciones en que el valor de la función para un n dado
se obtiene en función de valores anteriores.
• Esto permite calcular el valor de la función para cualquier n, a
partir de condiciones de borde (o condiciones iniciales)
• Ejemplo: Torres de Hanoi
an = 2an-1 + 1
a0 = 0
• Ejemplo: Fibonacci
fn = fn-1 + fn-2
f0 = 0
f1 = 1
Ecuaciones de Primer Orden
• Consideremos una ecuación de la forma
an = ban-1 + cn
• donde b es una constante y cn es una función conocida.
• Como precalentamiento, consideremos el caso b = 1:
an = an-1 + cn
• Esto se puede poner en la forma
an - an-1 = cn
• Sumando a ambos lados, queda una suma telescópica:
• an = a 0 +
Σ ck
1<=k<=n
Ecuaciones de Primer Orden: (cont.)
• Para resolver el caso general:
an = ban-1 + cn
• dividamos ambos lados por el “factor sumante” bn:
an/bn = an-1/bn-1 +cn/bn
• Si definimos An = an /bn, Cn = cn=bn, queda una ecuación que
ya sabemos resolver:
An = An-1 + Cn con solución
An = A0 + Σck
1<=k<=n
• y finalmente
an = a0bn + Σckbn-k
1<=k<=n
Ejemplo: Torres de Hanoi
• El número de movimientos de discos está dado por la
ecuación
an = 2an-1 + 1
a0 = 0
• De acuerdo a lo anterior, la solución es
an = Σ2n-k =
Σ2k
1<=k<=n
• Lo que significa
an = 2n-1
0<=k<=n-1
Propuesto
• Generalizar este método para resolver ecuaciones de la forma
an = bnan-1 + cn
• donde bn y cn son funciones conocidas.
Ecuaciones Lineales con coef. Const.
• Ejemplo: Fibonacci
fn = fn-1 + fn-2
f0 = 0
f1 = 1
• Este tipo de ecuaciones tienen soluciones exponenciales, de la
forma fn = λn:
fn = fn-1 + fn-2  λn = λn-1 + λn-2
• Dividiendo ambos lados por λn-2 obtenemos la ecuación
característica
λ2 - λ + 1 = 0
• cuyas raíces son Ф1= (1+ sqrt(5))/2 ≈ 1.618
Ф2= (1- sqrt(5))/2 ≈ 0.618
Ecuaciones Lineales con coef. Const.
• La solución general se obtiene como una combinación lineal de
estas soluciones:
fn = A Ф1n + B Ф2n
• La condición inicial f0 = 0 implica que B = -A, esto es,
fn = A(Ф1n - Ф2n)
• y la condición f1 = 1 implica que
A(Ф1 - Ф2) = A sqrt(5) = 1
• con lo cual obtenemos finalmente la fórmula de los números de
Fibonacci:
fn =(1 /sqrt(5)) (Ф1n - Ф2n)
• Nótese que Ф2n tiende a 0 cuando n tiende a infinito, de modo que
fn = Θ (n)
Teorema Maestro (div. para reinar)
• Consideremos la ecuación de la forma
T(n) = pT(n/q) + Kn
• Supongamos que n es una potencia de q, digamos n = q k
Entonces
T(q k ) = pT(q k -1 ) + Kq k
• Y si definimos a k = T(q k ) tenemos la ecuación:
a k = pa k -1 + Kq k
• La cual tiene solución
a k = a 0 p k + K Σqjpk-j (ver al principio)
1<=j<=n
Teorema Maestro (cont.)
• Como k = log q n, tenemos
T(n) = T(1)plog q n + Kplog q n Σ(q/p)j
1<=j<=log q n
• Y observamos que
plog q n = (qlog q p) log q n =(qlog q n) log q p =(n) log q p
• Por lo tanto:
T(n) = (n) log q p (T(1) + K Σ(q/p)j )
1<=j<=log q n
Teorema Maestro: caso p < q
T(n) = pT(n/q) + Kn
Teorema Maestro: caso p = q
T(n) = pT(n/q) + Kn
Teorema Maestro: caso p > q
T(n) = pT(n/q) + Kn
Dividir para Reinar
Este es un método de diseño de algoritmos que se basa
en subdividir el problema en sub-problemas, resolverlos
recursivamente, y luego combinar las soluciones de los
sub-problemas para construir la solución del problema
original.
Ejemplo: Multiplicación de Polinomios.
Supongamos que tenemos dos polinomios
con n coeficientes, o sea, de grado n-1:
A(x) = a0+a1*x+ ... +an-1*xn-1B(x) = b0+b1*x+ ... +bn-1*xn-1
representados por arreglos a[0], .., a[n-1] y b[0], ..,b[n-1].
Queremos calcular los coeficientes del polinomio C(x) tal
que C(x) = A(x)*B(x).
Solulción
Un algoritmo simple para calcular esto es:
// Multiplicación de polinomios
for( k=0; k<=2*n-2; ++k )
c[k] = 0;
for( i=0; i<n; ++i)
for( j=0; j<n; ++j)
c[i+j] += a[i]*b[j];
Evidentemente, este algoritmo requiere tiempo O(n2).
¿Se puede hacer más rápido?
Dividir-componer
Supongamos que n es par, y dividamos los polinomios en
dos partes. Por ejemplo, si A(x) = 2 + 3*x - 6*x2 + x3
entonces se puede reescribir como
A(x) = (2+3*x) + (-6+x)*x2
y en general
A(x) = A'(x) + A"(x) * xn/2
B(x) = B'(x) + B"(x) * xn/2
Entonces
C = (A' + A"*xn/2) * (B' + B"*xn/2) =
A'*B' + (A'*B" + A"*B') * xn/2 + A"*B" * xn
Dividir-componer (cont.)
C = (A' + A"*xn/2) * (B' + B"*xn/2) =
A'*B' + (A'*B" + A"*B') * xn/2 + A"*B" * xn
Esto se puede implementar con 4 multiplicaciones
recursivas, cada una involucrando polinomios de la mitad
del tamaño que el polinomio original.
T(n) = 4*T(n/2) + K*n
donde K es alguna constante cuyo valor exacto no es
importante. Por lo tanto la solución del problema
planteado (p=4, q=2) es
T(n) = O(nlog2 4) = O(n2) lo cual no mejora al algoritmo
visto inicialmente.
Dividir-componer (cont.)
Pero...
hay una forma más eficiente de calcular C(x). Si
renombramos :
D = (A'+A") * (B'+B")
E = A'*B‘
F = A"*B" entonces
C = E + (D-E-F)*xn/2 + F*xn Lo cual utiliza sólo 3
multiplicaciones recursivas, en lugar de 4.
Esto implica que
T(n) = O(nlog2 3) = O(n1.59)
Descargar

1. Desarrollo de Programas iterativos usando invariante