Por favor, use este identificador para citar o enlazar este ítem:
http://repositorio.ufc.br/handle/riufc/70588| Tipo: | Dissertação |
| Título : | O algoritmo ganancioso: uma introdução à teoria dos matroides |
| Título en inglés: | The greedy algorithm: an introduction to matroid theory |
| Autor : | Inácio Neto, Raimundo |
| Tutor: | Melo, Marcos Ferreira de |
| Palabras clave : | Matroides;Dependência linear;Matrizes (matemática);Teoria dos grafos;Algoritmo ganancioso;Matroids;Linear dependence;Matrices (mathematics);Graph theory;Greedy algorithm |
| Fecha de publicación : | 2023 |
| Citación : | 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. |
| Resumen en portugués brasileño: | 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 |
| Aparece en las colecciones: | PROFMAT - Dissertações defendidas na UFC |
Ficheros en este ítem:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| 2023_dis_rinacioneto.pdf | Dissertação de Raimundo Inácio Neto | 524,09 kB | Adobe PDF | Visualizar/Abrir |
Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.