Spazio delle soluzioni

Question 1

Quali strutture dati si utilizzano tipicamente per le funzioni di calcolo combinatorio?

Answer 1

typedef struct l { int *scelte; int n_scelte; } Livello;

int *val; oppure Livello *val;
int *mark;
int *sol;

Question 2

Principio di moltiplicazione: esempio

Answer 2

poké: 3 di una, 2 dell’altro, ecc.

32…

Question 3

Principio di moltiplicazione: codice

Answer 3

int princ_molt(int pos, Livello *val, int *sol, int n, int cnt){
int i;
if(pos >= n){
for(i = 0; i < n; i++) printf(“%d”, sol[i]);
return cnt+1;
}
for(i = 0; i < val[pos].n_scelte; i++){
sol[pos] = val[pos].scelte[i];
cnt = princ_molt(pos+1, val, sol, n, cnt);
}
return cnt;
}

Question 4

Disposizioni semplici: esempio

Answer 4

Raggruppamento k a k, senza ripetizione
n!/(n-k)!

per esempio: quanti numeri di due cifre distinte si possono formare con 4 cifre totali?

Question 5

Disposizioni semplici: codice

Answer 5

int dispiace_semplici(int pos, int val, intsol, int *mark, int k, int n, int cnt){ int i;
if(pos >= k){
// stampa sol
return cnt+1;
}
for (i = 0; i < n; i++){
if (mark[I] == 0){
mark[i] = 1;
sol[pos] = val[I];
cnt = disp_sempl(pos + 1, val, sol, mark, k, n, cnt);
mark[i] = 0;
}
}
return cnt;
}

Question 6

Disposizioni con ripetizione: esempio

Answer 6

elementi k a k, non distinti

n^k;

esempio: quanti sono i numeri binari su 4 bit?
2^4

Question 7

Disposizioni con ripetizione: codice

Answer 7

int disp_rip(int pos, int * val, int *sol, int n, int k, int cnt){
if (pos>=k){
//stampa sol
return cnt+1;
}

for(i = 0; i < n; i++){
sol[pos] = val[I];
cnt = disp_rip(pos+1, val, sol, n, k, cnt);
}
return cnt;
}

Question 8

Permutazioni semplici: esempio

Answer 8

n!

Question 9

Permutazioni con ripetizione: esempio

Answer 9

n!/a!B!…

Question 10

Permutazioni semplici: codice

Answer 10

int permutazioni_semplici(int pos, int val, intsol, int * mark, int n, int cnt){
if (pos>=n){ // stampa return cnt+1;}

for (int i = 0; i < n; i++){
if (mark[I] == 0){
mark[i] = 1;
sol[pos] = val[I];
cnt = permutazioni_semplici(pos +1, val, sol, mark, n, cnt);
mark[i] = 0;
}
}
return cnt;
}

Question 11

Permutazioni con ripetizione: codice

Answer 11

int perm_r(int pos, int *dist_val, int n_dist, int *sol, int *mark, int n, int cnt){
if (pos >= n) {
// stampa
return cnt+1;
}

for(int i = 0; i < n_dist; i++){
if(mark[I] > 0){
mark[i]–;
sol[pos] = dist_val[i];
cnt = perm_r(pos+1, dist_val, n_dist, sol, mark, n, cnt);
mark[i]++;
}
}
return cnt;
}

Question 12

Combinazioni semplici: esempio

Answer 12

in quanti modi si possono stringere la mano 20 persone?

binomiale (20 2)

Question 13

Combinazioni semplici: codice

Answer 13

int comb_s(int pos, int *val, int *sol, int n, int k, int start, int cnt){
if (pos >= k) {…}

for(int i = start; i < n; i ++){
sol[pos] = val[I];
cnt = comb_s(pos+1, val, sol, n, k, I+1, cnt);
}
return cnt;
}

Question 14

Combinazioni con ripetizione: esempio

Answer 14

Date 5 gocce bianche e 5 nere, quanti colori diversi si possono formare mischiando tra loro 5 gocce prese dai due colori?

binomiale (n+k-1)/k

Question 15

Combinazioni con ripetizione: codice

Answer 15

int comb_r(int pos, int *val, int *sol, int n, int k, int start, int cnt){
if (pos >= k) {…}

for(i = start; I < n; i++){
sol[pos] = val[I];
cnt = comb_r(pos+1, val, sol, n, k, start, cnt);
}
return cnt;
}

Question 16

Dato un insieme I, quando i blocchi in cui è diviso sono una sua partizione?

Answer 16

Dato un insieme I e S_i sottoinsiemi ciascuno di k_i elementi, essi sono una partizione di I se:
- ogni blocco non è vuoto
- e sono tutti disgiunti
- e la loro somma dà l’insieme I

Question 17

Data la partizione di un insieme, l’ordine dei blocchi e degli elementi in essi conta?

Answer 17

NO

Question 18

Dato un insieme I, quale può essere il numero complessivo di partizioni?

Answer 18

Il numero complessivo di partizioni è definito dai numeri di Bell: 1, 1, 2, 5, 15, 52

Question 19

Quali modelli ci sono per calcolare l’insieme delle parti?

Answer 19

1. paradigma divide et impera
2. disposizioni ripetute
3. combinazioni semplici

Question 20

Insieme delle parti con paradigma divide et impera, caratteristiche

Answer 20

per k = 0 viene ritornato l’insieme vuoto, per k > 0 l’insieme delle parti per k elementi è l’insieme delle parti per k-1 elementi a cui decido se aggiungere o meno il kesimo elemento -> due rami ricorsivi distinti

Question 21

Insieme delle parti con disposizioni ripetute, caratteristiche

Answer 21

• in sol gli elementi sono o 0 o 1 p
• bisogna scegliere se prendere il k-esimo elemento (sol[pos] = 1) oppure no (sol[pos] = 0) e per questo ci sono due rami ricorsivi distinti

Question 22

Insieme delle parti con combinazioni semplici, caratteristiche

Answer 22

c’è una funzione wrapper che chiama la funzione ricorsiva con k diverso ogni volta (k: numero degli elementi)

Question 23

Come si possono rappresentare le partizioni di un insieme?

Answer 23

• per ogni elemento si indica il blocco a cui appartiene
• dato ogni blocco se ne elencano gli elementi

Question 24

Numero casuale di partizioni con disposizioni ripetute

Answer 24

appunti

Question 25

algoritmo di Er

Answer 25

appunti

Question 26

Quali sono le possibilità per chiudere le ritorsioni quando si vuole una sola soluzione?

Answer 26

1) flag come variabile globale o come parametro by reference
2) funzione ricorsiva che ritorna una valore di successo o fallimento che viene testato

Question 27

cosa si intende per pruning?

Answer 27

è la riduzione dello spazio di ricerca che non porta alla perdita di informazioni o di completezza, ma che scarta a priori i riami dell’albero delle soluzioni che sicuramente falliranno, seguendo vincoli he permettano di non perdere soluzioni

Question 28

metodologie di anticipazione dei vincoli

Answer 28

non c’è una metodologia generale. tipicamente i casi sono:
- filtro statico sulle scelte: condizioni che dipendono dal problema e non dalle scelte precedenti
- filtro dinamico: dipendono da entrambe le cose
- speranza