Publicação em Diário da República: Despacho n.º 6191/2020 - 09/06/2020
2 ECTS; 1º Ano, Anual, 34,0 TP , Cód. 602430.
Docente(s)
- Maria Manuela Morgado Fernandes Oliveira (1)
(1) Docente Responsável
(2) Docente que lecciona
Pré-requisitos
Não aplicável
Objetivos
Conhecimento e domínio sobre aspectos introdutórios das ciências da computação, nomeadamente armazenamento de dados, estruturas de dados e estruturas de controle, funções, mas também do conhecimento de algoritmos nas áreas de Ordenação e Pesquisa, Grafos e Digrafos. Percepção das aplicações, já existentes, de algoritmos clássicos essenciais no desenvolvimento de software para as mais diversas áreas.
Programa
Aspectos introdutórios: Breve introdução ao Octave em ambiente Windows, desenvolvimento em Python; dados, estruturas de dados e estruturas de controle; vectores e matrizes; funções recursivas e não recursivas. Algoritmos de ordenação e de pesquisa: Bubblesort, ordenação por seleção, ordenação por inserção, Shellsort, Mergesort e Quicksort. Pesquisa linear e pesquisa binária. Algoritmos sobre Grafos: definição e propriedades fundamentais dos grafos; estruturas de dados para representação, armazenagem e manipulação de grafos; construção de caminhos e ciclos em grafos; grafos conexos; árvores; extensão aos digrafos e a redes. Aplicações: algoritmo DFS para a construção de uma árvore geradora de um grafo conexo; algoritmo para a construção de um ciclo euleriano; o problema da determinação de uma árvore geradora de custo mínimo: algoritmos de Kruskal e de Prim; o problema da determinação de um caminho de custo mínimo numa rede: algoritmos de Dijkstra e de Floyd-Marshall; Problema do fluxo máximo numa rede: algoritmo de Ford-Fulkerson. Extensões: noções básicas sobre heurísticas; aplicação ao problema do caixeiro-viajante.
Metodologia de avaliação
Avaliação Contínua: Realização de uma prova (escrita e computacional) , realização de trabalhos em sala de aula e um projecto intercalar. O projecto é um trabalho computacional e vale 20 valores. A prova é cotada de 0 a 20 valores. Os trabalhos estão cotados de 0 a 20 valores. A nota final será dada pela média ponderada dos três itens anteriores, 50% para a prova escrita, 30% para o projeto final e 20% para os trabalhos em sala de aula.
Avaliação por Exame: Os alunos admitidos a exame ou os aprovados que pretendam melhorar a sua nota, podem fazer um exame em época normal. Esse exame divide-se em duas vertentes: escrita e computacional e abrange toda a matéria leccionada. Os alunos que reprovarem na época normal ou que pretendem melhorar nota podem ainda submeter-se a um exame de recurso, nos moldes descritos. As notas dos trabalhos poderão ou não transitar para exame, conforme escolha do aluno. Dando-se ainda a hipótese de melhorar, uma única vez, os trabalhos até à data do exame, mantendo a nota da prova.
Bibliografia
- Aho, Hopcroft, Ullman, A. (1974). The Design and Analysis of Computer Algorithms. (pp. 1-470). Massachusetts: Addison-Wesley
- Fernandes, M. (0). Apontamentos da disciplina. Acedido em 12 de setembro de 2018 em www.e-learning.ipt.pt
- Rosen, K. (2012). Discrete Mathematics and its Applications. (pp. 641-803). New York: McGraw-Hill
- Wirth, N. (1976). Algorithms + Data Structures = Programs. (pp. 1-212). New Jersey: Prentice-Hall
Método de Ensino
As aulas decorrem predominantemente em ambiente computacional. Propõe-se o reconhecimento da aplicabilidade de alguns algoritmos clássicos, a sua compreensão teórica e procede-se à sua implementação.
Software utilizado nas aulas
Desenvolvimento em Python, Octave em ambiente Windows.
