Vai ai contenuti. | Spostati sulla navigazione | Spostati sulla ricerca | Vai al menu | Contatti | Accessibilità

logo del sistema bibliotecario dell'ateneo di padova

Agnolin, Andrea (2017) Algoritmi per problemi su matroidi e polimatroidi. [Laurea triennale]

Full text disponibile come:

[img]
Preview
PDF
547Kb

Abstract

I matroidi vennero introdotti per dare una descrizione generale all’idea di indipendenza. Tramite i matroidi è possibile descrivere oggetti della combinatoria, dell’algebra lineare, della teoria dei grafi. Nel presente lavoro introduciamo il concetto e mostriamo alcuni utilizzi: nel capitolo 1 affrontiamo il problema di trovare la base di costo massimo e presentiamo l'algoritmo greedy; nel capitolo 2 discutiamo il problema di trovare l'indipendente di cardinalità massima comune a più matroidi. Nell'ultima parte presentiamo una descrizione poliedrale dei matroidi, trattando una loro generalizzazione, i polimatroidi. Vedremo infine degli algoritmi per risolvere in modo efficiente programmi lineari, la regione dei quali sia un polimatroide.»

Item Type:Laurea triennale
Corsi di Laurea Triennale:pre 2012- Facoltà di Scienze MM. FF. NN. > Matematica
Uncontrolled Keywords:ricerca operativa, ottimizzazione, matroidi, polimatroidi, algoritmi
Subjects:Area 01 - Scienze matematiche e informatiche > MAT/02 Algebra
Area 01 - Scienze matematiche e informatiche > MAT/09 Ricerca operativa
Codice ID:54673
Relatore:Di Summa, Marco
Data della tesi:21 April 2017
Biblioteca:Polo di Scienze > Biblioteca di Matematica
Tipo di fruizione per il documento:on-line per i full-text
Tesi sperimentale (Si) o compilativa (No)?:No

Bibliografia

I riferimenti della bibliografia possono essere cercati con Cerca la citazione di AIRE, copiando il titolo dell'articolo (o del libro) e la rivista (se presente) nei campi appositi di "Cerca la Citazione di AIRE".
Le url contenute in alcuni riferimenti sono raggiungibili cliccando sul link alla fine della citazione (Vai!) e tramite Google (Ricerca con Google). Il risultato dipende dalla formattazione della citazione e non da noi.

[1] J. Oxley, \What is a matroid?." https://www.math.lsu.edu/~oxley/survey4. pdf, oct 2014. Vai! Cerca con Google

[2] J. G. Oxley, Matroid Theory. Oxford Graduate Texts in Mathematics, Oxford University Press, 1993. Cerca con Google

[3] B. Korte and J. Vygen, Ottimizzazione Combinatoria: Teoria e Algoritmi. Unitext, Springer, 4 ed., 2011. Cerca con Google

[4] A. Schrijver, Combinatorial Optimization, vol. B. Springer, 2003. Cerca con Google

[5] G. Pap, \A matroid intersection algorthm," EGRES Technical Report n. 2008-10, 2008. Cerca con Google

[6] J. Edmonds, \Matroids and the greedy algorithm," Mathematical Programming 1, pp. 127{136, 1971. Cerca con Google

[7] J. Edmonds, \Submodular functions, matroids, and certain polyhedra," in Cerca con Google

Combinatorial Structure and Their Applications, pp. 69-87, 1970. Cerca con Google

Solo per lo Staff dell Archivio: Modifica questo record