Técnicas de Demostración Algorítmica

TÉCNICAS DE DEMOSTRACIÓN ALGORÍTMICA
Entre las técnicas de demostración algorítmica están los siguientes:
ALGORITMOS VORACES
En ciencias de la computación, un algoritmo voraz (también conocido como ávido, devorador o greedy) es
una tecnica de búsqueda por la cual se sigue una heurística consistente en elegir 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.
DIVIDE Y VENCERAS
El diseño “divide y vencerás” es una técnica que se aplica a veces a algoritmos que reducen cada problema a
un único subproblema, como la búsqueda binaria para encontrar un elemento en una lista ordenada (o su
equivalente en computación numérica, el algoritmo de bisección para búsqueda de raíces).
Estos algoritmos usan una serie de recursiones, donde cada algoritmo que usa recursión o bucles puede ser
tomado como un algoritmo de “divide y vencerás”.
TECNICAS DE ORDENAMIENTO Y BUSQUEDA
 DE ORDENACIÓN
Existen diferentes algoritmos de ordenación elementales o básicos cuyos detalles de implementación se pueden

encontrar en diferentes libros de algoritmos. Los algoritmos presentan diferencias entre ellos que los convierten
en más o menos eficientes y prácticos según sea la rapidez y eficiencia demostrada por cada uno de ellos.
Los algoritmos básicos de ordenación más simples y clásicos se muestran en la siguiente tabla:
NOMBRE COMPLEJIDAD ESTABILIDAD MEMORIA ADICIONAL

Ordenamiento Burbuja (Bubblesort) O(n2) Estable No
Ordenamiento por Selección O(n2) No Estable No
Ordenamiento por Inserción O(n2) Estable No
Ordenamiento Rápido (Quicksort) O(n * log2(n)) No Estable No
El método de burbuja, es el más sencillo aunque a la par también es el más ineficiente; por esta causa no se
recomienda su uso, pero sí se debe conocer su técnica.
 DE BÚSQUEDA
BÚSQUEDA SECUENCIAL
QUICKSORT
El ordenamiento rápido (quicksort en inglés) es un algoritmo de ordenación creado por el científico británico en

computación C. A. R. Hoare.
El algoritmo trabaja de la siguiente forma:
 Elegir un elemento del arreglo de elementos a ordenar, al que se llama pivote.

 Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos
los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a
su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el
pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
 La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y
otra por los elementos a su derecha.
 Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un
elemento. Una vez terminado este proceso todos los elementos estarán ordenados.
Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.
 En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual
tamaño. En este caso, el orden de complejidad del algoritmo es O(n·log n).
 En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es
