GoConqr hat ein neues Design! Sag uns, wie es dir gefällt.

Mindmap

GRAFOS ALGORITMOS

luis pereira Spanisch

GRAFOS ALGORITMOS

Inhalt der Mindmap

GRAFOS ALGORITMOS

  1. Dijkstra

    • Edsger Dijkstra (1930 -2002 ) es uno de los padres de la informática al que poca gente ajena a la informática conoce. Éste físico teórico realizó contribuciones fundamentales al campo de la informática actual están los semáforos, el algoritmo del banquero o la notación polaca inversa.
      • El algoritmo de Dijkstra calcula la distancia desde un vértice inicial al resto de vértices del grafo. En cada paso etiquetaremos los vértices del grafo de la siguiente forma: (dist(u),v), dónde dist(u) es la distancia acumulada desde el vértice s al u y v es el vértice predecesor de u en el camino más corto de s a u.
        • 1. Un grafo ponderado (G,w) representado mediante una lista de adyacencias. G representa el conjunto de vértices y w (u, v) el peso del arco (u,v)
        • 2. Un conjunto U de los vértices que se han visitado, en el orden en el que se ha hecho.
          • SIMULACION
        • 3. Una tabla de distancias, dist(・), indexada por los vértices de G, que registra la distancia del vértice inicial a los vértices que se van visitando.
        • 4. Al final, la tabla dist(・) registra la distancia desde el vértice inicial al resto de los vértices.
  2. Prim

    • es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas.
      • El algoritmo fue diseñado en 1930 por el matemático Vojtech Jarnik y luego de manera independiente por el científico computacional Robert C. Prim en 1957 y redescubierto por Dijkstra en 1959. Por esta razón, el algoritmo es también conocido como algoritmo DJP o algoritmo de Jarnik.
        • El algoritmo incrementa continuamente el tamaño de un árbol, comenzando por un vértice inicial al que se le van agregando sucesivamente vértices cuya distancia a los anteriores es mínima. Esto significa que en cada paso, las aristas a considerar son aquellas que inciden en vértices que ya pertenecen al árbol. El árbol recubridor mínimo está completamente construido cuando no quedan más vértices por agregar.
  3. Kruskal

    • Joseph B. Kruskal investigador del Math Center (Bell-Labs), que en 1956 descubrió su algoritmo para la resolución del problema del Árbol de coste total mínimo (minimum spanning tree - MST) también llamado árbol recubridor euclídeo mínimo. Este problema es un problema típico de optimización combinatoria, que fue considerado originalmente por Otakar Boruvka (1926) mientras estudiaba la necesidad de electrificación rural en el sur de Moravia en Checoslovaquia.
      • El objetivo del algoritmo de Kruskal es construir un árbol (subgrafo sin ciclos) formado por arcos sucesivamente seleccionados de mínimo peso a partir de un grafo con pesos en los arcos.
        • Un árbol (spanning tree) de un grafo es un subgrafo que contiene todos sus vértices o nodos. Un grafo puede tener múltiples árboles. Por ejemplo, un grafo completo de cuatro nodos (todos relacionados con todos) tendría 16 árboles.
          • Algoritmo Resumido
  4. Floyd-Warshall

    • Robert W. Floyd nació el 8 de junio de 1936 en Nueva York, es profesor de la Stanford University (B.A. Chicago 1955 B.S. Chicago 1958), y en 1978 fue galardonado con el prestigioso premio A.M. Turing que otorga la ACM para reconocer las contribuciones de naturaleza técnica realizadas a la comunidad informática. El premio le fue concedido por tener una influencia clara en las metodologías para la creación de software eficiente y fiable, y por ayudar a fundar las siguientes áreas de la informática: teoría de análisis sintáctico, semántica de los leguajes de programación, verificación automática de programas, síntesis automática de programas y análisis de algoritmos.
      • El problema que intenta resolver este algoritmo es el de encontrar el camino más corto entre todos los pares de nodos o vértices de un grafo. Esto es semejante a construir una tabla con todas las distancias mínimas entre pares de ciudades de un mapa, indicando además la ruta a seguir para ir de la primera ciudad a la segunda. Este es uno de los problemas más interesantes que se pueden resolver con algoritmos de grafos.
        • Algoritmo Resumido

Bilder und Dateien der Mindmap

  • GRAFOS ALGORITMOS
  • GRAFOS ALGORITMOS
  • GRAFOS ALGORITMOS
  • GRAFOS ALGORITMOS
  • GRAFOS ALGORITMOS
  • GRAFOS ALGORITMOS
  • GRAFOS ALGORITMOS

Informationen

Beschreibung
Mindmap am GRAFOS ALGORITMOS, erstellt von luis pereira am 05/12/2017.
Erstellt von
luis pereira · Dez 2017
Aktualisiert
5 Dez 2017
Aufrufe
1
Bewertung

Mehr zu Grafos

Feedback

Worum geht es?

Wie gefällt dir das neue Design?

Dein Eindruck