UFGD - Inteligencia_Artificial_Aplicada_a_Educacao_I

Prévia do material em texto

INTELIGÊNCIA ARTIFICIAL 
APLICADA À EDUCAÇÃO I 
(PRÁTICA PEDAGÓGICA)
Autora: Valguima Victoria Viana Aguiar Odakura
2
Prezados acadêmicos,
Bem-vindos à disciplina de Inteligência Artificial Aplicada à Educação (IAAE) I do curso de Licenciatura 
em Computação da EaD-UFGD.
Nesta disciplina serão apresentados os conceitos introdutórios relacionados à Inteligência Artificial 
(IA), e vocês terão a oportunidade de conhecer as técnicas de resolução de problemas por meio de 
busca, representação do conhecimento e sistemas especialistas. Outras técnicas de IA serão vistas na 
continuação desta disciplina, em Inteligência Artificial Aplicada à Educação II.
O conhecimento de técnicas de IA permitirá que vocês vislumbrem como elas podem ser empregadas na 
Educação, de forma mais específica, como sistemas computacionais podem auxiliar no processo de ensino-
aprendizagem. 
Um excelente e proveitoso curso para todos!
Objetivos
Unidades
• Despertar o interesse para área de Inteligência Artificial.
• Compreender os conceitos relacionados à resolução de problemas por meio de busca com 
métodos não informados.
• Compreender os conceitos relacionados à resolução de problemas por meio de busca com 
métodos informados.
• Entender a necessidade de representar adequadamente o conhecimento e ser capaz de 
escolher uma representação de conhecimento adequada para o problema a ser solucionado.
• Adquirir conhecimento sobre os conceitos fundamentais de Sistemas Especialistas, bem 
como sua construção e utilização.
1. Introdução e História da Inteligência Artificial
2. Resolução de problemas: métodos não informados de busca 
3. Resolução de problemas: métodos informados de busca
 4. Representação do conhecimento
 5. Sistemas especialistas
3
Unidade
Caros acadêmicos,
Bem-vindos à disciplina de Inteligência Artificial aplicada à Educação I. Neste módulo, vamos começar 
nossos estudos conhecendo o conceito de Inteligência Artificial e vamos percorrer a sua história para 
acompanhar seu desenvolvimento, até chegarmos ao seu estado nos dias de hoje. Também iremos 
lançar um olhar inicial sobre a Inteligência Artificial aplicada à Educação.
1.1 Introdução
O termo Inteligência Artificial (IA) é bastante conhecido, por ser utilizado com frequência pela mídia, 
sendo assunto de livros e filmes de ficção científica. Quem não conhece as histórias de Isaac Asimov sobre 
robôs, que inspiraram os filmes: Eu, robô e o Homem Bicentenário? Ou não conhece o filme 2001, uma 
odisséia no espaço, de Kubrick, que apresenta o robô HAL, tão inteligente quanto os seres humanos, ou o filme 
I.A. de Spielberg, que apresenta um robô humanoide capaz de expressar sentimentos e emoções? Ou ainda 
o desenho animado Os Jetsons, em que uma família convivia com a Rosie, um robô empregada doméstica?
1
Esta unidade tem como objetivos:
• Despertar o interesse pela área de Inteligência Artificial.
• Conhecer a história da Inteligência Artificial.
• Destacar a aplicação da Inteligência Artificial na Educação.
Introdução e história da Inteligência Artificial
Permeado pela ficção científica, o termo Inteligência Artificial pode causar certa frustração para quem 
começa a estudar a área esperando encontrar mais ficção do que ciência. IA é uma área da Ciência da 
Computação e, como tal, estuda teorias e modelos computacionais. Em específico, as teorias e modelos de 
interesse são as de função cognitiva. Algumas definições encontradas na literatura podem ajudar a entender o 
conceito de IA: 
Isaac Asimov é um escritor de ficção científica que escreveu livros sobre robôs. É 
conhecido por ter criado as três leis da robótica:
• Primeira lei: um robô não pode causar dano a um ser humano, ou, por omissão, 
permitir que um ser humano sofra.
• Segunda lei: um robô deve obedecer às ordens dadas por seres humanos, exceto 
quando essas ordens entrarem em conflito com a primeira lei.
• Terceira lei: um robô deve proteger sua própria existência, desde que essa proteção 
não entre em conflito com a primeira, nem com a segunda lei da robótica.
Referência em inglês: http://www.asimovonline.com/asimov_home_page.html
Referência em português: http://www.din.uem.br/~ia/a_correl/classicos/Pesquisadores-
Asimov.htm
Saiba mais!
http://www.din.uem.br/~ia/a_correl/classicos/Pesquisadores-Asimov.htm
http://www.din.uem.br/~ia/a_correl/classicos/Pesquisadores-Asimov.htm
4
Pelas definições apresentadas para 
IA e segundo Bittencourt (2006), a IA 
possui os objetivos de formular modelos 
para a inteligência e construir sistemas 
computacionais para os modelos formulados. 
Tentando alcançar esses objetivos, diversos 
assuntos são investigados na área de IA, 
entre eles: resolução de problemas, jogos, 
representação do conhecimento, prova 
automática de teoremas, reconhecimento de 
padrões, visão computacional, compreensão 
de linguagem natural, aprendizado de máquina 
e robótica.
1.2 Um pouco da história
Vamos começar a história da Inteligência Artificial a partir da década de 1950, quando o termo foi 
oficialmente usado. A história da IA é repleta de sucessos e fracassos, que resultaram em um campo de 
pesquisa extremamente rico e consolidado. Atualmente, os sistemas computacionais produzidos sobre as 
bases da IA são amplamente utilizados.
Em 1943, Warren McCulloch e Walter Pitts propuseram um modelo matemático de um neurônio artificial, 
baseado na fisiologia de um neurônio no cérebro. Cada neurônio pode ter o estado ligado ou desligado, sendo 
que os neurônios artificiais podem ser conectados por uma rede. Um conjunto desses neurônios interligados 
resulta em uma rede neural artificial. McCulloch e Pitts mostraram que qualquer função computável podia 
ser calculada por alguma rede de neurônios conectados. Donald Hebb mostrou, em 1949, uma forma de 
atualização das intensidades de conexões entre os neurônios, utilizadas para aprendizagem.
Em 1950, Alan Turing, em seu artigo 
intitulado Computer Machinery and 
Intelligence, apresentou a ideia de uma 
máquina que pensasse. Nesse artigo também 
foi apresentado o teste de Turing.
A IA surgiu oficialmente em 1956, com a 
primeira menção ao termo, na conferência em 
Dartmouth College, EUA. A proposta dessa 
conferência, escrita por John McCarthy, Marvin 
Minsky, Nathaniel Rochester e Claude Shannon, 
tinha a intenção de reunir pesquisadores para 
estudar Inteligência Artificial.
No ano seguinte, em 1957, Allen Newell 
e Herbert Simon apresentaram a ideia do Solucionador de Problemas Gerais – General Problem Solver 
“Estudo de como fazer computadores realizarem 
tarefas, em que no momento, as pessoas são 
melhores.” Rich (1988, p. 1)
“É o estudo de conceitos que permitem aos 
computadores serem inteligentes [...] Objetivos: 
tornar os computadores mais úteis e entender os 
princípios que tornam a inteligência possível.” 
Winston (1988, p. 1)
“O ramo da ciência da computação que se preocupa 
com a automação do comportamento inteligente.” 
Luger (2004, p. 1)
“É o estudo dos sistemas que agem de um modo que 
a um observador qualquer pareceria ser inteligente” 
Coppin (2010, p. 4)
IA é um assunto polêmico. Recentemente, em abril 
de 2012, foi publicado um debate na Revista SBC 
Horizontes, sobre o fato de máquinas poderem ou 
não possuir inteligência. O debate foi apresentado na 
forma de dois artigos muito interessantes, o primeiro 
criticando a IA, e o segundo defendendo-a:
• Inteligência Artificial = Alquimia Digital, por 
Cristina Duarte Murta:
http://portal.sbc.org.br/horizontes/doku.php?id=v05n01:15
• Existe sistema inteligente (e vários !), por Seiji Isotani: 
http://portal.sbc.org.br/horizontes/doku.php?id=v05n01:19
Saiba mais!
O teste de Turing é uma forma de lidar com a questão: 
máquinas podem pensar? No teste, se um humano 
interrogar um computador e o interrogador não 
conseguir dizer se o interrogador é uma máquina ou 
um humano, então o computador seria inteligente. 
Mais informações sobre o teste de Turing podem ser 
encontradas nos links: 
• http://www.loebner.net/Prizef/loebner-prize.html;do sistema MYCIN. 
Estas regras são utilizadas pelo mecanismo de inferência para apresentar respostas sobre os tipos de infecções.
As regras do tipo se-então são uma das formas mais utilizadas para representação de conhecimento em 
sistemas especialistas. A regra a seguir possui como antecedente A e como conclusão B.
Sistemas Tutores Inteligentes são sistemas desenvolvidos com o objetivo de auxiliar no processo 
de ensino-aprendizagem, conforme Giraffa (1999): 
Os ITS são programas de computador que utilizam técnicas procedentes da IA para 
representar o conhecimento e levar a termo uma interação com o aluno... O objetivo 
fundamental dos ITS é proporcionar uma instrução adaptada ao aluno, tanto em 
conteúdo como na forma, superando desta maneira alguns dos problemas mais cruciais 
do software educativo na atualidade..
Um exemplo de sistema tutor para ensino de matemática é o Pat2Math. Trata-se de um projeto que 
está sendo desenvolvido no PIPCA/UNISINOS pelo Grupo de Inteligência Artificial aplicada à 
Educação. Conheça esse projeto pelo seguinte endereço eletrônico: http://www.projeto.unisinos.
br/pat2math/
GIRAFFA, L. Uma arquitetura de tutor utilizando estados mentais. Tese de Doutorado. Porto 
Alegre: CPGCC da UFRGS, 1999.
Saiba mais!
http://www.projeto.unisinos.br/pat2math/
http://www.projeto.unisinos.br/pat2math/
31
Se A então B
Esta regra também pode ser escrita usando uma seta para separar antecedente de conclusão:
A → B
Nas regras, podemos expressar também algumas relações lógicas, como e e ou:
Se previsão do tempo é sol e hoje é domingo então passeio no parque.
 5.3 Arquitetura do sistema especialista
Esta breve introdução sobre sistemas especialistas já nos deixa aptos a indagar: Como os sistemas 
especialistas são construídos? Para começarmos a responder a essa pergunta, vamos conhecer a arquitetura de 
um sistema especialista. Um SE apresenta três módulos: memória de trabalho, base de regras e mecanismo de 
inferência, como ilustra a Figura 18.
Figura 18: Arquitetura de um Sistema Especialista.
Fonte: Elaboração própria
A memória de trabalho e a base de regras juntas formam a base de conhecimento, que representa todo 
o conhecimento sobre o domínio do problema. A memória de trabalho armazena o conhecimento sobre o 
problema na forma de uma sequência de caracteres ou até na forma de estruturas de dados mais complexas. A 
forma como o conhecimento é armazenado depende do método de representação do conhecimento (apresentado 
no Módulo 4) utilizado.
A base de regras contém o conjunto de regras que compõem a base de conhecimento. A sintaxe das regras 
pode variar entre os sistemas e pode envolver variáveis a serem instanciadas.
Pense nisso: Como fazer para que os computadores tirem conclusões automaticamente a 
partir de fatos conhecidos?
Resposta: Através do mecanismo de inferência, que é um método formal (no caso da 
lógica) ou heurístico (no caso do conhecimento representado por regras de produção, redes 
semânticas e quadros), que pode ser programado para ser usado como manipulador de base 
de conhecimento, com o fim de deduzirmos algo que não está armazenado na base de fatos 
e conhecimentos.
O mecanismo de inferência manipula a base de conhecimento, os fatos e as regras, a fim 
32
de obter respostas sobre o problema. Veremos com mais detalhes o mecanismo de inferência no próximo item.
 5.4 Mecanismo de inferência
