 |
Carla Negri LintzmayerProfessor Adjunto - Atual Coordenadora da Pós-Graduação em Ciência da ComputaçãoE-mail: carla.negri@ufabc.edu.br Tel: (+55) (11) 4996-8304 (Sala) Office: Bloco A, Torre 2, Sala 508-2 Centro de Matemática, Computação e Cognição (CMCC) Universidade Federal do ABC (UFABC) Av. dos Estados, 5001 Bairro Bangu - Santo André - SP - Brasil 09210-580 |
|
Research interests ✍
Combinatorial OptimizationApproximation Algorithms
Design and Analysis of Algorithms
Graph Theory
Combinatorics of Genome Rearrangements
"Suppose computers were infinitely fast and computer memory was free. Would you have any reason to study algorithms? The answer is yes, if for no other reason than that you would still like to demonstrate that your solution method terminates and does so with the correct answer."
(Introduction to Algorithms by T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein.)
Orientações 👣
Meus interesses fazem parte da área de Teoria da Computação, com ênfase
em Análise de Algoritmos, Otimização Combinatória e Teoria Estrutural de
Grafos.
Problemas em Otimização Combinatória têm como objetivo encontrar a melhor
solução dentro de um enorme mas finito conjunto de soluções
possíveis.
Eles surgem naturalmente de aplicações práticas (minimizar rotas de
veículos, maximizar lucro, minimizar desperdício de material de produção,
minimizar uso de recursos disponíveis, entre tantos outros) e, de modo
geral, testar todos os elementos dentre as soluções possíveis na busca
pela melhor mostra-se inviável na prática, mesmo para instâncias de
tamanho moderado.
Estratégias que têm tido sucesso para tratar estes problemas envolvem
métodos em algoritmos de aproximação, heurísticas e programação inteira,
por exemplo.
Esse material dá uma ideia
geral sobre a área de otimização e as abordagens utilizadas para tratar
esses problemas, com alguns exemplos.
Muitos problemas de otimização combinatória também envolvem grafos,
discutidos a seguir.
Um grafo é uma estrutura que representa relações par-a-par entre objetos,
podendo representar inúmeras situações reais. São compostos de vértices (os
objetos) e arestas (as relações).
Por exemplo, vértices podem representar cidades enquanto arestas indicam
se duas cidades são vizinhas; vértices podem representar clientes e
fábricas e arestas podem indicar quais fábricas atendem quais clientes;
vértices podem representar atividades a arestas podem indicar que duas
atividades não podem ser realizadas ao mesmo tempo; entre outras. Além
disso, atributos como cores e pesos podem ser associados aos vértices
e/ou às arestas, aumentando ainda a gama de situações que podem ser
representadas por eles.
Em Teoria dos Grafos, o objetivo é estudar essas estruturas de um ponto
de vista teórico, de forma a entender melhor as leis que os governam.
Procuro alunos que tenham afinidade com e gosto por matemática, análise de algoritmos e programação, criatividade, iniciativa, motivação e organização, para trabalhar em problemas e técnicas relacionados à área de Otimização Combinatória ou em Teoria Estrutural de Grafos.
Se você estiver interessado(a), fique a vontade para me enviar um e-mail falando um pouco sobre você (descreva suas experiências, motivações, disciplinas que cursou, porquê se interessou pela minha área) e eu entrarei em contato assim que possível.
Students 🐣
Current master students:- Lucas Sampaio da Rocha (since 01/2020).
Decomposições Localmente Irregulares e a Conjecture 1-2-3.
- Gustavo da Silva Teixeira (since 06/2021).
Uma introdução à complexidade parametrizada. - Matheus Fellone dos Santos (since 03/2020).
Algoritmos para o problema de realocação de blocos. - Carolina Fugita Oliveira (since 03/2021).
Problemas de empacotamento e cobertura.
- Gustavo Borges Lugoboni (from 12/2019 to 05/2021).
Um método para simular e verificar Redes de Petri Aninhadas. - Kent Emershon Yucra Quispe (co-supervisor, from 02/2017 to 04/2018). CAPES scholarship.
Algoritmos para o Problema de Realocação de Blocos. - Alexsandro Oliveira Alexandrino (co-supervisor, from 02/2017 to 02/2019). Fapesp scholarship.
Problemas de Ordenação de Permutações por Operações Ponderadas pelo Número de Fragmentações. - Guilherme Henrique Santos Miranda (co-supervisor, from 02/2017 to 02/2019). CAPES scholarship.
O Problema da Ordenação de Permutações por Operações de Tamanho Limitado.
- Gustavo da Silva Teixeira (from 06/2020 to 06/2021). Fapesp scholarship.
Problemas de Transformação de Strings por Operações Rearranjo. - Gustavo da Silva Teixeira (from 08/2019 to 05/2020). CNPq/Fapesp scholarship.
Problemas de Rearranjos de Genomas sobre Strings. - Wesley Lima de Araújo (from 11/2020 to 06/2021). Fapesp scholarship.
Algoritmos para coloração de grafos. - Wesley Lima de Araújo (from 09/2019 to 08/2020). Fapesp scholarship.
Algoritmos de Aproximação. - Guilherme Naziozeno Barreto (from 08/2019 to 08/2020).
Problemas de Balanceamento de Carga em Teoria dos Jogos Algorítmica. - Letícia Almeida Santos (from 08/2018 to 07/2019).
Algoritmos para Problemas de Roteamento de Veículos. - Lucas da Silva de Lima (from 08/2019 to 08/2020). CNPq scholarship.
Algoritmos em Grafos. - Marcelo Tranche de Souza Junior (from 08/2018 to 07/2019).
Algoritmos para os problemas do Caixeiro Viajante e da Árvore de Steiner. - Marcelo Tranche de Souza Junior (from 08/2019 to 08/2020).
Algoritmos para o problema do Caixeiro Viajante.
Publications 👩💻
Teaching (Disciplinas) 🥑
Os materiais a seguir são de revisão para as disciplinas que eu ministro, feitos por mim:
|
Outros:
Anteriores:
Events organization 🍵
Events participation 🗺
Interesting stuff 🧁
About me 🐧
| 2017 - 2018 | Postdoctoral researcher in Computer Science University of Campinas (UNICAMP), Brazil Title: One and Two-dimensional Bin Packing with Conflicts and Unloading Restrictions Supervisor: Flávio Keidi Miyazawa (Curriculum Lattes) (also working with Eduardo Candido Xavier (Curriculum Lattes)) Scholarship: Fundação de Amparo à Pesquisa do Estado de São Paulo (Fapesp) Bibliography for Packing and some related problems |
||
| 2012 - 2016 | Ph.D. in Computer Science University of Campinas (UNICAMP), Brazil with a 6 month period at University of Nantes, France (under orientation of Guillaume Fertin) Title: The Problem of Sorting Permutations by Prefix and Suffix Operations Supervisor: Zanoni Dias (Curriculum Lattes) Scholarship: Fundação de Amparo à Pesquisa do Estado de São Paulo (Fapesp) My Thesis (in English) and the implementation of the algorithms I proposed Bibliography for Genome Rearrangements |
||
| 2008 - 2011 | B.Sc. in Computer Science State University of Maringá (UEM), Brazil Title: Heuristic Algorithms for Graph Coloring (in Portuguese) Supervisor: Mauro Henrique Mulati (Curriculum Lattes) |