Objetivos | Esta UC baseia-se no paradigma imperativo da programação de computadores a alunos que já tiveram uma primeira abordagem (imperativa e declarativa) à programação de computadores.
Esta unidade curricular visa introduzir técnicas para o desenho de algoritmos (seguindo estratégias algorítmicas comuns e utilizando estruturas de dados clássicas), e para a análise rigorosa da sua eficiência.
Esta unidade curricular visa ainda introduzir os estudantes às noções de computabilidade e estruturas discretas para modelação de dados, nomeadamente grafos e estruturas ordenadas.
|
Programa | 1. Análise de complexidade de algoritmos: modelo de complexidade assimptótica; estratégias algorítmicas; recorrências; análise de caso médio e amortizada; casos de estudo.
2. Algoritmos e computabilidade. Autómatos e máquinas de Turing; Recursividade e função computável; tese de ChurchTuring; Indecibilidade; completude NP
3. Estruturas discretas, algoritmos base associados e sua utilização na representação de dados e conhecimento: árvores AVL, tabelas de dispersão, "heaps". Implementação eficiente de "buffers" e dicionários.
4. Algoritmos fundamentais sobre grafos; estratégia algorítmica "greedy" e programação dinâmica.
5. Introdução às classes de problemas P, NP, e NP-completo.
|
Bibliografia | Kernigham, B.W., Ritchie, D.M. (1988) The C programming language. 2nd edition. Prentice Hall Software Series.
Lewis, H., Papadimitriou, C. (1998) Elements of the Theory of Computation, Prentice-Hall.
Jenkins, T., Stephenson, B. (2013) Fundamentals of Discrete Math for Computer Science. Springer.
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C. (2009) Introduction to Algorithms, third Edition. MIT Press.
Sedgewick, R. (2001) Algorithms in C, part 5: Graph Algorithms, third edition. Addison-Wesley.
|
Resultados da aprendizagem | 1. Dividir um problema em subproblemas mais simples.
2. Definir tipos de dados para a representação dos dados e resultados de um dado problema.
3. Analisar e desenvolver algoritmos manipulando diversos tipos de estruturas discretas, nomeadamente, ordens, árvores e grafos.
4. Determinar a complexidade assimptótica de um algoritmo iterativo ou recursivo.
5. Pressupões reconhecer e utilizar estratégias algorítmicas fundamentais.
6. Aplicar a noção de computabilidade (máquina de Turing, função computável) e problemas associados.
7. Resolver problemas NP-completos e alguns algoritmos aproximados para a sua resolução.
|
Departamento de Informática (UM)