Unidade Curricular:Código:
Algoritmos e Estruturas de Dados II1093AED2
Ano:Nível:Curso:Créditos:
2LicenciaturaEngenharia Informática6 ects
Período Lectivo:Língua de Instrução:Nº Horas:
Segundo SemestrePortuguês/Inglês78
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