In this thesis, we study the problem of evaluating set expressions over sorted sets in the comparison model. The problem arises in the context of evaluating search queries in text database systems; most text search engines maintain an inverted list, which consists of a set of documents that contain each possible word. Thus, answering a query is reduced to computing the union, the intersection, or a more complex set expression over sets of documents containing the words in the query. At the first step, for a given expression on a number of sets and the sizes of the sets, we investigate the worst-case complexity of evaluating the expression in terms of the sizes of the sets. We prove lower bounds and provide algorithms with the matching running time up to a constant factor. We then refine the problem further and design an algorithm that computes such expressions according to the degree by which the input sets are interleaved rather than only considering sets sizes. %We prove the running time of our algorithm is asymptotically optimal. We prove the optimality of our algorithm by way of presenting a matching lower bound sensitive to the interleaving measure. The algorithms we present are different in the set of set operators they allow in input expressions. We provide algorithms that are worst-case optimal for inputs with union, intersection, and symmetric difference operators. One of the algorithms we provide also supports minus and complement operators and is conjectured to be optimal when an input is allowed to contain these operators as well. We also provide a worst-case optimal algorithm for the form of problem where the input may contain "threshold'" operators, which generalize union and intersection operators: for a number t, a t-threshold operator selects elements that appear in at least in t of the operand sets. Finally, the adaptive algorithm we provide supports union and intersection operators.

Submitted by Alessandra Vallim Lima null (alessandra_vallim@hotmail.com ) on 2017-05-31T22:11:33Z No. of bitstreams: 1 Dissertação Alessandra Vallim Lima .pdf: 2351386 bytes, checksum: 01dcf435983f13dde4b1a10a638fb67f (MD5) / Rejected by Luiz Galeffi (luizgaleffi@gmail.com), reason: Solicitamos que realize uma nova submissão seguindo a orientação abaixo: O arquivo submetido está sem a ficha catalográfica. A versão submetida por você é considerada a versão final da dissertação/tese, portanto não poderá ocorrer qualquer alteração em seu conteúdo após a aprovação. Corrija esta informação e realize uma nova submissão com o arquivo correto. Agradecemos a compreensão. on 2017-06-02T13:17:01Z (GMT) / Submitted by Alessandra Vallim Lima null (alessandra_vallim@hotmail.com ) on 2017-06-02T20:48:13Z No. of bitstreams: 1 Dissertação Alessandra Vallim Lima .pdf: 2354245 bytes, checksum: f5af019776c7b37355d3bef2ad53b87f (MD5) / Approved for entry into archive by Luiz Galeffi (luizgaleffi@gmail.com) on 2017-06-06T14:03:06Z (GMT) No. of bitstreams: 1 lima_av_me_svic.pdf: 2354245 bytes, checksum: f5af019776c7b37355d3bef2ad53b87f (MD5) / Made available in DSpace on 2017-06-06T14:03:06Z (GMT). No. of bitstreams: 1 lima_av_me_svic.pdf: 2354245 bytes, checksum: f5af019776c7b37355d3bef2ad53b87f (MD5) Previous issue date: 2017-05-02 / Nas ultimas décadas, modelagem de nicho ecológico vem recebendo maior atenção em diversas áreas da biologia devido a evolução dos computadores pessoais e aumento dos dados disponíveis utilizados para a modelagem. Os resultados obtidos podem ser utilizados em ações preventivas, tais quais manejo de espécie e acompanhamento da distribuição de espécies invasoras. Desde o aumento dessa popularidade, diversos algoritmos estão disponíveis e testes estão em andamento para averiguar suas performances em relação a diferentes filos. Invertebrados marinhos, mais especificamente cnidários, apresentam poucos estudos nesse ramo, devendo receber mais atenção nos próximos anos devido ao aumento global das populações de aguas vivas (blooms), e branqueamento em quase todos os recifes de corais. Devido a essa lacuna em informação, este grupo foi escolhido para comparar três algoritmos. Utilizamos o MAXENT, GARP e AquaMaps em suas formas de desktop e os selecionamos baseado em outros estudos comparando algoritmos. Utilizamos diferentes organismos do filo cnidária, Lychnorhiza lucerna, Chrysaora lactea, Phyllorhiza punctata, Tamoya haplonema, Ceriantheomorphe brasiliensis e Mussismilia hispida, para comparar os algoritmos e averiguar qual demonstrou melhor performance. Nossos resultados mostram que o MAXENT superou os outros algoritmos tanto com relação a Área Sob a Curva ROC (AUC), quanto com relação aos mapas de distribuição. O GARP apresentou resultados variados com mapas generalizados e AquaMaps foi o menos confiável. Nossos resultados são similares aqueles encontrados em diversas publicações, significando então, que o MAXENT é o algoritmo mais confiável em se tratando da modelagem de nicho desses organismos. / Recently, ecological niche modelling has been receiving more attention in several areas in biology, due to the evolution of personal computers, and the increasing availability of data used in modelling. The results obtained can be used in preventive actions such as species management and invasive species distribution. Since its increasing popularity, several algorithms are available and undergoing tests regarding their performance towards different phylum. Marine invertebrates, more specifically cnidarians, present few studies on this field, and should receive closer attention in the next years due to worldwide increases in jellyfish population (blooms), and bleaching in almost every known shallow water coral reef. Because of this gap of information, we chose this still poor studied group to compare three algorithms. We used MAXENT, GARP and AquaMaps in its desktop form and selected them based on other studies comparing algorithms. Our aim was to, based on different organisms of the phylum Cnidaria, Lychnorhiza lucerna, Chrysaora lactea, Phyllorhiza punctata, Tamoya haplonema, Ceriantheomorphe brasiliensis and Mussismilia hispida, compare those algorithms and examine which one performed the best. Our results shown that MAXENT outperformed the other algorithms both regarding de Area Under the ROC Curve (AUC) and the map distribution. GARP show varying results with generalized maps and AquaMaps was the least accurate of them. Our results are similar to those found in other papers, thus meaning that MAXENT is the most reliable software when it comes to modelling these animals.

