Algoritmo basado en la coloración de grafos para la programación flexible de horarios y salones en una institución universitaria: caso de estudio en Colombia

La asignación de horarios y salones en instituciones universitarias es un problema complejo clasificado como NP-Completo, debido a la interdependencia de variables y restricciones asociadas. Este trabajo presenta el diseño de un algoritmo basado en la coloración de grafos para la programación eficaz...

Full description

Autores:
Leal Figueredo, Andrés David
Tipo de recurso:
Trabajo de grado de pregrado
Fecha de publicación:
2024
Institución:
Institución Universitaria Politécnico Grancolombiano
Repositorio:
Alejandría Repositorio Institucional
Idioma:
spa
OAI Identifier:
oai:alejandria.poligran.edu.co:10823/7524
Acceso en línea:
http://hdl.handle.net/10823/7524
Palabra clave:
Asignación de horarios
Coloración de grafos
Restricciones duras y suaves
Gestión administrativa
Innovación tecnológica - algoritmos
Registro de tiempos - horarios
Graph coloring
Hard and soft restrictions
Schedule assignment
Rights
License
Atribución-NoComercial-SinDerivadas 2.5 Colombia
id Poli2_654de7906ad4fdb08afbadd31b47cf18
oai_identifier_str oai:alejandria.poligran.edu.co:10823/7524
network_acronym_str Poli2
network_name_str Alejandría Repositorio Institucional
repository_id_str
dc.title.spa.fl_str_mv Algoritmo basado en la coloración de grafos para la programación flexible de horarios y salones en una institución universitaria: caso de estudio en Colombia
dc.title.translated.spa.fl_str_mv Graph Coloring-Based Algorithm for Flexible Scheduling of Classes and Rooms in a University Institution: A Case Study in Colombia
title Algoritmo basado en la coloración de grafos para la programación flexible de horarios y salones en una institución universitaria: caso de estudio en Colombia
spellingShingle Algoritmo basado en la coloración de grafos para la programación flexible de horarios y salones en una institución universitaria: caso de estudio en Colombia
Asignación de horarios
Coloración de grafos
Restricciones duras y suaves
Gestión administrativa
Innovación tecnológica - algoritmos
Registro de tiempos - horarios
Graph coloring
Hard and soft restrictions
Schedule assignment
title_short Algoritmo basado en la coloración de grafos para la programación flexible de horarios y salones en una institución universitaria: caso de estudio en Colombia
title_full Algoritmo basado en la coloración de grafos para la programación flexible de horarios y salones en una institución universitaria: caso de estudio en Colombia
title_fullStr Algoritmo basado en la coloración de grafos para la programación flexible de horarios y salones en una institución universitaria: caso de estudio en Colombia
title_full_unstemmed Algoritmo basado en la coloración de grafos para la programación flexible de horarios y salones en una institución universitaria: caso de estudio en Colombia
title_sort Algoritmo basado en la coloración de grafos para la programación flexible de horarios y salones en una institución universitaria: caso de estudio en Colombia
dc.creator.fl_str_mv Leal Figueredo, Andrés David
dc.contributor.advisor.none.fl_str_mv Chauta Torres, José Manuel
dc.contributor.author.none.fl_str_mv Leal Figueredo, Andrés David
dc.subject.proposal.spa.fl_str_mv Asignación de horarios
Coloración de grafos
Restricciones duras y suaves
topic Asignación de horarios
Coloración de grafos
Restricciones duras y suaves
Gestión administrativa
Innovación tecnológica - algoritmos
Registro de tiempos - horarios
Graph coloring
Hard and soft restrictions
Schedule assignment
dc.subject.lemb.spa.fl_str_mv Gestión administrativa
Innovación tecnológica - algoritmos
Registro de tiempos - horarios
dc.subject.keywords.spa.fl_str_mv Graph coloring
Hard and soft restrictions
Schedule assignment
description La asignación de horarios y salones en instituciones universitarias es un problema complejo clasificado como NP-Completo, debido a la interdependencia de variables y restricciones asociadas. Este trabajo presenta el diseño de un algoritmo basado en la coloración de grafos para la programación eficaz y flexible de horarios en la Institución Universitaria Politécnico Grancolombiano. El modelo propuesto aborda restricciones estrictas y opcionales, representando las sesiones de los cursos como vértices de un grafo no dirigido, con conflictos definidos por aristas. Los resultados incluyen la caracterización de variables, el diseño del algoritmo con una complejidad temporal cuadrática para una parte del problema y una normalización preliminar de datos. Se destaca la flexibilidad del enfoque mediante la asignación de espacios libres por tipo de salón y la aproximación a restricciones suaves, como la programación consecutiva y la asignación en un mismo campus. Las conclusiones proponen mejoras futuras, como la incorporación de la disponibilidad de profesores y el desarrollo de una interfaz gráfica para visualizar horarios. Este estudio contribuye al desarrollo de soluciones flexibles y adaptables en la programación académica universitaria.
publishDate 2024
dc.date.issued.none.fl_str_mv 2024-12-05
dc.date.accessioned.none.fl_str_mv 2025-01-30T16:34:40Z
dc.date.available.none.fl_str_mv 2025-01-30T16:34:40Z
dc.type.spa.fl_str_mv bachelorThesis
dc.type.local.spa.fl_str_mv Tesis/Trabajo de grado - Monografía - Pregrado
dc.type.driver.spa.fl_str_mv info:eu-repo/semantics/bachelorThesis
dc.type.coar.spa.fl_str_mv http://purl.org/coar/resource_type/c_7a1f
dc.type.hasversion.none.fl_str_mv info:eu-repo/semantics/acceptedVersion
dc.type.redcol.none.fl_str_mv https://purl.org/redcol/resource_type/TP
dc.type.version.spa.fl_str_mv info:eu-repo/semantics/acceptedVersion
format http://purl.org/coar/resource_type/c_7a1f
status_str acceptedVersion
dc.identifier.uri.none.fl_str_mv http://hdl.handle.net/10823/7524
dc.identifier.instname.spa.fl_str_mv instname:Politécnico Grancolombiano
dc.identifier.reponame.spa.fl_str_mv reponame:Alejandría Repositorio Comunidad
dc.identifier.repourl.spa.fl_str_mv repourl:http://alejandria.poligran.edu.co
url http://hdl.handle.net/10823/7524
identifier_str_mv instname:Politécnico Grancolombiano
reponame:Alejandría Repositorio Comunidad
repourl:http://alejandria.poligran.edu.co
dc.language.iso.spa.fl_str_mv spa
language spa
dc.relation.references.spa.fl_str_mv F. Zabidee y M. H. M. Adnan, «Optimization in University Student Timetables: A Comprehensive Literature Review,» Journal of Advanced Research in Applied Sciences and Engineering Technology, p. 14 – 43, 2024.
P. Nandal, A. Satyawali, D. Sachdeva y A. S. Tomar, «Graph Coloring based Scheduling Algorithm to automatically generate College Course Timetable,» 2021 11th International Conference on Cloud Computing, Data Science & Engineering (Confluence), pp. 210-214, 2021.
Avinash, R. Jain y R. Kumar, «University Time Table Scheduling Using Graph Coloring Technique,» ResearchGate, 2018.
V. Donderia y P. K. Jana, «A novel scheme for graph coloring,» Procedia Technology, vol. 4, pp. 261-266, 1 2012.
D. Brélaz, «New methods to color the vertices of a graph,» Communications of the ACM, vol. 22, nº 4, pp. 251-256, 4 1979.
N. Poddar y B. Mondal, «AN INSTRUCTION ON COURSE TIMETABLE SCHEDULING APPLYING GRAPH COLORING APPROACH,» International Journal of Recent Scientific Research, vol. 9, nº 2, pp. 23939-23945, 2 2018.
M. Assi, B. Halawi y R. A. Haraty, «Genetic Algorithm Analysis using the Graph Coloring Method for Solving the University Timetable Problem,» Procedia Computer Science, p. 899 – 906, 2018.
T. W. Ekanayake, P. Subasinghe, S. Ragel, A. Gamage y S. Attanayaka, «Intelligent Timetable Scheduler: A Comparison of Genetic, Graph Coloring, Heuristic and Iterated Local Search Algorithms,» 2019 International Conference on Advancements in Computing, ICAC 2019, p. 85 – 90, 2019.
R. K. J. Bendi, T. Sunarni y A. Alfian, «Using Graph Coloring For University Timetable Problem,» International Journal of Science and Research, vol. 7, nº 11, pp. 1692-1697, 2018.
A. Muklason, B. A. Nugroho, E. Riksakomara, R. Tyasnurita, F. Mahananto, R. A. Vinarti y M. A. Nuriman, «Flexible Automated Course Timetabling System with Lecturer Preferences Using Hyper-heuristic Algorithm,» ACM International Conference Proceeding Series, p. 258 – 262, 2022.
D. J. A. Welsh y M. B. Powell, «An upper bound for the chromatic number of a graph and its application to timetabling problems,» The Computer Journal, vol. 10, nº 1, pp. 85-86, 1 1967.
M. Laguna y R. Martí, «A GRASP for Coloring Sparse Graphs,» Computational Optimization and Applications, vol. 19, nº 2, pp. 165-178, 1 2001.
B. S. Baker y E. G. Coffman, «Mutual exclusion scheduling,» {Theoretical Computer Science, vol. 162, nº 2, pp. 225-243, 1996.
R. P. Grimaldi, Discrete and combinatorial mathematics, 5 ed., Rose-Hulman Institute of Technology: Addison Wesley, 2004.
A. Laaksonen, Competitive Programmer's Handbook, Helsinki: CSES, 2018.
R. Lewis, A Guide to Graph Colouring, UK: Springer, 2015.
E. Bampis, A. Kononov, G. Lucarelli y I. Milis, «Bounded max-colorings of graphs,» Journal of Discrete Algorithms, p. 56 – 68, 2014.
dc.rights.coar.fl_str_mv http://purl.org/coar/access_right/c_abf2
dc.rights.creativecommons.spa.fl_str_mv Atribución-NoComercial-SinDerivadas 2.5 Colombia
rights_invalid_str_mv Atribución-NoComercial-SinDerivadas 2.5 Colombia
http://purl.org/coar/access_right/c_abf2
dc.format.mimetype.spa.fl_str_mv application/pdf
dc.coverage.spatial.none.fl_str_mv Bogotá D.C.
dc.publisher.program.spa.fl_str_mv Ingeniería de Sistemas
dc.publisher.faculty.spa.fl_str_mv Facultad de ingeniería y Diseño e Innovación
institution Institución Universitaria Politécnico Grancolombiano
bitstream.url.fl_str_mv https://alejandria.poligran.edu.co/bitstream/10823/7524/4/Tesis%20v3%20corregida.pdf.jpg
https://alejandria.poligran.edu.co/bitstream/10823/7524/2/license.txt
https://alejandria.poligran.edu.co/bitstream/10823/7524/3/Tesis%20v3%20corregida.pdf
bitstream.checksum.fl_str_mv 96915179409d41c3726741de107ebac8
8a4605be74aa9ea9d79846c1fba20a33
817ba113d78a28da6720ae6631b0787c
bitstream.checksumAlgorithm.fl_str_mv MD5
MD5
MD5
repository.name.fl_str_mv Repositorio Comunidad Politecnico Grancolombiano
repository.mail.fl_str_mv dspace@poligran.edu.co
_version_ 1851058972719579136
spelling Chauta Torres, José ManuelLeal Figueredo, Andrés DavidBogotá D.C.2025-01-30T16:34:40Z2025-01-30T16:34:40Z2024-12-05http://hdl.handle.net/10823/7524instname:Politécnico Grancolombianoreponame:Alejandría Repositorio Comunidadrepourl:http://alejandria.poligran.edu.coLa asignación de horarios y salones en instituciones universitarias es un problema complejo clasificado como NP-Completo, debido a la interdependencia de variables y restricciones asociadas. Este trabajo presenta el diseño de un algoritmo basado en la coloración de grafos para la programación eficaz y flexible de horarios en la Institución Universitaria Politécnico Grancolombiano. El modelo propuesto aborda restricciones estrictas y opcionales, representando las sesiones de los cursos como vértices de un grafo no dirigido, con conflictos definidos por aristas. Los resultados incluyen la caracterización de variables, el diseño del algoritmo con una complejidad temporal cuadrática para una parte del problema y una normalización preliminar de datos. Se destaca la flexibilidad del enfoque mediante la asignación de espacios libres por tipo de salón y la aproximación a restricciones suaves, como la programación consecutiva y la asignación en un mismo campus. Las conclusiones proponen mejoras futuras, como la incorporación de la disponibilidad de profesores y el desarrollo de una interfaz gráfica para visualizar horarios. Este estudio contribuye al desarrollo de soluciones flexibles y adaptables en la programación académica universitaria.RESUMEN... 7 INTRODUCCIÓN... 8 JUSTIFICACIÓN Y ANTECEDENTES... 9 OBJETIVO GENERAL... 14 OBJETIVOS ESPECÍFICOS... 14 ALCANCE... 14 MARCO TEÓRICO... 16 GRAFO... 16 DIRECCIÓN DE ARISTAS... 16 TRAYECTORIA (WALK)... 16 CAMINO (PATH)... 17 CONECTIVIDAD DE GRAFO... 17 GRADO Y ADYACENCIA DE VÉRTICES... 17 REPRESENTACIÓN COMPUTACIONAL... 17 MATRIZ DE ADYACENCIA... 17 LISTA DE ADYACENCIA... 18 PROBLEMA DE COLORACIÓN... 18 PROPIEDADES DE COLORACIÓN... 18 COMPLEJIDAD COMPUTACIONAL (NP COMPLETO)... 19 METODOLOGÍA... 21 CARACTERIZACIÓN DE PARÁMETROS... 21 PROGRAM (PROGRAMA ACADÉMICO)... 21 CAMPUS... 21 BUILDING (EDIFICIO)... 21 ROOM TYPE (TIPO DE SALÓN)... 22 ROOM (SALÓN)... 22 SUBJECT (ASIGNATURA)... 22 CURRICULUM (PLAN DE ESTUDIOS)... 22 SESSION (SESIÓN)... 22 COURSE (GRUPO DE CURSO)... 23 TEACHER (PROFESOR/A)... m23 COURSE – SESSION – TEACHER (GRUPO DE CURSO – SESIÓN – PROFESOR/A)... 23 RESTRICCIONES... 24 RESTRICCIONES DURAS... 24 Temporales... 24 Espaciales... 24 RESTRICCIONES SUAVES... 24 Temporales... 24 Espaciales... 24 OBTENCIÓN DE LA INFORMACIÓN... 24 SESIONES POR CURSOS Y PROFESORES... 25 SALONES DISPONIBLES... 26 PLAN DE ESTUDIOS DE PROGRAMAS ACADÉMICOS... 26 OTRAS VARIABLES... 26 GENERACIÓN DE LAS ESTRUCTURAS DE DATOS... 27 VARIABLES DE CANTIDAD... 27 LISTA DE ADYACENCIA DE LAS SESIONES... 27 ARREGLO DE ÚLTIMO COLOR CON DISPONIBILIDAD POR TIPO DE SALÓN... 28 MATRIZ DE OCUPACIÓN ACTUAL DE TIPOS DE SALÓN POR COLOR... 28 ARREGLO DE PORCENTAJES DE OCUPACIÓN MAXIMA POR TIPO DE SALÓN... 28 ARREGLO DE DISPONIBILIDAD POR TIPO DE SALÓN... 28 ARREGLO DE OCUPACIÓN MAXIMA POR TIPO DE SALÓN... 28 ARREGLO DE CLASES DE COLORES... 28 MATRIZ DE COLORES ASIGNADOS A VÉRTICES... 28 ARREGLO DE CAMPUS OBLIGATORIOS POR VÉRTICE... 28 ARREGLO DE SALONES POR TIPO DE SALÓN... 29 ORDEN DE LOS BLOQUES DE TIEMPO... 29 ORDEN EN LA ASIGNACIÓN DE SALONES... 29 ALGORITMO... 30 CREACIÓN DE VARIABLES... 30 COLORACIÓN DE VÉRTICES DE UN MISMO NÚMERO DE BLOQUES DE TIEMPO... 30 COLORACIÓN DE GRAFO... 33 ASIGNACION DE SALON DE CAMPUS A UNA SESION... 34 CALCULAR CAMPUS UNICO DE ADYACENTE EN BLOQUE CONSECUTIVO... 35 ASIGNAR SALONES... 36 RESULTADOS Y DISCUSIÓN... 38 ESPECIFICACIÓN DE PARÁMETROS... 38 RESULTADOS... 38 CONCLUSIONES... 39 TRABAJO FUTURO... 39 REFERENCIAS... 40The allocation of schedules and classrooms in university institutions is a complex problem classified as NP-Complete, due to the interdependence of associated variables and constraints. This paper presents the design of an algorithm based on graph coloring for the effective and flexible scheduling of classes at the Politécnico Grancolombiano University Institution. The proposed model addresses both strict and optional constraints, representing course sessions as vertices of an undirected graph, with conflicts defined by edges. The results include the characterization of variables, the design of the algorithm with quadratic time complexity for part of the problem, and a preliminary data normalization. The flexibility of the approach is highlighted through the allocation of free spaces by room type and the approximation to soft constraints, such as consecutive scheduling and assignment on the same campus. The conclusions propose future improvements, such as incorporating the availability of professors and developing a graphical interface to visualize schedules. This study contributes to the development of flexible and adaptable solutions in university academic scheduling.application/pdfspaAlgoritmo basado en la coloración de grafos para la programación flexible de horarios y salones en una institución universitaria: caso de estudio en ColombiaGraph Coloring-Based Algorithm for Flexible Scheduling of Classes and Rooms in a University Institution: A Case Study in ColombiabachelorThesisTesis/Trabajo de grado - Monografía - Pregradoinfo:eu-repo/semantics/bachelorThesishttp://purl.org/coar/resource_type/c_7a1finfo:eu-repo/semantics/acceptedVersionhttps://purl.org/redcol/resource_type/TPinfo:eu-repo/semantics/acceptedVersionAsignación de horariosColoración de grafosRestricciones duras y suavesGestión administrativaInnovación tecnológica - algoritmosRegistro de tiempos - horariosGraph coloringHard and soft restrictionsSchedule assignmentF. Zabidee y M. H. M. Adnan, «Optimization in University Student Timetables: A Comprehensive Literature Review,» Journal of Advanced Research in Applied Sciences and Engineering Technology, p. 14 – 43, 2024.P. Nandal, A. Satyawali, D. Sachdeva y A. S. Tomar, «Graph Coloring based Scheduling Algorithm to automatically generate College Course Timetable,» 2021 11th International Conference on Cloud Computing, Data Science & Engineering (Confluence), pp. 210-214, 2021.Avinash, R. Jain y R. Kumar, «University Time Table Scheduling Using Graph Coloring Technique,» ResearchGate, 2018.V. Donderia y P. K. Jana, «A novel scheme for graph coloring,» Procedia Technology, vol. 4, pp. 261-266, 1 2012.D. Brélaz, «New methods to color the vertices of a graph,» Communications of the ACM, vol. 22, nº 4, pp. 251-256, 4 1979.N. Poddar y B. Mondal, «AN INSTRUCTION ON COURSE TIMETABLE SCHEDULING APPLYING GRAPH COLORING APPROACH,» International Journal of Recent Scientific Research, vol. 9, nº 2, pp. 23939-23945, 2 2018.M. Assi, B. Halawi y R. A. Haraty, «Genetic Algorithm Analysis using the Graph Coloring Method for Solving the University Timetable Problem,» Procedia Computer Science, p. 899 – 906, 2018.T. W. Ekanayake, P. Subasinghe, S. Ragel, A. Gamage y S. Attanayaka, «Intelligent Timetable Scheduler: A Comparison of Genetic, Graph Coloring, Heuristic and Iterated Local Search Algorithms,» 2019 International Conference on Advancements in Computing, ICAC 2019, p. 85 – 90, 2019.R. K. J. Bendi, T. Sunarni y A. Alfian, «Using Graph Coloring For University Timetable Problem,» International Journal of Science and Research, vol. 7, nº 11, pp. 1692-1697, 2018.A. Muklason, B. A. Nugroho, E. Riksakomara, R. Tyasnurita, F. Mahananto, R. A. Vinarti y M. A. Nuriman, «Flexible Automated Course Timetabling System with Lecturer Preferences Using Hyper-heuristic Algorithm,» ACM International Conference Proceeding Series, p. 258 – 262, 2022.D. J. A. Welsh y M. B. Powell, «An upper bound for the chromatic number of a graph and its application to timetabling problems,» The Computer Journal, vol. 10, nº 1, pp. 85-86, 1 1967.M. Laguna y R. Martí, «A GRASP for Coloring Sparse Graphs,» Computational Optimization and Applications, vol. 19, nº 2, pp. 165-178, 1 2001.B. S. Baker y E. G. Coffman, «Mutual exclusion scheduling,» {Theoretical Computer Science, vol. 162, nº 2, pp. 225-243, 1996.R. P. Grimaldi, Discrete and combinatorial mathematics, 5 ed., Rose-Hulman Institute of Technology: Addison Wesley, 2004.A. Laaksonen, Competitive Programmer's Handbook, Helsinki: CSES, 2018.R. Lewis, A Guide to Graph Colouring, UK: Springer, 2015.E. Bampis, A. Kononov, G. Lucarelli y I. Milis, «Bounded max-colorings of graphs,» Journal of Discrete Algorithms, p. 56 – 68, 2014.Ingeniería de SistemasFacultad de ingeniería y Diseño e InnovaciónAtribución-NoComercial-SinDerivadas 2.5 Colombiahttp://purl.org/coar/access_right/c_abf2THUMBNAILTesis v3 corregida.pdf.jpgTesis v3 corregida.pdf.jpgIM Thumbnailimage/jpeg4624https://alejandria.poligran.edu.co/bitstream/10823/7524/4/Tesis%20v3%20corregida.pdf.jpg96915179409d41c3726741de107ebac8MD54open accessLICENSElicense.txtlicense.txttext/plain; charset=utf-81748https://alejandria.poligran.edu.co/bitstream/10823/7524/2/license.txt8a4605be74aa9ea9d79846c1fba20a33MD52open accessORIGINALTesis v3 corregida.pdfTesis v3 corregida.pdfapplication/pdf1407912https://alejandria.poligran.edu.co/bitstream/10823/7524/3/Tesis%20v3%20corregida.pdf817ba113d78a28da6720ae6631b0787cMD53open access10823/7524oai:alejandria.poligran.edu.co:10823/75242025-01-31 03:00:14.819open accessRepositorio Comunidad Politecnico Grancolombianodspace@poligran.edu.coTk9URTogUExBQ0UgWU9VUiBPV04gTElDRU5TRSBIRVJFClRoaXMgc2FtcGxlIGxpY2Vuc2UgaXMgcHJvdmlkZWQgZm9yIGluZm9ybWF0aW9uYWwgcHVycG9zZXMgb25seS4KCk5PTi1FWENMVVNJVkUgRElTVFJJQlVUSU9OIExJQ0VOU0UKCkJ5IHNpZ25pbmcgYW5kIHN1Ym1pdHRpbmcgdGhpcyBsaWNlbnNlLCB5b3UgKHRoZSBhdXRob3Iocykgb3IgY29weXJpZ2h0Cm93bmVyKSBncmFudHMgdG8gRFNwYWNlIFVuaXZlcnNpdHkgKERTVSkgdGhlIG5vbi1leGNsdXNpdmUgcmlnaHQgdG8gcmVwcm9kdWNlLAp0cmFuc2xhdGUgKGFzIGRlZmluZWQgYmVsb3cpLCBhbmQvb3IgZGlzdHJpYnV0ZSB5b3VyIHN1Ym1pc3Npb24gKGluY2x1ZGluZwp0aGUgYWJzdHJhY3QpIHdvcmxkd2lkZSBpbiBwcmludCBhbmQgZWxlY3Ryb25pYyBmb3JtYXQgYW5kIGluIGFueSBtZWRpdW0sCmluY2x1ZGluZyBidXQgbm90IGxpbWl0ZWQgdG8gYXVkaW8gb3IgdmlkZW8uCgpZb3UgYWdyZWUgdGhhdCBEU1UgbWF5LCB3aXRob3V0IGNoYW5naW5nIHRoZSBjb250ZW50LCB0cmFuc2xhdGUgdGhlCnN1Ym1pc3Npb24gdG8gYW55IG1lZGl1bSBvciBmb3JtYXQgZm9yIHRoZSBwdXJwb3NlIG9mIHByZXNlcnZhdGlvbi4KCllvdSBhbHNvIGFncmVlIHRoYXQgRFNVIG1heSBrZWVwIG1vcmUgdGhhbiBvbmUgY29weSBvZiB0aGlzIHN1Ym1pc3Npb24gZm9yCnB1cnBvc2VzIG9mIHNlY3VyaXR5LCBiYWNrLXVwIGFuZCBwcmVzZXJ2YXRpb24uCgpZb3UgcmVwcmVzZW50IHRoYXQgdGhlIHN1Ym1pc3Npb24gaXMgeW91ciBvcmlnaW5hbCB3b3JrLCBhbmQgdGhhdCB5b3UgaGF2ZQp0aGUgcmlnaHQgdG8gZ3JhbnQgdGhlIHJpZ2h0cyBjb250YWluZWQgaW4gdGhpcyBsaWNlbnNlLiBZb3UgYWxzbyByZXByZXNlbnQKdGhhdCB5b3VyIHN1Ym1pc3Npb24gZG9lcyBub3QsIHRvIHRoZSBiZXN0IG9mIHlvdXIga25vd2xlZGdlLCBpbmZyaW5nZSB1cG9uCmFueW9uZSdzIGNvcHlyaWdodC4KCklmIHRoZSBzdWJtaXNzaW9uIGNvbnRhaW5zIG1hdGVyaWFsIGZvciB3aGljaCB5b3UgZG8gbm90IGhvbGQgY29weXJpZ2h0LAp5b3UgcmVwcmVzZW50IHRoYXQgeW91IGhhdmUgb2J0YWluZWQgdGhlIHVucmVzdHJpY3RlZCBwZXJtaXNzaW9uIG9mIHRoZQpjb3B5cmlnaHQgb3duZXIgdG8gZ3JhbnQgRFNVIHRoZSByaWdodHMgcmVxdWlyZWQgYnkgdGhpcyBsaWNlbnNlLCBhbmQgdGhhdApzdWNoIHRoaXJkLXBhcnR5IG93bmVkIG1hdGVyaWFsIGlzIGNsZWFybHkgaWRlbnRpZmllZCBhbmQgYWNrbm93bGVkZ2VkCndpdGhpbiB0aGUgdGV4dCBvciBjb250ZW50IG9mIHRoZSBzdWJtaXNzaW9uLgoKSUYgVEhFIFNVQk1JU1NJT04gSVMgQkFTRUQgVVBPTiBXT1JLIFRIQVQgSEFTIEJFRU4gU1BPTlNPUkVEIE9SIFNVUFBPUlRFRApCWSBBTiBBR0VOQ1kgT1IgT1JHQU5JWkFUSU9OIE9USEVSIFRIQU4gRFNVLCBZT1UgUkVQUkVTRU5UIFRIQVQgWU9VIEhBVkUKRlVMRklMTEVEIEFOWSBSSUdIVCBPRiBSRVZJRVcgT1IgT1RIRVIgT0JMSUdBVElPTlMgUkVRVUlSRUQgQlkgU1VDSApDT05UUkFDVCBPUiBBR1JFRU1FTlQuCgpEU1Ugd2lsbCBjbGVhcmx5IGlkZW50aWZ5IHlvdXIgbmFtZShzKSBhcyB0aGUgYXV0aG9yKHMpIG9yIG93bmVyKHMpIG9mIHRoZQpzdWJtaXNzaW9uLCBhbmQgd2lsbCBub3QgbWFrZSBhbnkgYWx0ZXJhdGlvbiwgb3RoZXIgdGhhbiBhcyBhbGxvd2VkIGJ5IHRoaXMKbGljZW5zZSwgdG8geW91ciBzdWJtaXNzaW9uLgo=