Utilize este identificador para referenciar este registo:
https://hdl.handle.net/1822/83246
Registo completo
Campo DC | Valor | Idioma |
---|---|---|
dc.contributor.advisor | Oliveira, José Nuno Fonseca | por |
dc.contributor.author | Pinho, Alexandre Mendonça | por |
dc.date.accessioned | 2023-03-15T11:22:24Z | - |
dc.date.available | 2023-03-15T11:22:24Z | - |
dc.date.issued | 2022 | - |
dc.date.submitted | 2022 | - |
dc.identifier.uri | https://hdl.handle.net/1822/83246 | - |
dc.description | Dissertação mestrado integrado em Informatics Engineering | por |
dc.description.abstract | The mathematical study of the greedy algorithm provides a blueprint for the study of Dynamic Programming (DP), whose body of knowledge is largely unorganized, remaining obscure to a large part of the software engineering community. This study aims to structure this body of knowledge, narrowing the gap between a purely examplebased approach to DP and its scientific foundations. To that effect, matroid theory is leveraged through a pointfree relation algebra, which is applied to greedy and DP problems. A catalogue of such problems is compiled, and a broad characterization of DP algorithms is given. Alongside, the theory underlying the thinning relational operator is explored. | por |
dc.description.abstract | O estudo matemático do algoritmo ganancioso («greedy») serve como guia para o estudo da programação dinâmica, cujo corpo de conhecimento permanece desorganizado e obscuro a uma grande parte da comunidade de engenharia de software. Este estudo visa estruturar esse corpo de conhecimento, fazendo a ponte entre a abordagem popular baseada em exemplos e os métodos mais teóricos da literatura científica. Para esse efeito, a teoria dos matroides é explorada pelo uso de uma álgebra de relações pointfree, e aplicada a problemas «greedy» e de programação dinâmica. Um catálogo de tais problemas é compilado, e é feita uma caraterização geral de algoritmos de programação dinâmica. Em paralelo, é explorada a teoria do combinador relacional de «thinning». | por |
dc.description.sponsorship | This work is financed by National Funds through the Portuguese funding agency, FCT - Fundação para a Ciência e a Tecnologia, within project UIDB/50014/2020 | por |
dc.language.iso | eng | por |
dc.relation | info:eu-repo/grantAgreement/FCT/6817 - DCRRNI ID/UIDB%2F50014%2F2020/PT | por |
dc.rights | openAccess | por |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/ | por |
dc.subject | Greedy algorithm | por |
dc.subject | Dynamic programming | por |
dc.subject | Algebra of programming | por |
dc.subject | Algoritmo greedy | por |
dc.subject | Programação dinâmica | por |
dc.subject | Álgebra da programação | por |
dc.title | Greedy and dynamic programming by calculation | por |
dc.type | masterThesis | eng |
dc.identifier.tid | 203231392 | por |
thesis.degree.grantor | Universidade do Minho | por |
sdum.degree.grade | 19 valores | por |
sdum.uoei | Escola de Engenharia | por |
dc.subject.fos | Engenharia e Tecnologia::Engenharia Eletrotécnica, Eletrónica e Informática | por |
Aparece nas coleções: | BUM - Dissertações de Mestrado DI/CCTC - Dissertações de Mestrado (master thesis) |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
Alexandre-Mendonça-Pinho-dissertação-final.pdf | 2,04 MB | Adobe PDF | Ver/Abrir |
Este trabalho está licenciado sob uma Licença Creative Commons