Listas de Exercícios de Inteligência Artificial - P1 E P2 - FEI

Prévia do material em texto

1. Em relação às técnicas de Inteligência Artificial vistas até então no curso, avalie as 
afirmações abaixo: 
 
a) Os mecanismos de busca em largura e em profundidade não utilizam informações específicas 
do problema, além daquelas fornecidas sobre a definição do mesmo, para expansão de nós em 
uma estrutura de dados em árvore. 
b) Os mecanismos de busca baseados em heurística são sempre ótimos, ou seja, encontram a 
melhor solução sempre que existirem soluções distintas para o problema. 
c) A inferência de uma hipótese (ou regra geral) a partir de exemplos (ou amostras) particulares 
(ou de treinamento) é um paradigma de aprendizado artificial denominado de aprendizado 
supervisionado ou aprendizado indutivo. 
 
É correto o que se afirma em 
 
( ) a, apenas. 
( ) b, apenas. 
( ) a e b, apenas. 
( ) a e c, apenas. 
( ) a, b e c. 
 
Justifique, com as suas palavras e sucintamente, a sua resposta. 
2. Seja o problema do Caixeiro-Viajante. A meta é encontrar a rota mais curta para visitar cada 
cidade exatamente uma vez. Suponha que as cidades a serem visitadas e as distâncias entre 
elas sejam aquelas mostradas na tabela abaixo. 
 
 
Considere que o vendedor irá iniciar a sua viagem em São Paulo e deverá ir depois 
necessariamente ou para o Rio de Janeiro ou para Belo Horizonte. Nesse cenário, 
 
a) Construa uma árvore de decisão do estado inicial até o nível de profundidade do objetivo; 
b) Ache a sequência de nós para o algoritmo de busca “Melhor Escolha”. 
 
São Paulo Rio de Janeiro Belo Horizonte Brasilia Salvador
São Paulo - 429 586 1015 1954
Rio de Janeiro 429 - 434 1145 1720
Belo Horizonte 586 434 - 716 1354
Brasilia 1015 1145 716 - 1529
Salvador 1954 1720 1354 1529 -
3. Resolva, por árvore de decisão, o problema de classificação ilustrado abaixo. O ponto (6, 7) 
seria classificado como ‘o’ ou ‘+’? 
 
 
4. Na edição de Novembro de 2009 da revista Quatro Rodas, foi publicada uma reportagem que 
comparava os seguintes carros (“Os folgados da rua”): Sandero (Renault), Fox (Volks) e Agile 
(GM). A tabela abaixo traduz esse comparativo em notas de 0 a 1. Quais carros, dos três 
descritos na tabela abaixo, são mais similares às suas preferências de compra? 
 
Sandero (Renault) Fox (Volks) Agile (GM)
Direcao, Freio e Suspensao 0.7 0.8 0.8
Motor e Cambio 0.7 0.9 0.8
Carroceria 0.8 0.9 0.8
Conforto a bordo 0.8 0.8 0.8
Seguranca 0.7 0.8 0.6
Seu Bolso 0.8 0.6 0.9
5. Considere que a figura abaixo corresponde a um grafo de cidades, cujos números ao lado 
dos arcos representam as distâncias percorridas entre as cidades origem (nó pai) e destino (nó 
filho) e os números em negrito ao lado dos nós descrevem as distâncias em linha reta dessas 
cidades até a cidade z. Neste contexto, há 7 (sete) cidades e a movimentação de uma cidade 
para outra tem custo equivalente à distância percorrida entre elas. 
 
 
Por meio de uma estrutura em árvore de decisão, procure o menor trajeto, ou uma alternativa 
aceitável, entre a cidade a (início) e a cidade z (fim), tomando como base uma função heurística 
admissível para o problema em questão. 
 
7 
6. Sejam as representações gráficas do problema da Torre de Hanói apresentadas nas figuras 
abaixo. Esse problema consiste em passar todos os discos de um pino para outro qualquer, 
usando um dos pinos como auxiliar, de maneira que um disco maior nunca fique em cima de 
outro menor em todos os movimentos. Defina uma representação sintática para modelagem 
deste problema e mostre que tal representação é válida para descrever os estados inicial e final 
mostrados nas Figuras 1 e 2, respectivamente. Dada essa representação, apresente a árvore de 
estados para esse problema observando a restrição de movimento descrita acima. Considere 
fator de ramificação igual a 2 e profundidade 3 para a árvore de estados. 
 
Figura 1. Estado inicial. 
 
 
Figura 2. Estado final. 
 
 
7. Considere o seguinte problema do mundo dos blocos: 
 
 
 
a) Descreva os estados “Início” e “Objetivo” do mundo de blocos acima utilizando os seguintes 
possíveis predicados: ON(x,y), ONTABLE(x), CLEAR(x), HANDEMPTY e HOLDING(x), onde 
D}C,B,{A,x e D}C,B,{A,y ; 
b) Especifique as listas de pré-condição, remoção e adição para cada uma das seguintes ações 
STRIPS já definidas: EMPILHAR(x,y), DESEMPILHAR(x,y), PEGAR(x) e SOLTAR(x), onde 
D}C,B,{A,x e D}C,B,{A,y ; 
c) Mostre como o STRIPS resolveria esse problema. 
 
 
 
A 
B 
C D 
Início: Objetivo: 
A 
B 
C 
D