Exercícios de IA

Prévia do material em texto

1. 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. 
 III - O emprego das mais diversas técnicas de Inteligência Artificial permite a criação de Sistemas 
Inteligentes capazes de substituir a ação humana nas mais diversas atividades. Na robótica, o HipNav substitui 
totalmente a ação humana no planejamento e execução de implantes em seres humanos podendo ser operado via internet. 
a) As afirmações I e III estão corretas e a afirmação II está errada 
b) As afirmações II e III estão corretas e a afirmação I 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 
 
2. A característica que melhor apresenta um AGENTE DE RESOLUÇÃO DE PROBLEMAS é: 
a) Apresentar (ou retornar) uma seqüência de ações para solução de um problema como conseqüência de uma ou 
mais percepções extraídas de seu ambiente 
b) Tratam-se de agentes baseados em funções de busca e tem como exemplo um aspirador de pó que pode 
executar aleatoriamente qualquer ação, independente do estado em que se encontra. 
c) Apresentar como resultado uma árvore de busca tendo como o nó mais profundo o que apresenta a solução 
ótima do problema. 
d) É um agente de busca por soluções em extensão. Tem como principal característica seu modelo de formulação 
de problema baseado em um custo de passo igual para todas as ações. 
e) Tem em seu algoritmo uma lista linear encadeada do tipo FIFO (First in-First out) que representa seu 
algoritmo de busca pela melhor solução do problema. 
 
3. Assinale a alternativa ERRADA nas afirmações abaixo (Valor da questão: 1,0 ponto): 
a) A grande dificuldade na implementação de um modelo racional em Inteligência Artificial é a implementação da 
condição de um raciocínio lógico que resulte em um resultado exato. Para tanto o algoritmo de Aristóteles ainda é 
atual e aplicado no desenvolvimento de muitos Sistemas Inteligentes conhecidos atualmente. 
b) A Ciência cognitiva consiste na captura dos pensamentos humanos na medida em que eles se desenvolvem a partir 
de experimentos psicológicos. Esta é a base da Modelagem cognitiva que caracteriza uma das abordagens da 
Inteligência artificial � “Pensando de forma humana”. 
c) O teste de Turing consiste em uma equiparação da ação de uma máquina similar à forma humana. Para tanto o 
sistema deverá desenvolver habilidades como comunicação, armazenamento de conhecimento, raciocínio e 
aprendizado. Também deverá ter a capacidade de percepção e manipulação de objetos. 
d) A probabilidade de Bayes, ou método Bayesiano, permite a implementação matemática em algoritmos que tratam 
informações incertas resultando em condições mais próximas da esperada com uma probabilidade de erro mínima 
(raciocínio incerto). 
e) A neurociência deu uma importante contribuição à Inteligência Artificial. Alguns algoritmos foram modelados 
com base no modelo de funcionamento cerebral. Tais modelos, denominados redes-neurais, operam em duas fases, 
uma primeira de auto-aprendizado e uma segunda de aplicação propriamente dita. 
 
4. Baseado no algoritmo abaixo, assinale a alternativa com a afirmação ERRADA: 
 
a) O algoritmo é um modelo clássico de busca em árvore. Nele define-se a borda como conseqüência da 
expansão de um nó em diversos outros nós, ordenados segundo uma lista linear. 
b) Pode-se observar claramente os elementos que compõe um nó: ESTADO, NÓ-PAI, 
AÇÃO,CUSTO-DO-CAMINHO e PROFUNDIDADE. 
c) O teste de verificação do NÓ-OBJETIVO ocorre de forma seqüencial, a medida que os nós são gerados. 
d) O custo de caminho de cada nó é dado pelo CUSTO-DE-CAMINHO[nó] adicionado 1. Isto nos mostra que o 
exemplo aplica-se à um modelo de busca em extensão com custo uniforme. 
e) A PROFUNDIDADE de cada nó, denotada pela variável PROFUNDIDADE[s] é dada pela 
PROFUNDIDADE DO NÓ-PAI adicionado o valor 1. 
 
5. Para a elaboração de um algoritmo de busca em árvore, os nós são constituídos de 4 elementos (informações). Assinale 
a alternativa, onde o elemento apresentado NÃO constitui um elemento do nó em uma árvore de busca. 
a) NÓ-PAI 
b) ESTADO-INICIAL 
c) ESPAÇO DE ESTADOS 
d) CUSTO-DO-CAMINHO 
e) AÇÃO 
 
6. 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. 
 
7. 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. 
 
8. 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. 
 
 
 
 
9. 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. 
 
10. 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 diferenciama 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. 
 
11. 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. 
a) As afirmações I e III estão corretas e a afirmação II está errada 
b) As afirmações II e III estão corretas e a afirmação I 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 
 
As questões 2 e 3 abaixo são baseadas no algoritmo abaixo. O algoritmo abaixo trata da busca em profundidade limitada. 
Analise o 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 
12. 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 
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. 
 
