Computação II
Código
100027
Unidade Orgânica
NOVA Information Management School
Créditos
7.0
Professor responsável
Mauro Castelli
Língua de ensino
Português. No caso de existirem alunos de Erasmus, as aulas serão leccionadas em Inglês
Objectivos
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
Pré-requisitos
- Familiaridade com a programação
- Conhecimento de probabilidade
- Conhecimento básico em matemática discreta
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".
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: 100% exame