O mecanismo de inferência controla a atividade do sistema no processo de obtenção de conclusões. 
Essas conclusões podem ser obtidas usando o mecanismo de encadeamento para frente ou encadeamento 
para trás. No encadeamento para frente, o mecanismo de inferência inicia-se com os fatos e regras na base 
de conhecimento e tenta encontrar uma sequência de aplicação das regras e fatos que levam à conclusão. 
No encadeamento para trás, o mecanismo de inferência inicia-se com a conclusão e tenta encontrar uma 
sequência de aplicações de regras e fatos que levam a fatos na base de conhecimento.
No encadeamento para frente, o primeiro passo é verificar a base de fatos para encontrar o objetivo; se 
o objetivo faz parte da base de fatos, a resposta afirmativa é retornada. Se o objetivo não fizer parte da base de 
fatos, verifica-se então a base de regras, tentando encontrar a regra em que todos os antecedentes fazem parte 
da base de fatos; a regra encontrada é então aplicada, e sua conclusão é adicionada à base de fatos. A aplicação 
de regras repete-se até que uma solução seja encontrada ou até que não haja nenhuma regra que possa ser 
aplicada; nesse caso, uma resposta negativa é retornada.
No encadeamento para trás, o primeiro passo é verificar a base de fatos para encontrar o objetivo; se o 
objetivo faz parte da base de fatos, a resposta afirmativa é retornada. Se o objetivo não fizer parte da base de 
fatos, verifica-se então a base de regras, tentando encontrar a regra em que o objetivo faz parte da conclusão; 
a regra encontrada é então aplicada, e seu antecedente é o novo objetivo, ou subobjetivo, a ser seguido. A 
aplicação de regras repete-se até que todos os antecedentes ou subojetivos tenham sido atingidos ou até que 
não tenha nenhuma regra que possa ser aplicada; nesse caso, uma resposta negativa é retornada.
Para exemplificar cada um dos tipos de encadeamento, vamos considerar a seguinte base de conhecimento:
Base de regras: Objetivo: F
 R1: B,C → E
 R2: A,B → C
 R3: E,D → F
 R4: C → D
Base de fatos:
 A, B 
No encadeamento para frente, a solução é encontrada partindo do conjunto de fatos conhecidos e 
aplicando as regras cujos antecedentes são conhecidos, até encontrar o objetivo:
 Encadeamento para frente
Regra aplicada Base de fatos
 - A, B
R2 A, B, C
R1 A, B, C, E
R4 A, B, C, E, D
R3 A, B, C, E, D, F
No encadeamento para trás, a solução é encontrada partindo do objetivo, aplicando as regras cujas 
conclusões são desejadas e tornando seus antecedentes os novos objetivos, até que não se tenham mais 
objetivos a serem alcançados:
33
 Encadeamento para trás
Regra aplicada Objetivos Base de fatos
- F A, B
R3 E, D A, B, F
R1 C, D A, B, F, E
R2 D A, B, F, E, C
R4 - A, B, F, E, C, D
A escolha do encadeamento para o mecanismo de inferência pode ser realizada considerando o tipo de 
problema a ser solucionado. O encadeamento para frente funciona melhor quando o número de respostas 
possíveis é grande, em geral em problemas de planejamento, projeto e classificação. O encadeamento para 
trás funciona bem quando há um conjunto pequeno de respostas possíveis para um conjunto grande de estados 
iniciais, em geral em problemas de diagnósticos.
Após definir o tipo de encadeamento, o mecanismo de inferência deve utilizar uma estratégia de busca 
para encontrar fatos e regras na base de conhecimento. As estratégias de busca em um espaço de estados 
podem ser a busca em largura ou em profundidade, conforme vimos no módulo 2. Quando o objetivo tem mais 
de uma estrutura, a busca pela solução pode se dar em largura, trabalhando todos os subobjetivos em paralelo; 
ou em profundidade, encontrando uma sequência completa de proposições para o primeiro subobjetivo antes 
de buscar soluções para os demais. 
Em alguns casos, ao terminar a busca pela solução, é possível encontrar um conjunto de regras que 
satisfazem a situação atual. A escolha de qual regra deve ser empregada é realizada por métodos de resolução 
de conflito. Existem diversas maneiras de decidir qual regra será ativada; por exemplo, ativar a regra que tenha 
correspondido aos fatos mais recentes na base de fatos.
Existe ainda a possibilidade de adicionar incerteza aos fatos e regras, com o intuito de representar 
alguma informação de confiança do especialista. A representação de incerteza pode ser modelada utilizando 
método de Bayes, fatores de certeza, teoria de conjuntos nebulosos, entre outros. Algumas ferramentas para 
implementação de SEs deixam à disposição do programador vários métodos de tratamentode incerteza.
Pense nisso: O sucesso de um SE depende do conhecimento armazenado, regras e fatos, 
que compõem a base de conhecimento. 
Esse conhecimento é obtido através dos especialistas humanos. O especialista pode não 
estar ciente de como usa o conhecimento e algumas soluções adotadas por ele são intuitivas. O 
conhecimento expresso pode ser incompleto, pode pular pontos importantes, pode até mesmo 
ser irrelevante. O grande desafio é evitar informação irrelevante sem bloquear a descoberta de 
conceitos adicionais. 
O método de Bayes, também conhecido como regra de Bayes ou teorema de 
Bayes, é uma equação da teoria da probabilidade que mostra a relação entre 
uma probabilidade condicional e sua inversa. Essa equação serve de base 
para muitos sistemas de IA. A equação de Bayes é dada por:
P(A|B) = P(B|A)P(A)/P(B)
onde P(A) e P(B) são as probabilidades a priori de A e B, e P(A|B) e P(B|A) 
são as probabilidades condicionais.
• RUSSEL, S. NORVIG, P. Inteligência Artificial. Rio de Janeiro: Editora 
Campus, 2004.
Saiba mais!
34
5.5 Exemplo de sistema especialista e ferramentas
Exemplo de um SE da árvore genealógica da família de João:
Fatos:
homem(joão)
mulher(maria)
mulher(ana)
genitor(joão,ana)
genitor(maria,ana)
Regras:
se genitor(X,Y) e mulher(X) então mãe(X,Y)
se genitor(X,Y) e homem(X) então pai(X,Y)
Exemplo de consultas ao SE:
Com o conhecimento adquirido sobre sistemas especialistas, já é possível desenvolver um sistema 
especialista para tomada de decisão. Escolha uma ferramenta e mãos à obra!
Consulta: mulher(maria)
Resposta: sim
O fato mulher(maria) pertence à base de fatos.
Consulta: mulher(teresa)
Resposta: não
A resposta é não, pois o fato mulher(teresa) não 
pertence à base de fatos.
Consulta: genitor(X, ana)
Resposta: joão, maria
Quem é o genitor de ana? Procura por valor para X 
que case com genitor(X,ana) e encontra primeiro 
joão e depois maria.
Consulta: mãe(X,ana)
Resposta: maria
Quem é a mãe de ana? Utiliza a regra: se genitor(X,Y) 
e mulher(X) então mãe(X,Y). Instancia a variável 
Y com ana e procura um valor para variável X que 
satisfaça genitor(X, ana) e mulher(X).
Existem algumas boas ferramentas gratuitas para 
construção de SEs disponíveis:
• ExpertSinta, shell brasileira para construção de SEs: 
http://www.lia.ufc.br/~bezerra/exsinta/
• Prolog, linguagem lógica: http://www.swi-prolog.
org/
• CLIPS (C Language Interface Production System), 
escrito em C: http://clipsrules.sourceforge.net/
• Jess, baseado no CLIPS, mas desenvolvido em Java: 
http://herzberg.ca.sandia.gov/jess/index.shtml
• Drools, escrito em Java: http://www.jboss.org/
drools
Saiba mais!
http://www.swi-prolog.org/
http://www.swi-prolog.org/
http://www.jboss.org/drools
http://www.jboss.org/drools
35
Exercícios
1. Qual a forma de representação de conhecimento mais utilizada em sistemas especialistas?
2. Descreva como o mecanismo de inferência é utilizado em sistemas especialistas.
3. Pesquise sistemas implementados para a educação que utilizem sistemas especialistas.
IA na Educação:
Bittencourt et al. (2006) apresentam um sistema de autoria para construção de ambientes interativos de 
aprendizagem baseados em agentes. Um dos agentes implementados utiliza raciocínio baseado em regras.
Seffrin, Rubi, e Jaques (2011) apresentam o módulo cognitivo do sistema tutor PAT2Math, que foi implementado 
como um sistema especialista, baseado em regras, do domínio de álgebra.
• BITTENCOURT, I. COSTA, C.N.E. TADEU, M. BEZERRA, C. Um sistema de autoria para construção 
de ambientes interativos de aprendizagem baseado em agentes. XVII Simpósio Brasileiro de Informática na 
Educação (SBIE), Brasília, 2006.
• SEFFRIN, H. RUBI, G. JAQUES, P. O Modelo cognitivo do sistema tutor inteligente PAT2Math. XXII 
Simpósio Brasileiro de Informática na Educação (SBIE), Aracaju, 2011. 
Disponível em: http://www.projeto.unisinos.br/pat2math/papers/SBIE_2011.pdf
36
Referências
BARANAUSKAS, M. C. C. et. al. Uma taxonomia para ambientes de aprendizado baseados no 
computador. In: VALENTE, J. A. (Org.). O computador na sociedade do conhecimento. Campinas: NIED/
UNICAMP, 1999.
BITTENCOURT, G. Inteligência artificial: ferramentas e teorias. Florianópolis: Editora da UFSC, 2006.
BITTENCOURT, I. COSTA, C.N.E. TADEU, M. BEZERRA, C. Um sistema de autoria para construção 
de ambientes interativos de aprendizagem baseado em agentes. XVII Simpósio Brasileiro de Informática 
na Educação (SBIE), Brasília, 2006.
CORMEN, T. H. RIVEST, R. L. LEISERSON, C. E. Algoritmos: teoria e prática. Rio de Janeiro: Editora 
Campus, 2002.
COPPIN, B. Inteligência artificial. Rio de Janeiro: LTC, 2010.
GIRAFFA, L. Uma arquitetura de tutor utilizando estados mentais. Tese de Doutorado. Porto Alegre: 
CPGCC da UFRGS, 1999.
HAYKIN. S. Redes neurais: princípios e práticas. Porto Alegre: Bookman, 2001.
HOBMEIR NETO, A. DIRENE, A. SILVA, F. BONA, L. GARCÍA, L. CASTILHO, M. SUNYÉ, M. Uma 
abordagem dialógica alternativa para a aquisição de habilidades táticas em jogos educacionais. XIX 
Simpósio Brasileiro de Informática na Educação (SBIE), Fortaleza, 2008.
JACKSON Jr, P. Introduction to artificial intelligence. New York: Dover, 1985.
LUGER, G. F. Inteligência artificial: estruturas e estratégias para a solução de problemas complexos. 4ª ed. 
Porto Alegre: Bookman, 2004.
MACEDO, A.C.O. BOTELHO, S.S.C. Considerando a dinâmica do processo de aprendizado em sistemas 
de autoria e tutoriamento. XVII Simpósio Brasileiro de Informática na Educação (SBIE), Brasília, 2006.
NWANA, H.S. Intelligent tutoring systems: an overview. Artificial Intelligence Review, v. 4, 1990.
ONG, J. RAMACHANDRAN, S. Intelligent tutoring systems: the what and the how. Learning Circuits, 
American Society for Training and Developing (ASTD), 2000.
PASSOS, E. Inteligência artificial e sistemas especialistas ao alcance de todos. Rio de Janeiro: LTC, 1989.
REZENDE, S.O. Sistemas inteligentes: fundamentos e aplicações. Barueri: Editora Manole, 2003.
RICH, E. Inteligência artificial. São Paulo: McGraw-Hill, 1988.
RUSSEL, S. NORVIG, P. Inteligência artificial. Rio de Janeiro: Editora Campus, 2004
37
SEFFRIN, H. RUBI, G. JAQUES, P. O Modelo cognitivo do sistema tutor inteligente PAT2Math. XXII 
Simpósio Brasileiro de Informática na Educação (SBIE), Aracaju, 2011.
SCHMITZ, A. LÓPEZ, O.C. AVILA R.F. Ferramenta de autoria de sistemas tutores inteligentes 
construindo o modelo do domínio do conhecimento com redes semânticas. II Congresso Brasileiro de 
Computação – CBComp 2002 Informática na Educação. Itajaí, 2002.
TURING, A.M. Computing machinery and intelligence. Mind, 59, 433-460, 1950.
VICCARI, R. Um tutor inteligente para a programação em lógica – idealização, projeto e desenvolvimento. 
Tese de Doutorado. Universidade de Coimbra, 1990.
WINSTON, P.H. Inteligência artificial. Rio de Janeiro: LTC, 1988.
WOOLDRIDGE, M. An introduction to multiagent systems. United Kingdom: John Wiley and Sons, 2009.• http://aaai.org/AITopics/TuringTest
Saiba mais!
5
(GPS), um programa capaz de demonstrar teoremas matemáticos.
Em 1958, McCarthy definiu a linguagem de programação de alto nível LISt Programming (LISP), que 
utiliza listas como sua estrutura de dados principal. A linguagem LISP é muito utilizada em IA até os dias 
de hoje.
O início da IA foi marcado de muita expectativa e otimismo. Na primeira década de pesquisa em IA, 
surgiu a resolução de problemas por meio de busca, que solucionou com sucesso problemas pequenos e 
fáceis. Ao se constatar que as técnicas desenvolvidas até o momento não conseguiriam resolver problemas 
grandes e complexos, surgiram as principais críticas em relação à IA.
Uma alternativa para resolução de problemas por meio de busca foi utilizar conhecimento específico 
sobre o domínio do problema. Como exemplo dessa abordagem, surgiram os Sistemas Baseados em 
Conhecimento (SBC), sendo o DENDRAL, de 1969, o primeiro exemplo.
 A partir do DENDRAL, a pesquisa em sistemas especialistas, que são baseados no conhecimento 
