Arquitectura de Computadores
Lic. Matemática & Ciências da Computação, 1º ano
2004/2005
Docente responsável: A.J.Proença

 

Projecto Integrado
Programação Imperativa & Arquitectura de Computadores

Enunciado | Regulamento

Ultima Modificação: 24 Jan 2006

 

 departamento de informática

Notas

  1. Este documento descreve o único tema disponível para a realização do projecto integrado das disciplinas em epígrafe

  2. Os assuntos referentes à organização do trabalho e à realização, entrega e avaliação do projecto, são descritos em regulamento próprio.

Enunciado

Índice

  1. Objectivos de formação e resultados de aprendizagem
  2. Formato de Imagem PNM
    1. PBM: Portable BitMap Format
    2. PGM: Portable GrayMap Format
    3. PPM: Portable PixMap Format
  3. Primeira fase (Fase 1)
  4. Segunda fase (Fase 2)
  5. Terceira fase (Fase 3)

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 tema em fundamentos de computação em áreas de informática afins e interligadas (a programação imperativa e a arquitectura de computadores). O tema seleccionado para esta instância lectiva foi o processamento de imagem.
No contexto deste projecto, as imagens a processar estarão sempre no formato PNM (Portable aNyMap) que se descreve na secção seguinte.

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.

Os objectivos de formação específica incluem: (i) a análise da especificação e do problema, (ii) o desenvolvimento de algoritmos e consequente programação numa linguagem imperativa, (iii) a execução e realização de testes de conformidade, (iv) a análise da execução desses programas numa dada arquitectura de computadores (IA-32), e (v) a aplicação de técnicas de optimização de algoritmos/programas/códigos, com vista a melhorar o desempenho.

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:

Formato de Imagem PNM

O PNM é um formato de imagem muito simples, fácil de ler a partir de um ficheiro e também fácil de escrever para um ficheiro. Actualmente uma imagem PNM pode pertencer a uma de três famílias, abaixo explicadas: PBM, PGM e PPM. Cada família tem duas representações: uma textual e uma compactada.

Embora não seja um requisito da especificação PNM, existe a convenção de que a imagem deve ser armazenada de cima para baixo e da esquerda para a direita. Cada pixel da imagem é armazenado num byte, valor 0 = preto, valor 255 = branco. Os componentes de cor são armazenados na ordem habitual RGB ("red", "green" and "blue"), um valor para o nível de vermelho, um valor para o nível de verde e um valor para o nível de azul.

PBM: Portable BitMap Format

Esta família corresponde a imagens contendo apenas duas cores, branco (1) e preto (0), normalmente designadas por bitmaps.

A sua forma textual pode ser descrita da seguinte maneira:

Um exemplo de uma imagem neste formato poderia ser:

P1
# PBM example 
9 7
 0 0 0 0 0 0 0 0 0 
 0 1 1 1 1 0 0 1 0 
 0 1 0 0 1 0 0 1 0 
 0 1 1 1 1 0 0 1 0
 0 1 0 0 0 0 0 1 0
 0 1 0 0 0 0 0 1 0
 0 0 0 0 0 0 0 0 0

Se analisar um pouco a imagem que esta representa um banner com fundo preto e letras a branco. Neste caso, a imagem contem a string "PI". Note também que, para este caso do banner, a primeira linha, a última linha, a primeira e última colunas são pretas e que entre duas letras há duas colunas pretas de separação.

A sua forma compactada resulta da constatação de que um byte é uma sequência de 8 0's e 1's. Assim, um byte pode guardar 8 pixeis da imagem. A única alteração ao formato é o identificador que passa a: P4.

A seguir apresenta-se o exemplo anterior agora compactado:

P4
# PBM example 
9 7
0 0
121 0
73 0
121 0
65 0
65 0
0 0 

Note que, apenas para efeitos de visualização, introduziram-se espaços entre os valores da forma compactada. Nas formas compactadas PNM, não há espaços de separação entre os valores. A informação é guardada em ficheiro em bytes sequenciais.

PGM: Portable GrayMap Format

Esta família corresponde a imagens definidas com vários níveis de cinzento.

A sua forma textual pode ser descrita da seguinte maneira:

Um exemplo de uma imagem neste formato poderia ser:

P2
# PBM example 
9 7
15
 0 0 0 0 0 0 0 0 0 
 0 15 15 15 15 0 0 12 0 
 0 15 0 0 15 0 0 12 0 
 0 15 15 15 15 0 0 12 0
 0 15 0 0 0 0 0 12 0
 0 15 0 0 0 0 0 12 0
 0 0 0 0 0 0 0 0 0

