Algoritmos computacionales

Indice
1.
Introducción
2. Marco Historico
3. Generalidades
4. Análisis De
Algoritmos
5. Técnica de diseño de
algoritmos
6. Algoritmos de
búsqueda y ordenación
7. Verificación y
derivación de programas
8. Análisis
Foda
9.
Conclusión
10.
Bibliografía

1.
Introducción

En el siguiente trabajo pretendemos presentar una serie
de concepto y
definiciones propios del estudio de los Algoritmos, su
análisis y diseño.
En el mismo podremos encontrar los conceptos de algoritmo y
algunos de sus componentes, análisis y diseño.
También veremos los diferentes tipos de formas y
tamaños o medidas en que se pueden almacenar y representar
los datos y estructuras en
un algoritmo o
programa. En
ese mismo orden encontraremos las diferentes técnicas
para diseñarlos como son el método de
la fuerza bruta,
el voraz, divide y vencerás, programación dinámica, de vuelta atrás, entre
otros.
De igual forma podremos ver las definiciones y algunas características, reglas, normas, tipos de
algoritmos de
búsqueda y ordenación así como sus
aplicaciones.
Finalmente veremos los que es la verificación y
derivación de programas, donde
daremos los conceptos básicos de semántica y sus
tipos haciendo mayor énfasis en la semántica
axiomática, la recursividad e iteración, los
diseños de estos últimos, así como los
típicos ciclos utilizados en algoritmos y programas y los
paso a tener en cuenta al momento de desarrollar un algoritmo
iterativo o recursivo.

Justificacion
Es importante el estudio y conocimiento
de lo que hoy conocemos como Algoritmos Computacionales, que
desde su aparición hasta nuestros días es, y
seguirá siendo; vital para el desarrollo de
aplicaciones para computadoras y
el manejo y dominio de la
lógica
de programación para resolver problemas.

Motivación
Como estudiantes de la Facultad de Ciencias y
Tecnología
" Escuela de
Informática y Computación " de la Universidad
Dominicana Organización y
Métodos O&M con aspiraciones de iniciarnos como
Ingeniero en Sistemas y
Computación. Con el objetivo
inmediato de aprobar con los mejores meritos la asignatura de
Algoritmos Computacionales.

Objetivos
General :
Posibilitar la estudiante alcanzar una visión
sistemática de lo que conocemos sobre Los Algoritmos
Computacionales.
Específicos :
Introducir los conceptos propios sobre Algoritmo, su importancia
en el mundo de las aplicaciones para computadoras y
el manejo de lógica
de programación.

• Proporcionar una idea de su uso.
• Visualizar sus ventajas e importancia.
• Definir sus tipos y variantes.
• Proporcionar conceptos sobre su análisis y
  diseño.
• Proporcionar concepto sobre
  las técnicas
  de diseño.
• Desglosar sus variantes (ordenación,
  búsqueda, etc. ).

2. Marco
Historico

Un algoritmo es un conjunto de operaciones y
procedimientos
que deben seguirse para resolver un problema. La palabra
algoritmo se deriva del nombre latinizado del gran
Matemático Árabe Mohamed Ibn Al Kow Rizmi, el cual
escribió sobre los años 800 y 825 su obra Quitad Al
Mugabala, donde se recogía el sistema de
numeración hindú y el concepto del cero. Fue
Fibinacci, el que tradujo la obra al latín y el inicio con
la palabra: Algoritmi Dicit.
El lenguaje
algorítmico es aquel por medio al cual se realiza un
análisis previo del problema a resolver y encontrar un
método que
permita resolverlo. El conjunto de todas las operaciones a
realizar y e orden en que se deben efectuarse, se le denomina
algoritmo.
Es un método para resolver un problema mediante una serie
de datos precisos,
definidos y finitos.

3.
Generalidades

El programador de computadoras es ante que nada una
persona que
resuelve problemas, por
lo que para llegar a ser un programador eficaz se necesita
aprender a resolver problemas de un modo riguroso y
sistemático. A la metodología necesaria para resolver
problemas mediante programas se denomina Metodología de la Programación. El
eje central de esta metodología es el concepto, ya
tratado, de algoritmo.
Un algoritmo es un método para resolver un problema.
Aunque la popularización del término ha llegado con
el advenimiento de la era informática, algoritmo proviene de Mohammed
al-Khowarizmi, matemático persa que vivió durante
el siglo IX y alcanzo gran reputación por el enunciado de
las reglas para sumar, restar, multiplicar y dividir
números decimales; la traducción al latín
del apellido de la palabra algorismus derivo posteriormente en
algoritmo. Euclides, el gran matemático griego (del siglo
IV antes de Cristo) que invento un método para encontrar
el máximo común divisor de dos números, se
considera con Al-Khowarizmi el otro gran padre de la algoritmia
(ciencia que
trata de los algoritmos).
El profesor Niklaus Wirth, inventor de Pascal, Modula-2
y Oberon, titulo uno de sus mas famosos libros,
Algoritmos + Estructuras de
Datos = Programas, significándonos que solo se puede
llegar a realizar un buen programa con el
diseño de un algoritmo y una correcta estructura de
datos. Esta ecuación será de una de las
hipótesis fundamentales consideradas en
esta obra.
La resolución de un problema exige el diseño de un
algoritmo que resuelva el problema propuesto.
Los pasos para la resolución de un problema
son:

1. Diseño de algoritmo, que describe la secuencia
   ordenada de pasos que conducen a la solución de un
   problema dado. (Análisis del problema y desarrollo
   del algoritmo).
2. Expresar el algoritmo como un programa de lenguaje de
   programación adecuado. (Fase de
   codificación.)
3. Ejecución y validación del programa por
   la
   computadora.

Para llegar a la realización de un programa es
necesario el diseño previo de algoritmo, de modo que sin
algoritmo no puede existir un programa.
Los algoritmos son independientes tanto del lenguaje de
programación en que se expresan como de la computadora
que lo ejecuta. En cada problema el algoritmo se puede expresar
en un lenguaje
diferente de programación y ejecutarse en una computadora
distinta; sin embargo, el algoritmo será siempre el mismo.
Así, por ejemplo, en una analogía con la vida
diaria, una receta de un plato de cocina se puede expresar en
español,
ingles o francés, pero cualquiera que sea el lenguaje,
los pasos para la elaboración del plato se realizaran sin
importar el idioma del cocinero.
En la ciencia de
la computación y en la programación, los algoritmos
son más importantes que los lenguajes de
programación o las computadoras. Un lenguaje de
programación es tan solo un medio para expresar un
algoritmo y una computadora es solo un procesador para
ejecutarlo. Tanto el lenguaje de programación como
la computadora
son los medios para
obtener un fin: conseguir que el algoritmo se ejecute y se
efectúe el proceso
correspondiente.
Dada la importancia del algoritmo en la ciencia de
la computación, un aspecto muy importante será el
diseño de algoritmos. El diseño de la
mayoría de los algoritmos requiere creatividad y
conocimientos profundos de la técnica de la
programación. En esencia, la solución de un
problema se puede expresar mediante un algoritmo.

Características de los Algoritmos:
Las características fundamentales que debe
cumplir todo algoritmo son:

• Un algoritmo debe ser preciso e indicar el orden de
  realización de cada paso.
• Un algoritmo debe estar definido. Si se sigue un
  algoritmo dos veces, se debe obtener el mismo resultado cada
  vez.
• Un algoritmo debe ser finito. Si se sigue un
  algoritmo se debe terminar en algún momento; o sea, debe
  tener un numero finito de pasos.

La definición de un algoritmo debe definir tres
partes: Entrada, Proceso y
Salida. En el algoritmo de receta de cocina citado anteriormente
se tendrá:
Entrada: ingrediente y utensilios empleados.
Proceso: elaboración de la receta en la cocina.
Salida: terminación del plato (por ejemplo,
cordero).

Ejemplo de Algoritmo:
Un cliente ejecuta
un pedido a una fábrica. Esta examina en su banco de datos la
ficha del cliente; si el
cliente es solvente entonces la empresa acepta
el pedido; en caso contrario rechazara el pedido. Redactar el
algoritmo correspondiente.
Los pasos del algoritmo son:

1. inicio
2. leer el pedido
3. examinar la ficha del cliente
4. si el cliente es solvente aceptar pedido; en caso
   contrario, rechazar pedido
5. fin

