D. Ho provato a fare gli esercizi di preparazione del secondo compitino
    (http://dna.bio.disco.unimib.it/~bonizzoni/modulo1.html) .
    I dubbi sono i seguenti:
    Es1. Come si costruisce la ricorrenza ?
    Es2 punto (b) Come faccio a spiegare che pur non essendo un matroide, greedy
        fornisce l'ottimo?
 

R. 1.  Per costruire la ricorrenza occorre innanzitutto riflettere (!). Provi a ragionare. L'insieme in questione
e' in realta' una mpla di elementi e ad ogni passo devo decidere se prendere un elemento oppure no.
Piu' precisamente, esiste un sottoinsieme di elementi tra i primi i elementi di costo totale k se e solo se
(1) prendo l'elemento in posizione i,  ma allora deve esistere un sottoinsieme di elementi tra i primi i-1 di costo
totale k - c(e_i), ossia di costo uguale a k meno il costo dell'elemento in posizione i (ma questo se il costo
dell'elemento in posizione i ha valore minore o uguale al costo k);
    oppure
(2) non prendo l'elemento i, ma allora deve esistere un sottoinsieme di elementi tra i primi i-1 di costo
totale k.
La ricorrenza, che ha valori booleani,  puo' essere descritta con

    S(j,t)=S(j-1,t) OR  [S(j-1,t-c(e_j)) AND (c(e_j) <= t)]

La soluzione viene calcolata con S(i,k) e le condizioni alla base sono: S(1,t)=1 se c(e_1)=t, altrimenti
S(1,t)=0. Infine S(j,0)=1(esiste sempre un sottoinsieme dei primi j elementi - quello vuoto - con costo zero).

D (continua). Si segue un po' il ragionamento delle A-liste (elemento preso ed elemento non preso)?
R. Esatto!

R 1.(continua) Passiamo all'esercizio sui matroidi. Innanzitutto, deve convincersi che lo schema greedy
dia l'ottimo per quella funzione peso (provi!). La questione e' che il fatto che ESISTA UNA funzione peso
per cui l'algoritmo greedy dia l'ottimo su un sistema che non e' un matroide, non contraddice, cioe' non nega,
ossia non trova sbagliato, il Teorema di Rado. Infatti questo teorema afferma che se PER OGNI
funzione peso l'algoritmo da' l'ottimo allora ho un matroide (e viceversa, cioe' se ho un sistema che non e' un
matroide, allora non per tutte le funzioni peso ho l'ottimo). Questo vuol dire che posso trovare anche 100000
funzioni peso rispetto alle quali lo schema greedy restituisce l'ottimo, ma questo non dimostra che per ogni
funzione peso cio' sia vero, chiaramente. Dunque l'aver trovato UNA funzione peso rispetto alla quale l'algoritmo trova l'ottimo non e' un problema, rispetto al teorema di Rado. Non e' infatti difficile trovare sia altre funzioni
peso rispetto alle quali l'algoritmo greedy continui a fornire l'ottimo, sia funzioni peso rispetto alle quali
l'algoritmo non da' l'ottimo (confermando il Teorema di Rado: se un sistema non e' un matroide, allora esiste una funzione peso rispetto alla quale l'algoritmo non da' l'ottimo).
 

D2.  Ho notato alcune incongruenze negli esercizi in web di programmazione dinamica
 (http://dna.bio.disco.unimib.it/~bonizzoni/modulo1.html). ESERCIZIO 10:
> Mi sembra che l'equazione di ricorrenza non consideri il caso in cui k,
> vertice intermedio, appartenga sia al cammino da i a j sia
> all'insieme E1.
> io aggiungerei  la seguente riga nell'equazione
> min { D(i,k,k-1,t1) + D(i,k,k-1,t2) } con t1+t2-1<=t , se k appartiene
> al cammino da i a j e se k appartiene ad E1
 

R2.  ma k e' un vertice (dunque non puo' appartenere a E_1 che e' un insieme di archi)!!!!
 

D2 (continua).  Inoltre mi sembra che nella base vi sia un errore.  Penso che dovrebbe essere
> Caso in cui k=0 e t=0:
>                               D(i,j,0,0) = infinito, se (i,j)  appartiene ad E1
>                               D(i,j,0,0) = w(i,j), altrimenti
> Nel testo è scritto esattamente il contrario!

R2 (continua).  su questo ha ragione, bravo! La versione corrente della dispensa e' stata corretta.
 

D3. Sempre sugli esercizi della dispensa. ESERCIZIO 12:
> Quando considera il caso in cui l, vertice intermedio,  è rosso dice che
> il minimo va fatto su k1 + k2 = k-1 .
> Anche guardandolo più volte penso che dovrebbe essere k1 + k2 -1 = k.
>

R3.  ha ragione anche qui!!! La versione corrente e' stata aggiornata pure in questo punto.
 

D3 (continua). Sempre sugli esercizi della dispensa. ESERCIZIO 9:
> La seconda ricorrenza, per M((u,v),0) non dovrebbe avere come sottoproblemi
M((v, left(v)),0)+ M((v, right(v)),1) ?

R3(continua). Uffa, avete trovato anche questo!
E' vero, ma qui era proprio un errore di stampa!!! Da correggere!
 

D4. Ancora sugli esercizi della dispensa. ESERCIZIO 2: perche' non si puo' adattare semplicemente
l'equazione della LCS?

R4. E come si fa? Il problema e' che occorre SAPERE qual e' effettivamente l'ultimo elemento preso,
altrimenti non si puo' cotrollare la crescenza dell'output!!! In altre parole, l'equazione della ricorrenza
usa degli indici che NON rappresentano via via quelli che effettivamente sono presi nella LCS. Se per la LCS
questo non e' un problema, per la LCS crescente lo e'. Non c'e' altro modo per controllare la crescenza
dei valori in comune a due sequenze se non quello di "controllarlo" (!) considerandolo  un parametro da cui
dipende la ricorrenza: dunque occorre specificare che l'indice della ricorrenza corrisponde effettivamente
ad un simbolo che e' stato inserito, cioe' che e' comune.

D5. Ma allora e' lo stesso che per la sequenza ZIG-ZAG (esercizio 3)?
R5. Esatto!

D6. Nell'esercizio 7 (cammini alternati) perche' devo minimizzare su j e non considerare
solo j-1?

R6. Attenzione!!! E dove sta scritto che il precedente del vertice j e' il vertice j-1???????????
Bisogna capire che quello che di solito si fa (perche' usato in Floyd-Warshall) e' di numerare i vertici.
Ma questo non significa che il predecessore del vertice j e' il vertice j-1 e il successore e' j+1!
Difatti NON si sa quale e' il predecessore, anzi, quali sono i predecessori (analogamente per i successori).
Per questo se il cammino e' dal vertice 1 al vertice i, i vertici predecessori di i hanno indice da 1 a i-1.
Piu' semplicemente si puo' scrivere j appartenente all'insieme dei predecessori di i.
 

D7. Come avviene l'ordinamento con il counting sort? Come sono utilizzati
i vettori di appoggio?

R7. Supponiamo di avere in input l'array A[1 ... n] di interi, che sappiamo
essere nel range di possibili valori da 1 a k (minimo valore 1, massimo
valore k). Dobbiamo ordinarli. Usiamo due vettori: B[1 ... n]
conterra' alla fine dell'esecuzione l'array A ordinato, mentre
C[ 1 ..k] e' un array di supporto (ha k posizioni).

Procedo con un esempio di pari passo con l'algoritmo

(ATTENZIONE: se all'esame e' chiesto questo algoritmo, non spiegarlo attraverso
l'esempio, ma ragiona sull'algoritmo in generale. Io faccio cosi' perche'  mi e'
stato chiesto...)

Sia A[1...n]=3,2,3,5,4,3,2 (ossia 7 elementi tra 1 e 5, dunque k=5 e n=7).
Inizialmente C=0,0,0,0,0 (inizializzato).
Poi si scorre A (il ciclo e' fino ad n), e poi, per ogni posizione j di A,
si vede il valore A[j] e si conserva tale valore in C nella posizione A[j]
(che sappiamo essere al piu' k). Percio',
eseguendo l'algoritmo sull'esempio, si ha:

A[1]=3, allora  in C[3] metto 0+1=1. C diventa 0,0,1,0,0
A[2]=2, allora  in C[2] metto 0+1=1. C diventa 0,1,1,0,0
A[3]=3, allora  in C[3] metto 1+1=2. C diventa 0,1,2,0,0
A[4]=5, allora  in C[5] metto 0+1=1. C diventa 0,1,2,0,1
A[5]=4, allora  in C[4] metto 0+1=1. C diventa 0,1,2,1,1
A[6]=3, allora  in C[3] metto 2+1=3. C diventa 0,1,3,1,1
A[7]=2, allora  in C[2] metto 1+1=2. C diventa 0,2,3,1,1

Percio' alla fine di questa iterazione abbiamo che ogni posizione di C
contiene effettivamente il numero degli elementi che in A hanno valore
quella posizione ( 0 elementi di valore 1, 2 elementi di valore 2,
3 elementi di valore 3, 1 elemento di valore 4 e 1 di valore 5).

La seconda iterazione modifica C e fa in modo che ogni
posizione contenga il numero di elementi che in A hanno valore
minore o uguale a quella posizione (ossia 0 elementi minori
o uguali a 1, 2 elementi minori o uguali a 2, 5 elementi minori
o uguali a 3, 6 elementi minori o uguali a 4 e, infine, 7 elementi
minori o uguali a 5). Per far questo basta scorrere di nuovo C e sommare
al numero contenuto in una posizione di C quello contenuto nella
precedente.

Percio' alla fine del for si ha C=0,2,5,6,7.

Perche' si fa questo????? Si capisce dall'ultimo ciclo che
traduce in codice il seguente ragionamento (provo a scriverlo!).
Scandiamo A dalla fine (cosi' manteniamo la stabilita' dell'algoritmo).
Al passo generico, prendiamo l'elemento A[j].
Dove "mettiamo" questo elemento in B?
Cioe' in quale posizione di B?. Analizziamo C, nella posizione A[j]:
sappiamo che
C[A[j]] contiene il numero di elementi che in A hanno valore minore
o uguale ad A[j].....ma tali elementi che in A hanno valore minore
o uguale ad A[j] dove si troveranno in B? Cioe' in quali posizioni
staranno???? Ma staranno proprio prima di A[j]! Allora in B avro'
C[A[j]] -1 posizioni occupate e poi posso mettere A[j]!!!!!!
Percio' A[j] viene messo nella posizione B[C[A[j]]]. Poi
decremento C[A[j]] di 1, perche' ho inserito una occorrenza
di A[j] in B.

Continuiamo con l'esempio:
A[7]=2, C[2]=2 (ci sono 2 elementi minori o = a 2), metto 2=A[7] in B[2].
              Poi C[2]=1 (ossia C=0,1,5,6,7).
A[6]=3, C[3]=5 (ci sono 5 elementi minori o = a 3), metto 3=A[6] in B[5].
              Poi C[3]=4 (ossia C=0,1,4,6,7).
A[5]=4, C[4]=6  (ci sono 6 elementi minori o = a 4), metto 4=A[5] in B[6].
              Poi C[4]=5 (ossia C=0,1,4,5,7).
A[4]=5, C[5]=7  (ci sono 7 elementi minori o = a 5), metto 5=A[4] in B[7].
              Poi C[5]=6 (ossia C=0,1,4,5,6).
A[3]=3, C[3]=4  (ci sono 4 elementi minori o = a 3), metto 3=A[3] in B[4].
              Poi C[3]=3 (ossia C=0,1,3,5,6).
A[2]=2, C[2]=1  (c'e' 1 elemento minori o = a 2), metto 2=A[2] in B[1].
              Poi C[2]=0 (ossia C=0,0,3,5,6).
A[1]=3, C[3]=3  (ci sono 3 elementi minori o = a 3), metto 3=A[1] in B[3].
              Poi C[3]=2 (ossia C=0,0,2,5,6).

Consiglio: di riprovare con un altro esercizio, convincerti della stabilita'
(avevamo tre elementi uguali a 3, ma sono stati inseriti cosi' come comparivano nella sequenza di input...) e dell'uso dei vettori.
 

 D8 Puo' darci esempi di matroidi nei quali non e' verificata
la prima proprieta', ma la seconda si?

R8. Innanzitutto, una precisazione. Vi ricordo che,
dato un sistema I=(E,F) dove E e' un insieme finito non vuoto, F e' una famiglia di sottoinsiemi di E, si dice che I e' un matroide se valgono entrambe le
proprieta', ossia se non vale la prima (I non e' un sistema di indipendenza)
possiamo subito affermare che I non puo' essere un matroide. Cosa
vuol dire questo? Se all'esame vi viene dato un esercizio in cui si
chiede di dimostrare se un sistema I e' un matroide e dimostrate che la
prima proprieta' non e' verificata, potete fermarvi e concludere che I non e' un
matroide.

Questo significa che la vostra domanda non ha molto senso..... :-))))
Ripeto: se non vale la prima proprieta', il sistema non e' un  matroide.
Per essere un matroide, un sistema DEVE essere un sistema di indipendenza (prima
proprieta') e deve valere la seconda proprieta' (scambio).

Comunque, per soddisfare la vostra curiosita', potete controllare
un esempio che vi accenno nella soluzione e che vi scrivo qui sotto
(sistema che non verifica la prima proprieta', ma verifica la seconda...
ripeto...non è un matroide!)

Considerate E insieme degli interi positivi minori di 100 e
F la famiglia dei sottoinsiemi A di E tali che A contiene
ESATTAMENTE un elemento tra {1,2,3,4}.
La prima proprieta' non e' vera: consideriamo un insieme A in F
(dunque A contiene esattamente un elemento in {1,2,3,4} e poi altri
elementi di E che non sono in {1,2,3,4}). E' facile vedere che
esistono dei sottoinsiemi di A che non contengono  quell'elemento, ossia
che non hanno elementi in {1,2,3,4}, percio' esistono sottoinsiemi di A
che non stanno in F. La seconda proprieta' resta vera: difatti,
comunque prendo due insiemi A,B in F tali che |A|=|B|-1,
esiste sempre un elemento b in B (con b che non appartiene
ad A) che posso spostare: sara' proprio quello che sta in B e che
non appartiene a {1,2,3,4} (l'ipotesi
sulla cardinalita' di B garantisce l'esistenza di tale elemento).

Un'ultima cosa: vedete che ho scritto in maiuscolo ESATTAMENTE,
perche' "di solito" questo vincolo fa scattare la falsita' della
prima proprieta'....