MC346 - Exame

Criada: 2014-07-27
Modificada: 2015-02-07

Enunciado distribuído na sala.

Gabarito

Questão 1

(defun comum (x y)
  (lca x y)
  )

(defun lca (x y)
  (or (descends y x)
      (lca-list (inset x) y)
      )
  )

(defun lca-list (l y)
  (if (null l)
      nil
    (or (lca (car l) y)
	(lca-list (cdr l) y))
    )
  )

(defun descends (y x)
  (if (equal x y)
      x
    (descends-list (inset y) x)
    )
  )

(defun descends-list (l x)
  (if (null l)
      nil
    (or (descends (car l) x)
	(descends-list (cdr l) x)
	)
    )
  )

;;; Para testar: função inset refletindo a figura da prova.

(defun inset (x)
  (cond
   ((eql x 'a) '(b))
   ((eql x 'b) '(j))
   ((eql x 'c) '(b j e))
   ((eql x 'd) '(c))
   ((eql x 'e) '(j))
   ((eql x 'f) '(c g))
   ((eql x 'g) '(h))
   ((eql x 'h) '())
   ((eql x 'i) '(h))
   ((eql x 'j) '())
   )
  )

Questão 2

ancestrais(X, [X|RX]) :-
    inset(X, PX),
    ancList(PX, RX).

%%% ancList(L, A) satisfeito quando A é a lista de todos os ancestrais 
%%% dos elementos de L

ancList([], []).
ancList([X|R], A) :-
    ancestrais(X, AX),
    ancList(R, AR),
    union(AX, AR, A).

%%% Para testar: predicado inset refletindo a figura da prova.

inset(a,[b]).
inset(b,[j]).
inset(c,[b,j,e]).
inset(d,[c]).
inset(e,[j]).
inset(f,[c,g]).
inset(g,[h]).
inset(h,[]).
inset(i,[h]).
inset(j,[]).

Questão 3

(defun amigos (n m)
  (and
   (= n (somadiv m))
   (= m (somadiv n))
   )
  )

(defun somadiv (n)
  (somadiv-ateh (1- n) n)
  )

(defun somadiv-ateh (k n)
  (cond
   ((<= k 1) 1)
   ((= 0 (mod n k)) (+ k (somadiv-ateh (1- k) n)))
   (t (somadiv-ateh (1- k) n))
   )
  )

Questão 4

%%% soma_div(N, S) eh satisfeito quando S eh a soma dos divisores de N menores que ele proprio
soma_div(N, S) :- N1 is N - 1, soma_div_ateh(N, N1, S).

%%% soma_div_ateh(N, L, S) eh satisfeito quando S eh a soma dos dividores de N ateh L
%%% (ou seja, dividores menores ou iguais a L)
soma_div_ateh(_, 0, 0) :- !.
soma_div_ateh(N, L, S) :-
    L1 is L - 1,
    soma_div_ateh(N, L1, S1),
    parcela(N, L, P),
    S is S1 + P.

%%% parcela(N, L, P) eh satisfeito quando P eh a parcela a somar nos dividores de N relativa a L.
%%% em outras palavras, se L divide N, a parcela eh L; se L nao divide N, a parcela eh zero.
parcela(N, L, 0) :- 0 =\= N mod L, !.
parcela(N, L, L) :- 0 =:= N mod L.

%%% amigos

amigos(N, M) :-
    soma_div(N, M),
    soma_div(M, N).

Critérios de correção

O critério de correção começou por decidir como seria a pontuação: de cima para baixo ou de baixo para cima. Se a resposta estava bem escrita, com sintaxe Lisp correta, resolução do problema pedido (e não de outro) e com comprimento proporcional à complexidade da questão, então a correção procedeu de cima para baixo, ou seja, parte-se do valor integral e vão sendo subtraidas frações de pontos para cada defeito encontrado.

Por outro lado, se a resposta estava mal escrita, com sintaxe errada, resolvendo o problema errado ou incompleta, então a correção procedeu de baixo para cima: parte-se de zero e vão sendo adicionadas frações de pontos a cada indício de conhecimento importante encontrado. Embora em geral a correção de cima para baixo resulte em notas maiores numa questão, é possível ter exceções a esta tendência.

Em todas as questões, os seguintes critérios foram universalmente aplicados:

Critérios de cima para baixo:

Parênteses a mais ou a menos: -0,5
is usado em contexto não aritmético: -0,5
uso de = em lugar de is: -0,5
Confusão entre append, cons, list: -0,5
Loop infinito: -0,5
Usou função pré-definida (por exemplo, car, list, etc.) a mais ou a menos: -0,5
Número errado de argumentos ou ordem errada de argumentos: -0,5
Erro em nome de variável: -0,5
Faltou corte: -0,5
Problema em caso base de recursão: -0,5
Usou mas não definiu função auxiliar: -1,0
Outros erros de sintaxe: -0,5

A seguir, critérios específicos para cada questão. Nas questões de código, são todos critérios de cima para baixo.

Questões 1 e 2

Critérios de cima para baixo:

Usou uma função como se recebesse tanto elementos como listas, mas não estava preparada para tal: -0,5
Só expandiu ancestrais de parte dos necessários: -1,0

Questão 1

Critérios de cima para baixo:

Usou nullp em Lisp em vez de null: -0,5
Uso errado de reduce: -0,5
Faltou defun na definição de função: -0,5
Não funciona com átomos: -0,5
Esqueceu o próprio elemento entre os ancestrais: -0,5
Usou if com apenas dois elementos: -0,5

Critérios de baixo para cima:

Só retorna os pais em comum: +1,0

Questão 2

Critérios de cima para baixo:

Uso de _ em vez de [ ]: -0,5
Confusão entre append e merge: -0,5
Trabalhos feitos em cláusulas separadas deveriam ser feitas na mesma cláusula: -0,5

Critérios de baixo para cima:

Só funciona quando para órfãos: +0,5

Questões 3 e 4

Critérios de cima para baixo:

Aceita zero como amigo de alguém: -0,5
Divisão por zero: -0,5

Questão 3

Critérios de cima para baixo:

Faltou apply: -0,5
Usou != em lugar de /=: -0,5
Usou integer em lugar de integerp: -0,5
Somou N entre os divisores próprios de N: -0,5
Não retornou o valor correto: -0,5
Usou NIL no lugar de zero: -0,5
Todos os pares de números são amigos: -1,0
Comparou as duas somas de divisores em lugar de comparar cada uma delas com o outro número: -1,0

Questão 4

Critérios de cima para baixo:

Faltou ponto final: -0,5
Usou := em lugar de :-: -0,5
Faltou fail: -0,5
Usou A/B em lugar de B/A: -0,5
Usou mesma variável em ambos os lados de is: -0,5
Argumento não instanciado para is: -0,5
Inverteu metas: -0,5
Definiu predicado mas não o utilizou: -0,5
Predicado "dentro" de outro: -1,0

MC346 Home