específico sobre o domínio do problema, se aprofundou. Na década de 1980, houve uma reinvenção dos 
sistemas especialistas e também o retorno das redes neurais, sendo aplicados com sucesso em diversos 
problemas. O tema das redes neurais pode ser mais explorado no texto de Haykin (2001).
Na década de 1990, a IA passou a utilizar o conceito de agentes inteligentes. O livro sobre Inteligência 
Artificial do Russel e Norvig (1995) é importante por apresentar todos os conceitos de IA envoltos na teoria 
de agentes inteligentes. Nessa concepção, um agente inteligente percebe o ambiente e escolhe suas ações 
de modo a melhor alcançar seus objetivos. O processo de escolha das ações a serem tomadas pelo agente é 
realizado utilizando diferentes métodos da IA, como sistemas especialistas ou redes neurais. O paradigma 
de agentes inteligentes evoluiu para a utilização de não apenas um, mas uma sociedade de agentes, chamada 
de sistemas multiagentes (Wooldridge, 2009). 
Alguns fatos marcaram a década de 1990. Em 1997, o computador Deep Blue venceu uma partida de 
xadrez do então campeão mundial desse jogo, Gary Kasparov. Em 1999, a Sony lançou um robô cachorro 
de estimação, chamado AIBO, que podia entender e obedecer a comandos de voz.
Em 2005, o DARPA Grand Challenge, uma prova para veículos não tripulados, foi vencida pelo Stanley, 
um veículo da Volkswagen, projetado por uma equipe da Universidade de Stanford.
De maneira resumida, a história da IA pode ser subdividida em clássica, romântica e moderna. Segundo 
Bittencourt (2006):
• Clássica (1956-1970), com o objetivo de simular a inteligência humana.
• Romântica (1970-1980), com o objetivo de simular a inteligência humana em situações pré-
determinadas.
• Moderna (1980-1990), com o objetivo de simular o comportamento de um especialista humano na 
solução de problemas em um domínio específico.
As mudanças nos objetivos da IA com o passar dos anos mostram uma redução gradativa nas 
expectativas, sendo atualmente um objetivo da IA construir sistemas computacionais úteis que, aos olhos 
de um observador externo, apresentem um comportamento inteligente na realização de tarefas e resolução 
de problemas.
Para conhecer mais sobre redes neurais artificiais:
• Um tutorial introdutório pode ser encontrado no link:
http://www2.icmc.usp.br/~andre/research/neural/index.htm
• Um livro clássico sobre o assunto:
HAYKIN. S. Redes neurais: princípios e práticas. Porto Alegre: Bookman, 2001.
Saiba mais!
6
1.3 Inteligência Artificial aplicada 
à Educação (IAAE)
Uma das áreas de aplicação da Inteligência Artificial 
é a de Informática na Educação. A Informática na 
Educação está relacionada à inserção do computador 
nas atividades de ensino-aprendizagem de conteúdos 
curriculares. Em específico, quando falamos de IA 
aplicada na educação, somos remetidos a utilizar técnicas 
de IA em programas computacionais implementados 
com o objetivo de auxiliar no processo de educação, 
como ilustrado na Figura 1.
IAAE é uma área interdisciplinar que envolve 
cientistas da computação, psicólogos e educadores e que 
busca construir softwares que consigam personalizar as 
atividades de ensino. Silveira (2006) apresenta a IAAE 
ressaltando que um sistema de IAAE é:
um sistema computacional para o ensino que tem algum grau de tomada de decisão autônoma em 
relação às suas interações com os usuários (estudantes). Esse processo de decisão é necessariamente 
feito on-line, durante as interações do sistema com os usuários e, geralmente o sistema precisa acessar 
vários tipos de conhecimento e processos de raciocínio para habilitar tais decisões a serem tomadas.
Os usos educacionais mais conhecidos da IA são Sistemas Tutores Inteligentes (STIs) e ambientes de 
aprendizado adaptativos e interativos.
Quanto aos STIs, diversas pesquisas já comprovaram que o aproveitamento do ensino um-a-um, um 
professor/tutor por aluno, é muito mais efetivo do que nas salas tradicionais em que temos um professor para 
uma turma de alunos (Ong; Ramachandran, 2000). No entanto, o custo da relação um-a-um é muito alto, 
tornando interessante a possibilidade de se utilizar um sistema tutor que consiga acompanhar individualmente 
cada aluno durante as atividades, respondendo a seus questionamentos e fornecendo dicas e exemplos.
Segundo Nwana (1990), STIs são programas de computador projetados para incorporar técnicas de 
IA em tutores que sabem o que, para quem e como ensinar. O projeto e o desenvolvimento de STIs devem 
ser baseados em pesquisas das áreas de ciência da computação, psicologia cognitiva e educação, sendo um 
trabalho interdisciplinar e não trivial.
Na perspectiva do aluno, segundo Viccari (1990), STIs são programas que, ao interagir com os alunos, 
O progresso recente das pesquisas em IA pode ser acompanhado através dos eventos científicos na área. 
No Brasil, o evento anual mais importante sobre Inteligência Artificial é o SBIA:
• Simpósio Brasileiro de Inteligência Artificial (SBIA):
http://ceia.labic.icmc.usp.br/index.php?p=sbia&l=SBIA
Internacionalmente, podemos destacar dois eventos bianuais:
• International Joint Conference on Artificial Intelligence (IJCAI):
http://ijcai.org/
• European Conference on Artificial Intelligence (ECAI):
http://www.eccai.org/ecai.shtml
Saiba mais!
Figura 1: Inteligência Artificial aplicada na Educação.
Fonte: Renjith Krishnan. 3d_Men_E_Learning. Royalty 
free image. Disponível em: http://www.freedigitalphotos.
net/images/Internet_g170- __p57082.html.
 Acesso em: novembro de 2012.