entonces de O(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente
ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero principalmente depende del pivote,
si por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del array, y el array
que le pasamos está ordenado, siempre va a generar a su izquierda un array vacío, lo que es ineficiente.
 En el caso promedio, el orden es O(n·log n).

No es extraño, pues, que la mayoría de optimizaciones que se aplican al algoritmo se centren en la elección
del pivote.
TÉCNICAS DE REPOSICIONAMIENTO
Una idea preliminar para ubicar el pivote, en su posición final sería contar la cantidad de elementos menores
que él, y colocarlo un lugar más arriba, moviendo luego todos esos elementos menores que él a su izquierda,
para que pueda aplicarse la recursividad.
Existe, no obstante, un procedimiento mucho más efectivo. Se utilizan dos índices: i, al que llamaremos índice
izquierdo, y j, al que llamaremos índice derecho. El algoritmo es el siguiente:
 Recorrer la lista simultáneamente con i y j: por la izquierda con i (desde el primer elemento), y por la
derecha con j (desde el último elemento).
 Cuando lista[i] sea mayor que el pivote y lista[j] sea menor, se intercambian los elementos en esas
posiciones.
 Repetir esto hasta que se crucen los índices.
El punto en que se cruzan los índices es la posición adecuada para colocar el pivote, porque sabemos que a un
lado los elementos son todos menores y al otro son todos mayores (o habrían sido intercambiados).
Ejemplo
En el siguiente ejemplo se marcan el pivote y los índices i y j con las letras p, i y j respectivamente.
Se comienza con la lista completa. El elemento pivote será el 4:
5-3-7-6-2-1-4
Comparamos con el 5 por la izquierda y el 1 por la derecha.
5-3-7-6-2-1-4
i j p
5 es mayor que 4 y 1 es menor. Se intercambia:

1-3-7-6-2-5-4
i j p
Avanzamos por la izquierda y la derecha:
1-3-7-6-2-5-4
i j p
3 es menor que 4: avanzamos por la izquierda. 2 es menor que 4: nos mantenemos ahí.
1-3-7-6-2-5-4
i j p
7 es mayor que 4 y 2 es menor: intercambiamos.
1-3-2-6-7-5-4
i j p
Avanzamos por ambos lados:
1-3-2-6-7-5-4
iyj p
En este momento termina el ciclo principal, porque los índices se cruzaron. Ahora intercambiamos lista[i] con
lista[p] (pasos 16-18):
1-3-2-4-7-5-6
Aplicamos recursivamente a la sublista de la izquierda (índices 0 - 2). Tenemos lo siguiente:
1-3-2
1 es menor que 2: avanzamos por la izquierda. 3 es mayor: avanzamos por la derecha. Como se intercambiaron
los índices termina el ciclo. Se intercambia lista[i] con lista[p]:
1-2-3
El mismo procedimiento se aplicará a la otra sublista. Al finalizar y unir todas las sublistas queda la lista inicial
ordenada en forma ascendente.
1-2-3-4-5-6-7
MERGESORT ORDENAMIENTO POR INTERCALACIÓN

El algoritmo, utiliza la técnica de dividir para vencer de la siguiente manera. Para ordenar un arreglo este se
divide en dos mitades, cada mitad es ordenada y ambas mitades ya ordenadas se intercalan para dar la
solución.
proc Mergesort (ini, f in)
comienza
si ini < f in entonces
mitad ← (ini+f in) 2
Mergesort(ini, mitad) Mergesort(mitad + 1, f in) Intercala(ini, mitad, f in) is termina.
El algoritmo de ordenamiento por intercalamiento presenta el problema de exceso de llamadas recursivas.

Técnicas de Demostración Algorítmica

Cargado por

Copyright:

Formatos disponibles

Técnicas de Demostración Algorítmica

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Técnicas de Demostración Algorítmica

Cargado por

Copyright:

Formatos disponibles

TÉCNICAS DE DEMOSTRACIÓN ALGORÍTMICA

Entre las técnicas de demostración algorítmica están los siguientes:

TECNICAS DE ORDENAMIENTO Y BUSQUEDA

Existen diferentes algoritmos de ordenación elementales o básicos cuyos detalles de implementación se pueden

NOMBRE COMPLEJIDAD ESTABILIDAD MEMORIA ADICIONAL

Ordenamiento por Selección O(n2) No Estable No

Ordenamiento por Inserción O(n2) Estable No

Ordenamiento Rápido (Quicksort) O(n * log2(n)) No Estable No

El ordenamiento rápido (quicksort en inglés) es un algoritmo de ordenación creado por el científico británico en

El algoritmo trabaja de la siguiente forma:

 Elegir un elemento del arreglo de elementos a ordenar, al que se llama pivote.

 En el caso promedio, el orden es O(n·log n).

En el siguiente ejemplo se marcan el pivote y los índices i y j con las letras p, i y j respectivamente.

Se comienza con la lista completa. El elemento pivote será el 4:

Comparamos con el 5 por la izquierda y el 1 por la derecha.

5 es mayor que 4 y 1 es menor. Se intercambia:

Avanzamos por la izquierda y la derecha:

7 es mayor que 4 y 2 es menor: intercambiamos.

Avanzamos por ambos lados:

Aplicamos recursivamente a la sublista de la izquierda (índices 0 - 2). Tenemos lo siguiente:

MERGESORT ORDENAMIENTO POR INTERCALACIÓN

El algoritmo de ordenamiento por intercalamiento presenta el problema de exceso de llamadas recursivas.

También podría gustarte