Se analisar um pouco a imagem que esta representa um banner com fundo preto e letras a branco. Neste caso, a imagem contém a string "PI". Note também que, para este caso do banner, a primeira linha, a última linha, a primeira e última colunas são pretas e que entre duas letras há duas colunas pretas de separação.

A sua forma compactada resulta da eliminação dos espaços nas linhas da imagem e apenas para o caso em que MAX está no intervalo [0,255]. A única alteração ao formato é o identificador que passa a: P5.

PPM: Portable PixMap Format

Esta secção ficará em branco. Espera-se que os alunos "investiguem" e que a preencham um pouco à semelhança das outras.

 

Primeira fase (Fase 1)

Nesta fase, pretende-se que as/os estudantes executem as seguintes tarefas:

  1. Pesquisar a Web para caracterizar sucintamente os formatos de imagem JPEG e GIF (avaliação exclusiva de AC), e para completar o enunciado na descrição do formato PPM;
  2. Procurar na Web produtos que, em ambiente Linux (preferencial) convertam ficheiros de imagem/gráficos em formato JPEG ou GIF para um dos formatos PNM (PBM, PGM ou PPM), e testar pelo menos um dos produtos que satisfaça os requisitos (avaliação exclusiva de AC);
  3. Desenvolver um conjunto de algoritmos elementares para transformar imagens PNM; mais concretamente, seguindo a descrição feita na secção anterior pretende-se transformar imagens do tipo P2, P3, P5 e P6 em imagens do tipo P1 ou P4 (avaliação exclusiva de PI);
  4. Codificar os algoritmos propostos, documentando-os adequadamente (avaliação exclusiva de PI);
  5. Preparar um conjunto de ficheiros de entrada para teste, que permita validar, além de outras, as de condições limite (avaliação exclusiva de PI);
  6. Criar programas executáveis, usando o ambiente de desenvolvimento da GNU, e seleccionando o nível de optimização -O2 ;
  7. Integrar e testar o produto final (da Fase 1) usando comandos da shell para (i) leitura de um ficheiro JPEG ou GIF e sua conversão para PNM, (ii) leitura de um ficheiro PNM (P2, P3, P5 ou P6) e sua conversão para noutro ficheiro PNM (P1 ou P4) e (iii) visualização da imagem usando ImageMagick (avaliação exclusiva de PI);
  8. Refinar o interface com o utilizador, construindo um menu de operações e permitindo mais que uma operação em cada sessão (avaliação exclusiva de PI);
  9. Apresentar os resultados destas tarefas num relatório redigido redigido conforme as regras definidas no regulamento; a sua estrutura deverá conter, para além do título e lista de autores, um resumo (máx. 600 caracteres), uma introdução com caracterização do problema a resolver, uma breve exposição/relato dos aspectos relevantes de cada uma das fases/tarefas, as conclusões, uma lista da bibliografia pertinente para a resolução do trabalho, e, em anexo, uma listagem do código.

A título de curiosidade, apresentam-se algumas das operações que se poderão oferecer ao utilizador (se tiver tempo utilize a sua imaginação para criar mais):

  1. Compactar P1 em P4
  2. Descompactar P4 em P1
  3. Binarizar P2 em P1
  4. Binarizar P3 em P1
  5. Descompactar e Binarizar P5 em P1
  6. Descompactar e Binarizar P6 em P1

 

Segunda fase (Fase 2)

