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 Contatorosiane@icomp.ufam.edu.br

 

04 e 05 de julho de 2016

http://www.csbc2016.com.br

 

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.