2º ETC

Encontro de Teoria da Computação

Sobre o evento

O II Encontro de Teoria da Computação (ETC 2017) é um fórum voltado para a grande área de Teoria da Computação, sendo proposto por membros da Comissão Especial em Algoritmos, Combinatória e Otimização (CE-ACO), com objetivo de promover uma maior divulgação da área para a comunidade brasileira de computação e afins, através do principal evento da SBC, o XXXVII CSBC.

Este evento é voltado para os alunos em formação, mas também visando proporcionar uma maior integração entre os pesquisadores e profissionais que atuam na mesma, seja com enfoque em teoria pura ou em aplicações, estimulando a discussão da importância dos fundamentos da computação e sua aplicação direta no entendimento e resolução de problemas das mais diversas áreas e segmentos de mercado.

Durante o CSBC, será realizado o II DACO (Desafio de Algoritmos, Combinatória e Otimização), cujos detalhes serão repassados posteriormente.

Datas importantes

  • Prazo estendido: 19.03
    26 março 2017
    Deadline para submissão dos trabalhos
  • Prazo estendido: 24.04
    01 maio 2017
    Deadline para notificação aos autores
  • 07 maio 2017
    Deadline para envio da versão final

Trabalhos aceitos

Artigos aceitos para apresentação oral

Título Autores
Análise dos Tempos de Setup Dependentes da Sequência em uma Empresa do Polo Industrial de Manaus através da Regra de Liberação e do Algoritmo Genético Luiz Bentes, Wesley Rocha, Renata da Encarnação Onety
Facility Leasing with Penalties Murilo de Lima, Mario San Felice, Orlando Lee
Número de Ramsey relativo a arestas de potências de caminhos Dennis Clemens, Matthew Jenssen, Yoshiharu Kohayakawa, Natasha Morrison, Guilherme Oliveira Mota, Damian Reding, Barnaby Roberts
Biclique edge-choosability in some classes of graphs Gabriel Sobral
Advances in Anti-Ramsey Theory for random graphs Guilherme Oliveira Mota
Vertex-disjoint path covers in graphs Renzo Gomez
Uma Aproximação para o Problema de Alocação de Terminais com Capacidade Lehilton Lelis Chaves Pedrosa, Vinícius Balbino de Souza
Sobre as relações racionais intrinsicamente ambíguas Rodrigo de Souza
Método Exato para Um Problema de Alocação Justa Edênis Azevedo
Deletion Graph Problems Based on Deadlock Resolution Alan Carneiro, Uéverton Souza, Fabio Protti
Representações Implícitas Probabilísticas de Grafos Juan Lopes, Fabiano Oliveira, Paulo Pinto
Epistemic Logic Based on Dolev-Yao Model Mário Benevides, Luiz Fernandez, Anna Oliveira
Edge-colouring of triangle-free graphs with no proper majors Leandro Zatesko, Renato Carmo, André Guedes
New Insights on Prize Collecting Path Problem Edcarllos Santos, Alfredo Candia, Luiz Satoru Ochi, Luidi Simonetti, Uéverton Souza
Um algoritmo exato para biclique-coloração Guilherme de Castro Mendes Gomes, Vinicius dos Santos
Coloração arco-íris em grafos resultantes de produto cartesiano Aleffer Rocha, Sheila Almeida
Hitting all longest cycles in a graph Cristina Fernandes, Juan Gutierrez
Uma generalização dos Códigos Hamming Natália de Souza, Paulo Pinto, Jayme Szwarcfiter
The 1,2,3-Conjecture for powers of paths and powers of cycles Atílio Luiz, C. N. Campos
Uma versão algoritmica do Lema Local de Lovász Bruno Cavalar
Least-Dependency Constrained Spanning Tree Problem Manoel Campelo, Luiz Alberto Viana
On a joint technique for Hajós' and Gallai's Conjectures Fabio Botler, Maycon Sambinelli, Rafael S. Coelho, Orlando Lee
Uma técnica para obtenção de atratores de autômatos celulares elementares Eurico Ruivo, Pedro de Oliveira
Grafos do tipo Half Cut Rubens Sucupira, Sulamita Klein, Luerbio Faria
Tight bounds for gap-labellings Celso Aimbiré Santos, C. N. Campos, Rafael Schouery
Modelo Matemático para o Problema de Transporte Escolar em Zonas Rurais Jean Araujo
Abordagens Heurísticas para o p-Cabo-Trincheira com Localização de Instalações Ulysses Rocha, Natanael Ramos, Lucas Melo, Marcelo Benedito, André Silva, Rafael Cano, Flavio Miyazawa, Eduardo Xavier
Algoritmo de Aproximação o Problema da Evacuação por Ônibus Lehilton Lelis Chaves Pedrosa, Rafael Schouery
Modelos para o Problema de Alocação de Pedágios Alloma Silva, Geraldo Robson Mateus
Reconhecendo Grafos com até 1 Cruzamento André Silva, Orlando Lee
Utilizando álgebras de flags para problemas de combinatória extremal Roberto Parente, Cristiane M. Sato
Minimum Weight t-Spanner Tree Problem Hugo Braga
Tighter Analysis of an Approximation for the Cumulative VRP Mauro Henrique Mulati, Flavio Miyazawa

