Um tutor inteligente para o ensino/aprendizado de programaçã com técnicas de diagnóstico hierárquico baseado em modelos

Introducao Fundamentos Solucao Conclusoes

Um tutor inteligente para o ensino/aprendizado deprogramacao com tecnicas de diagnostico

hierarquico baseado em modelos

Wellington R. Pinheiro, Leliane N. de Barros

Departamento de Ciencia da ComputacaoInstituto de Matematica e Estatıstica - Universidade Sao Paulo

{wrp,leliane}@ime.usp.br

24 de Julho de 2009

ENIA, 24 de julho de 2009 Slide: 1/22


Conceitos Gerais

Sistema Tutor Inteligente para Programacao

Sistema Tutor Inteligente [Wenger, 1987] (ITS): ferramenta deaprendizado eletronico que usa tecnicas de Inteligencia Artificial.

Um ITS para programacao deve ser capaz de:

propor problemas de programacao que promovam o aprendizadode um determinado aluno;

detectar os possıveis erros de programacao do aluno(diagnostico do programa do aluno);

comunicar as falhas ao aluno com a expectativa que ele aprendadurante esse processo;

construir o modelo do aluno (representacao de seuconhecimento) com base no resultado do diagnostico deproblemas.



Conceitos Gerais

Sistema Tutor Inteligente para Programacao

Sistema Tutor Inteligente [Wenger, 1987] (ITS): ferramenta deaprendizado eletronico que usa tecnicas de Inteligencia Artificial.

Um ITS para programacao deve ser capaz de:

propor problemas de programacao que promovam o aprendizadode um determinado aluno;

detectar os possıveis erros de programacao do aluno(diagnostico do programa do aluno);

comunicar as falhas ao aluno com a expectativa que ele aprendadurante esse processo;

construir o modelo do aluno (representacao de seuconhecimento) com base no resultado do diagnostico deproblemas.



Conceitos Gerais

ITS para Programacao

PROUST [Johnson and Soloway, 1984]

PROUST e o principal sistema encontrado na literatura capazde detectar erros de logica de programacao.

ProPAT: Tutor de Padroes Elementares [Delgado, 2005].

Utiliza diagnostico baseado em modelo para fazer depuracao deprogramas (MBSD).

Funciona para um subconjunto de instrucoes da linguagem C.

Utiliza um plugin Eclipse como ambiente de programacao einterface de comunicacao com o estudante.

Permite que o aluno programe usando padroes elementares deprogramacao.



Conceitos Gerais

Diagnostico do Programa do AlunoPROUST [Johnson and Soloway, 1984] ProPAT [Delgado, 2005]

Caracterısticas

tenta construir o modelo doestudante reconhecendo planos deprogramacao e metas (intencoes) noprograma do aluno;

os planos de programacao e asmetas para um determinadoconjunto de problemas saoarmazenados em uma biblioteca.

utiliza diagnostico baseado emmodelo para detectar falhas noprograma do aluno;

nao requer uma biblioteca de planose metas previamente definidos paraa solucao.

Limitacoes

os planos da biblioteca podem naocobrir todas as possıveis solucoespara um determinado problema;

se nenhum plano for encontradonao e possıvel detectar as falhas noprograma do aluno.

as falhas sao comunicadas ao alunoem termos de linhas do programa, oque fornece pouca ou nenhumainformacao para que o alunoidentifique os erros no programa.



Conceitos Gerais

Diagnostico Baseado em Modelo

E uma tecnica de InteligenciaArtificial usada paraencontrar componentesfalhos em sistemas fısicos.

Raciocina sobre modelos quedescrevem o comportamentocorreto dos sistemas.

Envolve tressubtarefas [Benjamins, 1993]:deteccao de sintomas,geracao de hipoteses ediscriminacao de hipoteses.



Conceitos Gerais

Depuracao de Programas Baseada em Modelo[Mayer et al., 2002]

