20211-A2- Projeto E Analise DE Algoritmos-1ECP39A- Miguel Figueiredo AIA PDF

Preview

Summary

PAA...

Description

ATIVIDADE INDIVIDUAL AVALIATIVA CURSO:

DISCIPLINA:

Engenharia e Ciência da Computação

Projeto e Análise de Algoritmos

ASSINATURA:

NOME:

DATA:

AIA:

TURMA

MATRÍCULA

A2

1ª Atividade (4,0 pontos; Competência: Conhecimento; Ref.: Enade 2017) A falta de uso do parágrafo na resposta implica na perda de 10% do valor da questão. A falta de uso correto de pontuações e vírgulas, quando se aplicarem, implica na perda de 10% do valor da questão. A falta de uso dos mesmos índices do enunciado e a falta da mesma quantidade de itens na resposta, implicam na perda de pelo menos 10% da questão.

Os algoritmos para busca de partes de um texto (substring) em geral procuram pela ocorrência de uma "palavra" W dentro de um "texto" S empregando a simples técnica de que quando aparece uma diferença, a palavra tem em si a informação necessária para determinar onde começar a próxima comparação. Um dos algoritmos mais conhecido é o KMP (Knuth-Morris-Pratt). (Cormen, T.H., Introdução aos Algoritmos). a) Elabore um programa em qualquer linguagem de programação que seja capaz de realizar a identificação de um padrão W dentro de um texto S, com complexidade O(n) no pior caso. b) A partir da cadeia de caracteres textuais ABACAABACCABACABAABB demonstre a pesquise do padrão ABACAB utilizando o método KMP, informando quantas comparações foram realizadas pelo método. O enunciado abaixo se refere às questões 2 e 3 a seguir. (Cormen, T.H., Introdução aos Algoritmos) Os analistas de sistemas de uma empresa de software estão trabalhando em melhorias no seu principal produto que é um editor de texto na língua portuguesa. Uma das melhorias desejadas é implantação do recurso “Sugestão Automática”, onde a partir de uma falha na busca, em um dicionário de tipo bucket[0..m]{(, ; , ..., )}, por uma palavra digitada pelo usuário no corpo do texto, seja sugerido um termo mais semelhante aos dos constantes no dicionário. 2ª Atividade (2,5 pontos; Competência: Conhecimento; Ref.: Enade 2008) A falta de uso do parágrafo na resposta implica na perda de 10% do valor da questão. A falta de uso correto de pontuações e vírgulas, quando se aplicarem, implica na perda de 10% do valor da questão. A falta de uso dos mesmos índices do enunciado e a falta da mesma quantidade de itens na resposta, implicam na perda de pelo menos 10% da questão.

Para atender a demanda dos analistas, elabore um programa em qualquer linguagem de programação para comparação de duas sequencias de caracteres, uma digitada pelo usuário T e outra qualquer presente no dicionário S, que retorne a quantidade de substituições, inserções ou exclusões necessárias para que T fique igual a S.

ATIVIDADE INDIVIDUAL AVALIATIVA CURSO:

DISCIPLINA:

Engenharia e Ciência da Computação

Projeto e Análise de Algoritmos

ASSINATURA:

NOME:

DATA:

AIA:

TURMA

MATRÍCULA

A2

3ª Atividade (1,5 pontos; Competência: Conhecimento; Ref.: Enade 2008) A falta de uso do parágrafo na resposta implica na perda de 10% do valor da questão. A falta de uso correto de pontuações e vírgulas, quando se aplicarem, implica na perda de 10% do valor da questão. A falta de uso dos mesmos índices do enunciado e a falta da mesma quantidade de itens na resposta, implicam na perda de pelo menos 10% da questão.

Para a mesma aplicação acima, demonstre os passos da execução do algoritmo para comparação de sequencias de caracteres, baseado no cálculo da distância de Levenshtein, entre a expressão digitada pelo usuário “COLLERES” e as expressões do mesmo bucket presentes no dicionário abaixo, e indique a melhor opção a ser sugerida. Bucket CO CO CO

Chave 0 1 2

Valor COLHER COLHERES COOLER

4ª Atividade (1,0 ponto; Competência: Conhecimento; Ref.: Enade 2005) Um projetista de banco de dados hierárquico, em função das mudanças no perfil das aplicações móveis de sua corporação, deseja rever as estruturas de dados internas do modelo e dos algoritmos de busca já implementados. Para isso ele decidiu a utilização de dicionários armazenados na forma de Tries, em detrimento de outras abordagens. (Toscani, L.V., Complexidade de Algoritmos). Em relação a decisão do projetista analise as afirmativas abaixo e julgue-as assinalando com (V) quando verdadeira e (F) quando falsa. Justifique seus julgamentos. I. II. III. IV.

A escolha foi equivocada, pois as árvores de busca binária seriam mais eficientes no pior caso. A escolha foi acertada, pois, no pior caso, a quantidade de comparações pela busca de uma chave em uma Trie seria o tamanho da mesma. A escolha foi indiferente, pois a utilização de tabelas Hash, por exemplo, teriam vantagens adicionais como colisões para chave diferentes. A escolha foi acertada, pois, há colisões entre chaves diferentes em uma Trie.

ATIVIDADE INDIVIDUAL AVALIATIVA CURSO:

DISCIPLINA:

Engenharia e Ciência da Computação

Projeto e Análise de Algoritmos

ASSINATURA:

NOME:

DATA:

AIA:

TURMA

MATRÍCULA

A2

5ª Atividade (1,0 ponto; Competência: Conhecimento; Ref.: Enade 2017) Em uma empresa de desenvolvimento de sistemas, um programador foi instruído a adotar em seus projetos, uma função de similaridade fonética de ampla utilização baseada no algoritmo SOUNDEX padronizado para a língua inglesa. Durante os testes foram avaliadas algumas palavras e obtidos seus respectivos códigos SOUNDEX conforme abaixo: Palavra Calvario Calvicie Nicolau Nicholas Melindrado Melindrarem

Código SOUNDEX C416 C412 N242 N240 N453 N453

Em função dos resultados alcançados, analise as afirmativas abaixo e julgue-as assinalando com (V) quando verdadeira e (F) quando falsa. Justifique seus julgamentos. I. II. III. IV. V.

O algoritmo não está correto, pois há SOMENTE três códigos SOUNDEX errados. O algoritmo não está correto, e depois de consertado, teria no pior caso complexidade O(n). O algoritmo está incorreto apenas no que tange a escolha do prefixo do código. O algoritmo não possui erros, e no pior caso possui complexidade O(n2). A diferença entre as partes numéricas de dois códigos com mesmo prefixo, indica o quanto semelhantes as palavras são foneticamente, onde 0 (zero) indicaria a maior similaridade....