|
Lição nº 1 13/09/2005 |
|
|
Apresentação. Bibliografia. Avaliação. |
| |
|
|
Lição nº 2 16/09/2005 |
|
|
Capítulo 0: Introdução * Metodologia da programação: as várias etapas do desenvolvimento de algoritmos e escrita dos respectivos códigos. Programação descendente. * Resolução dos exercícios indicados na primeira aula prática. * Revisões sobre os tipos de dados em Pascal: simples e estruturados
Capítulo 1: Tipo estruturado de dados "file" * Semelhanças e diferenças com o tipo estruturado de dados "array". * Diagrama de sintaxe. * Definição do tipo e declaração de variáveis: exemplos. |
| |
|
|
Lição nº 3 20/09/2005 |
|
|
Capítulo 1: Tipo estruturado de dados "file" * Variável "buffer" associada a um ficheiro. Modo de utilização. * Funções que actuam sobre ficheiros genéricos. * Caso particular: "text" = ficheiros do caracteres. Instruções de leitura e escrita neste caso. Função "eoln". * Fichiros pré-declarados: input, output. * Considerações finais.
|
| |
|
|
Lição nº 4 23/09/2005 |
|
|
Capítulo 2: Estudo da ordem de complexidade. * Objectivos. * Critérios avaliados: temporal e espaço de memória utilizado. * ordem de complexidade temporal: contagem do número de operações elementares. * Tipos de estudos mais frequentes: melhor/pior caso, caso médio e caso empírico. * Exemplos.
|
| |
|
|
Lição nº 5 27/09/2005 |
|
|
Capítulo 2: Estudo da ordem de complexidade. * Algoritmos de pesquisa de um elemento num vector desordenado e estudo da ordem de complexidade. |
| |
|
|
Lição nº 6 30/09/2005 |
|
|
Capítulo 2: Estudo da ordem de complexidade. * Algoritmos de pesquisa de um elemento num vector ordenado (alg. pesquisa binária) e estudo da ordem de complexidade. * Estudo geral da ordem de complexidade no caso médio: notação. * Determinação da ordem de complexidade no caso médio nos algoritmos de pesquisa estudados.
|
| |
|
|
Lição nº 7 04/10/2005 |
|
|
Capítulo 2: Estudo da ordem de complexidade. * continuação da última aula. * Soma dos n primeiros termos de uma série: casos particulares e respectivas fórmulas.
|
| |
|
|
Lição nº 8 07/10/2005 |
|
|
Capítulo 2: Estudo da ordem de complexidade. * Ordem de complexidade assintótica. Notação.
Capítulo 3: Algoritmos de ordenação de vectores iterativos. * Breve resumos e exemplificação dos algoritmos que serão estudados (iterativos/recursivos).
|
| |
|
|
Lição nº 9 11/10/2005 |
|
|
Capítulo 3: Algoritmos de ordenação de vectores iterativos. * algoritmos para inserir um elemento num vector ordenado. * estudo da ordem de complexidade (em termos de comparações e trocas efectuadas). |
| |
|
|
Lição nº 10 14/10/2005 |
|
|
Capítulo 3: Algoritmos de ordenação de vectores iterativos. * algoritmos para remover um elemento (ou elementos repetidos) num vector ordenado. * estudo da ordem de complexidade (em termos de comparações e trocas efectuadas). |
| |
|
|
Lição nº 11 18/10/2005 |
|
|
Capítulo 3: Algoritmos de ordenação de vectores iterativos. * continuação da última aula. Realização do 1o mini-teste teórico.
|
| |
|
|
Lição nº 12 21/10/2005 |
|
|
Capítulo 3: Algoritmos de ordenação de vectores iterativos. * continuação da última aula. * Algoritmo de ordenação: borbulhagem (bubble sort). Descrição e exemplo. * Estudo da ordem de complexidade no caso melhor/pior/médio relativamente ao número de comparações e trocas efectuadas.
|
| |
|
|
Lição nº 13 28/10/2005 |
|
|
Capítulo 3: Algoritmos de ordenação de vectores iterativos. * Algoritmo de ordenação: inserção sequencial. Descrição e exemplo. * Estudo da ordem de complexidade no caso melhor/pior/médio relativamente ao número de comparações e trocas efectuadas. * Algoritmo de ordenação: selecção linear. Descrição e exemplo. * Estudo da ordem de complexidade no caso melhor/pior/médio relativamente ao número de comparações e trocas efectuadas.
Capítulo 4: Introdução aos algoritmos recursivos * Definição de recursividade. * Apresentação de alguns exemplos: factorial, sucessão de Fibonnaci. * Comparação da eficiência entre a versão iterativa e recursiva. |
| |
|
|
Lição nº 14 04/11/2005 |
|
|
Capítulo 4: Introdução aos algoritmos recursivos * Outros exemplos de recursão: cálculo do mdc(a,b), inverter uma palavra, inverter um número. * Comparação da eficiência entre a versão iterativa e recursiva. * Problema das torres de Hanoi. |
| |
|
|
Lição nº 15 08/11/2005 |
|
|
Capítulo 4: Introdução aos algoritmos recursivos * Método "tentativa e erro", pesquisa exaustiva, "back-tracking" * Problema da colocação de 8 rainhas num tabuleiro de xadrez. |
| |
|
|
Lição nº 16 11/11/2005 |
|
|
Capítulo 5: Algoritmos de ordenação de vectores recursivos * Algoritmo de pesquisa linear num vector desordenado. Descrição e exemplo. * Estudo da ordem de complexidade no pior caso relativamente ao número de comparações. * Generalização do estudo anterior. * Algoritmo de pesquisa binária num vector ordenado. Descrição e exemplo. * Estudo da ordem de complexidade no pior caso relativamente ao número de comparações. * Estudo da ordem de complexidade no pior caso relativamente ao número de movimentos no problema das torres de Hanoi. * Generalização do estudo anterior. |
| |
|
|
Lição nº 17 15/11/2005 |
|
|
Capítulo 5: Algoritmos de ordenação de vectores recursivos * Algoritmo de ordenação: fusão. Descrição e exemplo. * Estudo da ordem de complexidade no pior caso relativamente ao número de comparações e deslocamentos efectuados. * Generalização do estudo anterior (Teorema Aho-Hopcroft-Ullmann). |
| |
|
|
Lição nº 18 18/11/2005 |
|
|
Capítulo 5: Algoritmos de ordenação de vectores recursivos * continuação da última aula. * Algoritmo de ordenação: quick sort. Descrição e exemplo. * Estudo da ordem de complexidade no pior caso relativamente ao número de comparações e deslocamentos efectuados. * Algoritmo de ordenação: shell sort. Descrição e exemplo. |
| |
|
|
Lição nº 19 22/11/2005 |
|
|
Capítulo 6: Notação Polaca ("postfix") de expressões aritméticas * Diferenças entre a notação "infix" (usual) e "postfix" (Polaca) * Vantagens da notação Polaca. * Conversão da notação "infix" para "postfix". *Descrição e eimplemntação do algoritmo para realizar a conversão.
|
| |
|
|
Lição nº 20 25/11/2005 |
|
|
Capítulo 7: Tipo estruturado de dados "set" * Introdução * Semelhanças e diferenças com o tipo estruturado de dados "array". * Diagrama de sintaxe. * Definição do tipo e declaração de variáveis: exemplos.
|
| |
|
|
Lição nº 21 29/11/2005 |
|
|
Continuação da aula anterior
|
| |
|
|
Lição nº 22 02/12/2005 |
|
|
Continuação da aula anterior
Capítulo 8: Tipo estruturado de dados "record" * Introdução
|
| |
|
|
Lição nº 23 06/12/2005 |
|
|
Capítulo 8: Tipo estruturado de dados "record" * Semelhanças e diferenças com o tipo estruturado de dados "array". * Definição de campo fixo. * Diagrama de sintaxe. * Definição do tipo e declaração de variáveis: exemplos.
|
| |
|
|
Lição nº 24 09/12/2005 |
|
|
Continuação da aula anterior * Definição de campo variável. * Diagrama de sintaxe. * Definição do tipo e declaração de variáveis: exemplos.
Capítulo 9: Tipo dinâmico de dados: ponteiros * Introdução (representação da memória de um computador e interpretação de um "ponteiro" como um endereço de memória).
|
| |
|
|
Lição nº 25 13/12/2005 |
|
|
Capítulo 9: Tipo dinâmico de dados: ponteiros * Semelhanças e diferenças com o tipo estruturado de dados "array". * Definição do tipo e declaração de variáveis: exemplos. * Representação gráfica dos diversos tipos de dados estudados. * Descrição de algumas funções e constantes pré-definidas para manipulação de ponteiros: new, dispose e NIL.
Resolução de exercícios da folha 5. 1. a) b)
|
| |
|
|
Lição nº 26 16/12/2005 |
|
|
Capítulo 9: Tipo dinâmico de dados: ponteiros * lista ligada simples - Definição do tipo e declaração de variáveis: exemplos - Operações básicas: percorrer, pesquisar um elemento, remover a ponta e remover todos os elementos de uma lista (versão recursiva e iterativa).
Resolução de exercícios da folha 5. 2. a) b) i - iv, vi 3.
|
| |
|
|
Lição nº 27 20/12/2005 |
|
|
Capítulo 9: Tipo dinâmico de dados: ponteiros * lista ligada simples - Operações básicas: inserção e remoção de um elemento numa lista ordenada
Resolução de exercícios da folha 5. 2. b) iv - v
|
| |
|
O Professor, José Luis Esteves dos Santos
|