Baigiamojo bakalauro darbo tema yra Rikiavimo algoritmų analizė, taigi, jame analizuojami šeši labiausiai naudojami rikiavimo algoritmai, po du iš trijų pagrindinių grupių - išrinkimo, įterpimo ir sukeitimo. Išrinkimo grupėje - Išrinkimo ir Dvigubo išrinkimo algoritmai, įterpimo grupėje - Įterpimo ir Šelo algoritmai, sukeitimo grupėje - Burbulo ir Gnomo algoritmai. Jie lyginami pagal palyginimų ir sukeitim kiekius ir pagal rikiavimo laiką mikrosekundėmis. Kad analizuoti būtų lengviau, naudojant C++ Builder programą buvo sukurtos trys nedidelės apimties programos: pirmoji - duomenų generavimui, antroji - atskirų algoritmų tyrimui ir trečioji - pagrindinė, rikiavimų parametrams tirti. Duomenys generuojami sveikųjų skaičių, slankaus kablelio skaičių ir raidyno pavidalu. Duomenys generuojami pagal reikšmių kiekį ir intervalą, iš kurio mes norime gauti reikšmes. Atskirų algoritmų tyrimo programa išrašo duomenų eilutes po kiekvieno sukeitimo, taigi, mes galime stebėti atskirų algoritmų darbą ir matyti, kuo jie skiriasi. Ir pagrindinė programa rikiuoja duomenis skirtingais algoritmais ir gražina tik palyginimų ir sukeitimų kiekius ir rikiavimo laiką. Pagal šiuos rezultatus buvo sudarytos lentelės ir diagramos algoritmų palyginimui. / The theme of Bachelor Final Work is Analysis of Sorting Algorithms, so I analyse six mostly used algorithms, by two of them from three main groups – selection, insertion, and exchange. In selection group – Selection Sort and Double Selection Sort, in insertion group – Insertion Sort and Shell Sort, in exchange group – Bubble Sort and Gnome Sort. I made comparison of them by the amount of compares, swaps and sorting time in mikroseconds. For making my analysis easier, using C++ Builder program, I made three small programs: one for data generation, the other for the examination of separate algoritms, and the main program which returns sorting parameters. The data are generating in Int type (Integer number), Float type (Floating-point number) and Char type (alphabet). The data are generating by the number of values, for the numbers generating we can appoint the range and so we can make files with different levels of data such like almost sorted row or, on the contrary, very scattered. The program for separate algorythms examination sorts data and after every swap writes the row of values in text box, so we can follow the work of separates algorithms and we can see how different they are. And the main program sorts values by data type and returns just amount of compares, swaps and sorting time. By these results I made tables and diagrams for algoritms comparisons.