Saltar a contenido

reducts

Este sitio documenta un proyecto de investigación sobre un problema clásico: encontrar todos los reductos de una tabla de datos. Continúa la línea de la tesis doctoral de Vladímir Rodríguez-Diez Rodríguez-Diez, 2022 (tesis) y prepara un artículo con sus asesores.

No hace falta saber nada del tema para leerlo. Los términos se definen en Conceptos básicos, y cada vez que se nombra un algoritmo o un artículo, la cita lleva un botón ▾ que abre los datos de la publicación. El enlace del nombre lleva a la ficha completa del artículo.

El problema en un párrafo

Una tabla de datos describe objetos con atributos. Un reducto es un conjunto mínimo de atributos que basta para distinguir los objetos igual que la tabla completa. Tres comunidades estudian este mismo problema con nombres distintos:

  • la de testores típicos (Cuba y México, desde los años sesenta), con algoritmos como BR, fast-BR y GCreduct;
  • la de dualización de la escuela rusa de Djukova, con OPT, RUNC y RUNC-M Djukova y Prokofjev, 2015;
  • la de minimal hitting sets, o transversales mínimas de un hipergrafo, con MMCS y RS Murakami y Uno, 2014.

La equivalencia formal entre testores típicos y transversales mínimas está demostrada Alba-Cabrera et al., 2019. Lo que no se había hecho es comparar los algoritmos de las tres comunidades entre sí con las mismas matrices y la misma vara. Ese es el centro del proyecto.

Por dónde empezar

Si quieres… Lee
Saber qué hemos encontrado y si da para publicar Descubrimientos
Ver qué falta para el artículo y en qué fecha Metas y avance
Entender el problema desde cero Conceptos básicos
Ver qué hace cada algoritmo y en qué se parecen Mapa de algoritmos y Propiedades de poda
Saber qué se decidió y qué se dejó de afirmar Decisiones y afirmaciones retiradas
Consultar un artículo citado Bibliografía

Convenciones del sitio

  • hecho sale del código o de una medición.
  • inferencia es interpretación nuestra, todavía sin prueba.
  • pendiente está planeado y sin hacer.
  • Los tiempos se midieron en una máquina de 2 núcleos (aarch64) y son orientativos. Por eso también se reportan candidatos evaluados, que no dependen de la máquina.
  • Las notas de trabajo son los documentos originales del proyecto, con fecha. Las páginas de arriba los resumen y enlazan; si hay diferencia, vale la página más reciente.