Please enable JavaScript.

Coggle requires JavaScript to display documents.

1_1krqTjChJQa0U7FiOUdfZQ ALGORITMOS CLASICOS, Referencias, Apps, E.N. et…

- - - - Merge Sort 0(nlog(n))
        
        Características
        
        Rápido
        
        Ordenamiento estable
        
        Recursivo
        
        En el peor de los casos es (n^2)
        
        Técnica Divide y venceras
        
        Consiste en dividir un arreglo en dos subarreglos de tamaño similar (lo más posible) mediante llamadas recursivas, para, posteriormente mezclar las dos partes
        
        Desarrollado por Jhon Von Neumman en 1945
      - Binary Tree Sort O(nlog(n))
        
        Ordena sus elementos haciendo uso de un árbol de busqueda
        
        Caracteristicas
        
        Buen rendimiento
        
        Es estable
        
        Ordena lista tal cual las recibe
      - Bucket Sort O(n log n)
        
        Caracteristicas
        
        Estable
        
        Distribución unifrome de datos
        
        En el peor de los casos en (n^2)
        
        Los elementos del arreglo principal se guardan en casilleros, los cuales posteriormente se ordenan con algún método de ordenamiento y se devuelven concatenando cada casillero ya ordenado.
        
        Desarrollado por Herman Hollerit
      - Counting Sort O(n)
        
        Características
        
        Solo ordena números enteros
        
        Estabilidad
        
        No hace comparaciones
        
        Desarrollado por Harold S. Sewards en 1954
        
        Toma el elemento más grande del arreglo para crear subarreglo con ese rango y en base a ello contar los números que aparecen en el arreglo principal.
      - Radix Sort O(n)
        
        Caracteristicas
        
        Estabilidad
        
        No hace comparaciones
        
        Tiempo de ejecución lineal
        
        Puede ordenar cadenas
        
        Desarrolladlo por Harold S. Seward en 1954
        
        Consiste en agrupar una serie de números dependiendo del número que tengan en las unidades que se traten.
      - Buble Sort O(n^2)
        
        Características
        
        No es tan eficiente
        
        Estable
        
        También conocido como el método de intercambio directo
        
        Tiempo de ejecución cuadrático
        
        No es recomendable para el desarrollo de software
        
        su nombre se deriva del hecho de que los valores más pequeños en el arreglo flotan o suben hacia la parte inicial y lo más grande se insertan en la parte final
      - Insertion Sort O(n^2)
        
        Consiste en ordenar los elementos del arreglo progresivamente, comenzando
        por los primeros y avanzando hasta ordenarlos todos
        
        Características
        
        Sencillo de comprender e implemenntar
        
        Tiempo de ejecución cuadrático
        
        Eficiente para listas cortas
        
        Estable
        
        En su mejor caso es lineal
    - - Quick Sort O(nlog(n))
        
        Características
        
        Recursivo
        
        Para el peor caso es casi improbable que suceda
        
        Rápido
        
        No estable
        
        Divide n elementos del arreglo en dos subarreglos, izquiero y derecho, y un pivote
        
        Creado por el cientifico britanico Charles Antony Richard Hoale en 1960
      - Heap Sort (n log n)
        
        Consiste en almacenar todos los elementos del arreglo a ordenar en un montículo (heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado.
        
        Su nombre se debe a su autor J. W. J. Williams quien lo bautizó así en 1964
        
        Características
        
        No recursivo
        
        No estable
        
        El más eficiente de los métodos de árboles
        
        “Para todo nodo del árbol se debe cumplir que
        su valor es mayor o igual al de cualquiera de sus hijos”
      - Shell Sort (n^3/2)
        
        Es una mejora del método de inserción directa, el cual elimina los saltos contiguos resultantes de las comparaciones por saltos de mayor tamaño
        
        Nombrado así en honor del ingeniero y matemático estadounidense Donald Shell que la propuso en 1959
        
        Características
        
        Los datos se almacenan en memoria principal
        
        Se basa en iteraciones y comparaciones
        
        Ideado para trabajar con Arrays y arrays de punteros
        
        Eficaz con array no tan grandes
        
        Ordena enteros y otro tipo de datos
        
        inestable
      - Selection Sort O(n^2)
        
        Consiste en encontrar el menor de todos los elementos del arreglo o vector e intercambiarlo con el que está en la primera posición. Luego el segundo mas pequeño, y así sucesivamente hasta ordenarlo todo.
        
        Características
        
        Eficiente para una entrada de datos pequeños
        
        Si sus datos tienen claves pequeñas pero
        área de datos grande, entonces la clasificación por selección puede ser la más rápida
        
        Fácil de comprender
- - - - Una secuencia de n elementos, donde cada elemento es un objeto
  - - - Repiten una fase de separación en tramos, otra de mezcla que da lugar a tramos ordenados y su acceso es únicamente secuencial
  - - - Características
        
        Es un método simple
        
        utiliza el esquema iterativo de separar secuencias de registros y su mezcla.
        
        Se opera con el archivo original y dos archivos auxiliares
    - - El método de fusión natural mejora el tiempo de ejecución de la mezcla directa al introducir
        una pequeña variación respecto a la longitud de las secuencias de registros.
      - Características
        
        las secuencias de registros tienen longitudes que son múltiplos de dos
        
        distribuye en todo momento secuencias
        ordenadas (tramos)
        
        mezcla secuencias ordenadas lo más largas posibles.
        
        El método de fusión natural funde tramos máximos en lugar de secuencias de tamaño fijo
        y predeterminado.
        
        Reduce e numero de pasadas, siendo más eficiente que la mezcla directa
        
        Se opera con el archivo original y dos archivos auxiliares
    - - Características
        
        Para aumenta su eficiencia aumenta más archivos auxiliares
        
        El proceso de mezcla se realiza en una sola fase, en lugar de dos (separación y fusión) a diferencia de los otros dos algoritmos mencionados
- - - - Proporciona la dirección lógica donde dos sistemas dispares determinan una ruta posible para comunicarse
        
        ¿Para qué?
        
        Los paquetes que viajan en internet tienen un origen y un destino
    - - Adaptables
        
        Dinámicos
        
        Desventajas
        
        Se implementan en los routers
        
        Se ejecutan en Tiempo Real
        
        Consumen recursos del CPU y memoria del Router
        
        Tipos
        
        Vector de Distancia
        
        Conocidos también como
        
        Bellman Ford
        
        Ford Fullkerson
        
        Caracteristicas
        
        Cada router mantiene una tabla de enrutamiento, en la cual existe una entrada para cada nodo
        
        1 more item...
        
        Cada router conoce la distancia a sus vecinos directos
        
        Realizan interacciones con sus vecinos periódicamente para mantenerse actualizados
        
        Ventaja
        
        Cambian sus decisiones para reflejar cambio de topología y trafico
      - No adaptables
        
        Sus procedimientos son de Enrutamiento Estáticos
        
        Desventaja
        
        No responde ante situaciones cambiantes
        
        Saturación
        
        Exceso de trafico
        
        Tipos
        
        Inundación
        
        Características
        
        Cada paquete recibido por una línea de entrada es enviado por todas las líneas de salida
        
        Genera muchos paquetes duplicados si no se controla la duración de paquetes
        
        Robusto y rápido para alcanzar su destino
        
        Dijkstra
        
        Características
        
        Calcula la ruta de menos costo
        
        Es un algoritmo iterativo
        
        Sencilla y fácil de entender
- - - - Pueden ser
        
        Internos
        
        Se clasifican en
        
        Binario log(n)
        
        Consiste en dividir el intervalo de búsqueda en dos partes, comparando el elemento buscado con el que ocupa la posición central en el arreglo.
        
        Características
        
        Funciona exclusivamente con arreglos ordenados
        
        Mayor eficiencia que búsqueda sec.
        
        Método confiable
        
        La comparación mínima es 1
        
        Utiliza el método Divide y vencerás
        
        Por transfrmaciones de claves
        
        El método trabaja utilizando una función que convierte una clave dada en una dirección (índice) dentro del arreglo.
        
        Características
        
        Mayor velocidad de búsqueda
        
        No es necesario tener el arreglo ordenado
        
        El tiempo de búsqueda es independiente al numero de elementos
        
        Genera un índice que permite acceder directamente a la elemento según la clave
        
        Puede ser usado en
        
        Almacenar información de alumnos y hacer su búsqueda según su clave, también para empleados y su clave de seguro.
        
        Secuencial O(n)
        
        Consiste en revisar elemento tras elemento hasta encontrar el dato buscado
        
        Caracteristicas
        
        Busqueda Directa
        
        Se basa en uso de fuerza bruta
        
        Puede realizarse en arreglos desordenados
        
        Método confiable
        
        El numero de comparaciones es significativo si el arreglo es muy grande
        
        La cantidad de comparaciones va de 1 hasta n
        
        Arboles de búsqueda O(log n)
        
        Utilizado para localizar llaves concretas dentro de un conjunto. Esta esta basada en nodos donde cada nodo contiene una llave y dos subárboles, el izquierdo y el derecho (Nodos hijos)y estas deben ser menores que la llave (Nodo Padre)
        
        Caracteristicas
        
        Eficiente
        
        Dinámico
        
        A mayor numero de datos a tratar, más beneficios
        
        Pueden Clasificarse en:
        
        Arboles Mutlicamino de búsqueda
        
        Árboles Binarios de Búsqueda
        
        Se encuentran en la memoria principal
        
        Externos
        
        Se encuentran en memoria externa o secuandaria
        
        Búsqueda Secuencial
        
        Por bloques
        
        Conjunto de registros
        
        Previamente ordenado
        
        Por índices
        
        Recorre archivo de indices y compara las claves
        
        Se determina el bloque
        
        1 more item...
        
        Sin previo orden
        
        Búsqueda Binaria
        
        Transformación de Claves o Hash
        
        Mismas características que
      - Ocupan menos tiempo cuando los datos ya estan previamente almacenado
- - - - se caracteriza por
        
        Buscar
        una subcadena a la que llamamos patrón
      - Algoritmo Knuth-Morris-Pratt O(n)
        
        objetivo
        
        Buscar la existencia de una subcadena dentro de una cadena
        
        Elaborado por Donald
        Knuth y Vaughan Pratt y de modo independiente por James H. Morris en 1977
      - lgoritmo de búsqueda de cadenas Boyer-Moore O(n)
        
        Desarrollado por Bob Boyer y J Strother Moore en 1977
        
        El algoritmo
        preprocesa la cadena objetivo (clave) que está siendo buscada, pero no en la cadena en que se busca
    - - Ahora no tenemos un sólo patron p a
        buscar sino que contamos con un conjunto P
      - El algoritmo de Aho-Corasick O(N + L + Z)
        
        inventado por Alfred V. Aho y Margaret J. Corasick en 1975.
        
        Para múltiples patrones.

Apps, E.N. et al.: Socialmedia optimization. 1–44 (2011).

Creutzburg, R.: Algoritmos y Estructura de Datos Parte 5 de 7 : Correspondencia de Cadenas. July, (2015). https://doi.org/10.13140/RG.2.1.4134.2562.

Drozdek, A.: Estructura de datos y algoritmos con Java. (2007).

Dylan Trotsek: 済無No Title No Title. J. Chem. Inf. Model. 110, 9, 1689–1699 (2017).

Goitia, M.J.: Protocolos de Enrutamiento Para la Capa de Red en Arquitecturas de Redes de Datos. Network. 1–19 (2003).

Gómez Fuentes María del Carmen, C.O.J.: Introducción al análisis y al diseño de algoritmos. (2014).

Grado, S., Hern, C.L.: Fundamentos de la programación 7.

Joyanes, L., Zahonero, I.: Estructura de datos en java Joyanes 1ed. (2008).

Loiseau, I.: Algoritmos y Estructuras de Datos III. Tzulberti.Googlecode.Com. 1–62 (2007).

Manuel, J., Beardo, D.: Árboles de búsqueda.

Molina, I.C.E.: Algoritmos de enrutamiento. 23 (2015).

Operaciones, P. et al.: Algoritmos aplicados en la programación de las cadenas de suministros para minimizar costos. Revisión de literatura * Algorithms applied in the programming of the supply chains to minimize costs. Literature Review. Año. 12, 20, 1909–2458 (2016).

Ordenamiento, B.Y.: 7. búsqueda y ordenamiento. (2009).

Profesor, D.I.I. et al.: ALGORITMIA DE LA ORDENACIÓN EFICIENTE Necesidad de Ordenar Eficientemente Análisis Algoŕıtmico. 41 JAIIO - EST 2012 15o Concurs. Trab. Estud. 569–578 (2012).

Ramirez, E.: Algoritmos y Estructuras de Datos Universidad Central de Venezuela Facultad de Ciencias Escuela de Computación Algoritmos y Estructuras de Datos. January 2015, (2018).

1 Radix and Bucket Sort Rekha Saripella CS566. 2 History of Sorting  Herman Hollerith (February 29, 1860 – November 17, 1929) is first known to have, https://pdfslide.net/documents/1-radix-and-bucket-sort-rekha-saripella-cs566-2-history-of-sorting-herman.html, last accessed 2020/11/03.

Algoritmo de ordenamiento por selección - EcuRed, https://www.ecured.cu/Algoritmo_de_ordenamiento_por_selección, last accessed 2020/11/03.

Análisis del ordenamiento de selección (artículo) | Khan Academy, https://es.khanacademy.org/computing/computer-science/algorithms/sorting-algorithms/a/analysis-of-selection-sort, last accessed 2020/11/03.

Counting Sort – Numerentur.org, http://numerentur.org/ordenacion-de-vectores-counting-sort/, last accessed 2020/11/03.