Please use this identifier to cite or link to this item: https://hdl.handle.net/1822/83246

Full metadata record
DC FieldValueLanguage
dc.contributor.advisorOliveira, José Nuno Fonsecapor
dc.contributor.authorPinho, Alexandre Mendonçapor
dc.date.accessioned2023-03-15T11:22:24Z-
dc.date.available2023-03-15T11:22:24Z-
dc.date.issued2022-
dc.date.submitted2022-
dc.identifier.urihttps://hdl.handle.net/1822/83246-
dc.descriptionDissertação mestrado integrado em Informatics Engineeringpor
dc.description.abstractThe 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.abstractO 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.sponsorshipThis 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/2020por
dc.language.isoengpor
dc.relationinfo:eu-repo/grantAgreement/FCT/6817 - DCRRNI ID/UIDB%2F50014%2F2020/PTpor
dc.rightsopenAccesspor
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/por
dc.subjectGreedy algorithmpor
dc.subjectDynamic programmingpor
dc.subjectAlgebra of programmingpor
dc.subjectAlgoritmo greedypor
dc.subjectProgramação dinâmicapor
dc.subjectÁlgebra da programaçãopor
dc.titleGreedy and dynamic programming by calculationpor
dc.typemasterThesiseng
dc.identifier.tid203231392por
thesis.degree.grantorUniversidade do Minhopor
sdum.degree.grade19 valorespor
sdum.uoeiEscola de Engenhariapor
dc.subject.fosEngenharia e Tecnologia::Engenharia Eletrotécnica, Eletrónica e Informáticapor
Appears in Collections:BUM - Dissertações de Mestrado
DI/CCTC - Dissertações de Mestrado (master thesis)

Files in This Item:
File Description SizeFormat 
Alexandre-Mendonça-Pinho-dissertação-final.pdf2,04 MBAdobe PDFView/Open

This item is licensed under a Creative Commons License Creative Commons

Partilhe no FacebookPartilhe no TwitterPartilhe no DeliciousPartilhe no LinkedInPartilhe no DiggAdicionar ao Google BookmarksPartilhe no MySpacePartilhe no Orkut
Exporte no formato BibTex mendeley Exporte no formato Endnote Adicione ao seu ORCID