Nesta fase, pretende-se que as/os estudantes executem as seguintes tarefas:

  1. Corrigir e/ou completar as tarefas solicitadas na 1ª fase e que não foram realizadas, ou foram-no de modo menos correcto ou adequado; estas incluem: (i) a produção de textos sobre JPEG/GIF/PPM, (ii) a selecção/teste de conversores JPEG/GIF para PNM (PBM, PGM ou PPM), (iii) o desenvolvimento dos algoritmos e respectiva codificação, teste e integração (com os comentários pertinentes) na transformação de imagens do tipo P2, P3, P5 e P6 em imagens do tipo P1 ou P4 , e (iv) a produção de um texto em LaTeX para posterior integração no relatório da 2ª fase e respectiva compilação para PDF.
  2. Desenvolver um conjunto adicional de algoritmos para: (i) efectuar sobre imagens PNM as operações de rodar, negativo, média-vizinhos e binarização-adaptativa (opcional), em que a descrição destas operações se encontra a seguir; e (ii) procurar os objectos contidos numa imagem colorindo-os com cores diferentes, à medida que os encontra (esta operação é apenas para imagens P1 e o resultado deverá ser uma imagem P3), de acordo com as indicações dadas no fim. Do ponto de vista de interface com o utilizador, estas novas operações solicitadas devem ser integradas com as conversões iniciais no menu de opções da Fase 1, permitindo mais que uma operação em cada sessão (avaliação exclusiva de PI).
  3. Codificar os algoritmos propostos, comentando-os e documentando-os adequadamente (avaliação exclusiva de PI).
  4. Criar programas executáveis, usando o ambiente de desenvolvimento da GNU, e seleccionando o nível de optimização -O2.
  5. Preparar um conjunto de ficheiros de entrada para teste dos algoritmos/código das funções solicitadas, que permita validar, além de outras, as condições limite (avaliação exclusiva de PI).
  6. Analisar o código assembly produzido pelo gcc no processo de compilação (apenas) do código C de uma das funções pedidas (média-vizinhos, no formato P5), dedicando uma secção do relatório a esta análise, com a seguinte informação: (i) apresentação do código em assembly, claramente identificando o corpo da função e as componentes de arranque e término da função, e incluindo comentários no corpo da função semelhantes a código C; (ii) identificação dos registos e/ou células de memória onde foram alocadas as variáveis locais da função; (iii) apresentação da estrutura e conteúdo da stack frame no início da execução do corpo da função; algumas destas tarefas deverão também ser executadas durante a defesa do trabalho (avaliação exclusiva de AC).
  7. Efectuar o reverse engineering de uma função que converte uma imagem P6 noutra P6, modificada: dado o executável obter uma possível versão do código da função em C, estruturada de uma forma correcta e elegante (avaliação exclusiva de AC).
  8. Integrar e testar o produto final (da Fase 2) usando comandos da shell para (i) leitura de um ficheiro JPEG ou GIF e sua conversão para PNM, (ii) leitura de um ficheiro PNM e aplicação de uma das operações pedidas, gerando um outro ficheiro PNM e (iii) visualização da imagem usando ImageMagick (avaliação exclusiva de PI).
  9. Apresentar os resultados destas tarefas num relatório redigido conforme as regras definidas no regulamento; a estrutura do relatório deverá ser idêntica à solicitada na Fase 1 ("conter, para além do título e lista de autores, um resumo (máx. 600 caracteres), uma introdução com caracterização do problema a resolver, uma breve exposição/relato dos aspectos relevantes de cada uma das fases/tarefas, as conclusões, uma lista da bibliografia pertinente para a resolução do trabalho, e, em anexo, uma listagem do código") e deverá incluir uma versão reformulada/corrigida/completa do relatório da Fase 1.
  10. Preparar uma apresentação oral do trabalho de grupo feito até à data, (sem slides!) que não deverá ocupar mais de 5 min do tempo de defesa do trabalho.

Detalhe das operações de manipulação de imagem acima referidos (para PI):

Relativamente à procura de objectos em imagens a preto-e-branco e sua coloração, os objectos a procurar são pixeis contíguos (horizontal, vertical ou diagonalmente) com o mesmo valor, e podem ser pontos, linhas ou áreas; por exemplo, se se considerar uma imagem P1 com as letras "PI" em cima, o resultado seria uma P3 com o "P" a uma cor (azul, por exemplo) e o "I" a outra cor (vermelho, por exemplo).

Terceira fase (Fase 3)

Nesta fase final, pretende-se que as/os estudantes executem as seguintes tarefas:

  1. Corrigir e/ou completar as tarefas solicitadas nas 1ª e 2ª fases e que não foram realizadas, ou foram-no de modo menos correcto ou adequado.
  2. Complementar as tarefas das fases anteriores com novas tarefas, para avaliação exclusiva em PI, conforme descrição efectuada na página dessa disciplina e apenas para as/os estudantes que pretendam obter classificação superior a Bom.
  3. Complementar as tarefas das fases anteriores com novas tarefas, para avaliação exclusiva em AC, conforme descrição detalhada feita a seguir a esta lista de tarefas, e apenas destinada a quem pretender uma classificação Razoável ou superior.
  4. Elaboração de um texto, por cada elemento do grupo de trabalho, com uma dimensão aproximada de 1 página A4, contendo: (i) uma visão pessoal da sua participação no projecto (e o seu papel em cada um dos temas das 2 disciplinas), (ii) uma reflexão crítica sobre o projecto como um todo, e (iii) a uma autoavaliação pessoal do trabalho efectuado pelo grupo e por si, no âmbito do projecto. Este texto deverá ser enviado, em PDF, por correio electrónico, a cada um dos responsáveis das 2 disciplinas, no prazo estabelecido para entrega do relatório.
  5. Elaboração e entrega do relatório final (tarefa obrigatória para aprovação no projecto) nas seguintes condições: (i) de acordo com o modelo de referência disponibilizado no início, (ii) submetido conforme estipulado no regulamento, e (iii) contendo uma descrição de todas as fases do projecto, de um modo integrado e coerente.

