Teste de IA (Duração: 2 horas)

Nome:

Nota: Data: 28/05/2003

1. O teste está fácil. Não compliquem!

2. Nas questões de múltipla escolha, cada questão errada anula uma certa.

3. Por favor, coloquem nome em todas as folhas que me entregarem. Respostas sem justificativa serão consideradas erradas.

4. Assinem a pauta de aula ao terminarem o teste, por favor.

5. Boa sorte!

Os dois grafos seguintes (figura 1) mostram as distâncias entre cidades por estradas e distãncias em linha reta das cidades para I (por exemplo, no grafo da esquerda, a estrada que liga a cidade P à cidade F tem 7 unidades de comprimento de extensão, enquanto no grafo da direita, a distância em linha reta de P a I é 28):

Figure 1: Grafo para questões 1, 2 e 3

(0,5) 1) Indique qual percurso parcial a estratégia de busca em profundidade, selecionando a cidade mais a oeste primeiro, testaria primeiro para encontrar o melhor percurso de B para I. Marque a melhor escolha abaixo:

(1) P-C (2)P-F (3) V-C

(1,0) 2) Para o grafo anterior, qual dos seguintes caminhos seria dado pela busca ``gulosa'' como parte do percurso de B para I:

(1) P-C (2) P-F (3) V-C

(1,0) 3) Para o mesmo grafo anterior, que caminho o algoritmo A* testaria primeiro para encontrar o melhor caminho a partir de B?

(1) P-C (2) P-F (3) V-C

(1,0) 4) Quais são as vantagens de se utilizar um algoritmo de melhoramento iterativo? A que tipos de problemas, estes algoritmos mais se adequam? Dê exemplos de algoritmos de melhoramento iterativo e explique seus funcionamentos de forma sucinta.

(1,0) 5) Discuta sobre vantagens e desvantagens dos vários algoritmos de busca (não informados e informados) estudados em aula. Não omita comparações entre complexidades temporal e espacial, e comente para que tipos de problemas os algoritmos são mais adequados.

(1,0) 6) Dada a seguinte árvore de jogos (figura 2), em que a jogada inicial é de maximização,

Figure 2: Grafo para questões 6 e 7

Indique qual é o máximo valor esperado para a jogada.

(1) 4 (2) 5 (3) 2

(1,0) 7) Para a árvore de jogos anterior, que nós seriam removidos pelo corte alfa-beta?

(1) (g,k,m,n,o,q) (2) (k,m,n,o) (3) nenhum

(1,0) 8) Prove que o algoritmo A* é admissível.

(1,0) 9) A sentença ``$2+2=4$ e está chovendo, ou $2+2=4$ e não estã chovendo'' está falando sobre alguma expressão aritmética, sobre o clima ou sobre nenhum dos dois?

(0,5) 10) A fórmula proposicional abaixo é válida?

$$[ (P \Rightarrow Q) \wedge (Q \Rightarrow R) ]\Rightarrow (P \Rightarrow R)$$

(1,0) 11) Mostre formalmente que $S \vee R$ é conseqüência lógica das fórmulas dadas abaixo. Não utilize mais do que 10 passos de inferência para fazer a prova.

Número	Fórmula	Justificativa
1	$\neg (\neg Q) \wedge Z$	dada
2	$\neg W$	dada
3	$(\neg W \wedge Q) \Rightarrow (\neg P)$	dada
4	$(W \wedge Z) \Rightarrow S$	dada
5	$Q \Rightarrow (S \vee P)$	dada
6	$(P \wedge Q) \Rightarrow R$	dada
7
8
9
10
11
12
13
14
15
16