Unidade Curricular:Código:
Algoritmos e Estruturas de Dados II831AED2
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:
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
Docente (* Responsável):
Ana Ribeiro Gomes (argomes@ufp.edu.pt)
André Ribeiro Pinto (arpinto@ufp.edu.pt)
José Manuel Torres (jtorres@ufp.edu.pt)