Seminario Interdipartimentale di Algoritmica
 
 
 

Lunedì 15 Gennaio 2001  ore 10:00
Come e perchè usare il metodo delle differenze limitate
Prof. Alessandro Panconesi
DSI, Università La Sapienza di Roma

Dipartimento di Informatica e Sistemistica - DIS
via Salaria 113, II piano
Aula C2

Abstract:
Il metodo in questione mette a disposizione un apparato potente e versatile per dimostrazioni del tipo "la probabilita' che la variabile aleatoria che mi interessa sia lontana dal suo valore atteso e' molto piccola". Nell'ambito dell`analisi degli algoritmi offre spesso potenzialita' superiori ai piu` noti ed usati bound di Chernoff.
Nel seminario vedremo il metodo in azione nelle sue due versioni, una user-friendly e l'altra meno. Scopo della discussione e` illustrare le maggiori potenzialita` della versione piu` "ostica" rispetto alla versione user-friendly, per non parlare dei bound di Chernoff.