Sistemas de Computação Lic. Ciências da Computação, 1º ano 2006/2007 Docente responsável: A.J.Proença

Projecto Integrado
Programação Imperativa & Sistemas de Computação

Objectivos | Regulamento | Enunciado: Fase1, Fase2, Fase3 | Submissão

Ultima Modificação: 06 Jun 2007

departamento de informática

Notas

1. O sistema de submissão já está operacional. (06-Jun-07)

2. Material disponível reformulado para a Fase3 aqui. (28-Maio-07)

3. Versão final da Fase 2 já actualizada! Inclui alterações pontuais ao Regulamento (prazos, em cor diferente), reforço das regras de escrita e submissão do relatório, e uma correcção na especificação das tarefas (também em cor diferente) (9-Maio-07)

4. Resultados da Fase 1: já foram divulgados directamente por email a todos os alunos referidos como autores dos relatórios entregues, tendo sido enviado o relatório corrigido, em PDF, para o endereço institucional; quem não recebeu, por favor contactar o docente.
   O aviso colocado no fim do Regulamento relativo a comportamentos fraudulentos não teve, infelizmente, impacto suficiente para prevenir situações destas: ocorreram novamente este ano vários casos que implicaram a reprovação imediata dos estudantes (sem hipótese de ida a exame), os quais terão na pauta Não Admitido. (08-Maio-07)

5. A especificação e o material referentes à Fase 2 já estão disponíveis! (1-Maio-07)

6. Sistema de submissão de trabalhos: foi hoje modificado, de modo a (i) ficar disponibilizada uma nova entrada para a Fase 1 do projecto específica de SC, (ii) validar automaticamente a designação do ficheiro introduzido (ver em baixo alguns detalhes que foram aperfeiçoados), e (iii) contemplar a tolerância de 6h ao prazo de entrega (mas com penalização na classificação). (10-Abr-07)

7. Todos os documentos indispensáveis à realização da Fase 1 já estão disponíveis!
   Qualquer outra falha ou dúvida, por favor contactar o docente da disciplina por email. (29-Mar-07)

Objectivos de formação e resultados de aprendizagem

Este projecto tem como objectivos principais a formação genérica e específica de estudantes num ou mais temas em fundamentos de computação, em áreas de informática afins e interligadas: a programação imperativa e a arquitectura dos sistemas de computação.

Os objectivos de formação genérica incluem: (i) a pesquisa, análise e selecção de informação, (ii) o treino de trabalho de grupo na resolução de problemas, (iii) o desenvolvimento da capacidade de análise e compreensão de textos em língua inglesa, e (iv) o desenvolvimento da capacidade de comunicação escrita e oral.

A avaliação dos resultados esperados de aprendizagem irão verificar se as/os estudantes conseguem demonstrar ter adquirido o seguinte conjunto de competências genéricas e específicas:

• competências genéricas
  • a capacidade de trabalho em grupo e respectiva comunicação efectiva e eficiente entre os elementos do grupo
  • a capacidade de comunicação escrita e oral na apresentação e discussão dos processos usados e resultados obtidos
  • a capacidade de utilização de ferramentas genéricas de informática em ambiente Linux e de elaboração de documentos anotados
• competências específicas de Programação Imperativa
  • a capacidade de desenvolver algoritmos para resolver problemas, de forma criativa, criteriosa e crítica, e inserida/o num grupo de trabalho
  • o conhecimento e a capacidade de codificar algoritmos e estruturas de dados segundo os princípios da programação estruturada (imperativa)
  • a capacidade e aptidões práticas para gerar, executar e testar programas codificados em C, usando um conjunto adequado de utilitários (GNU)
  • o conhecimento e a capacidade de analisar a execução de programas numa dada arquitectura, e as aptidões de desenvolver e aplicar testes de conformidade em situações de fronteira
  • capacidade e aptidões na produção de documentação adequada à manutenção por terceiros dos programas desenvolvidos
