Algoritmos

TeSP - Tecnologia e Programação em Sistemas de Informação
2 ECTS; 2º Ano, 1º Semestre, 37,50 TP

Docente(s)
- Maria Manuela Morgado Fernandes Oliveira

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; 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) e um projecto intercalar. O projecto é um trabalho computacional e vale 20 valores. A prova é cotada de 0 a 20 valores. A nota final será dada pela média aritmética da nota da prova e do projecto.
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
- Rosen, K. (2012). Discrete Mathematics and its Applications. (pp. 641-803). New York: McGraw-Hill
- Aho, Hopcroft, Ullman, A. (1974). The Design and Analysis of Computer Algorithms. (pp. 1-470). Massachusetts: Addison-Wesley
- Wirth, N. (1976). Algorithms + Data Structures = Programs. (pp. 1-212). New Jersey: Prentice-Hall
- Fernandes, M. (0). Apontamentos da disciplina. Acedido em 12 de setembro de 2018 em www.e-learning.ipt.pt

Método de interação
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
Octave em ambiente Windows ou outro à escolha do aluno.