7
modificam suas bases de conhecimento, possuindo capacidade de aprender e adaptar as estratégias de ensino 
de acordo com as interações com o aluno. Dessa maneira, STIs constroem um modelo cognitivo do aluno 
pela sua percepção por meio da interação. No STI descrito por Viccari, a interação é alcançada através de 
perguntas realizadas pelo sistema tutor ao aluno e subsequente resposta do sistema, apresentando ao aluno 
conteúdos instrucionais condizentes com a experiência adquirida pelo aluno.
Os ambientes interativos de aprendizado são também sistemas computacionais para auxiliar no processo 
de aprendizagem, que diferem dos STIs pelo fato de o controle da interação ser do aluno e não do sistema, 
segundo Baranauskas (1999, p.54).
Nos Ambientes Interativos de Aprendizado, o aprendizado é entendido como a construção individual do 
conhecimento a partir de atividades de exploração, investigação e descoberta. Sistemas, nessa classe, 
são um análogo dos sistemas físicos estudados por cientistas: não ensinam nem instruem, apenas têm 
um determinado comportamento.
Nos ambientes interativos de aprendizado, o conhecimento pode ser construído com o auxílio de 
ferramentas de simulação, modelagem e programação. Segundo Baranauskas (1999, p.67).
Embora os usos iniciais do computador na Educação enfatizassem o uso da tecnologia como uma 
alternativa para a prática de transferir informação ao aluno (instrucionismo), as aplicaçõesmais recentes 
têm enfatizado o uso do computador como uma ferramenta educacional que requer dos estudantes 
muito mais envolvimento (é o caso de simulação, modelagem, programação).
Vale notar que, em sistemas tutores 
inteligentes ou em ambientes interativos de 
aprendizado, os sistemas computacionais 
desenvolvidos para sistemas de aprendizado 
baseados em computador envolvem aplicação 
de técnicas e conceitos de IA na modelagem 
e na representação dos aspectos relevantes 
do problema. Essa área está em constante 
evolução e seu avanço pode ser acompanhado 
através das publicações especializadas.
Neste módulo vimos uma introdução à 
disciplina de IA, em que foram apresentadas 
algumas definições para IA, como também um 
pouco da sua história. Dedicamos uma parte 
do módulo para conhecer um pouco sobre as 
aplicações de IA na educação. Durante todo o 
módulo, foram dados vários links para sites em 
que será possível buscar informações atuais 
sobre os temas relacionados a esta disciplina. 
Esses links poderão ser utilizados para consulta durante todos os próximos módulos da disciplina de IAAE.
Exercícios
1. O que é inteligência artificial?
2. Qual a utilidade da IA para a educação?
3. Pesquise sobre Alan Turing e sua importância para a inteligência artificial.
Publicações especializadas na área de IA aplicada na 
Educação:
• Revista Brasileira de Informática na Educação 
(RBIE): 
http://www.br-ie.org/pub/index.php/rbie
• International Journal on Artificial Intelligence in 
Education (AIED)
http://iaied.org/journal/
Evento nacional:
• Simpósio Brasileiro de Informática na Educação 
(SBIE) que tem trilhas específicas para Inteligência 
Artificial aplicada à Educação:
http://www.br-ie.org/index.php/eventos
Saiba mais!
8
Unidade
Neste módulo e no seguinte, trataremos da resolução de problemas utilizando métodos de busca. 
Veremos como formular um problema e como empregar o método de busca apropriado para buscar 
uma solução. A resolução de problemas por meio de busca é um ramo muito importante da IA, uma 
vez que é necessária para solucionar uma grande variedade de problemas.
2.1 Espaço de busca
Muitos dos problemas de IA podem ser representados por espaços de estados ou espaços de busca. Um 
espaço de busca é uma representação do conjunto de possíveis escolhas de um dado problema. O espaço de 
busca consiste em um conjunto de estados que estão conectados, em que cada conexão representa uma ação 
que pode ser executada para ir de um estado a outro. As ligações entre um estado e outro são chamadas de 
transições de estados.
Em um problema de busca, parte-se de um determinado estado, chamado de inicial, e procura-se por 
um ou mais estados objetivos. Um objetivo é um conjunto de estados do espaço de busca, sendo estes os 
estados em que o objetivo é satisfeito. A busca é o processo de procurar a sequência de ações que leva a um 
determinado objetivo. A procura ou busca pelos estados objetivos retorna um caminho possível entre o estado 
inicial e o objetivo, sendo este caminho uma solução para o problema. A qualidade de uma solução é medida 
pelo custo do caminho: uma solução ótima terá o menor custo de caminho entre todas as soluções.
 2.2 Formulação do problema
A primeira etapa para a solução de um problema é sua formulação, ou seja, o processo de escolher quais 
ações e estados devem ser considerados, dado um objetivo. Na formulação do problema, vamos considerar:
• o conjunto de estados possíveis do mundo;
• o estado inicial em que o problema se encontra;
• um conjunto de ações que permitam passar de um estado a outro;
• um teste de objetivo, que verifica se está em um estado em que o objetivo foi atingido;
• o custo do caminho, que mede o custo de todos os passos realizados do estado inicial até o estado objetivo.
Para entendermos melhor como funciona a formulação do problema, vamos ver a formulação para um 
problema conhecido.
Problema: o quebra-cabeça de oito peças consiste em uma grade 3x3, com números de 1 a 8 e um 
espaço vazio. As peças podem ser deslocadas dentro da grade, nas direções cima, baixo, esquerda ou direita, 
sempre para um espaço vazio. O objetivo do quebra-cabeça é começar com qualquer configuração das peças 
e deslocá-las até atingir a configuração em que os números estão ordenados com o espaço vazio na posição 
(3,3), como mostra a Figura 2.
Esta unidade tem como objetivos:
• Compreender os conceitos relacionados à resolução de problemas por meio de busca com métodos 
não informados.
• Entender o espaço de busca.
• Elaborar a formulação do problema.
• Conhecer árvores de busca.
• Empregar os métodos de busca não informada.
• Comparar os métodos de busca não informada.
Resolução de problemas por meio de busca: 
métodos não informados 2
9
Figura 2: Quebra-cabeça de oito peças na sua configuração objetivo.
Fonte: Elaboração própria
Formulação para o problema do quebra-cabeça de 8 peças. O estado inicial e objetivo podem ser vistos 
na Figura 3:
• estados = a posição de cada uma das 8 peças e do espaço vazio em um dos 9 quadrados;
• estado inicial = qualquer um dos estados possíveis;
• teste de objetivo = ordenado, com branco na posição [3,3];
• as ações mover branco para (esquerda, direita, cima e baixo);
• custo do caminho = número de passos da solução (cada passo com custo 1).
Figura 3: Estados para o quebra-cabeça dos 8 números. 
Fonte: Elaboração própria
2.3 Árvore de busca
Após a formulação do problema, é necessário resolvê-lo, o que pode ser feito a partir da busca em todo 
o espaço de estados. Em muitos casos, o espaço de estados pode ser representado por uma árvore de busca. 
Uma árvore é composta por um conjunto de nós, sendo que cada nó representa um estado do espaço de busca. 
As ações ou transições de estados são representadas pelos arcos da árvore.
O nó raiz da árvore de busca corresponde ao estado inicial do problema. A partir do nó raiz, verificam-se 
quais ações podem ser executadas, sendo que cada ação leva a outro nó na árvore, que é conhecido como nó 
filho do nó raiz. Os nós que não têm filhos são chamados nós folhas. Os nós entre a raiz e as folhas são os nós 
internos. Cada nó interno possui um nó pai e pode ter vários nós filhos. O fator de ramificação de um nó é o 
número de filhos que este nó possui.
A árvore possui níveis: a raiz está no nível 0 (zero), os filhos da raiz estão no nível 1 (um) e assim por 
diante. A profundidade da árvore é dada pelo seu nível máximo mais um.
Um caminho na árvore de busca consiste em uma sequência de nós. Um caminho de apenas um nó é um 
caminho de comprimento 0 (zero). Um caminho de comprimento 1 (um) liga dois nós. Um caminho é dito 
completo se ele parte da raiz e chega até a um nó objetivo. 
A Figura 4 mostra uma árvore com 13 nós e profundidade 4. O nó raiz possui 2 filhos. O filho direito do 
nó raiz possui 3 filhos e o filho esquerdo da raiz possui 2 filhos. A árvore possui 8 nós folha, dos quais 3 estão 
no nível 2 e 5 estão no nível 3.
10
Figura 4: Árvore de busca.
Fonte: Elaboração própria
Com essas informações sobre árvore de busca, vamos voltar para o nosso problema do quebra-cabeça de 
8 peças, para o qual já fizemos a formulação, e visualizar um esboço para sua árvore de busca na Figura 5. O 
fator de ramificação da árvore é aproximadamente 3:
• fator de ramificação 4 quando o branco está no meio (cima, baixo, esquerda, direita);
• fator de ramificação 3 quando o branco está nas laterais (cima, baixo, esquerda) ou (cima, baixo, direita);
• fator de ramificação 2 quando o branco está nas quinas (cima e esquerda) ou (cima e direita) ou (baixo e 
esquerda) ou (baixo e direita).
A profundidade da árvore é de cerca de 20 níveis. Ou seja, partindo de um estado inicial qualquer, são 
necessários aproximadamente 20 passos para chegar ao estado final.
Figura 5: Árvore de busca para o quebra-
cabeça de 8 peças.
Fonte: Elaboração própria
11
A raiz da árvore é o estado inicial do problema. A partir da raiz, podem-se aplicar três ações: mover o branco 
para cima, para baixoe para a esquerda. Cada uma dessas ações leva a um nó filho da raiz. Sucessivamente, 
as ações são aplicadas aos nós filhos, que geram outros nós, até que encontremos o nó objetivo, ou seja, com 
os números ordenados.
A busca começa pela raiz da árvore, que corresponde ao estado inicial. O primeiro passo da busca é testar 
se a raiz é o objetivo; se não for o objetivo, a busca prossegue pela expansão do nó raiz, gerando um conjunto 
de estados sucessores. Em seguida, escolhe-se um dos estados para prosseguir e reservam-se os outros para 
serem considerados futuramente, se necessário. As técnicas de busca se diferenciam em como escolhem quais 
estados serão considerados e quais serão deixados de lado.
Os métodos de busca são ditos não informados quando não recebem nenhuma informação sobre o 
problema além da sua definição. Já os métodos de busca informados recebem alguma informação adicional 
sobre onde procurar as soluções. 
 2.4 Busca não informada ou cega
A busca cega ou busca sem informação é um tipo de busca em que as informações conhecidas para 
a solução do problema são apenas as da definição do problema e nada mais. O método de busca é baseado 
na aplicação de uma ação em um estado e a verificação de se o novo estado alcançado é ou não um estado 
objetivo. Os dois tipos de busca cega mais conhecidos são a busca em largura e a busca em profundidade. 
Estas duas buscas são chamadas de busca de força bruta ou busca exaustiva, pois percorrem cada nó da 
árvore, em ordem, até encontrar um estado objetivo.
Busca em largura
A busca em largura é uma estratégia simples de busca em que o nó raiz é expandido primeiro; em seguida 
todos os sucessores da raiz são expandidos, depois os sucessores desses nós e assim por diante, ou seja, todos 
os nós em uma profundidade são expandidos antes que os nós da camada seguinte sejam expandidos. 
Podemos acompanhar na Figura 6 um exemplo de uma árvore e os passos para percorrê-la em largura. 
Vejam: 
Nesse exemplo, vimos um caso em que toda a árvore é percorrida pelo processo de busca em largura. No 
entanto, na maioria dos casos, a árvore não precisa ser toda percorrida. A busca termina quando o nó objetivo 
é encontrado. Suponha que o nó c seja o nó objetivo; assim, no item (iv), a busca seria terminada, sem precisar 
percorrer os demais nós. 
No item (i) , vemos a árvore de busca. 
No item (ii), temos o nó raiz como o nó que está sendo expandido, marcado em cor-de-rosa. Os nós 
sucessores da raiz são os nós b e c, marcados em amarelo. 
No item (iii), o nó b é expandido, sendo marcado em cor-de-rosa, e os seus nós sucessores, d e e, são 
marcados de amarelo. 
No item (iv), o nó c é expandido, sendo marcado em cor-de-rosa, e os seus nós sucessores, f e g, são 
marcados em amarelo. Neste ponto, todos os nós do nível 1, b e c, foram expandidos. 
No item (v), o nó d é expandido, sendo marcado em cor-de-rosa; como ele não tem sucessores, nenhum 
outro nó é marcado em amarelo. 
No item (vi), o nó e é expandido, sendo marcado em cor-de-rosa; como ele não tem sucessores, nenhum 
outro nó é marcado em amarelo. 
Nos itens (vii) e (viii), os nós f e g são expandidos. Neste ponto, todos os nós do nível 2, d, e, f e g, foram 
expandidos.
12
Figura 6: Passo a passo da busca em largura. 
Fonte: Elaboração própria
De maneira mais simplificada, podemos ver um esquema do percurso de busca em largura na Figura 7. 
As setas numeradas indicam o caminho do percurso, que começa pela raiz, depois continua por todos os nós 
sucessores (b e c) e em seguida pelos nós no nível seguinte (d, e, f, e g).
Figura 7: Busca em largura.
Fonte: Elaboração própria
Nos casos em que a árvore de busca tem fator de ramificação muito alto, ou seja, os nós têm muitos filhos, 
a busca em largura não é uma boa opção, pois necessitaria de muita memória para armazenar todos os nós 
13
sucessores na fila para serem expandidos. No exemplo da Figura 6, os nós que aguardam ser expandidos são 
os nós marcados em amarelo.
Busca em profundidade
A busca em profundidade percorre o caminho da árvore até o nível mais profundo antes de seguir um 
novo caminho. Este percurso na árvore é realizado expandindo sempre o nó mais profundo na borda atual da 
árvore de busca.
A Figura 8 mostra um exemplo de uma árvore e os passos para percorrê-la em profundidade. Vejam:
No item (i) , vemos a árvore de busca, a mesma utilizada no exemplo da busca em largura. 
No item (ii), temos o nó raiz como o nó que está sendo expandido, marcado em cor-de-rosa. Os nós 
sucessores da raiz são os nós b e c, marcados em amarelo. 
No item (iii), o nó b é expandido, sendo marcado em cor-de-rosa, e os seus nós sucessores, d e e, são 
marcados em amarelo. 
No item (iv), o nó d é expandido, sendo marcado em cor-de-rosa; como ele não tem sucessores, nenhum 
outro nó é marcado em amarelo. Neste ponto, atingimos a profundidade máxima da árvore. 
No item (v), o nó e é expandido, sendo marcado em cor-de-rosa; como ele não tem sucessores, nenhum 
outro nó é marcado em amarelo. Neste ponto, todos os nós da subárvore esquerda foram expandidos e 
vamos agora percorrer a subárvore direita. 
No item (vi), o nó c é expandido, sendo marcado em cor-de-rosa, e os seus nós sucessores, f e g, são 
marcados em amarelo.
 Nos itens (vii) e (viii), os nós f e g são expandidos, respectivamente.
