Computação II
Objetivos
O objetivo principal deste curso é estudar as técnicas fundamentais para projetar algoritmos eficientes e analisar o tempo de execução. Após uma breve revisão do material pré-requisito (pesquisa, notação assintótica), resolveremos vários problemas através de algoritmos de "divisão e conquista" e algoritmos greedy.
Após a conclusão deste curso, os alunos terão as seguintes capacidades:
- Analise do desempenho assintótico de algoritmos.
- Demonstrar familiaridade com os principais algoritmos e estruturas de dados.
- Aplicar importantes paradigmas de design algorítmico e métodos de análise.
- Sintetizar algoritmos eficientes em situações comuns de design de engenharia
Caracterização geral
Código
100027
Créditos
7.0
Professor responsável
Mauro Castelli
Horas
Semanais - A disponibilizar brevemente
Totais - A disponibilizar brevemente
Idioma de ensino
Português. No caso de existirem alunos de Erasmus, as aulas serão leccionadas em Inglês
Pré-requisitos
- Familiaridade com a programação
- Conhecimento de probabilidade
- Conhecimento básico em matemática discreta
Bibliografia
Cormen, Thomas, Charles Leiserson, et al. Introduction to Algorithms. 3rd ed. MIT Press, 2009. ISBN: 9780262033848
Método de ensino
- Aula teórica onde o professor apresentará os métodos formais necessários para analisar e construir algoritmos eficientes.
- Aulas práticas onde os estudantes terão a oportunidade de testar o desempenho de diferentes algoritmos para resolver um conjunto de tarefas.
Método de avaliação
Primeira época: 70% teste e 30% projeto.
Segunda época: 70% teste e 30% projeto (the same of the first epoch).
Conteúdo
Estratégias básicas de design de algoritmos: design "top-down", dividir e conquistar, critérios de caso médio e caso pior, custos assintóticos.
Relações de recorrência simples para custos assintóticos.
Escolha de estruturas de dados apropriadas: arrays, listas, pilhas, filas, árvores, filas de prioridade, árvores.
Aplicações para pesquisa, ordenar e problemas com árvore.
Introdução a algoritmos discretos de otimização: programação dinâmica, algoritmos "greedy".
Cursos
Cursos onde a unidade curricular é leccionada: