Faculdade de Engenharia da Universidade do Porto
Plano
Semana Datas Assunto das Teóricas Aulas Práticas 1 21 (2ª) a 25 (6ª) Fev. Apresentação da ficha da disciplina. Introdução à programação estruturada em C++;
entrada e saída de dados; instruções de controlo do fluxo do programa - 2 28 a 3 de Março Tipos de dados básicos; operadores e expressões.
Funções; funções inline, argumentos por referência; argumentos por omisão; sobrecarga de funções; padrões (templates) de
funções. CR4 3 8 (4ª) a 14 (3ª) de Março Arrays e apontadores.
Alocação e libertação de memória dinâmica com new e delete. AG 4 15 a 21 de Março Algoritmos de pesquisa e ordenação de arrays: pesquisa sequencial, pesquisa binária,
ordenação por inserção; ordenação por partição.
Análise de algoritmos: noção de complexidade temporal e espacial; notação de O grande; aplicação aos algoritmos de pesquisa e
ordenação de arrays. CR4 5 22 a 28 de Março Introdução à programação orientada aos objectos em C++; conceito de classe e conceito de
objecto; membros-função de classes; restrições de acesso; construtores e destrutores; objectos e membros constantes;
membros-iniciador; composição de classes; classes e funções friend; apontador this; AG, 1º Mini-teste 6 29 a 4 de Abril Criação e destruição de objectos com new e delete; membros estáticos; padrões de classes.
tipos de dados abstractos; exemplo da stack; classes base e classes derivadas; herança; funções virtuais e polimorfismo;
tratamento de excepções. CR4 7 5 a 11 de Abril Listas Lineares: o tipo de dados abstracto; representação em array; representação ligada em
cadeia; listas circulares e listas duplamente ligadas; representação ligada em cadeia; implementação em C++. AG 8 12 a 18 de Abril Pilhas: tipo de dados abstracto; implementação baseada em array; implementação baseada
em cadeia; exemplo de aplicação.
Filas: tipo de dados abstracto; implementação baseada em array; implementação baseada em cadeia; exemplo de
aplicação. CR4, 2º Mini-teste 9 19 (4ª) e 2 (3ª) a 5 de Maio Árvores: definições; árvores binárias; representação de árvores baseada em fórmula;
representação ligada; percorrer a árvore em profundidade (pré-order, em-ordem e pós-ordem) e em largura.
Tipo de dados abstracto BinaryTree; classe C++ BinaryTree para implementar uma árvore binária; percorrer a árvore em
profundidade e em largura; exemplo de aplicação. AG 10 15 (2ª) a 19 (6ª) de Maio Árvores de procura de m-vias. Aplicações. Referência a B-trees. CR4 11 22 a 26 de Maio Heaps e filas de prioridades.
Hashing; dicionários, tabelas de dispersão ("hash"), implementação em C++ da classe HashTable; aplicação à compressão de
ficheiros segundo o algoritmo LZW. AG 12 29 a 2 Junho Grafos: definições, propriedades,
representações, algorimtos ("spanning trees", pesquisa em
largura e em profundidade), implementação em C++, aplicações. CR4 13 5 a 9 Junho Exercícios. AG
Licenciatura em Engenharia Electrotécnica e de Computadores
Algoritmos e Estruturas de Dados, 1999/2000
[Página da disciplina]
[J. Lopes Home page]
João Correia Lopes
(jlopes AT fe.up.pt).
Last modified: Mon Feb 21 10:15:39 2000