Diseño del Algoritmo:
En la etapa de análisis del proceso de programación
se determina que hace el programa. En la etapa de diseño
se determina como hace el programa la tarea solicitada. Los
métodos
mas eficaces para el proceso de diseño se basan en el
conocido por Divide y Vencerás, es decir, la
resolución de un problema complejo se realiza dividiendo
el problema en sub problemas y a continuación dividir
estos sub problemas en otros de nivel mas bajo, hasta que pueda
ser implementada una solución en la computadora. Este
método se conoce técnicamente como diseño
descendente (Top Down) o modular. El proceso de romper el
problema en cada etapa y expresar cada paso en forma más
detallada se denomina refinamiento sucesivo.
Cada sub programa es resuelto mediante un modulo (sub programa)
que tiene un solo punto de entrada y un solo punto de salida.
Cualquier programa bien diseñado consta de un programa
principal (el modulo de nivel mas alto) que llama a sub programas
(módulos de nivel mas bajo) que a su vez pueden llamar a
otros sub programas. Los programas estructurados de esta forma se
dice que tienen un diseño modular y el método de
romper el programa en módulos más pequeño se
llama Programación Modular. Los módulos pueden ser
planeados, codificados, comprobados y depurados
independientemente (incluso por diferentes programadores) y a
continuación combinarlos entre si. El proceso implica la
ejecución de los siguientes pasos hasta que el programa se
termina:

• programar modulo.
• Comprobar el modulo.
• Si es necesario, depurar el modulo.
• Combinar el modulo con los módulos
  anteriores.

El proceso que convierte los resultados del
análisis del problema en un diseño modular con
refinamiento sucesivo que permitan una posterior
traducción al lenguaje se denomina diseño de
algoritmo.
El diseño del algoritmo es independiente del lenguaje de
programación en el que se vaya a codificar
posteriormente.

4. Análisis De
Algoritmos

Recursos De Computadores Y Complejidad
Algoritmo: Conjunto de reglas para resolver un problema. Su
ejecución requiere unos recursos.
Un algoritmo es mejor cuantos menos recursos consuma,
su facilidad de programarlo, corto, fácil de entender,
robusto, etc.
Criterio empresarial: Maximizar la eficiencia.
Eficiencia:
Relación entre los recursos consumidos y los productos
conseguidos.
Recursos consumidos:
Tiempo de
ejecución.
Memoria
principal:
Entradas/salidas a disco.
Comunicaciones, procesadores,
etc.
Lo que se consigue:
Resolver un problema de forma exacta, forma aproximada o algunos
casos.
Recursos consumidos:
Ejemplo. ¿Cuántos recursos de tiempo y memoria consume
el siguiente algoritmo sencillo?
i:= 0
a[n+1]:= x
repetir
i:= i + 1
hasta a[i] = x
Respuesta: Depende.

¿De qué depende? De lo que valga n
y x, de lo que haya en a, de los tipos de datos,
de la máquina…
En general los recursos dependen de:
Factores externos.
El ordenador donde lo ejecutemos:
286, Pentium III,
Cray,…
El lenguaje de programación y el compilador usado.
La implementación que haga el programador del algoritmo.
En particular, de las estructuras de datos utilizadas.
Tamaño de los datos de entrada.
Ejemplo. Calcular la media de una matriz de
NxM.

Contenido de los datos de entrada.
Mejor caso. El contenido favorece una rápida
ejecución.
Peor caso. La ejecución más lenta posible.
Caso promedio. Media de todos los posibles contenidos.
Los factores externos no aportan información sobre el algoritmo.
Conclusión: Estudiar la variación del tiempo y
la memoria
necesitada por un algoritmo respecto al tamaño de la
entrada y a los posibles casos, de forma aproximada (y
parametrizada).
externos no aportan información sobre el algoritmo.
Normalmente usaremos la notación T(N)=…, pero
¿qué significa T(N)?
Tiempo de ejecución en segundos. T(N) = bN + c.
Suponiendo que b y c son constantes, con los segundos que tardan
las operaciones básicas correspondientes.
Instrucciones ejecutadas por el algoritmo. T(N) = 2N + 4.
¿Tardarán todas lo mismo?
Ejecuciones del bucle principal. T(N) = N+1.
¿Cuánto tiempo, cuántas
instrucciones,…?
Sabemos que cada ejecución lleva un tiempo constante,
luego se diferencia en una constante con los anteriores.
Asignación de tiempos, para el conteo de instrucciones.
Algunas reglas básicas.
Operaciones básicas (+, -, *, :=,…): Una unidad de
tiempo, o alguna constante.
Operaciones de entrada salida: Otra unidad de tiempo, o una
constante diferente.
Bucles FOR: Se pueden expresar como una sumatoria, con los
límites
del FOR.
IF y CASE: Estudiar lo que puede ocurrir. Mejor caso y peor caso
según la condición. ¿Se puede predecir
cuándo se cumplirán las condiciones?
Llamadas a procedimientos:
Calcular primero los procedimientos que no llaman a otros.
Bucles WHILE y REPEAT: Estudiar lo que puede ocurrir.
¿Existe una cota inferior y superior del número de
ejecuciones? ¿Se puede convertir en un FOR?
El análisis de algoritmos también puede ser a
posteriori: implementar el algoritmo y contar lo que tarda para
distintas entradas.
Ejemplo. Programa "cifras.exe":
N= 4, T(4)= 0.1 ms
N= 5, T(5)= 5 ms
N= 6, T(6)= 0.2 s
N= 7, T(7)= 10 s
N= 8, T(8)= 3.5 min

¿Qué conclusiones podemos extraer?
Análisis a priori: Evitamos la implementación, si
el algoritmo es poco eficiente. Podemos hacer previsiones.
Podemos comparar con otros algoritmos.
Medidas Asintoticas
Notación asintótica:
El tiempo de ejecución T(n) está dado en base a
unas constantes que dependen de factores externos.
Nos interesa un análisis que sea independiente de esos
factores.
Notaciones asintóticas: Indican como crece T, para
valores
suficientemente grandes (asintóticamente) sin
considerar
constantes.
O(T): Orden de complejidad de T.
W
(T): Orden inferior de T, u omega de
T.
Q (T): Orden exacto de T.
Orden de complejidad de f(n): O(f)
Dada una función f:
N ® R+, llamamos orden de f al
conjunto de todas las funciones de N en
R+ acotadas superiormente por un múltiplo real positivo de
f, para valores de
n suficientemente grandes.
O(f)= { t: N ® R+ /
$ c Î
R+, $ n0
Î N, "
n ³ n0: t(n)
£ c·f(n) }
Nota:
O(f) es un conjunto de funciones, no una
función.
"Valores de n sufic. Grandes…": no nos importa lo que pase para
valores pequeños.
"Funciones acotadas superiormente por un múltiplo de
f…": nos quitamos las constantes.
La definición es aplicable a cualquier función de N
en R, no sólo tiempos de ejec.

Propiedades
P1. Si f Î O(g) y g
Î O(h) entonces f
Î O(h).
Si f Î W (g) y
g Î W (h) entonces
f Î W (h)
Ej. 2n+1 Î O(n), n
Î O(n2) Þ
2n+1 Î O(n2)
P2. Si f Î O(g) entonces
O(f) Í O(g).

¿Cómo es la relación para
los W ?
P3. Dadas f y g de N en R+, se cumple:
i) O(f) = O(g) Û f
Î O(g) y g Î
O(f)
ii) O(f) Í O(g)
Û f Î
O(g)

¿La relación de orden entre O(..) es
completa? Dadas f y g, ¿se cumple
O(f)Í O(g) ó
O(g)Í O(f)?
P4. Dadas f y g, de N en R+, O(f+g) = O(max(f,
g)).
W (f+g) = W
(max(f+g))

¿Y para los Q
(f+g)?
¿Es cierto que O(f – g) = O(max(f, -g))?
P5. Dadas f y g de N en R+, se cumple:
i) limn¥ ®
f(n) Î R+
Þ O(f)=O(g), W
(f)=W (g), Q
(f)=Q (g)
g(n)
ii) limn¥ ® f(n) =
0 Þ O(f)
Í O(g), W
(g) Í W
(f)
g(n)
P5. Ej. ¿Qué relación hay entre O(log2 n) y
O(log10 n)?
P6. Dadas f y g de N en R+, O(f)=O(g) Û
Q (f)=Q (g)
Û f Î
Q (g) Û
W (f)=W (g)
P7. Dadas f y g de N en R+, se cumple:
i) limn¥ ®
f(n) Î R+
Þ O(f) = O(g)
g(n)
ii) limn¥ ® f(n) =
0 Þ O(f)
Ì O(g)
g(n)
iii) limn¥ ® f(n)
= +¥ Þ
O(f) É O(g)
g(n)

Notación con varios parámetros:
En general, el tiempo y la memoria
consumidos pueden depender de muchos parámetros.
f: Nm ® R+ (f: Nx…m..xN
® R+)
Ej. Memoria en una tabla hash. M(B,n, l, k) = kB+l+n+2kn
Orden de complejidad de f(n1, n2, …, nm): O(f)
Dada una función f: Nm ® R+,
llamamos orden de f al conjunto de todas las funciones de Nm en
R+ acotadas superiormente por un múltiplo real positivo de
f, para valores de (n1, …, nm) suficientemente grandes.
O(f)= { t: Nm ® R+ /
$ c Î
R+, $ n1, n2, .., nm
Î N, "
k1 ³ n1 ,
k2 ³ n2 ,..,"
km ³ nm : t(k1, k2, …,
km) £ c·f(k1, k2, …, km)
}