• competências específicas de Sistemas de Computação
  • a capacidade de pesquisar, analisar e especificar o modelo básico de funcionamento dum computador, com o objectivo de se desenvolver um simulador de um sistema de computação e respectiva visualização de resultados em formatos numéricos
  • o conhecimento e a capacidade de identificar e caracterizar as técnicas de codificação de estruturas típicas de controlo e dos métodos de acesso e manipulação de dados estruturados, no processo de compilação de uma linguagem imperativa, usando o gcc
  • a aptidão para analisar código em assembly e utilizar ferramentas de baixo nível de depuração (gdb) de programas
  • o conhecimento, a capacidade e a aptidão para aplicar técnicas de engenharia inversa a código binário
  • aptidões na aplicação de técnicas e métricas na análise de desempenho baseadas no profiling de aplicações
  • capacidades e aptidões para descrever, aplicar e avaliar técnicas de optimização de desempenho independentes e dependentes da máquina

Regulamento

Caracterização do Projecto

1. O projecto consiste na realização de um ou mais trabalhos práticos em grupo, integrando conteúdos de 2 disciplinas, e com entrega faseada de resultados.
2. A não aprovação no projecto conduz à classificação de "Não Admitido" na pauta final de exame. 
3. O projecto conterá questões e tarefas específicas para cada uma das disciplinas, devidamente especificadas no enunciado do projecto na página de cada uma das disciplinas.
4. O projecto deverá ser submetido através de um sistema de submissões de trabalhos; o ficheiro compactado a submeter com o trabalho deverá ter o seu nome relacionado com a fase (1, 2 ou 3, com a indicação de "Fasen-"), seguido do nº de grupo, do curso, e da extensão do modo de compactação, que deve ser ZIP (por ex., "Fase2-lcc-31.zip"); a documentação a submeter deverá constar de: (i) relatório redigido em LaTeX, segundo a estrutura e modelo definidos para os relatórios (modelo Tex com anexo), (ii) relatório compilado para PDF (aspecto do relatório), (iii) eventuais ficheiros com o código e/ou conjunto de testes, e (iv) eventual informação adicional. A Fase 3 poderá ter um relatório mais simples, e consequente modelo alterado/simplificado de submissão.
5. Material de apoio à produção de documentos em LaTeX, elaborado por Alberto Simões: Mini-curso de LaTeX e  Manual de LaTeX.
6. Os resultados do projecto serão avaliados em 3 fases distintas ao longo do semestre: nas semanas 7, 11 e 15 (datas indicadas adiante).
7. As questões e tarefas a efectuar pelos grupos que se encontram inscritos a apenas uma das disciplinas serão devida e atempadamente acauteladas, e por contacto directo com o docente responsável da respectiva disciplina.

O Projecto como trabalho de grupo

1. O projecto deverá ser realizado por grupos de 3 elementos, devendo estes estarem inscritos às mesmas disciplinas (ou às 2, ou todos apenas a uma delas). Em casos excepcionais, devidamente justificados e aceites pelo docente responsáveis de cada uma das disciplinas, será possível a realização do projecto com menos elementos.
2. A organização, planeamento e coordenação das actividades do trabalho de grupo é da inteira responsabilidade dos seus elementos. Os slides apresentados na sessão de  apresentação de SC estão aqui disponíveis.

Metodologia de avaliação do Projecto

1. A avaliação do projecto consiste na verificação da aquisição individual dos conhecimentos, capacidades e aptidões especificadas no enunciado do trabalho, e decorrerá num laboratório do DI.
2. Os elementos que serão utilizados na avaliação incluem:
   1. O relatório: (i) a versão electrónica deverá ser submetida no prazo especificado, e (ii) a versão impressa deverá acompanhar o grupo durante a defesa do trabalho (quando houver).
   2. Eventual apresentação formal oral (tarefa a definir explicitamente no enunciado).
   3. O programa desenvolvido de acordo com as especificações, em condições de ser apresentado (não são admitidos erros de compilação), e respectiva bateria de testes.
   4. A defesa do trabalho (obrigatória nas fases 2 e 3) junto a um computador, durante um tempo estimado de 20 min, que poderá ser individual ou em grupo.
