Listagem de Estágios

3202. Otimização de pesquisas na Web

Instituição: NOVA Math, FCT NOVA - Nova School of Science and Technology
Responsável: Lídia Lourenço
Nº Alunos: 5
Data: de -- a -- Horário: Manhã
Investigador(es): Lídia Lourenço e Graça Gonçalves

Descrição: A Otimização Combinatória (OC) é uma área da Matemática Aplicada que
combina técnicas da Programação Linear, da Teoria de Algoritmos e do Cálculo
Combinatório para resolver problemas de optimização em domínios discretos.

Considera que é feita na Web uma pesquisa de alojamento para um hotel em
Lisboa. O desafio consiste em determinar o k-cluster ótimo que minimiza a
dissemelhança total, para um conjunto de 10 hotéis, sugerindo um subconjunto
de 4 hotéis.

O problema que temos para vos propor surge na Optimização de Pesquisas na
Web.
Quando pesquisamos um produto na Web, um cluster de produtos similares
são propostos em janelas pop-up, baseados na pesquisa previamente
efectuada.
Estes produtos são agrupados num grupo de dimensão fixa, por meio de uma
medida de dissemelhança.
Este problema de desenho de software para as procuras na web é um
problema de optimização combinatória chamado k-Cluster Problem.
O k-Cluster Problem consiste em encontrar o cluster de dimensão fixa k, de
entre um conjunto de n itens, com objectivo de minimizar a dissemelhança
total entre os itens seleccionados para pertencer ao cluster.
Cada cluster, de dimensão k, é uma solução para o problema (solução
admissível). O número de soluções admissíveis para o problema é na ordem
dos , e entre estas soluções, é necessário encontrar a solução que tem a
menor dissemelhança total entre os itens do cluster. Essa é a solução óptima
do problema.
Quanto maior for o número total de itens e a dimensão do cluster, maior é a
dificuldade do problema.
O desafio para os alunos que escolherem este problema é encontrar uma
formulação em programação linear inteira para modelar o problema.
Em seguida, compreender a complexidade deste problema.
E finalmente, obter uma solução para um conjunto de dados reais que vos
vamos propor.

Este estágio não disponibiliza alojamento para alunos deslocados

Este estágio disponibiliza almoços

Local de encontro: Secretaria do Departamento de Matemática, NOVA School of Science and Technology Hora: 9h30
Pessoa de contacto: Lídia Lourenço e Graça Gonçalves