Análise e Projeto de Algoritmos (1S/2018)

Informações Importantes

Nesta seção você encontra: o horário das aulas e do atendimento extraclasse; e a planilha de notas. A forma de calcular sua média final, a bibliografia adotada e outros detalhes estão disponíveis no Portal do Aluno.

horário das aulas

Quinta-feira: das 08h20 às 10h00.
Sexta-feira: das 10h20 às 12h00.

Horário de Atendimento

Sexta-feira: das 13h50 às 16h20,

Sexta-feira: das 13h50 às 16h20, no DAINF.

atividade prática supervisionada

Este semestre, a atividade prática supervisionada consiste na construção de um corretor ortográfico para a Língua Portuguesa.

Primeira etapa: montar um dicionário de palavras da Língua Portuguesa em txt. Esta lista pode ser obtida a partir de dicionários abertos da língua portuguesa e deve ser o mais completa possível. Para que vocês tenham uma noção de quão grande deve ser esse dicionário, o Aurélio tem em torno de 435 mil palavras (e os verbos são apresentados no infinitivo, sem suas conjugações). Prazo para obter o dicionário: 27 de abril.

Segunda etapa: desenvolver um algoritmo que, dada uma cadeia de caracteres, pressupondo que esta cadeia seja uma palavra da língua portuguesa, diga se a mesma está correta ou apresente uma correção ortográfica para a palavra, buscando no dicionário como seria a escrita correta da mesma. O algoritmo deve ser implementado e exaustivamente testado. Prazo para apresentar a implementação: 11 de maio.

Terceira etapa: faça uma análise de complexidade do seu algoritmo e apresente um relatório técnico desta análise. Faça testes no software e inclua no seu relatório técnico tabelas e gráficos que mostrem a taxa de acerto do seu software e o tempo que ele demora para responder (inclua a configuração da máquina em que está rodando: hardware, sistema operacional e linguagem de implementação). Faça uma discussão comparando o resultado teórico obtido na análise de complexidade e o que foi observado na prática. Prazo de entrega do relatório: 1 de junho.

Quarta etapa: em breve.

Quinta etapa: em breve.

Para Estudo

Consulte o material do Professor Paulo Feofiloff (UPS), disponível aqui .

Faça exercícios do livro Introduction to Algorithms, de Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

notas de aula

Datas importantes

26/04/2018: P1
27/04/2018: entrega da primeira etapa da APS (1 ponto).
11/05/2018: entrega da segunda etapa da APS (2 pontos).
18/05/10/2018: R1
01/06/2018: entrega da terceira etapa da APS (2 pontos).
15/06/2018: entrega da quarta etapa da APS (2.5 pontos).
21/06/2018: P2
29/06/2018: entrega da quinta etapa da APS (2.5 pontos).
05/07/2018: R2