3. Calendário para a entrega dos relatórios em formato electrónico:
   1. Fase 1, quarta, 11-Abr-07.
   2. Fase 2, segunda, 07-Mai-07, 12h00 14-Mai-07.
   3. Fase 3: segunda, 04-Jun-07, 12h00. 10-Jun-07.
4. Calendário para a realização das defesas dos trabalhos:
   1. Fase 1: não há avaliação oral; os resultados da avaliação serão apresentados e discutidos pelos docentes nas suas aulas.
   2. Fase 2: no horário das sessões laboratoriais, na semana de 07-Mai-07 21-Mai-07.
   3. Fase 3: no horário das sessões laboratoriais, na semana de 04-Jun-07. Só haverá defesa se necessário.
5. A ordem de defesa dos trabalhos é coincidente com a ordem de inscrição dos grupos, e será atempadamente divulgada.
6. A classificação final do projecto será, em princípio, por patamares, sendo os definidos para SC os seguintes:
   • Não Aprovado - não apresentação de projecto ou resultados com um nível elevado de insatisfação de requisitos.
   • Fraco (<10) - com diversas falhas, mas que não inviabiliza a ida a exame teórico (lacunas sérias em conhecimentos ou na utilização de ferramentas, deficiências graves no programa apresentado, ... )
   • Aprovado (10) - cumpre, no limite, os requisitos mínimos especificados nos resultados de aprendizagem (embora com questões relevantes que não estejam correctas)
   • Razoável (entre 11 e 14) - cumpre razoavelmente os requisitos especificados nos resultados de aprendizagem
   • Bom (entre 15 e 18) - cumpre bem os requisitos especificados nos resultados de aprendizagem
   • Excelente (19 ou 20) - excede os requisitos especificados nos resultados de aprendizagem
7. Os pesos relativos da avaliação de cada uma das fases em SC são os seguintes:
   1. Fase 1: 20% .
   2. Fase 2: 65% .
   3. Fase 3: 15%  (opcional para quem já tiver garantido o acesso a exame de SC).
8. Para cada uma das fases de avaliação do projecto os grupos serão atempadamente informados do seu desempenho, com feedback adequado para melhorarem os seus resultados, de acordo com um modelo de classificação similar.
9. A classificação individual final será um valor de compromisso entre a classificação obtida pelo grupo no projecto e a impressão individual que cada elemento produziu nas equipas de examinadores e a opinião manifestada por todos os elementos do grupo de trabalho.
10. Caso sejam detectadas situações fraudulentas (desde plágio de outro grupo ou de um outro qualquer local, a comportamento fraudulento de um dos elementos do grupo), as partes envolvidas ficarão sujeitas a acções ou procedimentos disciplinares seguindo a hierarquia institucional e de acordo com a gravidade demonstrada. Recomenda-se a leitura do documento de reflexão produzido na sequência das irregularidades ocorridas em 2004/05, em que vários estudantes comprometeram a sua carreira de estudante com a reprovação a estas 2 disciplinas (para além dos procedimentos disciplinares).
11. Dúvidas que surjam na sequência de ambiguidades ou lacunas no enunciado do projecto e/ou deste regulamento, deverão ser apresentadas a um dos docentes responsáveis de PI ou SC, preferencialmente por email. Quando necessário, o esclarecimento dessas situações far-se-á por inclusão de um aviso na página Web da disciplina.

Topo...

Enunciado

Fase 1

Esta primeira fase do projecto é independente para as componentes de avaliação das duas disciplinas envolvidas. O resto deste enunciado aplica-se apenas à componente a ser avaliada em Sistemas de Computação.

Fase 2

A 2ª fase do projecto continua independente para as componentes de avaliação das duas disciplinas envolvidas, tal como acontecerá com o resto do projecto. Infelizmente, o esforço docente requerido para a elaboração de um projecto integrado e coordenado é superior ao humanamente possível em 2006/07.
Assim, o resto deste enunciado aplica-se apenas à componente a ser avaliada em Sistemas de Computação, embora tenha referências ao projecto a decorrer em paralelo em PI (LCC) ou LI2 (LEI), o projecto da Arca de Jogos.

