CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / Esta tese à composta de trÃs partes bem-delineadas. Na primeira parte, nÃs introduzimos o "problema de ordenaÃÃo de rodadas" (POR), que modela a minimizaÃÃo do uso de memÃria ("buffer") para o armazenamento temporÃrio de pacotes a serem repassados em comunicaÃÃes TDMA de redes de rÃdio em malha. NÃs apresentamos uma fundamentaÃÃo completa para a definiÃÃo do POR, e mostramos que o problema à NP-difÃcil para dois modelos teÃricos de interferÃncia de rÃdio conhecidos na literatura. Uma formulaÃÃo de programaÃÃo inteira mista à tambÃm apresentada para uma generalizaÃÃo puramente combinatÃria e independente de aplicaÃÃo do POR, o problema SMSP. Na segunda parte do trabalho, nÃs abordamos problemas de consulta sobre inserÃÃes em sequÃncias de nÃmeros. O nosso principal resultado nesta parte da tese à mostrar como, apÃs um passo de prÃ-processamento que executa em tempo linear sobre uma sequÃncia "A" de nÃmeros reais quaisquer, à possÃvel computar em tempo constante a maior soma de uma subsequÃncia contÃgua (circular ou nÃo) da sequÃncia que resulta da inserÃÃo de dado um nÃmero real "x" numa dada posiÃÃo "p" de "A". Na terceira parte da tese, nÃs utilizamos os algoritmos de consulta da segunda parte para obter uma implementaÃÃo eficiente da meta-heurÃstica GRASP aplicada ao problema SMSP. Uma anÃlise experimental dessa implementaÃÃo à descrita, onde os valores das soluÃÃes retornadas pela meta-heurÃstica sÃo comparados com os das soluÃÃes obtidas pela formulaÃÃo inteira mista, no caso de instÃncias pequenas, e com o limite inferior disponÃvel, no caso de instÃncias maiores.
| Identifer | oai:union.ndltd.org:IBICT/oai:www.teses.ufc.br:7588 |
| Date | 01 November 2013 |
| Creators | Pablo Mayckon Silva Farias |
| Contributors | Ricardo Cordeiro CorrÃa, Manoel Bezerra Campelo Neto, CrÃston Pereira de Souza, Thiago Ferreira de Noronha, FÃbio Protti |
| Publisher | Universidade Federal do CearÃ, Programa de PÃs-GraduaÃÃo em CiÃncia da ComputaÃÃo, UFC, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFC, instname:Universidade Federal do Ceará, instacron:UFC |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.002 seconds