Unidade Curricular:			Código:
Algoritmos e Estruturas de Dados II			831AED2
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:
Competências (Descritores Dublin): 1. Conhecimento e compreensão: 1.1. Noção de algoritmos (ALG) e estruturas de dados (ED) de pesquisa e de grafos 1.2. Compreensão desses ALG e estruturas de dados (ED) em projetos de software e na resolução de problemas concretos 2. Aplicação de conhecimento e compreensão: 2.1. Aplicar ALG e ED de pesquisa e de grafos 2.2. Utilizar a linguagem de programação Java na implementação de ALG e ED. 3. Avaliação/tomada de decisões: 3.1. Escolha das ED e ALG adequados para a resolução de problemas e/ou projetos de software. 4. Comunicação: 4.1. Descrever um ALG dominando representações abstratas de algoritmos. 4.2. Trabalhar em grupo. 4.3. Argumentar oralmente e por escrito. 5. Autonomia e aprendizagem: 5.1. Conhecer e aprofundar outras técnicas algorítmicas existentes. 5.2. Autonomia para ultrapassar dificuldades inerentes a novos problemas
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):
Componente teórico-prática (TP) e prático-laboratorial (PL). Nas aulas TP os conceitos são apresentados intercalados com exemplos e exercícios. Nas aulas PL são colocados e resolvidos exercícios e problemas, eventualmente recorrendo a software apropriado. Nota_Final_AED2 = (2/3) x Nota_TP + (1/3) x Nota_PL Obrigatório: Nota_TP >= 10 Nota_PL >= 10 Nota_PL: obrigatoriamente por avaliação contínua e não é sujeita a exame. Consiste num projeto de programação realizado durante o semestre. Caso o aluno não submeta o projeto terá zero valores e apenas poderá realizar o projeto numa edição subsequente da UC. Nota_PL = Nota do projeto prático Nota_TP: Em avaliação contínua, duas frequências F1 e F2, Nota_TP = (50%) x F1 + (50%) x F2 Em exame, Nota_TP = Nota_Exame_TP Se apenas uma componente TP ou PL for positiva fica válida durante um prazo máximo de dois anos lectivos após o ano em que o aluno obteve aprovação nessa componente. Durante esse período a UC está não concluída (NC)
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