Contexto

No âmbito do projecto da Arca de Jogos é essencial dispor de um gerador de números pseudo-aleatórios. Não sendo indispensável ter um gerador de muita qualidade, pode-se optar por um algoritmo relativamente simples. Contudo, para se saber exactamente como deve ser utilizado o algoritmo, é necessário compreender o seu funcionamento.

Lamentavelmente, o programador não disponibilizou o código fonte da função que realiza o algoritmo, pelo que, apenas estão disponíveis os ficheiros com o código objecto e o protótipo da função (extensões ‘o’ e ‘h’, respectivamente).

Recuperar o ficheiro com o código fonte de uma função em C que gera números pseudo-aleatórios, a partir do do seu protótipo e do código objecto dessa função.

Informação adicional
Deverão ser utilizadas ferramentas para compilar (gcc),  desmontar (objdump) e depurar (gdb) os códigos produzidos por um compilador, de forma a permitir:
- executar programas no modo passo a passo;
- instalar/desinstalar pontos de paragem;
- desmontar e analisar o código gerado;
- consultar/alterar o valor de registos e de posições de memória;
- consultar o estado da pilha associada à invocação de funções.

Material disponível
Todos os ficheiros necessários para este trabalho estão disponíveis no arquivo scFase2, com excepção do ficheiro que contém o código fonte da função que gera os números pseudo-aleatórios.
Nomeadamente, o arquivo contém:

Makefile:     com a informação que o programa make usa para produzir o executável correspondente ao programa final;

gerador.h:   com o protótipo da função;

gerador.o:   com o código objecto da função de que desconhecemos o código fonte;

main.c:         com o código fonte da função principal do programa final.

1.     Desmonte o código no ficheiro gerador.o e comente-o de forma apropriada;
2.     Use o comando make para gerar o ficheiro executável;
3.     Use o depurador para prosseguir as seguintes tarefas:

a)   Introduzir um ponto de paragem no início da função;

b)   Executar o programa, passando-lhe como parâmetros os  números de cada um dos elementos do grupo;

c)   Executar a função passo a passo, mostrando o conteúdo dos registos e das posições de memória que vão sendo modificados durante a execução de cada instrução.

d)   Explique, por palavras suas, o que acontece de cada vez que se executa a função; referindo as alterações ao estado de execução do programa após a execução da função e os valores devolvidos pela função de cada vez que é executada;

e)   A partir do código desmontado da função, deduza uma versão em código C que no seu entender poderá representar o algoritmo original usado para gerar os números pseudo-aleatórios;

f)    Sabendo que o compilador gcc quando instruído para optimizar (opção –On) tenta aumentar a eficiência do código, através de alguns artifícios, explique, por palavras suas, eventuais discrepâncias entre o código assembly produzido pela compilação da função escrita na alínea e) e o código desmontado original (gerador.o).

Nota: a alínea c) deverá ser repetida para cada uma das chamadas à  função, efectuadas a partir da função main, mostrando, de cada vez, os argumentos passados à função.

Relatório e submissão da Fase2

O relatório a elaborar e sua submissão segue as regras definidas para a Fase1, com excepção dos prazos que são os específicos da Fase2 e que foram reformulados no Regulamento.

Não serão aceites relatórios que não satisfaçam os seguintes critérios:
- não tenham a estrutura definida nas regras do Regulamento;
- tenham menos que 4 ou mais que 8 páginas (sem contar com os anexo);
- não sigam as recomendações feitas na correcção do relatório da Fase1;
- não contenham os seguintes campos obrigatórios: Resumo, Conteúdo, Introdução e Conclusões .