Figura 8: Passo a passo da 
busca em profundidade.
Fonte: Elaboração própria
14
Do mesmo modo que na busca em largura, a busca termina quando o nó objetivo é encontrado. Suponha 
que o nó e seja o nó objetivo; assim, no item (v), a busca seria terminada, sem precisar percorrer os demais nós.
De maneira mais simplificada, podemos ver um esquema do percurso de busca em profundidade na Figura 
9. As setas numeradas indicam o caminho do percurso, que começa pela raiz, e percorre um caminho até seu 
nível mais profundo (a, b e d) e depois percorre os demais caminhos, sendo que para cada caminho a busca vai 
até o seu nó mais profundo, nó folha, antes de voltar.
Figura 9: Busca em profundidade. 
Fonte: Elaboração própria
Uma situação em que o método de busca em profundidade não funciona bem é quando a árvore de busca 
apresenta caminhos muito longos ou até infinitos, que não levam ao objetivo. Considere a árvore da Figura 
10. Nela, a subárvore esquerda possui uma profundidade muito maior do que a subárvore direita, e o objetivo 
está na subárvore direita. Neste caso, a busca percorre toda a subárvore esquerda, um caminho muito longo 
percorrendo os nós a, b, d, g, i, j, k, l, h, e e, por fim, c, antes de encontrar a solução. Se o caminho da subárvore 
esquerda fosse não apenas maior, mas infinito, a busca nunca terminaria, não encontrando a solução.
Figura 10: Exemplo de busca em profundidade.
Fonte: Elaboração própria
15
2.5 Propriedades dos métodos de busca
Existem várias propriedades importantes dos métodos de busca que devem ser consideradas para a escolha 
do método mais apropriado para um determinado problema. As propriedades complexidade, completude e 
otimalidade são brevemente descritas a seguir para depois compararmos os métodos de busca apresentados 
segundo essas propriedades.
A complexidade de um método de busca está relacionada com a descrição de quão eficiente o método é 
em termos de tempo e espaço. Em relação ao tempo, consideramos a quantidade de tempo que o método leva 
para encontrar uma solução, ou seja, um estado objetivo. Em relação ao espaço, consideramos a quantidade 
de memória que o método utiliza para realizar o procedimento de busca. Para denotarmos a complexidade 
de um método, é comum utilizar a notação O. A busca em largura tem complexidade O(bd+1) e a busca em 
profundidade tem complexidade O(bm), em que b é o fator de ramificação, d é a profundidade da solução mais 
rasa e m é a profundidade máxima da árvore.
É importante observar a complexidade de um método de busca, pois um método ineficiente pode ter um 
desempenho aceitável para um problema pequeno, porém pode gastar um tempo inaceitavelmente longo para 
umproblema grande.
A completude de um método de busca 
está relacionada à propriedade de o método 
encontrar uma solução, se existir alguma. 
Assim, um método de busca é dito completo 
se ele encontrar o estado objetivo. A busca 
em largura é completa, mas a busca em 
profundidade não é, pois pode percorrer um 
caminho infinito e nunca chegar a um nó 
objetivo.
A otimalidade de um método de busca 
versa sobre a propriedade de o método garantir 
achar a melhor solução que existir. Assim, um 
método ótimo é aquele que encontra a melhor 
solução, ou seja, encontra o caminho que envolva o menor número de passos até seu objetivo. A busca em 
largura é um método ótimo, mas a busca em profundidade não é, pois oferece a primeira solução que encontra, 
que pode não ser a melhor que exista.
Comparação entre a busca em largura e a busca em profundidade 
O uso da busca em largura é adequado se a árvore de busca tiver caminhos muito profundos e se o nó 
objetivo estiver em uma parte mais rasa, ou seja, próximo da raiz da árvore. Porém, seu uso não é apropriado 
quando o fator de ramificação da árvore for muito alto.
Além disso, a busca em largura não é indicada na situação em que todos os caminhos da árvore de 
busca levam a um nó objetivo com caminhos de comprimentos semelhantes. Nessa situação, a busca em 
profundidade encontraria primeiro o nó objetivo. 
A comparação entre os métodos de busca cega segundo os critérios de completude, complexidade (tempo 
e espaço) e otimalidade pode ser vista na Tabela 1.
EXEMPLIFICANDO: Uma árvore com fator de ramificação 3, profundidade máxima 5 e profundidade 
da solução mais rasa 2 possui, para busca em largura O(33) e, para busca em profundidade, O(35). Nesse 
exemplo, a busca em largura seria a melhor opção.
Os assuntos de complexidade, completude e 
otimalidade de algoritmos podem ser aprofundados 
consultando os seguintes livros:
• CORMEN, T. H.; RIVEST, R. L.; LEISERSON, 
C. E. Algoritmos - Teoria e Prática. Rio de Janeiro: 
Editora Campus, 2002.
• RUSSEL, S.; NORVIG, P. Inteligência Artificial. 
Rio de Janeiro: Editora Campus, 2004.
Saiba mais!
16
Tabela 1: Comparação entre busca em largura e busca em profundidade.
Exercícios
1. O que é um espaço de busca?
2. Descreva como funciona a busca em uma árvore de busca.
3. Pesquise sobre outros métodos de busca cega além da busca em largura e da busca em 
profundidade.
Propriedade Busca em largura Busca em profundidade
Completa Sim, se b é finito Não
Tempo O(bd+1) O(bm)
Espaço O(bd+1) O(bm)
Ótima Sim Não
Fonte: Elaboração própria
Outros métodos de busca cega que são variações da busca em largura 
e da busca em profundidade são a busca de custo uniforme e a busca 
com aprofundamento iterativo. Mais informações sobre essas técnicas 
de busca podem ser encontradas nos livros:
• COPPIN, B. Inteligência Artificial. Rio de Janeiro: LTC, 2010.
• RUSSEL, S.; NORVIG, P. Inteligência Artificial. Rio de Janeiro: 
Editora Campus, 2004.
Saiba mais!
IA na Educação:
No trabalho de Macedo e Botelho (2006), um curso é modelado por um grafo em um sistema tutor 
inteligente, em que os nós representam os conteúdos e os arcos, os relacionamentos entre os conteúdos. 
O sistema utiliza busca em largura e busca em profundidade para encontrar os caminhos no grafo.
• MACEDO, A.C.O.; BOTELHO, S.S.C. Considerando a dinâmica do processo de aprendizado em 
sistemas de autoria e tutoriamento. XVII Simpósio Brasileiro de Informática na Educação (SBIE), 
Brasília, 2006. Disponível em: www.lbd.dcc.ufmg.br/colecoes/sbie/2006/001.pdf 
17
Unidade
Começamos no módulo anterior a tratar do assunto de resolução de problemas por meio de busca. Vimos 
dois métodos de busca: em largura e em profundidade. Os métodos vistos são chamados de busca cega 
ou não informada e, em alguns casos, representam o melhor que se tenha a fazer. Porém, na maioria das 
vezes são métodos ineficientes, pois procedem sistematicamente analisando estados e comparando-os com o 
estado objetivo na busca de uma solução. Essa situação pode ser melhorada quando há informação adicional 
que ajude a guiar o processo de busca, ajudando a encontrar a solução de uma maneira mais eficiente do que 
a busca de forma exaustiva.
Neste módulo, veremos como utilizar informação para melhorar a busca, estudando dois tipos de métodos 
de busca informada: a busca pela melhor escolha e a busca local. Também trataremos da utilização da busca 
informada para solucionar problemas de jogos.
3.1 Busca informada
Métodos de busca informada utilizam informações sobre os nós que ainda não foram explorados, ajudando 
na tarefa de escolher qual o próximo nó a ser examinado. Quanto melhor for a informação disponível para 
escolha do próximo nó, menor será o número de nós que terão que ser examinados antes de se encontrar uma 
solução.
Se tivéssemos à disposição uma função de avaliação, que determinasse a distância de um nó ao nó 
objetivo, denotada por f(n), em que n é um nó da árvore, poderíamos selecionar para expansão o nó que tivesse 
o menor valor para a função f(n). No entanto, nem sempre esta informação exata está disponível. Nesses casos, 
a informação adicional utilizada nos métodos de busca informada é representada por uma função heurística, 
que fornece um custo estimado do melhor caminho entre um nó n e um nó objetivo. Vamos denotar a função 
heurística por h(n). Se n for o nó objetivo, então h(n) = 0, ou seja, o custo estimado para chegar a um objetivo, 
estando nele, é zero.
 3.2 Busca pela melhor escolha