De la misma forma, podemos extender los conceptos
de W (f) y Q
(f), para funciones con varios parámetros.
Las propiedades se siguen cumpliendo ®
Demostrarlo.
Ejemplo. T(N) = T(N, a, b) = a·N + b
El tiempo depende del tamaño del problema N, y del tiempo
de inicialización b y de ejecución de un paso
a.
Podemos suponerlos constantes T(N), o variables
T(N,a,b).
¿Qué relación hay entre los siguientes
órdenes?
O(n+m), O(nm) O(n2), O(n+2m)

Notaciones condicionales:
En algunos casos interesa estudiar el tiempo sólo para
ciertos tamaños de entrada.
Ejemplo. Algoritmo de búsqueda binaria: Si N es potencia de 2 el
estudio se simplifica.

Orden condicionado de f(n): O(f | P)
Dada una función f: N ® R+,
y P: N ® B, llamamos orden de f
según P (o condicionado a P) al conjunto:
O(f | P)= { t: N ® R+ /
$ c Î
R+, $ n0
Î N, "
n ³ n0:
P(n) Þ t(n)
£ c·f(n) }
De igual forma, tenemos W (f | P)
y Q (f | P).
O(f) = O(f | true). Para cualquier f y g, f
Î O(g | false).
¿O(f) « O(f |
P)?

Ordenes De Complejidad
Uso de los órdenes de complejidad:
Dado un tiempo t(n), encontrar la función f más
simple tal que t Î O(f), y que
más se aproxime asintóticamente.
Ejemplo. t(n) = 2n2/5 + 3p /2;
t(n) Î O(n2).
•Relación de orden entre O(..) = Relación de
inclusión entre conjuntos.
–O(f) £ O(g)
Û O(f) Í
O(g) Û Para toda t
Î O(f), t Î
O(g)
•Se cumple que:
O(c) = O(d), siendo c y d constantes positivas.
O(c) Ì O(n)
O(cn + b) = O(dn + e)
O(p) = O(q), si p y q son polinomios del mismo grado.
O(p) Ì O(q), si p es un
polinomio de menor grado que q.

Orden inferior u omega de f(n): W
(f):
Dada una función f: N ® R+,
llamamos omega de f al conjunto de todas las funciones de N en R+
acotadas inferiormente por un múltiplo real positivo de f,
para valores de n suficientemente
grandes.
W (f)= { t: N
® R+ / $
c Î R+,
$ n0 Î
N, " n ³
n0: t(n) ³ c·f(n)
}
La notación omega se usa para establecer cotas inferiores
del tiempo de ejecución.
Relación de orden: igual que antes.
Orden exacto de f(n): Q (f):
Dada una función f: N ® R+,
llamamos orden exacto de f al conjunto de todas las funciones de
N en R+ que crecen igual que f, asintóticamente y salvo
constantes.
Q (f) = O(f)
Ç W (f)
= { t: N ® R+ /
$ c, d Î
R+, $ n0
Î N, "
n ³ n0:
c·f(n) ³ t(n)
³ d·f(n) }

Notación o pequeña de f(n): o(f):
Dada una función f: N ® R+,
llamamos o pequeña de f al conjunto de todas las funciones
de N en R+ que crecen igual que f asintóticamente:
o(f)= { t: N ® R+ / lim t(n)/f(n) =
1}n¥ ®

Esta notación conserva las constantes
multiplicativas para el término de mayor orden.
Ejemplo. t(n) = amnm + am-1nm-1 + … +a1n + a0
t(n) Î o(amnm)
¹ o(nm)
¿o(amnm) Í O(amnm)?
¿o(t) Í O(t)?

Costa de complejidad con frecuencia
Algunas relaciones entre órdenes frecuentes:
O(1) Ì O(log n)
Ì O(n) Ì
O(n·log n) Ì
O(n·(log n)2) Ì
O(n1.001…) Ì
O(n2) Ì O(n3)
Ì … Ì
O(2n) Ì O(n!)
Ì O(nn)

¿Qué pasa con las omegas? ¿Y con
los órdenes exactos?
El orden de un polinomio anxn+…+a1x+a0 es O(xn).
n n n
å 1 = n
Î O(n); å
i = n(n+1)/2 Î O(n2);
å im Î
O(nm+1)
i=1 i=1 i=1

Si hacemos una operación para n, otra para n/2,
n/4, …, aparecerá un orden logarítmico O(log2 n).
Los logaritmos son del mismo orden,
independientemente de la base.

5. Técnica de diseño de
algoritmos

Diseño de Algoritmos:
Hasta ahora se han realizado algunos comentarios respecto a la
necesidad de diseñar algoritmos correctos y eficientes
utilizando los elementos de un lenguaje de programación
.Es necesario en este momento mencionar algo sobre como hacerlo.
El acto de diseñar un algoritmo puede considerarse como
una tarea que difícilmente podrá ser del todo
automatizada.
Todo problema algorítmico es un reto para su
diseñador, algunos resultan inmediatos de resolver, otros
son bastante complejos. La investigación en esta área ha
permitido descubrir un conjunto de métodos o
esquemas de diseño hacia los cuales puede orientarse la
realización de muchos algoritmos.
No obstante, y a pesar de que resulta mas adecuado en bastantes
casos utilizar alguno de estos esquemas que realizar un
diseño desde cero, idear un algoritmo continua siendo una
labor bastante creativa donde los conocimientos y la experiencia
del propio diseñador tiene un papel
fundamental.
El diseño de un algoritmo que resuelva un problema es, en
general, una tarea difícil. Una forma de facilitar esta
labor consiste en recurrir a técnicas conocidas de
diseño de algoritmos, se decir, a esquemas muy generales
que pueden adaptarse a un problema particular al detallar las
partes generales del esquema.
Muchos problemas pueden resolverse buscando una solución
fácil y directa pero, a la vez bastante ineficiente. Este
método, llamado de fuerza bruta,
puede ser muy directo, pero con un poco de análisis puede
encontrarse algoritmos más eficientes. El esquema mas
sencillo quizás sea el llamado divide y vencerás,
basado en la descomposición de un problema en
subproblemas. Otros esquemas requieren un análisis
minucioso del problema de forma que la solución se vaya
construyendo en etapas. Si puede preverse que decisión
conviene en cada etapa para producir cierto tipo de mejor
resultado, tenemos una solución voraz, si la
decisión en una etapa, solo puede tomarse tras considerar
varias soluciones de
otras etapas mas simples, la solución es dinámica. Aun así, hay problemas
cuya solución no puede hallarse sino mediante un proceso
de búsqueda, a pesar de lo complejas que son las
operaciones de búsqueda, su uso adecuado mediante el
esquema de búsqueda con retroceso (o backtracking) permite
ganar gran eficiencia respecto a soluciones de
fuerza bruta. Por ultimo, conviene conocer otros métodos
de diseño de algoritmos que también resultan de
utilidad
práctica.
Nos estamos refiriendo a métodos basados en la mejora de
la eficiencia (por ejemplo, el uso de parámetros de
acumulación al resolver problemas utilizando divide y
vencerás, y el empleo de
tablas como estructura
auxiliar para la resolución eficiente de problemas donde
se aplica programación dinámica), y a
métodos basados en transformaciones del dominio para
encontrar una solución mas fácilmente a un problema
en un dominio transformado, siendo dicha solución
finalmente adaptada al dominio original.