Artigos aceitos para apresentação em pôster

Título Autores
Cellular automata for pattern recognition Hallefy Clariano, Núbia Silva
Heurísticas de Construção no Problema de Tabela-Hórario de Universidades Renan Costalonga Monteiro, Edmar Kampke
Representação de Sinais da Língua Brasileira de Sinais (LIBRAS) em Autômatos Finitos Eric Cabral, Patrick Brito
Algoritmo Branch-and-Bound para o Problema do Caixeiro Alugador Vítor Marques
PMIH: Poliedro Maximal de Vértices em Z^n Inscrito em uma Hiperesfera em R^n Yuri Tavares dos Passos, Eleazar Lozada
Coloração 2-backbone de grafos periplanares com um emparelhamento como backbone Julio Araujo, Camila Araújo, Alexandre Cezar

Artigos

Convidamos a comunidade a compartilhar resultados de pesquisa por meio da submissão de resumos estendidos de no máximo 4 páginas, seguindo o modelo de artigo da SBC (feito em latex preferencialmente, ou DOC, mas, submetendo o PDF do artigo), abrangendo tanto pesquisas em nível de pós-graduação como também iniciação científica na graduação.

Os trabalhos devem ser submetidos na forma de resumos estendidos formatados seguindo o estilo dos artigos da SBC. Devem ter no máximo 04 páginas incluindo referências, figuras e tabelas. A submissão dos artigos será eletrônica, em formato PDF, por meio do sistema JEMS.

Os trabalhos serão selecionados para apresentação oral de até 15 minutos ou para exposição em poster, a depender do volume de submissões e da qualidade das mesmas. O evento é aberto para a comunidade, mas com especial interesse nos alunos em formação de graduação e de pós-graduação. O melhor trabalho apresentado será objeto de premiação, a ser divulgado com as demais premiações do CSBC. Os trabalhos aceitos serão publicados em anais eletrônicos na página do CSBC.

Pelo menos um dos autores de cada artigo aceito deve se inscrever no evento e comparecer ao mesmo para apresentar o trabalho.

