O que é um Projeto? | As Equipes | Data de Entrega | Descrição dos Projetos | Produtos | Apresentações | Acompanhamento | Avaliação | Sugestão de Plano de Trabalho
O projeto é um trabalho mais elaborado, e que exigirá de você e da equipe um conhecimento sobre diversos assuntos do curso, além de outras habilidades. Todo projeto envolverá uma implementação da solução de problemas que envolve conhecimentos de algoritmos e estruturas de dados.
Para a Turma IA (45 alunos): serão formadas 11 equipes, sendo 10 equipes com um máximo de 4 componentes e, caso necessário, 1 equipe com um máximo de 5 componentes.
Para a Turma I2 (52 alunos): serão formadas 13 equipes com um máximo de quatro componentes cada.
A composição de cada equipe será definida por sorteio. A alocação de projetos a equipes será discutida em sala de aula. Depois de composta as equipes, estas poderão escolher os seus projetos. Em caso de conflito, as equipes tentarão negocioar uma solução. Em caso de falha da negociação os projetos conflitantes serão sorteados.
A data de entrega é o dia da apresentação do seu projeto. As apresentações ocorrerão na semana de 5 a 9 de julho de 1999, no horário da aula e/ou em horário a ser divulgado posteriormente.
Passamos a descrever abaixo cada um dos projetos. Todas as implementações devem ser feitas em C.
O objetivo neste projeto é estudar algoritmos de compressão. Tais algoritmos possuem várias aplicações e têm como objetivo reduzir o espaço ocupado por dados em dispositivos de armazenamento. Um dos programas mais conhecidos no nosso dia-a-dia e que aplica um algoritmos de compactação é o Winzip (gzip no UNIX também).
Neste projeto você deverá estudar o tema; citar exemplos de algoritmos de compressão e suas aplicações; e desenvolver um programa para realizar a compressão de textos. Compare o seu programa com outros programas de compressão existentes e descreva em detalhe o algoritmo de compressão utilizado.
O objetivo deste projeto é desenvolver algoritmos para a computação de uma votação eletrônica. Você deverá iniciar definindo o seu sistema de votação eletrônica, que deverá ser formado por um conjunto de urnas eletrônicas e um processo de totalização. Como resultado você deverá implementar um programa para a urna eletrônica e um programa totalizador que lê as urnas e totaliza o resultado de uma eleição. Use como modelo as eleições da UFPE para reitor de 1999 (http://www.di.ufpe.br/~eleicao99).
Um dos problemas mais difíceis enfrentados por empresas do setor industrial e comercial é de otimizar suas compras de modo a otimizar os seus resultados. Basicamente, a empresa tem um conjunto de fornecedores e uma lista de compra a serem comprados destes fornecedores. Sua tarefa é definir um algoritmos que otimize o preço total da lista de compra, levando em consideração os melhores preços e condições de pagamento.
Um problema comum enfrentado pelo Departamento de Informática (DI) todos os semestres é alocação das salas de aula. Dado um conjunto de disciplinas, uma alocação de horários, e uma quantidade de alunos por turma, gostaríamos de fazer de forma automática (ou semi-automática) a alocação de salas de aula para cada turma. Considere que cada sala tem capacidade definida. Sua tarefa é definir e implementar um programa que faça esta alocação. Use o DI como modelo. A Secretaria de Graduação poderá esclarecer algum requisito que não esteja claro.
Este projeto consiste na implementação de um programa que oriente um entregador de remédios (motoqueiro) sobre a melhor rota para entrega de remédios. Dada um conjunto de entregas que devem ser feitas em pontos distintos, a sua implementação deve sugerir uma rota que otimize o tempo e o combustível gastos. Cada ponto de entrega tem uma distância fixa do ponto de distribuição. Entenda o problema; faça a sua modelagem através de uma estrutura de dados adequada; e defina e implemente os algoritmos que vão auxiliar o motoqueiro no seu dia-a-dia.
Agendar reuniões entre um grupo de pessoas é uma tarefa difícil, principalmente se estas pessoas têm uma agenda ocupada. A sua tarefa é, dado um conjunto de pessoas e suas agendas, definir e implementar um algoritmo que agende uma reunião para este grupo de modo a otimizar a participação (isto é, que se tenha uma reunião com o maior númento de pessoas presentes).
Geradores de números aleatórios são usados em várias aplicações e em diversas áreas. A sua tarefa será estudar os algoritmos de números aleatórios, citando vários exemplos de utilização dos mesmos; fazer a implementação desses algoritmos; e fazer uma comparação entre eles.
Uma das aplicações que mais cresce hoje na Internet é o comércio eletrônico. Uma das maiores preocupações nesta área é questão de segurança, pois o processo envolve a transferência eletrônica de fundos. Várias soluções para esta questão são dadas em termos de criptografia, isto é, a codificação de textos de modo a assegurar a sua confidencialidade. Neste projeto você deverá estudar o tema e os principais algoritmos criptográficos utilizados hoje na rede, citando em que aplicações eles são usados. Faça a implementação de alguns deles. Outra área onde a criptografia é usada é a codificação de senhas de acesso a sistemas computacionais. Estude o processo criptográfico das senhas de login do sistema operacional UNIX e implemente o algoritmo correspondente.
Quando você usa compila um programa C, o primeiro passo no processo de compilação é o de análise léxica e sintática do programa-fonte. O compilador ler o texto (basicamente uma cadeia de caracteres) e agrupa estes caracteres em símbolos (tokens) segundo as regras de formação léxica da linguagem. Em seguida tais símbolos são agrupados em frases segundo as regras de formação sintática da linguagem. Sua tarefa neste projeto é definir e implementar um analisador sintático (parser) para um pequeno subconjunto da linguagem C formado por expressões aritméticas e pelo comando de atribuição. Inicie definindo a gramática deste subconjunto, para em seguida implementar alguma estratégia de parsing (top-down ou bottom-up).
B-trees é um tipo especial de árvore balanceada que permite o acesso eficiente grandes estruturas de dados (grande quantidade de nós). Sua tarefa neste projeto será elaborar um tutorial sobre B-trees. Inicie estudando o assunto e definindo detalhadamente este tipo de dados e seus algoritmos; em seguida implemente estes algoritmos. Cite vários exemplos reais de utilização de B-trees. O tutorial deverá ser composto por um texto sobre o assunto, uma apresentação (em PowerPoint) animada (que inclua a execução dos algoritmos implementados). A idéia central é que uma pessoa que queira saber o que são B-trees possa aprender unicamente pelo acesso ao material produzido pelo projeto (sem a necessidade de recorrer a um professor ou instrutor).
Dependendo do projeto, os seus produtos poderão variar, mas espera-se que cada projeto apresente, no mínimo os seguintes produtos:
O relatório deve ser entregue em papel. A apresentação e os programas implementados, assim como o relatório, devem ser entregues em disquete que devem acompanhar o relatório.
Todos os projetos serão apresentados em sala de aula. Esta apresentação será composta por uma apresentação oral do projeto e uma demonstração das implementações realizadas (veja Data de Entrega).
Cada equipe terá 30 min para apresentação e demonstração do projeto.
O professor Hermano estará disponível para tirar dúvidas sobre o projeto e verificar se a equipe está no caminho certo. As reuniões poderão ser realizadas no horário das aulas. Agende a reunião via e-mail para hermano@di.ufpe.br. Não deixe para tirar dúvidas na última hora, procure verificar se você está no caminho correto desde o início.
Os monitores também estarão disponíveis para auxiliar na implementação das soluções conforme o horário já estabelecido.
A avaliação final (nota) do projeto será atribuída em função dos seguintes itens:
A seguir você encontrará uma sugestão de roteiro de trabalho para execução do seu projeto. Ele foi feito no sentido de organizar os trabalhos em equipe e aumentar a produtividade e a qualidade do resultado obtido. Poderá ser adaptado conforme a necessidade e características de cada projeto/equipe.
- Avaliação Inicial: leitura do enunciado, estudo da teoria (individual)
- Análise: requisitos/entendimento (equipe)
- Especificação: esqueleto do código (equipe)
- Implementação: codificação (individual)
- Integração: integrar os programas construídos separadamente, pode requerer voltar ao passo anterior (equipe)
- Validação: testes finais da solução (equipe)
- Documentação: escrever o relatório e preparar a apresentação, fazer parcialmente durante o projeto (grupo e individual)
- Revisão: revisão geral do projeto (grupo e individual)