MC600 - Prova Escrita 2 - Prolog

Criada: 2003-09-30

Data da prova: 2003-09-23. Enunciado: aqui

Soluções e Critérios de Nota:

O pessoal foi mais ou menos, a média foi 5,0 com desvio padrão de 2,5. As notas foram distribuidas mais ou menos uniformemente no intervalo de 0 a 10. Bastante semelhante à prova de LISP.

Certas coisas que vi me deixaram bastante preocupado. Uma delas foi a grande quantidade de termos da forma N is N + 1 que vi nas provas. Gente, isto é influência procedural, e não faz sentido em Prolog, pois se N estiver instanciada, este termo nunca será satisfeito, e se N não estiver isntanciada, dá erro (is exige que seu lado direito esteja todo instanciado). Uma versão análoga foi append(L, T, L); este nunca dá erro, mas também nunca será satisfeito. Por fim, teve bastante gente que falou que [] unifica com [H|T], ficando H = [] e T = []. Errado! Na verdade, [] não unifica com [H|T].

As provas foram corrigidas com rigor. Os seguintes critérios foram aplicados a todas as questões. Falta de vírgula ou ponto final causou a perda de 0,5 pontos por ocorrência. Confusão entre X e [X] foi punida em 0,5 pontos. Cláusulas ou termos a mais, que atrapalharam o predicado, também custaram 0,5 pontos. O mesmo vale para a colocação de cláusulas ou termos em ordem errada. O uso errado de is (por exemplo, seu uso em situações não aritméticas, ou seu uso com variáveis não instanciadas do lado direito) também custou 0,5 pontos. Excesso ou falta de corte, prejudicando a funcionalidade do predicado, perdeu 0,5 pontos.

Nenhuma questão necessitava de assert ou manipulação da base de dados em geral para ser resolvida. Felizmente, não houve muitos asserts desnecessários (dentre as 69 provas, lembro-me de apenas 1 caso, punido em 0,5 pontos). Cortes a mais ou a menos, sem atrapalhar a funcionalidade, não afetaram a nota. O mesmo valeu para cláusulas ou termos a mais, ou ordem diferente de cláusulas ou termos, desde que não prejudicasse a funcionalidade. Alunos que usaram variáveis solitárias em cláusulas, em vez de usar uma variável anônima (cujo nome começa com _) também foram perdoados. Finalmente, aceitei /= em lugar de \=.

Se a resposta funcionava ou estava perto de funcionar então a nota foi 2,5 menos 0,5 por correção necessária para fazer o código funcionar. Se a resposta estava longe de funcionar então a nota foi zero na questão, exceto nos casos destacados abaixo. Os comentários (documentação) sobre os predicados auxiliares também valeram nota! O predicado principal não precisava ser comentado, pois o enunciado já o descrevia. Em alguns casos, o predicado principal valeu 1,5 e o auxiliar, 1,0.

Além destes critérios gerais, os critérios abaixo foram aplicados em cada questão específica. Seguem o gabarito oficial e os critérios.

  1. range3(I,J,[]) :- I > J, !.
range3(I,J,[I|L]) :- 0 is I mod 3,
        I3 is I+3, !,
        range3(I3,J,L).
range3(I,J,L) :- I1 is I+1,
        range3(I1,J,L).

    Os cortes são necessários para evitar re-satisfação. Uma solução alternativa, que muitos adotaram, foi substituir o corte na primeira cláusula por termos da forma I <= J iniciando as outras cláusulas. O corte na segunda cláusula poderia também ser substituido por R is I mod 3, R \= 0 ou equivalente na terceira.

    Quem testou se I > 0 perdeu 0,5 pontos. Não havia nada na questão que insinuasse que os números envolvidos deveriam ser positivos. Quem usou / como divisão inteira também perdeu 0,5 pontos. Se I não é múltiplo de 3, para atingir o primeiro inteiro M múltiplo de 3 a partir de I deve-se fazer R is I mod 3, M is I + 3 - R; quem usou R em lugar de 3 - R perdeu 0,5 pontos. Deixar o predicado falhar também perde 0,5 pontos.

  2. % predicado auxiliar geraint(X): gera os inteiros a partir do zero

