Teoria da Computa��o e Combinat�ria DCC-IME-USP

S�rie de semin�rios de Teoria da Computa��o e Combinat�ria, mantida pelo Grupo de Combinat�ria e Otimiza��o Combinat�ria do Departamento de Ci�ncia da Computa��o do IME-USP. Sextas-feiras �s 14 horas, na sala 267-A do IME-USP.

Subgrafos geradores de grafos aleat�rios (Sala 267 do Bloco A, de 25/11/2005 14:00 at� 25/11/2005 15:00) por cris

Seja $G(n,M)$ um grafo com $n$ v�rtices e $M$ arestas. Discutiremos alguns resultados sobre subgrafos geradores dos grafos $G(n,M)$ t�picos. Concretamente, mostraremos que, para todo inteiro $r \geq 1$ fixo, se $M=\lfloor n^{2-1/2r}\rfloor$, ent�o, tipicamente, $G(n,M)$ cont�m todos os grafos com $n$ v�rtices de grau m�ximo $r$ como subgrafos (este � um resultado conjunto com R\"odl e Ruci\'nski).

Um Algoritmo Eficiente para Imers�o de �rvores em Grafos Expansores (Sala 267 do Bloco A, de 18/11/2005 15:00 at� 18/11/2005 15:00) por cris

Em 1987, Friedman e Pippenger provaram o seguinte resultado: sejam n e d inteiros positivos; se G � um grafo (n,d)-expansor, isto �, um grafo para o qual todo conjunto com r <= 2n - 2 v�rtices tem pelo menos (d + 1)*r vizinhos, e T � uma �rvore com grau m�ximo limitado por d e |V(T)| <= n, ent�o G possui T como subgrafo. A prova deste teorema n�o fornecia diretamente um algoritmo (polinomial) para encontrar a �rvore T em G (o resultado era existencial). Conseguimos acrescentar um ingrediente � demonstra��o original de forma que esta passa a ter uma vers�o algor�tmica eficiente (polinomial) que efetivamente encontra T dentro de G.

A conjetura de Woodall: um resumo (Sala 267 do Bloco A, de 21/10/2005 14:00 at� 21/10/2005 15:00) por cris

A conjetura de Woodall afirma que todo grafo (orientado) G satisfaz a minimax \nu(G) = \tau(G), sendo \nu(G) o n�mero m�ximo de jun��es mutuamente disjuntas e \tau(G) a cardinalidade de um corte (orientado) m�nimo de G. Aqui, uma jun��o � um conjunto J de arestas tal que qualquer v�rtice � ligado a qualquer outro por um caminho cujas arestas diretas est�o em J. Esta palestra pretende fazer um resumo do que se sabe sobre a conjetura. Em particular, pretende comentar os trabalhos de Cornu�jols e Guenin (2000 e 2002), Williams (2004), Shepherd e Vetta (2005).

Empacotamento de T-pseudo-caminhos n�o-nulos (Sala 267 do Bloco A, de 04/11/2005 14:00 at� 04/11/2005 15:00) por cris

Considere um grafo orientado com custos nos arcos e seja T um subconjunto de seus v�rtices. Um T-pseudo-caminho � uma sequ�ncia <v_0,a_1,v_1,...,a_k,v_k> tal que v_0,...,v_k s�o v�rtices distintos, v_0 e v_k est�o em T e a_i=(v_{i-1},v_i) ou a_i=(v_i,v_{i-1}) � um arco do grafo. O custo de um pseudo-caminho � a soma dos custos dos arcos "diretos" menos a soma dos custos dos arcos "inversos". Chudnovsky, Geelen, Gerards, Goddyn, Lohman e Seymour obtiveram um rela��o min-max para o n�mero m�ximo de T-pseudo-caminhos disjuntos de custos n�o-nulos. Veremos algumas aplica��es dessa rela��o min-max e um pequeno esbo�o de sua demonstra��o.

Intersection representations of graphs (Sala 267 do Bloco A, de 11/11/2005 14:00 at� 11/11/2005 15:00) por cris

A p-intersection representation of a graph G is a collection of sets corresponding to the vertices of G with the property that two vertices form an edge if and only if the corresponding sets intersect in at least p elements. The p-intersection number of G is the minimum size of the union of all sets in a p-intersection representation of G . Although this parameter has been studied extensively for several classes of graphs, there are still many open questions left. We will survey the results, present some open problems, and (if time permits) outline some approaches to these problems.

Hard Mixed Integer Programs in Practice (Anfiteatro Jacy Monteiro, de 23/09/2005 14:00 at� 23/09/2005 15:00) por cris

In this talk we describe three different real-world problems arising in telecommunication, energy mangement, and public mass transportation. All these problems have in common that their modelling yields very difficult mixed integer programming problems. We show how these mixed integer programs may be solved and demonstrate their success and limits in solving practical instances.

Examination of the rearrangeable blocking behaviour of Clos-Networks with respect to multicast traffic (Sala 267 do Bloco A, de 14/10/2005 14:00 at� 14/10/2005 15:00) por cris

A special layout for switching networks has been invented 50 years ago by Charles Clos and used ever since in telecommunications. We will present work aimed towards the goal of understanding, how large a Clos network has to be in order to be able to dispatch multicast (i.e. one sender, multiple recipients) communication. A mathematical model is presented and a reduction to prima facie NP-hard problems like coloring and higher order matching is given. Furthermore, for a particular set of parameters, a practically relevant example will be studied.

The life of a BAOBAB in Lyon, France (Sala Gilioli, de 30/08/2005 14:00 at� 30/08/2005 15:00) por cris

This talk will present an overview of the research activities of the BAOBAB team. It will also serve to place in context three other talks from members of the team that will follow this one, one the same day and two the day after. The BAOBAB team is part of two distinct bigger French research structures, the HELIX project of the INRIA, the national institute of research in computer science, and the "Laboratoire de Biometrie et Biologie Evolutive" (LBBE) which is a laboratory affiliated to both the CNRS and the "Universite Claude Bernard" (Lyon I). The LBBE is composed mainly of biologists, bio-mathematicians and bio-informaticians. The BAOBAB team mirrors this multidisciplinarity in a perhaps starker way. Its members come thus from mathematics, statistics, (theoretical) computer science and biology (molecular biology, evolution, biochemistry). The team has a number of objectives that reflect its varied backgrounds yet common passion for biology. Through it's head, the team has been collaborating with the IME for many years. Since January of this year, the DCC-IME is an official research partner of BAOBAB-HELIX, with support from both the INRIA and the FAPESP for developing its collaboration. It is in the context of this partnership that the talks and visits of seven members of BAOBAB to the IME are taking place. For more information on the activities of BAOBAB, you may consult: http://www.inrialpes.fr/helix/people/sagot/team/index.html For information on the partnership between BAOBAB and the DCC-IME, you may consult: http://www.inrialpes.fr/helix/people/sagot/team/projects/associated_team_usp_helix/associated_team_usp_helix.html PS: BAOBAB stands for "Biologie et Algorithmie Ou Bien Algorithmie et Biologie".

Subgrafos geradores $k$-conexos de peso m�dio m�nimo e mais... (Sala 267 do Bloco A, de 30/09/2005 14:00 at� 30/09/2005 15:00) por cris

Recentemente, Gubbala and Raghavachari (Latin'04) consideraram o problema de encontrar um subgrafo gerador $k$-conexo de peso \emph{m�dio} m�nimo, num dado grafo $k$-conexo com pesos n�o-negativos nas arestas. Eles mostraram uma 3-aproxima��o para o caso de aresta-conexidade, e uma $cH_k$-aproxima��o para o caso de v�rtice-conexidade, onde $c \geq 6$. Mostraremos um esquema que permite obter, para o problema de peso m�dio m�nimo, as mesmas raz�es de aproxima��o conhecidas para o problema de encontrar um subgrafo gerador $k$-conexo de peso m�nimo. Como conseq��ncia, deduzimos, para os problemas de peso m�dio m�nimo, uma 2-aproxima��o para o caso de aresta-conexidade e uma $2H_k$-aproxima��o para o caso de v�rtice-conexidade. O esquema pode ser aplicado para uma gama maior de problemas, estendendo um trabalho cl�ssico de Megiddo, sobre otimiza��o de fun��es racionais. Este � um trabalho conjunto com Jos� Correa (Chile) e Yoshiko Wakabayashi.

Lossless Filter for Finding Long Multiple Approximate Repetitions Using a New Data Structure, the Bi-Factor Array (Sala Gilioli, de 30/08/2005 15:00 at� 30/08/2005 16:00) por cris

Similarity search in texts, notably biological sequences, has received substantial attention in the last few years. Numerous filtration and indexing techniques have been created in order to speed up the resolution of the problem. However, previous filters were made for speeding up pattern matching, or for finding repetitions between two sequences or occurring twice in the same sequence. In this talk, we present an algorithm called NIMBUS for filtering sequences prior to finding repetitions occurring more than twice in a sequence or in more than two sequences. NIMBUS uses gapped seeds that are indexed with a new data structure, called a bi-factor array, that is also presented in this paper. Experimental results show that the filter can be very efficient: preprocessing with NIMBUS a data set where one wants to find functional elements using a multiple local alignment tool such as GLAM, the overall execution time can be reduced from 10 hours to 6 minutes while obtaining exactly the same results.

Dinucleotide over- and under-representation in complete bacterial genomes (Bacteria and Archaea) (Sala Gilioli, de 31/08/2005 15:00 at� 31/08/2005 15:00) por cris

Statistical analysis of the representation of oligonucleotides has been widely used to try and shed light over sequence structure -- to try and determine the degree in which randomness and selection play a part within biological sequences. In order to understand these features, we conducted a systematic study of the over- and under-representation of dinucleotides in completed Bacteria and Archaea genomes. In this talk, we will first present the general statistical methodology used. We will then discuss some main results.

Invariantes de grafos (Sala 267 do Bloco A, de 16/09/2005 14:00 at� 16/09/2005 15:00) por cris

Um invariante � uma fun��o que associa um n�mero real a cada grafo, sendo que grafos isomorfos recebem o mesmo valor. Para muitos invariantes de interesse, existem rela��es entre seus valores num grafo e em certos subgrafos. Isso pode ser bem capturado embutindo-se os grafos em uma estrutura alg�brica, e estendendo-se os invariantes aos elementos da estrutura. O primeiro exemplo dessa id�ia foi do novato Tutte (1947), ao estender a no��o de polin�mio crom�tico por meio de um anel, o que levou � no��o do polin�mio de Tutte de um matr�ide. Combina��o linear de invariantes tamb�m � invariante. Mais recentemente, Forman (2004) introduziu uma filtra��o no espa�o vetorial dos invariantes, e o conceito de invariantes de "tipo finito". Estes t�m v�rias propriedades alg�bricas e est�o ligados ao problema da reconstru��o. Um panorama dessas id�ias ser� apresentado.

Similarity between neighbors: selection or mutational bias inside genomes? (Sala Gilioli, de 31/08/2005 14:00 at� 31/08/2005 15:00) por cris

In all three biological worlds (eukaryotes, prokaryotes, archea) it appears that neighbor sequences (genes or non coding sequences) are more similar than random ones. These similarities are very diverse and can involve base frequencies, transcription direction, expressivity, etc. An important evolutionary question is "what are the mechanisms that create and maintain such regional similarities?" As very often, the debate between natural selection and mechanistic effects of genome functioning appears and some relevant mathematical analysis from the lab are presented.

Algoritmos quadr�ticos em tempo subquadr�tico (Sala 267 do Bloco A, de 26/08/2005 14:00 at� 26/08/2005 15:00) por cris

Um dos problemas mais fundamentais na compara��o de seq��ncias (o que inclui alinhamento de seq��ncias biol�gicas ou busca com erros de palavras em textos) � que os algoritmos de programa��o din�mica usuais rodam em tempo quadr�tico, o que pode ser caro demais em alguns casos. V�rias heur�sticas foram criadas por conta disto, sendo o BLAST uma das mais famosas. Outro enfoque tamb�m bastante eficiente e usado � o da filtragem: a identifica��o de regi�es da matriz de programa��o din�mica que sabemos s�o "mortas" e que portanto s�o excluidas dos c�lculos. Em compara��o com as heur�sticas, a filtragem tem a vantagem de n�o eliminar solu��es �timas. Nesta palestra daremos uma introduc�o sobre o conceito de q-grams, definido por Ukkonen em 1992, com algumas aplica��es passadas e recentes para o problema da filtragem. Dentre estas aplica��es incluimos a busca com erros de palavras em textos e a procura de trechos (de comprimento acima de um certo limiar) das seq��ncias com dist�ncia de edi��o menor que um certo valor.

Um AFPTAS para o Problema do Empacotamento em Faixa (Sala 267 do Bloco A, de 19/08/2005 14:00 at� 19/08/2005 15:00) por cris

O Problema do Empacotamento em Faixa � o seguinte: dados n ret�ngulos, cada qual com largura e altura no m�ximo 1, encontrar um empacotamento desses ret�ngulos numa faixa de largura 1 (e altura ilimitada), de modo a minimizar a altura da faixa que � usada. Apresentaremos um AFPTAS (esquema de aproxima��o assint�tico completamente polinomial) para esse problema, desenvolvido por Kenyon e R�mila. Mencionaremos tamb�m outros resultados relacionados.

Semin�rios do primeiro semestre de 2005 por renato � �ltima modifica��o 28/05/2007 15:27

 

Semin�rios de TCC - Ano 2004 por renato � �ltima modifica��o 28/05/2007 15:27

S�rie de semin�rios de Teoria da Computa��o e Combinat�ria, mantida pelo Grupo de Combinat�ria e Otimiza��o Combinat�ria do Departamento de Ci�ncia da Computa��o do IME-USP. Sextas-feiras �s 14 horas, na sala 252-A do IME-USP.

Semin�rios dos anos anteriores por cris � �ltima modifica��o 28/05/2007 15:27