Problemas (2018/1)

alias Project Euler

Para os cursos de graduação em Matemática Aplicada e Engenharias.

Motivação

Programar é uma atividade que envolve comunicar um propósito (realizar alguma tarefa) ao ser mais burro do mundo: um computador. Mas nem sempre basta dar (todas!) as instruções - às vezes, dado o tamanho da tarefa, é preciso se preocupar com o tempo que esta vai tomar.

Este curso almeja combinar o aprendizado de uma linguagem de programação com a preocupação constante de escrever um programa eficiente. Os problemas do Project Euler estão organizados em dificuldade progressiva, o que permite ir aprofundando o conhecimento de programação sem, entretanto, perder de vista o objetivo de escrever programas rápidos. E a definição de "rápido" será relativamente clara: que o programa rode em menos de 1 minuto, a "regra de honra" do Project Euler.

Indicações práticas

Mesmo que, oficialmente, não haja pré-requisitos, vale a pena já ter feito alguma programação antes. Não necessariamente em um curso, é claro. O mais importante é ter motivação para resolver os problemas todas as semanas!

E que linguagem eu uso? Bom, a minha resposta (conforme acima) é sempre "a que você quer aprender", pois é assim que o Project Euler funciona melhor. Mas o que fazer em caso de dúvida? Se alguns amigos sugerem uma, outros sugerem outra, você ouviu falar de mais três... sugiro que você me mande um email. Se você não tem nenhuma sugestão de linguagem (!!!) e faz graduação em "exatas", você pode usar o Jupyter notebook.

Estrutura do curso

Aulas práticas, 2 vezes por semana, em horário a determinar de acordo com a sondagem.

Ementa subliminar

Ao longo de uma seleção dos 100 primeiros problemas do Project Euler, vamos ter oportunidade de falar de:

  • algoritmos (ordenação, busca, ...),
  • estruturas de dados (arrays, listas, conjuntos, ...), e
  • técnicas de programação (como testar se o seu programa roda rápido o suficiente, como escrever uma função que você possa reutilizar em problemas seguintes, ...)
Os projetos de final de curso serão voltados para a análise de alguns jogos combinatórios, tanto do ponto de vista de sua solução, como da construção algorítmica de posições iniciais.
  • 2018/1
    • Terças e Quintas, das 15h às 17h, LIG-IM2 (CT).
    • Semanas 1-2: Algoritmos, O(), medindo velocidade
    • Aula 1: Introdução, Euler 1
    • Aula 2: Euler 1, O(), árvore de MMC
    • Para dia 27 de Março: árvore
    • Aula 3: Estimando complexidade com clock(), Euler 8
    • Aula 4: Gráficos de complexidade, Euler 8
    • Para dia 03 de Abril: gerador e analisador P8
    • Semanas 3-6: Estruturas de dados para acelerar algoritmos
    • Aula 5: Euler 14: arrays
    • Aula 6: Euler 14: árvores e percurso em largura
    • Aula 7: Euler 14: representação de árvores
    • Aula 8: Euler 18: arrays e programação dinâmica
    • Aula 9: Euler 24: contagem
    • Para dia 17 de Abril: Pirâmide P18, P24 com lista
    • Aula 10: Euler 31: Recorrência e programação dinâmica
    • Aula 11: Euler 31: Complexidade
    • Aula 12: Euler 31: Soluções multi-recursivas
    • Para dia 26 de Abril: Comparação de complexidade das soluções P31: recursiva, rec2, prog dinâmica.
    • Aula 13: Euler 81: Andando nas diagonais de uma matriz
    • Aula 14: Euler 82: Uma recorrência mais difícil para PD
    • Para dia 2 de Maio: 81 e 82.
    • Semanas 7-10: Algoritmos e jogos
    • Semanas 11-15: Projeto
  • 2015/1
    • Tabela de problemas, parâmetros e tempos (em construção)
    • Planejamento do curso
    • Semana 1: Medindo a performance dos seus programas.
      Comparativo do problema 1 (em inglês)
      Em sala: 1, 4; em casa: 2, 3, 5
    • Semana 2: Números primos
      Em sala: 7, 9; em casa: 10, 12
    • Semana 3: Força bruta
      Em sala: 6, 8, 91; em casa: 11, 21
    • Semana 4: Programaçao dinâmica
      Em sala: 14, 15; em casa: 18, 21
      Alguns números para o problema 15 generalizado (k = 3 passos para a direita consecutivos no máximo):
    • Semana 5: Recorrência
      Em sala: 24; em casa: 25
    • Semana 6: Força bruta II
      Em sala: 23, 27, 28, 30; em casa: 29, 31
    • Semana 7: Recorrência II: Geradores e continuações
      Em sala: 32, 34; em casa: 35
    • Semana 8: Teoria dos Números
      Em sala: 26, 33, em casa: 37, 44
    • Semana 9: Teoria dos Números II
      Em sala: 41, 45, 48 em casa: 51
    • Semana 10: Geradores e BruteForce
      Em sala: 61, 68
    • Semana 11: Frações contínuas, Pell bis
      Em sala: 64, 65, 66
    • Semana 12: Revisao de geradores
      Em sala: 78, 98
    • Semana 13: Finish
      Em sala: 94, 88
    • Semana 14: Projeto
    • Semana 15: Projeto
    • Semana 16: Projeto, relatório até dia 15 de julho
    • Semana 17: Apresentaçoes dos projetos dia 15 de julho
    • Semana 18: Apresentaçoes dos projetos dias 20 e 22 de julho
UFRJ Departamento de Matemática Aplicada - Instituto de Matemática - UFRJ
Valid XHTML 1.1 Valid CSS! Desenvolvido por: Bernardo Freitas Paulo da Costa Inspirado do padrão: TIC/UFRJ