Please use this identifier to cite or link to this item:
http://repositorio.ufc.br/handle/riufc/70588| Type: | Dissertação |
| Title: | O algoritmo ganancioso: uma introdução à teoria dos matroides |
| Title in English: | The greedy algorithm: an introduction to matroid theory |
| Authors: | Inácio Neto, Raimundo |
| Advisor: | Melo, Marcos Ferreira de |
| Keywords: | Matroides;Dependência linear;Matrizes (matemática);Teoria dos grafos;Algoritmo ganancioso;Matroids;Linear dependence;Matrices (mathematics);Graph theory;Greedy algorithm |
| Issue Date: | 2023 |
| Citation: | INÁCIO NETO, Raimundo. O algoritmo ganancioso: uma introdução à teoria dos matroides. 2023. 27 f. Dissertação (Mestrado Profissional em Matemática em Rede Nacional) - Centro de Ciências, Departamento de Matemática, Universidade Federal do Ceará, Fortaleza, 2023. |
| Abstract in Brazilian Portuguese: | Em Matemática, um matroide é uma estrutura apresentada como uma estrutura geral para o conceito de independência linear. Está, portanto, naturalmente ligado à Álgebra Linear, mas também à Teoria dos Grafos, ao algoritmo ganancioso e à Geometria. (Para várias questões relacionadas com representação). Este trabalho visa estabelecer explicitamente qual a relação dessa estrutura com o algoritmo ganancioso. Partindo de problemas que exigem uma solução otimizada, definimos o conceito de matroide e suas propriedades. Em seguida serão demonstradas através de teoremas e exemplos as relações com matrizes e grafos, assim como alguns tipos de matróides. Por fim, será demonstrado o teorema que consolida a ligação com o algoritmo. |
| Abstract: | In Mathematics, a matroid is a structure presented as a general framework for the concept of linear independence. It is, therefore, naturally linked to Linear Algebra, but also to Graph Theory, the greedy algorithm and Geometry. (For various queries related to representation). This work aims to explicitly establish the relationship between this structure and the greedy algorithm. Starting from problems that require an optimized solution, we define the concept of matroid and its properties. Next, relations with matrices and graphs will be demonstrated, as well as some types of matroids, through theorems and examples. Finally, the theorem that consolidates the connection with the algorithm will be demonstrated. |
| URI: | http://www.repositorio.ufc.br/handle/riufc/70588 |
| Appears in Collections: | PROFMAT - Dissertações defendidas na UFC |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 2023_dis_rinacioneto.pdf | Dissertação de Raimundo Inácio Neto | 524,09 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.