A tarefa nova prevista para AC contém várias fases:

 

Topo...


Regulamento

Caracterização do Projecto

  1. O projecto consiste na realização de um trabalho prático em grupo, integrando conteúdos de 2 disciplinas, e com entrega faseada de resultados.
  2. O projecto é único para cada ano lectivo, e 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 .
  4. O projecto deverá ser submetido através do sistema de submissões de trabalhos de PI compactado em ZIP e com uma designação consoante a fase e o nº de grupo (com a indicação de "Fasen" seguido da identificação do grupo; por ex., "Fase2-3.1"); a documentação a submeter deverá constar de: (i) relatório redigido em LaTeX, segundo a estrutura e modelo definidos para os relatórios (ver em 5.), (ii) relatório compilado para PDF, (iii) ficheiro(s) com o código e/ou conjunto de testes, e (iv) eventual informação adicional.
  5. Para os estudantes apenas inscritos em AC, a informação disponibilizada na página de PI como material de apoio à produção de documentos em LaTeX é a seguinte: (i) Monografia introdutória ao LaTeX por Alberto Simões, (ii) Página HTML com o manual do LaTeX e (iii) Modelo TeX para relatórios.
  6. Os resultados do projecto serão avaliados em 3 fases distintas ao longo do semestre: nas semanas 5, 9 e 13 (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ávels 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 introdução ao trabalho de grupo estão aqui disponíveis.
  3. Cada grupo é responsável pela manutenção de um caderno de projecto contendo os dados mais pertinentes à elaboração do projecto, e que servirá de base à elaboração dos relatórios para avaliação.
  4. O Dep. Informática assegura diverso apoio extra-lectivo à preparação do projecto, nomeadamente:
    1. Postos de trabalho em laboratórios Unix (com MacOS ou Linux), quando disponíveis.
    2. Uma sala no CP-II (2.202) para trabalho em grupo, nas quartas, das 14h00 - 18h00.
    3. Uma sala no DI (0.02) para trabalho em grupo, com supervisão e apoio de um monitor (estudante do 4º ano de MCC), nas quartas, das 14h00 - 18h00.
    4. Um laboratório de Informática no DI (0.12) com 12 postos de trabalho em Linux, para trabalho em grupo, com supervisão e apoio de um monitor (estudante do 4º ano de MCC), nas quartas, das 14h00 - 18h00.

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, cuja versão electrónica deverá ser submetida com 24h de antecedência, e a versão impressa entregue aquando da defesa do trabalho; o relatório de cada uma das fases do projecto deverá incluir o relatório da fase anterior, com eventuais correções e melhorias.
    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) junto a um computador, na presença de todos os elementos do grupo, durante um tempo estimado de 20 min; em situações de ausência de um elemento, devidamente justificadas, poderá haver uma posterior defesa individual do trabalho.
  3. A avaliação do trabalho do grupo é da inteira responsabilidade das equipas de examinadores; a avaliação individual toma em consideração a opinião dos elementos do grupo, para além do desempenho individual na defesa do trabalho.
  4. O calendário para a realização das defesas dos trabalhos (ou fases do projecto) é o seguinte:
    1. Fase 1, quarta 30-Mar-05: 8h00-10h00 para os grupos inscritos no turno de sexta de manhã; 14h00-16h00 para os grupos inscritos no turno de terça; 16h00-19h00 para os grupos inscritos nos turnos de sexta à tarde.
    2. Fase 2, sexta 29-Abr-05: no horário das sessões laboratoriais; os grupos com sessões na terça defenderão o seu trabalho em conjunto com  os de sexta de manhã.
    3. Fase 3, sexta 04-Jun-05: no horário das sessões laboratoriais; os grupos com sessões na terça defenderão o seu trabalho em conjunto com  os de sexta de manhã.
  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:
  7. Para cada uma das fases de avaliação do projecto os grupos serão informados do seu desempenho, com feedback adequado para melhorarem os seus resultados, de acordo com um modelo de classificação similar.
  8. 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 pelos restantes elementos do grupo de trabalho.

Situações de excepção

  1. As dúvidas que surgirem 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 AC, preferencialmente por email. Quando necessário, o esclarecimento dessas situações far-se-á por divulgação por email (usando a mailing list com os inscritos a AC e/ou PI), com eventual inclusão de um aviso na página Web da disciplina.
  2. 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.

 

Topo...

 


Página mantida por aproenca@di.uminho.pt
Ultima Modificação: 24 Jan 2006