O relatório a produzir deverá conter, para além do especificado no parágrafo anterior:
- uma secção com o título "Análise do gerador de números aleatórios", contendo (i) uma subsecção a descrever esta função tal como ela foi compilada, e o comportamento dos registos e posições de memória alterados (respostas as questões 3.c e 3.d), e (ii) uma subsecção com o algoritmo usado para a geração de números aleatórios (descrito usando C) e uma explicação para a eventual discrepância entre o código gerado pela compilação do código com este algoritmo e o ficheiro original (respostas às questões 3.e e 3.f).
- um anexo com o código desmontado a partir do conteúdo do ficheiro gerador.o, devidamente comentado conforme solicitado acima.

 

Topo...

Fase 3

Objectivo funcional do trabalho na Fase3

O estudo de código produzido pelo compilador gcc, considerando o nível de optimização “-O2” a partir de programas em linguagem C que incluem: chamadas encadeadas de funções, controlo de fluxo e estruturas de dados. A ênfase vai para a análise do código produzido e das estruturas e contextos que suportam a invocação de procedimentos.

Material disponível
O material necessário para este trabalho, incluindo o modelo a utilizar para a resposta e submissão desta fase, está disponível no arquivo scFase3, que contém os seguintes ficheiros:

• Makefile:          usado pelo programa make para produzir o programa executável;
• seq.h:               o protótipo das funções;
• seq.c:               o código fonte das funções acessórias;
• main.c:             o código fonte da função principal;
• relatorio.txt      o modelo de documento para submissão de respostas.

Informação geral
Impõe-se a utilização de ferramentas de acesso livre para as tarefas de: compilar (gcc),  desmontar (objdump) e depurar (gdb), seguindo o modelo adoptado para o desenvolvimento da fase 2.

Descrição detalhada das tarefas da Fase3

1.    Use o comando make para gerar o ficheiro executável;

2.    Use o depurador para prosseguir as seguintes tarefas :
 

a)   Na função gera estabeleça um ponto de paragem imediatamente antes da instrução ret para permitir suspender a execução antes do regresso da função.

b)    Executar o programa passando como argumento o seu número mecanográfico de aluno (e.g. prog 49442).

c)    Acrescente toda a informação (comentários) necessária para estabelecer a relação entre o código C original da função gera e o código IA32 desmontado. Em particular, apresente todos os elementos respeitantes: (i) à estrutura de controlo de fluxo (for) e (ii) ao acesso à estrutura de dados (sequencia) declarada.

d)    Construa a tabela de alocação de registos, da função gera, incluindo os valores iniciais das variáveis C que representam.

e)    Apresente toda a informação relevante, tanto no que diz respeito à estrutura como ao conteúdo (incluindo os valores das variáveis globais e locais), das áreas de activação da pilha (activation records, também conhecidas como quadros das funções ou stack frames), correspondentes à função gera e das demais funções que a precederam no processo de execução.

f)     Conclua a execução do programa e apresente o resultado obtido na saída de dados.

Relatório e submissão da Fase3

O relatório a elaborar deverá obedecer ao formato definido no ficheiro relatorio.txt, fornecido no material disponível, e ser submetido, impreterivelmente, até às 24h do dia 10 de Junho.

Atenção:
1. A Fase 3 terá uma avaliação individual, pelo que a sua submissão deverá também ser feita de modo individual .
2. O processo de submissão segue o modelo adoptado para as fases anteriores, mas como algumas alterações, para permitir distinguir os trabalhos de LCC dos de LEI, e para identificar individualmente os trabalhos; o nome do ficheiro a submeter deverá obedecer ao seguinte novo formato: Fase3-(lei|lcc)-núm_aluno.txt  de que são exemplos: Fase3-lei-48342.txt ou Fase3-lcc-42856.txt.
3. O sítio na Web para submissão da Fase 3 está ainda em construção, e deverá ficar operacional antes de Junho. Logo que esteja, esta nota será retirada deste local. E se houver alteração ao formato, será aqui apresentada. O sistema de submissão já está a funcionar: cada elemento deve entrar com o login do seu grupo e introduzir o nº de aluno com que se inscreveu nesse grupo.
 

Topo...