Consideraciones generales
Si el hábil programador dispone de un recetario de
algoritmos de donde poder
seleccionar el más adecuado para cada problema, su tarea
se simplifica.
Supongamos que disponemos de una especificación precisa,
completa y consistente del problema a resolver y queremos obtener
un algoritmo en el que, dados uno datos de entrada valido, se
produzca cierto resultado. Si no nos importa la eficiencia del
algoritmo, podríamos utilizar un algoritmo general llamado
algoritmo del museo británico. Se programa un computador de
manera que parta de un conjunto de axioma matemáticos y
los que use para reducir aleatoriamente teoremas validos.
Aprender los principios
básicos del diseño de algoritmos podemos
preguntarnos por un método aceptable. El mas entendido, y
quizás el mejor, es organizar el diseño sobre un
esquema de algoritmo o una técnica de diseño que
haya demostrado su utilidad para
otros problemas. Este método de trabajo es practicable,
puesto que existe un número reducido de esquema y
técnicas de diseño.
El
conocimiento de técnicas de diseño es solo un
primer paso para el diseñador, que debe completarse con
otros
conocimientos y, sobre todo, con la experiencia.
Método de fuerza bruta
Comenzamos el estudio de esquemas algorítmicos con un
método sencillo, pero que debe evitarse siempre que se
pueda, dad su ineficacia; la fuerza bruta. En realidad, no es un
esquema algorítmico, si no mas bien calificativo
Para una forma de diseñar algoritmos: tomar una
solución directa, poco reflexionada. En principio, esto no
es malo, pero dado que no se ha analizado apenas el problema, es
muy probable que no se hayan aprovechado propiedades deducibles
del problema y que la solución sea terriblemente
ineficiente.
Una solución por fuerza bruta también puede
resultar adecuada como primera aproximación a la
solución final, porque su desarrollo puede permitir
profundizar más sobre el problema y conocer propiedades
que sean utilizadas para obtener otra versión más
eficiente.
Por ejemplos:
Algunos algoritmos de búsqueda de un elemento en un
vector. Uno de ellos realizaba una búsqueda secuencial con
complejidad lineal sobre el tamaño del vector y
podía usarse con cualquier vector. Otro algoritmo
realizaba un búsqueda dicotomica o binaria, con
complejidad logarítmica, y solo se podía usar
cuando el vector estuviese ordenado. El algoritmo primero
responde a un razonamiento más sencillo, por lo que uno
puede sentirse tentado a usar siempre. Esta es la solución
de fuerza bruta: una solución directa, pero poco
reflexionada. Lo más razonable es comprobar si el vector
esta ordenado y, en caso positivo, aprovechar esta circunstancia
para usar el algoritmo más eficiente: el de
búsqueda binaria.

Técnicas de los Parámetros Acumuladores y
de Tabulacion
La recurcion es un mecanismo que permite obtener, en
combinación con otras contrucciones, una solución
funcional a muchos problemas. Muchos algoritmos recursivos
resultan eficientes, pero no todos: hay algunos fácilmente
formulables, pero muy ineficientes. En estos casos, dichos
algoritmos pueden servir como una primera aproximación al
algoritmo definitivo, pero debe mejorar su rendimiento para que
sea práctico.
Veremos dos parámetros para la mejora de eficiencia de
algoritmos recursivos: el uso de parámetros acumuladores y
el uso de tablas. Cada una se ilustra con un ejemplo
distinto.

Parámetros Acumuladores
Veamos primero una solución ineficiente que intentaremos
mejorar.
Ejemplo: Números de Fibonacci
Los números de fibonacci suele especificarse como:
Fib(0)=1
Fib(1)1
Fib(n+2)=fib(n)+fib(n+1)

Esta especificación de los números de
fibonacci tienen una formulación recursiva inmediata en
estilo funcional.
Un modo de evitar problema lo proporciona la técnica de
los parámetros acumuladores, cuya idea básica se
expone a continuación. La función principal usa una
función auxiliar que tiene los parámetros de
aquellas más algunos adicionales. La función
principal simplemente realiza una llamada a esta función
auxiliar en los que los parámetros de aquellas se
modifican y los parámetros nuevos toman un valor inicial
adecuado .
Los parámetros adicionales tienen como misión ir
acumulando resultados principales durante el proceso
recursivo.

Tabulacion
No todos los algoritmos recursivos ineficientes pueden
optimizarse con la técnica de los parámetros
acumuladores.
Otra técnica útil es el uso de tablas.
La intención es que la primera vez que se realiza un
cálculo, se almacena en una tabla, donde
puede consultarse otras veces que se necesite. Esta
técnica también se suele emplear con la
programación dinámica.
Ejemplo:
Sea el problema de la competición. Hay dos participantes
(deportistas o equipos, no importa que), A,B, que juegan una
competición que es ganada por el primero que venza en n
partidos, siendo ( n ) mayor que( 0 ).
Por sencillez , se supone que ambos participantes tienen
cualidades y preparación similar . De forma que cada uno
tiene un 50% de posibilidades de ganar cada partido. De todas
formas, la modificación para incorporar probabilidades
diferentes es evidente y no complica el problema.

Divide y vencerás:
Consiste en descomponer un problema en un subproblema, resolver
independientemente los subproblemas para luego combinar sus
soluciones y obtener la solución del problema original.
Esta técnica se puede aplicar con éxito a
problemas como la multiplicación de matrices, la
ordenación de vectores, la
búsqueda en estructuras ordenadas,etc.
Ejemplo. Búsqueda de una palabra en un diccionario
Como ejemplo sencillo de aplicación de esta estrategia puede
considerarse la búsqueda de una palabra en un diccionario de
acuerdo con el siguiente criterio.
Se abre el diccionario
por la pagina centrar(quedando dividido en dos mitades) y se
comprueba si la palabra aparece allí o si es léxico
gráficamente anterior o posterior. Si no ha encontrado y
es anterior se procede a buscarla en la primera mitad., si es
posterior, se buscara en la segunda mitad. El procedimiento se
repite sucesivamente hasta encontrar la palabra o decidir que no
aparece.

Método voraz:
Este método trata de producir tipo de mejor resultado a
partir de conjunto de opciones candidatas .Para ello, se va
procedimiento
paso a paso realizándose la mejor elección (usando
una función objetivo que
respeta un conjunto de restricciones ) de entre las posibles.
Puede emplearse en problemas de optimización, como el
conocido de la mochila, en la búsqueda de caminos
mínimos sobre grafos, la
planificación en el orden de la
ejecución de unos programas en un computador,etc.
Ejemplo. Dar un cambio
utilizando el menor número de monedas
Considérese ahora el problema de la devolución del
cambio al
realizar una compra (por ejemplo, en una maquina expendedora de
tabaco).
Suponiendo que se disponga de cantidad suficiente de ciertos
tipos diferentes de monedas de curso legal, se trata de dar como
cambio la menor cantidad posible usando estos tipos de monedas.
La estrategia voraz
aplicada comienza devolviendo, cuando se pueda, la moneda de
mayor valor ( es
decir, mientras el valor de dicha moneda sea mayor o igual al
cambio que resta por dar), continua aplicándose el mismo
criterio para la segunda moneda mas valiosa, y así
sucesivamente. El proceso finaliza cuando se ha devuelto todo el
cambio.

Consideraciones y Criterios para Diseñar
Algoritmos
Algunas consideraciones estilísticas pueden contribuir a
mejor la calidad de los
algoritmos (y programas ) mediante la reducción del numero
de errores que aparecen al desarrollar los. También
influyen haciendo que nuestro algoritmo resulten más
fáciles de leer y entender para otras personas.
Los criterios de estilo pueden reflejarse en un conjunto de
normas de
estilo de codificación. Ello asegura que tanto algoritmos
como programa resulten legibles y puedan modificarse
fácilmente en caso de necesidad. Generalmente, estas
normas de estilo se dirigen hacia aspectos como la forma de
construir los nombres de variables o
tipo de datos que aparezcan., la tipografía seguida ala
hora de escribir nombres de variables, subprogramas, palabras
claves, etc. El modo de encolumnar las distintas partes de un
algoritmo para facilitar su lectura y
comprensión, y la normas sobre como y donde deben de
introducirse los comentarios.
Estilo y calidad de los
programas van fuertemente unidos. Ante la pregunta
¿Cuáles son las característica de un buen
algoritmo?, las siguientes respuestas reflejan, cierta medida,
los factores que identifican la calidad en ellos .

1. Corrección, el algoritmo debe
   funcionar.
2. Nunca se debe olvidar que la característica
   más simple e importante de un algoritmo es que funcione.
   Pude aparecer obvio, pero resulta difícil de asegurar en
   algoritmos complejos.
3. Eficiencia, el algoritmo no debe desaprovechar
   recursos. La eficiencia de un algoritmo se mide por los
   recursos que este consume. En particular, se habla de la
   memoria y del tiempo de ejecución . A pesar de que con
   la reducción de los costes del hardware es
   posible diseñar computadores más rápidos y
   con más memoria, no hay que desperdiciar estos recursos
   y tratar de desarrollar algoritmos más
   eficientes.
4. Claridad, el algoritmo debe estar bien documentación. La documentación ayuda a comprender el
   funcionamiento de los algoritmos. Ciertos detalles o algunas
   partes especiales de los mismos pueden olvidarse
   fácilmente o quedar oscura si no están
   adecuadamente comentadas.

En realidad, y de acuerdo con los puntos de vista
anteriores, la calidad de un algoritmo tiene muchas facetas y
todas ellas importantes. Resumiendo, lo ideal es que nuestro
algoritmo resulte correcto, eficiente, claro, fiable y
fácil de mantener.

