Post on 09-Jul-2015
PARCIAL
POR
JUAN ESTEBAN PUERTA CANO
DOCENTE
RICARDO BOTETRO
ASIGNATURA
ANALISIS DE ALGORITMOS
I N T I T U C I Ó N U N I V E R S I T A R I A
T E C N O L O G I C O D E A N T I O Q U I A
F A C U L T A D D E I N G E N I A R I A
M E D E L L Í N
2 0 1 3 - I I
1R:
PREORDEN: 89-67-42-10-2-35-44-78-91-90-99
INORDEN: 2-10-35-42-44-67-78-89-90-91-99
POSTORDEN: 10-2-35-42-44-67-78-91-90-99-89
2R: HAMILTONIANO
Camino que visita todos los vértices sólo una vez.
0-2-3-1-4
EULERIANO
Camino que visita todas las aristas del grafo sólo una vez.
02-1-4-2-3-1-0
3R: Los pasos son 3, división, ordenamiento y combinación.
División: en primer lugar ha de plantearse el problema de forma que pueda ser descompuesto
en K subproblemas del mismo tipo, pero de menor tamaño, es decir, si el tamaño de la entrada
es N, hemos de conseguir dividir el problema en K subproblemas donde (1<=K<=N), cada uno
con una entrada de tamaño N/k y donde (0<=N/K<N).
Ordenamiento: En segundo lugar han de resolverse independientemente todos los
subproblemas, bien directamente si son elementales o bien de forma recursiva. El hecho de
que el tamaño de los subproblemas sea estrictamente menor que el tamaño original del
problema nos garantiza la convergencia hacia los casos elementales, también denominados
casos bases.
Combinación: Por último, combinar las soluciones obtenidas en el paso anterior para construir
la solución del problema original.
4R:
Topología entre procesadores X
Tipo de los módulos de memoria (compartida ó distribuida)
X
Cantidad de procesadores X
5R: Desventajas: puede llegar a utilizar grandes cantidades de memoria en un instante, pues
implementa una pila cuyo tamaño crece linealmente con el número de recursiones necesarias
en el algoritmo. Si lo datos en cada paso son muy grandes podemos requerir grandes
cantidades de memoria.
Ventajas: Algunos problemas son esencialmente recursivos, por lo cual su implementación se
facilita mediante un algoritmo de naturaleza recursiva, sin tener que cambiarlo a un método
iterativo.
6R: Megasort.
7R:
Ordenamiento por método del montículo (heap sort)
O(n log n)
Ordenamiento por inserción directa O(n)
Ordenamiento rápido o Quick sort O(n log n)
Problema del viajero en una solución heurística
O(n^2)
Búsqueda secuencial en un vector O(n)
Llenado de una matriz de m filas y n columnas, donde m y n son números enteros
O(n^3)
Recorrido de una lista ligada O(n)
Fibonacci recursivo O(2^n)
Fibonacci no recursivo O(n)
Busqueda Binaria en un vector O(log n)
8R:
9R:
MCD (12,8)=2
MCD (15,6)=3
Se divide le número mayor por el número menor hasta dar una división exacta, si no da una
división exacta se divide el divisor por el residuo.
10.1R: Inserción directa.
10.2 R: Megasort.