Please use this identifier to cite or link to this item:
http://hdl.handle.net/11612/4386| Authors: | Ribeiro, Reinaldo da Silva |
| metadata.dc.contributor.advisor: | Carvalho, Rafael Lima de |
| Title: | Alocação de estados quase ótima em máquina de estados finitos utilizando Simulated Annealing |
| Keywords: | Máquina de Estados Finitos;Simulated Annealing;Sistemas Digitais;Metaheurística |
| Issue Date: | 2022 |
| Publisher: | Universidade Federal do Tocantins |
| Citation: | RIBEIRO, Reinaldo da Silva. Alocação de estados quase ótima em máquina de estados finitos utilizando Simulated Annealing. 2022. 16 f. TCC (Graduação) - Curso de Ciência da Computação, Universidade Federal do Tocantins, Palmas, 2022. |
| metadata.dc.description.resumo: | Neste projeto de pesquisa, a aplicação do algoritmo Simulated Annealing para resolver o problema de atribuição de estados em uma máquina de estados finitos foi investigada. O problema de atribuição de estado é um problema clássico em projeto de sistemas digitais e impacta diretamente no custo, tanto de área quanto de energia, no tempo de projeto, por se tratar de um problema NP-Completo. O algoritmo Simulated Annealing foi escolhido por não utilizar populações no espaço de busca da solução, e a literatura traz métodos mais complexos e com maior esforço computacional, portanto o objetivo foi avaliar o impacto na qualidade da solução com um método mais simples . Nos experimentos realizados, a qualidade da solução caiu em menor porcentagem, em média houve uma perda de 14,29%. E o percentual de ganho de processamento foi maior que o porcentual de perda, em média 58,67%. Isso mostra que é possível ter poucas perdas de qualidade com um aumento significativo no desempenho. |
| Abstract: | In this research project, the application of the Simulated Annealing algorithm to solve the state assignment problem in a finite state machine was investigated. The state assignment problem is a classic problem in digital systems design and directly impacts on the cost, both area and power costs, on design time, as it is an NP-Complete problem. The Simulated Annealing algorithm was chosen because it does not use populations in the search space for the solution, and the literature brings more complex methods with greater computational effort, so the objective was to evaluate the impact on the quality of the solution with a simpler method. In the experiments performed, the dropin solution quality was smaller in percentage, on average there was a loss of 14.29%. And the processing gain percentage higher, on average 58.67%. This shows that it is possible to have few quality losses with a significant increase in performance. |
| URI: | http://hdl.handle.net/11612/4386 |
| Appears in Collections: | Ciência da Computação |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Reinaldo da Silva Ribeiro - monografia.pdf | 365.53 kB | Adobe PDF |  View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.