Unidade Curricular:			Código:
Algoritmos e Estruturas de Dados II			1093AED2
Ano:	Nível:	Curso:	Créditos:
2	Licenciatura	Engenharia Informática	6 ects
Período Lectivo:		Língua de Instrução:	Nº Horas:
Segundo Semestre		Português/Inglês	78
Objectivos de Aprendizagem:
Ao completar com sucesso a unidade curricular os alunos devem ser capazes de (learning outcomes - LO): LO1-interpretar a noção de tabelas de símbolos e sua aplicabilidade LO2-explicar a noção de árvores binárias de pesquisa e articular algoritmos associados LO3-aplicar a noção de balanceamento de árvores usando árvores red-black LO4- aplicar e operar tabelas de dispersão, funções de dispersão e suas propriedades LO5-identificar e aplicar a noção de grafo em modelização algorítmica LO6-desenvolver e utilizar grafos dirigidos em diversos problemas algorítmicos LO7-aplicar algoritmos de cálculo da árvore mínima de suporte e suas propriedades LO8- distinguir e aplicar algoritmos de cálculo do caminho mais curto em grafos
Conteúdos Programáticos:
1. Introdução às estruturas de dados não lineares 1.1. Introdução às árvores e grafos 1.2. Notação e terminologia 1.3. Formas de representação 1.4. Aplicações de estruturas de dados não lineares 2. Pesquisa e estruturas de dados em árvore 2.1. Tabelas de símbolos (symbol tables) 2.2. Introdução às estruturas de dados em árvore 2.3. Árvores binárias de pesquisa (BST - binary search trees) 2.4. Árvores balanceadas 2.5. Tabelas de dispersão (hash tables) 3. Grafos 3.1. Introdução à estrutura de dados grafo e sua representação 3.2. Algoritmos de travessia em grafos 3.3. Grafos não dirigidos 3.4. Grafos dirigidos 3.5. Grafos pesados 3.6. Grafos pesados e dirigidos
Demonstração da Coerência dos Conteúdos Programáticos com os Objectivos da Unidade Curricular:
Os conteúdos programáticos apresentados são coerentes com os objectivos de aprendizagem da unidade curricular uma vez que existe uma grande convergência entre os capítulos do programa da cadeira e os conhecimentos que é suposto o aluno adquirir em cada um desses capítulos. Os conceitos fundamentais de análise e desenho algorítmico e estruturas de dados não lineares são apresentados no capítulo introdutório, nos capítulos seguintes são apresentados vários algoritmos e estruturas de dados de pesquisa e de algoritmos de grafos. Os objectivos da aprendizagem são atingidos complementando os conceitos teóricos com exemplos concretos executados em ambiente de laboratório recorrendo a software específico
Metodologias de Ensino (Avaliação Incluída):
Esta Unidade Curricular (UC) é de Projeto. Inclui competências nucleares não passíveis de avaliação em exame. Há elementos de avaliação contínua em cuja média pesada se exige positiva, a Nota Prática de Avaliação Contínua (NPAC) Resultados de avaliação possíveis: a) Aluno atinge objetivos mínimos (NPAC >= 9,5 valores) e Nota Final positiva (NF1 >=9,5 valores) em avaliação contínua. Aprova à UC com a NF1 b) Aluno atinge objetivos mínimos (NPAC >= 9,5 valores) e (NF1 < 9,5 valores). Pode ser avaliado em exame. Avaliação em exame é independente da avaliação contínua. Nota Final da UC é NF2 c) Aluno não atinge objetivos mínimos (NPAC < 9,5 valores). Não tem aprovação à UC e não poderá aceder ao exame Elementos de avaliação previstos: A1. Teste 1 A2. Teste 2 A3. Projeto prático A4. Exame Modelo de Avaliação Contínua: NPAC = A3 NF1 = (A1 + A2 + NPAC)/3, NPAC >= 9,5 Modelo de Avaliação Exame (NPAC >= 9,5): NF2 = A4
Demonstração da Coerência das Metodologias de Ensino com os Objectivos de Aprendizagem da Unidade Curricular:
A metodologia de ensino/aprendizagem aplicada nesta unidade curricular bem como o seu sistema de avaliação encontram-se perfeitamente alinhados com os objectivos a atingir pelos alunos no final do período letivo. Os conceitos teóricos são apresentados, discutidos, aplicados e avaliados no contexto das aulas teóricas o que garante aos alunos uma base sólida de conhecimentos fundamentais para entenderem de forma aprofundada os desafios que se colocam a esta área do conhecimento. Por outro lado, para que o estudo não fique restrito a modelos conceptuais, nas aulas práticas são apresentados casos de estudo concretos e implementadas soluções para problemas reais recorrendo a ferramentas de software apropriadas. Esta combinação garante uma formação aos alunos que lhes permite conhecer os fundamentos científicos essenciais a uma boa compreensão do tema bem como a capacidade de eles se adaptarem a mudanças tecnológicas constantes. O processo de avaliação constituído por testes teóricos e trabalhos práticos garante também um correto equilíbrio entre o esforço dedicado a ambas as componentes. O objectivo é formar profissionais conhecedores das técnicas e ferramentas do estado da arte mas também garantir a sua capacidade de evolução futura. Nesta unidade curricular os conceitos relacionados com a algoritmia e estruturas de dados são apresentados e avaliados na componente teórica. Estes conceitos são depois aplicados na resolução das fichas e trabalhos práticos no contexto das aulas práticas
Bibliografia:
[CLRS] Thomas H. Cormen, Leiserson, C., Rivest, R., & Stein, C. (2009). Introduction to Algorithms, third edition. MIT Press. [KT] Kleinberg, J., & Tardos, E. (2006). Algorithm Design. Pearson Education. [SW] Sedgewick, R., & Wayne, K. (2011). Algorithms, 4th Edition. Pearson Education. [VSC] Vasconcelos, J., & Carvalho, J. V. de. (2005). Algoritmia e Estrutura de Dados: programação nas linguagens C e Java. Editora Centro Atlântico. [AAR2] Rocha, A. A. da. Estruturas de Dados e Algoritmos em Java. FCA - Editora de Informática, ISBN 978-972-722-704-4. [AAR1] Rocha, A. A. da. (2008). Estruturas de Dados e Algoritmos em C. FCA - Editora de Informática