Inteligência Artificial
Segundo Teste
• 16 de Janeiro de 2013
•
17:00-18:30
Este teste é composto por 12 páginas contendo 7 perguntas. Identifique já todas as folhas
do teste com o seu nome e número. Na mesa em que está a fazer o exame deve ter apenas
lápis/caneta, identificação e este exame. Pode utilizar o verso das folhas como rascunho.
Deve responder às perguntas no espaço deixado para o efeito.
Para as perguntas de escolha múltipla é dada uma cotação negativa no caso de a resposta
estar errada: se existirem n alternativas e a cotação for c, então respostas erradas
contribuem negativamente para a classificação final com –c/(n-1).
Cotações Perguntas 1) _______ 2_______ 3_______ 4_______ 5_______ 6_______ 7_______
Pergunta 6 de escolha múltipla (deve ser respondida aqui):
Pergunta
1
2
3
4
5
6
7
8
9
10
11
12
a
b
c
d
e
f
Classificação
Nome:_____________________________________________ Número:_________
1
1. (2.5) Considere a seguinte árvore de procura de um jogo:
5
2
1
7
5
0
7
5
0
5
Suponha que o triângulo com o vértice virado para cima quer maximizar e o triângulo
com o vértice virado para baixo quer minimizar. Aplique o algoritmo minimax com
cortes alfa-beta da esquerda para a direita, escurecendo os nós terminais visitados, e
indicando os cortes e tipos de cortes. Indique a jogada escolhida.
Nome:_____________________________________________ Número:_________
2
2. (3.0) Considere a seguinte base de conhecimento:
1. mulher(X) ⇒ usa_faca(X)
2. estava_cozinha(X) ∧ usa_faca(X) ⇒ matou(X, Dr.Neves)
3. homem(X) ∧ médico(X) ⇒ usa_faca(X)
4. cozinheira(X) ⇒ estava_cozinha(X)
5. cozinheira(X) ⇒ mulher(X)
6. homem(Dr.Pacheco)
7. médico(Dr.Pacheco)
8. homem(Prof.Brandão)
a. (1,5) Acrescentando à base de conhecimento que “A Ana é cozinheira” (usando
apenas os predicados das proposições já na BC), recorra ao Modus Ponens
Generalizado (MPG) e à inferência progressiva para indicar que conclusões
permite a proposição inferir. Não se esqueça de indicar as cláusulas que lhe
permitiram aplicar o MPG, bem como as substituições realizadas.
Nome:_____________________________________________ Número:_________
3
b. (1,5) Utilizando inferência regressiva na BC original mais a proposição “A Ana é
cozinheira” responda à pergunta “Quem matou o Dr. Neves?”.
Nome:_____________________________________________ Número:_________
4
3. (3.0) Há muitas maneiras de caracterizar planeadores. Para cada uma das seguintes
dicotomias, explique o que significam as características contrapostas e como a
escolha entre elas afecta a eficiência e a completude de um planeador:
a. (0.6) Espaço de situações face a espaço de planos.
b. (0.6) Progressivo face a regressivo.
c. (0.6) Comprometimento mínimo face a mais comprometimento.
d. (0.6) Variáveis ligadas face a variáveis desligadas.
e. (0.6) Ordem total face a ordem parcial.
Nome:_____________________________________________ Número:_________
5
4. (4.0) Qualquer fã de filmes de terror para adolescentes é capaz de acertar nas
personagens que vão ser assassinadas ao longo do filme. Observando um conjunto de
características das personagens deve ser possível construir uma árvore de decisão que
permita prever quem são as personagens que vão ter esse destino.
a) (3.0) Recorrendo aos dados da tabela abaixo e ao algoritmo Decision Tree
Learning crie o primeiro nó de uma tal árvore de decisão. Não se esqueça de
indicar os cálculos efectuados e de justificar a sua escolha para o nó.
P
ersonagem
1
2
3
4
5
6
7
8
Cor
do
cabelo
Ruivo
Castanho/Preto
Castanho/Preto
Castanho/Preto
Loiro
Loiro
Loiro
Loiro
Capacidade de
gritar
histericamente
Sim
Sim
Sim
Não
Sim
Não
Sim
Não
Idade
Assassinada
18 ≤ x ≤ 35
x < 18
18 ≤ x ≤ 35
x > 35
18 ≤ x ≤ 35
x < 18
x > 35
x > 35
Sim
Não
Não
Não
Sim
Não
Sim
Não
A seguir fornecem-se alguns valores que podem ser úteis para os cálculos:
I(0, 1) = 0; I(1/2, 1/2) = 1; I(2/3, 1/3) = 0.918; I(3/5, 2/5) = 0.97; I(3/8, 5/8) = 0.955;
Nome:_____________________________________________ Número:_________
6
b) (1.0) Sem efectuar mais cálculos indique ainda o que teria de fazer para completar
a sua árvore de decisão.
Nome:_____________________________________________ Número:_________
7
5) (2,5) Considere a seguinte gramática para expressões aritméticas, aumentada com
semântica:
Exp(x) → Exp(x1) Operator(op) Exp(x2) {x=Apply(op, x1,x2)}
Exp(x) → ( Exp(x) )
Exp(x) → Number(x)
Number(x) → Digit(x)
Number(x) → Number(x1) Digit(x2) {x=10 * x1 + x2}
Digit(x) → x {0 ≤ x ≤ 9}
Operator(x) → x {x {+,-,:,*}}
a) (1,5) Desenhe a árvore analítica com interpretação semântica para a cadeia de
caracteres “4 * (5 - 3) ”
b) (1,0) As regras da gramática obedecem ao princípio da semântica composicional. Diga
em que consiste este princípio.
Nome:_____________________________________________ Número:_________
8
6. (3.0) Pergunta de escolha múltipla (responder na primeira página)
1. (0,25) As funções de avaliação (EVAL) e de teste de corte (CUTOFF-TEST) são
usadas no MINIMAX:
a.
b.
c.
d.
e.
f.
Quando há tempo para procurar todo o espaço de estados.
Quando se pretende usar os cortes ALFA e BETA.
Quando se pretende melhorar a qualidade das soluções encontradas.
Face à necessidade de tomar decisões imperfeitas.
Todas as respostas acima são verdadeiras.
Nenhuma das resposta acima é verdadeira.
2. (0,25) No cálculo situacional, cada acção é descrita pelos seguintes axiomas:
a. Um axioma de possibilidade, um axioma de efeito e um axioma de quiescência.
b. Um axioma de possibilidade, um axioma de efeito e vários axiomas de
quiescência.
c. Um axioma de impossibilidade, um axioma de efeito e vários axiomas de
quiescência.
d. Vários axiomas de possibilidade, um axioma de efeito e um axioma de
quiescência.
e. Vários axiomas de possibilidade, vários axiomas de efeito e vários axiomas de
quiescência.
f. Nenhuma das respostas acima é verdadeira.
3.
(0,25) O planeamento:
a. Tem sido objecto de diferentes abordagens.
b. É um tipo de resolução de problemas alternativo à procura.
c. Usa conhecimento explícito das acções e dos seus efeitos para procurar uma
solução num espaço mais abstracto de planos em vez de situações.
d. Usa algoritmos de planeamento regressivo cujas soluções são planos parcialmente
ordenados.
e. Todas as respostas acima são verdadeiras.
f. Nenhuma das respostas acima é verdadeira.
4. (0,25) A análise gramatical (“parsing”, em Inglês) permite:
a.
b.
c.
d.
e.
f.
Encontrar uma árvore analítica para uma gramática.
Encontrar uma cadeia de símbolos a partir de uma árvore analítica.
Levantar o conhecimento e informação (análise) do domínio de língua natural.
Recuperar a estrutura semântica a partir de uma elocução.
Todas as respostas acima são verdadeiras.
Nenhuma das respostas acima é verdadeira.
Nome:_____________________________________________ Número:_________
9
5. (0,25) As gramáticas aumentadas de cláusulas definidas:
a.
b.
c.
d.
e.
f.
Crescem exponencialmente com o número de categorias.
Permitem falar de análise sintáctica como inferência lógica.
Não permitem usar a mesma gramática para análise e geração.
Apresentam problemas de sobre-geração.
Todas as respostas acima são verdadeiras.
Nenhuma das respostas acima é verdadeira.
6. (0,25) A aprendizagem:
a. É uma forma de gerar novo conhecimento.
b. É uma forma de dotar um agente com autonomia de forma a poder lidar com
ambientes desconhecidos.
c. É uma forma de permitir a um agente melhorar o seu desempenho com a
experiência.
d. Pode ser realizada com o auxílio de diferentes algoritmos.
e. Todas as respostas acima são verdadeiras.
f. Nenhuma das respostas acima é verdadeira.
7.
(0,25) Numa árvore de decisão:
a. Um nó interno corresponde a um teste do valor de um dos atributos de um objecto
ou situação.
b. Os ramos de um nó são rotulados com os possíveis valores do teste representado
pelo nó.
c. Uma folha especifica o valor a ser devolvido se a folha for atingida.
d. Todas as respostas acima são verdadeiras.
8. (0,25) Na indução de árvores de decisão a partir de exemplos, o que se deve fazer
quando um teste tem como resultado apenas exemplos positivos ou apenas exemplos
negativos?
a. Escolhe-se, recursivamente, o melhor atributo dos restantes para os separar.
b. Devolve-se sim ou não, respectivamente.
c. Usa-se o voto de maioria consoante haja mais exemplos positivos ou negativos,
respectivamente, no nó pai.
d. Nenhuma das respostas acima é verdadeira.
Nome:_____________________________________________ Número:_________
10
9. (0,25) Na indução de árvores de decisão a partir de exemplos, o que se deve fazer
quando um teste tem como resultado exemplos positivos e negativos?
a. Escolhe-se, recursivamente, o melhor atributo dos restantes para separar os
exemplos, caso haja mais atributos.
b. Usa-se o voto de maioria se não existirem mais atributos, consoante haja mais
exemplos positivos ou negativos, respectivamente, no nó pai.
c. Nenhuma das respostas a) e b) é verdadeira.
d. Ambas as respostas a) e b) são verdadeiras.
10. (0,25) Na indução de árvores de decisão a partir de exemplos, o que se deve fazer
quando um teste tem como resultado um conjunto vazio de exemplos?
a. Escolhe-se, recursivamente, o melhor atributo dos restantes.
b. Usa-se o voto de maioria, consoante haja mais exemplos positivos ou negativos,
respectivamente, no nó pai.
c. Nenhuma das respostas a) e b) é verdadeira.
d. Ambas as respostas a) e b) são verdadeiras.
11. (0,25) A análise gramatical (“parsing”, em Inglês) consiste em:
a.
b.
c.
d.
Encontrar uma árvore analítica para uma dada cadeia de símbolos.
Recuperar a estrutura sintáctica a partir de uma elocução, dada uma gramática.
Nenhuma das respostas a) e b) é verdadeira.
Ambas as respostas a) e b) são verdadeiras.
12. (0,25) As Gramáticas de Cláusulas Definidas (DCGs) permitem:
a.
b.
c.
d.
Falar de análise sintática como inferência lógica.
Usar a mesma gramática para análise e geração.
Nenhuma das respostas a) e b) é verdadeira.
Ambas as respostas a) e b) são verdadeiras.
Nome:_____________________________________________ Número:_________
11
7. (2.0) Usando ANSI Common LISP:
1.
(1,0) Escreva a função recursiva substituir-elemento que substitui o
elemento dado como primeiro argumento pelo elemento dado como segundo
argumento na lista dada como terceiro elemento:
> (substituir-elemento ‘b ‘y ‘(a b c d))
(A Y C D)
e. (1,0) Escreva a função recursiva uniao que recebe duas listas e devolve a união
entre elas:
> ((uniao ‘(a b c d) ‘(b d j))
(A C B D J)
Nome:_____________________________________________ Número:_________
12