Tópicos de Programação
Verão de 2007


Introdução

Bem vindo à página do Curso de Verão de Tópicos de Programação, edição de 2007. Aqui você encontrará informações a respeito do curso (inclusive de seu andamento) e ponteiros para material de apoio.

Esta página será atualizada com freqüência enquanto o curso estiver em andamento. Você deve visitá-la sempre para verificar as atividades propostas (listas de exercícios, trabalhos práticos etc) ao longo do curso.

Objetivo

O objetivo da disciplina é exibir técnicas não-triviais (com grande ênfase em Matemática) de Análise e Projeto de Algoritmos, incluindo verificação e demonstrações de corretude de Algoritmos, através de problemas clássicos (como buscas ou ordenações).

Na disciplina, diversos conceitos serão introduzidos e as técnicas de escritas de programas serão ilustradas em pseudo-código ou em trechos de programas em Linguagem ANSI C.

Novidades

2007-01-21:
Material para registro de aulas
Coloquei material para registro de nossas aulas em formato LaTeX com o nome scribe.tgz. Tente caprichar no registro das aulas para que todos possam beneficiar-se de seus esforços. Se for o caso, procure trabalhar em conjunto com outros colegas.
Uma ótima referência on-line para usar o LaTeX é o Hypertext Help with LaTeX, que, a propósito, pode ser baixado completamente para seu computador. Ler o conteúdo dos arquivos dados também pode ajudá-lo a entender como usar o modelo.
2007-01-17:
Lista de discussões (mailing list) criada
Leia abaixo as instruções para participar da lista. Ela será nosso meio oficial de comunicação.
2007-01-17:
Segunda Lista atualizada
A Segunda Lista de exercícios tinha enunciado incompleto para o exercício de número 13. A nova versão está com o enunciado corrigido.
2007-01-16:
Segunda Lista disponível
Lista de exercícios para entrega no dia 2007-01-23. Tente fazer todos os exercícios. Alguns são um pouco trabalhosos.
2007-01-08:
Primeira Lista disponível
Lista de exercícios para entrega no dia 2007-01-15. Procure fazer todos os exercícios.
2007-01-02:
Versão inicial da página
Mais novidades serão anunciadas por aqui.

Informações Básicas


Bibliografia

Os seguintes livros/materiais são os mais adequados para nossa disciplina:

Há ainda outras páginas que estão relacionadas ao nosso curso, apesar de não serem, de uma forma geral, parte da bibliografia ou material de estudo.

Histórico das Aulas

Aqui você encontrará um histórico resumido de nossas aulas.

