Newsgroup: it.scienza.informatica
Titolo: Domanda NON banale

Salve a tutti.
Volevo avere qualche vostro parere/suggerimento per risolvere questo
questito relativo alla individuazione di un "insieme minimale"
rappresentativo di quello di partenza.
Concentriamoci, per esempio, al caso del superenalotto ed partiamo da un
certo insieme colonnare A
corrispondente allo sviluppo integrale di una serie o tutta dei 90 numeri
potenzialmente selezionabili.
A questo punto dall'insieme A possiamo ottenerne un'altro diciamo B se
applicassimo, per esempio a tutte le colonne dell'insieme di partenza dei
criteri a cui ciascuna colonna dell'insieme derivato B dovrà sottostare.
Questo, schematizzato molto vagamente, è ciò che potrebbe essere
identificato come "Filtro-riduzione".
Oltre a questo modo di procedere, piuttosto basilare, vi sono ovviamente dei
modi, diciamo più "interessanti", matematicamente parlando, che mirano
all'ottenimento di un insieme B che sia, per quanto possibile, il più
piccolo raggruppamento di colonne, appartenenti all'insieme A e che, nel
contempo, sia "rappresentativo" a meno di una "garanzia" dell'insieme di
partenza.
Per esempio se partiamo dalla selezione di 8 numeri diciamo, per semplicità:
1,2,3,4,5,6,7,8 l'insieme A sarebbe rappresentato dalle seguenti 28 colonne:
  1: 1-2-3-4-5-6
  2: 1-2-3-4-5-7
  3: 1-2-3-4-5-8
  4: 1-2-3-4-6-7
.....................
28: 3-4-5-6-7-8
A questo punto se volessimo ottenere un sistema B "sistema minimale"
rappresentativo di A a meno di una garanzia di "5 punti" otterremmo per
esempio un insieme come il seguente:
1: 1-2-3-4-5-6
2: 1-2-3-4-7-8
3: 1-2-5-6-7-8
4: 3-4-5-6-7-8
esso sarà composto da 4 colonne ed ci garantisce, nel caso in cui i sei
numeri estratti(escludiamo il numero jolly per semplicità) siano presenti
fra i nostri 8 prescelti la presenza all'interno del nostro sistema B di
"almeno" una colonna con 5 punti.
Io ho implementato il seguente algoritmo:
 - calcolo una colonna di A;
 - aggiungo la colonna corrente all'insieme
    B se essa non risulta "coperta" a meno
    della garanzia richiesta da qualche altra già
    accettata in B.
Va detto che un'analisi esaustiva sarebbe impensabile infatti nel procedere
innanzi si tiene conto di eventuali salti da effettuare!
Adottanto questo procedimento si ha, come ovvia conseguenza, che l'insieme B
ottenuto sia sempre lo stesso. Questo affermazione potrebbe sembrare ovvia e
banale ma non lo è affatto!
Interessante è notare che variando la disposizione/ordinamento delle colonne
presenti nell'insieme A di partenza con l'algoritmo sopra descritto si
ottengono insiemi B differenti e cio che è maggiormente interessante di
dimensioni anch'esse differenti!!!!
La considerazione, ovvia, risulta essere la seguente: individuato un
algoritmo di riduzione, si ottengono risultati differenti a seconda
"dell'ordine" in cui sono disposte le colonne
da analizzare.
Adesso, il calcolo delle permutazioni ci consente di stabilire su quante
differenti "versioni" dello stesso insieme colonnare è possibile applicare
il procedimento di riduzione. Se si prendesse in esame un insieme generato
da 8 numeri (28 colonne) esse potrebbero essere disposte in
28*27*...*3*2*1=3,05*10E29 circa modi differenti (un numero a 29 cifre!!!).
Quindi, l'algoritmo di riduzione avrebbe potuto fornire un numero enorme di
risultati (alle volte, magari, solo differenti tra loro per l'ordine delle
colonne presenti in ogni riduttore).
Pongo a questo punto una serie di domande:
1)Appare evidente che l'analisi di tutte le  permutazioni in un insieme di
colonne da ridurre (analisi esaustiva) non è, all'atto pratico, proponibile
(per lo meno con i computer oggi disponibili). In che modo sarebbe più
idoneo procedere???? Sarebbe forse bene utilizzare delle tecniche euristiche
per limitare il numero delle permutazioni da analizzare (conseguentemente,
migliore sarà l'euristica individuata, migliore sarà il risultato ottenuto,
sia in termini di colonne presenti nel riduttore, sia in termini di tempo di
elaborazione);in questo caso sapreste indicarne qualcuna????
2)Come ordinare le colonne nell'insieme A per ottenere con l'algoritmo
descritto un insieme B,
"rappresentativo" di A, che sia il più piccolo possibile????
2)E' possibile implementare un'algoritmo che permetta di ottenere il più
piccolo insieme B "rappresentativo" di A e che non sia dipendente dalla
disposizione interna delle colonne nell'insieme A????
3)E' possibile calcolare in anticipo, o per lo meno in assoluto, un
"lower-bound" della dimensione dell'insieme B????
Ciao Berny.
-> it.scienza.informatica (Moderated)
%followup-to
it.scienza.informatica

 "lower-bound" della dimensione dell'insieme B????
A occhio parrebbe di si. Non chiedermi come, però.
Scusa la vaghezza, ma era una cosa che studiavo con carta e penna durante i
viaggi in treno, quando non dormivo, e ora non uso più il treno...
Ciao
Alessandro Monti
