Universidade do Minho  

Mapa do Site
Programação com Conecções  de Galois  
Programação com Conecções de Galois
21 de março de 2012
José Nuno Oliveira (Departamento de Informática, Universidade do Minho)
Many problems in algorithm design can be specified in two parts, one defining a broad class of solutions (the "easy'' part) and the other requesting one particular such solution, optimal in some sense (the "hard'' part). This dichotomy is nicely captured by Galois connections (GC) in which one of the adjoints delivers the optimal (hard) solution. We show how the algebra of GCs can be used to reason about such algorithms independently of their implementation, and introduce a binary relational combinator whereby such implementations can be calculated using the (relational) algebra of programming. The approach extends results previously known for so-called "greedy'' and "dynamic''  programming in a way which makes them more systematic and easier to apply.
(joint work with Shin-Cheng Mu, Academia Sinica, Taiwan)
  © 2024 Universidade do Minho  - Termos Legais  - actualizado por CMAT Símbolo de Acessibilidade na Web D.