Programação Estruturada

Sumários - Aulas Teóricas

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


22/02/2007 (1h)
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.

27/02/2007 (1h)
Continuação da aula anterior.

6/03/2007 (1h)
Análise do problema "Estádio de Maracanã": implementação dum programa usando vector de 0/1 para suporte das reservas (programa simples mas ineficiente em termos de gastos de tempo e memória).

8/03/2007 (1h)
Conclusão da análise do problema "Valor dos Nomes": manipulação de sequências de caracteres (ASCII), uso de propriedades do código ASCII para obter programas simples, conversão entre minúsculas e maiúsculas.
Definição e utilização de macros .

13/03/2007 (1h)
Desenvolvimento duma implementação mais eficiente para resolução do problema "Estádio de Maracanã": utilização duma matriz para representação compacta do conjunto (ordenado) dos números dos bilhetes reservados. Operações necessárias: criação uma linha livre numa matriz por deslocamento de elementos para baixo, remoção duma linha por deslocamento de elementos para cima, união de dois conjuntos de inteiros representados por intervalos (possivelmente, degenerados), verificação de intersecção entre dois conjuntos desse tipo, contagem do número de elementos dum conjunto definido dessa forma.
Escrita formatada de conjuntos definidos por intervalos e conjuntos de pontos isolados.

15/03/2007 (1h)
Continuação da aula anterior. Comparação entre pesquisa sequencial e pesquisa binária num vector (de n inteiros) ordenado: complexidade temporal linear e logaritmica.
Funções recursivas (revisão): análise de terminação.

20/03/2007 (1h)
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. Exemplos (simples) de aplicação. Passagem de parâmetros a funções por valor e por referência.
Introdução à definição de tipos de dados compostos: estruturas em C ( struct).

22/03/2007 (1h)
Continuação da aula anterior. 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).
Exemplo de aplicação: construção duma base de dados com informação sobre alunos e disciplinas.

27/03/2007 (1h)
Apontadores: distinção entre endereço do apontador, endereço que guarda, e valor que aponta; erros resultantes de apontadores não (ou mal) inicializados (exemplo, segmentation fault ).
Continuação da aula anterior.

29/03/2007 (1h)
Exemplos de problemas de consulta à base de dados introduzida nas aulas anteriores.
Comparação de sequências de caracteres (identificação das posições a comparar através de apontadores cujo valor vai sendo alterado).
Algoritmo para contagem do número de ocorrências de cada valor numa sequência com repetições, supondo conhecido o intervalo de variação desses valores: aplicação na resolução dum problema de contagem do número de alunos inscritos a cada disciplina.

03/04/2007 (1h)
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.

12/04/2007 (1h)
Compilação de programas constituídos por vários módulos. Ficheiro Makefile e utilitário make.
Estruturas de dados para acesso dinâmico: listas ligadas simples (não circulares): definição da estrutura, criação de novos elementos, apontador para início da lista, e acesso ao elemento que segue um dado elemento. Exemplos: construção duma lista para guardar uma sequência de inteiros dada.

17/04/2007 (1h)
Manipulação de listas ligadas simples (não circulares): remoção dum elemento da lista, inversão da ordem dos elementos (reverse). Análise de abordagens iterativas e recursivas.

19/04/2007 (1h)
Não houve aula (Dias Abertos da FCUP).

24/04/2007 (1h)
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).
Criação de listas duplamente ligadas não circulares. Remoção dum elemento duma lista duplamente ligada não circular (versão recursiva).

27/04/2007 (1h)
Implementação do método de ordenação quicksort (versão recursiva): definição duma função para determinar a lista dos elementos que são maiores ou iguais a um dado valor e a lista dos que são menores.
Utilização de apontadores para apontadores.
Encapsulamento de funções auxiliares: declarações static e extern .
Tipos abstractos de dados para listas: modularidade (implementações de funções para manipulação da lista não dependentes do tipo de valor guardado em cada nó).

3/05/2007 (1h)
Organização de programas (cont): modularidade do código, possibilidade de re-utilização e facilidade de extensão. Análise dum programa de dimensão média.

08/05/2007 (1h)
Queima das Fitas: o problema dos casamentos estáveis e algumas variantes; emparelhamentos com preferências mútuas (estritamente ordenadas); Algoritmo de Gale-Shapley; emparelhamentos estáveis óptimos segundo os homens e segundo das mulheres.
Extensões: aplicações à resolução do problema de colocação de professores.

10/05/2007 (1h)
Estruturas de dados para árvores binárias. Aplicações: representação de sequências ordenadas (por exemplo, para inteiros), representação de expressões aritméticas; árvores sintáticas.
Definição dum tipo de dados para árvores binárias ordenadas (contendo inteiros) e implementação de funções para: impressão dos valores por ordem crescente, por ordem decrescente, determinar o nó que contem um valor dado (caso exista).
Definição duma estrutura para representação de expressões aritméticas simples: avaliação do valor da expressão.

15/05/2007 (1h)
Implementação de funções para manipulação de árvores binárias: localização do nó mais à esquerda (direita); alteração da árvore por remoção dum nó (possivelmente raíz).

17/05/2007 (1h)
Definição de estruturas do tipo union. Exemplos de aplicação na análise sintática de expressões aritméticas.
Apresentação do tema do segundo trabalho prático da disciplina.

22/05/2007 (1h)
Filas (queues) com disciplina FIFO e pilhas (stacks) com disciplina LIFO.
Desenvolvimento de API's para suporte de uma fila e de várias filas. Ilustração da sua aplicação na resolução do problema "Combate Final" (concurso TOPAS'2006).

24/05/2007 (1h)
Breve introdução à procura de soluções óptimas por pesquisa em profundidade (com retrocesso). Implementação duma máquina para efectuar trocos "honestos", em alternativa à sugerida no problema "Não lhes dês troco (TOPAS 2007)", analisado nas aulas teórico-práticas.

29/05/2007 (1h)
Utilização duma API para suporte de operações sobre uma pilha (stack): simulação dum autómato de pilha ( exame de Julho 2006).

31/05/2007 (1h)
Conclusão da aula anterior.
Programação genérica (ou de ordem superior): apontadores para funções e tipo void * . Exemplos de aplicação: procura dum elemento que satisfaça um critério (implementado por uma função dada); quicksort genérico.