A área de Combinatória e Grafos trata de abstrações de certos problemas práticos encontrados na indústria (projetos de chips VLSI, administração de frotas de veículos, sistemas operacionais de computadores, etc.) e em outras áreas da matemática e da pesquisa operacional. Muitos destes problemas podem ser descritos sobre um grafo. Os problemas consistem em encontrar uma configuração ótima (máxima ou mínima, conforme o caso) de um certo tipo no grafo. A dificuldade de todos os problemas de CG está em desenvolver algoritmos eficientes que encontrem a configuração ótima desejada. Para alguns dos problemas, algoritmos eficientes muito interessantes já foram descobertos, mas para muitos outros, a procura por algoritmos eficientes continua. Nosso grupo tem interesse não só nas técnicas mais tradicionais como também em algoritmos paralelos, algoritmos probabilísticos e algoritmos que buscam soluções "aproximadamente ótimas''. Suspeita-se que para muitos dos problemas não existem algoritmos eficientes. A fundamentação desta suspeita é fornecida pela Teoria da Complexidade Computacional. Uma pergunta básica desta Teoria é "Que tipos de problemas são intrinsecamente difíceis?'' Esta é uma questão fundamental que tem preocupado um grande número de pesquisadores nos últimos 20 anos.

Para obter maiores informações, envie uma mensagem para o Professor Yoshiharu Kohayakawa: yoshi(arroba)ime.usp.br 

Veja também Combinatória.
Problemas de Otimização Combinatória ocorrem em áreas tão diversas como projetos de sistemas de distribuição de energia elétrica, posicionamento de satélites, projetos de computadores e de chips VLSI, roteamento ou escalonamento de veículos, alocação de trabalhadores ou máquinas a tarefas, empacotamento de caixas em containers, corte de barras e placas, seqüenciamento de genes e DNA, classificação de plantas e animais, etc. Muitos desses problemas podem ser modelados como problemas de maximizar (ou minimizar) uma função cujas variáveis devem obedecer certas restrições. Encontrar soluções ótimas, ou mesmo aproximadas, para esses tipos de problemas é um desafio nem sempre fácil de ser vencido. Para alguns desses problemas são conhecidos métodos eficientes (rápidos) para se resolvê-los; para outros, métodos de enumeração implícita, relaxação, métodos de planos-de-corte (nem sempre tão rápidos) são alguns dos aplicados com maior sucesso na solução de problemas reais. O grupo de Otimização Combinatória tem interesse no estudo teórico de técnicas para a solução de problemas como os descritos acima, bem como na implementação eficiente de tais técnicas para a solução de problemas reais.

Marcel Kenji

Para obter maiores informações, envie uma mensagem para a Professora Yoshiko Wakabayashi: Este endereço de email está sendo protegido de spambots. Você precisa do JavaScript ativado para vê-lo.
Na pesquisa em redes de computadores são propostos algoritmos e protocolos com o objetivo de garantir qualidade de serviço para as aplicações na Internet. Esses mecanismos podem ser implementados tanto nas aplicações quanto nos dispositivos de interconexão de redes.

Técnicas de análise de desempenho como modelagem analítica, simulação e medição são utilizadas com frequência para avaliar os mecanismos propostos.

Os principais tópicos de pesquisa são: grades computacionais, computação na nuvem, redes P2P, virtualização de redes, redes multimídia, metrologia na Internet, protocolos de roteamento, redes ópticas e redes sem fio.


Prof. Daniel Macêdo Batista - Este endereço de email está sendo protegido de spambots. Você precisa do JavaScript ativado para vê-lo.
Na pesquisa realizada na área de computação em nuvem são propostosmecanismos para permitir que aplicações sejam executadas de formatransparente e eficiente em nuvens. Esses mecanismos devem fazem parteda infraestrutura da nuvem de modo a permitir que os desenvolvedoresnão precisem se preocupar em monitorar suas aplicações e nem emdefinir em quais recursos das nuvens suas aplicações devem executar.Tarefas como essas (monitoramento e escalonamento) sãodisponibilizadas pela infraestrutura da nuvem como serviços para asaplicações submetidas pelos usuários.

Tópicos relacionados com coreografias de serviços web, um tipo decomposição de serviços, também são estudados a fim de permitir quecoreografias sejam mapeadas para computação em nuvem.

Os principais tópicos de pesquisa são: realização de coreografiassobre nuvens, escalonamento, middleware, adaptação dinâmica,monitoramento, virtualização, garantia de QoS e Internet das coisas.



Prof. Fabio Kon
Prof. Alfredo Goldman
Prof. Marco Aurelio Gerosa
Prof. Daniel Macêdo Batista

A pesquisa em Teoria dos Autômatos se articula em várias linhas, algumas de caráter estritamente matemático/lógico, outras com vistas ao desenvolvimento concreto de algoritmos.

 

No primeiro caso temos os vários aspectos do estudo de linguagens, seja pelo lado algébrico, ligado à teoria de semigrupos finitos (estudos do semianel tropical, estudos sobre pseudovariedades de conjuntos e de semigrupos, o problema de Burnside para semigrupos aperiódicos), seja pelo lado da Lógica (caracterização lógica de classes de linguagens).

 

Algoritmos desenvolvidos a partir de Autômatos têm como tema básico a manipulação de seqüências de símbolos. Suas aplicações estão em busca de padrões em textos, compressão de arquivos e problemas combinatórios em biologia molecular, entre outros. É uma característica básica desses algoritmos sua sólida fundamentação na teoria.

 

Prof. Arnaldo Mandel Este endereço de email está sendo protegido de spambots. Você precisa do JavaScript ativado para vê-lo.
Profª. Nami Kobayashi Este endereço de email está sendo protegido de spambots. Você precisa do JavaScript ativado para vê-lo.