Conteúdo
Linha de Pesquisa
Equipe
Laboratório
Benchmarks
Seminário
Grupo de Pesquisa em Engenharia de Algoritmo
Linha de Pesquisa
Equipe
Laboratório
Benchmarks
Seminário
O GPEA foi criado em 2006 no Departamento de Informática da UEM.
As atividades de pesquisa do GPEA estão concentradas no projeto e análise teórica e experimental de algoritmos para automação de planejamento em sistemas de produção e computação aplicados a problemas complexos de gerenciamento de recursos.
A missão do grupo é a investigação de algoritmos eficientes para resolução de problemas de otimização com ênfase em aplicações envolvendo espaços de busca complexos e grande quantidade de dados. O foco atual é a otimização de escalonamentos na agroindústria, no transporte, em hospitais, em escolas e na indústria de software.
Otimização
A linha de pesquisa deste grupo está focada em otimização combinatória, que refere-se ao estudo de problemas em que se busca minimizar ou maximizar uma função através da escolha sistemática dos valores de variáveis reais ou inteiras dentro de um conjunto viável.
O que é otimização combinatória?
Suponha que você possui um conjunto de itens e uma série de regras que podem ser usadas para selecionar alguns elementos (itens) desse conjunto. Usando essas regras, há várias maneiras diferentes de escolher os elementos e criar outros conjuntos menores (ou subconjuntos). Se, a cada elemento estiver associado um custo, os subconjuntos criados, também, terão um custo que é dado, por exemplo, pela soma dos custos de seus elementos.
O problema de Otimização Combinatória, em geral, se resume a encontrar, dentre todos os possíveis subconjuntos, aquele cujo custo seja o menor possível. Uma forma de resolver tais problemas seria simplesmente enumerar todas as soluções possíveis e guardar aquela de menor custo. Entretanto, essa é uma ideia ingênua pois para qualquer problema de um tamanho interessante (e útil), esse método torna-se impraticável, já que o número de soluções possíveis é muito, muito grande. Mesmo que você utilize um supercomputador para resolver o problema, o tempo de processamento pode levar várias horas, ou vários dias ou até anos.
Parece uma coisa absurda, mas estamos rodeados de problemas práticos dessa natureza. Os problemas aqui tratados são conhecidos tecnicamente por NP-difícil. Portanto, técnicas computacionais mais apuradas são necessárias para resolver esses problemas.
Aplicações práticas
Existe uma infinidade de problemas da vida real que podem ser encarados como problemas de Otimização Combinatória. Para que você tenha uma ideia da diversidade de aplicações possíveis, veja a lista de alguns problemas descritos informalmente, abaixo:
Técnicas utilizadas (modelos e algoritmos)
A resolução de um problema de otimização normalmente precisam passar por duas fases: a primeira consiste em transformar o problema em um modelo e, posteriormente, um algoritmo deve ser implementado para resolver o modelo.
O que você tem a ganhar?
Na sociedade da informação o mais preparado é aquele que possui o conhecimento certo para ser aplicado ao problema certo. Quanto vale um profissional capaz de reduzir os custos de uma empresa em 30%? Nem é preciso responder, certo? Capacitação profissional é a moeda forte no mercado de trabalho atual. E é isso que nós podemos lhe oferecer. Se você desenvolve um sistema capaz de reduzir 10% do custo total de uma empresa, então por quanto você poderia vender o seu sistema? Muitas vezes esse tipo de sistema não só reduz o custo imediato, como também, melhora o desempenho da empresa.
Dentro do meio acadêmico, não podemos nos esquecer de que o mercado lá fora está mais competitivo a cada dia que passa. Trabalhos de graduação ou de iniciação científica podem ajudar a complementar a sua formação. E, se você tem vontade de fazer uma pós-graduação, por que não se especializar em uma área que está em pleno crescimento?
O que as empresas têm a ganhar?
Infelizmente, ainda é pequeno o número de empresas que utilizam em seus processos (sejam eles produtivos ou não) alguma técnica de otimização. Isto se deve, principalmente, a uma falta de conhecimento a respeito do poder real de tais técnicas.
É muito comum que as empresas não tenham consciência de que certas tarefas são passíveis de otimização por sistemas computacionais. Tarefas altamente ineficientes poderiam ser melhorados significativamente, mas continuam promovendo prejuízos que passam despercebidos porque, afinal de contas, “sempre funcionou tão bem assim, não é mesmo?”.
Ter prejuízo não significa somente terminar o mês com o caixa negativo. Significa, também, terminar o mês com um “lucro” de R$ 100.000,00 sem se dar conta de que o lucro poderia ter sido de R$ 250.000,00, caso os recursos fossem administrados de forma mais adequada. Esse tipo de comportamento é bastante freqüente e precisa ser mudado.
Durante muitos anos, as teorias e métodos desenvolvidos por matemáticos e cientistas foram arquivados em livros e periódicos especializados e muito pouco foi absorvido pelo setor empresarial. Felizmente, contudo, essa situação vem se alterando. É cada vez maior o número de companhias que adotam modelos de otimização no seu dia-a-dia, diminuindo seus custos e, por conseguinte, aumentando os lucros. Além do mais, com a onda crescente de privatizações nos diversos setores da sociedade, a concorrência se fortifica e a sobrevivência dos negócios começa a depender seriamente do desempenho de cada um com relação aos demais. Quem estiver melhor preparado irá, sem dúvida alguma, suplantar os adversários.
No Brasil, esse processo vem ganhando força mas ainda é incipiente. Nos demais países, principalmente na Europa e nos Estados Unidos, a utilização de técnicas de otimização dentro das empresas é bem mais difundida, assumindo um papel de grande relevância.
O que a ciência tem a ganhar?
Os exemplos aqui citados são eminentemente práticos e existem muitas dessa aplicações aqui em nossa cidade e região. Por outro lado, os problemas trabalhados nessa área possuem aspectos de difícil solução por meio de técnicas computacionais convencionais. A natureza dos problemas exige técnicas computacionais eficientes e rápidas para resolver os problemas. Portanto, a investigação científica concentra-se no desenvolvimento de modelos e algoritmos para esses problemas.
Muitos paradigmas têm sido pesquisados e continuam sendo investigados nos últimos tempos. Alguns desse paradigmas têm sido impulsionados por esses problemas, tais como: Algoritmos Aproximados, Algoritmos Meméticos, Scatter Search, Simulated Annealing, Busca Tabu, Ant System, GRASP, etc.
O perfil desejado do candidato
Experiência prática e parcerias
Ultimamente, nós temos estabelecido contatos com empresas e prefeitura de nossa cidade e região. Desses contatos tem surgido oportunidades de levarmos o nosso conhecimento científico à comunidade externa, resultando em aplicações práticas das nossas pesquisas. Isso tem nos animado ao ver que temos o que contribuir para a ciência e à nossa região.
Instituições brasileiras com pesquisa e pós-graduação
Mais informações
Existem muitos sites na Internet com textos introdutórios sobre otimização combinatória e sobre cada algumas das técnicas mencionadas acima. Se você deseja ler um pouco mais sobre o assunto, dê uma olhada nos links abaixo:
Agradecimentos ao Prof. Cid de Carvalho de Souza (IC/UNICAMP) por autorizar a reprodução de partes de seu texto nesta página.
Fechar Janela
Docentes/Pesquisadores
Discentes
O LEAL está localizado na sala 201 do bloco C56. Os membros do GPEA desenvolvem suas atividades neste local que conta com ar condicionado split, sistema digital de controle de acesso e 7 (sete) computadores de diversas configurações, 3 (três) estações de trabalho de alto desempenho e acesso a vários servidores no data center. Dispõe de uma rede local conectada a diversos servidores instalados em um centro de processamento de dados (datacenter) da própria UEM.
O que é engenharia?
É a ciência e a arte da aplicação de princípios científicos e matemáticos para projetar coisas e resolver problemas em benefício da sociedade.
O que é algoritmo?
Trata-se de um conceito na área de computação que significa uma sequência finita de passos lógicos e bem definidos para resolver um problema. Esses passos posteriormente poderão ser escritos numa linguagem de computador e transformados num programa.
O que é Engenharia de Algoritmo?
É a ciência e a arte da aplicação de princípios científicos e matemáticos para projetar algoritmos que resolva problemas de maneira eficiente. O conhecimento necessário para esta área resume-se em matemática, programação matemática, análise de algoritmos, teoria da computação, teoria dos grafos, combinatória e estrutura de dados.
Esta é uma nova denominação dentro da área de computação que reúne os aspectos teóricos e científicos da computação juntamente com aplicações em problemas reais. A ACM (Association for Computing Machinery) tem considerado essa nova área há mais de cinco anos, promovendo o evento anual ALENEX (Workshop on Algorithm Engineering and Experiments).
Motivação
Constantemente nos deparamos com algoritmos concebidos a partir de formulações de programação matemática. Na literatura encontramos alguns desses algoritmos clássicos e muito importantes, tais como: algoritmo húngaro para o problema de atribuição, algoritmo de Out-of-Kilter para fluxo de custo mínimo, algoritmo de Edmond para emparelhamento de grafo não bipartido. Alguns desses algoritmos baseiam-se em variáveis primais e/ou duais oriundas de formulações de programação matemática, como é o caso do Out-of-Kilter. Estes exemplos mostram a importância da programação matemática na concepção de algoritmos robustos e eficientes.
O trinômio Problema-Modelo-Algoritmo tem sido o foco de trabalho para a Engenharia de Algoritmo. Antes da resolução do problema diretamente por um algoritmo, a formulação de um modelo do problema deve ser uma fase imprescindível para a obtenção de um bom algoritmo. Os exemplos de algoritmos clássicos supracitados revelam essa necessidade.
Fechar Janela
Regra para uma boa apresentação de seminário
Apresentar bem uma ideia é um desafio permanente para qualquer pesquisador, ainda mais quando se está no meio do processo de busca do conhecimento.
Uma das máximas é a regra 10-20-30 de Guy Kawasaki, que já foi colaborador e “chefe evangelizador” da Apple (uma espécie de missionário da marca). Em um post muito engraçado em seu blog “How to Change the World”, ele explica que chegou a essa regra depois de ouvir centenas de apresentações de startups. A fórmula é simples:
Extraído da revista Pequenas Empresas & Grandes Negócios.
Pergunte a si mesmo: “Qual o propósito da minha palestra?”
O público irá provavelmente se lembrar de 10% da palestra, ou talvez 3 pontos principais, então foque nos pontos que serão “levados para casa”. Tenha certeza que eles estejam claros e repetidos na explanação.
A palestra deve ser estruturada, isto é, deve ter seções claramente definidas (assim como um livro é claramente dividido em capítulos). No fim de cada seção pare e pergunte se alguém necessita de algum esclarecimento, ou se algo precisa ser explicado de alguma outra forma. Dê ao público a chance de perguntar, se eles não entenderam. Silêncio implica que o público não entendeu. Talvez se deva questionar o público para iniciar uma resposta.
Não encha a palestra com detalhes. As pessoas irão perguntar se quiserem (então tenha os detalhes talvez em outros slides). É melhor manter a palestra simples do que complicá-la demais.
Aprenda como dar boas palestras observando outras pessoas – o que elas fizeram que foi bom ou ruim.
Se você gosta de apresentar a palestra, o público provavelmente vai gostar se assistir.
Preparação da apresentação
Cheque sua apresentação pela legibilidade:
Altamente recomendado
Assim que você tiver um protótipo dos slides, vá para a sala do seminário, faça a projeção e verifique se pode ler bem do fundo da sala.
Não seja uma dessas pessoas que veem seus slides pela primeira vez durante o discurso e então ficam obviamente surpresas quando ficam ilegíveis.
Por outro lado se quiser irritar o público ou não tem conteúdo ou simplesmente quiser obscurecer o assunto, então:
Conteúdo
Tente lembrar que o público não trabalhou em sua área durante meses como você.
Pelo menos metade da sua apresentação deve ser plenamente compreensível a todos.
Lembre-se sempre do propósito da apresentação dos slides: eles devem em primeiro lugar auxiliar na exposição das ideias durante a apresentação e não uma referência documental da apresentação.
Inclua nos slides somente o que você planeja utilizar durante a apresentação
Se você tiver algum slide em particular que poderá ser usado para responder perguntas, então o torne um slide oculto ou coloque-o após o último slide. Tente evitar qualquer slide que você terá que pular.
Dê referências/bibliografia no final da apresentação (para iniciantes e experts) assim pessoas interessadas podem usar isso para aprender mais sobre o assunto.
Se a sua apresentação utiliza algo que não é seu ou do seu grupo, então deixe isso claro. Por exemplo, coloque uma pequena citação dos autores originais e o ano [autor, 88]. Caso contrário é uma forma de plágio.
Evidentemente isso não é necessário para algo que é bastante conhecido ou de conhecimento público (exemplo: “Máquina de Turing”), mas se houver alguma dúvida então adicione uma citação.
Realizando a apresentação
Se existe um ponteiro a lazer por perto, use-o.
Se você receber uma pergunta e achar que o público não ouviu ou não entendeu ou não ficou claro, repita a questão: “A pergunta era …” ou “Eu não tenho certeza se entendi, mas acho que a pergunta foi …”, etc. Assim todos saberão o que você está tentando responder.
Lembre-se que a maioria da platéia provavelmente também deverá ministrar palestras e irão se solidarizar com a sua dificuldade, então tente relaxar.
Fonte: ASAP Research Group
Fechar Janela
O sistema visa automatizar o preenchimento do horário de atividades docente com base na Resolução nº 070/2017-CAD e recomendação da PRH, dando mais celeridade e mais confiabilidade, além de gerar uma padronização.
O objetivo principal desta pesquisa consiste na investigação e no desenvolvimento de modelos e algoritmos aplicáveis em problema computáveis de escalonamento e problemas correlatos.
No contexto de hospitais, estamos desenvolvendo algoritmos de otimização de escalonamento de enfermeiros.
Para o caso de escalonamento de enfermeiros já temos resultados concretos publicados em evento internacional, o que nos permite propor a investigação de novas estruturas de busca na vizinhança baseada na resolução de modelos de programação matemática e grafos. Estas técnicas ainda não são encontradas na literatura, sendo, portanto, uma contribuição inédita para o estado da arte.
Propomos estender a investigação dos algoritmos heurísticos encontrados até o presente momento, combinando com programação matemática, aplicando-os em novos problemas de escalonamento.
Além dos aspectos práticos, esses problemas são fomentadores da investigação de algoritmos eficientes, estimulando o desenvolvimento de novas técnicas que proporcionem avanços no projeto de algoritmos também para outros fins.
Fechar Janela