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)Tesis doctoral sobre cómputo de reductos y testores típicos
Vladímir Rodríguez-Diez
BUAP, 2022
Resumen: Resumen pendiente.Nuestra nota: Título provisional en esta ficha. Describe la regla de la raíz (fila con menos unos arriba) y propone un meta-algoritmo que cambie de estrategia según la matriz.Ficha completa → 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, 2015Asymptotically optimal dualization algorithms
E. V. Djukova; P. A. Prokofjev
Computational Mathematics and Mathematical Physics, 55(5), 891–905, 2015
https://doi.org/10.1134/S0965542515050103
Resumen: Resumen pendiente.Nuestra nota: Leído completo (traducción al inglés). Es la traducción del artículo de 2014 en Mach. Learn. Data Anal.; no son dos conjuntos de experimentos.Ficha completa →; - la de minimal hitting sets, o transversales mínimas de un hipergrafo, con MMCS y RS Murakami y Uno, 2014Efficient algorithms for dualizing large-scale hypergraphs
Keisuke Murakami; Takeaki Uno
Discrete Applied Mathematics, 170, 83–94, 2014
https://doi.org/10.1016/j.dam.2014.01.012
https://arxiv.org/abs/1102.3813
Resumen: Resumen pendiente.Nuestra nota: Leída la versión final (DAM) y arXiv 1102.3813v2. La numeración de secciones cambia: en DAM la elección de la hiperarista mínima es §3.5 y la poda es §3.6.Ficha completa →.
La equivalencia formal entre testores típicos y transversales mínimas está demostrada Alba-Cabrera et al., 2019On the Relation Between the Concepts of Irreducible Testor and Minimal Transversal
Eduardo Alba-Cabrera; others
IEEE Access, 7, 82809–82816, 2019
https://doi.org/10.1109/ACCESS.2019.2922231
Resumen: Resumen pendiente.Nuestra nota: Teorema 3: los testores irreducibles de una matriz básica son exactamente las transversales mínimas del hipergrafo de sus filas. Referencia de la equivalencia.Ficha completa →. 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.