Computação II

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

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: