Algoritmes de gràfics

Nuestra agencia de traducción en Barcelona cuenta con traductores expertos en traducción a/de Catalán de todo tipo de documentos: informes, contratos, escrituras notariales, manuales técnicos, catálogos, páginas web, etc. Uno de nuestros traductores en prácticas en Barcelona ha realizado la traducción de inglés a catalán del artículo sobre algoritmos informáticos «Advanced Topics in Graph Algorithms» escrito por el profesor Ron Shamir, de la Universidad de Tel Aviv y publicado originalmente en
http://cs.tau.ac.il/~rshamir/atga/atga.html

* * *

Aquest fitxer conté el material de l’assignatura «Temes avançats en algoritmes de gràfics» © del Ron Shamir en el departament de Informàtica de la Universitat de Tel Aviv, en 10/91-2/92 (tardor 92), 4-6/94 (primavera 94) i 4-6/97 (primavera 97).  Aquesta assignatura era d’un semestre també obert pels estudiants d’últim curs, amb una sessió de tres hores cada setmana. El curs va emfatitzar els aspectes algorítmics i estructurals de les famílies de gràfics “bones”, en particular gràfics perfectes, gràfics d’intervals, gràfics cordals i gràfics de comparabilitat. A la tardor del 92 l’assignatura es basava en gran manera en el llibre llibre clàssic de Martín C. GOLUMBICTeoría del Gràfic d’Algoritme i Gràfics Perfectes (Academic Press, 1980), i en algunes parts també en el manuscrit de L’art de la combinatòria, de Douglas B. West. Les primaveres del 94 i el 97 tenia una base similar, però va destacar material més recent, i va fer moltes referències a les aplicacions en biologia molecular (vegeu la pàgina web Algoritmes per biologia molecular per a més informació sobre aquest tema).

Material disponible :

• Esquema detallat del curs .
  • Primavera 97 (HTML)
  • Primavera 94 (ASCII)
  • Tardor 92 (ASCII)
• Material del curs de la primavera de 1997 (no organitzat; alguns enllaços no s’han actualitzat i algun material només es poden llegir des dels navegadors TAU. Disculpeu-me.)
  • pàgina web oficial del curs
  • pàgina web activa del curs
• Transcripcions de les classes de la primavera del 94

Els alumnes van transcriure les xerrades i el professor les va revisar. El conjunt complet d’apunts va ser posteriorment editat i formatat pel Sariel Har-Peled . Gràcies, Sariel!

Podeu descarregar les notes completes com un sol arxiu PostScript (150 pàgines), o cada Lliçó per separat.

Per a traduccions de les notes de la Lliçó a altres idiomes, vegeu aquí.

Portada

•  Pàgina de portada
  •  Taula de contingut
  •  Llista de figures

Lliçó # 1: Introducció a la teoria del gràfic

• Definicions bàsiques i notacions
  • Gràfics d’intersecció
  • Gràfics d’arc circular
  • Gràfics d’interval
  • Gràfics lineals de gràfics bipartits

Lliçó # 2: Gràfics perfectes

• Definició de gràfic perfecte
  • Algunes definicions i propietats
  • Teorema de gràfics perfectes

Lliçó # 3: Gràfics perfectes i triangulars

• Gràfics perfectes
  • $p$ – Gràfics crítics
  • Una caracterització polièdrica de gràfics perfectes
  • La conjectura del gràfic perfecte fort
  • Gràfics triangulars
    • Introducció
    • Caracterització de gràfics triangulars
    • Reconeixement de gràfics triangulars
    • Complexitat horària

Lliçó # 4: Reconeixement de gràfics triangulars

• Reconeixement de gràfics triangulars
  • Generar un PEO
  • Prova d’un esquema d’eliminació
    • Algoritme ingenu
    • Algoritme eficient
    • Exemple
    • Correcció de l’algoritme
    • Complexitat de l’algoritme
  • Gràfics triangulars com a gràfics d’intersecció
    • Arbres evolutius
    • Gràfics triangulars com a gràfics d’intersecció

Lliçó # 5: Els gràfics triangulars són perfectes

• Els gràfics triangulars són perfectes
  • Prova d’aquesta propietat
  • Altres resultats
  • Computar el mínim d’ompliment
    • El problema
    • L’ompliment és NP-hard
      • Gràfics en cadena
      • Arranjament lineal òptim (OLA)
      • Completar un gràfic en cadena (CGC)
      • El resultat de l’ompliment
    • Problemes

Lliçó # 6: Algoritmes de gràfics triangulars i gràfics de comparabilitat

• Alguns algoritmes d’optimització en gràfics triangulars
  • Calcular el nombre cromàtic i totes les indicacions màximes
  • Trobar $\alpha $ i $k$
  • Gràfics de comparabilitat
    • Algunes definicions
    • Classes d’implicació
    • El Triangle de Lema
    • Descomposició de gràfics

Lliçó # 7: Gràfics ordenables parcialment i únicament

• Gràfics ordenables parcialment i únicament
  • Algoritmes de caracteritzacions i reconeixement

Lliçó # 8: Algunes famílies gràfiques interessants caracteritzades per la intersecció

• Introducció
  • Gràfics de permutació
  • $F$ – Gràfics
  • “Els controladors aeris fan vaga”
  • Una composició del diagrama de permutació.
  • Gràfics de tolerància
  • Els gràfics d’interval són un subconjunt de gràfics de tolerància.
  • Gràfics de tolerància amb i sense límits.

Lliçó # 9: Gràfics de comparabilitat

• Reconeixement de gràfics de comparabilitat
  • La complexitat del reconeixement de gràfics de comparabilitat
    • Implementació
    • Anàlisi de complexitat
  • Coloració i altres problemes sobre gràfics de comparabilitat
    • Els gràfics de comparabilitat són perfectes
    • Clique màxim ponderat
    • Càlcul de $\alpha (G)$
  • La dimensió d’ordres parcials

Lliçó # 10: Invariants de comparabilitat i gràfics d’intervals

• Invariants de comparabilitat
  • Gràfics d’interval

Lliçó # 11: Gràfics d’intervals

• Preferència i indiferència
  • Reconeixement de gràfics d’interval
    • Un algorisme quadràtic 1
    • Un algoritme lineal
  • Més informació sobre la propietat consecutiva de l’1

Lliçó # 12: Raonament temporal

• Raonament temporal i àlgebres d’interval
  • Problemes de satisfacció de intervals
  • Interval de problemes de sandvitx i ISAT
  • Un algoritme de temps lineal per a ISAT ($\Delta _1}$)
  • Bandwidth, Pathwidth i Pathwidth adecuada

Índex

Si us plau, envieu els vostres suggeriments i comentaris a: rshamir@tau.ac.il

[Nota del Traductor]

Traducción de cursos, programas académicos y textos científicos

Esta traducción de inglés a catalán la ha realizado Antonio Diaz, profesor de matemáticas en Barcelona. En la actualidad, Antonio está terminando su formación como traductor de inglés técnico para trabajar el próximo curso en un Instituto Tecnológico de Estados Unidos. Allí formará parte de un equipo interdisciplinar encargado de estudios de álgebra avanzada sobre algoritmos gráficos complejos. Antonio ha participado en el programa de prácticas de Ibidem Group en Barcelona como traductor de/a catalán de artículos en inglés sobre matemáticas, informática y su pasión, la ingeniería computacional. Ha traducido gratuitamente este artículo escrito por el profesor israelí Ron Shamir de inglés a catalán con fines divulgativos y educativos para la comunidad científica y universitaria catalana.