CI1355 / INFO7056

Tópicos em Algoritmos: Funções Geradoras para Ciência da Computação

Primeiro Semestre de 2025

Professor: Renato

Estagiário Docente: Eduardo M. Souza

Horário: terças e quintas-feiras, das 15h30 às 17h10

Sala: PA-01

Lista de e-mails: https://listas.inf.ufpr.br/cgi-bin/mailman/listinfo/ci1355

  1. Ao inscrever-se você receberá mensagem pedindo confirmação. Só após a confirmação você estará efetivamente inscrito.
  2. A lista só aceita mensagens enviadas a partir do endereço com o qual você se inscreveu.
  3. Você pode inscrever mais de um endereço.

Conteúdo da Disciplina

Funções Geradoras ou Séries de Potências podem ser informalmente descritas como "polinômios infinitos". Por exemplo, são funções geradoras

F(x) = 1 + x + x2 + … + xn + …

ou

E(x) = 1 + (x)/(1!) + (x2)/(2!) + … + (xn)/(n!) + …

As propriedades das Funções Geradoras tornam-nas ferramentas poderosas em diversos tópicos da Matemática importantes para a Ciência da Computação.

Nesta disciplina estudaremos seu uso em dois destes tópicos: a resolução de recorrências e a solução de problemas de contagem (que quase sempre podem ser reformulados como problemas de probabilidades).

Veremos que um repertório relativamente pequeno de operações sobre Funções Geradoras é suficiente para solucionar diversos tipos de recorrências bem como questões não triviais de contagem/probabilidades. Em muitos destes casos, a solução dos mesmos problemas sem o uso de Funções Geradoras demanda trabalho consideravelmente maior e/ou mais difícil.

Além disso, veremos que o uso de Funções Geradoras muitas vezes permite um tratamento sistemático destes problemas. Noutras palavras, com o uso de Funções Geradoras, diferentes problemas são resolvidos "do mesmo jeito" enquanto que sem seu auxílio, cada diferente problema parece depender de uma ideia ou técnica particular (ad hoc).

A disciplina não tem pré-requisitos. Alunos que já cursaram "Matemática Discreta" (CI-1237) perceberão que vários dos tópicos estudados ali serão revisitados sob esta nova perspectiva.

As aulas da primeira semana (dias 11 e 13 de março) serão dedicadas a dar uma "visão panorâmica" da disciplina. Potenciais interessados ainda incertos quanto a matricular-se, são bem-vindos.

Caso tenha alguma pergunta, envie e-mail para renato.carmo.rc@gmail.com


Avaliação

Duas provas de pesos iguais


Datas Importantes

8/4: Não haverá aula (avaliação do BCC)

29/4: primeira prova

1/5: Não haverá aula (Feriado: Dia do Trabalho)

5/6: Não haverá aula (Feira de Cursos e Profissões)

19/5: Não haverá aula (Feriado: Corpus Christi)

1/7: Segunda Prova


Material de Apoio

Lista de Exercícios


Bibliografia de Referência

Analytic Combinatorics (Philippe Flajolet, Robert Sedgewick)

Generatingfunctionology (Herbert Wilf)

The Concrete Tetrahedron - Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates (Manuel Kauers, Peter Paule)