CC111 - Introdução à Programação

2011/2012

Departamento de Ciência de Computadores
Faculdade de Ciências da Universidade do Porto

Aulas Teóricas e Teórico-Práticas

Enunciados de testes e exames de 2011/2012: Enunciados de testes e exames de 2010/2011:
  • 1ºteste: versões 1, 2, 3, 4 (Resolução: 1) (*)
  • 2ºteste: versões 1, 2 (Resolução: 1 e 2 )
  • Exames: Normal, Recurso
(*) Em 2010/2011, programa foi lecionado por uma ordem distinta.

(TP) 12.01.2012

Conclusão da aula teórica: exemplo de aplicação da passagem de argumentos à função main para poder utilizar vários ficheiros de dados e de resultados num programa.
Breve introdução do conceito de programação genérica: possibilidade de passagem de apontadores para funções como argumentos; interesse e exemplo (função de ordenação qsort da biblioteca standard stdlib.h).
Descrição do método de ordenação quicksort e implementação de uma versão (não genérica) para ordenação de listas de inteiros.
  • Programas: my_qsort.c
  • (T) 10.01.2012

    Correção do 2º teste escrito (versão 100 - exercícios 4 e 6).
    Função main com parâmetros (número de argumentos e argumentos passados na linha de comando). Vectores de apontadores (em particular, com elementos do tipo char *).
    Manipulação de ficheiros: introdução do tipo FILE *; canais (streams) pré-definidos no sistema (stdin, stdout e stderr); funções para abertura e fecho de ficheiros (canais/correntes de dados) e para I/O (fopen, fclose, fscanf, fprintf, fgetc, getc, fputc, e putcf).

    (TP) 05.01.2012

    Correção do 2º teste escrito - versão 100 - (exercícios 1, 2, 3 e 5).

    (T) 03.01.2012

    Introdução da noção de recursão. Implementação de funções baseadas em definições recursivas para: calcular o factorial de um inteiro não negativo; calcular o termo de ordem n da sucessão de Fibonnacci (ineficiência da abordagem recursiva quando comparada com a iterativa); criar uma lista ligada (de inteiros); calcular o valor de uma expressão aritmética simples representada por uma árvore binária.

    (TP) 15.12.2011

    Implementação de uma função para determinar o máximo e o mínimo de uma sequência de inteiros lida da entrada padrão e que termina por 0, com passagem de apontadores para as posições onde ficará o resultado. Implementação de funções para determinar o número de elementos de uma lista ligada (com nós do tipo NOCONJ, introduzido na aula teórica) e para procurar o elemento que antecede o que verifica uma certa condição.
    Estudo para resolução de um problema - Reservas para Estádio do Maracanã: análise de estruturas de dados para guardar informação sobre as reservas efectuadas: BOOL Reservas[200001]; vector de 200K booleanos (definidos com tipo char) ou int IntervalosReservados[100][2]; matriz de duas colunas para guardar até 100 intervalos com extremos inteiros (i.e., 2x100 inteiros)? Comparação da complexidade espacial da solução, e também, temporal (tempo que demora a validação de uma reserva em cada caso). Desvantagem da utilização do vector: gasto de memória excessivo e tempo gasto para validação de cada reserva. Desvantagem da utilização da matriz: necessidade de efectuar deslocamentos de linhas para criar espaço para um novo intervalo ou para retirar um intervalo. Motivação para o interesse da utilização de estruturas de dados dinâmicas (listas ligadas).

    (T) 13.12.2011

    Apontadores: variáveis cujo conteúdo é o endereço de outras variáveis. Declaração de apontadores, inicialização, alteração do conteúdo da variável apontada, aritmética de apontadores (breve introdução). Passagem de parâmetros a funções: por valor e por referência.
    Reserva dinâmica de memória: funções malloc() e free() de stdlib.h.
    Exemplo de aplicação (continuação da aula anterior): substituição do campo nome das estruturas ALUNO e DISCIPLINA por um apontador; reserva dinâmica do espaço necessário depois da leitura do nome (leitura efectuada caracter a caracter para espaço temporário auxiliar).
    Exemplos de estruturas de dados dinâmicas. Introdução esquemática de listas simplesmente ligadas (circulares e não circulares), listas duplamente ligadas (circulares e não circulares), e árvores binárias.
    Definição de uma lista ligada simples para guardar um par de valores inteiros: estrutura de cada nó, criação de novos elementos, apontador para o nó inicial e acesso ao elemento que segue um dado elemento.

    (T) 06.12.2011

    Definição de tipos de dados compostos: estruturas em C (struct); várias formas de definição; indexação dos campos da estrutura; actualização e escrita dos seus valores; passagem a funções (por valor). Definição de tipos de dados compostos: declaração de novos tipos (instrução typedef).
    Definição de um tipo de dados abstracto FRAC para racionais (representação simples usando dois inteiros - numerador e denominador - sendo o denominador positivo). Implementação de funções para: simplificar um racional (obter fracção irredutível correspondente, com denominador 1 se o valor for inteiro), determinar o simétrico de um racional, calcular a soma, produto, diferença e quociente de racionais. Apresentação de um exemplo de aplicação de FRAC's: resolução exata de sistemas de equações lineares com coeficientes racionais; exemplos de resultados.
    Definição de tipos para guardar dados sobre inscrições de alunos e sobre disciplinas de um curso. Implementação de funções para consulta e gestão dessa informação. Introdução do conceito de variável global e interesse da sua aplicação no contexto deste exemplo.
    Utilização da diretiva #define do pré-processador para definir macros simples (por exemplo, LETRA(C)).

    (T) 29.11.2011

    Introdução dos tipos float e double para representação de valores em vírgula flutuante (aproximações de números reais) em precisão simples e dupla. Promoção e coersão de tipos em C.
    Análise de erros numéricos: distinção entre representação exata e aproximada; número aproximado de algarismos significativos das representações em precisão simples e dupla; erros de truncatura na soma e subtração de valores de magnitudes distintas.
    Programas para: cálculo de aproximações da constante de Neper (série convergente), cálculo de números harmónicos (série não convergente) e resolução de equações do segundo grau. Análise crítica dos resultados dos programas: erros numéricos que sugerem convergência de sucessões que não convergem e/ou divergência de sucessões que convergem; imprecisão na resolução de equações do segundo grau (soluções duplas nem sempre identificadas como tal e valores aproximados para raízes).
    Comparação de valores em vírgula flutuante: não distinção de valores próximos dentro de uma certa tolerância de erro.
    Métodos exatos e numéricos (de aproximação). Determinação de um zero de uma função contínua f num intervalo ]a,b[ tal que f(a)f(b) < 0: método das bissecções sucessivas para redução da amplitude do intervalo e melhoramento da aproximação de um zero da função. Determinação de uma estimativa da área de uma região de interesse contida num rectângulo e delimitada por gráficos de funções conhecidas: geração aleatória de pontos e determinação da fracção situada na região de interesse; utilização deste método para obter uma aproximação do valor da constante Pi e uma aproximação de uma área delimitada por uma função quadrática e uma recta (cujo valor poderia ser calculado também de forma exata); cálculo de média e desvio padrão dos resultados de um certo número de experiências.
    Utilização de bibliotecas standard da linguagem C: determinação de raízes quadradas usando a função sqrt do módulo math.h; função rand de stdlib.h para geração de pseudo-aleatórios inteiros no intervalo [0,RANDMAX] e srand para inicialização da semente do gerador (definição da semente através do valor dado pela função time).
    Compilação condicionada: instruções #ifdef...#else...#endif e instruções #ifndef...#else...#endif para o pré-processador.
    Breve introdução à definição de tipos compostos: estruturas em C (struct) e declaração de novos tipos de dados (instrução typedef). Definição de um tipo para representação exata de racionais dois inteiros - numerador e denominador - sendo o denominador positivo e implementação funções para somar e multiplicar elementos deste novo tipo .

    (TP) 24.11.2011

    Implementação de funções para: ler uma sequência de caracteres da entrada padrão até ao fim de uma linha (caracter a caracter) e guardá-los numa sequência (com substituição de '\n' pelo terminador '\0'); comparar duas sequências de caracteres lexicograficamente (segundo a ordem induzida pelos códigos ASCII). Escrita de um programa completo que utiliza tais funções para ler duas sequências (de duas linhas da entrada padrão) e as escrever por ordem crescente.
    Utilização da instrução vazia (isto é, ;) em ciclos for.

    (T) 22.11.2011

    Caracteres e código ASCII. Tipo char em linguagem C. Leitura e escrita de um caracter: funções getchar() e putchar(). Desenvolvimento de programas para: contar o número de ocorrências de um certo caracter numa sequência lida; converter maiúsculas para minúsculas e vice-versa.
    Valor de retorno EOF (constante simbólica end-of-file) para assinalar a não existência de mais dados para ler (fim de ficheiro). Exemplo de utilização da instrução de atribuição numa condição de ciclo.
    Strings em linguagem C: sequências de caracteres terminadas pelo caracter nulo ('\0'); inicialização de um vector de caracteres com uma string constante; distinção entre caracter e sequência de caracteres (por exemplo, 'a' e "a"); formato "%s" em scanf() para leitura e em printf() para escrita de strings. Implementação de uma função para verificar se duas sequências de caracteres são iguais. Exemplo de aplicação: problema "Psittacus Erithacus" (análise de uma resolução). Breve referência à função strcmp da biblioteca string.h.

    (TP) 17.11.2011

    Exercícios com variáveis bidimensionais: exemplo de um programa para produzir um documento LaTeX com a definição de uma imagem de um polígono ortogonal.

    (T) 15.11.2011

    Ordenação de vetores de inteiros: método de seleção (selection sort), método de inserção (insertion sort) e método da bolha (bubble sort). Breve referência à complexidade O(n2) dos três métodos de ordenação dados, sendo n o número de elementos a ordenar.

    Variáveis multidimensionais, em particular, matrizes (variáveis bidimensionais). Passagem de variáveis bidimensionais a funções (necessidade de especificar o número de colunas com que a variável foi definida).
    Exemplos de funções para: ler e escrever elementos de uma matriz; determinar a matriz de uma relação binária definida num conjunto {1,...,n}, sendo dados os pares de inteiros que a constituem, verificar as propriedades (reflexiva, simétrica, transitiva e antissimétrica) de uma relação binária definida num conjunto dada a matriz dessa relação, classificar uma relação como relação de equivalência e/ou ordem parcial.
    Ciclos para visita dos elementos de uma matriz com m linhas e ncolunas, dos elementos situados na diagonal principal numa matriz quadrada e dos elementos situados abaixo da diagonal principal numa matriz quadrada.

    (TP) 10.11.2011

    Passagem de valores a funções: comparação de possíveis efeitos co-laterais sobre os argumentos de chamada, recorrendo a dois exemplos: void troca(int a,int b) e void vtroca(int v[], int i, int j).
    Implementação de funções para: substituir todas as ocorrências de um valor por outro valor nas primeiras n posições de um vetor; procurar a posição do mínimo entre os elementos que estão entre duas dadas posições de um vetor; ordenar um vetor de inteiros por ordem crescente aplicando o método de seleção (do mínimo).

    (T) 08.11.2011

    Noção de função. Definição de funções. Instruções de chamada e retorno de funções. Introdução do tipo void. Variáveis locais e parâmetros (passagem por valor). Passagem de vetores a funções: endereço da base do vetor passado como argumento; alteração de elementos de vetores dentro de funções. Declaração dos protótipos versus definição do código das funções. Estrutura de programas simples em C.
    Re-estruturação de programas dados anteriormente para exemplificar a escrita e a utilização de funções: implementação de funções para imprimir um certo número de asteriscos numa linha, calcular do valor absoluto de um inteiro, calcular o máximo divisor comum usando o algoritmo de Euclides, inicializar as n primeiras posições de um vetor de inteiros com zero, contar o número de ocorrências de cada elemento de um intervalo numa sequência de valores lidos da entrada padrão, e escrever o histograma horizontal correspondente.
    Implementação de uma função para localizar a posição de um valor num vetor de inteiros (caso esse valor ocorra): pesquisa linear e pesquisa binária; condições de aplicabilidade dos métodos e comparação da suas complexidades computacionais.

    (TP) 03.11.2011

    Exercícios sobre aplicações de vetores de inteiros: contagem do número de ocorrências de cada valor numa sequência dada, supondo conhecido o intervalo de variação dos elementos da sequência

    (TP) 27.10.2011

    Exercícios sobre aplicações de vetores de inteiros. Algoritmo para determinar todos os números primos entre 1 e n, para n dado (Crivo de Eratóstenes).

    (T) 25.10.2011

    Variáveis indexadas unidimensionais com elementos do tipo int: declaração, inicialização e acesso a elementos Implementação de programas para: guardar uma sequência de n inteiros em memória e escrever depois os valores guardados; contar quantos dos valores guardados são múltiplos de um inteiro não nulo m, para vários valores de m lidos sucessivamente do standard input; verificar se a sequência de valores guardados se encontra ordenada por ordem não decrescente.
    Exemplo de utilização da instrução break.
    Breve referência ao comando (directiva) #define para o pré-processador de C: utilização para definição de valores constantes.
    Implementação de um programa para analisar um conjunto de sequências de inteiros não negativos, todas com o mesmo número de elementos, e identificar aquelas cuja soma dos elementos é máxima (modelo de um jogo em que cada sequência representa as pontuações de um jogador nas várias partidas e se pretende determinar os jogadores vencedores).

    (TP) 20.10.2011

    Demonstração de propriedades da divisão inteira e do máximo divisor comum que justificam a correção do algoritmo de Euclides para cálculo do máximo divisor comum.
    Determinação dos divisores positivos de um inteiro positivo n: propriedade dos divisores de n que permite o emparelhamento de candidatos e restringir a análise aos valores de 1 a raíz quadrada de n. Implementação de um programa que explora este resultado.

    (T) 18.10.2011

    Algoritmo para determinar o comprimento da maior subsequência crescente numa sequência de inteiros lidos da entrada padrão, sendo dado o número de elementos da sequência. Implementação em linguagem C.
    Operadores de incremento e decremento ++ e -- (distinção entre pré-decremento e pós-decremento e entre pré-incremento e pós-incremento). Instrução de ciclo for.
    Programa (trivial) para cálculo do máximo divisor comum de dois inteiros positivos a e b (baseado no teste de todos os inteiros maiores do que 1 e que não ultrapassam a nem b) e introdução de um algoritmo mais eficiente (algoritmo de Euclides).

    (TP) 13.10.2011

    Algoritmo para determinar o número de ocorrências do máximo de uma sequência de inteiros lida da entrada padrão, sendo dado o número de elementos da sequência: escolha de variáveis, interpretação informal no contexto do problema, codificação do algoritmo em linguagem C. Análise da correção do programa: análise do estado das variáveis e análise de invariantes de ciclo.

    (T) 12.10.2011 (aula de revisão)

    Aula extra para estudantes colocados na 2a-fase: revisão de tópicos fundamentais já lecionados na disciplina.

    (T) 11.10.2011

    Algoritmos e sua codificação em linguagem C: análise de uma sequência de inteiros (com terminador 0) lida da entrada padrão: indicação do último valor lido, dos dois últimos valores lidos ou dos dois últimos valores lidos distintos; determinação do máximo; determinação simultanea dos extremos (máximo e mínimo).
    Introdução da instrução de ciclo do...while.

    (TP) 06.10.2011

    Resolução de alguns problemas para exemplificar a utilização da instrução de ciclo while.

    (T) 04.10.2011

    Representação digital de informação (breve introdução): representação posicional de inteiros não negativos numa base b; representação decimal (base 10), binária (base 2), octal (base 8) e hexadecimal (base 16); noção de bit e de byte; representação de inteiros com um número finito e fixo de bits: sem sinal e em complemento para 2. Limite da capacidade de representação das variáveis do tipo int na linguagem C. Análise de erros de overflow de um programa para cálculo de potências de 2.
    Introdução de instruções de ciclo (while): programa para cálculo de potências de 2 e programa para cálculo da soma de uma sequência finita de inteiros (com terminador -1).
    Utilização dos programas com redireccionamento da entrada padrão (standard input) e da saída padrão (standard output) do sistema, para leitura de dados a partir de um ficheiro e saída de resultados num ficheiro.

    (TP) 29.09.2011

    Resolução de exercícios envolvendo instruções de leitura/escrita, instruções de atribuição, expressões aritméticas simples e instruções condicionais.

    (T) 27.09.2011

    Objectivos e Programa da disciplina. Critérios de Avaliação.
    Edição, compilação e teste de programas em ambientes Linux.
    Alguns aspetos da estrutura sintática de um programa em C. Utilização básica da instrução printf. Inserção de comentários em programas.
    Introdução da noção de variável de tipo int.
    Instrução scanf para leitura de inteiro.
    Instrução de atribuição. Distinção entre os operadores = (de atribuição) e == (de teste de igualdade).
    Introdução das instruções condicionais if e if/else através de exemplos simples.


    © Ana Paula Tomás, Departamento de Ciência de Computadores, FCUP, Universidade do Porto, 2011