algoritmi probabilistici

Question 1

Cosa si intende per algoritmo probabilistico?

Answer 1

è un algoritmo nella quale vengono fatte a livello di procedimento alcune scelte arbitarie. può essere rappresentato come una macchina di touring con annesso un nastro di cifre casuale. l’idea nel corso è di determinare alcune proprietà di questi algoritmi che prescindono dalla compoenente aleatoria

Question 2

Cos’è un algoritmo non deterministico? in cosa differisce con gli altri?

Answer 2

Algoritmo non deterministico è un algoritmo utilizzato primariamente nella teoria della complessità, l’idea è di utilizzare una macchina di turing in grado di valutare in paralello una quantità infinita di strade diverse

Question 3

Quali tipi di algoritmi probabilistici esistono

Answer 3

Algoritmi monte Carlo e algoritmi Las Vegas

Question 4

come funzionano gli algoritmi montecarlo?

Answer 4

determinano la probabilità di un output dato un input senza conoscere la sorgente aleatoria

Question 5

che tipi di algoritmi di approssimazione sono possibili negli algoritmi montecarlo?

Answer 5

sono possibili o algoritmi che determinano la probabilità con cui si raggiunge l’ottimo, senza ulteriori garanzie o algoritmi che garantiscono, con una determinata probabilità, di raggiungere un determinato rapporto di approssimazione

Question 6

come funzionano algoritmi las vegas?

Answer 6

sono algoritmi con un output deterministico in cui l’output è la probabilità che l’algoritmo termini in una determinata quantità di tempo

Question 7

cos’è il problema di taglio minimo dei grafi?

Answer 7

problema volto a individuare un insieme di vertici (diverso da U) che permette il taglio minimo ( minimo numero di vertici incidenti su quelli contenuti nell’insieme)

Question 8

cos’è una contrazione?

Answer 8

operazione di eliminazione di un lato, i vertici agli estremi vengono unficati in un unico vertice sul quale incidono i lati che incidevano sui due vertici iniziali. possibili multi grafi.

Question 9

come funziona algoritmo di karger?

Answer 9

viene dato in input un grafo ordinato. Se sono presenti componenti + componenti connese data in output una a caso. in caso contrario finchè il numero di vertici > 2 viene scelto casualmente un lato e viene contratto. quando rimangono due vertici viene dato in output uno dei due. in numero di archi che li collegano è il taglio ottenuto

Question 10

che osservazioni vengono fatte a livello di lati e vertici nell’algoritmo di karger?

Answer 10

per quanto rigaurda i vertici data la seguenza di grafi G_1..G_t risultanti dalle vaire iterazioni del cicli il numero di vertici di G_i = |V|-i+1 in quanto ad ogni iterazione il numero di vertici diminuisce di 1 e all’iterazione 1 sono nella situazione iniziale.
inoltre in ogni momento la cardinalità minima nel grafo è >= k* dove k* è il valore di taglio minimo. Per quanto riguarda i lati, il numero di lati nel grafo G_i >= m-i+1

Question 11

come riesco a mettere in relazione il numero di lati con k* nell’algoritmo di karger?

Answer 11

considero che il doppio dei lati è minore o uguale della somma della cardinalità di tutti i vertici, e dato che la cardinalità di ogni vertice è >=k* il doppio dei lati è di certo >= k* numero vertici (iterazione i )

Question 12

come viene svolta l’analisi del teorema di krager?

Answer 12

vengono fatte alcune osservazioni riguardanti i lati e i vertici nelle varie iterazioni dell’algoritmo, viene messo in relazione il numero di lati con k*, viene definita la probabilità che venga scelto un arco della soluzione ottima, vengono ricavati due lemmi; il primo volto a stabilire questa probabilità ad ogni iterazione e il seocndo a calcolarla per intero. viene quindi ricavato il teorema che fissa la probabilità di avere l’ottimo (ricavata da lemma 2) e viene poi dimostrato un corollario che determina la probabilità dell’ottimo eseguendo karger n sceglie 2 ln n volte

Question 13

cosa dice il primo lemma di karger?

Answer 13

prima di tutto defnisce l’evento epsilon come la probabilità di aver preso un arco che non sia parte della soluzione ottima. si considera poi la probabilità epsilon_i dati epsilon_1.. epsilon_i-1 e si vuole dimsotrare sia uguale a n-i-1/n-i+1. utilizzo: probabilità pijiare uno dei k* archi considerando il numero totale di archi espresso in funzione di k dalle osservazoini.

Question 14

cosa dice secondo lemma di karger

Answer 14

