Matematica. La regina delle scienze
 

Problemino di ottimizzazione combinatorica (più lun

piergiorgio.benenati@gmail.com 31 Lug 2017 18:57
Salve,

sto cercando di risolvere un problema, ma purtroppo faccio fatica anche a
modellarlo (ho cercato di usare delle equazioni alle differenze, senza
successo).
Ecco il problema:

Ho un insieme S_0 di n singoletti distinti (i.e, n insiemi distinti, ciascuno
contenente un unico elemento, che chiamiamo "oggetto").

Un processo di fusione degli insiemi contenuti in S opera in modo sequenziale,
in passi distinti. Definiamo S_k come l'insieme S al termine del k-esimo passo.
Abbiamo S_k=S_0.

Ad ogni passo k vengono eseguite in ordine queste tre operazioni:

1) Da S_k vengono tolti a_k<|S_k| insiemi che possono essere scelti in qualsiasi
modo rispettando il vincolo definito nel modo seguente: nessun oggetto può
essere **scelto** più di log_2(n) volte in totale.

Definiamo " **scelto** " nel vincolo appena descritto:
"un oggetto viene **scelto**" se appartiene -- a qualsiasi livello gerarchico di
membership, a un insieme scelto --

(cioè se appartiene a un insieme scelto, oppure se appartiene a un insieme che
appartiene a un insieme scelto, oppure se appartiene a un insieme che appartiene
... che appartiene a un insieme scelto).

---

2) Ognuno degli |S_k|-a_k insiemi rimasti si unisce a uno degli altri rimasti
formando un insieme più grande. Dopo questa fusione abbiamo quindi al massimo
(|S_k|-a_k)/2 insiemi -- oltre agli a_k insiemi tolti al punto (1).

---

3) Gli a_k insiemi tolti da S_k al punto (1) vengono ri-aggiunti a S_k
trasformato nel punto (2), formando così finalmente S_(k+1).

---

Ci terrei molto a dimostrare che, all'aumentare di k, n deve essere almeno
esponenziale in k
(oppure, alternativamente, che per n->oo, k deve essere uguale a O(log n) ).

Ringrazio in anticipo chiunque sia in grado fornirmi qualsiasi tipo di aiuto!
P.

Links
Giochi online
Dizionario sinonimi
Leggi e codici
Ricette
Testi
Webmatica
Hosting gratis
   
 

Matematica. La regina delle scienze | Tutti i gruppi | it.scienza.matematica | Notizie e discussioni matematica | Matematica Mobile | Servizio di consultazione news.