Está aqui

home / Oferta Formativa - Sinopse /
Voltar ao Topo

Oferta Formativa - Sinopse

Algoritmos e Estruturas de Dados

Imprimir / PDF
Código: 26723
Ano Letivo: 2015/16
Departamento: Informática
ECTS: 6
Carga horária: T: 2:00 h; TP: 1:30 h; OT: 2:00 h;
Área Científica: Informática; 

Objetivos da Unidade Curricular

Introdução aos conceitos fundamentais de algoritmos e técnicas de estruturação de dados no contexto da metodologia de programação centrada em objectos. Aprofundamento do estudo desta metodologia com ênfase nos princípios de abstracção e modularização, assim como nos mecanismos de correcção. Introdução a técnicas algorítmicas mais comuns.

Pré-requisitos

  • Introdução à Programação (26722)

Conteúdos

Complexidade assintótica temporal e espacial. Melhor caso, pior caso e caso esperado.

Dividir para conquistar e recursão. Tail recursion. Técnica de Memorização. Sistemas de recorrência.

Alguns tipos de dados abstratos elementares como a Pilha, Lista, Fila, Fila com Prioridades, Conjunto, Árvore, Mapa e Dicionário e sua especificação formal. Implementação destes tipos de dados com diferentes estruturas de dados como listas e outras estruturas ligadas, vectores, vectores circulares, árvores de pesquisa, amontoados, tabela de dispersão e árvores AVL e análise da sua eficiência.

Ordenação.  

 

Descrição detalhada dos conteúdos programáticos

Componente Teórica

Análise de Algoritmos, Notação O-grande, Tipos de Dados Abstractos, Pilhas, Filas, Iteradores, Recursão, Árvores, Conjuntos e Tabelas, Ordenação, Árvores Equilibradas.

 

Componente Teórica-Prática

Análise de Algoritmos, Notação O-grande, Tipos de Dados Abstractos, Pilhas, Filas, Iteradores, Recursão, Árvores, Conjuntos e Tabelas, Ordenação, Árvores Equilibradas.

 

Componente Prática

Não se aplica.

 

Bibliografia

Recomendada

E. Koffman e P. Wolfgang, "Data Structures: Abstraction and Design Using Java, 2nd edition" , Wiley, ISBN 978-0-470-12870-1, 2011. [Código do livro disponível aqui].

Exemplos, soluções de exercícios e outros recursos podem ser encontrados no "Student Companion site" do livro.

V.Vasconcelos, A.Lopes and I.Nunes, Specifying and Monitoring Java Classes with ConGu 2.0, Lecture Notes, 2014.  

 

Outros elementos de estudo

Séries de exercícios, disponíveis no site da disciplina.

M. T. Goodrich e R. Tamassia, "Data Structures and Algorithms in Java", John Wiley & Sons, ISBN978-0-470-93439-5, 2010.

A. Vermeulen et al., "The Elements of Java Style", Cambridge University Press, ISBN 9780521777681, 2000.
J. Bloch,  "Effective Java, 2nd edition", Addison-Wesley, ISBN 0321356683, 2008

 

Métodos de Ensino

As aulas teóricas consistem na exposição e discussão dos conteúdos do programa. As aulas práticas consistem na exposição e ilustração de temas do programa sobretudo através da resolução de problemas.

 

Métodos de Avaliação

Avaliação contínua (10%) medida pela participação nas aulas TPs e trabalhos de casa Projecto (15%) Exame (75%) Aprovação se  notaExame ≥ 9.5  e   0.10*notaAvC+ 0.15*notaProj + 0.75*notaExame ≥ 9.5

 

Língua de ensino

Português