Validação Numérica

A linha de trabalho que adotamos é fortemente baseada no gabarito do professor, que deve ser não ambíguo (veja seção ). O resultado da validação é uma medida de distância entre a solução do aluno e o gabarito do professor. Como a distância é obtida a partir da descrição numérica dos objetos, denotaremos esta por validação numérica .

Para se fazer esta validação é necessário definir o critério de distância entre os pares de objetos geométricos. Definimos o critério de distância apenas para pares de objetos de mesma família (ou tipo). Para simplificar, vamos nomear apenas alguns dos exemplos de famílias mais comuns numa construção: família dos pontos ($F_{p}$); família das circunferências ($F_{c}$); e família dos segmentos ($F_{s}$). O conjunto de todas as famílias de objetos será representado por $F_{og}$.

Deste modo, o critério de distância pode ser uma função $dist$ que recebe um par de objetos geométricos e devolve um valor em :

$$dist: (og1, og2) \longrightarrow \mathcal{R_{+}}.$$ (5.1)

A descrição computacional dos objetos é definida para cada configuração da construção e deste modo pode ser feita a partir de uma lista de valores numéricos. Por exemplo: um ponto pode ser representado por um par $(x, y)$, onde $x$ e $y$ são as coordenadas do ponto; uma circunferência pode ser representada por uma tripla $(x,y,r)$, sendo $(x, y)$ as coordenadas de seu centro e $r$ seu raio; e um segmento $s=[(x_1,y_1), (x_2,y_2)]$, pode ser representado pela quádrupla $(x_1,y_1,x_2,y_2)$. Deste modo, se considerarmos apenas as famílias de pontos, circunferências e segmentos, podemos definir $dist$ conforme a equação . Dados dois objetos quaisquer de mesma família, $og1$ e $og2$, se $(l^1_1,l^1_2,\ldots,l^1_{i_{1}})$ e $(l^2_1,l^2_2,\ldots,l^2_{i_{2}})$ são as listas que representam, respectivamente, $og1$ e $og2$, então:

$$dist(og1,og2)\footnotemark = \left\{ \begin{array}{ll} \vs... ...ght\} &, (og1, og2) \in F_{s}\times F_{s}. \end{array} \right.$$ (5.2)

A necessidade do mínimo ($min$) quando os objetos forem do tipo segmento é devido ao desejo de classificar como iguais os segmentos AB e CD, mas também suas permutações AB e DC, BD e CD e BA e DC. Ou seja, se for segmento, o critério de distância não distingue um segmento AB do segmento BA.

Uma vez definida a distância entre objetos, podemos definir a distância entre pares de construções distintas a partir de seus objetos. Sendo $OG_{p}$ e $OG_{a}$, duas construções, e seus objetos representados, respectivamente, por $(og^{p}_{1}, og^{p}_{2} \: ... \: og^{p}_{i})$ e $(og^{a}_{1}, og^{a}_{2} \: ... \: og^{a}_{j})$, a distância entre $OG_{p}$ e $OG_{a}$ pode ser expressa conforme a tabela . Sendo $tipo(og)$ uma função que devolve o tipo do objeto geométrico $og$.

Tabela: Definição da distância entre pares de construções

Se a cardinalidade das listas $OG_{p}$ e $OG_{a}$ ($\char93 OG_p$ e $\char93 OG_a$) forem distintas, então

$dist(OG_{p},\: OG_{a}) = +\infty$.

Se $\char93 OG_p = \char93 OG_a = n$,

sejam $I_{p}$ = $(p_1,\ldots, p_n)$ e $I_{a} = (a_1,\ldots, a_n)$ duas permutações sobre os $n$ primeiros

naturais,

$dist(I_{p}, I_{a}) = \left\{ \begin{array}{ll} \displaystyle\sum_{i=1}^{n} ... ...\vspace{0.3cm}\\ %\\ [-0.5cm] +\infty &, \ \hbox{ c.c.} \end{array}\right\}$

então

se $\mathcal{P}_{n}$ é o conjunto de todas as permutações dos $n$ primeiros naturais,

$dist(OG_{p},\: OG_{a}) = min \left\{ dist(I_{p}, I_{a}), \forall(I_{p}, I_{a})\in{P}_{n}\times{P}_{n} \right\}$

ou seja, dentre todas as permutações de objetos de $OG_p$ e $OG_a$, $dist(OG_{p},\: OG_{a})$

é a soma das distâncias entre cada par de objetos de mesmo tipo que resulta no

menor valor.

Esta é apenas uma das possibilidades para medir distância entre construções. Uma generalização simples desta função é colocar coeficientes positivos para ponderar cada objeto.

Uma solução (construção geométrica) pode ser representada como uma função que recebe uma lista de objetos geométricos (entrada) e devolve uma outra lista de objetos geométricos (saída), que podemos representar como:

$$S: OG_{i} \longrightarrow OG_{f}.$$ (5.3)

Uma instância de uma construção $S$ é a aplicação de $S$ sobre uma dada configuração de objetos. Uma vez determinada a distância entre pares de listas de objetos e a representação de uma solução, podemos definir quando duas construções (soluções) são equivalentes, como segue .

Definição 5..2 (Equivalência)   Sejam $S_{p}$ e $S_{a}$ duas construções aplicáveis sobre a mesma lista de objetos geométricos $OG$. Então $S_{a}$ e $S_{p}$ são equivalentes se, e somente se, para qualquer configuração $OG_{0}\:$ da lista $OG$, tivermos .

Vale observar que se duas construções são equivalentes, a distância entre ambas é invariante em relação às configurações iniciais, isto é, à distância computada para qualquer instância é sempre nula. Portanto, se desconsiderarmos erros numéricos, um bom critério de validação é dizer que uma construção $S_a$ esta correta sempre que for equivalente à construção $S_p$ gabarito. Entretanto existe o problema prático: como implementar uma versão suficientemente rápida e levando em consideração os erros numéricos ?

Como construções distintas que obtém os mesmos objetos-resposta podem resultar em pequenas diferenças numéricas, optamos por relaxar o critério de equivalência, permitindo que, por exemplo, dois pontos ``muito próximos'' em um bom número de distintas instâncias sejam considerados ``quase equivalentes'' (vide seção ). Esta solução, em princípio, permite que sejam construídos exemplos em que ocorram erros de falso positivo (exercício errado avaliado como correto) ou de falso negativo (exercício certo avaliado como incorreto), mas funciona bem na prática. Também é possível aumentar o número de instâncias a serem testadas ou fazer outras modificações de parâmetros para reduzir/eliminar validações falsas.

Nas próximas seções, quando estiver implícito, ou for indiferente qual a lista de objetos geométricos $OG$, utilizaremos a notação simplificada $S$ e não $S(OG)$.