A busca pela melhor escolha é uma abordagem em que a escolha do nó para ser expandido é baseada em 
uma função de avaliação f(n). No entanto, se tal função fosse conhecida, não haveria uma busca, mas poderia 
se seguir diretamente do estado inicial para o objetivo. Assim, a busca pela melhor escolha utiliza o estado que 
aparentemente é o melhor, utilizando para isso uma função heurística. Veremos a seguir dois tipos de busca 
pela melhor escolha: a busca gulosa e a busca A*.
Busca gulosa
A busca gulosa pela melhor escolha procura expandir o nó mais próximo ao objetivo seguindo a intuição 
Esta unidade tem como objetivos:
• Compreender os conceitos relacionados à resolução de problemas por meio de busca com métodos 
informados.
• Distinguir os métodos informados dos não informados.
• Conhecer os métodos de busca pela melhor escolha.
• Valorizar o uso de uma boa heurística.
• Conhecer os métodos de busca local.
• Associar métodos de busca com jogos.
Resolução de problemas por meio de busca: 
métodos informados3
18
de que isso a levará mais rápido ao objetivo. A busca pela solução avalia os nós usando uma função heurística: 
f(n) = h(n). Os métodos de busca gulosa costumam ser eficientes na maioria dos casos; porém, no pior caso, 
podem nunca encontrar uma solução.
Na Figura 11, podemos acompanhar o percurso de busca realizado utilizando o método de busca gulosa, 
em que os custos da função f(n) estão marcados ao lado dos respectivos nós. No item (i), a partir do nó raiz 
temos três opções, com custo 35 pelo nó b, com custo 90 pelo nó c e com custo 40 pelo nó d. Como a busca 
gulosa procura sempre a melhor escolha, o nó escolhido para ser expandido é o nó b. No item (ii), vemos duas 
opções a partir do nó b: ir para o nó e com custo 60 e ir para o nó f com custo 35. Neste caso, o nó f é escolhido, 
e do nó f já é possível alcançar o nó h, que é o objetivo, como podemos ver no item (iii). Assim, o caminho 
solução do problema é passar pelos nós a, b, f e h.
Figura 11: Solução por busca gulosa.
Fonte: Elaboração própria
A busca gulosa não é ótima e pode levar a uma solução com caminho mais longo quando um passo inicial 
do caminho mais curto tiver custo maior do que um passo do caminho mais longo. Essa situação pode ser vista 
na Figura 12, que mostra a mesma árvore de busca da Figura 11, em que aplicando a busca gulosa encontramos 
o caminho a, b, f e h, com custo total 70; porém, o caminho a, d, g e i tem custo menor, 60, mas no primeiro 
passo de escolha, a partirdo nó a, a escolha foi pelo nó b, localmente com menor custo, e não pelo nó d, com 
custo local maior, porém passando pelo menor caminho.
Figura 12: Melhor caminho do que o encontrado pela busca gulosa.
Fonte: Elaboração Própria
Busca A*
A busca A* (lê-se A estrela) é uma forma de busca pela melhor escolha. O algoritmo A* busca pelo melhor 
19
caminho avaliando a seguinte função: f(n) = g(n) + h(n), em que f(n) é o custo estimado da solução de menor 
custo passando por n, sendo:
• g(n) o custo do caminho do nó inicial ao nó n,
• h(n) o custo estimado do nó n até um objetivo.
A busca A* pode ser completa e ótima nos casos em que a função h(n) seja admissível, ou seja, h(n) nunca 
superestima o custo para atingir o objetivo.
Na Figura 13, podemos ver um exemplo de aplicação da busca A*. Nesse exemplo, os valores para a 
função h(n) são marcados em azul e os valores da função g(n) são marcados em cor-de-rosa na figura. No item 
(i), partindo da raiz, são expandidos três nós; a escolha é pelo nó b, pois é o nó com o menor valor de f(n)=70. 
Em seguida, no item (ii), o nó b é expandido, resultando nos nós e e f. Com isso, temos quatro nós para serem 
considerados para expansão, c, d, e e f, sendo que o nó d tem menor valor para f(n)=80. No item (iii), o nó d 
é então expandido, apresentando o nó g. Entre os nós disponíveis para expansão, temos c, e, f e g. O nó g é 
escolhido por ter o menor valor de f(n)=90 e sua expansão encontra o nó objetivo i. A solução para a busca é 
dada pelo caminho a, d, g e i, que é o menor caminho da árvore até um objetivo.
3.3 Heurísticas
Os métodos de busca informada são também conhecidos por métodos de busca heurística, pois a informação 
de que o método dispõe para ajudar no processo de busca é adquirida através de uma heurística. Para problemas 
de busca, uma heurística fornece um custo estimado do melhor caminho entre um nó n qualquer e um nó objetivo.
No processo de busca, quanto melhor for a heurística, menos nós a busca precisará percorrer até encontrar 
uma solução. Assim, a escolha da heurística influencia diretamente a capacidade de solucionar um problema. 
Mais ainda, a heurística deve ser eficiente, pois se a heurística tomar muito tempo para retornar um valor, ela 
não ajuda a diminuir o tempo total de busca.
Outra característica fundamental para que uma heurística seja utilizada é a admissibilidade. Heurísticas 
admissíveis nunca superestimam o custo de ir de um estado ao estado objetivo.
No módulo 2, utilizamos como exemplo de árvore de busca o problema do quebra-cabeça de 8 peças. A 
Figura 13: Solução 
por busca A*.
Fonte: Elaboração 
própria
20
árvore de busca do quebra-cabeça de 8 peças tem profundidade aproximadamente 20. Utilizar uma heurística 
para reduzir o tempo de busca é uma boa pedida para esse problema. Heurísticas para o problema do quebra-
cabeça de 8 peças já foram bastantes estudadas e esse é um problema antigo da IA.
Para entendermos melhor a diferença entre heurísticas, vamos olhar duas heurísticas para o problema 
do quebra-cabeça. A primeira heurística, h1, representa o número de peças que estão na posição errada. No 
exemplo da Figura 14, h1=8, pois todas as peças estão fora do seu lugar. Essa heurística é admissível, uma vez 
que, se uma peça estiver na posição errada, ela terá que ser deslocada pelo menos uma vez.
Figura 14: Um estado do quebra-cabeça de 8 peças.
Fonte: Elaboração própria
No entanto, a situação em que cada peça consegue chegar à sua posição com um deslocamento é diferente 
de outra situação em que mais deslocamentos são necessários. Pensando nisso, a heurística h2 considera quão 
longe uma peça está do seu local correto. Para isso, h2 utiliza a distância de Manhattan, a soma das distâncias 
verticais e horizontais, uma vez que as peças não podem se mover na diagonal. Para o estado da Figura 
14, h2=3+1+3+1+1+1+4+3=17. A heurística h2 é admissível, uma vez que cada peça precisa se deslocar um 
quadrado por vez até chegar sua posição objetivo.
Duas heurísticas, h1 e h2, podem ser comparadas. Se h2(n) ≥ h1(n) para qualquer nó n, então dizemos que h2 
domina h1, ou seja, h2 é mais informada que h1. Em outras palavras, uma heurística dominar a outra significa 
que ela sempre terá um desempenho melhor. No nosso exemplo do quebra-cabeça de 8 peças, a heurística h2 
é a melhor por dominar h1.
3.4 Busca local
Nos algoritmos de busca vistos até o momento, busca pela melhor escolha, o espaço de estados é explorado 
sistematicamente e os caminhos que levam à solução são mantidos na memória. Quando uma solução é 
encontrada, não só o estado objetivo, mas todo o caminho até esse objetivo também constitui uma solução para 
o problema. No entanto, para muitos problemas, um caminho até um objetivo não é relevante: o que realmente 
importa é o estado final. Nesses casos, podemos considerar uma classe diferente de algoritmos, chamada de 
busca local.
A busca local é bastante utilizada para solucionar problemas de otimização combinatória, problemas em 
que é necessário encontrar o melhor conjunto de valores para um grupo de variáveis. Exemplos de problemas 
de otimização combinatória são alocar professores e turmas ou escolher melhores rotas para veículos.
A busca local mantém um único estado atual e move-se para os estados vizinhos, não sendo necessário 
guardar os caminhos seguidos pela busca. A busca começa com o estado inicial, que é uma configuração completa, 
uma solução aceitável, e iterativamente tenta melhorá-lo. No exemplo de alocação de professores e turmas, o 
problema começa com uma alocação qualquer e vai alterando a alocação até que todas as turmas e professores 
estejam alocados corretamente. Veremos dois métodos de busca local: subida da encosta e têmpera simulada.
Subida da encosta
Subida da encosta é um método de busca local que, partindo do estado inicial, move-se para estados 
vizinhos sempre encosta acima, ou seja, para um estado melhor que o atual, até que alcance um pico, em que 
nenhum vizinho tenha valor mais alto. O objetivo da busca subida da encosta é encontrar o pico mais alto de 
todos, ou seja, encontrar um máximo global.
Para entendermos melhor a técnica de subida da encosta, vamos definir alguns termos, que também são 
21
ilustrados na Figura 15:
• Máximo global é o pico mais alto do espaço de estados.
• Máximo local é um pico alto, embora não seja o mais alto de todos.
• Pico é um estado em que nenhum dos seus vizinhos é mais alto.
• Platô é uma área em que todos os vizinhos têm o mesmo valor. 
Figura 15: Busca subida da encosta.
Fonte: Elaboração própria
Na busca pela subida da encosta, o espaço de busca pode ser visto como uma superfície como a da Figura 
15, com máximo global, máximos locais e platôs. Na Figura 15, conseguimos ver três picos, sendo que o 
maior deles corresponde ao máximo global e os outros dois são máximos locais. A parte plana é o platô. O 
estado inicial da busca é um ponto qualquer nesse espaço.
Vamos supor que o estado inicial seja o ponto A e a busca procede escolhendo o próximo estado, dentre 
os seus vizinhos. O estado escolhido é o que tem maior valor. Nesse caso, o próximo estado será o ponto 
vizinho ao ponto A, no sentido encosta acima. Este procedimento se repete e, a cada vez, o estado corrente é 
um ponto um pouquinho mais alto, até que o estado atual seja o estado correspondente ao pico. Ao chegar ao 
pico a busca pára, pois os seus vizinhos têm valores menores. Nesse caso, a busca retorna uma solução que é 
um máximo local: é um ponto máximo, porém não é o mais alto do espaço de estados.
Agora, vamos supor que o estado inicial seja o ponto B; a busca procede escolhendo sempre como próximo 
estado o vizinho com valor maior, até chegar ao pico. Nesse caso, o pico corresponde ao máximo global, sendo 
esta a melhor solução possível para o problema.
Por esses dois exemplos é possível notar que o sucesso da busca depende do seu estado inicial. Com o estado 
inicial sendo o ponto B, a busca rapidamente encontra o máximo global; porém,com o ponto A, a busca retorna 
o máximo local. Para tentar minimizar esse problema, a busca pode ser reiniciada algumas vezes com estados 
iniciais escolhidos aleatoriamente, ou então, pode-se utilizar uma heurística para escolha do estado inicial.
Têmpera simulada
O método de subida da encosta nunca faz movimentos encosta abaixo, ou seja, uma vez que comece em uma 
direção, a busca não muda de direção e isso faz com que a busca seja incompleta, pois pode não encontrar a melhor 
solução, por ficar presa em um máximo local. A técnica de têmpera simulada utiliza a ideia da subida da encosta; 
porém, para evitar ficar presa em máximos locais, faz a busca também por estados escolhidos aleatoriamente.
Isso é alcançado contornando pontos de ótimo local, permitindo a realização de movimentos que conduzam 
temporariamente a soluções de pior qualidade que a atual. A probabilidade de se aceitarem movimentos que 
levem a soluções de pior qualidade decresce ao longo do processo de busca.
O nome “têmpera simulada” é baseado no processo de têmpera, utilizado para produzir vidros e metais, 
que envolve aquecer o material em uma temperatura muito alta e depois deixá-lo esfriar lentamente. Esse 
22
processo garante ao material maior resistência. Simulando o processo da têmpera, o método de têmpera 
simulada utiliza um parâmetro de temperatura T, que é o seu principal parâmetro de controle. A cada iteração, 
um estado vizinho é escolhido aleatoriamente do conjunto de estados vizinhos do estado atual.
O método é ótimo e completo se o mapeamento de resfriamento tiver muitas entradas com variações 
suaves, isto é, se o mapeamento diminui T suficientemente devagar no tempo, o algoritmo vai encontrar um 
máximo global ótimo.
3.5 Jogos
Os jogos fazem parte do interesse dos seres humanos desde que surgiu a civilização. As pesquisas em IA 
também se direcionaram para os jogos. O xadrez, por exemplo, é um jogo interessante para IA, pois é um 
jogo difícil, com fator médio de ramificação 35, e com até 50 movimentos por jogador até finalizar o jogo. 
Isso resulta em uma árvore de busca muito grande, que torna necessário utilizar algum processo de tomada de 
decisão para se escolher a próxima ação.
Sistemas de jogos combinam técnicas de busca com diversas heurísticas e uma base de dados de 
conhecimento sobre o jogo. Um jogo para dois jogadores pode ser representado por uma árvore de jogos, em 
que a raiz representa o estado antes do início do jogo e as jogadas de cada um dos jogadores são apresentadas 
em níveis alternados. As folhas representam estados finais, em que o jogo foi vencido, perdido ou empatado. A 
busca pela árvore procede utilizando uma função de avaliação, considerando que o computador quer maximizar 
uma pontuação que o adversário está tentando minimizar.
O método utilizado para encontrar os movimentos no jogo é o Minimax, baseado na ideia de maximizar a 
pontuação supondo que o adversário vai tentar minimizá-la. Minimax realiza uma busca cega em profundidade, 
sendo Max o computador e o Min o adversário. O método gera a árvore inteira até os estados objetivos; 
em seguida aplica a função de avaliação nas folhas; propaga os valores dessa função subindo na árvore e 
retorna a ação que deve ser escolhida por Max. O Minimax não é adequado para diversos jogos em que o 
fator de ramificação e a profundidade da árvore 
são grandes; porém, sua importância está em 
servir de base para outros métodos que tentam 
melhorar seu desempenho. Mais informações 
sobre o método Minimax e outros métodos de 
busca para jogos podem ser encontrados em 
(RUSSEL, NORVIG, 2004; JACKSON, 1985; 
COPPIN, 2010).
Exercícios
1. Qual a diferença entre busca cega e busca informada?
2. Qual a importância da heurística para os métodos de busca informada?
3. Pesquise um jogo que pode ser solucionado utilizando árvore de jogos.
• Um jogo que adivinha o que você está pensando 
em até 20 perguntas. Vejam no seguinte endereço 
eletrônico: http://www.20q.net/
Saiba mais!
IA na Educação:
Hobmeir et al. (2008) apresentam um sistema para ensino do jogo de xadrez, utilizando heurísticas para 
busca em árvores de jogos.
• HOBMEIR NETO, A.; DIRENE, A.; SILVA, F.; BONA, L.; GARCÍA, L.; CASTILHO, M.; SUNYÉ, 
M. Uma abordagem dialógica alternativa para a aquisição de habilidades táticas em jogos 
educacionais. XIX Simpósio Brasileiro de Informática na Educação (SBIE), Fortaleza, 2008. 
Disponível em: http://www.br-ie.org/pub/index.php/sbie/article/download/759/745.
23
Unidade
Nos dois módulos anteriores, estudamos a solução de problemas através de métodos de busca. Para 
os métodos estudados, não nos preocupamos em como o conhecimento sobre o problema está sendo 
representado. No entanto, existem problemas em que a complexidade e a quantidade de conhecimentos 
necessários para a solução exigem que utilizemos uma forma adequada de representação. É exatamente disso 
que trata este módulo: como podemos representar o conhecimento sobre determinado domínio para 
solução de um problema.
4.1 Sistemas baseados em conhecimento
Os Sistemas Baseados em Conhecimento (SBC) são programas computacionais que usam o conhecimento 
representado explicitamente para solucionar problemas. Tais sistemas são usados quando se tem uma quantidade 
grande de conhecimento específico sobre algum domínio. Os SBCs possuem uma base de conhecimento, com 
linguagem específica para modelar o problema, e um mecanismo de inferência para obter conclusões a partir 
da base. A base de conhecimento é um conjunto de representações em uma linguagem específica, chamada de 
linguagem de representação do conhecimento (REZENDE, 2003).
A representação do conhecimento é um tema-chave para solução de problemas computacionais, em 
especial de IA. Para que um problema possa ser solucionado por um computador, ele precisa primeiro ser 
representado internamente. O modo pelo qual o problema é representado, que variáveis e operadores utiliza, 
interfere diretamente na eficiência do algoritmo empregado para encontrar a solução.
Representação do conhecimento são métodos usados para modelar o conhecimento de especialistas em 
algum campo. A representação é um conjunto de convenções sintáticas e semânticas que nos possibilitam 
descrever coisas. A representação sintática especifica os símbolos que podem ser usados e as maneiras como 
os símbolos são arranjados. A representação semântica especifica que significado está incorporado naqueles 
símbolos representados pela sintaxe (WINSTON, 1988).
Ao escolher uma forma de representação, é importante ter em mente que uma representação deve armazenar 
informação necessária para a solução do problema, nem mais, nem menos. A falta de informação pode fazer 
com que o sistema não encontre a resposta e o excesso de informação pode tornar a busca ineficiente. Encontrar 
a dosagem correta de informação armazenada nem sempre é fácil; porém, o conhecimento sobre o problema 
pode ajudar.
As formas de representação mais usadas em IA são lógica, regras de produção, redes semânticas e quadros. 
Veremos agora cada uma dessas formas de representação de conhecimento.
4.2 Lógica
A representação baseada em lógica tem sido bastante utilizada por pesquisadores de IA desde a década 
de 1970. Sua característica principal é o fato de a lógica matemática ser uma linguagem formal, diferente de 
linguagens naturais, como o português ou inglês. Uma motivação importante para o uso da lógica na representação 
de conhecimento é que ela fornece uma maneira de raciocinar sobre o conhecimento, ou seja, a lógica matemática 
permite realizar inferências dedutivas a partir do formato sintático das expressões da linguagem.
Esta unidade tem como objetivos:
• Entender a necessidade de representar adequadamente o conhecimento e ser capaz de escolher uma 
representação de conhecimento adequada para o problema a ser solucionado.
• Conhecer os tipos de representação: lógica, regras de produção, redes semânticas e quadros.
Representação do conhecimento4
24
Um sistema lógico consisteem um conjunto de sentenças e um conjunto de regras de inferência. As sentenças 
são pertencentes a uma linguagem formal cuja sintaxe é dada e cada sentença pode ser associada a um valor 
verdade (V ou F). Uma regra de inferência é uma regra sintática que, quando aplicada repetidamente a uma ou 
mais sentenças verdadeiras, gera novas sentenças verdadeiras. Nesse contexto, uma prova é uma sequência de 
sentenças geradas através da aplicação de regras de inferência sobre um conjunto inicial de sentenças.
Existem vários tipos de lógica utilizados para representar conhecimento, entre elas o cálculo proposicional 
e a lógica de primeira ordem. O cálculo proposicional tem como objetivo modelar o raciocínio humano, 
partindo de frases declarativas ou proposições. A lógica proposicional é simples e baseia-se na existência de 
constantes e no uso de operadores lógicos. Exemplos de sentenças na lógica proposicional são dados a seguir:
 
 Sentença lógica Frase em português
 cachorro(lola) Lola é um cachorro
 possui(alice, lola) Alice é a dona de Lola.
