trabajo final

Ministerio del Poder Popular para la Educación Universitaria
Fundación Sucre
Aldea: Unidos Venceremos
Trayecto II. Trimestre II
Programa de Formación: Sistemas e informática.
Unidad Curricular: Desarrollo de Software












Trabajo Final












Realizado por:
CARLOS NAVARRO
EDUARDO NAVARRO
KATIUSKA BARRIOS
TIBISAY AGUILLON
RAUL OLLARVES
DAYAGNAQUINTERO
ANA ROMERO
LUIS MAVAREZ
NOAHYELY DIAZ


ESQUEMA


Introducción

TAD Grafo

Concepto de grafo.
Representación del TAD grafo.
Matriz de caminos.
Algoritmos fundamentales con grafos.
Aplicaciones.

Búsqueda

Búsqueda Lineal.
Búsqueda Binaria.

Hashing

Función de Hashing

1. Orígenes del término
2. Terminología asociada
3. Parámetros adicionales
3.1 Funcioneshash con clave
4. Propiedades
5. Funciones hash iterativas. Construcción de Merkle-Damgård
6. Aplicaciones

Bibliografía








INTRODUCCIÓN

El nacimiento del concepto GRAFOS se puede situar, por el año 1730, cuando Euler (matemático) se convirtió en el padre de la Teoría de Grafos al modelar un famoso problema no resuelto, llamado el "problema de los puentes de Königsberg".Un río con dos islas atraviesa la ciudad. Las islas están unidas, entre si y con las orillas, a través de siete puentes. El problema consistía en establecer un recorrido que pasara una y solo una vez por cada uno de los siete puentes, partiendo de cualquier punto y regresando al mismo lugar. Para probar que no era posible, Euler sustituyó cada zona de partida por un punto y cada puente por un arco,creando así un grafo, el primer grafo, diseñado para resolver un problema.
En matemáticas y ciencias de la computación, un grafo (del griego grafos: dibujo, imagen) o gráfica es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto. Son objeto de estudio de la teoría de grafos.Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).










TAD Grafo

Concepto de grafo.
La teoría de grafos (también llamada teoría de las gráficas) es un campo de estudio de las matemáticas y las ciencias de la computación, que estudia las propiedades de los grafos (también llamadas gráficas, que no se debeconfundir con las gráficas que tienen una acepción muy amplia) estructuras que constan de dos partes, el conjunto de vértices, nodos o puntos; y el conjunto de aristas, líneas o lados (edges en inglés) que pueden ser orientados o no.
La teoría de grafos es una rama de la matemáticas discretas y aplicadas, y es una disciplina que unifica diversas áreas como combinatoria, álgebra, probabilidad,geometría de polígonos, aritmética y topología.
Actualmente ha tenido mayor preponderancia en el campo de la informática, las ciencias de la computación y telecomunicaciones.
Representación del TAD grafo.
Existen diferentes implementaciones del tipo grafo: con una matriz de adyacencias (forma acotada) y con listas y multilistas de adyacencia (no acotadas).
Matriz de adyacencias: se asocia cada filay cada columna a cada nodo del grafo, siendo los elementos de la matriz la relación entre los mismos, tomando los valores de 1 si existe la arista y 0 en caso contrario.





Lista de adyacencias: se asocia a cada nodo del grafo una lista que contenga todos aquellos nodos que sean adyacentes a él.


Matriz de caminos.

Sea G un grafo dirigido simple con m nodos v1,v2…..vm. La matriz decaminos o matriz de alcance de G es la matriz m-cuadrada P= v(i,j) definida como sigue:







Suponga que hay un camino desde vi hasta vj. Entonces tiene que haber un camino simple desde vi hasta vj cuando vi=vj, o un ciclo de vi a vj cuando vi=vj. Como G solo tiene m nodos n un camino simple así ha de tener longitud m-1 o menor, o un ciclo así ha de tener longitud m o menor. Esto...