Seminários 2011.2


  • A partir de 9/8/2011

    Princípios das Casas de Pombo,
    por Petrucio Viana, UFF.

    Resumo:

    Nesta série de seminários introdutórios vamos apresentar e investigar versões finitas e infinitas do Princípio das Casas de Pombo (PCP), tanto como um método de prova quanto como uma propriedade fundamental dos conjuntos. Em particular, vamos discutir algumas relações do PCP versão infinita com o Axioma da Escolha e o Lemma de König.


  • 30/8/2011

    Probabilidade Finita: propriedades fundamentais,
    por Daniele Costa, PIBIC-UFF.

    Resumo:

    Embora a teoria das probabilidades seja um ramo bem estabelecido e desenvolvido da matemática, o conceito de probabilidade ainda levanta muitas discussões. No centro destas discussões está a questão de qual é a natureza da probabilidade: matemática? lógica? estatística? tendência? psicologia? etc.

    Com a dificuldade de dizer exatamente o que é a probabilidade, vem a dificuldade de selecionar e entender seus conceitos principais. Conceitos como espaço amostral, evento, dependência, condicionalidade, etc., são considerados como centrais em qualquer abordagem para a fundamentação da probabilidade. Por outro lado, em certos contextos específicos, conceitos como, espaços não equiprováveis, variável aleatória, etc., são introduzidos apenas por conveniência.

    Neste trabalho, exemplificamos esta situação mostrando que quando estamos restritos ao cálculo de probabilidades sobre espaços amostrais finitos, as noções de probabilidade como um número real, espaço não equiprovável e axiomatização da probabilidade não são de maneira nenhuma essenciais para o desenvolvimento da teoria. Fazemos isso, provando três resultados, que enunciados de maneira informal, dizem o seguinte:
    1. Para todo espaço de probabilidade finito, existe um espaço de probabilidade cuja função de probabilidade toma valores nos números racionais, que calcula "as mesmas probabilidades" com qualquer aproximação desejada.
    2. Para todo espaço de probabilidade finito, existe um espaço equiprovável no qual "as mesmas probabilidades" são calculadas.
    3. Toda função de probabilidade sobre um espaço finito é definida de maneira única por uma função de distribuição.
    Estes resultados afirmam que, quando lidamos apenas com espaços finitos, (1) probabilidades não precisam ser números reais; (2) espaços não equiprováveis são desnecessários; (3) a axiomatização das probabilidades sobre espaços finitos é completamente trivial.


  • 6/9/2011

    Teorema de Erdös-Szekeres sobre subsequências monotônicas,
    por Renata de Freitas, UFF.

    Resumo:
    Neste seminário apresentamos uma aplicação clássica do Princípio das Casas de Pombo: a prova do Teorema de Erdös-Szekeres sobre subsequências monotônicas.


  • 13/9/2011

    Algumas técnicas de resolução de séries e sequências,
    por Priscilla Mafra, Monitora GAN-UFF.

    Resumo:

    Em algumas disciplinas estudadas nos cursos de graduação em computação ou matemática é usual a apresentação do método de prova por indução matemática para justificar igualdades envolvendo uma soma (de um lado da igualdade) e uma fórmula fechada (do outro lado da igualdade). Porém, na maioria das vezes, não é explicado como a igualdade é obtida, isto é, como se pode, dada uma soma, obter sua fórmula fechada. Uma situação análoga acontece com a obtenção de fórmulas fechadas para relações de recorrência.

    Em nosso trabalho, apresentamos algumas técnicas que podem ser aplicadas na obtenção de fórmulas fechadas para somas e relações de recorrências. Exemplificamos estas técnicas obtendo fórmulas fechadas para algumas das somas que são usualmente abordadas em disciplinas da computação ou da matemática. Estas técnicas, embora bem conhecidas, não são, usualmente, divulgadas para os alunos de graduação. O conhecimento de tais técnicas é importante, pois elas auxiliam enormemente na resolução de problemas aparentemente complicados.

    Apresentamos duas técnicas de dedução de fórmulas para somas: o Truque de Gauss e a Soma Telescópica, que são métodos poderosos de obtenção de fórmulas fechadas. Mostramos também como podemos usar conceitos da álgebra linear, como autovalores e autovetores, para deduzir fórmulas fechadas para relações de recorrência lineares. Em particular, obtemos por este método a "misteriosa" fórmula fechada da Sequência de Fibonacci. Por fim, mostramos outra aplicação da álgebra linear na dedução de identidades relacionadas à sequência de Fibonacci, utilizando potências de matrizes e determinantes, na dedução da famosa Identidade de Cassini. É importante observar que essas técnicas são utilizadas no cálculo da complexidade de determinados algoritmos e que certos métodos utilizados na obtenção destas técnicas possuem aplicação direta em outras partes da Ciência da Computação.


  • A partir de 20/9/2011

    Princípios das Casas de Pombo - continuação,
    por Petrucio Viana, UFF.

    Resumo:

    Nesta série de seminários introdutórios vamos apresentar e investigar versões finitas e infinitas do Princípio das Casas de Pombo (PCP), tanto como um método de prova quanto como uma propriedade fundamental dos conjuntos. Em particular, vamos discutir algumas relações do PCP versão infinita com o Axioma da Escolha e o Lemma de König.