Gabarito do teste 1 (28/05/2003)

1) (2) P-F

2) nenhuma (o certo seria V-T)

3) (3) V-C

4) Estes algoritmos são utilizados para problemas onde podemos
   construir uma solução inicial não ótima. A vantagem é encontrar
   máximos ou mínimos globais. Exs: random restart hill-climbing,
   algoritmos genéticos, simulated annealing (algs estão no livro).

5) Algs de busca não informados são úteis para algus tipos de
   problemas, onde encontrar a solução ótima não é fundamental e onde
   não sabemos as características do problema e se torna difícil
   construir uma função ou algoritmo heurístico. Busca
   em profundidade é o algoritmo que possui menor complexidade
   espacial, porém pode não ser completo sem a verificação de estados
   repetidos. Busca em largura somente se torna viável para problemas
   onde o fator de ramificação não é muito alto e a solução não está
   muito profunda na árvore. O melhor método na prática é o busca em
   profundidade iterativo (combina a completude de busca em largura
   com a complexidade de espaço de busca em profundidade). Métodos de
   busca informados são bastante úteis para encontrar soluções
   ótimas. Têm complexidade exponencial de espaço no pior caso. O
   método mais popular é o IDA*.

6) (5)

7) nenhuma (g,k,q,n,o)

8) está no livro.

9) (p ^ q) v (p ^ not q)

   (p v p) ^ (p v not q) ^ (q v p) ^ (q v not q)

    p ^ (p v not q) ^ (q v p)
    p
    p v not q
    p v q

resolucao: alfa v beta, not beta v gama -> alfa v gama
           p v q -> alfa v beta
           not q v p -> not beta v gama 
           p v p -> p

está falando sobre uma expressão aritmética, mas tb pode ser uma
tautologia e não falar sobre nenhum dos dois ou sobre os dois (ver
solucao da lista).

10) sim, a tabela-verdade mostra isso

11) 

de (1) temos (7) Q e (8) Z
de (3) temos (9) ~P
de (5) temos (10) S v P
de (9) como ~P é verdadeiro, em (10) concluímos que (11) S tem que ser
       verdadeiro. 
de (11) Se S é verdadeiro, S v R também é verdadeiro.
cqd.