Enquanto o cálculo proposicional representa fatos, a lógica de primeira ordem representa fatos, objetos 
e relações, permitindo que suas proposições sejam formadas por predicados, argumentos, quantificadores e 
variáveis. A lógica de primeira ordem tem sido bastante utilizada como forma de representação de conhecimento, 
por ser bastante expressiva.
Vejamos um exemplo de sentenças escritas em lógica de primeira ordem:
 Sentença lógica Frase em português
 ᴲ x cachorro(x) ^ possui(alice,x) Alice possui um cachorro.
 x cachorro(y) ^ possui(x,y)) → Todo dono de cachorro é um protetor dos animais.
 protetorAnimais(x) 
Uma das principais vantagens da 
representação lógica, em especial da lógica de 
primeira ordem, é o fato de utilizar mecanismos 
de inferência simples e poderosos, como a 
resolução (Rich, 1988).
Uma das linguagens de programação mais 
utilizadas e conhecidas que utiliza princípios 
da lógica matemática é o PROLOG.
4.3 Regras de produção
Os primeiros sistemas baseados em 
conhecimento foram construídos utilizando 
regras. A ideia das regras é empregar a forma 
de representação do conhecimento utilizada 
por seres humanos. Uma regra representa o 
conhecimento na forma:
Se condição (ou premissa ou antecedente) então ação (resultado, conclusão ou consequente). 
A parte do se corresponde ao antecedente da regra e a segunda parte, à conclusão da regra. Por exemplo, 
a regra a seguir tem como antecedente está frio e como conclusão vista um casaco:
Se está frio então vista um casaco.
A
PROLOG é uma linguagem de programação baseada 
em lógica, especificamente em um subconjunto da 
lógica de primeira ordem. É uma linguagem bastante 
utilizada em IA.
Existem diferentes implementações de PROLOG 
disponíveis:
• Ciao Prolog: http://www.clip.dia.fi.upm.es/Software/Ciao
• GNU Prolog: http://gnu-prolog.inria.fr
• YAP Prolog: http://www.ncc.up.pt/~vsc/Yap
• SWI Prolog: http://www.swi-prolog.org
Saiba mais!
25
Outro exemplo de regra de produção é:
Se está frio então prepare uma sopa para o jantar.
Note que este exemplo tem o mesmo antecedente da regra anterior, está frio, porém com uma conclusão 
diferente: prepare uma sopa para o jantar.
As regras são chamadas de regras de produção porque, quando utilizadas com encadeamento para frente, 
produzem novos fatos a partir dos fatos e regras da base de conhecimento. Esses novos fatos passam então a 
fazer parte da base de conhecimento.
As regras representam o conhecimento de forma modular, ou seja, cada regra representa uma parte do 
conhecimento independente. Em conjunto, as regras e os fatos formam a base de conhecimento. Considere 
como exemplo as três regras sobre um semáforo:
Se sinal está amarelo então diminua a velocidade do carro.
Se sinal está vermelho então pare o carro.
Se sinal está verde e não há pedestre atravessando a rua então siga com o carro.
Um sistema que utilize a representação de conhecimento baseada em regras deve manipular regras e fatos 
utilizando um mecanismo de inferência que permita produzir novos fatos e chegar ao resultado final.
4.4 Redes semânticas
As redes semânticas possuem como característica principal o fato de permitirem a visualização gráfica do 
conhecimento e de suas relações. Essa característica serve tanto de atrativo como de limitação, uma vez que 
a sua expressividade pode ficar comprometida. O que distingue uma rede qualquer de uma rede semântica é o 
fato de a rede semântica carregar um significado ou semântica da informação representada.
Uma rede semântica é um grafo 
rotulado e direcionado, ou seja, 
uma rede de nós interconectados 
através de arcos. Cada nó do grafo 
representa um objeto, que pode 
ser indivíduos, coisas, conceitos, 
etc. e cada arco que liga os nós 
representa a relação existente entre 
esses objetos.
A herança de propriedades 
através de caminhos formados por 
arcos permite que propriedades 
de um nó sejam especificadas 
apenas uma vez, no nível mais 
alto da hierarquia, sendo herdadas 
por todos os conceitos derivados. 
Essa característica fornece às 
redes semânticas uma economia 
de memória, evitando duplicidade 
desnecessária de informações.
Um exemplo simples de rede semântica pode ser visto na Figura 16. Curso de Graduação, Licenciatura 
em Informática, Sistemas de Informação e Ana são nós da rede, enquanto é-um e cursa são os arcos, que 
representam as relações entre os nós. Note que os arcos são setas que têm uma direção. Em razão dos arcos 
direcionados, é possível representar que Ana cursa Licenciatura em Informática, porém Licenciatura em 
Grafos
Um grafo G(V,E) consiste em dois conjuntos V e E. V é um 
conjunto não vazio de vértices e E é um conjunto de pares não 
ordenados de V, chamados arestas. Se as arestas tiverem direção, 
o grafo é chamado direcionado ou orientado.
Mais conceitos introdutórios relacionados à teoria dos grafos 
podem ser encontrados nos links:
http://www.inf.ufsc.br/grafos/definicoes/definicao.html
http://www.ime.usp.br/~pf/teoriadosgrafos/
Saiba mais!
26
Informática não cursa Ana. Seguindo o caminho formado pelos arcos na rede, podemos ver que Ana é uma 
aluna do curso de Licenciatura em Informática, que é um Curso de Graduação. Esse caminho nos permite ver 
a propriedade de herança presente nas redes semânticas.
Figura 16: Rede semântica.
Fonte: Elaboração própria
Em redes semânticas, a base de conhecimento é composta pelos nós e arcos da rede. O mecanismo de 
inferência utiliza busca e casamento de padrões. A busca se dá para frente e para trás através dos arcos. A busca 
pode ser usada de várias maneiras em redes semânticas para se extrair informações: como uma ferramenta 
explicativa, para explorar exaustivamente um módulo ou para encontrar o relacionamento entre dois objetos.
4.5 Quadros
Os quadros ou frames permitem utilizar a representação gráfica com herança das redes semânticas e 
também agrupar conhecimento relevante sobre algum objeto, situação ou conceito. Um quadro é identificado 
por um nome e descreve um objeto complexo através de um conjunto de atributos. Um sistema de quadros é 
um conjunto de quadros organizados hierarquicamente. Os quadros são uma evolução das redes semânticas em 
que os nós são substituídos por quadros e os arcos são substituídos por atributos; além disso, procedimentos 
podem ser anexados a um quadro.
As ideias de quadros estão presentes na origem das linguagens de programação orientadas a objetos, que 
têm em comum a organização em classes e objetos e a herança de propriedades.
Os quadros possibilitam uma organização hierárquica dos dados, que traz o benefício de evitar a duplicação 
desnecessária de informação. Os dados são organizados de forma aninhada, com propriedades comuns que são 
automaticamente herdadas através da hierarquia. A associação entre os quadros determina a sua hierarquia: 
cada associação liga um quadro-pai a um quadro-filho. O quadro-filho pode herdar valores dos seus quadros 
ancestrais, quepor sua vez também herdam valores de seus quadros ancestrais.
Um exemplo bem simples de um sistema de quadros é apresentado na Figura 17. O quadro sala tem os 
atributos paredes, portas e janelas e o quadro sala de aula tem os atributos carteiras e lousa. O quadro sala de 
aula é uma instância do quadro sala; assim, sala de aula herda os atributos de sala, ou seja, uma sala de aula 
também possui paredes, portas e janelas.
27
Figura 17: Quadros.
Fonte: Elaboração própria
Um quadro pode ter um procedimento associado. Um procedimento é um conjunto de instruções que pode ser 
executado quando solicitado. Por exemplo, podemos ter um procedimento que cria uma instância de uma classe.
Os quadros carregam o conceito de herança de propriedades, que, além de possibilitar compartilhar 
propriedades entre classes de objetos, também pode ser um mecanismo de inferência bastante eficiente. A hierarquia 
de especialização do sistema de quadros norteia a busca por uma solução. Além disso, uma vez que os quadros 
possuem atributos, sua instanciação deve encontrar valores para os mesmos. O processo de raciocínio deve 
preencher os valores dos atributos com as informações disponíveis. Existe também a possibilidade de recorrer à 
ligação procedimental, ou seja, executar um procedimento associado a um atributo para descobrir seu valor.
Finalizando
Lógica, regras de produção, redes semânticas e quadros são os métodos de representação de conhecimento 
mais utilizados em IA. A lógica é o único dos métodos que possui uma base teórica formal; os demais são ditos 
métodos especializados e, apesar de não formais, podem ser bastante eficientes.
Ao escolher uma representação do conhecimento para um determinado problema, deve-se primar pela 
representação que permita que todo o conhecimento necessário seja adequadamente representado e que 
possibilite uma fácil utilização desse conhecimento para solucionar o problema em questão.
IA na Educação:
Schmitz, López e Ávila (2002) utilizaram redes semânticas para representar conhecimento em um sistema tutor:
Na técnica de rede semântica, a relação entre dois Módulos da matéria a ser estudada pode ser 
expressa através de um relacionamento. 
Objetos de conteúdo podem ser textos, imagens, sugestões, bibliografias e outras informações 
associadas aos Módulos ou nós da rede semântica. Um possível exemplo seria associar um vídeo 
ou apresentação sobre determinado conceito a um Módulo que forma um nó da rede semântica.
• SCHMITZ, A. LÓPEZ, O.C. AVILA R.F. Ferramenta de autoria de sistemas tutores inteligentes 
construindo o modelo do domínio do conhecimento com redes semânticas. II Congresso Brasileiro 
de Computação – CBComp 2002 Informática na Educação. Itajaí, 2002
28
Exercícios
1. Qual a importância da representação adequada do conhecimento na resolução de 
problemas em IA?
2. Descreva sucintamente cada uma das formas de representação de conhecimento: lógica, 
regras de produção, redes semânticas e quadros.
3. Pesquise sistemas implementados para a educação que utilizem as representações de 
conhecimento vistas neste módulo.
29
Unidade
Neste módulo, abordaremos um assunto bastante interessante e enriquecedor da disciplina de Inteligência 
Artificial, que são os Sistemas Especialistas (SE). Os primeiros SE surgiram na década de 1970 e 
foram projetados com o objetivo de simular o comportamento de resolução de um problema por um 
especialista humano em um domínio específico. No início, os SE geraram bastante entusiasmo; hoje em dia 
eles são vistos de maneira mais realista, como mais uma ferramenta útil para alguns problemas específicos.
5.1 Introdução
Um Sistema Especialista é um sistema baseado em conhecimento, que soluciona problemas em um 
domínio específico, apresentando conclusões, que podem ser recomendações, diagnósticos ou até mesmo 
ações a serem tomadas. A ideia principal de um SE é capturar o conhecimento de um especialista humano em 
determinado domínio para solucionar problemas, que em geral são não numéricos.
Um SE é composto por uma base de conhecimento formada por fatos e regras sobre o domínio e um 
mecanismo de inferência. Uma definição para SE dada por Passo (1989) é apresentada a seguir:
Um sistema especialista é um programa de computador destinado a solucionar problemas em um campo 
específico do conhecimento, que tem para isso uma base de conhecimento desse domínio restrito. Usa 
um raciocínio inferencial para executar tarefas, e tem desempenho comparável ao dos especialistas 
humanos.
A definição dada por Passo diz que um SE é um programa de computador. O que diferencia um SE 
da programação convencional? A principal diferença está no fato de o SE utilizar um paradigma lógico de 
programação, que é um paradigma declarativo, ou seja, o programa é um conjunto de declarações ao invés 
de uma sequência de passos a serem seguidos. As respostas são obtidas mediante as perguntas feitas pelos 
usuários, consultando a base de conhecimento e utilizando processos de inferência. Veremos o funcionamento 
dos processos de inferência com mais detalhes posteriormente.
Situações em que um SE é particularmente bastante útil são as de emergência, onde o estresse diminui 
consideravelmente a capacidade de resolução de problemas dos seres humanos. Nessas situações, em que a 
velocidade de resolução de problemas é imperativa e quando se deseja padronizar ações tomadas por diferentes 
especialistas humanos, um sistema especialista é de grande utilidade, auxiliando o especialista humano na 
tomada de decisão.
Uma característica importante de um sistema especialista é a sua capacidade de explicação, ou seja, além 
de solucionar um problema, o SE também pode conseguir explicar como chegou a uma determinada conclusão, 
de maneira semelhante a como fazem os especialistas humanos. Dessa maneira, a explicação pode ser usada 
até mesmo para ensinar pessoas que não são especialistas no assunto tratado pelo SE, como ressalta Passo:
Sistemas Especialistas5
Esta unidade tem como objetivos:
• Adquirir conhecimento sobre os conceitos fundamentais de Sistemas Especialistas, bem como sua 
construção e utilização.
• Entender o uso de regras em sistemas especialistas.
• Compreender a arquitetura dos sistemas especialistas.
• Conhecer os mecanismos de inferência.
• Considerar as ferramentas para implementação de um sistema especialista.
30
Procura-se construir sistemas especialistas capazes de explicar as etapas de seus raciocínios e de justificar 
com clareza suas conclusões. Esta última característica pode transformar os sistemas especialistas em 
ferramentas de ensino.
De fato, SEs têm sido utilizados amplamente como ferramentas de ensino, especialmente em implementações 
dos chamados Sistemas Tutores Inteligentes.
5.2 Regras
Os primeiros SEs que obtiveram sucesso foram o DENDRAL e o MYCIN, o primeiro de 1965 e o segundo 
de 1970, ambos da Universidade de Stanford, nos Estados Unidos. 
O sistema DENDRAL é capaz de inferir estruturas químicas a partir de resultados da espectrografia de 
massa de corpos orgânicos, gerando todas as estruturas possíveis que satisfazem as restrições dos dados. 
O sistema MYCIN é derivado do DENDRAL e foi desenvolvido para doenças infecciosas sanguíneas, 
para auxiliar médicos na escolha de uma terapia de antibióticos para pacientes com bacterimia, meningite e 
cistite infecciosa, em ambiente hospitalar. O sistema usa regras de produção com fatores de certeza no auxílio 
do raciocínio probabilístico e usa estratégia de encadeamento para trás dirigido pelas hipóteses, perguntando 
dados ao usuário para continuar o encadeamento. 
Um exemplo de regra do MYCIN pode ser visto a seguir:
Se a infecção é meningite e 
 o tipo de infecção é bacterial e
 o paciente passou por cirurgia e
 o paciente passou por neurocirurgia e
 o tempo da neurocirurgia foi