Objetivos Generales:
- Estudio de
propiedades y algoritmos sobre grafos.
Objetivos Específicos:
- Estudio del modelo de Grafos
y de
las estructuras básicas de representación de
grafos.
- Familiarización
con
los algoritmos
fundamentales sobre grafos y con las técnicas de
diseño de algoritmos
utilizadas
en ellos:
ciclos Euclerianos, recorridos de
grafos, caminos de costo mínimo (backtracking, modelo
general de
etiquetamiento, programación dinámica
progresiva y regresiva, branch
and bound). Planificación
de Proyectos, árbol cobertor de costo mínimo - Presentar la
noción de algorimos eficientes
sobre grafos.
Contenido Detallado
Teoría:
- Definición de
Grafo y
Digrafo, conceptos fundamentales: nodos, lados, aristas, arcos,
subgrafos, cadenas, caminos, ciclos, circuitos, isomorfismos e
invariantes.
- Representación
de
Grafos: representación
gráfica, representación en el
computador: usando arreglos
usando listas
enlazadas.
- Conectividad en
Grafos: alcance, clausura transitiva, algoritmo de
RoyWarshal, componentes conexas y fuertemente
conexas, puntos de articulación.
- Recorridos en Grafos.
Modelo General de etiquetamiento: algoritmos de
Búsqueda en
Profundidad (DFS) y Búsqueda
en Amplitud (DFS). Aplicaciones.
- Caminos de Costo
MÃnimo y
Máximo. Algoritmos de Dijkstra, Bellman
(Programación Dinámica
Progresiva y Regresiva),
Floyd.
- Grafos de Precedencia.
Partición en Niveles, Ordenamiento
Topológico, Programación de
Actividades.
- Arboles y
Arborescencias. Propiedades. Arbol Mínimo
Cobertor:
Algoritmos de Prim y Kruskal.
Bibliografía:
- Meza, Ortega. "Grafos
y Algoritmos". Editorial
Equinoccio,
U.S.B. Caracas, 2006. ISBN 980-237232-3
- Cormen, Thomas; Leiserson,
Charles; Rivest, Ronald. "Introduction to Algorithms".
MIT Press,
McGraw Hill. 1997
- Berge Claude. "Grafos e
Hipergrafos". Dunod. 1970.
- Horstmann, Cay; Cornell,
Gary. "Core Java 1.3 Volume I- Fundamentals". The SUN Mycrosystems
Press JAVA SERIES. 1999. ISBN 0-13-081933-6
- Aho; Hopcroft;
Ullman. "Estructuras de Datos y Algoritmos".
Addison-Wesley. 1983.
- Brassard;
Bratley. "Fundamentos de Algoritmia".
Ed. Prentice
Hall. 1997.
- Sedgewick, R.
Algorithms in JAVA. Addison-Wesley. 1990.
- N. Wirth.
"Algoritmos y Estructuras de Datos". Editorial
Prentice Hall.
Material:
- Libro de Texto: "Grafos y Algoritmos". autores: Oscar Meza
y Maruja Ortega. Editorial Equinoccio, Universidad Simón Bolívar. 2007.
ISBN 980-237232-3
Puede adquirirlo en:
Dirección de Cultura USB (Edificio Comunicaciones, 2do piso)
Tlfs: (+58) (212) 906 3158 al 62
Fax: (+58) (212) 906 3159
Email: cultural usb.ve
|
