Temes avançats en algoritmes de gràfics

Traducción de inglés a catalán del artículo sobre Algoritmos Gráficos publicado por el profesor Ron Shamir de la Tel Aviv University (Israel)

algoritmostraducción catalántraducción inglés catalán
15 junio, 2020 Traducción al catalán del artículo sobre algoritmos publicado originalmente en Inglés
15 junio, 2020 Traducción al catalán del artículo sobre algoritmos publicado originalmente en Inglés

Nuestra sede de Barcelona cuenta con especialistas en la 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 :

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.

Valora este artículo

Articulos relacionados


Traducci√≥n al espa√Īol del art√≠culo ¬ęXML Schema 1.1 Tutorial¬Ľ originalmente publicado en ingl√©s

Traducci√≥n al espa√Īol del art√≠culo ¬ęXML Schema 1.1 Tutorial¬Ľ originalmente publicado en ingl√©s

Traducci√≥n de Ingl√©s a Espa√Īol del Art√≠culo ¬ęPlanetary Placemats¬Ľ del profesor Mike Brown sobre Astronom√≠a