en pt-br

Sugestões de Projetos

Como falei em aula, alguns destes projetos podem ser encaminhados/inicializados como uma pesquisa para TCC, mestrado e doutorado. Contudo, o escopo aqui cobrado é proporcional. %\center%

  • Gerador do Jogo de Palavras-Cruzadas: ao invés de resolver o jogo

de palavras-cruzadas, aqui a idéia é de gerar os quadros, de acordo com algumas restrições.
Responsável: Gabriel Mesquita Rossito

  • A divisão equânime (quase perfeita) por n: aqui é estender a solução

do problema do cabo de guerra (aqui temos n=2), para uma divisão arbitrária n. Balanced Partition Problem – Finding the minimized sum between two partitions of a set of positive integers.
Responsável: Guilherme Eccher

  • O problema do casamento perfeito entre duas matrizes: n homens dão

notas a m atributos (gostos, preferências, etc), idem para uma segunda matriz de n-mulheres. Quais são as combinações perfeitas de alguns pares, e globalmente, qual é o melhor composição para todos se darem bem no casamento?
Responsável: Fernando (15/03/2012)

  • Planejamento de N escolas, que atendam M bairros. Aqui é uma aplicação

clássica de set-covering problem.
Responsável:

  • Jogo-do-resta-um: é conhecido. Há variações em torno deste jogo.

Qual a sequência de ações que levará há um sucesso de resta uma peça no tabuleiro. Problema de planejamento. Sim, este problema é elegível. Dificuldade média-alta, a modelagem está feita em O Peg Solitarire -- versão inglesa Tem a versão francesa.
Responsável: Clayton

  • Grafo tri-partido: é um problema conhecido da area de grafos. Dado um grafo, com nos valorados,

dividir este grafo em 3 outros grafos, tal que algumas restriçoes da di visao sejam respeitadas. O normal para esta particao é algo do tipo: r1 + r2 + r3 = R, onde r1, r2 e r3 estejam nos 3 grafos distintos/gerados. O caso generico do particionamento em K-grafos é provado ser um NP-completo. Contudo, para o caso de K=3, foi encontrado um algoritmo linear. Usando a CP teriamos como melhorar ou igualar este resultado? Estenderiamos facilmente para um grafo de K-particoes? Aqui hah um artigo com toda fundamentacao do problema, basta ler e implementar o que estah lah.
Responsável:

  • Resolver via CP o "Balance problem research of the mixed model assembly line"

Ha um artigo detalhando o problema, o qual foi resolvido com simulated annealing algorithm. Aqui teriamos resultados para comparar com a CP, o que daria um artigo internacional, talvez.
Responsável:

  • Resolver o problema de escalonamento do trem em mono-vias com várias estações. "Um exemplo simplificado para uma instância de 2 trens e 3 estações estão no slides do professor".
    Responsável:
  • Resolver o problema de time-table para linhas de ônibus. Há muitas variações em torno deste tema, escolher uma delas, por exemplo, encontrar a quantidade mínima de ônibus para atender uma determinada linha em seu trajeto de ida e volta, respeitando/restringindo um determinado tempo entre as paradas intermediárias. Ou seja, dada uma parada esta deverá ter um ônibus a cada x minutos, sabendo que o tempo médio entre uma parada e outra, o ônibus demora y minutos. Ou seja um problema de escalonamento e real!
    Responsável: Mauricio Hatori
  • Resolver o TSP dinâmico. O problema do caixeir-viajante é um clássico NP-completo. Tudo bem, adicione a variável tempo (t) em suas trajetórias entre cidades. Assim, um TSP adaptativo deve ser pensado. Claro que a cada cidade visitada, o tamanho do problema diminui em uma instância na entrada. A área deste problema é conhecida como algoritmos adpativos ou temporais. Aqui, há muito a ser explorado, desde um trabalho de disciplina há uma tese de doutorado.
    Responsável:

Problemas definidos pelos alunos, ainda em fase de elaboração:

  • O problema que será tratado é modelar e desenvolver um algoritmo usando programação por restrições, que ache uma configuração/programação valida de jogos entre times de qualquer tipo de torneio ou campeonato, como basquete,futebol.
    Responsável: Felipe de Souza Longo
  • De forma informal, a cobertura de vértices consiste em um conjunto de vértices capaz de incidir sobre todas as arestas de um grafo. O tamanho de uma cobertura de vértices é o número de vértices contidos na cobertura. O problema da cobertura de vértices consiste em encontrar uma cobertura de vértices de tamanho mínimo em um dado grafo.
    Responsável: Pedro Nandi
  • O problema do escalonamento de trabalho é a busca do menor tempo a ser utilizado para que um conjunto de tarefas quaisquer seja concluído. Este conjunto é genérico, podendo representar qualquer tipo de tarefas desejadas, como etapas de um projeto arquitetônico ou o desenvolvimento de um software.

Cada tarefa possui determinada duração, e pode ou não depender de tarefas anteriores. A tarefa pode, ainda, utilizar um ou mais recursos que são compartilhados com outras tarefas. As tarefas, caso possível, podem ser executadas simultaneamente, se não dependerem do mesmo recurso (ou seja, o recurso desejado não pode estar alocado em outra tarefa). Caso uma tarefa dependa de outras tarefas para ser iniciada, deverá aguardar o término das mesmas para que possa ser iniciada. Responsável: Bruno Pereira Damasceno