Algoritmos e Estruturas de Dados - LEIC

 

T - Teórica; TP - Teórico-prática; PL - Prática Laboratorial; S - Seminário; OT - Orientação Tutorial.

• Objetivos da aprendizagem

  Os estudantes que terminam com sucesso esta unidade curricular serão capazes de:

  (1) Conhecer, compreender e utilizar os algoritmos e as estruturas de dados fundamentais;

  (2) Analisar a correção e o desempenho de algoritmos simples;

  (3) Escolher de forma fundamentada as estruturas de dados mais adequadas a cada problema e aplicá-las às sua resolução;

  (4) Desenhar estruturas de dados ligadas e algoritmos para a sua manipulação.

• Programa

  (I) Algoritmos de ordenação elementares e avançados: insertion sort, selection sort, bubblesort, quicksort, mergesort e heapsort.

  (II) Algoritmos de ordenação em tempo linear.

  (III) Tipos de dados: pilhas, filas de espera, filas de prioridade, amontoados, árvores, conjuntos disjuntos, grafos.

  (IV) Estruturas de dados fundamentais: arrays, listas ligadas, árvores binárias de pesquisa, tabelas de dispersão, listas e matrizes de adjacências.

  (V) Algoritmos fundamentais sobre as diferentes estruturas de dados, como algoritmos de pesquisa e algoritmos de procura em grafos.

  (VI) Técnicas para a análise e o desenho de estruturas de dados e algoritmos.

• Demonstração de coerência entre conteúdos programáticos e resultados da aprendizagem

  A coerência entre os conteúdos programáticos e os objetivos da unidade curricular é a seguinte:

  IV e III fornecem o essencial para atingir o objetivo 3;

  VI cobrem as técnicas de desenho e análise identificadas nos objetivos 2 e 4;

  Apesar de todos os conteúdos contribuírem para o objetivo  1, os mais relevantes são I, II, III, IV e V.

• Metodologia de ensino e avaliação

  Ensino teórico-prático, estando previstas 30 aulas durante o semestre a que correspondem 67,5 horas de contacto (15 aulas de 3 horas e 15 de 1,5 horas).O tempo total de trabalho do estudante é de 160 horas. As aulas destinam-se à apresentação dos temas e de exemplos práticos de aplicação. Os tópicos principais são ainda explorados através da realização de séries de problemas, incluindo a implementação de soluções em Java. Os resultados da aprendizagem de (1) a (4) são avaliados individualmente através de uma componente teórica e uma de componente prática: (Componente teórica) 2 testes parciais ou, em alternativa, exame. O 2º teste realiza-se na época normal de exames. Na época de recurso poderá ser repetido um dos testes parciais ou o exame. (Componente prática) 3 séries de problemas realizadas em grupo e uma discussão final.

• Demonstração de coerência entre metodologias de ensino e resultados de aprendizagem

  A apresentação da teoria é adequada para introduzir os objectivos 1 e 2. Dadas as diferentes áreas em que a utilização de algoritmos e estruturas de dados permite resolver problemas, a realização de séries de problemas ao longo da disciplina é essencial para entender e ganhar experiência, isto é, para alcançar os objectivos 3 e 4.

• Bibliografia principal

  T. Cormen et al., Introduction to Algorithms, 3rd edition, MIT Press 2009.