Tópicos Especiais em Programação —  2015/2

Main page

Página principal

Informações

Conteúdo das aulas

13/10


Início da Primeira Parte do curso. Conversa introdutória. O problema de se produzir um histograma dos usuários online ao longo de um período.  
 

15/10


Implementando dois algoritmos para o problema do histograma. Medindo tempos e os relacionando com as complexidades assintóticas.  
 

20/10


Desenhando um cluster de servidores para um jogo online no modelo estrela: cada cliente se conecta diretamente a um membro do cluster (i.e., um servidor). Como sincronizar os relógios de todos?  
 

22/10


Ainda sobre o cluster de servidores para um jogo online:
- Como selecionar o servidor que cada cliente deverá utilizar para enviar e receber dados?
- Como subir novos servidores? - Como tratar rapidamente o problema de servidores defeituosos / down? - Como balancear as cargas? - Como impedir os possíveis "efeitos-gangorra"?  
 

27/10


Descomplicando o backtracking: um esquema limpo. Problema de se enumerar todas as permutações caóticas dos n primeiros naturais.  
 

29/10


Implementação do problema das permutações caóticas. Testes unitários.

Para casa: dado n, t_min e t_max, gerar todos os subconjuntos de {1, 2, ..., n} com tamanho entre t_min e t_max (inclusive).  
 

03/11


Pensando diferentes estratégias de busca exaustiva. Backtracking com podas, e beneficiando-se das simetrias do problema. Algoritmos exponenciais. Algoritmos pseudo-polinomiais.

O problema da balsa.  
 

05/11


Implementação do problema da balsa.  
 

17/11


Fatorial recursivo (ok) e não-recursivo. Fibonacci recursivo (não-ok!!) e não-recursivo.
Memoização.  
 

19/11


Memoização avançada: limitando o tamanho de memos "imprevisíveis".
Quando uma abordagem recursiva pode ser de fato superior à não-recursiva (permitindo memoizar sub-sub-problemas).

O problema da Conjectura de Collatz.  
 

26/11


Raciocínio lógico: pensando o problema ao invés de correr para estruturas.
Arrays de bits/booleanos. Paridade.

O problema dos condenados encapuzados.
O problema dos armários.
O problema dos pontos colineares.  
 

01/12


Solução para o problema dos pontos colineares.
Tabelas hash encadeadas (aka LinkedHashMap). Exemplo de aplicação: cache LRU.  
 

03/12


O problema do prédio e das duas bolas idênticas.
Mais sobre LinkedHashMap. Implementação.  
 

08/12


k-selection. Vários algoritmos. Heap. QuickSelect.  
 

10/12


Como permutar aleatoriamente com uniformidade? Vários métodos ineficientes.
Knuth shuffle.  
 

15/12


Cuckoo hashing.  
 

05/01


Números aleatórios e simulação.
Ex.1: O jogo do trio versus dois pares seguidos.
Ex.2: Probabilidade de A ser igual a C dado que A é diferente de B, para A, B e C variáveis aleatórias independentes e identicamente distribuídas.  
 

07/01


Bloom filters.  
 

12/01


Tópicos em BD relacionais.
Apresentação do aluno Alexandre Ribeiro de Almeida.  
 

14/01


Testes de aceitação e integração.
Apresentação dos alunos Denis Takeo Aoki, Eduardo Felipe Gama Ferreira e Raul Gabrich Moreira de Freitas.  
 

19/01


Tries. Árvores de prefixo.
Apresentação do aluno Joshua Silveira Kritz.  
 

21/01


Design Patterns.
Apresentação dos alunos Gabriel Gonçalves de Castro Marques, Leonardo Alexandre Santos da Silveira Gonçalves e Thales Nathan Caico Matias da Silva.  
 

26/01


Continuous Integration / Continuous Delivery.
Apresentação dos alunos Fausto Ferreira Junqueira e Guilherme Serra Oki.  
 

28/01


Heaps e Priority Queues.
Apresentação dos alunos Herbert Salazar dos Santos, Leandro Carneiro Leite e Wagner Luiz Lobo Ferreira.  
 

02/02


Controle de versão.
Apresentação dos alunos Gabriel Luis Santos Freire, Josiele de Sousa Gonçalves e Julia Anne de Souza Alves.  
 

16/02


NoSQL. MongoDB.
Apresentação dos alunos Allan Monteiro David, Felipe Sepulveda de Faria e Miguel Péres de Castro.  
 

18/02


Unit tests / TDD / BDD / Mock.
Apresentação dos alunos Carlos Sergio de Paiva Araujo, Fellipe Fratini Studart Sombra e Luan Cerqueira Martins.  
 

23/02


Testes A/B.
Apresentação da aluna Letícia Aguiar e Souza.  
 

Voltar ao topo