Algoritmos voraces
Esquema voraz
Hay muchos problemas en los que se pretende obtener un
subconjunto de n elementos que satisfaga ciertas restricciones y
que optimice alguna medida. Se supone que un problema de esta
clase tiene al menos una solución. Puede haber varias
soluciones optimas, en cuyo caso no importa cual se elija. Por
ejemplo, sea el problema de encontrar un subconjunto de los arcos
de un grafo. Otro ejemplo se da cuando, dados unos ficheros
almacenados en una cinta de que el tiempo de recuperación
de un fichero cualquiera sea el mínimo en promedio. A
menudo, el problema incluye restricciones adicionales que limitan
el número posible de soluciones.
Normalmente, estos problemas no se intentan resolver "de golpe ",
encontrando de una sola vez la solución completa y
óptima. Es más frecuente que el subconjunto de la
solución se vaya formando paso a paso, analizando durante
cada etapa que elemento conviene añadir a la
solución parcial ya existente. La dificultad principal
para resolver esta clase de problemas estriba en el
análisis necesario para poder formular
un algoritmo que halle la solución en varios pasos.
Un algoritmo voraz sigue el esquema anterior, pero con la fortuna
de que cada vez que añade un elemento a la solución
se tiene la certeza de haber realizado la mejor elección
posible. Esta característica hace que aunque el
análisis del problema sea arduo, la solución voraz
siempre resulte sencilla. La única complicación es
comprobar que se siguen satisfaciendo las restricciones del
problema.
Por lo que se ha descrito del esquema voraz, éste es un
proceso repetitivo sencillo que trata sucesivamente los
diferentes elementos del problema. Para facilitar la descripción de este proceso, puede llamarse
candidato al elemento tratado en cada paso. Inicialmente, el
conjunto de candidatos que forman la solución está
vacío. En cada paso se intenta añadir el mejor de
los candidatos restantes a dicha solución parcial. Si este
conjunto ampliado sigue siendo válido, es decir, si
satisface las restricciones del problema y, por tanto, permite
formar una solución del problema, el candidato se
incorpora definitivamente. Al contrario, si dicho conjunto no es
válido, se desecha el candidato. Si el algoritmo voraz se
ha diseñado correctamente, la primera solución
encontrada es óptima. Por tanto, la dificultad principal
al diseñar un algoritmo voraz reside en encontrar un
criterio en encontrar un criterio de selección
que garantice la optimalidad de la solución.
Según esta descripción, el problema parte
de:

• Una función objetivo que da el valor de una
  solución. Obviamente, ésta es la función
  por optimizar.
• Un conjunto de restricciones sobre el valor de los
  datos de entrada y sobre la solución final del
  problema.

A su vez, la solución consta de:

• Un conjunto de candidatos
• Una función de selección que en cada momento determine
  que candidato de los aún no usados parece ser el
  mejor.
• Una función que determine si cierto conjunto
  de candidatos es válido; es decir, si permite formar
  alguna solución del problema.