geraint(0).
geraint(X) :- geraint(X1), X is X1 + 1.

geraquad(X) :- geraint(Y), X is Y*Y.

    Houve várias soluções que seguiram o modelo alternativo abaixo, também correto:

    % predicado auxiliar geraquad(N,Quad): gera em Quad os quadrados
% perfeitos de todos os inteiros a partir de N.

geraquad(N,Quad) :- Quad is N * N.
geraquad(N,Quad) :- N1 is N + 1, geraquad(N1,Quad).

geraquad(X) :- geraquad(0,X).

    Esta questão aparentemente foi das mais difíceis da prova. As notas em geral foram ou 2,5 ou então 0 ou 0,5, pois ou a pessoa acertava ou então passava muito longe da resposta. Dei 0,5 para quem pelo menos gerou o zero. Alguns ganharam mais pontos por ter percebido de alguma forma que precisariam geram todos os inteiros. Muitos escreveram um predicado recursivo com uma só cláusula, esqueceram do caso de parada.

  3. Solução:

    menor([],L) :- L \= [].
menor([H|_],[X|_]) :- H < X.
menor([H|L],[H|T]) :- menor(L,T).

    A primeira cláusula poderia ser também:

    menor([],[_|_].

    A ordem das cláusulas pode ser trocada sem problemas, pois são mutuamente exclusivas.

    O critério utilizado foi o seguinte:

    Quem fez pelo comprimento das listas se deu mal, a questão era comparar elemento a elemento. O comprimento é secundário.

  4. append1([H|T],L,[H|R]) :- append1(T,L,R).
append1([],L,L).

    Vamos dar nome às metas (e sub-metas) como meta1, meta2, etc. conforme forem sendo geradas. Quando houver casamento entre uma meta e uma cláusula (ou com a cabeça de uma cláusula), as variáveis da cláusula receberão como índice o número da meta para distingüir encarnações diferentes. Assim, por exemplo, H3 será a variável H num casamento com a meta3.

    A única letra que aparece nas duas cláusulas e' L, portanto teremos que distingüi-las. Usaremos L1_ e L2_ (L da cláusula 1 ou da cláusula 2). As variáveis da pergunta não receberão índice, ficarão "ao natural". Estamos prontos agora para dizer em que cláusulas pararam as metas: 

    ?- append1(X,Y,[a,b]).

X = [a,b] , Y = [] ;

  meta1: append1(X,Y,[a,b])  (meta mãe: não tem)
  parou na cláusula 1, com X=[H1|T1], Y=L1_1, a=H1, [b]=R1

  meta2: append1(T1,L1_1,[b])  (meta mãe: meta1)
  parou na cláusula 1, com T1=[H2|T2], L1_1=L1_2, b=H2, []=R2

  meta3: append1(T2,L1_2,[])  (meta mãe: meta2)
  parou na cláusula 2, com T2=[], L1_2=L2_3, []=L2_3

X = [a] , Y = [b] ;

  meta1: append1(X,Y,[a,b])  (meta mãe: não tem)
  parou na cláusula 1, com X=[H1|T1], Y=L1_1, a=H1, [b]=R1

  meta2: append1(T1,L1_1,[b])  (meta mãe: meta1)
  parou na cláusula 2, com T1=[], L1_1=L1_2, [b]=L1_2

X = [] , Y = [a,b] ;

  meta1: append1(X,Y,[a,b])  (meta mãe: não tem)
  parou na cláusula 2, com X=[], Y=L2_1, [a,b]=L2_1

No

    São 4 respostas (incluindo a última, No e 3 traces que teriam que ser dados. O seguinte critério foi usado: uma ou duas respostas corretas valeram 0,5, três ou quatro respostas corretas valeram 1,0, e cada trace valeu 0,5. A ordem em que as respostas apareciam também foi levada em conta. Quem disse que entrava em loop infinito ganhou zero. Para acertar um trace, bastava dizer em que cláusula cada meta parou, não precisava necessariamente explicitar as instanciações (embora isto fosse útil para saber qual resposta saiu).

© 2003 João Meidanis