Ideia basica: fazer uma simulacao passo do programaapontando as instrucoes que justificam as discrepanciasobservadas (i.e. a diferencas entre as saıdas do programa e assaıdas esperadas (sintomas).

Pode ser usada por um ITS para tentar entender as diferencasentre as intencoes do aluno e seu programa.



Conceitos Gerais

Depuracao de Programas Baseada em Modelo



Conceitos Gerais

Limitacoes do MBSD para o Aprendizado de Programacao

Informar as linhas do programa possivelmente falhas pode naoser o suficiente para que o aluno consiga corrigir seu programa.

Mesmo para um programa pequeno, podem haver muitashipoteses de falha para serem comunicadas (e discriminadas) aoaluno, podendo deixa-lo cansado e confuso.

Um aprendiz de programacao nao tem conhecimento osuficiente para fazer predicoes a respeito do comportamento doprograma.



Objetivo

Proposta

Estender a tecnica MBSD com o uso do Diagnostico HierarquicoBaseado em Modelos (diagnostico hierarquico), de maneira que:

Falhas no programa do aluno possam ser encontradas emdiferentes nıveis de abstracao.

Funcoes, procedimentos e padroes elementares sejam vistoscomo componentes abstratos.

A comunicacao com o aluno possa ser feita em termos dessescomponentes abstratos , i.e. atraves de uma linguagem altonıvel, e nao somente atraves de linhas do programa.

Na media, o tutor comunique um conjunto de hipoteses defalha menor.



Objetivo

Ideia do MBSD + HMBD

Dar a oportunidade para que aluno entenda e corrija a falha doprograma em diferentes nıveis de abstracao.

Apos serem encontradas as hipoteses de falha em umdeterminado nıvel de abstracao, o aluno pode:

fazer a discriminacao de hipoteses no nıvel de abstracao atual(fornecendo novas observacoes a respeito do comportamentoesperado para o programa);depurar o programa em um nıvel mais detalhado, substituindoum componente abstrato pelos seus componentes internos(refinamento);modificar o programa para tentar corrigir as falhas.



Objetivo

Ideia do MBSD + HMBD

Dar a oportunidade para que aluno entenda e corrija a falha doprograma em diferentes nıveis de abstracao.

Apos serem encontradas as hipoteses de falha em umdeterminado nıvel de abstracao, o aluno pode:

fazer a discriminacao de hipoteses no nıvel de abstracao atual(fornecendo novas observacoes a respeito do comportamentoesperado para o programa);depurar o programa em um nıvel mais detalhado, substituindoum componente abstrato pelos seus componentes internos(refinamento);modificar o programa para tentar corrigir as falhas.



MBD

Modelos do Circuito de Exemplo

ok(C) indica que o componente C esta funcionando corretamente e;

¬ok(C) indica que o componente C esta falho.

Modelo comportamental Modelo estrutural Observacoes

adder(x)∧ok(x)→add(in1(x),in2(x),out1(x))

multiplier(x)∧ok(x)→mult(in1(x),in2(x),out1(x))

multiplier(M1)

multiplier(M2)

multiplier(M3)

adder(A1)

adder(A2)

out1(M1)=in1(A1)

out1(M2)=in2(A1)

out1(M2)=in1(A2)

out1(M3)=in2(A2)

in1(M1)=3

in2(M1)=2

in1(M2)=2

in2(M2)=3

in1(M3)=2

in2(M3)=3

out1(A1)=10

out1(A2)=12



HMBD

Diagnostico Hierarquico Baseado em Modelo (HMBD)

Uma tecnica usada para se obter melhor desempenho noprocesso de diagnostico.

A descricao do sistema e feita em diferentes nıveis de abstracao.

Utiliza abstracoes para representar componentes ou ocomportamento do sistema (abstracoes estruturais ecomportamentais).

Utiliza a tecnica de MBD tradicional para encontrar a solucao.



HMBD

Modelos com Abstracoes

Modelos do nıvel 1Modelo estrutural interno Modelo comportamental Modelo estrutural externo

nand−composition(NandComp,And,Inv)→

in1(NandComp)=in1(And)∧

in2(NandComp)=in2(And)∧

out1(And)=in1(Inv)∧

out1(NandComp)=out1(Inv))

nand−composition(NA1,A1,I1)

nand(C)∧ok(C)→

∃A,I [ nand−composition(C ,A,I )∧

and−ok(A)∧inv−ok(I ) ]

and−ok(C)≡out1(C)=1↔

in1(C)=1∧in2(C)=1

nand(NA1)

out1(NA1)=in1(A2)



HMBD

Arvore de Abstracoes

Suposicao de subsistemas independentes.



HMBD

Comportamento de um Componente Interno

Modelos de um componente abstrato

Um componente abstrato pode ser descrito pelos modelos:

estrutural interno, estrutural externo e comportamental.

Comportamento de um componente abstrato

Um componente abs-trato AC1 e os compo-nentes internos C1, C2e C3

O comportamento deAC1 e assumido comocorreto

Assim, o comporta-mento de C1, C2 e C3devem ser assumidoscomo corretos

Esse comportamento pode ser descrito formalmente pelo seguinte axioma:

ok(CA) → ok(C1) ∧ ok(C2) ∧ · · · ∧ ok(Cm) (Axioma 1)



HMBD

Abordagem top-down para fazer Diagnostico Hierarquico

Algoritmo de Diagnostico Hierarquico [Mozetic, 1991]:

1 Verificar quais observacoes deverao ser usadas em cada um dosnıveis de abstracao.

2 Para cada nıvel i , de l ate 0, sendo l o nıvel mais alto que naoesconde todas as conexoes com observacoes, encontrar oconjunto de hipoteses de falha utilizando algum algoritmo deMBD. Para cada componente abstrato CA nao envolvido emnenhuma hipotese de falha no nıvel i , usar o Axioma 1 para onıvel i − 1.

3 Devolver as hipoteses de falhas encontradas no nıvel 0.



HMBD

Exemplo do HMBD



HMBD

Exemplo do HMBD



HMBD

Exemplo do HMBD



HMBD

Exemplo do HMBD



MBSD+HMBD=HMBSD

Exemplo de Programa

