Unidade Curricular:			Código:
Algoritmos e Estruturas de Dados I			1093AED1
Ano:	Nível:	Curso:	Créditos:
2	Licenciatura	Engenharia Informática	6 ects
Período Lectivo:		Língua de Instrução:	Nº Horas:
Primeiro 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-entender e utilizar as principais estruturas de dados usadas em algoritmos LO2-explicar e analisar complexidade algorítmica LO3-explicar a importância do desenho de algoritmos e o seu impacto no desempenho LO4-aplicar princípios de eficiência algorítmica em casos particulares LO5-aplicar técnicas de pesquisa de informação em strings como KMP LO6-identificar e utilizar métodos de ordenação elementares LO7-identificar e utilizar métodos de ordenação como merge sort e quick sort LO8-identificar e utilizar tipos abstratos de dados como pilhas, filas e filas prioritárias
Conteúdos Programáticos:
1. Fundamentos de Algoritmos e Estruturas de Dados 1.1. Modelos de representação e programação de algoritmos 1.2. Introdução às estruturas de dados lineares e não lineares 1.3. Análise da complexidade algorítmica 1.4. Introdução às técnicas de desenho algorítmico 1.5. Aplicações e casos de estudo 2. Algoritmos de tratamento de texto (Strings) 2.1. Introdução às operações com cadeias de caracteres2.2. Operações de ordenação2.3. Operações de pesquisa3. Estruturas de Dados Elementares3.1. Tipos de dados e abstração (ADT – Abstract Data Types)3.2. Vetores 3.3. Listas ligadas 3.4. Pilhas 3.5. Filas 4. Ordenação 4.1. Introdução ao problema de ordenação 4.2. Métodos elementares de ordenação 4.3. Merge Sort 4.4. QuickSort 4.5. Amontoados, filas prioritárias e Heap Sort
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 são apresentados no capítulo introdutório, nos capítulos seguintes são apresentados vários algoritmos de ordenação e pesquisa e de estruturas de dados lineares e strings. Os objetivos da aprendizagem são atingidos complementando os conceitos teóricos com exemplos e exercícios concretos executados em ambiente de laboratório recorrendo a software apropriado
Metodologias de Ensino (Avaliação Incluída):
Esta Unidade Curricular (UC) é classificada como de Projeto e contém competências nucleares que não sã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: 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: 1. Teste 1 2. Teste 2 3. Projeto prático 4. Exame Modelo de Avaliação Contínua: NPAC = (3) NF1 = ((1) + (2) + NPAC)/3, NPAC >= 9,5 Modelo de Avaliação Exame (NPAC >= 9,5): NF2 = (4)
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):
Célio Carvalho (celio@ufp.edu.pt) José Manuel Torres (jtorres@ufp.edu.pt)