In questa tesina si descrive e si analizza il processo Balls and Bins per ottenere delle approssimazioni per il carico massimo e il numero di scatole vuote, anche nei casi in cui il numero di palline non coincide con il numero di scatole. Si cita inoltre una variante che permette di ottenere una distribuzione del carico più bilanciata. Infine si discutono alcune applicazioni del processo in algoritmi e strutture dati: bucket sort, hash table e Bloom filters
Problemi di Occupancy e Balanced Allocation
Boscariol, Matteo
2011/2012
Abstract
In questa tesina si descrive e si analizza il processo Balls and Bins per ottenere delle approssimazioni per il carico massimo e il numero di scatole vuote, anche nei casi in cui il numero di palline non coincide con il numero di scatole. Si cita inoltre una variante che permette di ottenere una distribuzione del carico più bilanciata. Infine si discutono alcune applicazioni del processo in algoritmi e strutture dati: bucket sort, hash table e Bloom filtersFile in questo prodotto:
File | Dimensione | Formato | |
---|---|---|---|
tesina.pdf
accesso aperto
Dimensione
402.98 kB
Formato
Adobe PDF
|
402.98 kB | Adobe PDF | Visualizza/Apri |
The text of this website © Università degli studi di Padova. Full Text are published under a non-exclusive license. Metadata are under a CC0 License
Utilizza questo identificativo per citare o creare un link a questo documento:
https://hdl.handle.net/20.500.12608/15034