Buscar


Mostrar el registro sencillo del ítem

dc.rights.license http://creativecommons.org/licenses/by-nc-nd/4.0 es_ES
dc.contributor Arturo González Gutiérrez es_ES
dc.creator Hansel Amadeus Montúffar Otero es_ES
dc.date 2019-08-07
dc.date.accessioned 2023-06-13T21:00:46Z
dc.date.available 2023-06-13T21:00:46Z
dc.date.issued 2019-08-07
dc.identifier.uri https://ri-ng.uaq.mx/handle/123456789/8674
dc.description En esta tesis se estudia el problema de planeación de horarios escolares y se modela mediante el problema de coloración de vértices en un grafo. Un grafo apropiadamente coloreado consiste en una asignación de color a cada uno de sus vértices de modo tal que ningún par de vértices tienen el mismo color si existe una arista que los una. La modelación consiste en representar cada materia mediante un vértice, y si dos materias no se deben ofrecer en el mismo horario, ya que el plan de estudios requiere que ambas materias se deben cursar durante el mismo período académico, o porque existe al menos un estudiante que deba llevar ambas, entonces se construye una arista uniendo esos dos vértices. El número de colores necesarios corresponde al número de ranuras de tiempo requeridas para ofertar las materias que un alumno regular puede tomar, donde cada subconjunto de vértices del mismo color representa las materias que pueden ofrecerse al mismo tiempo sin riesgos de conflicto de horario. Se ha demostrado que el problema de coloración de grafos es NP-completo, por lo que se conjetura que no existe un algoritmo eficiente que produzca soluciones óptimas para cualquier instancia del problema. En esta tesis se discuten una serie de algoritmos metaheurísticos eficientes basados en técnicas de inteligencia artificial, tales como Búsqueda Local, Búsqueda Tabú y Algoritmos Genéticos. Asimismo se exploran algunas heurísticas basadas en criterios que establecen un orden preferente de coloración de vértices. La eficiencia y resultados de estos algoritmos son medidos utilizando instancias de grafos publicadas por el DIMACS (\textit{Center for Discrete Mathematics and Theoretical Computer Science}). Finalmente, se propone un prototipo de sistema en el cual el usuario puede obtener una planeación de horarios de cursos dado el requerimiento de curso a ofertar durante un semestre determinado de acuerdo al plan de estudios en cuestión que establece el orden en que los cursos puedan ser tomados por un estudiante. es_ES
dc.format Adobe PDF es_ES
dc.language.iso spa es_ES
dc.publisher Facultad de Ingeniería es_ES
dc.relation.requires Si es_ES
dc.rights Acceso Abierto es_ES
dc.subject Ingeniería y Tecnología es_ES
dc.subject Ciencias Tecnológicas es_ES
dc.subject Ciencia de los ordenadores es_ES
dc.title Optimización de procesos de planeación de horarios escolares mediante coloración de grafos es_ES
dc.type Tesis de maestría es_ES
dc.creator.tid CURP es_ES
dc.creator.identificador MOOH940730HNENTN04 es_ES
dc.contributor.role Director es_ES
dc.degree.name Maestría en Ciencias en Inteligencia Artificial es_ES
dc.degree.department Facultad de Ingeniería es_ES
dc.degree.level Maestría es_ES


Ficheros en el ítem

Thumbnail
Nombre: RI007598.pdf
Tamaño: 6.057Mb
Formato: PDF
Ver/

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem