Teóricas e Teórico-Práticas * Introdução à Programação CC111 * 10/11 * DCC-FCUP
Enunciado do Exame da Época Normal
Os resultados da avaliação contínua estão no sistema Sigarra na pasta de Documentos/Geral (ficha de disciplina).
Os exames da disciplina incidem sobre a matéria leccionada até ao final do semestre
(T) 17.12.2010
Manipulação de ficheiros ( 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). Exemplo simples.
Algumas considerações sobre o teste escrito (cont).
Enunciados do 2ºteste: 1,2 (Resolução: 1 e2 )
(T) 16.12.2010
Correcção de alguns exercícios do teste escrito (realizado a 15.12). Discussão do exercício 1: função mal definida se a conjectura de Collatz for falsa (método que pode não terminar); referência à indecibilidade do Problema da Paragem (halting problem). Comparação de duas resoluções do exercício 1a) em termos de eficiência: abordagem recursiva (ineficiente; crescimento imprevisível da pilha) e abordagem iterativa (memória constante).
(TP) 16.12.2010
Implementação de conjuntos de inteiros por listas de intervalos disjuntos dois a dois (Folha de exercícios 11): função para verificar se um conjunto é vazio; função para contar o número de elementos que pertencem a um conjunto dado. Vantagens da existência de formas normais.
(TP) 15.12.2010
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), somar racionais.
Apresentação de um exemplo de aplicação de FRAC's: resolução exacta de sistemas de equações lineares com coeficientes racionais; exemplos de resultados.
Implementação de conjuntos de inteiros por listas de intervalos disjuntos dois a dois (Folha de exercícios 11): contagem de elementos que pertencem a um conjunto dado.
(T) 10.12.2010
Exemplos de estruturas de dados dinâmicas: 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 valores inteiros: estrutura de cada nó, criação de novos elementos, apontador para início da lista, e acesso ao elemento que segue um dado elemento. Exemplos de funções para construir uma lista para guardar uma sequência de inteiros lida do standard input (inserção dos elementos à cabeça, ficando por ordem inversa da dada) e para determinar do número de elementos de uma lista (versão iterativa e versão recursiva).
Definição do nó de uma árvore binária (em que cada nó guarda um valor inteiro e apontadores para as sub-árvores esquerda e direita). Função para contar o número de nós de uma árvore dada a sua raíz (versão recursiva).
Definição recursiva da função factorial.
Programas:rfactorial.c, fact_animado.c, e listas_arvores.c
(TP) 9.12.2010
(T) 9.12.2010
Apontadores: variáveis cujo conteúdo é o endereço de outras variáveis. Definiçã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).
Alguns apontamentos (também sobre operações com inteiros em precisão infinita "Big Numbers").
Programas:apontadores.c, funcParametros.c (passagem por valor e por referência), bd_AlunosDisc.c e bd_dados.txt
(T) 3.12.2010
Continuação da aula anterior: implementação de várias funções no contexto do exemplo dado sobre gestão e consulta de informação sobre alunos e disciplinas.
Programa: gestaoCurso.c
(TP) 2.12.2010
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), somar, subtrair e multiplicar racionais. Leitura de racionais para conversão em FRAC: ideia para resolução do problema da conversão de uma sequência de caracteres para um FRAC, com restrição dos formatos possíveis PINT, -PINT, -PINT/PINT e PINT/PINT, em que PINT designa uma sequência de dígitos decimais.
Apresentação de um exemplo de aplicação de FRAC's: resolução exacta de sistemas de equações lineares com coeficientes racionais; exemplos de resultados (ex1_gauss.pdf, ex2_gauss.pdf, ex3_gauss.pdf ex4_gauss.pdf, ex5_gauss.pdf).
Programa: frac.c, frac.h
(T) 2.12.2010
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 complexos: declaração de novos tipos (instrução typedef). Exemplo de aplicação: gestão de informação sobre alunos e disciplinas.
Utilização da directiva #define para definir macros simples (por exemplo, LETRA(C) e MAXIMO(X,Y)).
(T) 26.11.2010
Definição de variáveis bidimensionais para guardar tabelas de strings: escrita da sequência de caracteres guardada numa linha da matriz. Exemplos de utilização de tabelas de strings para a simplificação do programa: problemas "Boa Sorte" (outras resoluções) e "Caçando caudas" (codificação da posição (0 a 7), do estado (0 ou 1) e do sentido de movimento (1 ou -1); utilização de aritmética modular para extrair o número de voltas inteiras e para simular um deslocamento circular na rosa dos ventos).
Biblioteca string.h standard da linguagem C: a função strcmp para comparação de sequências de caracteres. Implementação de uma função semelhante. Exemplo de aplicação: problema "Psittacus Erithacus" (análise de uma resolução).
Expressão condicional (condição ? Expressão1 : Expressão2). Introdução da instrução switch.
Programas: boaSorte_a.c, boaSorte_b.c, e my_strcmp.c
(T) 25.11.2010
Caracteres e código ASCII. Tipo char em linguagem C. Leitura e escrita de um caracter: formato "%c" em scanf() e printf(); 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).
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 escrita de strings.
Programas: minParaMaiusculas.c, contar_x.c, ler_escrever.c e contar_seq_x.c
(TP) semana de 22.11
Escrita de uma função para compactar um vector de n inteiros guardado em memória substituindo ocorrências consecutivas de um valor dado x por um único x: análise do problema; implementação por modificação directa do vector sem recorrer a memória auxiliar. [R]
Notas 1º Teste Escrito (A coluna NF contém a nota de frequência após os dois primeiros testes)
(T) 19.11.2010
Geração aleatória de permutações. Determinação dos ciclos de uma permutação (relação de equivalência cujas classes correspondem aos ciclos de uma dada permutação).
Definição dinâmica de vectores em funções.
Exemplos de funções para: criar aleatoriamente uma matriz quadrada (com entradas 0/1), 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.
Programas: permutacoes.c e RelacoesBinarias.c
(T) 18.11.2010
Ordenação de um vector (de inteiros) pelo método de selecção e pelo método da bolha. Breve referência à complexidade O(n2) dos três métodos de ordenação dados, sendo n o número de elementos do vector.
Programas: ordenar_por_seleccao.c e ordenar_por_metodoBolha.c
(TP) semana de 15.11
Funções rand e srand (com inicialização de semente por time). Programa de simulação de lançamentos de um dado e análise da distribuição da sequência de valores (distribuição aproximadamente uniforme). Exemplo de aplicação da função rand - geração aleatória de objectos geométricos (geração de polígonos ortogonais), exemplificando também o uso de relações de equivalência, indução matemática e grafos (em particular, árvores) no desenvolvimento de algoritmos.
Programa: dados6.c
(T) 12.11.2010
Correcção do teste escrito. (Enunciados dos testes: 1,2,3,4; Resolução: 1)
(T) 11.11.2010
Desenvolvimento de programas para: compactar uma sequência de n inteiros guardada num vector removendo todos os zeros (deslocamento à esquerda); libertar uma posição k de um vector de inteiros, deslocando os elementos uma posição para a direita.
Ordenação de um vector pelo método de inserção.
Programas: compactar.c, libertar_k.c, ordena_por_insercao.c
(TP) semana de 08.11
Mini-teste escrito.
(T) 05.11.2010
Pesquisa sequencial (linear) e pesquisa binária em vectores: condições de aplicabilidade e comparação de eficiência.
Algoritmo para determinar todos os números primos entre 1 e n, para n dado (Crivo de Eratóstenes).
Programas: pesquisaVec.c, crivoEratostenes.c (outra versão: crivoEratostenesB.c )
(T) 04.11.2010
Algumas considerações sobre o 1º teste prático: programas para dois problemas.
Variáveis: conteúdos e endereços. Passagem de argumentos a funções: passagem por valor e passagem por referência; passagem de vectores por referência (identificação do endereço da primeira posição de um vector v por &v[0] ou, simplesmente, v). Exemplo: trocar dois elementos de um vector.
Programas: apont.c troca.c
(TP) semana de 01.11
Algoritmo para determinar o número de ocorrências de cada elemento de um intervalo [a,b] numa sequência dada e sua codificação em linguagem C. Representação de um histograma (na horizontal).
Programas: histograma.c (exemplo de ficheiro de dados)
(T) 29.10.2010
Variáveis indexadas unidimensionais. Definição, inicialização e acesso a elementos em variáveis indexadas. Exemplos: guardar uma sequência de inteiros em memória; escrever os valores guardados até uma certa posição; analisar uma sequência de inteiros positivos guardada em memória para determinar o máximo e a posição em que ocorre pela primeira vez; extensão do problema 3 da Folha Prática 5 (determinar todos os vencedores do jogo).
Programas: maxVecPos.c
Jogo: na aula TP pontosVencedores.c e agora osVencedores.c (exemplo de ficheiro de dados)
(T) 28.10.2010
Análise da função implementada para resolução de equações do segundo grau: imprecisão resultante de operações com números em vírgula flutuante; soluções duplas nem sempre identificadas como tal. Tolerância em testes de condições (maior, menor ou igual) envolvendo valores em vírgula flutuante.
Método de Horner para avaliação de funções polinomiais.
Programas: equacaoGau2_tol.c metodoHorner.c
(TP) semana de 25.10
Definição de funções e sua utilização em programas simples.
Enunciados [R1-b),R2,R3]
(T) 22.10.2010
Introdução ao sistema Mooskak: resolução do problema "Minuto Verde" e submissão ao sistema; exemplos de erros e algumas indicações sobre como os evitar.
Protótipos de funções e estrutura de programas. Implementação de uma função para imprimir as soluções reais de uma de equação de segundo grau na forma standard; tipo void; utilização dessa função (procedimento) para resolver uma sequência de equações.
Programas: minutoVerde.c e equacaoGau2.c
(T) 21.10.2010
Operações com números em vírgula flutuante: erros numéricos em operações envolvendo operandos de magnitudes distintas; cálculos em precisão simples e dupla; erros numéricos que sugerem convergência de sucessões que não convergem e/ou divergência de sucessões que convergem; distinção entre cálculos exactos e aproximados.
Noção de função. Utilização da biblioteca standard do C: módulo math.h. Definição de funções. Instruções de chamada e retorno de funções. Variáveis locais e parâmetros. Protótipos. Estrutura de um programa em C.
Programas: Algoritmo de Euclides (novamente); Bissecções sucessivas
(TP) semana de 18.10
Determinação (por aproximaçã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 localização de um zero num intervalo de amplitude menor ou igual que um valor dado. Implementação do método e teste.
(T) 15.10.2010
Introdução dos tipos float e double para representação de valores em vírgula flutuante (aproximações de números reais). Exemplos de programas: cálculo da média de n valores dados; cálculo de uma aproximação do número de Neper (e) por análise da soma dos inversos de k! para k menor ou igual que um dado natural. Promoção e coersão de tipos em C.
Programas: Média e Número de Neper
(T) 14.10.2010
Algoritmo de Euclides para cálculo do máximo divisor comum de dois inteiros: revisão de propriedades da divisão inteira e do máximo divisor comum que justificam a correcção do algoritmo.
Programa: Algoritmo de Euclides (ou outra versão com explicação de resultado).
(TP) semana de 11.10
Eficiência e correcção de um algoritmo. Exemplo: cálculo de potências de expoente natural por multiplicações sucessivas e pelo método binário: comparação do número de operações realizadas pelos dois métodos.
Programas: Multiplicações sucessivas e Método Binário
(T) 08.10.2010
Algoritmo para determinar o comprimento da maior subsequência estritamente crescente numa sequência de inteiros lidos da entrada padrão: valores em memória após entrada de um prefixo da sequência, variáveis correspondentes, actualização dos valores após entrada de um novo elemento. Codificação do algoritmo em C. Exemplo de utilização de pré-decremento na condição de ciclo while.
Programa: maiorSubSeq.c
(T) 07.10.2010
Operadores de incremento e decremento ++ e -- (distinção entre pré-decremento e pós-decremento e entre pré-incremento e pós-incremento). Operadores de atribuição: +=, -=, *=, /=, e %=
Instrução de ciclo for.
(TP) semana de 04.10
Exercícios simples com ciclos while. Exemplo: problema Triângulos (ToPAS-treino). [R]
(T) 01.10.2010
Algoritmo para determinar o máximo de uma sequência finita de inteiros sendo dado o número de elementos da sequência. Implementação em linguagem C.
Escrita e teste de um programa para tabelar potências de base 2: análise de erros de overflow resultantes do limite da capacidade de representação das variáveis do tipo int.
Programas: maxSeqN.c e pot2.c
(T) 30.09.2010
Introdução de instruções de ciclo (while).
Algoritmo para cálculo da soma de uma sequência finita de inteiros (com terminador -1).
Algoritmo para determinar o máximo de uma sequência finita de inteiros positivos (com terminador -1).
Tradução dos dois algoritmos para linguagem C.
Programas: classes.c, somaSeq.c e maxSeq.c
(TP) semana de 27.09
Resolução de exercícios envolvendo instruções de leitura/escrita, instruções de atribuição, expressões aritméticas simples (quociente e resto de divisão inteira) e instruções condicionais.
Converter de um número inteiro de horas em minutos. [R]
Converter um número de minutos em horas e minutos.
O resultado deve ser apresentado em duas linhas se o número de horas e de minutos não for nulo (ou em apenas uma se algum dos dois for nulo). Em cada linha deve indicar o valor seguido de um espaço e da unidade correspondente ("horas", "hora", "minutos" ou "minuto", para que fique gramaticalmente correcto). [R]