secondo lemma di karger pone in and tutte le epsilon per calcolare la probabilità di non pijiare un arco appartenente al taglio ottimo in tutte le iterazioni. (1/(n sceglie 2)

Question 15

cosa dice il teorema di karger

Answer 15

Quanto viene ricavato dal secondo lemma; la probabilità di ottenere ottimo utilizzando l’algoritmo è di 1/n sceglie 2

Question 16

Cosa dice il corollario del teorema di karger? come si dimostra?

Answer 16

il corollario del teorema di karger dice che la probabilità di non trovare l’ottimo eseguendo l’algoritmo (n sceglie 2) ln n volte è di 1 - 1/n. per farlo prima definisce proprietà esponenziale (1-x)^x <= 1/e con x > 1 e poi sfrutta la cosa andando a guardare la probabilità di non avere l’ottimo ed elevandola al numero di volte per cui vogliamo eseguire l’algoritmo

Question 17

Cos’è il problema di set cover?

Answer 17

diversi subset che uniti coprono tutto l’insieme universo (possibili sovrapposizioni), ad ogni sotto insieme viene assegnato un peso, devo trovare tot sotto insiemi che coprono tutto di costo minimo

Question 18

Come ricavo set cover approssimato?

Answer 18

idea: trasformo il set cover in un problema PLI (xi -> selezione degli insiemi, 1 o 0) e poi rilasso a PL. una volta ottenuti questi xi per ogni subset provo ad aggiungerlo all’insieme di output S con probabilità x_i k log n volte, dove k è un parametro. Fatto questo emetto S

Question 19

Come trasformo set cover nel corrispondente PLI?

Answer 19

associo variabile selezione x_i ad ogni sotto insieme. pongo come vincolo che per ogni elemento presente in u la somma delle variabili x_i, considerando gli insiemi s corrispondenti contenenti l’elemento >= 1.
la funzione obbiettivo è il min tra il prodotto di xi con i pesi wi associati al subset corrispondente.

Question 20

Quali elementi statistici è necessario definire per risolvere set cover?

Answer 20

Disuguaglianza di Markof e union bound; la prima dice che P[x> alpha] <= E[x]/alpha; disuguaglianza di concentraizone.
Il secondo è union bound che dice che P[e1 U e2] <= P(e1) + P(e2) (uguaglianza stretta con insiemi disgiunti)

Question 21

Come viene svolta l’analisi di set cover probabilistico?

Answer 21

Viene prima dimostrato un teorema che determina la fattibilità del problema (con che probabilità ottengo una soluzione accettabile), un teorema che determinata la probabilità con cui si ottiene un rapporto di approssimazione entro una certa soglia e infine viene dimostrato un corollario che mostra che con k = 3 c’è la probabilità del 45% di avere rapporto di approssimazione <= 6 +2 ln n

Question 22

quali sono le ideee per dimostrare la probabilità che set cover dia una solizione ammissibile?

Answer 22

teoriema: soluzione ammissibiile con prob >= 1-e^(-k)considero la probabilità di non avere una soluzione ammissibile, cioè che almeno un elemento dell’insieme non sia coperto. 1 - probabilita tutto -> unione probabilità singolo non sia -> sommatoria per union bound.
per trovare probabilità singolo voglio tutti gli insiemi che lo contengano predicano negativo. predirre negativo:(1-x)^k+ln n. moltiplico per tutti gli insiemi in quanto deve essere negativo per tutti, and. questo per il singolo elemento. maggioro (1-x)<= e -x, poi trasformo sommatori a in produttoria all’esponente (prodotto tra potenze con raccoglimento). sommatoria -> almeno 1 per vincolo, sostituisco con 1. poi passaggi algebrici per arrivare 1 -e^k

Question 23

cosa dice e quali sono le idee per dimostrare il secondo teorema legato a cover set probabilistico?

Answer 23

il teorema dice che p[ fatt. approssimazione >= alpha(k+lnn)]<= 1/alpha.
prima definisco costo v cappuccio come pesi * xi e lo pongo <= v. poi dimostro che prob. scegliere S_i <= (k+kn n)x cappuccio.
calcolo E[v_out] come somma w_i * prob scegliere s_i e poi mi ricordo che pesixi <= v*. quindi ri-scrivo disuguaglianza iniziale e applico markov.

Question 24

cosa dice il corollario dell’algoritmo per cover set probabilistico? quali sono le idee per dimostrarlo?

Answer 24

che con k = 3 c’è circa il 45% della probabilità di avere una soluzione ammissibile con un rapporto di approssimaizone >= 6+2lnn. le idee sono di mettere in and la probabilità sia ammissibile e la probabilità sia buono, negarle, 1 - or del complemento e poi sostituire k = 3

Question 25

in cosa consiste il problema maxE_kSat?

Answer 25

consiste nel determinare, dato un numero di elementi k che compongono una clausola (dove la clausola sono un insieme di elementi in or) e l’intera espressione è un insieme di clausole in and, qual’è il numero massimo di clausole vere ottenibili con un qualsiasi assegnamento

Question 26

come è stata svolta l’analisi di maxE_ksat?

Answer 26

con l’enunciato di un primo teorema, che afferma che con k>=3 maxE_ksat è insolubile, con una prima dimostrazione in cui si ricava il valore atteso del numero di clausole vere e con una seconda dimostrazione che permette la de-randomizzazione dell’algoritmo.

Question 27

cos’è la legge del valore atteso totale?

Answer 27

una legge statistica per cui definiti una serie di elementi epsilon_i, tale che questi siano disgiunti e che la loro somma formi l’insieme universero E[t] = sum_i E[t|epsilon_i} * P[epsilon_i] .

Question 28

cosa dice e quali sono le idee per dimostrare il teorema maxE_ksat per trovare il numero atteso di clausole soddisfatte?

Answer 28

il teorema dice che il numero atteso di clausole vere è : ((2^k -1 )/ 2^k) * t.le idee di base sono: scrivere il teorema utilizzando la legge del valore atteso totale, considerano le somme di tutti i possibili valori assumibili da tutte le variabili. a questo punto ricavare che la probabilitò che queste siano 1 è sempre di 1/2. Poi si può esprimere il valore atteso del numero di clausole come la sommatoria del valore atteso delle singole. si ricava quindi la probabilità che una clausola sia vera (2^n-2^n-k). con qualche passaggio algebrico si arriva a ricavare l’enunciato del problema

Question 29

Cosa dice il teorema usato per la corettezza della derandomizzazione in makE_ksat? come si dimostra?

Answer 29

dice che date n clausole esiste un modo di fissare j clausole (con j che va da 0 a n) per ottenere un numero di clausole >= (2^n-2^n-k). viene dimostrato per induzione; il passo base (j=0) è dato dal teorema del valore atteso, si può fare l’ipotesi induttiva che il terema sia vero fino a j-1. a questo punto per la legge del lavore atteso totale si fissa j ai suoi due possibili valori e si dimostra che uno dei due è di sicuro >= 2?n-2^n-k)

Question 30

cosa dice il corollario al teorema usato per la correttezza della derandomizzazione di maxE_k sat?

Answer 30

che esiste una sequenza di n clausole fissate tale che E[T|nclausole] >= 2^k-1/2^k

Question 31

come funziona l’algoritmo per fare maxe_ksat deterministico?

Answer 31

inizialmente azzero l’insieme delle clausole determinate. per ognuna dei valori letterali possibili vengono azzerati i valori delta0 e delta1 e posti a vuoto gli insiemi Delta0 e Delta1. per ognuna delle clausole poi: skippo se la variabile non compare nella clausola o se la clausola è determinata. Negli altri casi ricavo h che è il numero di letterali presenti nella clausola con i >; se il letterale compare positivo quindi aggiungo 1/2^h a delta1 e tolgo 1/2^h a delta 0 ( 1/2^h è il peso, questo è proporzionale al numero di letterali rimanenti in quanto se sono arrivato qui vuol dire che tutte le precedenti sono negative. se è l’ultimo determina effettivamente il valore assunto dalla clausola), inoltre aggiungo il letterale a Delta1. viene fatto il contrario nel caso l’elemento sia negativo. alla fine del diclo che scorre su tutte le clausole guardo chi è maggiroe fra delta1 e delta0, e poi prendo il Delta corrispondente e lo unisco all’insieme delle clausole determinate; in questo modo ho determinato se il valore di un letterale è uno o zero. alla fine dell’algoritmo emetto la cardinalità di D

Question 32

cosa dice il teorema associato all’algoritmo per la derandomizzazione di max e_ksat? come si dimostra?

Answer 32

dice che l’argoritmo permette di ottenere un numero di clausole >= 2^l-1/2^k. per dimostrarlo si parte dicendo che ad ogni passo garantisco che il valore atteso è >= 2^k-1/2^k. la dimostrazione è induttiva; per x = 0 è vera da teoriema, assumo sia vera 2^(i-1) e provo a verificare vada bene per i. calcolo la differenza di valore atteso con xi e calcolo questa come il nuovo valore (se assegno 1 o 0) - il valore atteso precedente (2^h-1/2^h). ricavo che i valori sono opposti e che quindi è sempre possibile scegleiere il valore totale in modo che il valore atteso fisstao xi sia >= di quello che avevo precedentemente

Question 33

cosa dice il corollario sulla dimostrazione del teorema di correttezzza associato all’algoritmo di derandomizzazione di max e_ksat? come si dimostra?

Answer 33

dice che l’algoritmo fornisce una 2^k -1 / 2^k approssimazione a max_e_ksat. per dimostrare questo vedo: rapp. approssimazione = t*/talg <= t/talg e sostutuisco il valore di talg