2007-01-03:
Introdução à disciplina: aspectos burocráticos (apresentação, objetivos, bibliografia, critério de avaliação). Uso de alocação dinâmica de memória em Linguagem C. Aplicação 1: forma usual de alocação de memória de um vetor bidimensional; economia de espaço para matrizes simétricas ou matrizes triangulares. Aplicação 2: listas ligadas simples, sem cabeça (motivação), estruturas em linguagem C, funções básicas de manipulação (criação, impressão do conteúdo de uma lista).
2007-01-04:
Listas ligadas (continuação): funções básicas de manipulação (inserção de elementos, remoção de elementos, consulta de elementos, liberação de memória alocada dinamicamente). Estruturas de dados abstratas: dicionário. Aplicação de listas ligadas: pilha.
2007-01-08:
Conceito de algoritmo (cinco propriedades básicas) e breve comentário sobre modelos de computação (lambda-cálculo, modelo proposto por Markov, máquinas de Turing, modelo RAM). Algoritmos recursivos: conceito, exemplo simples (soma dos n primeiros números naturais). Importância de boa documentação de programas (principalmente recursivos). Escrita de um algoritmo recursivo para a soma dos primeiros naturais. Recursividade de cauda e transformação automática em laços por compiladores. Escrita de um programa iterativo para a soma dos primeiros naturais. Comparação com a versão recursiva. Comentários sobre forma alternativa de cálculo (fórmula fechada). Definição da seqüência dos números de Fibonacci. Propriedades elementares da seqüência (função geradora, fórmula de Binet, mdc de dois termos consecutivos etc). Programa recursivo para o n-ésimo número de Fibonacci. Programa iterativo.
2007-01-09:
Um pouco sobre cardinalidade de conjuntos ("diferentes tipos de infinitos" e comentário sobre diagonalização de Cantor). Limitações de modelos computacionais: problemas indecidíveis. Comentários sobre o processo de compilação de código (otimizações como "dead-code elimination" e "out-of-order execution", para melhor uso de pipelines de processadores). Exemplo de problema indecidível: Problema da Parada. Princípio de Indução Finita: enunciado, uso para provar teoremas sobre inteiros, exemplo (prova detalhada da fórmula fechada para a soma dos n primeiros números naturais). Introdução ao Problema das Torres de Hanói: enunciado, restrições, inspeção de casos de pequeno tamanho: 0, 1, 2 e 3. Contagem do número de passos para essas estratégias. Fórmula geral para o número de passos para uma forma de resolver o problema.
2007-01-15:
Motivação para a análise de algoritmos. Critérios usados para a análise de um algoritmo: sua corretude, o consumo de tempo e o consumo de espaço. Críticas à forma de medida de tempo por cronometragem. Medida de tempo de algoritmos através de medida de passos utilizados. Introdução de notação assintótica. Definição de função assintoticamente positiva. Definição de f = O(g) exemplos.
2007-01-16:
Notação assintótica: continuação. Revisão do conceito de O. Intuição sobre o significado da notação assintótica O ("no máximo"). Definição de uma função ser Omega de outra. Intuição ("pelo menos"). Definição de uma função ser Theta de outra. Intuição ("mesmo ritmo de crescimento"). Exemplos e contra-exemplos. Definição alternativa das notação O por meio de limites. Prova (por indução) de que lg n tem crescimento menor do que n.
2007-01-17:
Introdução à Análise de Algoritmos. Motivação para análise de pior caso. Definição do Problema de Busca (em um vetor). Definição de um problema de decisão. Formulação do problema de busca como um problema de decisão. Critério para classificação de eficiência de um algoritmo. Observação sobre medida de entrada: normalmente, em bits. Problemas (computacionalmente) "fáceis". Problemas (computacionalmente) intratáveis. Exemplo de problema de decisão: problema da primalidade. Noção de um certificado para um problema de decisão. Definição da classe P de problemas como a classe dos problemas que podem ser resolvidos em tempo polinomial. Definição da classe NP como problemas que podem ter sua resposta SIM verificada (com auxílio de um certificado) em tempo polinomial. Definição análoga para a classe co-NP. Enunciado do problema P =? NP. Busca seqüencial em um vetor. Estratégias de implementação e decisões de projeto. Resposta interpretada como um certificado para o problema. Implementação iterativa. Análise de Espaço. Análise de Tempo. Implementação com uso de sentinelas. Invariante do algoritmo.
2007-01-18:
Mais definições de notações assintóticas: o ("menos que"), omega ("mais que"), ~ ("igual a"). Intuição por trás dos conceitos. Fórmula de Stirling para n! e sua relação com notação assintótica. Esclarecimento de dúvidas. Prova de corretude da busca seqüencial. Argumentação do número de elementos compreendidos entre dois índices de um vetor. Idéia da busca binária. Exemplo de funcionamento da busca binária. Implementação iterativa. Invariantes da busca binária. Verificação de que os invariantes são válidos no início da execução do algoritmo. Comentários sobre "casos degenerados" da busca binária. Comentários sobre funcionamento da busca binária no caso em que a divisão do vetor não é feita ao meio, mas a uma fração fixada do número de elementos do vetor.

Listas de Exercícios

As listas de exercícios (para você exercitar os conceitos vistos em sala de aula) estão disponíveis abaixo:


Esta página é orgulhosamente escrita em XHTML 1.1 válido. Para sua confecção, apenas Software Livre foi usado. Software livre é muito mais do que apenas software gratuito!