Unidade Curricular:Código:
Algoritmos e Estruturas de Dados I831AED1
Ano:Nível:Curso:Créditos:
2LicenciaturaEngenharia Informática6 ects
Período Lectivo:Língua de Instrução:Nº Horas:
Primeiro SemestrePortuguês/Inglês78
Objectivos de Aprendizagem:
Competências (Descritores Dublin):
1. Conhecimento e compreensão:
1.1. Noção de algoritmo (ALG): descrição, implementação e análise utilizando diversas notações
1.2. Compreensão de 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 ED lineares e genéricas como arrays e listas ligadas.
2.2. Aplicar ALG em conjunto com ED e tipos abstratos de dados (TAD), como pilhas e filas.
2.3. Utilizar a linguagem de programação C 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. 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):
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_AED1 = (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 letivos 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):
André Ribeiro Pinto (arpinto@ufp.edu.pt)
José Manuel Torres (jtorres@ufp.edu.pt)