Problema da Multa: Dados tres inteiros: (1) o valor de uma prestacao, (2) um inteiro 1ou 0 informando se deve ou nao ser aplicada uma multa de atraso e; (3) um inteiro 1 ou0 informando se deve ou nao ser aplicada a multa de mora. O valor da prestacao deveser calculado da seguinte forma: se multa for igual a 0, decremente 25 da prestacao,senao, incremente 50. Alem disso, caso o valor da mora seja 0, decremente 5 do valorobtido no calculo da multa, caso contrario, incremente 15.

1 public static void main(String[] args) {2 int valor, multa, mora, valorTotal;

3 valor = Integer.parseInt(args[0]);

4 multa = Integer.parseInt(args[1]);

5 mora = Integer.parseInt(args[2]);

6 valorTotal = valor;

+ 7 if (multa == 1)

+ 8 valorTotal = valorTotal + 50;

+ 9 else valorTotal = valorTotal -25;

∗ 10 if (mora == 1)

∗ 11 valorTotal = valorTotal - 5;

∗ 12 else valorTotal = valorTotal + 15;

13 System.out.println(valorTotal);

14 }

(+), (*) Linhas que fazem parte do padrao elementar Selecao Alternativa [Bergin, 1999].



MBSD+HMBD=HMBSD

Modelos do programa de exemplo

Ass ignment (C0)

Ass ignment (C1)

Ass ignment (C2)

valor0

multa1

mora2

valor = Integer.parse..

multa = Integer.parse..

mora = Integer.parse..

b) Mode lo base

a) Mode lo abs t ra to

Ass ignment (C3)novoValor3novoValor = valor

Condi t ional - C5C5 - Then

Adder (C6)

novoValor + 50 aux6

Ass ignment (C7)

novoValor += 50novoValor’

50novoValor7

C5 - Else

Adder (C8)

novoValor - 25 aux8

Ass ignment (C9)

novoValor += -25novoValor’’

-25novoValor9

Expr (C4)

multa == 1aux4

Condi t ional - C11

C11 - Then

Adder (C12)

novoValor - 5aux12

Ass ignment (C13)

novoValor += -5novoValor’’’

-5novoValor13

C11 - Else

Adder (C14)

novoValor + 15aux14

Ass ignment (C15)

novoValor += 15novoValor’’’’

15novoValor15

Expr (C10)

mora == 1

1

1

Ass ignment (C16)

System.out.println(...novoValor11

novoValor5

Ass ignment (C0)

Ass ignment (C1)

Ass ignment (C2)

valor0

multa1

mora2

valor = Integer.parse..

multa = Integer.parse..

mora = Integer.parse..

Ass ignment (C3)novoValor3

novoValor = valor

Seleção A l te rna t i va[7 -9 ] (CA1)1

novoValor5Seleção

A l te rna t i va[10 -12 ] (CA2)1

Ass ignment (C16)

System.out.println(...novoValor11

condResult

aux10

condResult



Conclusoes e trabalhos futuros

Nessa apresentacao mostramos:

uma extensao do diagnostico hierarquico para encontrar falhas emprogramas representados em diferentes nıveis de abstracao,considerando componentes abstratos, tais como: funcoes,procedimentos e padroes elementares;

propriedades importantes para tornar o processo de depuracao maiseficiente;

que a abordagem hierarquica para depurar programas de aprendizesserve para comunicar as falhas em uma linguagem de alto nıvel(considerando as abstracoes).

Trabalhos futuros:

Finalizar a implementacao do algoritmo de MBSD + HMBD;

Fazer uma avaliacao atraves de um experimento com alunos.



Bibliografia

Benjamins, R. (1993).Problem Solving Methods for Diagnosis.PhD thesis, University of Amsterdam.

Bergin, J. (1999).Patterns for selection.http://csis.pace.edu/ bergin/patterns/Patternsv4.html.

de Kleer, J. and Williams, B. C. (1987).Diagnosing multiple faults.Artif. Intell., 32(1):97–130.

Delgado, K. V. (2005).Diagnostico baseado em modelos num sistema tutor inteligente para programacaocom padroes pedagogicos.Dissertacao de mestrado, Instituto de Matematica e Estatıstica.

Johnson, W. L. and Soloway, E. (1984).Proust: Knowledge-based program understanding.In ICSE ’84: Proc. of the 7th international conference on Software engineering,pages 369–380, Piscataway, NJ, USA. IEEE Press.



Bibliografia

Mayer, W., Stumptner, M., Wieland, D., and Wotawa, F. (2002).Observations and results gained from the jade project.In Proc. of the 13th International Workshop on Principles of Diagnosis,Semmering, Austria.

Mozetic, I. (1991).Hierarchical model-based diagnosis.Int. J. Man-Mach. Stud., 35(3):329–362.

Reiter, R. (1987).A theory of diagnosis from first principles.Artif. Intell., 32(1):57–95.

Wenger, E. (1987).Artificial intelligence and tutoring systems: Computational and cognitiveapproaches to the communication of knowledge.Morgan Kaufmann Press.


Education

Um tutor inteligente para o ensino/aprendizado de programaçã com técnicas de diagnóstico hierárquico baseado em modelos