Modelos matemáticos e problemas de optimização combinatória

• Author(s): Iouliia Skliarova ; António B. Ferrari
• Date: 2012
• Origin: Electrónica e Telecomunicações
• Subject(s): modelos matemáticos; optimização combinatória; dispositivos digitais; algoritmos combinatórios; modelos matemáticos; optimização combinatória; dispositivos digitais; algoritmos combinatórios
• Document Type: Article
• Language: Portuguese

Description

The paper presents the results of the analysis of different models that are used in problems of combinatorial optimization, such as graphs, sets, discrete matrices, and Boolean functions. It is shown that these models can be mutually converted one into another. Many examples of typical combinatorial tasks, which appear at different steps of the design of digital devices, are considered. The majority of these tasks can be solved with the aid of the presented models and the respective combinatorial methods. Finally, different ways of implementation of combinatorial algorithms are analyzed. Este artigo apresenta alguns resultados da análise de modelos matemáticos, tais como conjuntos, grafos, matrizes discretas e funções booleanas, utilizados para a especificação e a resolução de problemas de optimização combinatória. É demonstrado que estes modelos são mutuamente convertíveis uns nos outros. São apresentados também exemplos de problemas combinatórios típicos que surgem na área de projecto de dispositivos digitais. A maioria destes problemas podem ser resolvidos com a ajuda dos modelos referidos, através da aplicação de métodos combinatórios. Por fim, analisam-se diferentes possibilidades da implementação de algoritmos combinatórios.