ETD system

Electronic theses and dissertations repository

 

Tesi etd-09212020-014214


Thesis type
Tesi di laurea magistrale
Author
BERETTA, LORENZO
URN
etd-09212020-014214
Title
Sorting and Selecting with Liars
Struttura
INFORMATICA
Corso di studi
INFORMATICA
Supervisors
relatore Prof. Venturini, Rossano
Parole chiave
  • sorting
  • selection
  • information retrieval
  • tournament graphs
Data inizio appello
09/10/2020;
Consultabilità
Parziale
Data di rilascio
09/10/2023
Riassunto analitico
Sorting and selection are two fundamental problems in theoretical computer science, their optimal solution in the usual comparison model is a typical introductory topic of textbooks in algorithmics. Suppose that, instead of the usual comparison operation, we dispose of a black-box comparison function, that sometimes can err, producing inconsistent outputs. Studying selection and sorting in this setting becomes more interesting: we need to both set up models describing how our comparator may fail, and design algorithms to efficiently perform approximate selection and sorting. In this thesis we will overview various models to define in which sense the comparisons are {\em faulty} and what kind of approximate sorting or selection we can perform. For every model exposed we will analyze the state-of-the-art complexity of selection and sorting in those models. The last chapter contains an original result, partially published in \ref{spire} that solves the problem of finding the maximum element in presence of faulty comparisons and employs a novel parameterization, that captures an important feature of applications.
File