Algoritmi Sequenziali e di Streaming per la Selezione della Mediana

La presente tesi analizza il problema della selezione della mediana nel contesto del modello di streaming. Dopo una panoramica introduttiva sull'algoritmo di selezione nel modello RAM tradizionale e sulle caratteristiche fondamentali del modello computazionale di streaming, il lavoro approfondisce un algoritmo multi-pass per la selezione della mediana proposto da J. Ian Munro e Mike Paterson nel paper "Selection and Sorting with Limited Storage". La tesi fornisce una descrizione dettagliata e rigorosa dell’algoritmo, mettendone in evidenza il funzionamento, le strategie adottate per operare con memoria limitata e il compromesso tra numero di passaggi sulla sequenza di input e lo spazio di memoria disponibile.