Módulo Complementar II - Exercícios

Prévia do material em texto

29/03/2015 online.unip.br/imprimir/imprimirconteudo
http://online.unip.br/imprimir/imprimirconteudo 1/5
 Exercícios Extra
Exercício 1:
O processo de expansão em uma árvore de busca consiste em:
A ­ Ocorre após a verificação do NÓ e consiste na geração do ESPAÇO DE ESTADOS que são uma
seqüência de nós proveniente do NÓ­PAI. Cada nó deste ESPAÇO DE ESTADOS é representado por cinco
elementos que o caracterizam. 
B ­ Ocorre antes da verificação NÓ e consiste na geração de um NÓ­FOLHA a partir do NÒ verificado e
assim por diante até chegar na profundidade máxima da ÁRVORE­DE­BUSCA. 
C ­ Ocorre após a verificação do NÓ e consiste na geração da borda que é uma seqüência de nós
proveniente do NÓ­PAI. Cada nó desta borda é conhecido por NÓ­FOLHA. 
D ­ Ocorre durante a verificação do NÓ e consiste na execução do algoritmo do AGENTE­DE­RESOLUÇÃO­
DE­PROBLEMAS, o qual resulta em uma seqüência de ações. 
E ­ Ocorre após a verificação do NÓ e consiste na geração de uma seqüência de NÓS dispostos em uma
FILA do tipo PILHA, independente de qualquer estratégia de busca pré­estabelecida no algoritmo. 
Comentários:
Essa disciplina não é ED ou você não fez comentários
Exercício 2:
São  elementos  que devem  constituir,  de  forma  completa,  a  formulação de um
problema:
A ­ Custo de passo, teste­de­objetivo, percepção, sensores e estado­final. 
B ­ Espaço de estados, estado­inicial,função sucessor, teste­de­objetivo e custo de caminho. 
C ­ Função sucessor, problema, espaço de estados, custo de passo, otimização e completeza. 
D ­ Função O(.), espaço de estados, função agente de resolução de problemas, custo de passo e custo de
caminho. 
E ­ Estado inicial, mapa de estados, objetivo, custo de passo e função de expansão. 
Comentários:
Essa disciplina não é ED ou você não fez comentários
Exercício 3:
São medidas de desempenho de um algoritmo de busca:
A ­ Completeza, otimização, complexidade de tempo e complexidade de espaço. 
B ­ Tempo de execução, ocupação de memória, dimensões do algoritmo, quantidade de elementos do
espaço de estados. 
C ­ Existência ou não de informações, estratégia de busca, modelamento da árvore de busca e
distribuição dos NÒS­PAIS. 
D ­ Modelagem da árvore de busca, distribuição dos NÓS na árvore de busca, intervalo de tempo para
expansão de um NÓ e desempenho do algoritmo na verificação do NÓ­OBJETIVO. 
E ­ NP­Completeza, função O( . ), desempenho em tempo e ocupação de memória para execução do
algoritmo. 
Comentários:
29/03/2015 online.unip.br/imprimir/imprimirconteudo
http://online.unip.br/imprimir/imprimirconteudo 2/5
Essa disciplina não é ED ou você não fez comentários
Exercício 4:
Assinale  a  alternativa  ERRADA  com  relação  aos  algoritmos  de  busca  sem
informação:
A ­ Um algoritmo de busca uniforme é um algoritmo ótimo. 
B ­ Um algoritmo de busca em extensão será ótimo se seu custo de caminho for sempre crescente em
relação aos seus níveis de expansão. 
C ­ Um algoritmo de busca em profundidade pode não ser um algoritmo ótimo e completo, porém,
apresenta como principal vantagem a economia de memória e conseqüente tempo de execução. 
D ­ A opção pelo desenvolvimento de um algoritmo de busca em profundidade limitada está baseada no
conhecimento prévio do problema ao ponto de permitir sua limitação com relação ao número de
expansões. 
E ­ A busca em profundidade sempre será completa, pois, sua estrutura permite, sempre, a obtenção de
um caminho que represente a solução do problema. 
Comentários:
Essa disciplina não é ED ou você não fez comentários
Exercício 5:
 
