Estudio de El Problema del Agente Viajero (TSP) y Variaciones
El Problema del Agente Viajero (TSP, por sus siglas en inglés) es uno de los problemas de optimización más estudiados en la ciencia de la computación. El problema consiste en encontrar la ruta más corta para un vendedor que visite una lista de ciudades exactamente una vez y regrese a la ciudad de or...
- Autores:
-
Giraldo Botero, Santiago
- Tipo de recurso:
- Trabajo de grado de pregrado
- Fecha de publicación:
- 2022
- Institución:
- Universidad de los Andes
- Repositorio:
- Séneca: repositorio Uniandes
- Idioma:
- spa
- OAI Identifier:
- oai:repositorio.uniandes.edu.co:1992/64001
- Acceso en línea:
- http://hdl.handle.net/1992/64001
- Palabra clave:
- TSP
Travelling salesman problem
Complejidad
Máquinas de Turing
Ciencia de la computación
Clases de complejidad
Matemáticas
- Rights
- openAccess
- License
- Attribution-NoDerivatives 4.0 Internacional
| id |
UNIANDES2_d267b45c4dad564a4f4f82350bf1952c |
|---|---|
| oai_identifier_str |
oai:repositorio.uniandes.edu.co:1992/64001 |
| network_acronym_str |
UNIANDES2 |
| network_name_str |
Séneca: repositorio Uniandes |
| repository_id_str |
|
| dc.title.none.fl_str_mv |
Estudio de El Problema del Agente Viajero (TSP) y Variaciones |
| title |
Estudio de El Problema del Agente Viajero (TSP) y Variaciones |
| spellingShingle |
Estudio de El Problema del Agente Viajero (TSP) y Variaciones TSP Travelling salesman problem Complejidad Máquinas de Turing Ciencia de la computación Clases de complejidad Matemáticas |
| title_short |
Estudio de El Problema del Agente Viajero (TSP) y Variaciones |
| title_full |
Estudio de El Problema del Agente Viajero (TSP) y Variaciones |
| title_fullStr |
Estudio de El Problema del Agente Viajero (TSP) y Variaciones |
| title_full_unstemmed |
Estudio de El Problema del Agente Viajero (TSP) y Variaciones |
| title_sort |
Estudio de El Problema del Agente Viajero (TSP) y Variaciones |
| dc.creator.fl_str_mv |
Giraldo Botero, Santiago |
| dc.contributor.advisor.none.fl_str_mv |
Goodrick, John Richard |
| dc.contributor.author.none.fl_str_mv |
Giraldo Botero, Santiago |
| dc.contributor.jury.none.fl_str_mv |
Bogart, Tristram |
| dc.subject.keyword.none.fl_str_mv |
TSP Travelling salesman problem Complejidad Máquinas de Turing Ciencia de la computación Clases de complejidad |
| topic |
TSP Travelling salesman problem Complejidad Máquinas de Turing Ciencia de la computación Clases de complejidad Matemáticas |
| dc.subject.themes.es_CO.fl_str_mv |
Matemáticas |
| description |
El Problema del Agente Viajero (TSP, por sus siglas en inglés) es uno de los problemas de optimización más estudiados en la ciencia de la computación. El problema consiste en encontrar la ruta más corta para un vendedor que visite una lista de ciudades exactamente una vez y regrese a la ciudad de origen. Normalmente, se representa el esquema de ciudades como un grafo completo, donde cada arista tiene un peso asociado que representa la distancia entre ciudades. El TSP se relaciona con los ciclos hamiltonianos, que son caminos cíclicos en grafos que pasan por cada nodo una única vez y tienen el mismo punto de llegada y salida. A pesar de ser un problema estudiado, encontrar la solución óptima para el TSP en grafos grandes puede ser muy costoso en términos de tiempo y recursos computacionales. El TSP pertenece a la clase NP, lo que significa que es un problema cuya complejidad es muy alta y se requiere mucho tiempo y muchos pasos para encontrar la solución correcta. El trabajo se divide en 4 capítulos: en el primero se revisan los conceptos necesarios para hacer el análisis del problema, como la eficiencia y complejidad de los algoritmos, la teoría de máquinas de Turing y las clases de complejidad P, NP y NP-completo. En el segundo capítulo se analiza el Problema del Agente Viajero (TSP) en detalle, incluyendo su definición, formulaciones matemáticas, complejidad y ejemplos de problemas de la vida real que pueden ser planteados como instancias del TSP. En el tercer capítulo se explican y analizan los métodos de Robinson, Danztig, Fulkerson y Johnson para resolver el TSP. Por último, en el cuarto capítulo se desarrolla un algoritmo basado en el método de Robinson y se muestran los resultados obtenidos mediante una simulación en Python. El objetivo final es entender la complejidad del problema y los métodos utilizados para resolverlo. |
| publishDate |
2022 |
| dc.date.issued.none.fl_str_mv |
2022-06-02 |
| dc.date.accessioned.none.fl_str_mv |
2023-01-19T21:32:44Z |
| dc.date.available.none.fl_str_mv |
2023-01-19T21:32:44Z |
| dc.type.es_CO.fl_str_mv |
Trabajo de grado - Pregrado |
| dc.type.driver.none.fl_str_mv |
info:eu-repo/semantics/bachelorThesis |
| dc.type.version.none.fl_str_mv |
info:eu-repo/semantics/acceptedVersion |
| dc.type.coar.none.fl_str_mv |
http://purl.org/coar/resource_type/c_7a1f |
| dc.type.content.es_CO.fl_str_mv |
Text |
| dc.type.redcol.none.fl_str_mv |
http://purl.org/redcol/resource_type/TP |
| format |
http://purl.org/coar/resource_type/c_7a1f |
| status_str |
acceptedVersion |
| dc.identifier.uri.none.fl_str_mv |
http://hdl.handle.net/1992/64001 |
| dc.identifier.instname.es_CO.fl_str_mv |
instname:Universidad de los Andes |
| dc.identifier.reponame.es_CO.fl_str_mv |
reponame:Repositorio Institucional Séneca |
| dc.identifier.repourl.es_CO.fl_str_mv |
repourl:https://repositorio.uniandes.edu.co/ |
| url |
http://hdl.handle.net/1992/64001 |
| identifier_str_mv |
instname:Universidad de los Andes reponame:Repositorio Institucional Séneca repourl:https://repositorio.uniandes.edu.co/ |
| dc.language.iso.es_CO.fl_str_mv |
spa |
| language |
spa |
| dc.relation.references.es_CO.fl_str_mv |
Sanjeev Arora y Boaz Barak. Computational complexity: A modern approach. Cambridge University Press, abr. de 2009. isbn: 9780521424264. Dimitris Bertsimas y John Tsitsiklis. Introduction to Linear Optimization. 1st. Athena Scientific, 1997. isbn: 1886529191. Xavier Bresson y Thomas Laurent. «The Transformer Network for the Traveling Salesman Problem». En: CoRR abs/2103.03012 (2021). arXiv: 2103.03012. url: https://arxiv. org/abs/2103.03012. William J. Cook. In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton University Press, nov. de 2014. isbn: 9780691163529. George Bernard Dantzig, D. R. Fulkerson y Selmer Martin Johnson. Solution of a Large- Scale Traveling-Salesman Problem. Santa Monica, CA: RAND Corporation, 1954. Antoine François, Quentin Cappart y Louis-Martin Rousseau. «How to Evaluate Machi- ne Learning Approaches for Combinatorial Optimization: Application to the Travelling Salesman Problem». En: CoRR abs/1909.13121 (2019). arXiv: 1909.13121. url: http: //arxiv.org/abs/1909.13121 B. H. Korte y Jens Vygen. Combinatorial optimization: theory and algorithms. 5th ed. Algo- rithms and combinatorics v. 21. Heidelberg ; New York: Springer, 2012. isbn: 9783642244872 J. K. Lenstra y A. H. G. Rinnooy Kan. «Some Simple Applications of the Travelling Sa- lesman Problem». En: Operational Research Quarterly (1970-1977) 26.4 (1975), pág. 717. doi: 10.2307/3008306. url: https://core.ac.uk/download/pdf/205710912.pdf. C. E. Miller, A. W. Tucker y R. A. Zemlin. «Integer Programming Formulation of Traveling Salesman Problems». En: Journal of the ACM 7.4 (nov. de 1960), págs. 326-329. doi: 10.1145/321043.321046. url: https://doi.org/10.1145/321043.321046. Cristopher Moore y Stephan Mertens. The Nature of Computation. Oxford University Press, ago. de 2011. doi: 10.1093/acprof:oso/9780199233212.001.0001. url: https://doi. org/10.1093/acprof:oso/9780199233212.001.0001. Charles Petzold. The annotated Turing: a guided tour through Alan Turing's historic pa- per on computability and the Turing machine. Indianapolis, IN: Wiley Pub, 2008. isbn: 9780470229057 Julia Robinson. «On The Hamiltonian Game (A Travelling Salesman Problem)». En: Pro- ject Rand RM-303.70 (dic. de 1949). Michael Sipser. Introduction to the theory of Computation. Cengagae Learning, 2013 «MAPE (mean absolute percentage error)MEAN ABSOLUTE PERCENTAGE ERROR (MAPE)». En: Encyclopedia of Production and Manufacturing Management. Ed. por P. M. Swamidass. Boston, MA: Springer US, 2000, págs. 462-462. isbn: 978-1-4020-0612-8. doi: 10.1007/1-4020-0612-8_580. url: https://doi.org/10.1007/1-4020-0612-8_580. University of Waterloo. TSP Annotated Bibliography. http://www.math.uwaterloo.ca/ tsp/history/biblio/1940.html. url: http://www.math.uwaterloo.ca/tsp/history/ biblio/1940.html. What is integer programming? Mar. de 2021. url: https://www.ibm.com/docs/en/icos/ 12.8.0.0?topic=problem-what-is-integer-programming. |
| dc.rights.license.spa.fl_str_mv |
Attribution-NoDerivatives 4.0 Internacional |
| dc.rights.uri.*.fl_str_mv |
http://creativecommons.org/licenses/by-nd/4.0/ |
| dc.rights.accessrights.spa.fl_str_mv |
info:eu-repo/semantics/openAccess |
| dc.rights.coar.spa.fl_str_mv |
http://purl.org/coar/access_right/c_abf2 |
| rights_invalid_str_mv |
Attribution-NoDerivatives 4.0 Internacional http://creativecommons.org/licenses/by-nd/4.0/ http://purl.org/coar/access_right/c_abf2 |
| eu_rights_str_mv |
openAccess |
| dc.format.extent.es_CO.fl_str_mv |
88 páginas |
| dc.format.mimetype.es_CO.fl_str_mv |
application/pdf |
| dc.publisher.es_CO.fl_str_mv |
Universidad de los Andes |
| dc.publisher.program.es_CO.fl_str_mv |
Matemáticas |
| dc.publisher.faculty.es_CO.fl_str_mv |
Facultad de Ciencias |
| dc.publisher.department.es_CO.fl_str_mv |
Departamento de Matemáticas |
| institution |
Universidad de los Andes |
| bitstream.url.fl_str_mv |
https://repositorio.uniandes.edu.co/bitstreams/a4051642-b032-4c02-ad42-8d29babbc4b0/download https://repositorio.uniandes.edu.co/bitstreams/151cf061-af5a-45d3-b59a-c9a9ee3baa28/download https://repositorio.uniandes.edu.co/bitstreams/71623157-3895-4fde-bfab-33a2882b1f88/download https://repositorio.uniandes.edu.co/bitstreams/bbe76cb6-826a-40ff-8751-70674d9b884d/download https://repositorio.uniandes.edu.co/bitstreams/a37cea73-e97d-4fa4-a2e2-99d573721d34/download https://repositorio.uniandes.edu.co/bitstreams/df312035-4b27-4d59-9f66-8c81afc44130/download https://repositorio.uniandes.edu.co/bitstreams/14109c97-e6b7-4a95-bd30-b85c4268d4a2/download https://repositorio.uniandes.edu.co/bitstreams/070ad8ec-6d95-45f8-a3e0-9776c262a1bf/download |
| bitstream.checksum.fl_str_mv |
f2380750e2cd2b453b1794ecd50ab478 643782b33b1ca5156b74d18471d61311 5aa5c691a1ffe97abd12c2966efcb8d6 565077f32614408de5b78b351a3256d9 3b98e311397ae846cd717131d6bc2f3f f7d494f61e544413a13e6ba1da2089cd 60bd84a29c32f025b93df24627e7f2ae 4491fe1afb58beaaef41a73cf7ff2e27 |
| bitstream.checksumAlgorithm.fl_str_mv |
MD5 MD5 MD5 MD5 MD5 MD5 MD5 MD5 |
| repository.name.fl_str_mv |
Repositorio institucional Séneca |
| repository.mail.fl_str_mv |
adminrepositorio@uniandes.edu.co |
| _version_ |
1812133810605654016 |
| spelling |
Attribution-NoDerivatives 4.0 Internacionalhttp://creativecommons.org/licenses/by-nd/4.0/info:eu-repo/semantics/openAccesshttp://purl.org/coar/access_right/c_abf2Goodrick, John Richard13ff6516-0d0e-4f4f-92c0-6bcab0026dfa600Giraldo Botero, Santiago2bf13150-df36-42b7-8220-a879dc0ab5b8600Bogart, Tristram2023-01-19T21:32:44Z2023-01-19T21:32:44Z2022-06-02http://hdl.handle.net/1992/64001instname:Universidad de los Andesreponame:Repositorio Institucional Sénecarepourl:https://repositorio.uniandes.edu.co/El Problema del Agente Viajero (TSP, por sus siglas en inglés) es uno de los problemas de optimización más estudiados en la ciencia de la computación. El problema consiste en encontrar la ruta más corta para un vendedor que visite una lista de ciudades exactamente una vez y regrese a la ciudad de origen. Normalmente, se representa el esquema de ciudades como un grafo completo, donde cada arista tiene un peso asociado que representa la distancia entre ciudades. El TSP se relaciona con los ciclos hamiltonianos, que son caminos cíclicos en grafos que pasan por cada nodo una única vez y tienen el mismo punto de llegada y salida. A pesar de ser un problema estudiado, encontrar la solución óptima para el TSP en grafos grandes puede ser muy costoso en términos de tiempo y recursos computacionales. El TSP pertenece a la clase NP, lo que significa que es un problema cuya complejidad es muy alta y se requiere mucho tiempo y muchos pasos para encontrar la solución correcta. El trabajo se divide en 4 capítulos: en el primero se revisan los conceptos necesarios para hacer el análisis del problema, como la eficiencia y complejidad de los algoritmos, la teoría de máquinas de Turing y las clases de complejidad P, NP y NP-completo. En el segundo capítulo se analiza el Problema del Agente Viajero (TSP) en detalle, incluyendo su definición, formulaciones matemáticas, complejidad y ejemplos de problemas de la vida real que pueden ser planteados como instancias del TSP. En el tercer capítulo se explican y analizan los métodos de Robinson, Danztig, Fulkerson y Johnson para resolver el TSP. Por último, en el cuarto capítulo se desarrolla un algoritmo basado en el método de Robinson y se muestran los resultados obtenidos mediante una simulación en Python. El objetivo final es entender la complejidad del problema y los métodos utilizados para resolverlo.MatemáticoPregrado88 páginasapplication/pdfspaUniversidad de los AndesMatemáticasFacultad de CienciasDepartamento de MatemáticasEstudio de El Problema del Agente Viajero (TSP) y VariacionesTrabajo de grado - Pregradoinfo:eu-repo/semantics/bachelorThesisinfo:eu-repo/semantics/acceptedVersionhttp://purl.org/coar/resource_type/c_7a1fTexthttp://purl.org/redcol/resource_type/TPTSPTravelling salesman problemComplejidadMáquinas de TuringCiencia de la computaciónClases de complejidadMatemáticasSanjeev Arora y Boaz Barak. Computational complexity: A modern approach. Cambridge University Press, abr. de 2009. isbn: 9780521424264.Dimitris Bertsimas y John Tsitsiklis. Introduction to Linear Optimization. 1st. Athena Scientific, 1997. isbn: 1886529191.Xavier Bresson y Thomas Laurent. «The Transformer Network for the Traveling Salesman Problem». En: CoRR abs/2103.03012 (2021). arXiv: 2103.03012. url: https://arxiv. org/abs/2103.03012.William J. Cook. In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton University Press, nov. de 2014. isbn: 9780691163529.George Bernard Dantzig, D. R. Fulkerson y Selmer Martin Johnson. Solution of a Large- Scale Traveling-Salesman Problem. Santa Monica, CA: RAND Corporation, 1954.Antoine François, Quentin Cappart y Louis-Martin Rousseau. «How to Evaluate Machi- ne Learning Approaches for Combinatorial Optimization: Application to the Travelling Salesman Problem». En: CoRR abs/1909.13121 (2019). arXiv: 1909.13121. url: http: //arxiv.org/abs/1909.13121B. H. Korte y Jens Vygen. Combinatorial optimization: theory and algorithms. 5th ed. Algo- rithms and combinatorics v. 21. Heidelberg ; New York: Springer, 2012. isbn: 9783642244872J. K. Lenstra y A. H. G. Rinnooy Kan. «Some Simple Applications of the Travelling Sa- lesman Problem». En: Operational Research Quarterly (1970-1977) 26.4 (1975), pág. 717. doi: 10.2307/3008306. url: https://core.ac.uk/download/pdf/205710912.pdf.C. E. Miller, A. W. Tucker y R. A. Zemlin. «Integer Programming Formulation of Traveling Salesman Problems». En: Journal of the ACM 7.4 (nov. de 1960), págs. 326-329. doi: 10.1145/321043.321046. url: https://doi.org/10.1145/321043.321046.Cristopher Moore y Stephan Mertens. The Nature of Computation. Oxford University Press, ago. de 2011. doi: 10.1093/acprof:oso/9780199233212.001.0001. url: https://doi. org/10.1093/acprof:oso/9780199233212.001.0001.Charles Petzold. The annotated Turing: a guided tour through Alan Turing's historic pa- per on computability and the Turing machine. Indianapolis, IN: Wiley Pub, 2008. isbn: 9780470229057Julia Robinson. «On The Hamiltonian Game (A Travelling Salesman Problem)». En: Pro- ject Rand RM-303.70 (dic. de 1949).Michael Sipser. Introduction to the theory of Computation. Cengagae Learning, 2013«MAPE (mean absolute percentage error)MEAN ABSOLUTE PERCENTAGE ERROR (MAPE)». En: Encyclopedia of Production and Manufacturing Management. Ed. por P. M. Swamidass. Boston, MA: Springer US, 2000, págs. 462-462. isbn: 978-1-4020-0612-8. doi: 10.1007/1-4020-0612-8_580. url: https://doi.org/10.1007/1-4020-0612-8_580.University of Waterloo. TSP Annotated Bibliography. http://www.math.uwaterloo.ca/ tsp/history/biblio/1940.html. url: http://www.math.uwaterloo.ca/tsp/history/ biblio/1940.html.What is integer programming? Mar. de 2021. url: https://www.ibm.com/docs/en/icos/ 12.8.0.0?topic=problem-what-is-integer-programming.201729572PublicationTHUMBNAILTesis - Santiago Giraldo Botero.pdf.jpgTesis - Santiago Giraldo Botero.pdf.jpgIM Thumbnailimage/jpeg6102https://repositorio.uniandes.edu.co/bitstreams/a4051642-b032-4c02-ad42-8d29babbc4b0/downloadf2380750e2cd2b453b1794ecd50ab478MD56Carta Tesis.pdf.jpgCarta Tesis.pdf.jpgIM Thumbnailimage/jpeg15659https://repositorio.uniandes.edu.co/bitstreams/151cf061-af5a-45d3-b59a-c9a9ee3baa28/download643782b33b1ca5156b74d18471d61311MD58LICENSElicense.txtlicense.txttext/plain; charset=utf-81810https://repositorio.uniandes.edu.co/bitstreams/71623157-3895-4fde-bfab-33a2882b1f88/download5aa5c691a1ffe97abd12c2966efcb8d6MD51ORIGINALTesis - Santiago Giraldo Botero.pdfTesis - Santiago Giraldo Botero.pdfArtículo principalapplication/pdf1045677https://repositorio.uniandes.edu.co/bitstreams/bbe76cb6-826a-40ff-8751-70674d9b884d/download565077f32614408de5b78b351a3256d9MD53Carta Tesis.pdfCarta Tesis.pdfHIDEapplication/pdf149407https://repositorio.uniandes.edu.co/bitstreams/a37cea73-e97d-4fa4-a2e2-99d573721d34/download3b98e311397ae846cd717131d6bc2f3fMD54CC-LICENSElicense_rdflicense_rdfapplication/rdf+xml; charset=utf-8799https://repositorio.uniandes.edu.co/bitstreams/df312035-4b27-4d59-9f66-8c81afc44130/downloadf7d494f61e544413a13e6ba1da2089cdMD52TEXTTesis - Santiago Giraldo Botero.pdf.txtTesis - Santiago Giraldo Botero.pdf.txtExtracted texttext/plain175684https://repositorio.uniandes.edu.co/bitstreams/14109c97-e6b7-4a95-bd30-b85c4268d4a2/download60bd84a29c32f025b93df24627e7f2aeMD55Carta Tesis.pdf.txtCarta Tesis.pdf.txtExtracted texttext/plain1163https://repositorio.uniandes.edu.co/bitstreams/070ad8ec-6d95-45f8-a3e0-9776c262a1bf/download4491fe1afb58beaaef41a73cf7ff2e27MD571992/64001oai:repositorio.uniandes.edu.co:1992/640012023-10-10 15:23:14.381http://creativecommons.org/licenses/by-nd/4.0/open.accesshttps://repositorio.uniandes.edu.coRepositorio institucional Sénecaadminrepositorio@uniandes.edu.coWW8sIGVuIG1pIGNhbGlkYWQgZGUgYXV0b3IgZGVsIHRyYWJham8gZGUgdGVzaXMsIG1vbm9ncmFmw61hIG8gdHJhYmFqbyBkZSBncmFkbywgaGFnbyBlbnRyZWdhIGRlbCBlamVtcGxhciByZXNwZWN0aXZvIHkgZGUgc3VzIGFuZXhvcyBkZSBzZXIgZWwgY2FzbywgZW4gZm9ybWF0byBkaWdpdGFsIHkvbyBlbGVjdHLDs25pY28geSBhdXRvcml6byBhIGxhIFVuaXZlcnNpZGFkIGRlIGxvcyBBbmRlcyBwYXJhIHF1ZSByZWFsaWNlIGxhIHB1YmxpY2FjacOzbiBlbiBlbCBTaXN0ZW1hIGRlIEJpYmxpb3RlY2FzIG8gZW4gY3VhbHF1aWVyIG90cm8gc2lzdGVtYSBvIGJhc2UgZGUgZGF0b3MgcHJvcGlvIG8gYWplbm8gYSBsYSBVbml2ZXJzaWRhZCB5IHBhcmEgcXVlIGVuIGxvcyB0w6lybWlub3MgZXN0YWJsZWNpZG9zIGVuIGxhIExleSAyMyBkZSAxOTgyLCBMZXkgNDQgZGUgMTk5MywgRGVjaXNpw7NuIEFuZGluYSAzNTEgZGUgMTk5MywgRGVjcmV0byA0NjAgZGUgMTk5NSB5IGRlbcOhcyBub3JtYXMgZ2VuZXJhbGVzIHNvYnJlIGxhIG1hdGVyaWEsIHV0aWxpY2UgZW4gdG9kYXMgc3VzIGZvcm1hcywgbG9zIGRlcmVjaG9zIHBhdHJpbW9uaWFsZXMgZGUgcmVwcm9kdWNjacOzbiwgY29tdW5pY2FjacOzbiBww7pibGljYSwgdHJhbnNmb3JtYWNpw7NuIHkgZGlzdHJpYnVjacOzbiAoYWxxdWlsZXIsIHByw6lzdGFtbyBww7pibGljbyBlIGltcG9ydGFjacOzbikgcXVlIG1lIGNvcnJlc3BvbmRlbiBjb21vIGNyZWFkb3IgZGUgbGEgb2JyYSBvYmpldG8gZGVsIHByZXNlbnRlIGRvY3VtZW50by4gIAoKCkxhIHByZXNlbnRlIGF1dG9yaXphY2nDs24gc2UgZW1pdGUgZW4gY2FsaWRhZCBkZSBhdXRvciBkZSBsYSBvYnJhIG9iamV0byBkZWwgcHJlc2VudGUgZG9jdW1lbnRvIHkgbm8gY29ycmVzcG9uZGUgYSBjZXNpw7NuIGRlIGRlcmVjaG9zLCBzaW5vIGEgbGEgYXV0b3JpemFjacOzbiBkZSB1c28gYWNhZMOpbWljbyBkZSBjb25mb3JtaWRhZCBjb24gbG8gYW50ZXJpb3JtZW50ZSBzZcOxYWxhZG8uIExhIHByZXNlbnRlIGF1dG9yaXphY2nDs24gc2UgaGFjZSBleHRlbnNpdmEgbm8gc29sbyBhIGxhcyBmYWN1bHRhZGVzIHkgZGVyZWNob3MgZGUgdXNvIHNvYnJlIGxhIG9icmEgZW4gZm9ybWF0byBvIHNvcG9ydGUgbWF0ZXJpYWwsIHNpbm8gdGFtYmnDqW4gcGFyYSBmb3JtYXRvIGVsZWN0csOzbmljbywgeSBlbiBnZW5lcmFsIHBhcmEgY3VhbHF1aWVyIGZvcm1hdG8gY29ub2NpZG8gbyBwb3IgY29ub2Nlci4gCgoKRWwgYXV0b3IsIG1hbmlmaWVzdGEgcXVlIGxhIG9icmEgb2JqZXRvIGRlIGxhIHByZXNlbnRlIGF1dG9yaXphY2nDs24gZXMgb3JpZ2luYWwgeSBsYSByZWFsaXrDsyBzaW4gdmlvbGFyIG8gdXN1cnBhciBkZXJlY2hvcyBkZSBhdXRvciBkZSB0ZXJjZXJvcywgcG9yIGxvIHRhbnRvLCBsYSBvYnJhIGVzIGRlIHN1IGV4Y2x1c2l2YSBhdXRvcsOtYSB5IHRpZW5lIGxhIHRpdHVsYXJpZGFkIHNvYnJlIGxhIG1pc21hLiAKCgpFbiBjYXNvIGRlIHByZXNlbnRhcnNlIGN1YWxxdWllciByZWNsYW1hY2nDs24gbyBhY2Npw7NuIHBvciBwYXJ0ZSBkZSB1biB0ZXJjZXJvIGVuIGN1YW50byBhIGxvcyBkZXJlY2hvcyBkZSBhdXRvciBzb2JyZSBsYSBvYnJhIGVuIGN1ZXN0acOzbiwgZWwgYXV0b3IgYXN1bWlyw6EgdG9kYSBsYSByZXNwb25zYWJpbGlkYWQsIHkgc2FsZHLDoSBkZSBkZWZlbnNhIGRlIGxvcyBkZXJlY2hvcyBhcXXDrSBhdXRvcml6YWRvcywgcGFyYSB0b2RvcyBsb3MgZWZlY3RvcyBsYSBVbml2ZXJzaWRhZCBhY3TDumEgY29tbyB1biB0ZXJjZXJvIGRlIGJ1ZW5hIGZlLiAKCg== |