Tema 2
Análisis y diseño de algoritmos
Objetivo: El alumno aplicará diversas técnicas para
el análisis y el diseño de algoritmos orientados a la
solución de problemas computacionales.
2.1 Fundamentos de algorítmica
• ¿Para qué estudiar temas de Teoría de la Computación?
• Una formación más sólida, un computólogo más profesional.
• Desarrollo y uso de herramientas complejas.
• Seguir adelante a un posgrado.
• Dedicarse a la teoría de la computación en investigación y
docencia.
2.2 Algorítmica básica
• El objetivo principal de esta rama de las Ciencias de la Computación
es analizar algoritmos para determinar la cantidad de recursos (tales
como tiempo o espacio) que se necesitan para ejecutarlo.
• La mayoría de los algoritmos se diseñan para trabajar con entradas de
longitud arbitraria.
• Usualmente la eficiencia de un algoritmo se expresa como una
función que relaciona la longitud de la entrada con el número de
pasos (complejidad temporal) o la cantidad de memoria (complejidad
espacial).
2.2.1 Algoritmos y programas
• Un algoritmo (o procedimiento) es un conjunto finito de instrucciones
libres de ambigüedades que sirven para realizar una tarea específica;
el término “algoritmo” se debe al matemático persa Al-Khowarizmi.
• El concepto de algoritmo fue definido
formalmente por Church en 1936 con el
cálculo lambda, y por Turing con
máquinas de Turing.
2.2.1 Algoritmos y programas
• Un algoritmo computacional debe cumplir con una serie de
requisitos:
• Debe ser una descripción exacta de las actividades a
realizar que cualquiera pueda tener éxito al realizarlas,
incluso si no tiene idea del objetivo del algoritmo.
• Debe ser absolutamente libre de ambigüedades,
excluyendo interpretaciones diferentes.
• No importa quien ejecute las instrucciones del algoritmo,
el resultado debe ser exactamente el mismo cada vez que
se aplique a la misma entrada.
2.2.1 Algoritmos y programas
• Un programa es una secuencia de
instrucciones representadas de
forma que sean “entendibles” por
una computadora.
• De este modo, la programación puede
verse como la actividad de “reescribir”
algoritmos en instrucciones de algún
lenguaje de programación.
2.2.2 Representación de los algoritmos
• Cuando se desarrollan algoritmos computacionales, el objetivo es
que posteriormente se pueda escribir un programa a partir de ese
algoritmo.
• Existen dos formas de representar este tipo de algoritmos:
• Pseudocódigo.
• Diagrama de flujo.
[Link] Pseudocódigo.
• El pseudocódigo, es un tipo de lenguaje pseudonatural estructurado
utilizado para describir algoritmos computacionales.
• Es una descripción compacta y de alto nivel de un algoritmo
computacional que combina lenguaje natural con algunas
convenciones sintácticas similares a las de los lenguajes de
programación.
• El objetivo es que sea entendido por
personas, más que por una computadora;
sin embargo debe ser lo más completo
posible.
[Link] Pseudocódigo.
• No existe un estándar para escribir pseudocódigos; sin embargo, se
pueden establecer mejores prácticas para su escritura:
• Verbos en infinitivo para indicar órdenes (psudoinstrucciones).
• Enumerar las instrucciones.
• Distinguir órdenes, y estructuras de control tipo lenguaje de programación del
resto de los elementos del algoritmo, usando mayúsculas o negritas.
• Establecer distinción clara entre asignación y comparación, usualmente se
utiliza '<-' para la primera y '=' para la segunda.
• Utilizar indentación para bloques de código que se encuentran anidados.
[Link] Diagrama de flujo.
• Un diagrama de flujo (flowchart en inglés), es la representación gráfica
de un algoritmo; se compone de símbolos estandarizados que
representan acciones específicas.
• Existen diversos estándares para la simbología utilizada en
diagramas de flujo, el más utilizado está definido por la International
Organization for Standardization (Organización internacional para la
estandarización), en su estándar ISO 5807:1985.
[Link] Diagrama de flujo.
[Link] Diagrama de flujo.
• Además de utilizar símbolos estandarizados en los diagramas de
flujo, existen otras características útiles al momento de realizarlos:
• Nombre del algoritmo, para evitar confusiones posteriores.
• Fecha de creación ó actualización, para identificar la versión más reciente.
• Nombre de la persona o grupo que creo el diagrama.
• Puntos de inicio y fin claros, para facilitar su uso.
• Dirección de flujo clara, de arriba a abajo y de izquierda a derecha.
• En caso de utilizar algún símbolo no estandarizado, debe indicarse
claramente su uso.
2.2.2 Representación de los algoritmos,
ejemplo
• Realizar un algoritmo para obtener el factorial de un entero
positivo n.
2.2.2 Representación de los algoritmos, tarea
• Realizar pseudocódigo para:
• Obtener la serie de Fibonacci hasta el
n-ésimo elemento.
• Multiplicar dos polinomios de diferente
grado.
• Ordenar un conjunto de n elementos.
• Sumar dos matrices de n x m elementos.
2.3 Complejidad
• El propósito de la complejidad computacional es medir la cantidad de
recursos necesarios para resolver problemas concretos y clasificar tareas
algorítmicas con respecto a su dificultad computacional.
• Su principal objetivo es dividir problemas algorítmicos en la clase de
problemas solubles (tratables) y no solubles (intratables) de forma práctica.
• La teoría de la complejidad ha mostrado que
existen problemas computacionales para los
cuales la energía del Universo no sería
suficiente para resolverlos:
• Soluble algorítmicamente no implica que sea tratable.
2.3.1 Medidas de complejidad
• Elegir qué debe contarse involucra dos pasos:
• Elegir las operaciones significativas.
• Decidir qué operaciones se considerarán
como atómicas y serán contadas o no.
• Existen dos clases de operaciones que típicamente se eligen como
significativas: de comparación y aritméticas.
2.3.1 Medidas de complejidad
• Las operaciones de comparación se consideran equivalentes y se
contabilizan en algoritmos de búsqueda y ordenamiento.
• En este tipo de algoritmos, la tarea importante
es comparar dos valores:
• En la búsqueda, para verificar si el valor
se ha encontrado.
• En el ordenamiento, para revisar si los
valores están desordenados.
2.3.1 Medidas de complejidad
• Los operadores aritméticos se contabilizan en dos grupos:
• Aditivos: adición, substracción,
incremento y decremento.
• Multiplicativos: multiplicación,
división y módulo.
• Estos dos grupos se cuentan de forma separada debido a que los
multiplicativos toman más tiempo que los aditivos.
• Un caso especial es división o multiplicación entera por 2; este operación
puede reducirse a una operación de desplazamiento, que se considera tan
rápida como una operación aditiva.
[Link] ¿Por qué es útil medir la
complejidad?
• Una vez que se ha seleccionado qué se medirá para determinar la
complejidad, se debe obtener una función del tamaño de la entrada que
caracteriza el comportamiento del algoritmo.
• Al igual que en otras disciplinas científicas, el conocimiento sirve para
predecir el comportamiento de diversas
situaciones y procesos de interés: si se logra
determinar la complejidad temporal de un
algoritmo, entonces se puede predecir de
forma confiable el tiempo de ejecución del
algoritmo para diferentes instancias sin tener
que ejecutar el cómputo correspondiente.
[Link] ¿Por qué es útil medir la
complejidad?
• Además, se puede comparar la eficiencia de dos o más algoritmos
CAPÍTULO 1. ANÁLISIS Y DISEÑO DE ALGORITMOS
que resuelven el mismo problema, simplemente analizando sus
funciones de complejidad.
• Por ejemplo, si se tiene un algoritmo cuya
función es n^2 y otro con complejidad n+5.
La forma más sencilla de compararlos es
graficando ambas funciones.
• En la figura es fácil notar que a partir
Figurade1.2: n=3, el algoritmo
Comparación con
de funciones de complejidad de dos a
función n+5 resulta mejor queEn el algoritmo
la figura cuya
es fácil notar que a función
partir de n =es n^2.
3, el algoritmo con funci
que el algoritmo cuya función es n2 .
1.3.2. Notación “O” y “o”
Dado que la razón de crecimiento de un algoritmo es importante y que e
2.3.1 Medidas de complejidad, tarea
• Ordena las siguientes funciones de acuerdo a su rapidez de
crecimiento:
•
2.3.2 Notación “O” y “o”
• Dado que la razón de crecimiento de un algoritmo es importante y que
esta razón es dominada por el término más grande en una ecuación, los
términos que crecen más lentamente pueden ser despreciados.
• Una vez que se eliminan todos estos términos, el resultado se conoce como
el orden de la función o del algoritmo relacionado.
• Las consideraciones anteriores nos llevan a
estudiar el comportamiento de un algoritmo
cuando se fuerza el tamaño del problema al
que se aplica; matemáticamente hablando,
cuando n tiende a infinito:
su comportamiento asintótico.
[Link] Notación “O” y “o”
• Los órdenes más comunes en análisis de algoritmos, en orden creciente,
son los siguientes, c representa una constante y n el tamaño de la entrada:
O (1) constante
O ( log n ) logarítmico
O (n) lineal
O ( n log n ) lineal-logarítmico
( )
O nc polinomial
O (c )
n
exponencial
O ( n!) factorial
[Link] Notación “O” y “o”
• O(g(n)), llamada O grande, representa la clase de funciones que no crecen
más que g(n) o, de otro modo: g(n) es la cota superior de la razón de
crecimiento de un algoritmo.
En términos precisos, si f(n) representa el tiempo
de ejecución de un algoritmo, y g(n) es alguna
expresión para su cota superior, f(n) está en el
conjunto O(g(n)), si existen dos constantes positivas c y n0 tales que
|f(n)|<= c|g(n)| para todo n>n0, con n0 entera y c real.
• o(g(n)), llamada o pequeña se utiliza para determinar funciones del mismo
orden o, de otro modo, “f(n) crece igual que g(n) asintóticamente”.
Formalmente, establece que si n es muy grande, f(n)/g(n) =1.
[Link] Notación “O”, ejemplo
• Mostrar que f(n)=2n^3+5n^2+n es O(g(n)), con g(n)=n^3.
• De acuerdo a la definición, debemos encontrar dos constantes positivas c y n0
tales que |f(n)|<= c|g(n)| para todo n>n0.
• La constante c debe ser mayor que el coeficiente del término dominante.
Para este ejemplo, debe cumplirse que c>2, usaremos c=3.5.
• Ahora, hay que determinar un n0 tal que |f(n)|<= c|g(n)| para n>n0.
Para obtener un n0, buscamos que:
2n0^3+5n0^2+n0 <= 3.5n0^3 ó 2n0^2+5n0+1 <= 3.5n0^2
Con un poco de álgebra, obtenemos:
-1.5n0^2+5n0+1<=0; cuyas raíces son: 0.2137 y 3.1196
Como n0 debe ser entera, probamos con 1 y 4, de donde vemos que el
segundo valor cumple con la restricción.
[Link] Notación “O”, tarea
• Clasifica las siguientes funciones de acuerdo a la notación O(g(n)):
•
2.3.3 Algoritmos de comportamiento
logarítmico
• Los algoritmos de complejidad O(n) y O(n log n) son los que muestran un
comportamiento más “natural”: si se duplica el tamaño de la entrada, se
requerirá el doble de tiempo para resolverlos.
• Los algoritmos cuya función característica
es logarítmica, es decir O(log n), son un
descubrimiento fenomenal, pues en el
doble de tiempo permiten atacar problemas
notablemente mayores, y para resolver un
problema el doble de grande sólo hace falta un poco más de tiempo
(mucho menos del doble).
2.3.4 Algoritmos de tiempo polinomial
• Los algoritmos de tiempo polinomial, son
aquellos cuya razón de crecimiento está
acotada por algún polinomio, esto es O(n^x)
para x>=2.
• No son una maravilla, y se enfrentan con
dificultad a problemas de tamaño creciente.
• En la práctica son el límite de lo tratable.
2.3.5 Algoritmos factibles y no factibles
• Sobre la tratabilidad de los algoritmos de complejidad polinomial se
puede polemizar; mientras complejidades del orden O(n^2) y O(n^3)
suelen ser efectivamente abordables, prácticamente nadie afirma lo mismo
para algoritmos de orden O(n^100); la frontera es imprecisa.
• Cualquier algoritmo por encima de una
complejidad polinomial se clasifica como
“intratable” y sólo será aplicable a
instancias muy pequeñas de esos
problemas.
• En la URL siguiente, se muestran ejemplos de diferentes funciones con sus
gráficas correspondientes:
[Link]
2.3.6 Cota inferior y superior
• Dado lo anterior, es natural que se busquen algoritmos de complejidad
lineal. Es muy afortunado encontrar algoritmos logarítmicos. Las
soluciones polinomiales son las más comunes, se puede vivir con ellas;
pero ante soluciones de complejidad superior, es mejor seguir buscando
alternativas.
• La cota inferior asintótica es una función que sirve como frontera mínima de
otra función cuando el argumento tiende a infinito. Se utiliza para
determinar la complejidad del mejor caso para los algoritmos.
• La cota superior asintótica es una función que sirve
como frontera máxima de otra función cuando el
argumento tiende a infinito. Se utiliza para definir
clases de complejidad.
2.3.7 Valor promedio, peor caso
• Generalmente es importante determinar los valores frontera de un
algoritmo, y no para cada una de las entradas posibles, principalmente se
utilizan tres valores:
• El mejor caso de un algoritmo es aquella instancia que requiere menos
recursos para ser resuelto.
• El tiempo del caso promedio representa el tiempo aproximado para un
ejemplar “típico”. Se calcula la media del tiempo para todos los
posibles ejemplares de tamaño n, asumiendo distribución uniforme.
• El peor caso de un algoritmo es aquel ejemplar que exige más recursos
para ser resuelto. El peor caso puede exigir mucho más tiempo que un
ejemplar “típico”.
2.3.8 Compromiso espacio-tiempo
• El compromiso espacio-tiempo es una situación en la que la memoria
puede reducirse a costa de la ejecución más lenta de los programas, o
viceversa, el tiempo de ejecución puede reducirse a costa de incrementar
el uso de memoria.
• La situación más común es un algoritmo
que utiliza una tabla de búsqueda: una
implementación puede incluir la tabla
completa, lo que reduce el tiempo de
ejecución, pero incrementa la cantidad de
memoria necesitada, o puede calcular entradas de la tabla a medida que se
necesiten, incrementando el tiempo de ejecución, pero reduciendo los
requisitos de memoria.
2.3.9 Clases de complejidad: P, NP, NP
completos
• Si se mide cuánto tiempo tarda un algoritmo en resolver un problema con
entradas cada vez más grandes, como ordenar una lista de 10, 20, 30
elementos, etc., se puede dibujar una gráfica con estos resultados y así
obtener su función de complejidad.
• La clase de complejidad P se compone de aquellos algoritmos cuya
función de complejidad está acotada por algún polinomio o, dicho de
otro modo, está compuesta por aquellos algoritmos que resuelven
problemas en tiempo polinomial en una Máquina de Turing
determinística.
2.3.9 Clases de complejidad: P, NP, NP
completos
• La clase de complejidad NP es el conjunto de problemas solubles en
tiempo polinomial no determinístico. O, de forma equivalente, aquellos
problemas cuya solución puede ser comprobada en tiempo polinomial
en una Máquina de Turing deterministica.
• La clase de complejidad NP-completa es el conjunto de problemas que
son los problemas más difíciles dentro del conjunto NP, en el sentido
de que son los que tienen menos posibilidades de encontrarse en el
conjunto P. Si se encuentra una forma de resolver un problema NP-
completo rápidamente, entonces ese mismo algoritmo puede resolver
todos los problemas NP rápidamente.
2.3.9 Clases de complejidad: P, NP, NP
completos
• Una de las preguntas abiertas más importantes en la actualidad es
descubrir si estas clases son diferentes o no ¿P=NP?. El Clay Mathematics
Institute ofrece un millón de dólares a quien sea capaz de responder a esa
pregunta. [Link]
Princeton CS building west wall
2.3.10 Métodos para encontrar soluciones
aproximadas a problemas no factibles
• Actualmente, todos los algoritmos conocidos para problemas no factibles (NP-
completos), utilizan tiempo exponencial con respecto al tamaño de la entrada.
• No se sabe si hay algoritmos más rápidos (o no), por lo cual, para resolver un
problema NP-completo de tamaño arbitrario se utiliza alguno de los siguientes
enfoques:
• Aproximación: un algoritmo que rápidamente
encuentra una solución no necesariamente
óptima, pero dentro de un cierto rango de
error. En algunos casos, encontrar una buena
aproximación es suficiente para resolver el
problema, pero no todos los problemas NP-completos tienen algoritmos de
aproximación.
2.3.10 Métodos para encontrar soluciones
aproximadas a problemas no factibles
• Probabilístico: un algoritmo probabilístico utiliza
aleatoriedad para obtener en promedio una buena
solución al problema planteado con una pequeña
probabilidad de fallar, para una distribución de los
datos de entrada dada.
• Restricciones: restringiendo la estructura de las entradas se pueden
encontrar algoritmos más rápidos.
• Casos particulares: puede ocurrir que se reconozcan casos particulares del
problema para los cuales existen soluciones rápidas.
2.3.10 Métodos para encontrar soluciones
aproximadas a problemas no factibles
• Algoritmo genético: algoritmos que mejoran las posibles soluciones hasta
encontrar una que posiblemente esté cerca del óptimo. Tampoco existe forma
de garantizar la calidad de la respuesta.
• Heurísticas: un algoritmo que trabaja razonablemente bien en muchos casos.
En general son rápidos, pero no existe medida de la calidad de la respuesta.
• ¿Buscar otro modelo de cómputo? En algunos
casos, un modelo de cómputo diferente al de las
Máquinas de Turing puede resultar una buena
opción. Actualmente se realiza investigación en
modelos alternativos como el cómputo con ADN
o el cómputo cuántico.
2.4 Análisis de algoritmos
• Es la rama de la teoría computacional que se encarga de proveer
estimaciones teóricas para los recursos que necesita un algoritmo para
resolver un problema.
• Estas estimaciones proporcionan guías para una búsqueda razonable de
algoritmos eficientes.
• Uno de los más reconocidos expertos de esta área
es Donald Knuth, su libro “the art of computer
programming” es una de las más respetadas
referencias en el campo de las ciencias de la
computación.
[Link]
2.4.1 Algoritmos iterativos y recursivos
• Los algoritmos iterativos son aquellos que hacen uso de ciclos while,
do-while, for, etc.
• Son algoritmos recursivos aquellos que, dentro de la definición de una
función, son llamados desde ella misma una y otra vez.
2.4.1 Algoritmos iterativos y recursivos
• Una definición es recursiva si se define en términos de sí misma. Para que
una definición recursiva sea válida, la referencia a sí misma debe ser
relativamente más sencilla que el caso considerado.
• Ejemplo: definición de los números naturales:
• El 0 es un número natural (dependiendo
del autor el primer natural es el 0 o el 1).
• n es un número natural si n-1 lo es.
2.4.1 Algoritmos iterativos y recursivos
• Un algoritmo recursivo requiere de 2 partes:
• 1. Caso base, trivial o de fin de recursión: Es un caso donde el
problema puede resolverse sin tener que hacer uso de una nueva
llamada a sí mismo. Evita la continuación
indefinida de las partes recursivas.
• 2. Caso puramente recursivo: Relaciona
el resultado del algoritmo con resultados
de casos más simples. Se hacen nuevas
llamadas a la función, pero están más
próximas al caso base.
2.4.2 Análisis de algoritmos recursivos:
ecuaciones de recurrencia
• Expresiones en las que el término general de la sucesión se escribe en
función de algunos términos anteriores, reciben el nombre de ecuación de
recurrencia, relación de recurrencia o ecuación en diferencias.
• Por ejemplo, los números de Fibonacci están definidos de la siguiente
manera:
f0 = 0
f1 = 1
fn = fn-1 + fn-2 para n>1
2.4.2 Análisis de algoritmos recursivos:
ecuaciones de recurrencia
• El objetivo de la resolución de la ecuación de recurrencia es encontrar una
forma de calcular los números de Fibonacci sin necesidad de depender de
valores anteriores.
• De la definición se obtiene la siguiente relación de recurrencia:
fn+2 - fn+1 - fn = 0
con los valores iniciales (casos base): f0=0 y f1=1.
El polinomio característico de esta relación es t 2 − t − 1 = 0, cuyas raíces
son: 1± 5
t=
2
2.4.2 Análisis de algoritmos recursivos:
ecuaciones de recurrencia
• De esta manera, la solución general de la sucesión de Fibonacci tendrá la
siguiente forma: n n
⎛1+ 5 ⎞ ⎛1− 5 ⎞
fn = c1 ⎜ ⎟ + c2⎜ ⎟
⎝ 2 ⎠ ⎝ 2 ⎠
• Tomando en cuenta las condiciones iniciales, se obtiene el siguiente
sistema de ecuaciones: c +c = 0
1 2
⎛1+ 5 ⎞ ⎛1− 5 ⎞
c1 ⎜ ⎟ + c2⎜ ⎟ = 1
⎝ 2 ⎠ ⎝ 2 ⎠
• Con solución: c1 =
1
;c2 = −
1
5 5
• Por lo tanto, cada número de la serie de Fibonacci puede obtenerse con
ayuda de la función: 1 ⎛ ⎛ 1+ 5 ⎞
n
⎛ 1− 5 ⎞
⎞
n
fn = ⎜⎜ ⎟ −⎜ ⎟ ⎟⎟
5 ⎜⎝ ⎝ 2 ⎠ ⎝ 2 ⎠ ⎠
2.4.3 Estimación de costos
• La estimación de costos de una actividad es una evaluación cuantitativa de
los costos probables de los recursos necesarios para llevarla a cabo.
• En el caso de los algoritmos, los recursos sobre los que se realiza la
estimación son tiempo de ejecución y espacio de almacenamiento.
2.4.4 Predicción
• La estimación de costos sirve para predecir el comportamiento de diversas
situaciones y procesos de interés:
• Si se logra determinar la complejidad
temporal y/o espacial de un algoritmo,
entonces se puede predecir de forma
confiable el tiempo de ejecución y el
espacio que requiere el algoritmo para
diferentes instancias sin tener que
ejecutar el cómputo correspondiente.
2.4.5 Criterios de medición
• Una vez dispongamos de un algoritmo que funciona correctamente, es
necesario definir criterios para medir su rendimiento o comportamiento.
Estos criterios se centran principalmente en su simplicidad y en el uso
eficiente de los recursos.
• A menudo se piensa que un algoritmo
sencillo no es muy eficiente.
Sin embargo, la sencillez es una característica
muy interesante a la hora de diseñar un
algoritmo, pues facilita su verificación, el
estudio de su eficiencia y su mantenimiento.
2.4.5 Criterios de medición
• Respecto al uso eficiente de los recursos, éste suele medirse en función de
dos parámetros: el espacio utilizado y el tiempo de ejecución. Se utilizan
principalmente dos estudios en cuanto a los recursos:
• Una medida teórica (a priori), que consiste en obtener una función que
acote el recurso que utiliza el algoritmo.
• Una medida real (a posteriori), consistente
en medir el recurso que utiliza el algoritmo
para unos valores de entrada dados en un
dispositivo físico.
2.4.6 Instrumentos de software para efectuar
mediciones
• En el software lo que se mide son atributos propios del mismo, se descompone
un atributo general en otros más simples de medir. Algunos atributos
comúnmente medidos, son:
• Funcionalidad.
• Número de errores durante un periodo determinado.
• Capacidad de respuesta frente a errores externos.
• Nivel de seguridad.
• Errores en la codificación o diseño del sistema.
• Tamaño de un producto informático (líneas de código, LOC)
2.4.7 Eficiencia
• La palabra eficiencia proviene del latín efficientia: es un término económico
que se refiere a la ausencia de recursos productivos ociosos, es decir, a que
se están usando de la mejor manera posible los factores en la producción
de bienes o servicios.
• En términos computacionales, la eficiencia es utilizada para describir
varias propiedades deseables en los algoritmos.
• La optimización es el proceso de mejorar un
código (grupo de algoritmos) lo más posible.
A veces optimizar espacio implica una
desmejora en la velocidad, o viceversa.
2.5 Estrategias para la construcción de
algoritmos
• Como se ha explicado en los temas anteriores,
dentro del universo de problemas existen
unos que son computables y otros no
computables.
• A través de los algoritmos se pueden
implementar diferentes formas de solución
para los problemas computables.
2.5.1 Selección de métodos basados en
criterios de eficiencia
• Cuando se analiza la eficiencia de un algoritmo son posibles distintos
enfoques: medir el tiempo que un programa tarda en ejecutarse en una
computadora particular, medir la cantidad de memoria que utiliza o
utilizar un análisis asintótico.
• Sea cual sea la medición tomada, los resultados deben servir como guía
para seleccionar un algoritmo para resolver un problema.
• Esta elección depende principalmente de la sencillez del
algoritmo y la eficiencia del mismo: es común que entre
más sencillo sea el algoritmo, su complejidad sea mayor
y viceversa.
2.5.2 Tipos de algoritmos, Ávidos
• Un algoritmo ávido (también conocido como voraz o greedy) es aquel que,
para resolver un determinado problema, elige la opción óptima en cada
paso local con la esperanza de llegar a una solución general óptima.
• Este esquema algorítmico es el que menos dificultades plantea a la hora de
diseñar y comprobar su funcionamiento. Normalmente se aplica a los
problemas de optimización.
• Ejemplo de este tipo de algoritmos es el algoritmo de Dijkstra para
encontrar el camino más corto entre dos nodos de una gráfica.
2.5.2 Tipos de algoritmos, “Divide y
vencerás”
• El término divide y vencerás (divide and conquer) hace referencia a uno de
los más importantes paradigmas de diseño algorítmico.
• Está basado en la resolución recursiva de un problema dividiéndolo en
dos o más subproblemas de igual tipo o similar. El proceso continúa hasta
que éstos llegan a ser lo suficientemente sencillos
como para que se resuelvan directamente.
• Al final, las soluciones a cada uno de los subproblemas
se combinan para dar una solución al problema original.
• Ejemplos de este paradigma, son el método de bisección para obtener
raíces de una función y algoritmos óptimos de ordenamiento basados en
comparaciones como el mergesort.
2.5.2 Tipos de algoritmos, Backtrack
• En su forma básica, la idea de backtracking se asemeja a un recorrido en
profundidad dentro de una gráfica dirigida tipo árbol.
• El objetivo del recorrido es encontrar soluciones para algún problema; esto se
consigue construyendo soluciones parciales a medida que progresa el recorrido;
estas soluciones parciales limitan las
regiones en las que se puede encontrar una
solución completa.
• El recorrido tiene éxito si, procediendo de esta forma, se puede definir por
completo una solución.
• Por otra parte, el recorrido no tiene éxito si en alguna etapa la solución parcial
construida hasta el momento no se puede completar; en tal caso, el recorrido vuelve
atrás (backtrack) exactamente igual que en el recorrido en profundidad, eliminando
sobre la marcha los elementos que se hubieran añadido.
2.5.2 Tipos de algoritmos, Búsqueda local
• Los algoritmos de búsqueda local parten de una solución inicial, y,
aplicándole operadores de variación, la van alterando; si la solución
alterada es mejor que la original, se acepta, si no lo es, se vuelve a la
inicial. El procedimiento se repite hasta que no se consigue mejora en la
solución.
• Como se trata de algoritmos de búsqueda local, sólo van a encontrar el
máximo local más cercano al punto de inicio.
2.5.2 Tipos de algoritmos,
Por transformaciones
• Las transformaciones locales son una estrategia para resolver problemas
de optimización sobre espacios de búsqueda exponenciales. La idea básica
es:
• Crear una solución aleatoria,
generalmente mediante heurística.
• Aplicarle una transformación de
un conjunto de transformaciones.
• Elegir la mejor.
• Repetir lo anterior hasta que ninguna transformación mejore.
2.5.2 Tipos de algoritmos, Probabilístico
• Un algoritmo probabilístico es un algoritmo que basa su resultado en la
toma de algunas decisiones al azar, de tal forma que, en promedio, obtiene
una buena solución al problema planteado para cualquier distribución de
los datos de entrada.
• Es decir, al contrario que un algoritmo
determinista, a partir de unos mismos
datos se pueden obtener distintas
soluciones y, en algunos casos,
soluciones erróneas.
2.6 Definición, ejemplos, diseño, implantación,
corrección, eficiencia, complejidad de algoritmos
• Ejemplo:
• Diseñar un algoritmo que obtenga el máximo y el mínimo de una lista.
• [2, 5, 6, 4, 1, 8, 4, 9, 7]
• min = 1
• max = 9
2.6 Definición, ejemplos, diseño, implantación,
corrección, eficiencia, complejidad de algoritmos
• Algoritmo básico:
• min_max(lista):
tam <- long(lista)
min <- max <- lista1
desde i <- 2 hasta tam
if min > listai
min <- listai
if max < listai
max <- listai
2.6 Definición, ejemplos, diseño, implantación,
corrección, eficiencia, complejidad de algoritmos
• Para determinar la función de complejidad del algoritmo anterior, sólo es
necesario contar el número de comparaciones que realiza (es un algoritmo
de búsqueda de valores).
• Para encontrar el mínimo realiza n-1
comparaciones y las mismas para
encontrar el máximo. Por tanto, para
determinar ambos valores de la lista
requiere 2n-2 comparaciones totales.
• El algoritmo es entonces O(n).
2.6 Definición, ejemplos, diseño, implantación,
corrección, eficiencia, complejidad de algoritmos
• ¿Se puede determinar el mínimo y máximo de la lista con menos
comparaciones? Sí:
• El algoritmo mostrado en la imagen realiza 3 * ceil(n/2) comparaciones.
Aún es O(n).
2.6 Definición, ejemplos, diseño, implantación,
corrección, eficiencia, complejidad de algoritmos
• ¿Se puede determinar el mínimo y máximo de la lista con menos
comparaciones? Parece que sí: divide y vencerás.
• Dividimos en listas más pequeñas hasta tener listas de no más de 2
elementos.
• Se obtiene el min/max de cada sublista y se compara con los de la
sublista más cercana, se obtiene el min/max de una lista de 4.
• Se continúa el proceso hasta obtener el min/max de toda la lista.
• Parece ser O(log n)
2.6 Definición, ejemplos, diseño, implantación,
corrección, eficiencia, complejidad de algoritmos
• Tarea (programa 3): Implementar el algoritmo básico y mejorado para
determinar mínimo y máximo de una lista.
• Obtener una gráfica del número de comparaciones que realiza cada
algoritmo, como función del tamaño de la entrada.
• Puntos extra: Implementar el algoritmo divide y vencerás, obtener
también su gráfica y verificar si se comporta como O(log n)
2.7 Análisis y diseño avanzado de
algoritmos
• Los algoritmos son la parte más fundamental de todos los aspectos de la ciencia
e ingeniería de la computación.
• Un buen diseño algoritmos y estructuras de datos es esencial para el buen
desempeño de un sistema de información, un conocimiento profundo de las
propiedades teóricas de los algoritmos es esencial para cualquier científico de la
computación.
• La investigación teórica de los algoritmos conduce a
una comprensión más profunda de la estructura de los
problemas; el conocimiento de una gran variedad de
tipos de algoritmos permite observar un nuevo problema
desde diferentes ángulos.