Programação Estruturada

Ana Paula Tomás
Departamento de Ciência de Computadores
Faculdade de Ciências da Universidade do Porto


22/02/2005 (2h)
Objectivos e programa da disciplina. Critérios de avaliação.
Vectores, matrizes e sequências de caracteres (Revisão): análise de problemas de aplicação.

25/02/2005 (1h30)
Continuação da aula anterior. Alguns subproblemas tratados: criar uma linha livre numa matriz (com duas colunas) por deslocamento de elementos para baixo, compactar uma matriz depois da remoção duma linha, união de conjuntos de inteiros representados por intervalos ou pontos, verificar se a intersecção de dois desses conjuntos é não vazia, contar número de elementos dum conjunto definido dessa forma.

01/03/2005 (2h)
Continuação da aula anterior: análise dum problema envolvendo matrizes e vectores de inteiros. Alguns subproblemas abordados: procurar um elemento num vector, substituir elementos em vectores, acrescentar elementos a vectores, deslocar linhas de matrizes (para baixo ou direita) por cópia, modificar posições duma submatriz, verificar condições sobre o contéudo duma submatriz.

04/03/2005 (1h30)
Revisão de strings e códigos ASCII para caracteres. Análise de problemas de manipulação de strings: leitura caracter a caracter até um terminador, inteiro representado por uma string de algarismos (regra de Horner para cálculo do valor duma função polinomial), separação de subpalavras por espaços, identificação das posições de palavras numa string, indexação indirecta de elementos em vectores.
Passagem de parâmetros a funções por valor e por referência.

08/03/2005 (2h)
Continuação da aula anterior. Análise e resolução do problema "Valor dos Nomes": conversão de caracteres de minúsculas para maiúsculas (e vice-versa); leitura de strings caracter a caracter com remoção de espaços (e de caracteres de tabelação '\t') desnecessários entre palavras dum nome; uso de macros; determinação dum mínimo numa sequência de valores; uso de propriedades dos códigos ASCII das letras (maiúsculas) para simplficar a escrita do programa.

11/03/2005 (1h30)
Variáveis cujo conteúdo é o endereço doutras variáveis. Introdução à utilização de apontadores: definição de apontadores, inicialização, alteração do conteúdo da variável apontada. Exemplos simples de aplicação.

15/03/2005 (2h)
Estruturas em C: várias formas de definição, indexação dos campos da estrutura, actualização e escrita dos seus valores.
Ilustração da sua aplicação na implementação do algoritmo de Gale-Shapley para resolução do problema dos casamentos e estáveis: análise do problema e de formas de guardar os dados necessários de modo a aumentar a eficiência do programa; implementação duma lista usando um vector.

18/03/2005 (1h30)
Estruturas e enumerações em C (struct, enum ). Análise dum problema simples de gestão de stocks.

22/03/2005
Dia da Universidade (tolerância de ponto).

01/04/2005 (1h30)
Conclusão da análise do problema de gestão de stocks: aspectos de interface, vantagens da manipulação de quantias monetárias como inteiros.
Introdução à estruturação de programas por separação em módulos: ficheiros header .

05/04/2005 (2h)
Alocação dinâmica de memória.
Apontadores para estruturas.
Construção e manipulação de listas ligadas: criação de novos elementos, inserção de elementos no princípio da lista ou em posições convenientes, remoção de elementos, procura dum elemento que satisfaça uma condição dada.

08/04/2005 (1h30)
Continuação da aula anterior. Manipulação de listas ligadas simples.
Uso de apontadores para apontadores.
Modificação do programa do problema "Estádio de Maracanã", para passar a representar o conjunto de reservas por uma lista ligada.

12/04/2005 (2h)
Funções recursivas: revisão. Exemplos de aplicação a problemas envolvendo listas ligadas, incluindo inversão e ordenação (quicksort).

15/04/2005 (adiada)

19/04/2005 (2h)
Consulta da informação sobre alunos/cursos/disciplinas da base de dados apresentada na primeira submissão: algumas questões mais elaboradas.
Tipos abstractos de dados (introdução): implementação de length e member independente da estrutura de dados usada. Definições e procedimentos para interface a estruturas de dados particulares.

22/04/2005 (1h30)
Tipos abstractos de dados (continuação).
Organização de programas. O pré-processador: macros e compilação condicional, header files . Divisão de um programa em vários ficheiros e Makefiles.

26/04/2005 (2h)
Implementação simples do método de eliminação de Gauss-Jordan para resolução de sistemas de equações lineares (com valores do tipo float).

29/04/2005 (1h30)
Organização de programas (cont): ilustração através do desenvolvimento dum programa estruturado para o método de eliminação de Gauss-Jordan, que permite trabalhar com vários tipos de valores e formatos de input/output, bastando configurar parâmetros de compilação.

3/05/2005 e 6/05/2005
Semana da Queima das Fitas.

10/05/2005 (2h)
Conclusão da aula anterior.
Introdução de novas estruturas de dados: listas duplamente ligadas. Exemplos de aplicação: descrição e manipulação de polígonos simples (e ortogonais).

13/05/2005 (1h30)
Conclusão da aula anterior.

17/05/2005 (2h)
Estruturas de dados para grafos.
Ideias básicas dalguns algoritmos para resolução de problemas em grafos: determinação de árvores de suporte mínimas (algoritmos de Kruskal e de Prim), de caminhos máximos em DAGs (algoritmo de Ford), de caminhos mínimos em grafos (algoritmo de Dijsktra) e de caminhos de capacidade máxima.

20/05/2005 (1h30)
Descrição formal dos métodos de Kruskal, Prim, Ford e Dijkstra. Desenvolvimento duma biblioteca para grafos e sua utilização na implementação do método de Ford.

24/05/2005 (2h)
Definição de estruturas de dados para árvores com raíz. Desenvolvimento duma biblioteca para árvores binárias.

27/05/2005 (1h30)
Resolução de problemas: partição duma lista circular simples por uma condição; implementação do algoritmo de Prim.

31/05/2005 (2h)
Input/Output: streams, ficheiros , I/O formatado (revisão).
Utilização de debuggers : introdução ao gdb.
Programação genérica: apontadores para funções e tipo void * .