13. Ainda com base no algoritmo apresentado acima, vale afirmar: 
f) 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. 
g) 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. 
h) O algoritmo irá retornar falha, no caso de alcançado todos os nós na profundidade limite estabelecida e não tenha 
encontrado o nó-objetivo. 
i) 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. 
j) 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. 
 
14. Com base no algoritmo : 
 função BUSCA-POR-APROFUNDAMENTO- ITERATIVO (problema)retorna uma solução ou falha 
 entradas: problema, um problema 
 para profundidade ← 0 até ∞ faça 
 resultado ← BUSCA-EM-PROFUNDIDADE-LIMITADA(problema, profundidade) 
 função BPL-RECURSIVA(nó,problema,limite)retorna uma solução ou falha/corte 
 se resultado ≠ corte então retornar resultado 
 Assinale a alternativa que contenha a afirmação ERRADA: 
 
a) Trata-se de um algoritmo de busca de aprofundamento iterativo. Este algoritmo consiste na combinação dos 
benefícios da busca em profundidade com a busca em extensão. 
b) A execução deste algoritmo é realizada por níveis de verificação. Ele aumenta gradualmente o limite de 
profundidade para cada nível de verificação até encontrar o nó-objetivo. Para cada nível o algoritmo é 
re-inicializado. 
c) Apesar dos estados serem gerados várias vezes, este fator não implica na geração de um custo computacional 
muito alto, pois, em uma árvore com o mesmo fator de ramificação em cada nível, a maior parte dos nós estão 
nos níveis inferiores. 
d) O algoritmo apresentado pode ter outras variações. Uma delas e, talvez a mais eficiente e completa, seria a 
combinação do algoritmo de busca em profundidade para a re-inicialização de cada nível combinado com o 
algoritmo de busca em profundidade limitada, resultando assim, além de um algoritmo ótimo e completo, com 
um mínimo de custo computacional (complexidade em espaço e memória). 
e) A aplicação do algoritmo de busca de aprofundamento iterativo em uma combinação de busca em 
profundidade com a de busca uniforme resultaria em um algoritmo ótimo e completo com uma complexidade 
de tempo e espaço aceitáveis. 
 
15. A função de avaliação em um algoritmo deve ser estabelecida com base: 
a) Em nenhum critério relacionado ao tipo de algoritmo, ou seja, algoritmos de busca sem informação podem 
utilizar esta função para uma avaliação final do custo de caminho resultante de sua aplicação. 
b) Deve expressar um critério para busca baseado no estado inicial e final da árvore de busca ou do grafo de 
busca. 
c) No custo do caminho do nó expandido, pois, expressa a distância percorrida do estado inicial até o nó em 
verificação. 
d) Na ação à ser tomada a partir da expansão de um determinado nó. Esta função deverá ser decisiva na busca 
pela solução ótima e com menor profundidade. 
e) Em uma estimativa da distância do nó expandido até o nó-objetivo. Certamente, uma função de avaliação bem 
elaborada conduz um algoritmo de busca pela melhor escolha em uma marcha direta parao nó-objetivo. 
 
16. A função de avaliação em um algoritmo de busca gulosa consiste em: 
a) Uma função heurística, h(n) que representa a menor distância em linha reta, hDLR, entre o nó e o nó-objetivo . 
b) Uma função assintótica, denotada por h(n), que representa o custo computacional mínimo para execução do 
algoritmo. 
c) Uma função genérica que representa o custo do nó expandido adicionado o custo de cada passo para se chegar 
ao nó-objetivo. 
d) Uma função exponencial que depende do número de expansões ocasionadas no algoritmo e do número de 
ramificações de cada nó. Também é denotada de O( . ). 
e) Uma função que representa a distância entre dois estados diferentes do espaço de estado. Sua eficiência na 
busca pela melhor escolha é duvidosa devido a possibilidade de existirem diversos caminhos que podem levar 
ao nó-objetivo. 
 
 
17. Uma heurística h(n) é dita admissível se, e somente se: 
a) Possui um comportamento exponencial em relação ao custo de caminho; 
b) Calcula a soma de todos os custos de passo para chegar do nó em questão ao objetivo; 
c) Nunca superestime o custo para alcançar o objetivo. 
d) Nunca subestime o custo para alcançar o objetivo. 
e) Resulta sempre no custo ótimo para alcançar o objetivo. 
 
18. Problemas de locomoção entre cidades podem ser resolvidos por meio de técnicas de busca. 
Utilizando as técnicas de busca pela melhor escolha – gulosa e A* 
a) Encontrar o caminho para se locomover do estado A até o estado B. 
b) Avaliar o custo do caminho considerando os seguintes itens: 
i. número de estados visitados 
ii. distancia entre os estados 
iii. tempo de deslocamento entre estados (considerar 1h para percorrer cada 100 km) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
DISTANCIAS ENTRE CADA PONTO E O OBJETIVO (EM KM) 
A 660 5 410 
1 520 6 380 
2 510 7 210 
3 550 8 220 
4 390 9 240 
 
 
 
A 
3 
1 
2 5 
6 
4 
8 7 
9 
B 
290 
310 
270 260 170 
190 
160 
290 320 
270 
290 
220 
270 
290 
250 310 
240 
270 
210