Diagrama semanal

  • General

    Colapsar todo Expandir todo

  • Datos Generales

    Horarios y salones

    Comienzo: Martes 17 de Setiembre de 2019.
    Finalización: Jueves 26 de Diciembre de 2019.

    Martes y Jueves de 17:30 a 19:30. Desde el 17/09 al 27/12.

    Salones:

    - los martes en el Salón Negro del IMERL (ubicado en el Piso 1 en el corredor de Bedelía rumbo al IMFIA),

    - los jueves en el Salón de Posgrado 701 del séptimo piso del cuerpo central de FING.


    Horas presenciales y horas de dedicación para el Trabajo Final

    • clases teórico: 52 horas (26 clases de dos horas).
    • clases consulta: 10 horas.
    • prueba escrita Teórica de 4 horas (primer semana de Diciembre)
    • evaluación final: 100 horas (Trabajo Final - Resolución de Carpeta de Ejercicios).


    Público objetivo y cupos:

    El curso, como curso de posgrado, esta dirigido a estudiantes de: Maestría en Informática, Maestría en Ingeniería Eléctrica, Maestría en Ing. Matemática, Doctorado en Informática, y Doctorado en Ingeniería Eléctrica.
    No tiene cupos.


    Objetivos:

    La determinación de la topología de redes de alto porte son problemas combinatorios usualmente de orden de exponencial en su resolución exacta. En la práctica, encontrar soluciones factibles que mejoren en pocos puntos porcentuales soluciones ya existentes, redunda en ahorros significativos para las empresas constructoras.

    El propósito central del curso es introducir a la metodología y la modelación de problemas de diseño de redes con altos niveles de conectividad de forma de obtener topologías de bajo costo robustas ante fallas en links y/o servidores. El estudiante se capacitará en tópicos inherentes a la modelación de problemas de diseño de la estructura topológica de redes con niveles de supervivencia preestablecidos y la resolución aproximada de éstos mediante el diseño de algoritmos a medida.


    Metodología de enseñanza:

    El curso está estructurado en tres fases:

    • Comprende el dictado y discusión temática en 26 clases (52 horas totales, 2 teóricos por semana de dos horas cada uno).
    • Cinco clases de consulta de dos horas cada una (total 10 horas).
    • La evaluación y extensión de formación mediante la realización de una prueba escrita de 4 horas de duración y un proyecto final (100 horas de dedicación estimada para la elaboración del trabajo final).


    Forma de evaluación:

    Evaluación escrita final y un proyecto final realizado una vez terminado el dictado de clases teóricas.

    La primer semana de Diciembre se hará una Prueba Escrita Teórica de 4 horas de duración. Deberán superar el 60% de la prueba para continuar el curso.
    Durante el curso se fijarán clases de consultas adicionales con un total de 10 horas específicas dedicadas para la preparación de la Prueba Escrita.

    Como Trabajo Final se entregará una Carpeta de 24 Problemas Teo-Práctico que deberán resolver detalladamente y documentar mediante un informe individual que elaborará cada estudiante. Los ejercicios/problemas a resolver llevarán no menos de 100 horas de dedicación por parte del estudiante.


    Docentes de la asignatura:

    • Dr. Ing. Franco Robledo Amoza, gr. 5 DT, Dpto. de Inv. Operativa, INCO  (responsable de la asignatura, dirigir la correspondencia)
    • Dr. Ing. Pablo Rodriguez Bocca, gr. 4, Dpto. de Inv. Operativa, INCO
    • Dr. Ing. Eduardo Canale, gr. 3, IMERL



  • Material

    Material general del curso, filminas:

    Transparencias de todo el curso (Franco Robledo)     descargar
    Clases de metaheurísticas (Rodriguez Bocca)     descargar
    Clases de conectividad (Eduardo Canale)     descargar

    Bibliografía:

    • Design of Survivable Networks, Mechthild Stoer. Spring-Verlag 1992. (3-540-56271-0).
    • Graph Theory, Reinhard Diestel. Springer 1997. (0-387-98210-8).
    • The Combinatorics of Network Reliability. Oxford University Press 1987. (0-19-504920-9

    • y otras proporcionadas por el docente...


    Enlaces:

    • e-Optimization.com - sitio que apunta a la comunidad de optimización; incluye papers, materiales, y Conferencias "en vivo" en tiempo real, que luego son archivadas.
    • "Optimization Online : An eprint site for the optimization community" - archivo de prepublicaciones en temas de optimización.
    • IFORS - International Federation Of Operational Research Societies.
    • IFORMS - Institute for Operations Research and the Management Sciences.
    • SADIO - Sociedad Argentina de Informática e Investigación Operativa.
    • SOBRAPO - Sociedade Brasileira de Pesquisa Operacional.

  • Cronograma

    Clase 1:
    1. Introducción - Motivación.
    2. Fundamentos básicos de la Teoría de Grafos.
    Clase 2 a 4:
    1. Conectividad en Grafos:
      1. Componentes conexas de un grafo; conjuntos de separación; conjuntos de corte; nodo de articulación; arista puente.
      2. Definiciones de k-arista-conectividad, k-nodo-conectividad y relación entre ellas.
      3. Caracterización de topologías de cubrimiento minimales (árboles).
      4. Teorema de Mader (condición suficiente de k-conectividad).
      5. Contracción en un grafo.
      6. Redes 2-conexas:
        1. Caracterización
        2. Operaciones que preservan la 2-conexidad
        3. Aplicación en modelos topologicamente robustos.
        4. Caso Particular: Ciclos Hamiltoneanos.
      7. Redes 3-conexas:
        1. Caracterización (Teorema de Tutte),
        2. Operaciones que preservan la 3-conexidad.
        3. Aplicación en modelos topologicamente robustos
      8. El Teorema de Menger.
      9. Teorema de Ford-Fulkerson y su aplicación para la determinación de un conjunto de corte en un grafo.
      10. Condición necesaria y suficiente para la existencia de k árboles de cubrimiento arista-disjuntos en un grafo (Teorema de Tutte-Nash-Williams).
    Clase 5 a 7:
    1. Diseño de redes con niveles de sobrevivencia prefijados:
      1. Definición de la k-nodo-(resp. arista)-sobrevivencia respecto a un conjunto distinguido de nodos de una red.
      2. Problemas:
        1. ECON - Encontrar la sub-red de costo mínimo que satisfaga ciertos requerimientos de arista-sobrevivencia preestablecidos.
        2. NCON - Encontrar la sub-red de costo mánimo que satisfaga ciertos requerimientos de nodo-sobrevivencia preestablecidos.
        3. Casos particulares del ECON y NCON: kNECON, kNCON, 2NCON, 2ECON, etc.
      3. Casos particulares del NCON/ECON resolubles en tiempo polinomial.
      4. Formulación del ECON y NCON como problemas de programación lineal entera.
      5. Condición necesaria para que una red sea k-nodo-conexa (Lema de Harary).
      6. Condición necesaria para que una red satisfaga requerimientos de conectividad heterogéneos (Lema de Chou-Frank).
      7. Número mánimo de aristas a agregar en una red dada, de forma de alcanzar requerimientos de conectividad preestablecidos (Teorema de Frank).
    Clase 8 a 10:
    1. Resultados estructurales para redes con desigualdad triangular entre los costos de los arcos:
      1. Modelos MWkVCSN y MWkECSN: el problema de encontrar el subgrafo k-nodo-conexo (resp. k-arista-conexo) de costo mínimo que cubre los nodos de un grafo completo.
      2. Caso particular (k=2): modelos MW2VCSN- MW2ECSN con desigualdad triangular:
        1. Condiciones equivalentes para la 2-nodo-conectividad de un grafo (Teorema de Berge).
        2. Existencia y estructura de una solución óptima 2-nodo-conexa para el problema MW2VCSN (Teorema de Monma et al.).
        3. Condición suficiente para que una solución factible a un problema MW2VCSN (resp. MW2ECSN) con función de distancia canónica sea solución óptima global (Teorema de Monma et al.).
      3. Modelos MWkVCSN y MWkECSN con k &ge 3 y desigualdad triangular:
        1. Existencia y estructura de una solución óptima k-arista-conexa para el problema MWkECSN (Teorema de Bienstock et al.).
        2. Existencia y estructura de una solución óptima k-nodo-conexa para el problema MWkVCSN (Teorema de Bienstock et al.).
        3. Condición necesaria de una solución óptima del MWkVCSN satisfaciendo la condicion |V| ≥ 2k (Teorema de Bienstock et al.).
    Clase 11 a 13:
    1. Algoritmos clásicos de diseño topológico: Heurística de Steiglitz, Heurística de Goemans-Bertsimas, etc.
    2. Introducción a la Confiabilidad Estructural.
    Clase 14 a 15:
    1. Heurísticas a medida como herramientas de diseño:
      1. Construcción greedy de soluciones factibles.
      2. Algoritmos de Búsqueda Local.
    Clase 16 a 24:
    1. Resolución Heurística-Greedy de los problemas:
      1. GSP (Generalized Steiner Problem).
      2. STNCSP (Steiner 2-node-connected subgraph problem).
      3. SPG (Steiner Problem in Graphs).
      4. STSP (Steiner Traveling Salesman Problem).
      5. RSP (Ring Star Problem).
    Clase 25 a 26:
    1. Presentación de los problemas de diseño topológico que deberían resolver los estudiantes.

  • Ediciones en años anteriores

    Obligatorio Final del Curso:


    Resultados Finales del Curso DTR: