¡Se me pisan los horarios!

viernes, 20 de febrero de 2009
Un grafo es esencialmente un dibujito que consta de bolitas y rayitas. Detrás de su inocente aspecto, los grafos ocultan poderosas herramientas matemáticas para resolver problemas muy comunes. Por su naturaleza simple, son una buena muestra de que la matemática no trata solamente de números.

El plan de carrera de Ciencias de la Computación es un poco peliagudo. La carrera está prevista para hacerse en 5 años, a los que se suma el Ciclo Básico Común para lograr un total de 6. Este cuatrimestre (el primero de mi cuarto año en la facultad) me toca una situación que hasta ahora vine esquivando por poco.

Resulta que si bien el plan indica que en este año deben cursarse 4 materias obligatorias y 2 optativas, mis planes de hacer 3 obligatorias en el primer cuatrimestre se ven frustrados por la superposición de horarios. Las materias se superponen solamente una hora, con lo cual parecería ser que alguien intentó (sin éxito) que esto no ocurra.

¿Y ahora quién podrá defenderme?

Con mis planes aparentemente arruinados por la burocracia, me veo en la disyuntiva de elegir qué cursar. Tengo una serie de problemas: hay algunas materias cuyos horarios se superponen, otras que no me interesan, otras que me quiero sacar de encima y al menos una que la tengo que cursar sí o sí porque una materia del segundo cuatrimestre la requiere.

Este problema es un caso típico de algo que se resuelve de forma sencilla utilizando grafos. Lo primero que hay que hacer es modelar la información que tengo, que son materias, días y horarios. El grafo que propongo tiene una bolita o nodo por cada materia, y una rayita o eje une a dos materias cuando los horarios de éstas se superponen.

Para construir el grafo voy a usar un pequeño pedazo de código que a partir de los horarios decide si dos materias se superponen o no. A continuación este programa produce un archivo dot, que utilizando GraphViz puedo representar como imagen. Si me limito a las materias que puedo cursar en este momento (obviando las que ya hice, y las que todavía no puedo hacer), me queda algo así:



Puse de color verde las materias obligatorias, y la única materia que tengo que cursar obligadamente es Paradigmas de Lenguajes de Programación, ya que Ingeniería de Software II depende de ella.

El dibujo tiene una complejidad muy alta, ya que hay muchas materias. Si miran con cuidado verán que hay una línea que une a Bases de Datos con Teoría de Lenguajes, ambas de color verde. Por lo tanto, estas dos materias tienen sus horarios superpuestos y no puedo cursar ambas a la vez.

Una cualidad interesante es que el dibujo de arriba contiene toda la información necesaria para resolver el problema: los días de la semana, las horas, la aritmética, los feriados y la mar en coche desaparecieron de la vista. Esta capacidad de abstracción es un rasgo fundamental del uso de grafos.

¿Qué estamos buscando?

Necesito encontrar un conjunto de materias (bolitas en el grafo) que no tengan líneas entre sí. Esto se llama, en términos de grafos, un conjunto independiente. Existen muchos conjuntos independientes, y uno muy sencillo es simplemente tomar una materia sola. Claro que si curso una sola materia por cuatrimestre no me voy a recibir muy rápido, así que voy a intentar hacer algo mejor.

Me gustaría que el conjunto de materias elegidas tenga las siguientes características:
  • Tiene que ser independiente (sin rayitas entre las bolitas), ya que de otro modo dos materias tendrían sus horarios superpuestos.
  • Tiene que contener a la materia Paradigmas de Lenguajes de Programación (porque de otro modo me atrasa el cuatrimestre que viene)
  • Tiene que contener al menos otra materia obligatoria, sea Teoría de Lenguajes o Bases de Datos
  • Y por último, tiene que tener al menos 3 materias
Si escribo el código de esta restricción en Python, me queda lo siguiente:
def esConveniente(s):
    return esIndependiente(s) and \
           "Paradigmas de Lenguajes de Programación" in s and \
           ("Teoría de Lenguajes" in s or "Bases de Datos" in s) and \
           len(s) >= 3
Para terminar solo es cuestión de dejar que la computadora haga su trabajo, y me diga qué me conviene cursar el cuatrimestre que viene. Tras una (instantánea) corrida, resulta que solo hay 7 combinaciones posibles que reúnen los criterios que describí arriba:
gomo@ciabatta:~$ python inscripcion.py
Formas válidas de cursar materias: 233
Formas de cursar 'convenientes': 7

Paradigmas de Lenguajes de Programación, Lógicas Modales, Bases de Datos
Paradigmas de Lenguajes de Programación, Computación Gráfica, Bases de Datos
Visualización de la Información, Paradigmas de Lenguajes de Programación, Teoría de Lenguajes
Visualización de la Información, Paradigmas de Lenguajes de Programación, Lógicas Modales, Teoría de Lenguajes
Paradigmas de Lenguajes de Programación, Lógicas Modales, Teoría de Lenguajes
Visualización de la Información, Paradigmas de Lenguajes de Programación, Computación Gráfica, Teoría de Lenguajes
Paradigmas de Lenguajes de Programación, Computación Gráfica, Teoría de Lenguajes
Solo me resta elegir la opción que más me divierta, y voilà! Pueden ver el código completo en Python si siguen leyendo este post.

Ver el código completo >>

Código completo en Python

#!/usr/bin/python
# *-* encoding: utf-8 *-*

materias = {'Estadística y Data Mining':               (('Ma',1800,2100), ('Mie',1800,2100)                   ),
            'Inteligencia Artificial':                 (('Lu',1800,2200), ('Ma', 1900,2200)                   ),
            'Metaheurísticas':                         (('Ma',1800,2100),                                     ),
            'Redes Neuronales':                        (('Ma',1800,2100), ('Jue',1800,2100)                   ),
            'Seguridad de la Información':             (('Lu',1800,2200), ('Mie',1800,2200)                   ),
            'Teoría de Juegos':                        (('Lu',1800,2100), ('Mie',1800,2000)                   ),
            'Paradigmas de Lenguajes de Programación': (('Ma',1700,2000), ('Jue',1700,1930)                   ),
            'Bases de Datos':                          (('Mie',1830,2200),('Vie',1700,2230)                   ),
            'Teoría de Lenguajes':                     (('Lu',1800,2100), ('Mie',1700,1930), ('Jue',1930,2200)),
            'Lógicas Modales':                         (('Lu',1400,1800),                                     ),
            'Computación Gráfica':                     (('Lu',1400,1700), ('Vie',1400,1700),                  ),
            'Procesamiento de Lenguaje Natural':       (('Mie',1900,2200),                                    ),
            'Grafos y Tratabilidad Computacional':     (('Ma',1800,2200), ('Jue',1800,2200),                  ),
            'Programación Orientada a Objetos':        (('Lu',1900,2200), ('Mie',1900,2200),                  ),
            'Simulación de Eventos Discretos':         (('Lu',1800,2200), ('Mie',1800,2200),                  ),
            'Visualización de la Información':         (('Vie',1900,2200),                                    ),
}


def sePisan(h1, h2):
    '''Determina si dos horarios se superponen'''
    for c1 in h1:
        for c2 in h2:
            if c1[0] == c2[0]:

                # cual empieza antes?
                if c1[1] <= c2[1]:
                    prim = c1
                    seg = c2
                else:
                    prim = c2
                    seg = c1

                # si la primera termina despues de 
                # que empiece la otra, se pisan
                if prim[2] > seg[1]:
                    return True

    return False


def getDot():
    '''Devuelve un source DOT para el grafo de materias'''
    buf = []
    
    buf.append('graph grafo {')

    # genero IDs para los nodos
    i = 0
    ids = {}
    mats = {}
    for m in materias:
        ids[m] = i
        mats[i] = m
        i += 1

    for i in ids.values():
        buf.append('node%s [label="%s"]' % (i, mats[i]))
 
    ejes = []

    for m1 in materias:
        for m2 in materias:
            if m1 != m2 and sePisan(materias[m1], materias[m2]):
                if not (ids[m2], ids[m1]) in ejes:
                    buf.append('node%s -- node%s' % (ids[m1], ids[m2]))
                    ejes.append((ids[m1], ids[m2]))

    buf.append('}')

    return '\n'.join(buf)


def subconjuntos(s):
    '''Dada una secuencia s devuelve todos los subconjuntos de sus elementos'''
    if s == []:
        return []
    else:
        e = s[0]
        resto = s[1:]

        sin = subconjuntos(resto)
        con = subconjuntos(resto)

        for sub in con:
            sub.append(e)
        con.append([e])

        return sin + con
            

def esIndependiente(s):
    '''Determina si el conjunto de materias es independiente'''
    for m1 in s:
        for m2 in s:
            if m1 != m2:
                if sePisan(materias[m1], materias[m2]):
                    return False
    return True


def esConveniente(s):
    return esIndependiente(s) and \
           "Paradigmas de Lenguajes de Programación" in s and \
           ("Teoría de Lenguajes" in s or "Bases de Datos" in s) and \
           len(s) >= 3
           

if __name__ == '__main__':
    s = subconjuntos(materias.keys())
    
    print "Formas válidas de cursar materias: %s" % len([x for x in s if esIndependiente(x)])
    print "Formas de cursar 'convenientes': %s" % len([x for x in s if esConveniente(x)])
    print

    for c in [x for x in s if esConveniente(x)]:
        print ', '.join(c)

4 comentarios:

Pablo Antonio dijo...

¡Muy bueno! Gracias por compartirlo. Estaría bueno que alguien con ganas se ponga y haga las partes faltantes del sistema:
* la parte que lleve un registro de las materias que ya cursaste, y las que te faltan por cursar
* la parte que obtenga las materias y los horarios para este cuatrimestre

Así, definiendo esConveniente en un ratito uno se ahorraría todos los dolores de cabeza de principio de cuatrimestre.

Saludos.

Pablo Antonio dijo...

En realidad, el sistema también debería tener los datos de las correlatividades para poder distinguir, de las que te faltan, cuáles son las que podés cursar.

Anónimo dijo...

>La carrera está prevista para hacerse en 5 años, a los >que se suma el Ciclo Básico Común para lograr un total >de 6.
YO termine el CBC para Ciencias de la Computacion en exactas. Pregunta: Un estudiante normal (no genio, pero que estudie), cuanto tarda en hacer la carrera ?

GomoX dijo...

Si ya hiciste el CBC, en 5 años te podés recibir, es lo estipulado por el plan. Si realmente le metés pata (haciendo algunas materias en verano, y metiendo optativas desde temprano), lo podés incluso hacer en menos de 4. Sin enloquecerte pero si dedicándote, en 5 años terminás seguro.

Publicar un comentario