Menu



Exportar registro bibliográfico

Tese

Análise estatística do problema da partição numérica (2001)

  • Authors:
  • Autor USP: FERREIRA, FERNANDO FAGUNDES - IFSC
  • Unidade: IFSC
  • Sigla do Departamento: FFI
  • Assunto: MECÂNICA ESTATÍSTICA
  • Language: Português
  • Abstract: Nesta tese apresentamos a abordagem da Mecânica Estatística para o clássico problema de otimização denominado problema da partição numérica (PPN), que é definido como: dada uma seqüência de N números reais positivos {'a IND.1''a IND.2'..., 'a IND.N'} o problema consiste em particioná-los em dois conjuntos complementares, A e 'A POT.c', tais que o valor absoluto da diferença da soma dos 'a POT.' IND.j's nos dois conjuntos seja minimizada. No caso em que os 'a POT.' IND.j's são variáveis aleatórias estatisticamente independentes distribuídas uniformemente no intervalo unitário, este problema NP-completo equivale ao problema de encontrar o estado fundamental de um modelo de Ising anti ferromagnético aleatório de alcance infinito. Conseqüentemente, a análise probabilística do PPN pode ser realizada com as ferramentas da Mecânica Estatística de sistemas desordenados. Neste trabalho empregamos a aproximação recozida ('annealed') para derivar uma expressão analítica para o limitante inferior do valor médio da diferença para partições tanto com vínculo de cardinalidade quanto sem vínculo para grandes valores de N. Além disso, calculamos analiticamente a fração de estados metaestáveis, isto é, estados que possuem a menor energia mediante todos os vizinhos (estados que diferem pela troca de um único spin). Concluimos a análise da abordagem direta, cujas instâncias {'a IND.i'} são fixas e as partições são variáveis, com o estudo analítico da versão relaxada desteproblema de programação inteira NP-completo. Na segunda parte desta tese propomos e exploramos uma abordagem inversa para o PPN, no qual as partições ótimas são fixas e as instâncias são variáveis. Especificamente, usando o método das réplicas estudamos analiticamente o espaço de configuração do problema da partição numérica. Mostramos que, independentemente da distribuição de entradas das instâncias, existe um limitante superior ''alfa'IND.c'N para o número de ) partições perfeitas aleatórias (isto é, partições com diferença igual a zero). Em particular, no caso em que os dois conjuntos têm a mesma cardinalidade (partições balanceadas) encontramos ''alfa' IND.c'=1/2. Mais ainda, no caso de partições não balanceadas, mostramos que as partições perfeitas aleatórias existem somente se a diferença entre as cardinalidades dos dois conjuntos escala com 'N. POT.1/2'
  • Imprenta:
  • Data da defesa: 08.03.2001
    • Acesso à fonte
    How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      FERREIRA, Fernando Fagundes. Análise estatística do problema da partição numérica. 2001. Tese (Doutorado) – Universidade de São Paulo, São Carlos, 2001. Disponível em: http://www.teses.usp.br/teses/disponiveis/76/76131/tde-05112008-131459/. Acesso em: 19 abr. 2024.

    • APA

      Ferreira, F. F. (2001). Análise estatística do problema da partição numérica (Tese (Doutorado). Universidade de São Paulo, São Carlos. Recuperado de http://www.teses.usp.br/teses/disponiveis/76/76131/tde-05112008-131459/

    • NLM

      Ferreira FF. Análise estatística do problema da partição numérica [Internet]. 2001 ;[citado 2024 abr. 19 ] Available from: http://www.teses.usp.br/teses/disponiveis/76/76131/tde-05112008-131459/

    • Vancouver

      Ferreira FF. Análise estatística do problema da partição numérica [Internet]. 2001 ;[citado 2024 abr. 19 ] Available from: http://www.teses.usp.br/teses/disponiveis/76/76131/tde-05112008-131459/

    Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

Digital Library of Intellectual Production of Universidade de São Paulo     2012 - 2024