Obsérvese que las funciones de validez y
completitud no se preocupan de la optimalidad del la
solución, pero si la función de selección es
la adecuada, cada solución válida y completa es
optima.
Podemos representar el esquema voraz de la siguiente forma
funcional:
FUNCTION Voraz ( candidatos: ( 1..n ) : ( 1..n) ->
FUNCTION VorazAcumulador ( candidatos : (1..n),
Solución : (1..n) : (1..n) ->
Cadidatos = ( ) v EsSolución ( solución)->
Value siguiente -> seleccionar ( candidatos )
IN
EsVálida (solución v ( siguiente)) =>
VorazAcumulador (candidatos – (solución),
solución v (siguiente))
VorazAcumulador (candidatos – (siguiente),
solución)
VorazAcumulador (candidatos, ( ) )

Puede verse por qué estos algoritmos se llaman "
voraces " : en cada paso toman el mejor trozo de la
solución; es decir, el mejor candidato. Además,
nunca cambian de opinión: una vez que un candidato es
aceptado o rechazado en la solución, la decisión,
es definitiva.
La función objetivo no suele aparecer en el algoritmo
final, sino que se utiliza durante el análisis del
problema y es determinante en la elección de la
función de selección. De todas formas, debe
recordarse que puede haber varios criterios alternativos de
selección y que de su correcta elección depende que
la solución calculada por el algoritmo sea optima.
Como ejercicio, el lector puede intentar encontrar una
solución voraz del problema del calendario. Es
fácil encontrar una solución si en cada etapa se
genera el subcalendario correspondiente a un equipo; es decir, la
tabla de competición se va completando por filas. Como
fila primera se toma la secuencia de los índices de los
participantes en cualquier orden. Cada fila resultante puede
tener una complejidad de o (n2). Además, este algoritmo
tiene la ventaja de valer para las situaciones en que el
número de participantes no es una potencia de
dos.

Desglose en monedas
Como primer ejemplo introductorio sencillo al que puede aplicarse
la técnica voraz, se considera el problema de un cambio o
desglose en monedas. Hay que desglosar una cantidad en un
conjunto de monedas tratando de cumplir alguna condición;
en este caso, utilizar el menor número de monedas. Para
ello, se parte de un conjunto de tipos de monedas válidas,
de las que se supone que hay cantidad suficiente para realizar el
desglose, y de un importe. Se trata de indicar la cantidad
(menor) de monedas de los tipos considerados, tales que sumados
sus valores equivalgan al importe.
Para simplificar, suponemos que manejamos dinero
español
y, en particular, podemos utilizar sólo monedas de 500,
100, 50, 25, 5 y 1 pesetas para el desglose. Estos valores se
definen por medio de un tipo enumerado MONEDAS. Asimismo, se
declaran los tipos VALORES y CANTIDADES para representar el valor
asignado a cada unidad monetaria y la cantidad de cada tipo de
moneda que se devolverá en el desglose. Su
declaración es la siguiente:
TYPE
Monedas -> M500 I M100 I M50 I M25 I M5 I M1,
Valores -> Integer M500…M1
Cantidades -> Integer M500….M1

Se supone inicialmente asignados los valores a
cada uno de los tipos de monedas. Los elementos de la
técnica voraz están presentes en este problema de
la siguiente forma:

• El conjunto de candidatos está constituido por
  cada una de las monedas de los diferentes tipos que se pueden
  usar para realizar el desglose del importe dado.
• Una solución viene dad por un conjunto de
  monedas devuelto tras el desglose, y cuyo valor total es igual
  al importe a desglosar.
• La condición de factibilidad de
  la solución siendo construida establece en el desglose
  debe ser menor o igual que el importe a desglosar.
• La función de selección establece que
  hay que elegir, mientras sea posible, la moneda de mayor valor
  de entre las candidatas.
• La función objetivo cosiste en minimizar la
  cantidad total de monedas utilizadas en el
  desglose.

Con esta información se puede comprobar que en
este problema están presentes los distintos elementos de
la técnica voraz. Además, cuando un candidato
(moneda) se incorpora al conjunto solución, éste no
será nunca excluido de él.

Divide Y Vencerás
La técnica divide y vencerás consiste en
descomponer el problema en un conjunto de subproblemas más
pequeños. Después se resuelven estos subproblemas y
se combinan las soluciones para obtener la solución para
el problema original.

Esquema de Divide y vencerás.
La técnica de divide y vencerás es quizás
una de las utilizadas debido a su sencillez: si un problema es
demasiado grande para resolverlo de una vez, se descompone en
varias partes más fáciles de resolver. Mas
formalmente, dado un problema al resolver planteando en
términos de una entrada de tamaño n, la
técnica de divide y vencerás parte la entrada en k
subproblemas, 1<k<=n. Estos subproblemas se resuelven
independientemente y después se combinan sus soluciones
parciales para obtener la solución del problema original.
Este esquema de partición de problemas se denomina esquema
de divide y vencerás solo en el caso en que los problemas
sean de la misma clase del problema original. Esta
restricción permite una formulación y
resolución recursiva de los subproblemas. Por supuesto,
deben existir algunos pasos sencillos cuya solución pueda
calcularse fácil y directamente; en caso contrario, el
proceso recursivo nunca terminaría.
El caso más frecuente es cuando el número de
subproblemas es dos. Veamos el esquema de divide y
vencerás para dos subproblemas; es fácil su
generalización a k subproblemas 2<k<=n. Su
formación funcional es como sigue, considerado el problema
como de tipo dato y la solución, de tipo resultado:
TYPEVAR
Dato, resultado
FUNCTION DivideYVenceras (problema : dato) : resultado ->
EsPequeño (problema) }=>
ResolverDirectamente (problema)
|
VALUE subproblemas -> Partir (problema)
IN subproblemas == (subproblema1, subproblema2) =>
Combinar (DivideYVenceras (subproblema1) ,
DivideYVenceras (subproblema2))
Se puede hacer una formulación imperativa similar. Sin
embargo, escribiremos una formulación más
restrictiva pero bastante usual, en la que se utiliza un vector
de tamaño N.
TYPEVAR
dato, resultado
PROCEDURE DivideYVenceras (IN problema :
dato1..n,
OUT solución : resultado)
->
PROCEDURE DyVAux (IN problema : dato1..n,
IN
inferior, superior : 1..N,
OUT solución : resultado) ->
VAR
medio: 1..N
subsolucion1, subsolucion2 : resultado
IF EsPequeño (inferior, superior) THEN
ResolverDirectamente (problema, inferior, superior,
olución)
ELSE
Medio := Partir (inferior, superior);
DyVAux (problema, inferior, medio, subsolucion1);
DyVAux (problema, medio+1, superior, subsolucion2);
Combinar (subsolucion1, subsolucion2, solución)
DyVAux (problema, 1, N, solución)

El esquema general se adapta a un problema concreto al
sustituir los metasimbolos EsPequeño,
ResolverDirectamente, Partir y Combinar por funciones o
procedimientos concretos.
Si el tamaño de los dos subproblemas es el mismo (o casi),
el tiempo de cómputo de la función DivideYVecneras
se describe con la siguiente relación de recurrencia:
g(n),si n es pequeño
T(n) = 2 T(n/2) + f(n), en caso contrario
donde T(n) es la función de tiempo de DivideYVenceras para
entradas de tamaño n, g(n) es el tiempo que tarda la
función ResolverDirectamente en resolver problemas de
pequeño tamaño (normalmente una constante) y f(n)
es el tiempo necesario para partir el problema y combinar las
subsoluciones. La eficiencia final del algoritmo depende de la
función f(n) concreta que aparezca durante el
análisis. Nótese que, es general, para que esta
técnica resulte eficiente todos los subproblemas deben ser
de tamaño parecido.

Elaboración de un Calendario Deportivo:
Sea un campeonato deportivo; para nuestros propósitos
resulta indiferente el deporte objeto de la
competición, así que hablaremos de participantes en
vez de deportistas o equipos. El problema consiste en elaborar un
calendario de competición de forma que cada participante
compita exactamente una vez con cada uno de los demás
participantes. Por concreción, y sin perdida de
generalidad, puede suponerse que las competiciones se celebran en
días sucesivos y que cada participante compite una vez por
día.
Para simplificar el problema, se supone que el numero de
participantes es una potencia de dos; es decir, hay n =
2k participantes para algún entero positivo k.
Se supone también que cada participante tiene asignado un
número comprendido entre 1 y N. Se necesitan elaborar n-1
competiciones por participantes. Por tanto, la solución
del problema puede representarse en una tabla de dimensión
nx(n-1). El elemento (i,j)–esimo de la tabla, 1<=
i<=n, 1<=j<n, contiene el numero del participante contra
el que el participante i-esimo compite el día j-esimo.
Obsérvese que los números de participantes
incluidos en la fila i de la tabla son distintos porque el
participante i-esimo solo debe competir una vez con cada
participante restante. A su vez, la columna j también
contiene números distintos, porque el día j-esimo
cada participante solo puede competir con otro participante.
Se dispone de una solución inmediata aplicando fuerza
bruta. Primero se obtiene para cada participante i,
1<=i<=n, el conjunto P(i) de todas las permutaciones
posibles del resto de los participantes con los que debe
competir, es decir, el conjunto de permutaciones de los
números {1..n}-{i} ahora se completan las filas de la
tabla de todas las formas posibles, incluyendo en cada fila i
algún ejemplo de P(i). Solo sirve como solución
aquellas combinaciones de fila que cumplan las restricciones
enunciadas en el párrafo
anterior sobre las columnas de la tabla (las restricciones sobre
las filas están garantizadas por el modo de generar los
conjuntos
P(i)). Si hay varios calendarios validos, se elige uno
cualquiera.
El método de fuerza bruta resulta sencillo, pero es
terriblemente ineficiente. Cada conjunto P(i) consta de (n-1)!
Elementos. Dado que el numero de participantes de n, resultan
nx(n-1)!=n! formas de rellenar la tabla.
Sin embargo la aplicación de la técnica de divide y
vencerás produce una solución mas sencillas aun
pero muy eficientes. La siguiente figura describe visualmente
parte de la elaboración de la tabla.

Se distinguen dos casos. El caso básico se da
cuando solo hay dos participantes. La solución es directa
porque se celebra una sola competición entre ambos. El
caso recursivo, cuando hay más de dos participantes, es
más complejo. Si el numero de participantes es
2k , para k>1, puede decirse que el "tamaño"
del problema es 2k (sabemos que el calendario
tendrá un tamaño de 2k x(2k-1
-1) posiciones). El problema puede reducirse a dos sub problemas
de tamaño 2k-1 si se elaboran
independientemente dos subcalendarios de tamaño
2k x(2k-1 -1): uno para los participantes,
de numeración comprendida entre 1 y 2k-1 y otro
para los participantes comprendidos entre 2k-1 +1 y
2k . Sin embargo, la unión de estos
subcalendarios no forma un calendario completo para el campeonato
de 2k participantes, ya que a unión de los dos
calendarios tiene un tamaño 2k
x(2k-1 -1), faltando 2k x2k-1
celdas para completar el calendario total. En efecto, faltan por
elaborar las competiciones cruzadas entre los participantes de
numeración inferior y los de numeración
superior.
Por fortuna, el resto del calendario se puede construir
fácilmente. Completemos primero la parte de los
participantes de numeración inferior. El subcalendario del
primer participante es sencillo porque basta con que compita en
días sucesivos con los participantes de numeración,
superior en orden creciente de numeración; es decir,
sucesivamente con los participantes 2k-1
+1,….,2n . El siguiente participante toma esta
secuencia y realiza una fácil permutación de la
misma que le garantiza el respeto de las
restricciones de la solución; por ejemplo, rotando dicha
secuencia a la derecha. Este proceso se repite para el resto de
los participantes de numeración inferior. El calendario de
los participantes de numeración superior se completa de
forma similar con los números de los participantes de
numeración inferior.

El algoritmo descrito se expresa a
continuación.
PROCEDURE Calendario ( INOUT tabla :
(1..N)1..N,1..N-1) ->
PROCEDURE FormaTabla (IN inf : 1..N,
IN sup :1..N,
OUT tabla : (1..N) 1..N,1..N-1) ->
VAR
medio : 1..N
IF inf = sup-1 THEN
tablainf.1 : = sup;
tablasup.1 := inf
ELSE
medio := (inf + sup) Div 2;
FormarTabla (inf, medio, tabla);
FormarTabla (medio+1, sup, tabla);
CompletarTabla (inf, medio, medio,sup-1, medio+1, tabla);
CompletarTabla (medio+1, sup, medio, sup-1, inf,
tabla)

Este sistema de
ecuaciones
defina una función de tiempo del orden de O(n2), que es
mucho mas eficiente que la solución de fuerza bruta.
Veamos otra estrategia, también de orden de complejidad
cuadrática, donde se aplica divide y vencerás para
resolver el problema y que se aprovecha de la simetría de
la solución. La idea consiste en añadir
inicialmente a la tabla una columna "ficticia" de índice
j=0, que almacena los índices de las filas. Después
se genera, mediante divide y vencerás, la mitad izquierda
de la tabla. Finalmente se completa la mitad derecha de la tabla
(correspondiente al cruce de los dos grupos de equipos
cuyos subcalendarios se han generado por divide y
vencerás). En esta última etapa, los valores de
las casillas (k,l), siendo 1<=k<=n y 0<=l<=(n/2)-1,
de acuerdo con las siguientes expresiones de los
índices:
i = (k + n/2) Mod (n+1)
j = (1 + n/2) Mod n
De esta forma se rellenan las casillas aun vacías, es
decir, los componentes tablai,j a partir de las
casillas tablak,l ya completadas.

Ordenación de un Vector por Mezcla:
La ordenación de un vector es un problema que se presta
fácilmente a la aplicación de la técnica de
divide y vencerás. El caso básico corresponde a un
subvector de un solo elemento, que obviamente ya esta ordenado.
Para el caso general, sea vi..s un vector de
índice inferior i e índice superior s. La
partición puede hacerse por la mitad si se toma un
índice m=[(i+s)/2] y dos subvectores vi..m y
vm+1..s . la combinación de los dos subvectores
ya ordenados es fácil. basta con mezclar los dos
subvectores, mediante comparaciones de sus elementos sucesivos,
para obtener un único vector ordenado. Este proceso de
mezcla es realizado por un procedimiento auxiliar. El algoritmo
resultante es:
PROCEDURE Ordenar (INOUT v : INTEGER1..N) ->
(* ordenación por mezcla *)
PROCEDURE OrdenarAux (INOUT Vector :
INTEGER1..N,1..N,
IN inf, sup : 1..N) ->
VAR
Medio : 1..N
IF inf < sup THEN
medio := (inf+sup) Div 2;
OrdenarAux (vector, inf, medio);
OrdenarAux (vector, medio+1, sup);
Mezclar (vector, inf, medio, sup)
OrdenarAux (v, 1, N)

El procedimiento para realizar la mezcla de los
subvectores ordenados es:
PROCEDURE Mezclar ( IN inf : INTEGER,
IN medio: INTEGER,
IN sup : INTEGER,
INOUT vector : INTEGER1..N) ->
VAR
vectorAux : INTEGER1..N,
i1, i2, j : INTEGER,
índice : INTEGER
i1 := inf;
i2 := medio + 1;
j := inf;
WHILE (i1<=medio) ^ (i2<=sup) DO
IF vectori1 << vectori2 THEN
vectorAuxj :=vectori1;
i1 :=i1 + 1
ELSE
vectorAuxj ;= vectori2;
i2 := i2 + 1
j := j +
FOR índice IN i1..medio DO
vectorAuxj := vectorindice;
J := j + 1
FOR índice IN i2..sup DO
vectorAuxj := vectorindice ;
J := j + 1
FOR índice In inf..sup DO
vectorindice := vectorAuxindice

El algoritmo resultante es sencillo conceptualmente.
Es fácil analizar la complejidad del algoritmo para un
vector de longitud n. La operación de mezcla es
proporcional a n, de forma que las ecuaciones de
recurrencia de la función de tiempo son:
T(n) = a, n=1, a=cte
2T(n/2) + bn, n>1, b=cte

Si n es una potencia de 2; es decir, n =2k
para algún k, las ecuaciones anteriores se resuelven por
sustituciones sucesivas, resultando:
T(n) = 2T(n/2) + bn=…=2K T(n/2K) +
kbn = an + bn log2 n
El algoritmo de ordenación por mezcla es óptimo en
tiempo de ejecución. Los únicos inconvenientes que
presenta es que el procedimiento de mezcla necesita gran
capacidad de almacenamiento
(para dos copias del vector) y que, además de mezclar,
necesita copiar el vector auxiliar completo en el principal.
Puede diseñarse un algoritmo de mezcla más complejo
que mejore ambos aspectos, pero mantenga la complejidad
asintótica calculada.

Multiplicación de Matrices:
Sean dos matrices, A y B, de dimensión nxn. La matriz
producto C=AxB
también es una matriz de nxn cuyo elemento (i,j)-esimo se
forma multiplicando cada elemento de la final i-esima de A por el
elemento correspondiente de la columna j-esima de B y sumando los
productos
parciales.
El cálculo
de cada elemento Cij requiere n multiplicaciones. La
matriz C tiene n2 elementos, así que el tiempo
total del algoritmo de multiplicación es de orden
O(n3).
El algoritmo anterior, que podemos llamar algoritmo convencional
de multiplicación de matrices, proviene directamente de la
definición matemática
del producto de
matrices. Sin embargo, la técnica de divide y
vencerás sugiere un algoritmo distinto.
Supongamos, por sencillez, que n es una potencia de dos; es
decir, que existe un entero no negativo k tal que
n=2k. (Si n no es un potencia de dos, pueden
añadirse las filas y columnas de ceros necesarias para
formar una dimensión que sea potencia de dos.) las
submatrices A y B pueden partirse en cuatro submatrices de
dimensión (n/2)x(n/2). Si el producto AxB tiene la
forma:
A11 A12 B11
B12 C11 C12
A21
A22 B21 B22 C21
C22
Entonces:
C11 = A11*B11 +
A12*B21
C12 =
A11*B12 +
A12*B22
C21 =
A21*B11 +
A22*B21
C22 =
A21*B12 +
A22*B22

Para n=2, los elementos Cij se calculan
mediante algunas multiplicaciones y sumas de números, pero
para n>2 las submatrices Cij se calculan mediante
multiplicaciones (recursivas) y sumas de submatrices de
dimensión (n/2)x(n/2). Dos submatrices de (n/2)x(n/2)
pueden sumarse en un tiempo bn2, siendo b alguna
constante.
La resolución de este sistema de ecuaciones nos dice que
O(T(n))=OT(n3), de forma que no se ha conseguido ningún
ahorro
sustancial de tiempo. Sin embargo, interesa encontrar algoritmos
mas eficientes, porque la multiplicación esta relacionada
con otras operaciones sobre matrices mas usuales, como inversión de una matriz o hallar su
determinante. La existencia de un algoritmo eficiente para la
multiplicación (en realidad, para cualquier
operación de las anteriores) significaría la
existencia de un algoritmo similar para las demás.
Podría conseguirse mas eficiencia si lográramos
realizar menos multiplicaciones de matrices, aunque fuera a costa
de un mayor numero de sumas de matrices, dado que la complejidad
respectiva de estas operaciones es O(n3)n y o(n2). El algoritmo
de Strassen calcula las cuatro submatrices Cij
empleando 7 multiplicaciones y 18 sumas o restas de
matrices.

Programación Dinámica
Principios de
programación dinámica
Se ha visto que la técnica voraz se aplica a problemas
cuya solución puede formularse como el resultado de una
secuencia de decisiones. El método es eficiente porque una
vez que se toma una decisión en un paso, no se reconsidera
en el futuro, conduciendo de forma directa a la solución.
Sin embargo, no todos los problemas pueden resolverse de esta
manera, asegurando que la secuencia de decisiones es la mejor de
las posibles.
La programación dinámica (también llamada
planificación dinámica) es una
técnica de programación que también permite
resolver problemas mediante una secuencia de decisiones, pero de
una manera menos directa que en el caso voraz. Esta vez se
necesita producir varias secuencias de decisiones. Solamente al
final se sabe cuál es la mejor de todas.
No es fácil establecer una definición de la
programación dinámica; una característica es
que el programa "aprende "dinámicamente de las decisiones
que toma. Además, todo problema resoluble con esta
técnica debe de satisfacer el principio de optimalidad.
Este principio establece que "una secuencia óptima de
decisiones que resuelve un problema debe cumplir la propiedad de
que cualquier subsecuencia de decisiones también debe ser
óptima respecto al subproblema que resuelva ".
Usando una técnica de fuerza bruta, el número de
secuencias de decisión es exponencial sobre el
número de decisiones, porque si hay d opciones para cada
una de las n decisiones, resultará un total de d
secuencias posibles de decisión. En la programación
dinámica todos los subproblemas se resuelven de acuerdo
con criterio de tamaño creciente y los resultados de
subproblemas más pequeños se almacenan en
algún tipo de estructura de
datos
(normalmente tablas) para facilitar la solución de los
problemas más grandes. De esta forma se reduce al
número total de subsecuencias generadas, evitándose
una explosión combinatoria en la producción de las secuencias y
consiguiéndose soluciones más eficientes en cuanto
a tiempo de ejecución.
Podemos formalizar algo más la idea básica.
Supongamos que tenemos un problema que satisface el principio de
optimalidad, tal que Eo es el estado
inicial del problema y deben tomarse n decisiones d, 1<i<n.
Sea
D = { v1…..vn} el conjunto de valores de decisión
posibles para la decisión d1. sea, asimismo, Eli el
estado del
problema tras la elección del valor vli 1<i<n1 y Sli
una secuencia óptima de decisiones respecto al estao Eli.
Entonces, una secuencia óptima de decisiones respecto a E0
es la mejor secuencias de decisión { Vli Sli },
1<i<N1.
El razonamiento anterior se refiere a la primera decisión
d1 tomada desde el estado
inicial E0 sin embargo, puede generalizarse la formulación
del problema a cualquier subsecuencia de decisiones
dk…..,dl, 1<k<n, partiendo como estado inicial
de Ek-1. si este subproblema de simboliza como problema (k,l),
entonces el problema completo es problema ( l,n ). Tiene sentido
centrarse en un subproblema del problema inicial porque
éste satisface el principio de optimalidad pero,
además, tiene la ventaja ( quizás paradójica
al tratar de un problema más pequeño ) de que
proporciona una visión más general del problema en
cuestión. ( Obsérvese que vamos a usar la
técnica de resolución de problemas por
generalización para después poder realizar una
particularización de la solución obtenida.)
Una solución dinámica para problema ( k,1 ) debe
expresarse en términos de los valores de decisión
existente para decisiones d1 y el subproblema problema ( k+1,1 )
resultante de aplicar cada valor de decisión. La
expresión inicial de la ecuación de recurrencia,
hay un caso en que la decisión d1 no va seguida por
ninguna secuencia de decisiones, que es problema ( n,n ).
En resumen, la aplicación de la técnica de
programación dinámica a un problema significa
comprobar primero el principio de optimalidad y desarrollar
después unas ecuaciones recurrentes del estilo de (1) y
(2). La ecuación general relaciona la secuencia
óptima en una etapa i con la decisión tomada en la
etapa i y la subsecuencia óptima en la etapa posterior
i+1. la ecuación de base establece el valor para la etapa
n+1 en que no queda ninguna decisión Xi, 1<i<n, a
tomar.
La ecuación de recurrencia puede formularse de dos formas:
delantera o trasera. Sea X1…..Xn la secuencia de
decisiones necesaria para resolver el problema. La
formulación delantera expresa la decisión de Xl ,
1<i<n, a partir de la secuencia de decisiones
Xi+1……Xn ( es la clase de formulación
adoptada hasta ahora ). La formulación trasera expresa la
decisión de Xi, 1<i<n , a partir de la recurrentes
con formulación trasera es igual que e la
formulación delantera, sólo que en orden contrario.
La elección de una formulación delantera o trasera
depende del problema considerado o, sencillamente, del gusto del
programador.

Algoritmos De Vuelta Atrás
Existen un alto número de problemas que pueden formularse
como la búsqueda de la mejor solución o del
conjunto de todas las soluciones que satisfacen ciertas
condiciones. Además, cada solución es el resultado
de una secuencia de decisiones. Por supuesto, debe existir una
función de criterios que debe ser satisfecha por cada
secuencia solución u optimizada por dichas secuencias
solución si solo queremos la mejor. En algunos problemas
de optimización se conoce un criterio óptimo de
selección que puede usarse de forma voraz. Otros problemas
satisfacen el principio de optimalidad, pudiéndose aplicar
la técnica de programación dinámica. Sin
embargo, todavía hay otros problemas peores que no queda
mas remedio que realizar una búsqueda de la
solución.

Esquema de Algoritmos de Vuelta Atrás:

Sea (x1,…,xi) el camino desde la raíz hasta un
nodo de un árbol del espacio de estado. Sea G(x1…xi) el
conjunto de todos los valores posibles de xi+1 tales que
(x1,…,xi+1) es un camino hasta el estado del problema.
Supongamos que existe algún predicado acotador A tal que
A(x1,…,xi+1) es falso si el camino (xi,…,xi+1) no puede
extenderse para alcanzar un nodo de respuesta. Por lo tanto, los
candidatos para la posición i+1 del vector desolucion
x1..n son aquellos valores generados por G que satisfacen A.
Supongamos que también existe algún predicado R que
determina si un camino (x1,…,xi+1) termina en un nodo de
respuesta.
El Algoritmo de Vuelta Atrás se especifica de la forma
siguiente:
PROCEDURE Retroceso (IN k : INTEGER, INOUT solucion :
elemento1…n) ->
VAR
nodo : elemento
FOR noso IN G(solucion, 1, k-1) DO
Solucion k := nodo;
IF R(solucion, 1, k) THEN
IF R(solucion, 1,k) THEN
<< guardar ‘solucion’ >>;
Retroceso (k+1, solucion)
La llamada inicial del algoritmo es Retroceso(1, solucion). El
procedimiento no hace ninguna llamada recursiva cuando k = N+1 o
cuando ningún nodo generado por G satisface el elemento
posible que satisfacen A se añade una solución
particular, se comprueba si se ha encontrado una solucion.
Después simplemente se llama recursivamente al algoritmo
para generar los estados descendientes. Se sale del bucle FOR
cuando no quedan mas valores para solución terminando la
llamada actual al algoritmo.

Ramificación (Bifurcacion) Y Acotación
Los métodos de Ramificación y Acotación
constituyen un a variante de las técnicas de retroceso
para problemas donde se trata de encontrar el valor máximo
o mínimo de cierta función objeto (esto suele
suceder en los problemas de programación
lineal entera).

La técnica de ramificación y acotacotacion
aplica de la siguiente manera:
Supóngase que al recorrer un árbol y alcanza una
hoja se tiene una solucion con k colores, y que al
seguir avanzando en el árbol (mediante la
aplicación de varios pasos de retrocesos) se alcanza un
nodo que requiere k+1 colores. En este
punto podemos retroceder (y no seguir avanzando por mas ramas),
pues tenemos ya una solucion mayor. Así, k sirve de cota
inferior al retroceso. Este mismo proceso se repite en el resto
de nodos del árbol, evitando así la
exploración de gran parte de al estructura.

Algoritmos Heuristicos
Existen muchos problemas para los cuales no se conocen algoritmos
que puedan encontrar la solución de forma eficiente:
problemas NP-completos.
La solución exacta puede requerir un orden factorial o
exponencial: el problema de la explosión combinatoria.
Se hace necesario utilizar algoritmos heurísticos:
Un algoritmo heurístico (o simplemente heurística)
puede producir una buena solución (puede que la
óptima) pero también puede que no produzca ninguna
solución o dar una solución no muy buena.
Normalmente, se basa en un conocimiento
intuitivo del programador sobre un determinado problema.
La estructura de algoritmo voraz se puede utilizar para construir
procedimientos heurísticos: hablamos de heurísticas
voraces.
Objetivo: obtener buenas soluciones en un tiempo de
ejecución corto.
El problema del viajante
Problema: Dado un grafo no dirigido, completo y ponderado G = (V,
A), encontrar un ciclo simple de costo
mínimo que pase por todos los nodos.
Es un problema NP, pero necesitamos una solución
eficiente.
Problema de optimización, donde la solución
está formada por un grupo de
elementos en cierto orden: podemos aplicar el esquema voraz.
Posibilidades:

1. Los nodos son los candidatos. Empezar en un nodo
   cualquiera. En cada paso moverse al nodo no visitado más
   próximo al último nodo seleccionado.
2. Las aristas son los candidatos. Hacer igual que en el
   algoritmo de Kruskal, pero garantizando que se forme un
   ciclo.

Heurística voraz 1
– Una solución será un cierto orden en el
conjunto de nodos (c1, c2, …, cn), el orden de visita de los
nodos.
Inicialización: seleccionar un nodo cualquiera.
Función de selección: de los nodos candidatos
seleccionar el más próximo al último (o al
primero) de la secuencia actual (c1, c2, …, ca).
Acabamos cuando tengamos n nodos.
Ejemplo.
Empezando en el nodo 1.
Solución: (1, 4, 5, 3, 2)
Coste: 30+15+25+10+45=125
Empezando en el nodo 3.
Solución: (5, 4, 3, 2, 1)
Coste: 15+20+10+45+50=140
Heurística voraz 2
– Una solución será un conjunto de aristas
(a1, a2, …, an-1) que formen un ciclo hamiltoniano, sin
importar el orden.
Empezar con un grafo sin aristas.
Selección: seleccionar la arista candidata de menor
coste.
Factible: una arista se puede añadir a la solución
actual si no se forma un ciclo (excepto para la última
arista añadida) y si los nodos unidos no tienen grado
mayor que 2.
•Ejemplo.
Solución: ((2, 3), (4, 5), (3, 4), (1, 2), (1, 5))
Coste = 10+15+20+45+50 = 140

Conclusiones:
Ninguno de los dos algoritmos garantiza una solución
óptima. Sin embargo, normalmente ambos dan soluciones
buenas, próximas a la óptima.
Posibles mejoras: buscar heurísticas mejores; repetir la
heurística 1 con varios orígenes; ó bien, a
partir de la solución del algoritmo intentar hacer
modificaciones locales para mejorar esa
solución.

Algoritmos De Aproximación
Dado un problema NP completo, es probable que no sepamos
resolverlo de manera precisa y completa utilizando un algoritmo
polimico en tiempo. Para este tipo de problemas, los algoritmos
que no conducen a una solución óptima se llaman
algoritmos de aproximación. Sin embargo, resulta
parcialmente interesante que estos garanticen una cota en el
margen de imprecisión.
A continuación se ilustra este tipo de tratamiento de
problemas al problema de recubrimiento de un grafico:
Dado un grafo G=(V,A), se trata de encontrar un conjunto con el
menor numero de vértices tal que toda arista sea incidente
por lo menos de un vértice de V.
Este problema se puede resolver a través de otro
aproximado, como es calcular el ajuste maximizal del grafo G. Se
trata de calcular un subconjunto A’ de aristas tal que dos
aristas cualquiera de A’ no tengan ningún
vértice común y toda arista de A-A’ comparta
algún vértice común con una arista de
A’. Este nuevo problema garantiza conseguir un
recubrimiento que contiene no más de dos vértices
del recubrimiento mínimo. El procedimiento para construir
un ajuste maximizal de un grafo G consistiría en ir
tomando aristas de G, de una en una y en cualquier orden e ir
eliminando las incidentes al conjunto que se esta construyendo
hasta recubrir todo en grafo.
Para poder aplicar el nuevo problema aproximado, seria necesario
demostrar que el conjunto de todos los vértices inciden a
las aristas de un ajuste maximal M para un grafo G es un
recubrimiento con no mas de dos veces el numero de veces el
recubrimiento de tamaño mínimo. Esto es evidente,
ya que por la definición de ajuste maximal, los
vértices incidentes a las aristas de M son un
recubrimiento de G. también por la propia
definición, ningún vértice perteneciente a M
puede recubrir a mas de una arista en M. En consecuencia, por lo
menos la mitad de los vértices de M deben pertenecer a un
recubrimiento.