A diferenciação entre os vários algoritmos de busca é baseada:
A ­   Na sua complexidade   de tempo e espaço, profundidade, fator de ramificação e completeza.   
B ­ Na existência ou não de informações que diferenciam a verificação ou não de um determinado nó. 
C ­ Na estratégia que determina a forma em que os nós serão verificados e expandidos. Esta estratégia
pode ser baseadas ou não em informações prévias contidas nestes nós (com informação ou sem
informação). 
D ­ Não existe nenhuma diferenciação entre os algoritmos, somente seus valores de desempenho são
diferenciados. 
E ­ Em uma estratégia ótima para verificação e expansão da árvore de busca. Com base nesta estratégia
que se estabelece os diversos tipos de algoritmos de busca.  
Comentários:
Essa disciplina não é ED ou você não fez comentários
Exercício 6:
Baseada nas três informações abaixo assinale a alternativa correspondente:
 
I.  Um  algoritmo  de  busca  em  profundidade  limitada  possui  nós  sem
sucessores, pois, estão no limite estabelecido na definição do algoritmo.
Esta  abordagem  pode  adicionar  um  fator  de  incompleteza.  Isto  só
ocorrerá    quando  l  <  p  ,  ou  seja,  a  profundidade  para  o  limite
estabelecido é menor que a profundidade do nó objetivo mais   raso.
II.  A  busca  em  profundidade  limitada  será  ótima  para  l  >  p.  O
comportamento de seu algoritmo não tem nenhuma semelhança com um
algoritmo de busca em profundidade genérico.
III.   O algoritmo de busca em profundidade limitada  pode ser implementado
como  uma  modificação  simples  do            algoritmo  geral  de  busca  em
árvore.  
29/03/2015 online.unip.br/imprimir/imprimirconteudo
http://online.unip.br/imprimir/imprimirconteudo 3/5
 
A ­ As afirmações I e III estão corretas e a afirmação II está errada 
B ­ As afirmações I e III estão corretas e a afirmação II está errada 
C ­ As afirmações I e II estão corretas e a afirmação III está errada 
D ­ Todas as afirmações estão erradas 
E ­ Somente a afirmação III está correta 
Comentários:
Essa disciplina não é ED ou você não fez comentários
Exercício 7:
Baseado no algoritmo abaixo:
 
 
            função BUSCA­EM­PROFUNDIDADE­ LIMITADA (problema,  limite)retorna
uma solução ou falha/corte
                  retornar BPL­RECURSIVA(CRIAR­NÓ(ESTADO­INICIAL[problema]),
problema, limite)
 
                        função  BPL­RECURSIVA(nó,problema,limite)retorna  uma  solução  ou
falha/corte
                  corte_ocorreu?  falso
                                    se  TESTAR­OBJETIVO[problema](ESTADO[nó]) então  retornar
SOLUÇÃO(nó)
                  senão se PROFUNDIDADE[nó] = limite então retornar corte
                  senão para cada sucessor em EXPANDIR(nó,problema) faça
                        resultado  BPL­RECURSIVA(sucessor,problema,limite)
                        se resultado = corte então corte_ocorreu?  verdadeiro
                        senão se resultado  falha então retornar  resultado
                  se corte_ocorreu? então retornar corte senão retornar falha
 Assinale a alternativa que representa a afirmação errada com base no algoritmo acima:
 
 
A ­ Um algoritmo de busca em profundidade limitada se difere de um algoritmo de busca em profundidade
na definição de uma variável que represente o limite, ou profundidade máxima para o algoritmo. Caso
esta variável seja menor que o limite máximo estabelecido ela pode aplicar a expansão como se faria em
um algoritmo de busca em profundidade normal. 
B ­ A definição de uma função recursiva (função BPL­RECURSIVA) é feita com o propósito de economizar
memória, este conceito de função recursiva só é passível de aplicação em algoritmos de Busca em
29/03/2015 online.unip.br/imprimir/imprimirconteudo
http://online.unip.br/imprimir/imprimirconteudo 4/5
Profundidade Limitada. 
C ­ A função BUSCA­EM­PROFUNDIDADE­LIMITADA poderá resultar em uma solução que corresponde o
caminho do nó raiz até o nó­objetivo ou uma falha. Esta falha pode ser resultante da profundidade do
limite estabelecido onde não se encontrou o nó­objetivo ou da finalização do processo sem encontrar o
nó­objetivo como se fosse um algoritmo de busca em profundidade qualquer. 
D ­ Apesar de se tratar de uma variante da busca em profundidade,o algoritmo de Busca em
Profundidade Limitada não soluciona o problema da incompleteza do algoritmo de Busca em
Profundidade. Ele ainda pode adicionar mais um foco de incompleteza se o dimensionamento do limite de
profundidade for inferior à profundidade do nó­objetivo mais raso. 
E ­ Assim como o algoritmo de Busca em Profundidade, a Busca em Profundidade Limitada também não
será ótima, uma vez que, havendo mais de um nó­objetivo, nada irá assegurar que o nó encontrado é o
nó­objetivo com profundidade mais rasa. Considera­se nesta afirmação o modelo similar de expansão nos
dois modelos de algoritmos. 
Comentários:
Essa disciplina não é ED ou você não fez comentários
Exercício 8:
Baseadas no algoritmo abaixo:
 
            função BUSCA­EM­PROFUNDIDADE­ LIMITADA (problema,  limite)retorna
