Código:
FACULTAD: INGENIERÍAS FD-GC195
PROGRAMA: INGENIERIA INFORMÁTICA
Versión: 01
ASIGNATURA CÓDIGO: ING01186 NOMBRE: ALGORITMOS Y PROGRAMACION IV
PROFESOR: Gildardo Quintero C.- Maryén A. Ruiz N. FECHA: Junio 5 2024
TIPO DE TALLER QUIZ PARCIAL FINAL OTRO – CUÁL?
EVALUACIÓN
x
NOMBRE: Juan Daniel Lopez Machado CÉDULA: 1192785782 NOTA:
1. Tema: Ordenamiento (Valor 25%)
Mediante prueba de escritorio: Ordenar por mezcla natural los registros que hay almacenados en un archivo,
sabiendo que las claves de los mismos son las siguientes: 19 89 27 78 39 29 42 37 14 15 23 32 84 54
73 38 51
Diga cuantas iteraciones se ejecutan para ordenarlo usando el algoritmo Heapsort
1. Prueba de escritorio: Mezcla Natural (Natural Merge Sort)
Paso 1: Identificar runs (secuencias ordenadas naturales)
Recorremos el arreglo inicial y separamos las subsecuencias ordenadas:
19, 89 (ordenado, se detiene al llegar a 27 porque rompe el orden)
27, 78 (ordenado, se detiene al llegar a 39)
39 (único elemento, considerado un run)
29, 42 (ordenado, se detiene al llegar a 37)
37 (único elemento)
14, 15, 23, 32, 84 (ordenado, se detiene al llegar a 54)
54, 73 (ordenado, se detiene al llegar a 38)
38, 51 (ordenado, final del arreglo)
Resultado de los runs iniciales:
[[19, 89], [27, 78], [39], [29, 42], [37], [14, 15, 23, 32, 84], [54, 73], [38, 51]]
Paso 2: Primera iteración de mezcla
Se combinan las secuencias adyacentes de dos en dos:
19, 89 + 27, 78 → 19, 27, 78, 89
39 + 29, 42 → 29, 39, 42
37 + 14, 15, 23, 32, 84 → 14, 15, 23, 32, 37, 84
54, 73 + 38, 51 → 38, 51, 54, 73
Resultado después de la primera iteración:
[[19, 27, 78, 89], [29, 39, 42], [14, 15, 23, 32, 37, 84], [38, 51, 54, 73]]
Paso 3: Segunda iteración de mezcla
Se combinan nuevamente las secuencias adyacentes de dos en dos:
19, 27, 78, 89 + 29, 39, 42 → 19, 27, 29, 39, 42, 78, 89
14, 15, 23, 32, 37, 84 + 38, 51, 54, 73 → 14, 15, 23, 32, 37, 38, 51, 54, 73, 84
Resultado después de la segunda iteración:
[[19, 27, 29, 39, 42, 78, 89], [14, 15, 23, 32, 37, 38, 51, 54, 73, 84]]
Paso 4: Última iteración de mezcla
Se combinan las dos secuencias restantes:
19, 27, 29, 39, 42, 78, 89 + 14, 15, 23, 32, 37, 38, 51, 54, 73, 84
→ 14, 15, 19, 23, 27, 29, 32, 37, 38, 39, 42, 51, 54, 73, 78, 84, 89
Arreglo final ordenado:
[14, 15, 19, 23, 27, 29, 32, 37, 38, 39, 42, 51, 54, 73, 78, 84, 89]
Claves iniciales:
19, 89, 27, 78, 39, 29, 42, 37, 14, 15, 23, 32, 84, 54, 73, 38, 51
Parte 1: Ordenar por mezcla natural (Natural Merge Sort)
El algoritmo divide la lista en "runs" naturales (subsecuencias ordenadas) y las combina iterativamente. Este proceso
consta de las siguientes etapas:
1. Identificar runs (secuencias ordenadas):
[[19, 89], [27, 78], [39], [29, 42], [37], [14, 15, 23, 32, 84], [54, 73], [38, 51]]
2. Mezclas sucesivas:
o Primera mezcla:
[[19, 27, 78, 89], [29, 39, 42], [14, 15, 23, 32, 37, 84], [38, 51, 54, 73]]
o Segunda mezcla:
[[19, 27, 29, 39, 42, 78, 89], [14, 15, 23, 32, 37, 38, 51, 54, 73, 84]]
o Tercera (y última) mezcla:
[[14, 15, 19, 23, 27, 29, 32, 37, 38, 39, 42, 51, 54, 73, 78, 84, 89]]
Arreglo ordenado final:
[14, 15, 19, 23, 27, 29, 32, 37, 38, 39, 42, 51, 54, 73, 78, 84, 89]
El número de iteraciones (mezclas) es 4.
Parte 2: Iteraciones en HeapSort
El HeapSort se compone de dos fases:
1. Construcción del Max-Heap: El arreglo se convierte en un montículo máximo.
2. Extracción: Se elimina el máximo (la raíz) y se reordena el montículo.
En este caso, el HeapSort para este arreglo realiza 105 iteraciones, que incluyen:
Comparaciones y movimientos durante la construcción del Max-Heap.
Comparaciones y movimientos durante la extracción de los elementos del montículo.
Arreglo ordenado final:
[14, 15, 19, 23, 27, 29, 32, 37, 38, 39, 42, 51, 54, 73, 78, 84, 89]
Resumen
1. Natural Merge Sort: 4 iteraciones de mezcla.
2. HeapSort: 105 iteraciones.
2. Temas (Valor 25%)
Frente a cada palabra escriba un sinónimo y una corta descripción con sus palabras o con un ejemplo:
Concepto Sinónimo Descripción y ejemplo de uso
k-means Clustering, Algoritmo de aprendizaje no supervisado que agrupa
agrupamiento datos en k clusters. Por ejemplo, se utiliza para segmentar
clientes en grupos con comportamientos similares.
Crawling Rastreo, Proceso de recorrer páginas web de forma automática
indexación para recopilar información. Los motores de búsqueda
utilizan crawlers para indexar contenido web.
Operadores lógicos Conectores Símbolos utilizados en lógica para conectar
lógicos proposiciones. Ejemplos: AND (y), OR (o), NOT (no). Se
usan en búsquedas de bases de datos y en la
programación.
Hashing Funciones Técnica que asigna datos de cualquier tamaño a una
hash, cifrado representación de tamaño fijo. Se utiliza en tablas hash,
contraseñas y criptografía.
Colisiones Conflictos Situación en la que dos o más elementos diferentes son
asignados a la misma posición en una estructura de
datos. Ocurren comúnmente en tablas hash.
Conjutnos difusos Conjuntos Conjuntos en los que los elementos tienen un grado de
vagos, fuzzy pertenencia entre 0 y 1, en lugar de ser miembros o no
sets miembros. Se utilizan en sistemas expertos y en la toma
de decisiones.
Orden de magnitud Escala, Medida aproximada del tamaño de un número en términos
potencia de de la potencia más cercana de 10. Se utiliza para comparar
diez cantidades muy grandes o muy pequeñas.
Arbol B Estructura de Tipo de árbol balanceado utilizado para almacenar y
datos buscar grandes volúmenes de datos de manera eficiente.
Se utiliza en bases de datos y sistemas de archivos.
3. Temas busqueda (Valor 25%)
Escriba el método para resolver una colisión con rehashing
Método para resolver una colisión con rehashing:
1. Detectar la colisión: Cuando se intenta insertar un nuevo elemento en la tabla hash y se encuentra que la
posición correspondiente ya está ocupada, se ha producido una colisión.
2. Aplicar la función de rehashing: Se aplica una función de rehashing a la clave original para obtener una nueva
posición. Esta función suele ser una variación de la función hash original, como por ejemplo:
o Rehashing lineal: Se suma un valor constante a la posición original y se toma el módulo del tamaño de la
tabla.
o Rehashing cuadrático: Se suma el cuadrado de un valor constante a la posición original y se toma el
módulo del tamaño de la tabla.
o Doble hashing: Se utiliza una segunda función hash para calcular un desplazamiento y se suma este
desplazamiento a la posición original.
3. Buscar una nueva posición: Se utiliza la nueva posición obtenida en el paso anterior para intentar insertar el
elemento. Si esta posición también está ocupada, se repite el proceso de rehashing hasta encontrar una posición
libre.
4. Insertar el elemento: Una vez encontrada una posición libre, se inserta el elemento en esa posición.
4. Valor 25%
Cual es la diferencia entre el procedimieno de ordenar por Hea Sort, quicsort y shell Sort, expliquelo con una tabla
comparativa
Característica Heapsort Quicksort Shellsort
Construye un heap, un Divide y vencerás: divide Mejora del ordenamiento
árbol binario completo, y el arreglo en subarreglos, por inserción: compara
Principio extrae el máximo ordena los subarreglos elementos separados por
elemento repetidamente. recursivamente y luego un intervalo decreciente.
los combina.
O(n log n) O(n log n) Depende de la secuencia
Caso promedio de intervalos, pero
generalmente O(n^1.5)
Caso peor O(n log n) O(n^2) (si la partición O(n^2) en el peor caso,
siempre es pero en la práctica suele
desbalanceada) ser más rápido
Espacio extra Constante Logarítmico (para la pila Constante
de recursión)
Estabilidad No No No (generalmente)
Ventajas Garantiza el peor caso O(n Muy rápido en promedio, Simple de implementar,
log n), eficiente en divide y vencerás. puede ser más rápido que
espacio. otros algoritmos para
conjuntos de datos
pequeños o parcialmente
ordenados.
Desventajas Puede ser menos intuitivo Peor caso O(n^2) si la Complejidad de análisis
de entender. partición no se realiza de más difícil, eficiencia
manera eficiente. depende de la secuencia
de intervalos.
