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