uma solução ou falha/corte
                  retornar BPL­RECURSIVA(CRIAR­NÓ(ESTADO­INICIAL[problema]),
problema, limite)
 
                        função  BPL­RECURSIVA(nó,problema,limite)retorna  uma  solução  ou
falha/corte
                  corte_ocorreu?  falso
                                    se  TESTAR­OBJETIVO[problema](ESTADO[nó]) então  retornar
SOLUÇÃO(nó)
                  senão se PROFUNDIDADE[nó] = limite então retornar corte
                  senão para cada sucessor em EXPANDIR(nó,problema) faça
                        resultado  BPL­RECURSIVA(sucessor,problema,limite)
                        se resultado = corte então corte_ocorreu?  verdadeiro
                        senão se resultado  falha então retornar  resultado
                  se corte_ocorreu? então retornar corte senão retornar falha
 
Com base no algoritmo apresentado acima, é errado afirmar
A ­ O estabelecimento de um limite de profundidade nada mais é do que associar ao modelo um
procedimento de finalização do algoritmo mesmo que todas as soluções viáveis ainda não tenham sido
exploradas. Tal procedimento assegura que, pelo menos, uma solução será apresentada. 
B ­ A definição de uma função recursiva tem como objetivo a economia de memória pela expansão de
apenas um nó sucessor por vez. Neste caso, cada nó parcialmente expandido memoriza o sucessor que
deve gerar em seguida. 
C ­ O algoritmo irá retornar falha, no caso de alcançado todos os nós na profundidade limite estabelecida
29/03/2015 online.unip.br/imprimir/imprimirconteudo
http://online.unip.br/imprimir/imprimirconteudo 5/5
e não tenha encontrado o nó­objetivo. 
D ­ O algoritmo irá retornar corte, no caso de alcançado todos os nós na profundidade limite estabelecida
e não tenha encontrado o nó­objetivo. 
E ­ A variável que estabelece a ocorrência do corte no algoritmo é denominada corte_ocorreu? e, a ela é
atribuída o valor lógico verdadeiro (ou true) no caso de ocorrência do limite de profundidade estabelecido
para o algoritmo. 
Comentários:
Essa disciplina não é ED ou você não fez comentários
Exercício 9:
Dentre as definições a seguir, conceitos de computação evolutiva da Inteligência Artificial, qual delas é incorreta?
A ­ A computação evolutiva deve ser entendida como um conjunto de técnicas e procedimentos genéricos
e adaptáveis, a serem aplicados na solução de problemas complexos, para os quais outras técnicas
conhecidas são ineficazes ou nem sequer são aplicáveis. 
B ­ Os sistemas baseados em computação evolutiva mantêm uma população de soluções potenciais,
aplicam processos de seleção baseados na adaptação de um individuo e também empregam outros
operadores genéticos." 
C ­ A roleta é um método de seleção no qual se atribui a cada individuo de uma população uma
probabilidade de passar para a próxima geração proporcional ao seu fit ness , medido em relação a
somatória do  fitness  de todos os indivíduos da população. Assim, algoritmos genéticos são métodos de
busca puramente aleatórios. 
D ­ Os algoritmos genéticos empregam uma terminologia originada da teoria da evolução natural e da
genética. Um indivíduo da população é representado por um único cromossomo, o qual contém a
codificação (genótipo) de uma possível solução do problema (fenótipo). 
E ­ O processo de evolução executado por um algoritmo genético corresponde a um procedimento de
busca em um espaço de soluções potenciais para o problema.   
Comentários:
Essa disciplina não é ED ou você não fez comentários