1º ETC - Encontro de Teoria da Computação
Nome do Evento: I ETC – Encontro de Teoria da Computação
Coordenadoras do evento: Claudia Linhares (UFC) e Rosiane de Freitas (UFAM)
Apoio local: Alfio Martini (PUCRS)
Instituição organizadora: Instituto de Informática – UFRGS
E-mail para Contato: rosiane@icomp.ufam.edu.br
04 e 05 de julho de 2016
CHAMADA DE PARTICIPAÇÃO
O I Encontro de Teoria da Computação (ETC 2016) é 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 XXXVI CSBC (Congresso da Sociedade Brasileira de Computação). Este ano o Congresso da SBC discutirá "Computação e Interdisciplinaridade" e o I ETC está bem contextualizado com esta temática, pois visa mostrar através das palestras plenárias e dos trabalhos aceitos, a diversidade de conteúdos e a total interação com outras disciplinas da Computação, estimulando a discussão da importância dos fundamentos teóricos da computação e suas aplicações no entendimento e resolução de problemas das mais diversas áreas e segmentos de mercado.
Ao longo dos dois dias do evento, contaremos na abertura com a apresentação da área de Teoria da Computaçao no Brasil, proferida pelo professor Jayme Szwarcfiter (UFRJ).e o o lançamento do I DACO (Desafio de Algoritmos, Combinatória e Otimização). Teremos também 03 (três) excelentes palestras a serem proferidas pelos professores Celina de Figueiredo (UFRJ), Luciana Buriol (UFRGS), Luiz Satoru Ochi (UFF) e Luis Lamb (UFRGS).Na abertura, teremos também
Tivemos 40 submissões de trabalhos, com autores de instituiçoes de todas as 05 regiões do Brasil e também dos EUA, Canadá, França e Argentina, sendo 34 trabalhos aceitos e, destes, 28 com apresentação oral distribuídos em seis sessões técnicas, e 06 trabalhos para a sessão de exposição de pôsteres.
Os 8 melhores trabalhos classificados são listados ao final e, destes, os 3 melhores serão divulgados na Abertura do I ETC. O Prêmio de Melhor Trabalho do I ETC será dado no jantar do CSBC 2016.
A programação detalhada do I ETC pode ser encontrada ao final desta mensagem ou no site web do CSBC,
Contamos com a presença de todos em Porto Alegre! E prestigiem o I ETC!
Cordialmente,
Claudia Linhares (UFC)
Rosiane de Freitas (UFAM)
-------------------------
PROGRAMAÇÃO
04 de julho de 2016
8:00 – 8:55
Abertura
Rosiane de Freitas - UFAM
Lançamento I Desafio de Algoritmos, Combinatória e Otimização – DACO
Vinicius dos Santos - UFMG e Claudson Bornstein-UFRJ
8:55 - 9:10
A área de Teoria da Computação no Brasill
Jayme Szwarcfiter - UFRJ
9:10 – 10:30 – Sessão técnica I
Minimal Obstructions of (2,1)-cographs with external restrictions
Raquel Bravo (UFF - Brasil), Fabio Protti (UFF - Brasil), Loana Nogueira (UFF - Brasil), Cláutenis Viana (Instituto Federal do Piauí – Brasill)
On Linial's Conjecture for Split Digraphs
Maycon Sambinelli (UNICAMP- Brasil), Orlando Lee ( UNICAMP - Brasil), Cândida Silva (USP-SCarlos at Sorocaba – Brasil)
On Colored Edge Cuts in Graphs
Luerbio Faria (UERJ - Brasil), Sulamita Klein (UFRJ - Brasil), Ignasi Sau (CNRS, LIRMM, Montpellier - France), Uéverton Souza (UFF - Brasil), Rubens Sucupira (UERJ – Brasil)
Frustração de Arestas em (3,6)-Fullerenes
Diego Nicodemos (UFRJ - Brasil), Sulamita Klein (UFRJ - Brasil), Luerbio Faria (UERJ – Brasil)
10:30 – 11:00 – Intervalo - coffee-break
11:00 – 11:40 - Palestra I
Lógica em Computação, IA e Cognição
Prof. Dr. Luis C. Lamb (UFRGS)
11:40 – 13:20 – Sessão técnica II
Descriptive Complexity of Probabilistic Complexity Classes through Second Order Generalized Quantifiers
Thiago Rocha (IFCE - Brasil), Ana Teresa Martins (UFC - Brasil)
A Gramática de Grafos como uma alternativa para o desenvolvimento do Pensamento Computacional na Educação Básica
Braz Junior (UFPel - Brasil), Simone Cavalheiro ( UFPel - Brasil), Luciana Foss ( UFPel – Brasil)
Sobre coloração total dos grafos r-partidos completos
Raphael Martins (UERJ -Brasil), Diana Sasaki (Université Paris Dauphine – France)
Amostragem Gaussiana na Criptografia Baseada em Reticulados
Jheyne N. Ortiz (UNICAMP - Brasil), Ricardo Dahab ( UNICAMP - Brasil), Diego Aranha ( UNICAMP – Brasil)
Achieving CCA1-security in homomorphic encryption
Eduardo Morais (UNICAMP - Brasil), Diego Aranha ( UNICAMP - Brasil), Ricardo Dahab ( UNICAMP - Brasil)
13:30 – 14:30 - Intervalo Almoço
14:30 – 16:30 - SECOMU
16:30 – 17:00 - Intervalo - coffee-break
17:00 – 17:40 - Palestra II
Intratabilidade e Otimização: uma Homenagem ao David Johnson
Prof. Dr. Celina de Figueiredo (UFRJ)
Luciana Buriol (UFRGS)
17:40 – 18:40 – Sessão técnica III
Análise de um algoritmo aproximativo para o problema de escalonamento de tarefas com restrições de precedência em máquinas paralelas idênticas
Elton Lever (UFAM- Brasil), Omar Vilca (UFAM - Brasil), Rosiane de Freitas (UFAM - Brasil)
Some families of 0-rotatable graceful caterpillars
Atílio Luiz ( UNICAMP - Brasil), C. N. Campos (UNICAMP-Brasil), Bruce Richter (University of Waterloo – Canada)
Computação sobre dados cifrados em GPGPUs
Pedro Alves (UNICAMP - Brasil), Diego Aranha ( UNICAMP - Brasil)
18:40 – 19:20 - Exposição de pôsteres
Stochastic scenario generation: an empirical approach
Alan Delgado de Oliveira (UFRGS - Brasil), Tiago Filomena (UFRGS – Brasil)
Análise e Comparação dos Algoritmos de Dijkstra e A-Estrela na Descoberta de Caminhos Mínimos em Mapas de Grade
Marcel Rios (UFAM - Brasil), Francisco S.S Neto (UFAM - Brasil), José Francisco Netto (UFAM – Brasil)
Um modelo RCPSP para Gestão Ágil Scrum
Osmar Leandro Dantas da Silva (IFCE - Brasil), Emanuel Dantas Filho (IFCE - Brasil), Diego Rocha Lima (IFCE - Brasil)
KM-Finder: Uma Ferramenta para Detecção de Motivos
Lucas Vilhagra (UFMS - Brasil), Luciana Montera (UFMS - Brasil), Taina Alencar (FIOCRUZ)
Estruturas de Dados Probabilísticas para Representação de Conjuntos
Juan Lopes (UERJ - Brasil), Paulo Pinto (UERJ - Brasil), Fabiano Oliveira (UERJ – Brasil)
Análise Empírica do Algoritmo Shellsort
Paulo Pinto (UERJ - Brasil), Fabiano Oliveira (UERJ - Brasil), Raquel Souza (UERJ – Brasil)
05 de julho de 2016
8:30 – 9:50 – Sessão técnica IV
Algoritmos Branch-and-Price para o Problema de Empacotamento em Recipientes com Restrições de Classe
Yulle Glebbyo Felipe Borges (UNICAMP - Brasil), Flávio Miyazawa (UNICAMP - Brasil), Rafael Schouery (UNICAMP - Brasil), Eduardo Xavier (UNICAMP – Brasil)
Uma Aproximação para o Problema de Alocação de Terminais
Lehilton Pedrosa (UNICAMP - Brasil), Vinicius dos Santos (UFMG - Brasil), Rafael Schouery (UNICAMP – Brasil)
UKP5: Solving the Unbounded Knapsack Problem
Henrique Becker (UFRGS - Brasil), Luciana Buriol (UFRGS – Brasil)
Uma Abordagem baseada nas Preferências dos Docentes para o Problema de Programação de Horários em Universidades
Osmar Leandro Dantas da Silva (IFCE - Brasil), Diego Rocha Lima (IFCE - Brasil)
9:50 – 10:30 - Palestra III
Problemas de Edição de Arestas em Grafos
Prof. Dr. Luiz Satoru Ochi (UFF)
10:30 – 11:00 – Intervalo - coffee-break
11:00 – 13:00 – Sessão técnica V
On a Leasing Variant of the Online Connected Facility Location Problem
Murilo de Lima (UNICAMP - Brasil), Mario San Felice (UNICAMP - Brasil), Orlando Lee (UNICAMP – Brasil)
Sobre a minimização de transdutores sequenciais
Rodrigo de Souza (UFRPE – Brasil)
Quantificando o vazamento de informações sobre estratégias
Mário Alvim (UFMG - Brasil), Piotr Mardziel (University of Maryland, College Park - USA), Michael Hicks (University of Maryland, College Park – USA)
Compartilhamento de Custos de Empacotamento
Flávio Miyazawa (UNICAMP - Brasil), Rafael Schouery (UNICAMP – Brasil)
Algoritmos aleatorizados com oráculo para MCSP: aplicações para o problema do resíduo quadrático e do logaritmo discreto
Nicollas Sdroievski (UTFPR - Brasil), Murilo da Silva (UTFPR – Brasil)
Um Leilão à Prova de Estratégia para o Compartilhamento de Viagens Dinâmico com Múltiplos Passageiros
Leonardo Schwarzstein (UNICAMP - Brasil), Rafael Schouery (UNICAMP - Brasil), Flávio Miyazawa (UNICAMP – Brasil)
13:00 – 14:30 - Intervalo Almoço
14:30 – 16:30 - SECOMU
16:30 – 17:00 - Intervalo - coffee-break
17:00 – 17:40 – Sessão técnica VI
Caracterizações de convexidades geométricas de grafos
Rafael Teixeira de Araujo (UFC - Brasil), Rudini Sampaio (UFC – Brasil)
Results on Circular-Arc Bigraphs
Fabricio Kolberg (UFPR - Brasil), Marina Groshaus (Universidad de Buenos Aires - Argentina), André Guedes (UFPR - Brasil), Renato Carmo (UFPR – Brasil)
O Problema da Atribuição Dupla de Custo Mínimo
Vinicius dos Santos (UFMG - Brasil), Sebastian Urrutia (UFMG – Brasil)
The Geodetic Carathéodory Number
Eduardo Silva Lira (UFGO - Brasil), Diane Castonguay (UFGO - Brasil), Erika Coelho (UFGO - Brasil), Hebert da Silva (UFGO - Brasil)
Padrão de Desenho para a Família de Grafos Gêmeos
Cassio Ferreira Merlo (UFES - Brasil), Mauro Pinheiro (UFES - Brasil), Marcia Paiva (UFES – Brasil)
An Efficient Algorithm for the Closest String Problem
Omar Latorre (UFAM - Brasil), Rosiane de Freitas (UFAM - Brasil)
PALESTRAS
Palestra I
Lógica em Computação: IA e Cognição
Luis C. Lamb (Universidade Federal do Rio Grande do Sul)
Desde o início do século XX, estudos em em teoria da recursão e compatibilidade levaram a resultados científicos que tiveram destacada relevância em Ciência da Computação. O impacto da lógica foi tão significativo que a mesma foi considerada por pesquisadores eminentes como o "cálculo da Ciência da Computação". Posteriormente, o desenvolvimento de áreas como a Inteligência Artificial contribuiu para o desenvolvimento da lógica computacional. Nesta palestra, apresentaremos uma breve análise da contribuição da lógica à Ciência da Computação, com destaque aos resultados que contribuíram diretamente no desenvolvimento dessa ciência e que tiveram impacto e aplicação em diversas tecnologias.
Palestra II
Intatibilidade e Otimização: uma Homenagem ao David Johnson
Celina de Figueiredo (Universidade Federal do Rio de Janeiro)
Luciana Buriol (Universidade Federal do Rio Grande do Sul)
Faremos uma homenagem a David Johnson (1945–2016), destacando as suas contribuições para a análise teórica e experimental de algoritmos. Ao longo da sua brilhante carreira de 40 anos no Bell Las Research, foi chefe do departamento de Fundamentos Matemáticos de Computação e do departamento de Algoritmos e Otimização. David Johnson liderou na ACM a área de Algoritmos e Teoria da Computação, através da criação da conferência ACM-SIAM SODA e do grupo de interesse ACM SIGACT. O seu livro "Computers and Intractability: A Guide to the Theory of NP-Completeness" e a sua série "An Ongoing Guide on NP-completeness" constituem os fundamentos para o desenvolvimento da teoria que identifica os problemas difíceis. Ele criou e liderou nos últimos 25 anos as DIMACS Implementation Challenges para computação experimental buscando o rigor científico na avaliação empírica de algoritmos.
Palestra III
Problemas de Edição de Arestas em Grafos
Luiz Satoru Ochi (Universidade Federal Fluminense)
O Problema de Clusterização por Edição de Arestas (PCEA) consiste em transformar um grafo G em um "cluster graph" (união disjunta de subgrafos completos), através do menor número de operações de edição de arestas. Cada operação de aresta consiste em uma adição de uma nova aresta ou em uma remoção de um aresta existente. O Problema de Biclusterização por Edição de Arestas (PBEA) é um problema de biclusterização similar ao PCEA, dado como entrada um grafo bipartido G, seu objetivo é transformar G em uma união disjunta de grafos bipartidos completos (bicliques) através do menor número de operações de edição de aresta. Problemas de Edição de Arestas em Grafos apresentam diversas aplicações, dentre elas: processamento de imagem, projeto de redes multicast, análise da dados biológicos e formação de células de manufatura. Nesta palestra será apresentado o desenvolvimento de novos resultados teóricos, metaheurísticas, métodos exatos e algoritmos híbridos para os Problemas de Edição de Aresta em Grafos. Este é um trabalho em conjunto com Anand Subramanian (UFPB), Fábio Protti (UFF), Gilberto Sousa (UFF e UFPB), Ivan Martins (UFF), Lucas Bastos (FINEP), Lucídio Cabral (UFPB), Luidi Simonetti (UFRJ), Rian Pinheiro (UFRPE) e Teobaldo Bulhões Júnior (UFF).
I DESAFIO DE ALGORITMOS, COMBINATÓRIA E OTIMIZAÇÃO (I DACO)
Na aberuura do I ETC,, segunda-feira 04/07 às 8:30, será divulgado o I DACO (I Desafio de Algoritmos, Combinatória e Otimização), uma competição envolvendo a elaboração de solução algorítmica para problemas sem uso de computador. O resultado deverá ser entregue até 9h da manhã d terça-feira, dia 05/07, e a divulgação dos vencedores será feita no jantar do evento.
Maiores detalhes se encontram em http://etc.dcc.ufmg.br/daco.html.
PRÊMIO DE MELHOR TRABALHO DO I ETC
1a FASE – 8 trabalhos melhor classificados
On Linial's Conjecture for Split Digraphs
Maycon Sambinelli, Orlando Lee, Cândida Silva
On a Leasing Variant of the Online Connected Facility Location Problem
Murilo de Lima, Mario San Felice, Orlando Lee
On Colored Edge Cuts in Graphs
Luerbio Faria, Sulamita Klein, Ignasi Sau, Uéverton Souza, Rubens Sucupira
Descriptive Complexity of Probabilistic Complexity Classes through Second Order Generalized Quantifiers
Thiago Rocha, Ana Teresa Martins
UKP5: Solving the Unbounded Knapsack Problem
Henrique Becker, Luciana Buriol
Sobre coloração total dos grafos r-partidos completos
Raphael Martins, Diana Sasaki
Some families of 0-rotatable graceful caterpillars
Atílio Luiz, Christiane Campos, Bruce Richter
Achieving CCA1-security in homomorphic encryption
Eduardo Morais, Diego Aranha, Ricardo Dahab
2a FASE - 3 melhores trabalhos
A serem divulgados na Abertura do I ETC
3a FASE: melhor trabalho do I ETC
A ser definido após a avaliação das apresentações, com o resultado a ser divulgado no Jantar do CSBC 2016.
-------------------------------------------
COORDENAÇÃO GERAL DO CSBC 2016
Avelino Zorzo (PUCRS)
COORDENAÇÃO DO I ETC
Cláudia Linhares Sales (DC, UFC) - linhares@lia.ufc.br
Rosiane de Freitas (IComp, UFAM) - rosiane@icomp.ufam.edu.br
Apoio Local: Alfio Martini (PUCRS)
COMITÊ DE PROGRAMA
Ana Teresa Martins (DC, UFC)
Claudson Bornstein (DCC - IM, UFRJ)
Edson Cáceres (FACOM, UFMS
Fábio Protti (IC, UFF)
Flavio Keidi Miyazawa (IC, UNICAMP)
Jayme Szwarcfiter (COPPE, IM e NCE, UFRJ)
Luciana Buriol (INF, UFRGS)
Luis Satoru (IC, UFF)
Mario Benevides (IM, UFRJ)
Vinícius Gusmão Pereira de Sá (DCC - IM, UFRJ)
Vinícius Fernandes dos Santos (DCC, UFMG)
SOBRE O I ETC
O I Encontro de Teoria da Computação (ETC 2016) é 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 XXXVI CSBC (Congresso da Sociedade Brasileira de Computação).
Este evento é voltado para alunos de graduação e Mestrado/Doutorado, mas também visa proporcionar uma maior integração entre os pesquisadores e profissionais que atuam na área, 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.
Este ano o Congresso da SBC discutirá "Computação e Interdisciplinaridade" e o I ETC está bem contextualizado com esta temática, pois visa mostrar através das palestras plenárias e dos trabalhos aceitos, a diversidade de conteúdos e a total interação com outras disciplinas da Computação e de outras áreas.
Neste sentido, convidamos a comunidade a compartilhar resultados de pesquisa por meio da submissão de resumos de no máximo 4 (quatro) 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.
DATAS IMPORTANTES
-
01/maio submissão dos artigos via JEMS (Estendido)
-
25/maio: notificação dos autores
-
03/junho: submissão da versão final dos artigos aceitos
-
04/julho: realização do I ETC (e I DACO) no CSBC 2016
TÓPICOS DE INTERESSE
O ETC aceita trabalhos envolvendo aspectos teóricos da Computação no geral, como exposto nos tópicos abaixo:
- 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, aplicações.
- Computabilidade: modelos teóricos de computação, métodos e linguagens formais, autômatos, 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.