Tesis profesional presentada por Rocío Santillán Rodríguez

Licenciatura en Ingeniería en Sistemas Computacionales. Departamento de Ingeniería en Sistemas Computacionales. Escuela de Ingeniería, Universidad de las Américas Puebla.

Jurado Calificador

Presidente: Mtra. Carolina Yolanda Castañeda Roldán
Vocal y Director: Dr. Mauricio Javier Osorio Galindo
Secretario: Dra. María del Pilar Gómez Gil

Cholula, Puebla, México a 13 de diciembre de 2004.

Table of content

Agradecimientos (archivo pdf, 216 kb)

Capítulo 1. Introduction (archivo pdf, 99 kb)

  • 1.1 Bioinformatics context
  • 1.2 Problem formalization
  • 1.3 Algorithms for set covering

Capítulo 2. Theoretical Frame (archivo pdf, 106 kb)

  • 2.1 Algorithms and Complexity
  • 2.2 State of the Art: Other solutions to the set covering
  • 2.3 Logic programming
  • 2.4 Dynamic programming

Capítulo 3. Algorithms Design (archivo pdf, 147 kb)

  • 3.1 DLV specification
  • 3.2 Exact algorithm
  • 3.3 Polynomial Algorithm using a Greedy Approach
  • 3.4 Dynamic programming approach
  • 3.5 General structure of the implementation

Capítulo 4. Results (archivo pdf, 130 kb)

  • 4.1 Exact algorithm
  • 4.2 Approximation algorithms

Capítulo 5. Conclusions and Future Work (archivo pdf, 70 kb)

Referencias (archivo pdf, 81 kb)

Apéndice A. Algorithms for Set Covering Documentation (archivo pdf, 297 kb)

Apéndice B. User Manual (archivo pdf, 111 kb)

Santillán Rodríguez, R. 2004. Algorithms to Solve Set Covering. Tesis Licenciatura. Ingeniería en Sistemas Computacionales. Departamento de Ingeniería en Sistemas Computacionales, Escuela de Ingeniería, Universidad de las Américas Puebla. Diciembre. Derechos Reservados © 2004.