Tópicos de interesse

  • Algoritmos: análise e projeto de algoritmos, técnicas de decomposição e balanceamento, algoritmos exatos, algoritmos aproximativos, algoritmos randomizados, algoritmos online, algoritmos distribuídos e paralelos.
  • Complexidade Computacional: análise de problemas e algoritmos, NP-completude, reduções polinomiais, prova de polinomialidade, classes de complexidade de tempo e espaço, complexidade parametrizada, análise amortizada, inaproximabilidade, algoritmos, abordagens lógicas à complexidade computacional, aplicações.
  • Computabilidade: modelos teóricos de computação, métodos e linguagens formais, autômatos, autômatos celulares, computabilidade de Turing e generalizações, teoria da prova, teoria da recursão, reduções, decidibilidade, definabilidade, conjuntos enumeráveis, sistemas de prova interativa, matemática reversa, redes de Petri, aplicações.
  • Otimização Combinatória: estruturas combinatórias, combinatória poliédrica, métodos exatos e aproximados, métodos de busca global e de busca local, otimização multiobjetiva, otimização estocástica, otimização em redes, pesquisa operacional, modelagem e aplicações.
  • Programação Matemática: formulações, programação inteira linear e não-linear, programação por restrições, métodos enumerativos, cortes no plano, branch-and-bound, branch-and-cut, branch-and-price, branch-cut-and-price, branch-and-prune, métodos híbridos exato-heurístico, programação dinâmica, etc.
  • Teoria dos Grafos e Combinatória: caracterização estrutural, classes de grafos, reconhecimento, estruturas proibidas, problemas clássicos, desenho e layout de grafos, teoria espectral, grafos aleatórios, complexidade, algoritmos, aplicações.
  • Teoria da Informação, Números e Criptografia: fundamentos, teoria de códigos, sistemas numéricos, aritmética modular, congruências, divisibilidade, codificação de fonte, corretores de erro, compressão, criptoanálise, protocolos com segurança demonstrável, algoritmos, aplicações.
  • Teoria dos Jogos e da Decisão: fundamentos, estratégias competitivas, sistemas em equilíbrio, equilibrio de Nash, dominância, preço da anarquia e da estabilidade, leilão e meecanismos, precificação, jogos cooperativos, jogos combinatórios, pesquisa operacional, algoritmos, aplicações.
  • Geometria Computacional: espaços métricos, geometria de distâncias, algoritmos geométricos,estruturas baseadas em propriedades geométricas, estruturas espaciais, aplicações.
  • Aplicações em outras áreas de conhecimento e problemas práticos: alocação de recursos, apoio à tomada de decisão, biologia computacional, compiladores, economia, escalonamento, engenharias, estrutura molecular, pesquisa operacional, probabilidade e estatística, processos produtivos, reconhecimento de padrões, redes de computadores, redes complexas, redes livres de escala e redes web, robótica, roteamento, segurança de código, sistemas e redes, sistemas paralelos e distribuídos, teoria de conjuntos, visualização de dados, aplicações com grandes massas de dados, aplicações dinâmicas, aplicações de tempo real.

Organização

Coordenação Geral

  • Nizam Omar, Mackenzie
  • Luciano Silva, Mackenzie

Coordenação

  • Cláudia Linhares Sales, UFC
  • Rosiane de Freitas,UFAM

Comitê de Programa

  • Ana Teresa Martins, UFC
  • Calebe Bianchini, Mackenzie
  • Carlos E. Ferreira, USP
  • Celina M.H. de Figueiredo, UFRJ
  • Cláudia Linhares Sales, UFC
  • Claudson Bornstein, UFRJ
  • Cristina G. Fernandes, USP
  • Edson Cárceres, UFMS
  • Erika Morais, UFG
  • Fábio Protti, IC/UFF
  • Flavio Keidi Miyazawa, UNICAMP
  • Jayme Szwarcfiter, UFRJ/UERJ
  • Luciana Buriol, UFRGS
  • Luerbio Farias, UERJ
  • Luiz C. Lamb, UFRGS
  • Luiz Satoru Ochi, UFF
  • Mario Benevides, UFRJ
  • Manoel Campelo, UFC
  • Rosiane de Freitas, UFAM
  • Vinicius Santos, UFMG

Coordenação Local

  • Pedro P.B. de Oliveira, Mackenzie