Guia de Cursos

Queres conhecer a oferta de cursos da NOVA, nas áreas das licenciaturas, mestrados e doutoramentos?
No nosso Guia de Cursos encontras informação útil sobre Faculdades, Institutos e Escolas.
Podes ainda aceder a informações complementares necessárias a uma completa integração.

saber mais Guia de Cursos

Faculdade de Ciências e Tecnologia

Análise e Desenho de Algoritmos

Código

8154

Unidade Orgânica

Faculdade de Ciências e Tecnologia

Departamento

Departamento de Informática

Créditos

6.0

Professor responsável

Luís Manuel Marques da Costa Caires, Margarida Paula Neves Mamede

Horas semanais

5

Total de horas

67

Língua de ensino

Português

Objectivos

Saber

Definir e identificar três técnicas de desenho de algoritmos: estratégias greedy, programação dinâmica e transformação-e-conquista.

Conhecer os algoritmos fundamentais de grafos, os tipos abstratos de dados envolvidos e as estruturas de dados usadas para os implementar com eficiência.

Compreender complexidade amortizada.

Definir algumas classes de complexidade e compreender alguns problemas em aberto.

Saber Fazer

Conceber e analisar um algoritmo aplicando programação dinâmica.

Formalizar um problema concreto em termos de grafos e adaptar um algoritmo clássico para o resolver.

Escolher, comparar, adaptar e utilizar estruturas de dados adequadas ao problema a resolver.

Calcular a complexidade de algoritmos com base na complexidade amortizada das funções auxiliares e calcular a complexidade amortizada dessas funções.

Avaliar soluções e efetuar escolhas fundamentadas.

Provar que um problema é NP-completo.

Pré-requisitos

Os alunos devem:

(a) ter destreza em programação orientada por objetos;

(b) estar familiarizados com as estruturas de dados fundamentais (listas ligadas, tabelas de dispersão, árvores binárias de pesquisa, heaps binários);

(c) saber calcular as complexidades temporal e espacial de algoritmos.

Conteúdo

(1) Programação dinâmica.

(2) Introdução ao estudo de grafos. Definições fundamentais. Tipos abstratos de dados grafo não orientado e grafo orientado. Implementações de grafos.

(3) Algoritmos elementares de grafos. Percursos em profundidade e em largura. Ordenação topológica.

(4) Árvores mínimas de cobertura. Algoritmo de Kruskal. Tipo abstrato de dados partição.

(5) Complexidade amortizada. Método do potencial.

(6) Algoritmo de Prim. Tipo abstrato de dados fila com prioridade adaptável.

(7) Caminhos mais curtos. Algoritmos de Dijkstra, Bellman-Ford e Floyd-Warshall.

(8) Redes de fluxos. Fluxos máximos. Método de Ford-Fulkerson. Algoritmo de Edmonds-Karp. Emparelhamentos máximos em grafos bipartidos. Cortes mínimos.

(9) Introdução à Teoria da Complexidade. As classes P, NP, PSPACE e EXPTIME. Os sufixos difícil e completo. Redução de problemas. Alguns problemas em aberto.

Bibliografia

Referências Principais

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (3rd edition). The MIT Press, 2009.

Jon Kleinberg and Éva Tardos. Algorithm Design. Addison-Wesley, 2005.

Referências Complementares

Anany Levitin. Introduction to The Design and Analysis of Algorithms (3rd edition). Addison-Wesley, 2011

Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979.

Steven S. Skiena. The Algorithm Design Manual (2nd edition). Springer, 2008.

Steven S. Skiena and Miguel A. Revilla. Programming Challenges: The Programming Contest Training Manual. Springer, 2003.

Método de ensino

O ensino consiste na exposição da matéria em aulas teóricas e na resolução de problemas em aulas práticas de laboratório. No laboratório, os alunos desenham, analisam e implementam algoritmos.

Método de avaliação

Componentes da Avaliação

A avaliação é constituída por duas componentes: a componente laboratorial e a componente teórico-prática.

Componente Laboratorial e Frequência

A componente laboratorial é composta por três trabalhos. Cada trabalho consiste no desenho, na análise e na implementação de um algoritmo para resolver um problema de um concurso de programação, na elaboração de um relatório e na realização de uma discussão. As duas primeiras partes do trabalho (programa e relatório) são realizadas em grupo de dois alunos; a discussão é individual.

Um grupo entrega um trabalho se o seu programa for aceite pelo Mooshak e o respetivo relatório (em papel) for entregue na Secretaria do DI dentro do prazo. As notas dos trabalhos entregues variam entre 10 e 20 valores.

As discussões (para aferir o conhecimento que cada aluno tem sobre os trabalhos que entregou) são obrigatórias e individuais. A nota de um aluno num trabalho depende do trabalho que entregou (realizado em grupo), do seu desempenho na discussão e do desempenho do seu colega de grupo na discussão, caso os desempenhos de ambos sejam significativamente desequilibrados. Consequentemente, as notas dos dois elementos do grupo podem ser diferentes (e variam entre 0 e a nota do trabalho).

A nota da componente laboratorial (CompL) é a média das notas do aluno nos três trabalhos (P1, P2 e P3):

CompL = (P1 + P2 + P3) / 3.

Para obter frequência, é necessário que CompL >= 7.0 .

As discussões dos trabalhos serão efetuadas no fim do semestre, apenas com os alunos que puderem ter frequência.

Componente Teórico-Prática

A componente teórico-prática é composta por dois testes (no período de aulas) ou por um exame (na Época de Recurso). As três provas são individuais, escritas e com consulta. Cada aluno pode consultar todo o material que quiser, desde que esteja em papel e o tenha levado para a prova. Não são permitidos dispositivos eletrónicos (e.g. calculadoras, telemóveis, smartwatches e portáteis).

Há pré-inscrição nos testes e no exame.

A nota da componente teórico-prática (CompTP) é a média pesada das notas dos testes (T1 e T2) ou a nota do exame (Ex):

CompTP = 0.4 T1 + 0.6 T2   ou   CompTP = Ex.

Para obter aprovação, é necessário que CompTP >= 9.5 .

Nota Final

A nota final (F) dos alunos com frequência é:

  • F = CompTP,   se CompTP < 9.5;
  • F = 0.4 CompL + 0.6 CompTP,   se CompTP >= 9.5 .

Todas as notas (P1, P2, P3, T1, T2, Ex, CompL e CompTP) são arredondadas às décimas, exceto a nota final (F) que é arredondada às unidades.

Frequência e Classificações Obtidas em Anos Anteriores

Os alunos que obtiveram frequência em 2015/16 ou 2016/17 têm automaticamente frequência. No cálculo da nota final, a nota da componente laboratorial é o máximo entre as notas (da componente laboratorial) obtidas em 2015/16, em 2016/17 e este ano.

Os alunos que obtiveram pelo menos 9.5 na componente teórico-prática em 2016/17 estão dispensados de realizar os testes e o exame. No cálculo da nota final, a nota da componente teórico-prática é o máximo entre as notas (da componente teórico-prática) obtidas o ano passado e este ano.

Cursos