algoritmi probabilistici Flashcards
Cosa si intende per algoritmo probabilistico?
è 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
Cos’è un algoritmo non deterministico? in cosa differisce con gli altri?
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
Quali tipi di algoritmi probabilistici esistono
Algoritmi monte Carlo e algoritmi Las Vegas
come funzionano gli algoritmi montecarlo?
determinano la probabilità di un output dato un input senza conoscere la sorgente aleatoria
che tipi di algoritmi di approssimazione sono possibili negli algoritmi montecarlo?
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
come funzionano algoritmi las vegas?
sono algoritmi con un output deterministico in cui l’output è la probabilità che l’algoritmo termini in una determinata quantità di tempo
cos’è il problema di taglio minimo dei grafi?
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)
cos’è una contrazione?
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.
come funziona algoritmo di karger?
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
che osservazioni vengono fatte a livello di lati e vertici nell’algoritmo di karger?
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
come riesco a mettere in relazione il numero di lati con k* nell’algoritmo di karger?
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 )
come viene svolta l’analisi del teorema di krager?
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
cosa dice il primo lemma di karger?
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.
cosa dice secondo lemma di karger
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)
cosa dice il teorema di karger
Quanto viene ricavato dal secondo lemma; la probabilità di ottenere ottimo utilizzando l’algoritmo è di 1/n sceglie 2
Cosa dice il corollario del teorema di karger? come si dimostra?
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
Cos’è il problema di set cover?
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
Come ricavo set cover approssimato?
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
Come trasformo set cover nel corrispondente PLI?
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.
Quali elementi statistici è necessario definire per risolvere set cover?
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)
Come viene svolta l’analisi di set cover probabilistico?
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
quali sono le ideee per dimostrare la probabilità che set cover dia una solizione ammissibile?
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
cosa dice e quali sono le idee per dimostrare il secondo teorema legato a cover set probabilistico?
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.
cosa dice il corollario dell’algoritmo per cover set probabilistico? quali sono le idee per dimostrarlo?
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
in cosa consiste il problema maxE_kSat?
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
come è stata svolta l’analisi di maxE_ksat?
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.
cos’è la legge del valore atteso totale?
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] .
cosa dice e quali sono le idee per dimostrare il teorema maxE_ksat per trovare il numero atteso di clausole soddisfatte?
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
Cosa dice il teorema usato per la corettezza della derandomizzazione in makE_ksat? come si dimostra?
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)
cosa dice il corollario al teorema usato per la correttezza della derandomizzazione di maxE_k sat?
che esiste una sequenza di n clausole fissate tale che E[T|nclausole] >= 2^k-1/2^k
come funziona l’algoritmo per fare maxe_ksat deterministico?
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
cosa dice il teorema associato all’algoritmo per la derandomizzazione di max e_ksat? come si dimostra?
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
cosa dice il corollario sulla dimostrazione del teorema di correttezzza associato all’algoritmo di derandomizzazione di max e_ksat? come si dimostra?
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
