Programação Estruturada

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


15/02/2006 (2h)
Objectivos e programa da disciplina. Critérios de avaliação.
Vectores, matrizes e sequências de caracteres (Revisão). Análise do problema "Dizímas": importância da escolha de estruturas de dados adequadas para a obtenção de programas simples e eficientes.

17/02/2006 (1h30)
Análise do problema "Estádio de Maracanã". 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, unir dois 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.

22/02/2006 (2h)
Conclusão da aula anterior: algoritmo para escrita formatada de sequências do tipo {x_1,x_2,...,x_n} para n > 0 (parentesis e vírgulas incluídos).
Sequências de caracteres (strings) e código ASCII para representação de caracteres (revisão). Análise de problemas de manipulação de sequências de caracteres: leitura caracter a caracter até um terminador; inteiro representado por uma sequência de algarismos; regra de Horner para cálculo do valor duma função polinomial e sua aplicação nessa conversão; identificação de palavras nums sequência (por exemplo, como sendo as sequências maximais de caracteres que não contêm espaços). Uso de propriedades do código ASCII para obter programas simples (relação entre o código do dígito e o valor do dígito).
Execução de programas passo a passo: utilização de debuggers ; breve introdução ao gdb.

24/02/2006 (1h30)
Análise de problemas de manipulação de sequências de caracteres (cont): identificação das posições de palavras numa sequência, indexação indirecta de elementos em vectores; 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 desnecessários entre palavras dum nome; determinação dum mínimo numa sequência de valores (formas de inicialização do mínimo); uso de propriedades do código ASCII para obter programas simples (relação entre códigos de maiúsculas e minúsculas).

01/03/2006 (2h)
Uso de macros .
Variáveis cujo conteúdo é o endereço doutras variáveis: apontadores. Definição de apontadores, inicialização, alteração do conteúdo da variável apontada, alteração do valor do apontador por incremento/decremento duma unidade (dependência do tipo de dados que aponta). Aritmética de apontadores. Exemplos (simples) de aplicação. Passagem de parâmetros a funções por valor e por referência. Reserva dinâmica de memória.
Análise de problemas de manipulação de sequências de caracteres (cont): escrita de programa para verificar se duas sequências são iguais, usando apontadores.

03/03/2006 (1h30)
Estruturas em C ( struct): várias formas de definição, indexação dos campos da estrutura, actualização e escrita dos seus valores.
Definição de tipos de dados complexos. Declaração de novos tipos (typedef).
Reserva dinâmica de memória (exemplo, para guardar sequência de caracteres): malloc (reservar espaço) e free (libertar espaço reservado dinâmicamente). Exemplos. Erros resultantes de apontadores não (ou mal) inicializados (exemplo, segmentation fault ).
Exemplo de aplicação: construção duma base de dados com informação sobre alunos e disciplinas; consulta da base de dados para obter informações.

08/03/2006 (2h)
Estruturas e enumerações em C ( struct e enum). Definição dum tipo para valores booleanos usando enum.
Continuação da aula anterior: escrita de algumas funções para consulta à base de dados sobre alunos e disciplinas, com cruzamento de dados de várias tabelas (estruturas).
Algoritmo para contagem do número de ocorrências de cada valor numa sequência de inteiros com repetições, supondo conhecido o intervalo de variação desses valores. Algoritmo para determinação do máximo duma sequência de valores (não negativos).

10/03/2006 (1h30)
Estruturas em C (cont). 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.

15/03/2006 (2h)
Algumas considerações sobre os resultados da primeira submissão Mooshak.
Reserva dinâmica de memória.
Apontadores para estruturas.
Construção e manipulação de listas ligadas simples: criação de novos elementos, determinação do comprimento, determinação do último elemento, procura dum dado elemento, concatenação de duas listas, remoção dum elemento dado (duma lista sem repetições).

17/03/2006 (1h30)
Utilização de estruturas. Definição de macros para aceder aos seus campos. Definição de novos tipos de dados. Introdução à estruturação de programas: modularidade, tipos abstractos de dados, definições e procedimentos para interface a estruturas de dados particulares, robustez dos programas à alteração das estruturas de dados usadas.

22/03/2006 (2h)
Continuação da aula anterior. Organização de programas. O pré-processador: macros e compilação condicional, Ficheiros de cabeçalho ( header files ). Divisão de um programa em vários ficheiros/módulos.

24/03/2006 (1h30)
Compilação de programas constituídos por vários módulos. Ficheiro Makefile e utilitário make.
Funções recursivas (revisão).

29/03/2006 (2h)
Funções recursivas: exemplos. Uso de apontadores para apontadores.

31/03/2006 (1h30)
Tipos abstractos de dados: estruturas de dados de suporte à implementação de listas ligadas simples.

05/04/2006 (2h)
Algumas considerações sobre a segunda submissão Mooshak: resolução dalguns dos problemas.
Continuação da aula anterior.

07/04/2006 (1h30)
Várias estruturas ligadas: definição de tipos para listas simplesmente ligadas (não circulares e circulares), listas duplamente ligadas (não circulares e circulares) e árvores binárias com raíz (com possibilidade de cada nó apontar ou não o seu pai).
Manipulação de listas circulares simples (com valores inteiros): implementação de funções para verificar se um dado inteiro pertence à lista e para construir uma lista (ordenada e não ordenada).

12/04/2006 (2h)
Resolução dalguns problemas envolvendo recursão: avaliação do valor duma expressão aritmética simples (problema do exame de Julho 2005).
Árvores binárias. Árvores que guardam inteiros (ordenados): função para verificar se um valor se encontra na árvore.

21/04/2006 (1h30)
Árvores binárias ordenadas que guardam valores inteiros (cont): implementação de funções para inserção dum valor na árvore, criação dum nó, remoção dum valor, pendurar uma árvore no nó mais à direita doutra, imprimir os valores por ordem crescente, por ordem decrescente e a árvore (mostrando a sua estrutura, por colocação de parentesis).

26/04/2006 (2h)
Implementação do método de eliminação de Gauss-Jordan para resolução de sistemas de equações lineares. Desenvolvimento dum programa estruturado permitindo resolver sistemas em vários corpos (valores racionais, reais, complexos) e para vários formatos de input/output, por alteração de parâmetros de compilação.
Operações em precisão finita e infinita: erros introduzidos e propagados nas operações aritméticas envolvendo variáveis do tipo float (ou double), ausência de significado das comparações com valores exactos (por exemplo, com zero), formas alternativas para comparação de valores (ilustração usando a resolução de sistemas de equações).

28/04/2006 (1h30)
Continuação da aula anterior: implementação dalgumas funções para escrita de expressões lineares, sistemas de equações e matrizes (nos formatos usuais do LaTeX ).

03/05/2006 (2h)
Entrada/Saída de dados: correntes (streams), ficheiros, dados/resultados formatados. Exemplo: representação de polígonos usando listas circulares duplamente ligadas; implementação de funções para desenho de polígonos ortogonais (formato de output adequado para processamento por LaTeX).

05/05/2006 (1h30)
Continuação da aula anterior. Descrição e implementação dum método para geração de polígonos ortogonais.

17/05/2006 (2h)
Conclusão da aula anterior.

19/05/2006 (1h30) (PREVISTO)
Programação genérica: apontadores para funções e tipo void * .

24/05/2006 (2h)
Programação genérica: alguns exemplos de aplicação; resolução do problema 4. do exame de Junho 2005).
Filas (queues) com disciplina FIFO e pilhas (stacks): desenvolvimento de módulos para suporte de operações com estes tipos de estruturas de dados.

26/05/2006 (1h30)
Filas e pilhas (cont.). Aplicação de filas para resolução do problema "Combate Final" (concurso TOPAS'2006).

31/05/2006 (2h)
Estruturas de dados para representação de grafos (com valores associados aos ramos).
Breve introdução dalguns problemas em grafos e de algoritmos para sua resolução: ilustração por aplicação a alguns exemplos.
Análise duma implementação do algoritmo de Ford para determinação do caminho de peso máximo num grafo dirigido acíclico e com pesos.

02/06/2006 (1h30)
Resolução dalguns exercícios de revisão.