Universidade Católica de Angola

Curso de Engenharia Informática

Sistemas Inteligentes
I
Docente: Henriques Fernando
Setembro/2022
Código: zdycfpg
 Apresentação
Cadeira

• Sistemas Inteligentes

Sumário

• Informação Geral
• Objectivos e Programa
• Avaliação
• Material de Apoio

Informação Geral

• Docente: Henriques Fernando

• Email: fhenrivx@[Link]
• Sala Virtual: SI
• Código:zdycfpg

Aulas

• Teóricas
• Teóricas_Práticas
Geral
Objectivos
• Dotar os estudantes de conhecimentos
sobre agente, aprendizagem, resolução
de problemas, busca, conhecimento,
raciocínio e programação em lógica de
formas capacita-los a desenvolver
aplicações inteligentes que resolvam
problemas complexos.
• Fornecer as competências necessárias
para a análise crítica de Aplicações e
algoritmos existentes de formas a
desenvolver Sistemas Inteligentes
 Programa
Nº Aula Aula- Tema
1 Apresentação Metodologias
Introdução Conceitos e Evolução Histórica
Aplicações e Perspectivas
2 Agentes Inteligentes Estrutura e Modelos
Agentes Reactivos e não reactivos
Agentes baseados em objectivos
3 Métodos de Busca Busca cega: Algoritmos DFS e BDF;
Busca heurística:
Greedy search e A*;
busca competitiva: Algoritmo Minimax
4 Representação de Formalismos de representação do conhecimento;
Conhecimento Sistemas baseados em conhecimento.
5 Paradigmas de O Paradigma Lógico; Prolog: Características e aplicações;
Programação Criação de base de conhecimento.
6 Aprendizagem de Aprendizado supervisionado;
máquina Aprendizado não-supervisionado;
Aprendizagem por esforço.
7 Fundamento de Fundamentos de Mineração de Dados
Mineração de Dados
 Programa
❑ Ano/Semestre: 3º Ano / 1º Semestre Carga H.
Semanal: 2T + 2P Carga H. Semestral: 64 Créditos:
5 Tipo: Obrigatória

❑ Avaliação: Nota Final = 0.4 x Frequência + 0.6 x

Exame Pré-Requisito: Algoritmos e Complexidade;
Métodos Estatísticos
Metodologias
Métodos

•Aulas expositivas através de a

exemplos práticos que
atendem o contexto do estado
da arte actual e discussões.
 Sumário
Apresentação e Revisão Conceptual
Introdução à IA

Agentes Inteligentes

Métodos de Busca

Representação de Conhecimento

Paradigma de programação em Lógica

Apredizado de Máquina

Fundamentos de Mineração de Dados

 Introdução
Pressuposto de IA

• Existem processos comuns baseando perceção e pensamento.

Estes processos podem ser compreendidos e estudados
cientificamente.
• É completamente irrelevante para a teória da IA quem (ou o quê)
"percebe" ou "pensa" - homem ou computador. Isso é um detalhe
de implementação..

Disciplina

• Estuda dos processos que possibilitam aos computadores realizar tarefas

para as quais, no momento, as pessoas são mais aptas.“E. Rich
• objectivo fundamental é realizar sistemas computacionais capazes de
exteriorizar comportamentos operacionais semelhantes aos humanos em
situações estereótipadas.
• As técnicas de programação de pesquisa não deterministicas utilizadas,
baseiam-se, pelo menos parcialmente, em Linguagens declarativas, sendo
essencialmentalmente relacionais, baseadas na lógica ou funcionais.
Existem ferramentas (“Tools”) incluindo algoritmos de inspiração
estatística (frequencista ou não) para extração de conhecimento baseados
em dados
Motivação

As quatro partes imagem podem ser

representados nesse ambiente de 24
maneiras diferentes
Cont…

Testando um bilhão de combinações

por segundo, leva-se cerca de 4 x 1089
milénios
Humano- Monta de quebra cabeça muito
mais rápido
• Não necessita tentar todas combinações
possíveis
• Temos uma noção da imagem
representada e sabemos como as peças
podem ser combinadas

Ideia Principal

• Utilizamos conhecimento do problema

de forma inteligente
8x8
• 1.2268x1089 combinações possíveis
• Testando um bilhão de
combinações por segundo,
levaríamos cerca de 4 x 10 89
milênios para testar todas as
combinações
Humanos
• Fazemos resolução muito mais rápido.
Porque usamos conhecimento sobre o
problema de forma inteligente
• Pode-se programar o computador para
utilizar o conhecimento de um problema
de forma inteligente
Programar um computador

• Para utilizar o conhecimento de um

problema de forma inteligente?

IA - Abordagens

• Pensar como humanos (cognitiva-

psicologia);
• Pensar de forma racional (lógica);
• Agir como humanos (teste de turing);
• Agir de forma racional;
Estudos iniciais de IA
• IA Forte : as máquinas que agem como os
humanos, criar máquina que funcionam em
semelhança ao cérebro
• IA Fraca: preocupasse com o resultado final, o ser
artificial age e toma decisões independente de
como é programado ou funciona

Turing (1950)

• Ao invés de perguntarmos se as máquinas podem

pensar.
• Deve perguntar se podem passar no teste de
comportamento (racional)
Habilidades de Máquinas – Teste de
Turing
• Processamento em Linguagem Natural: Sistema
deve se comunicar o com o examinador;
• Representação de Conhecimento: representar o
conhecimento sobre o mundo;
• Raciocínio Automático: como pensar e elaborar
a resposta para aquela pergunta (inferência);
• Aprendizagem de Máquina: Os sistema tendem
aprender a medida que dialogam com o
interrogador.
Pré- História de IA

• Filosofia;
• Lógica;
• Matemática;
• Economia;
• Psicologia;
• Neurociência;
• Linguística; e
• etc.
Surgimento de IA

• Warren MacCulloch e Walter Pitts(1943)-

Criação de neurónios artificiais
• Programar computadores com a ideia que
cada neurónio poderia estar ligado ou
deligado (simulava o conhecimento que se
tem sobre os neurónios)
• Baseado em conhecimento sobre filosofia e
as funções dos neurónios
Darthmouth (John MacCarthy-
1956)
• Propôs um encontro e utilizou pela primeira vez
o termo IA
• Claude Shonnon (teoria da informação);
• Marvin Minsky (construiu a primeira rede
neural);
• Herbert Simon (prémio de economia,
contribuiu com o pensamento racional) …
• MacCartthy (criou LISP)
• Propôs o uso da lógica para resolver
problemas em 1959
• Artigo sobre habilidades de programas com
senso comum
O que é IA - Abordagens
• Pensar como humano - Cognitiva
• Pensar de forma racional- Lógica
• Agir como Humanos- Teste de turing
• Agir de forma racional -

Surgimento – McCulloch &

Pitts (1943)

• Cada neurônio poderia estar ligada

ou desligada
• Baseado nos conhecimentos sobre a
filosofia e as funções dos neurônios
 Habilidades

• Processamento em linguagem
Natural
• Representação de Conhecimento
• Raciocínio Automático
• Aprendizado de Máquina

Início de IA (Dartmouth) –
John MacCarthy - 1956

• Channon, Minsky, Simon…

 Evolução
Domínios de Aplicação de IA
Robótica IA

Ciências
Cognitivas + Engenharia de
Ciências de Conhecimento
Computação

Ciências
Agentes
de Autónamos
Dados
Darthmouth (John MacCarthy-
1956)
• Primeiros sistemas especialistas: uso de
conhecimento para resolução de problemas;
• Codificar o conhecimento de um especialista de
uma certa área;
• Dendral (1965) : analisava as moléculas de
química orgânica de formas a pensar como os
átomos se posicionavam i.e. tentar encontrar a
estrutura de uma molécula ;
• Mycyn(1875): sistema de recomendações de
antibióticos para infecçoes bacterianas
• Tom Mitchel(1978): Primeiro algoritmo de
aprendizagem em máquina
Quase em todas as áreas
Aplicações
• Smartphones (cálculo de rotas)
• Sistemas de recomendações (Netflix, Youtube, Spotify..)
• Google (anúncios )
• Simulação e Jogos(DeepBlue: primeiro a ganhar o campeão de
xadrez e AlphaGo: primeiro a ganhar do campeão de Go)
• Robótica
• Veículos autónomos;
• Automação de Sistemas complexos (automação industrial)
• Sistemas de controlo (carros autonámos)
• Previsão do mercado
• Recuperação de informações
• Detecção de intrusão e filtragem de spam
• Interface Humana Computador
• Sistemas de informações(tomada de decisões)
Novas experiencias e novas formas de interação
• Interface por voz (alexa- amazon, Siri- Apple, Home- Google)-
comando por voz e recebe a informação por texto
• Netflix- entende o comportamento e recomenda filmes e capas
Visão Geral
• Resolução de Problema
• Como representar um problema;
• Como buscar soluções a partir da
representação;
• Sem informação sobre o domínio;
• Informada (heurísticas)
• Resolução de problemas utilizando lógica

Exemplos de Problemas
• Xadrez, Quebra – Cabeça, Encontrar caminho
Elementos para definição de um
problema
• Estado inicial;
• Acções;
• Teste de objecto;
• Custo.
Solução
•Sequência de estados que
levam do estado inicial ao
estado objectivo;
•Solução óptima é aquele que
oferece o custo mínimo.
Exemplo- Sair de casa para o
trabalho

• Estado inicial: casa;

• Estado final: trabalho;
• Acções possíveis: andar, apanhar
autocarro, conduzir, andar de bicicleta
• Custo: financeiro, tempo, distância.
Utilização de IA Envolve
Saber representar o conhecimento e
utilizar métodos que o manipulam

Conhecer os métodos que façam

as máquinas aprenderem de
maneira autonóma

Conhecer as aplicações mais

importantes de IA
 Adordagens - IA
Baseada em Conhecimentos
• Baseada em regras (SE): Esforço em
mapear os conhecimento dos especialistas
(ex. médicos);
• foi óptima mas está ultrapassada
• Vários If, condições e a máquina não era
capaz de aprender
Aprendizado Estátistico
• Utilização de Métodos estatísticos
(Machinig Learning)
 Metas - IA
Ciêntifica

• Proposições e emprego de ideias

• Representação de conhecimento
• Utilização e construção de sistemas que explicam
vários tipos de IA

Engenharia

• Resolução de problemas do Mundo real para

representação de conhecimento
• Emprego de conhecimentos e criação de sistemas
computacionais
Exemplos de Capacidades - IA
1- Sistemas
• Sistemas inteligentes podem ajudar especialistas a
resolver problemas difíceis de análise
• Sistemas inteligentes podem aprender através de
exemplos
• Sistemas inteligentes podem resolver questões de
linguagem natural usando dados estruturados e texto
livre.

2 Dispositivos
• Sistemas inteligentes podem ajudar especialistas a
projectar novos dispositivos
Classificação de Sistemas Inteligentes
Sistemas Simbólicos

• Conhecimento é representados por sistemas simbólicos e

separado da máquina de inferência
• Prova de Teoremas;
• Sistemas Especialistas;
• Programação em Lógica;
• Redes Semânticas;
• Sistemas de Frames;
• Sistemas de Agentes;

Sistemas sub-simbólicos

• Representa o conhecimento na própria estrutura, integrado

ao mecanismo de raciocínio
 Cont..
Sistemas Sub-Simbólicos

• Redes neurais
• Algoritmos genéticos
• Autômatos celulares
• Sistemas complexos adaptativos
 Arquitectura de Sistemas
Computação Convencional Computação Simbólica Engenheiro de
Utilizador Conhecimento
Utilizador

Dados
Dados

Programador Mecanismo Base de

Algoritmo Aquisição de
de Raciocínio Conhecimento
passo-a-passo Conhecimento
Genérico Heurístico
especializado

Utilizador Interface
Explicação do
Raciocínio
Dados
Especialista

Dados Explicações

Fonte Adaptada: Silva(2018)

Utilizador
 Arquitectura de Sistemas
Aprendizagem Utilização

Utilizador
Dados
Treinados
Dados
Pesos(RN)
Provas(RB) ou Pesos(RN)
Programador individuais(AG) Provas(RB) ou
Treinados individuais(AG)
Treinados
Dados
Treinamento Dados Utilizador

Comprador Dados

Fonte Adaptada: Silva(2018)

 Agentes Inteligentes
Agente
• Um agente é qualquer objecto que pode
perceber seu ambiente através de sensores e
agir sobre este ambiente através de actuadores.
Exemplos
Agente Sensores Actuadores
Humanos Olhos, ouvidos, nariz, boca, pele Mãos, pés, cordas vocais
Robots Camaras, infravermelhos, Motores, braços
sonoras, sensores de pressão mecânicos, pinças,
altifalantes
Agentes Software Batimentos de teclados, Ecrãs, ficheiros de saída,
conteúdos de ficheiros, dados dados enviados pela rede
recebidos de redes
 Software - Jennings (1995)
• Executa uma determinada tarefa empregando
informação extraída de seu ambiente para agir
de forma adequada no sentido de completar
sua tarefa de modo bem sucedido.
• O agente deve ser capaz de adaptar-se
dinamicamente às modificações ocorridas no
ambiente”.
Percepção
• Capacidade de receber informação do ambiente
Sequência de percepções
• Historia completa dos dados que o agente
tenha percebido durante um tempo , é
guardado numa memória, a acção a selecionar
depende desta
 Função Agente

• Seleciona uma acção a partir da sequencia de

percepções (mapeamento)
Percepção acção
1 Accão 1
1,2 Accão 2
1,2,3 Accão 3

Programa agente

• Implementação sobre uma arquitectura de uma

função agente
 Arquitectura
Arquitectura
vs. Programa
• Como é que agente irá agir fisicamente
• Exemplo um taxi autônomo
• Percebe que há uma curva a ser feita a 60
KM/h e está a 240 KM/h em cima da curva, a
acção a tomar é diminuir a velocidade .
Quanto em velocidade precisará diminuir para
fazer a curva. O programa numa hora dirá
frea.
Programa
• Programa ( estruturais condicionais (if, else),
tabelas, percepções etc.). O sensor deve saber o
mínimo permitido para fazer a curva e
arquitetura tem que frear, se não tiver freio
Medidas de desempenho
• Perfeição: o agente conhece todos os resultados
reais das suas acções e pode actuar sempre da
melhor forma possível (onisciente)
• Racionalidade: para cada sequencia de
percepções possíveis seleciona-se a acção que
supostamente maximiza o desempenho esperado
• Aprendizagem: conhecer todo o ambiente a priori
deve-se perceber e aprender para maximizar o
desempenho ( memoria);
• Exploração: recompilar a informação realizando
acções para modificar percepções futuras e
memorizando o resultado de cada acção;
• Autonomia: aprender tudo que puder para
compensar a falta de conhecimento a priori
Tipos de Agentes
•Agentes Reactivos Simples;
•Agentes Reactivos Baseados em
Modelos;
•Agentes Reactivos baseados em
objectivos;
•Agentes reactivos baseados na
utilidade.
 Agentes Reactivo Simples
Reage
• Através da Instrução que ele recebe executa
uma determinada acção .
Carro
• Ex. Carro da frente quando frea, o carro de
traz também frea, poderá verificar a distância
através, de lazer, camara;
• Processar a imagem do agente motorista de
táxi e verificar que “o carro da frente está
freando”;
• Ao invés de ter uma tabela com cada
mudança que ocorre na imagem,
“interpretamos” a condição da imagem
 Agente Reactivo Simples Baseado em Regras
função Agente-Reativo-Simples (percepção) devolve acção
estática: regras, um conjunto de regras condição-acção
estado ← INTERPRETA-ENTRADA(percepção )
regra ← CASA-REGRA (estado, regras)
acção ← AÇÃO-DA-REGRA(regra)
devolve acção

Descrição abstrata do estado do mundo a partir

da percepção
 Regra Condição_Acção
Se carro_da_frente_está_freando então
começar_a_frear
• Conexões nos seres humanos:
• Aprendidas: dirigir
• Reflexos inatos: tirar a mão do fogo, ou
piscar quando algo se aproxima do olho
• Projecto do agente;
• Construir um interpretador de uso geral para
regras de condição-ação
• Criar um conjuntos de regras para cada
ambiente de tarefa
 Estrutura do Agente
Simples
agente = arquitetura + programa

Agente
Sensor
Percepção
(Entradas)

Ambiente
Qual é a aparência
actual do Mundo ?

Regras condição Que acção devo

Acção? executar agora?

Acção(Saídas)
Actuador
 Exemplo Aspirador de Pó
A B

C
D

Percepções: Local e conteúdo

Acções: Esquerda, directa, Aspirar, Noop (Não fazer nehuma
operação)
 Vantagens e Limitações
Regras condição-ação: representação inteligível, modular e eficiente ex.
se velocidade > 60 então multar

Não pode armazenar uma sequência perceptiva, pouca autónomia

Funcionará somente se a decisão correta puder ser tomada com base

apenas na percepção actual

Ambiente completamente observável

Até mesmo uma pequena impossibilidade de observação pode causar

sérias dificuldades
 Exemplo de Problemas
Um agente presa que percebesse um
predador, iniciaria um comportamento
de fuga, virando as costas para o
predador, entretanto, já não o veria mais
e pararia de fugir. Seria interessante que
esse agente pudesse saber ou estimar
quanto o predador realmente ficou para
trás e não mais representa um perigo
iminente
 Agente Reactivo Baseado em Modelo
Utiliza o modelo do mundo, tem conhecimento de como o
mundo funciona
Como lidar com a possibilidade de observação parcial. O
gente deve controlar as partes do mundo que ele não pode ver
agora.

• Ex.: a presa ao dar as costas para o predador,

deve continuar fugindo...
O agente deve manter um estado interno que dependa do
histórico de percepções e reflicta os aspectos não observados
no estado actual.

• Dois tipos de conhecimento são necessários para

actualizar o estado interno do agente (modelo do
mundo):
 Modelo do Mundo
Como o ambiente evoluí independente do agente .
• O facto de o predador não estar no campo de
visão da presa durante a fuga não garante a
ausência de perigo.
Como as ações do próprio agente afetam o mundo
• Se o agente presa continuar o processo de
fuga durante um certo tempo ele poderá
estimar quando o predador realmente ficou
para
 Algoritmo
function agente_reflexo_estado(percepção):açcão
static: estado (uma descrição do estado actual do mundo)
regras (um conjunto regra condição-ação)
estado ← actualiza_estado (estado,percepção)
regra ← casamento_regra ( estado,regras)
açcão ← açcão_regra[regra]
return acção
Actualiza_Estado –> é responsável por criar uma nova
descrição do estado interna
 Agente Reactivo Baseado
em Modelos
Agente

Estado
Sensor
Percepção

Ambiente
Ambiente
Como o mundo
era antes e
Como está o
como evoluiu
Mundo Agora ?
Impacto da
minhas acções
Que acção devo
Regras de
executar agora?
condição- Acção
Acção
Actuador

Modelo de como a poera evolui ao longo do tempo

 Limitacões
Conhecer os estados do ambiente não é suficiente para tomar uma
boa decisão

Exemplo

• o agente Motorista de Táxi chega a um cruzamento com

três caminhos, qual direção tomar?
• Simplesmente reagir: mas existem três reações possíveis
• Examinar o modelo de mundo: não ajuda a decidir qual o
caminho
• A decisão depende de onde o táxi está tentando chegar
(objetivo)
 Agente Baseado em Objectivos
O agente precisa de algum tipo de informação sobre o seu
objectivo

Objetivos descrevem situações desejáveis. Ex: estar no destino

Combinando informações sobre:

• O objetivo do agente
• Os resultados de suas ações
O agente pode escolher ações que alcancem o objetivo
• A seleção da açcão baseada em objectivo pode ser:
• Directa: quando o resultado de uma única ação atinge o
objetivo;
• Mais complexa: quando será necessário longas sequências
de açcões para atingir o objectivo;
• Busca é um subcampo da IA dedicado a encontrar
sequencias de açcões que alcançam os objetivos dos
agentes)
 Cont..
Para encontrar sequências de ações que alcançam os
objectivos

• Algoritmos de Busca
• A tomada de decisão envolve a consideração do futuro
• “O que acontecerá se eu fizer isso ou aquilo?”
• “O quanto isso me ajudará a atingir o objetivo?”
• Agentes reactivos: reaçcão -> frear quando carro da frente
• frear. Simplesmente aplica a regra condição-ação
• Agentes baseado em objetivo: raciocínio -> carro da frente
freia -> carro da frente diminui velocidade -> objetivo: Não
atingir outros carros -> açcão para atingir objectivo: travar
 Agente Reactivo Baseado
em Objectivos
Agente
Sensor
Percepção
Estado

Ambiente
Como o mundo Como está o
era antes e Mundo Agora ?

Ambiente
como evoluiu
Efeitos da Sinulação de
minhas acções Acções(Como o
mudo ficará se
realizar acção X)

Objectivos Que acção devo

executar agora?
Acção

Actuador
Ex. minimizar a poera no ambiente
 Limitações
É mais flexivel
• Agente reflexo -> açcões pré-compiladas
(condição-açcão)
• Agente p/ objetivo -> pode alterar somente o
objectivo sem necessidade de se reescrever as
regras de comportamento
Permite modificações
• O objectivo não garante o melhor comportamento
para o agente, apenas a distinção entre estados
objectivos e não objectivos;
• Ex: Algumas alternativas de planeamento de
açcões futuras podem ser mais rápidas, seguras ou
baratas que outras
 Agente Baseado em utilidade
Sozinhos os objetivos não são suficientes para gerar um
comportamento de alta qualidade.
• Muitas seqüências de açcões levarão o táxi até seu destino,
porém algumas são mais rápidas, seguras e económicas
• Se um estado do mundo é mais desejável que outro, então
ele terá maior utilidade para o agente
• Utilidade é uma função que mapeia um estado para um
número real que representa o grau de satisfação com este
estado. A função de utilidade mede suas preferências entre
estados do mundo
• Especificação completa da função de utilidade – decisões
racionais em dois tipos de casos:
• Quando existem objetivos conflitantes (velocidade x
segurança) a função de utilidade especifica o compromisso
apropriado
• Quando existem vários objetivos que se deseja alcançar e
nenhum deles pode ser atingido com certeza – ponderar a
importância dos objectivos
 Agente
Agente Utilidade
Sensor
Percepção

Estado

Ambiente
Como está o

Ambiente
Como o mundo Mundo Agora ?
evoluiu
Sinulação de
Efeitos da Acções(Como o
minhas acções mudo ficará se
realizar acção X)
Utilidade Utilidade de Acções(Quão satisfeito
estarei nesse estado?)
Acção
Que acção devo
executar agora?

Actuador
 Agente Baseado
Em agentes sem aprendizagem tudo em
o queApredizagem
o agente sabe
foi colocado nele pelo projectista
• Aprendizagem também permite ao agente actuar
em ambientes totalmente desconhecidos e se tornar
mais competente do que o seu conhecimento inicial
poderia permitir Ex. motorista sem o mapa da
cidade

Componentes conceptuais

• Elemento de aprendizado
• Crítico
• Elementos de desempenho
• Gerador de problemas
 Agente Baseado em Apredizagem
Elemento de Apredizado(Modificador de Regras)
• Responsável pela execução dos aperfeiçoamentos
• Utiliza realimentação do crítico sobre como o
agente está funcionando
• Determina de que maneira o elemento de
desempenho
Crítico
• Informa ao elemento de aprendizado como o
agente está se comportando em relação a um
padrão fixo de desempenho
• É necessário porque as percepções não fornecem
nenhuma indicação de sucesso
• Ex.: O crítico pode indicar para o agente que o
xeque-mate é algo bom. O agente não deverá
modifica-lo
 Agente Baseado em Apredizagem
Elemento de desempenho

• Responsável pela seleção de ações externas

• Recebe percepções e decide sobre ações

Gerador de problemas
• Responsável por sugerir ações que levarão a
• experiências novas e informativas. Ações não
ótimas a curto prazo para descobrir
• ações ótimas a longo prazo
 Exemplo Motorista de Taxi
Elemento Crítico: conhecimento e procedimentos paradirigir
• Ex.: o agente vira sem dar seta. O crítico observa que
isso gera uma reação agressiva dos outros motoristas e
informa ao elemento de aprendizagem.
• Elemento de Apredizado
Elemento de Apredizado
• É capaz de formular uma regra afirmando que a ação foi
boa/ruim. Modifica o elemento de desempenho pela
instalação da nova regra

Gerador de problemas:
• Identifica áreas que precisam de melhorias
• Sugere experimentos: testar os freios em diferentes
superfícies
 Inteligência colectiva
Situações /solução

• Porque pensar a inteligência/racionalidade como

propriedade de um único indivíduo?
• Não existe inteligência ... Em um time de futebol? ; Em
um formigueiro?; Em uma empresa (ex. correios)?
• Na sociedade?
• Solução: IA Distribuída
• Agentes simples que juntos resolvem problemas
complexos tendo ou não consciência do objetivo global
• Proposta por Marvin Minsky e em franca expansão...
• o próprio ambiente pode ser modelado como um agente
 IA Distribuida
Tipos de Sistemas

• Resolução distribuída de problemas

• Consciência do objetivo global e divisão clara de
tarefas
• Exemplos: Robótica clássica, Busca na Web,
Gerência de sistemas distribuídos, ...
• Sistemas Multi-Agente
• Não há consciência do objecto global e nem divisão
clara de tarefas ex. n-puzzle, futebol de robots,
balaneaceamento de carga, robótica
 Questões
Centrais

• comunicação
• negociação (ex. compra-venda na Web)
• estados mentais
• crença,
• Tensão (Trade-Off)
• Quanto mais agentes, mais simples
(subdividido) fica o problema
• No entanto, mais complexa fica a
comunicação e coordenação entre os agentes
 Padrão de
Desempenho
Agente com Apredizado
Crítico
Sensor
Percepção
Feedback
Alterações

Ambiente
Elemento de Elemento de

Ambiente
Apredizado Desempenho
Conhecimento
Objectivos de
Apredizado

Gerador de
Problemas
Acção
Actuador
Agente
 Avaliar o Sucesso
Como

Através de Definição de Médidas de Desempenho

objectiva e imposta por um observador externo

Quando

Durante a realização das tarefas pelo agente

Ambiente Condução de
Comparação
Palavras Cruzadas Análise de Imagens
Taxi
Observável Parcial Completo Completo
Deterministico Estócastico Deterministico Deterministico
Episódico Sequencial Sequencial Episódico
Estático Dinámico Estático Semi
Discreto Contínuo Discreto Contínuo
Agentes Multiplos Único Único

O tipo do do Agente determina o projecto do agente

O mundo real é parcialmente observável, estocástico, sequencial, dinámico,

contínuo e multiagente
 Medidas de Desempenho Critério que define o grau de sucesso de um agente
na realização de uma dada tarefa
Tipo de Medidas de Ambiente Actuadores Sensores
Agente Desempenho
Aspirador de ▪ Quantidade de ▪ Sala
Pó Sujeira Aspirada ▪ Quarto
▪ Gasto de Tempo
▪ Quantidade de
Barrulho Gerado
▪ Gasto de Energia

Carro ▪ Não teve nenhum • Estrada ▪ Acelerador, ▪ Distância,

Autónomo acidente, • Garagem ▪ Freio, ▪ Velocidade
▪ Não estragou no ▪ Abre a porta, ▪ Temperatur
caminho, ▪ fecha a a interna
▪ Passageiro saiu porta, ▪ Iluminação
de A e chegou em ▪ liga ar ▪ GPS, etc
B condicionad
o
 Medidas de Desempenho
Tipo de Medidas de Ambiente Actuadores Sensores
Agente Desempenho
Carro Viajem estrada Direcção Camara
Autónomo Segura
Dentro da lei Cliente Acelador Sonar
Confortavel Piões Travões GPS
Sinal Hodometro
Busina Sensor do
Motor
Visor
 Exemplo de Aplicações
Aplicações
Agricultura Processamento de imagem
Negócios e finanças Direito,
Química Indústria
Comunicações Matemática
Comércio Medicina, comércio electrónico
Computação Meteorologia
Educação Militar
Eletrônica Sistemas de potência
Engenharia Ciência
Meio ambiente Tecnologia espacial
Geologia Transportes, ...
Internet e redes Correio eletrônico, gestão de sistemas de redes
Recuperação de Acesso e gestão de informação
dados
Desenvolvimento de SW Inteligentes
Projecto

• Modelar tarefa em termos de ambiente,

• percepções, ações, objetivos e utilidade
• Identificar o tipo de ambiente
• Identificar a arquitetura de agente adequada ao
ambiente e tarefa

Implementação

• o gerador e o simulador de ambientes

componentes do agente (vários tipos de
conhecimento)
• Testar o desempenho com diferentes instâncias do
ambiente
 Porque e Quando Utilizar
Tarefas
• Grande complexidade (número, variedade e natureza
das tarefas)
• Não há “solução algorítmica”, mas existe
conhecimento
• Modelagem do comportamento de um ser
inteligente (autonomia, aprendizagem,
conhecimento, etc.)

Algumas Capacidades
• Comportamento guiado por objetivos e autonomia
• Reatividade e raciocínio
• Adaptabilidade e aprendizagem
• Comunicação e cooperação
• Personalidade
• Outros mobilidades
 Resumo
Agente: arquitetura + programa do agente;

Agente ideal: escolhe a ação que maximiza sua medida

de desempenho, dada a sequência de percepção;

Agente autônomo: experiência própria ao invés de

depender do conhecimento pré-codificado sobre o
ambiente

Projecto (design) do agente depende do tipo de

informação disponível e usada no processo de decisão;

O projecto apropriado depende da descrição PEAS do

agente
 Métodos de Busca
Problemas de Busca
• Modelar um problema de busca consistem
em
• Identificar Estado do Mundo
• Actual
• Objectivo
• Definir as transições
• Escolher Algoritmo de Busca
Problema de busca consiste
• Encontrar uma sequência de acções que
conduzem do estado actual ao estado
objectivo
 Cont..
Questões
• Quantos sites indexados existem na internet?
• Quantas ruas mapeadas existem na Google Maps?
• Quais as possiveis combinações de jogadas num jogo
de xadrez

Os algoritmos de busca responde as perguntas anteriores

• Achar um objecto x numa estrutura Y
• 2008 – Google indexava – 1T de sites – Busca binária
um vector ordenado
• Melhor rota entre duas ruas por exemplo. Dijkastra
• Minimax
 Busca Binária
Busca na estrutura de vector
• Lista Telefónica

• A complexidade é da ordem O(n)-Log(n)

Exemplo(vector em forma de Árvore)
14

6
29

5 17 36

1 7
32 54
N elementos da árvore Log(n) complexidade da busca < O(n)
Busca de elemento 32
Pseudocódigo
• 1º 32>14 descarta o ramo a esquerda
• 2º 32>29 descarta o ramo a esquerda
• 36>32 descarta o ramo a direita

Pseudocódigo
• Busca_binária(V[], ínicio, fim, e)
• i recebe o índice do meio entre ínicio e fim
• Se (V[i]=e) então
• Devolva o índice e # elemento é encontrado
• Fim-se
• Se (inicio=fim) então
• Não encontrou o elemento procurado
• Senão se (V[i] vem antes de e) então
• faça a busca binária( V, i+1, fim, e)
• Senão
• faça a busca binária(V,ínicio, i-1, e)
• Fim-se
• Fim
 Métodos de Busca
Busca não Informada- Busca exaustiva Cega ou aleatória

• Não leva em conta informações sobre o problema

• Não sabe qual é o melhor caminho a seguir do estado inicial ao final;
porque não tem informações sobre o problema (sobre se está perto ou
longe do nó objectivo)
• Estratégias de Busca (ordem de expansão dos nós): Largura e
profundidade
• Direcção de busca: estado inicial-objectivo/objectivo-estado inicial
• Algoritmos BFS e DFS

Busca Heurística- Informada

• Estima qual o melhor nó da fronteira a ser expandido com base em funções
heurísticas conhecimento
• Estratégia de Busca: best first search (Melhor escolha)
• Direção de Busca: idem à busca cega
• Algoritmos: greedy, Search A*

Busca Competitiva
• Algoritmo Minimax
 Métodos de Busca

Busca Cega

• O agente não tem nenhuma

informação no percurso fora dos
seus vizinhos;
• Quando chega a uma posição apenas
sabe que são os seus vizinhos
 Métodos de Busca
Resolução de problemas através de força bruta

• O programa tenta todas alternativas para resolver o problema

Algoritmo de busca

• Recebe descrição do problema e descrições de operações

elementares

Exemplo de Problema ( 8-Puzzle)

• Estado Incial Estado Final

1 2 3 1 2 3
5 6 4 5 6
4 7 8 7 8
[1,2,3,0,5,6,4,7,8] [1,2,3,4,5,6,7,8,0] Representação através da lista
 Operações 8-Puzzle
Opererações

• Mover o espaço em branco para baixo;

• Mover o espaço em branco para cima;
• Mover o espaço em branco para a direita; e
• Mover o espaço em branco para a esquerda.

Especificação de Operações

• move_right(State1, State2):-
• space_position(State1, Pos, Part1, [X|Part2]),
• \+ member(Pos, [3, 6, 9]),
• append(Part1, [X, 0|Part2], State2).
• O programa recebe um estado e produz a representação do estado que
resulta a aplicação da operação
Exempo A procura em profundidade primeiro e a procura em largura primeiro
são algoritmos de força bruta
• Procuram, às cegas, todas as possíveis sequências de operações até
encontrar uma solução para o problema recebido
 Resolução de Problemas Reais
Possibilidades ou Alternativas
• Envolve quantidades astronómicas de
possibilidades, o que conduz a tempos de
resolução inaceitáveis em muitas
circunstâncias
• necessário guiar a procura de soluções na
direção mais promissora, o que exige
conhecimento do domínio do problema.
Best First search (melhor primeiro)
• A busca não é cega. cada decisão que tem de tomar,
encaminha-se para aquela que parecer melhor.
 Conceitos Importantes Métodos de
Busca

Conceitos

• Estado ( estado inicial ou de partida) e estado final ou

objectivo
• Espaço de estados ou de procura: conjunto de todos os
estados que representam configurações do mundo
relativamente aos aspectos relevantes para o problema.
Puzzle um estado é uma lista de números
[0,1,2,3,4,5,6,7,8]. 9!= 362.880 estados possíveis para o
espaço de procura. 15-Puzzle versão habitual 16!=
[Link].000 estados (mais do que 20 milhões de
milhões de estados)
 Cont.
Operador

• As ações que se podem aplicar aos estados ex. Puzzle:

• Mover o espaço em branco para baixo;
• Mover o espaço em branco para cima;
• Mover o espaço em branco para a direita; e
• Mover o espaço em branco para a esquerda.

Solução

• O algoritmo de procura vai aplicando operações até que

eventualmente encontra um estado final. Aplicação de
sequência de operações até o estado final. O mesmo
problema pode ter várias soluções
 Cont.
Duração da procura e comprimento da solução

• tempo e memória gastos na procura da solução,

e o tempo e memória gastos para aplicar a
solução descoberta pelo algoritmo

Geração e Expansão de estados

• Aplica as operações ao estado inicial e gera um

conjunto de estados sucessores, depois escolhe um e
volta aplicar todas operações possíveis a este. O
processo é repetido até encontrar o estado final. Este
processo é chamado de expansão e este gera os
estados
 Cont..
Independência do domínio do problema
• Na expansão de um estado os algoritmos explicam as
operações de domínio e poder determinar se um
estado é final. Logo deve incluir dois programas
(expansão e determinador do estado final) ,melhor
primeiro inclui outro programa para avaliar cada
estado quão promissor é (fusão heurística).

Três programas
• Encapsulam todo o domínio do conhecimento do
problema
• Permite que o resto do algoritmo continua totalmente
idempendente do domínio da da aplicação
 Exemplo
Expansão e Geração
E
B
H
A C F

D G I

A é o primeiro expandido e gerado a sua expansão gera os

sucessores B,C,D. A cada expansão gera sucessores
 Exercício
Expansão e Geração
E
B
H
A C F

D G I

Explica a expansão caso fossem utilizados algoritmos de busca em

profundidade e em largura primeiro
 Resolução Puzzle
Estado inicial Estado final

1 2 3 1 2 3 1 2 3 1 2 3
Abaixo Direita Direita
5 6 4 5 6 4 5 6 4 5 6
4 7 8 7 8 7 8 7 8

Resolução possível a sequência de accções: mover o buraco abaixo, a direita e

repetir a direita
Critérios de Avaliação de Estratégias de Busca
Completitude

• A estratégia sempre encontra uma solução quando existe alguma?

Custo de Tempo

• Quanto tempo gasta para encontrar uma solução?

Custo de Memória

• Quanta memória é necessária para realizar a busca?

Otimalidade/qualidade (optimality):

• A estratégia encontra a melhor solução quando

• existem diferentes soluções?
 Medidas de Desempenho de Busca
Desempenho de Algoritmo de Busca
• 1. O algoritmo encontrou alguma solução?
• 2. É uma boa solução? – custo de caminho (qualidade
da solução)
• 3. É uma solução computacionalmente barata?– custo
da busca (tempo e memória)

Custo de Total
• Custo do caminho + custo de busca

Espaço de Estado Grande

• compromisso (conflito) entre a melhor solução e a
solução mais barata
 N-Puzzle Jogo dos N
Jogo de 8 números:
2 3
• n números dispostos em um
quadrado com uma célula em
branco
1 8 4
• a cada jogada pode-se trocar
número e célula em branco
adjacentes
7 6 5
• Objectivo:rearranjar números
em ordem crescente
1 2 3
4 5 6
7 8
N-Puzzle 2 3 7
8
6
4
5
1 8 4
7 6 5
2 3
1 8 4
7 6 5
2 3
1 8 4 2 3
2 3 7 6 5 1 8 4
1 8 4 7 6 5
7 6 5
2 8 3 2 3 4
1 4 1
7
8
5
7 6 5 6
N-Puzzle
Solução
• estados = cada possível configuração do tabuleiro
• estado inicial = qualquer um dos estados possíveis
• teste de término = ordenado, com branco na posição [3,3]
• operadores = mover branco (esquerda, direita, para cima e
para baixo)
• custo da solução = número de passos da solução

2 8 3
2 8 3 1 4
1 4 7 6 5
7 6 5
2 8 3
1 4
7 6 5
Exemplo de Problema de Busca
Ir de Bauru a São Paulo
 Exemplo Viagem
Ir para São Paulo

Estados (espaço de estados) = cada possível cidade do mapa

• estado inicial = Bauru Em(Bauru)

• teste de término = estar em São Paulo Em(SaoPaulo)
• operadores = dirigir de uma cidade para outra

Operadores=dirigir de uma cidade para outra

• Dado um estado x, SUCESSOR(x) retorna um conjunto de pares ordenados

(ação, sucessor), em que cada ação é uma das acções
• válidas no estado x, e cada sucessor é um estado que pode ser alcançado a
partir de x aplicando-se a acção.
• Ex.: {(Ir(Bauru, Em(Bauru))}
• Juntos o estado inicial e a função sucessor definem o espaço de estados
• custo do caminho = número de cidades visitadas, distância percorrida, tempo
de viagem, grau de divertimento,etc.
 Exemplo Aspirador de Pó
Aspirador de Pó

Estados (espaço de estados) = cada possibilidade

do lado
• estados = as 8 possibilidades ao lado
• estado inicial = qualquer um dos estados

teste de término=verifica se todos os quadrados

estão limpos

Operadores=operadores = (esquerda, direita,

aspirar)

custo da solução = cada passo custa 1, e assim o

custo é o número de passos do caminho
 Exemplos
Aplicações
• Jogos ed N-Rainhas
• Jogos de N-Números (Puzzle)
• Criptomoedas
• Torre de Hanoi
• Palavras cruzadas
• Canibais e Missionários

Cálculo de rotas

• Rotas em redes de computadores

• Planeamento de ações militares
• Sistemas de planeamento de viagens
• Planeamento de rotas de aviões
• Caixeiro viajante
• Jogos de computadores (rotas dos personagens)
• Pesquisas na internet ( grafo de nós (páginas) conectadas por links
Alocação(Sheduling)
• Sala de Aulas
Projecto VSLI
• Cell layout (disposição de células na área do chip)
• Channel routing (rota para fios passando por espaços vazios entre as células)
 Cont..
Navegação de Robots

• Generalização do problema da navegação

• Robôs movem-se em espaços contínuos, com um conjunto
(infinito) de possíveis ações e estados – controlar os
movimentos do robô no chão, e de seus braços e pernas
requer espaço multi-dimensional

Montagem de Objectos complexos pelos robots

• Ordenar a montagem de várias partes dos objectos

 Busca Cega
Estratégias para determinar a ordem de ramificação
dos nós:
• 1. Busca em largura (busca em extensão)
• 2. Busca de custo uniforme
• 3. Busca em profundidade
• 4. Busca com aprofundamento iterativo

Direcção de Ramificação

• 1. Do estado inicial para um estado final

• 2. De um estado final para o estado inicial
• 3. Busca bi-direcional
 Busca primeiro em Largura e Profundidade

Busca Profundidade Primeiro

1 2 3 6 1 2 3
1 2 3
4 5 6 Direita 4 5 6 Cima 4 6
2:2
7 8 5:3 7 8 D 7 5 8
ire
ita
i xo
Aba 2 3
1 2 3 1 2 3
1 5 6
5 6 7 4 5 6
Acima 4 7 8
4 7 8 3 7 8
Dir
1:1 eit 1 2 3
a
5 6
4
4 7 8
 1 2 3 a
1 2 3 Cont..
Acim 4 6
4 5 6
Busca Largura Primeiro 7 8 7 5 8
Ad

ita
5:5 ire 10
ita

re
2 3

Di
1 2 3 1 2 3
1 5 6
4 5 6 4 5 6
4 7 8
7 8 7 8
6

a
xo 2:2
it
i
Aba Di
re
1 2 3 11
1 2 3 2 3 5 7 6
5 6 1 5 6 4 8
Acima 7
4 7 8 4 7 8 o
Dir ix 1 3
eit 3:3 A ba
1:1 a 5 2 6
1 2 3
A cima 4 7 8 Escolha sempre o nó não
5 6 8 espandido menos profundo
Di
re
4 7 8 ita 1 2 3
5 6
4:4
4 7 8 9
 Cont..
Limitações
• A maioria dos problemas reais têm espaços de estados
muitíssimo grandes e, em alguns casos, infinitos.
• Os recursos consumidos por um algoritmo de procura
para em alguns casos, infinitos.
• Os recursos consumidos por um algoritmo de procura
para encontrar uma solução (tempo e memória)
dependem do tamanho do espaço do problema.

Solução
• É importante que algoritmo não procure todo o espaço
e deve ncaminhe por uma trajetória que conduza mais
rapidamente ao objectivo
• para que o algoritmo saiba qual dos caminhos é mais
promissor, necessita usar
• conhecimento específico sobre o problema que está a
resolver e escolher depois da avaliação àquele mais
promissor
 Busca em Largura (BFS)
Estratégias para determinar a ordem de ramificação
dos nós:
• Ordem de ramificação dos nós:
• 1. Nó raiz
• 2. Todos os nós de profundidade 1
• 3. Todos os nós de profundidade 2, etc.
• Percorre todos os nós vinhos da fronteira antes de
passar para o próximo nível
Algoritmo
• 1função Busca-em-Largura (problema)
• retorna uma solução ou falha
• Busca-Genérica (problema, Insere-no-Fim)
 Cont..
BFS

• Percorrer todos os visinhos do nó actual, antes de passar pelo próximo

no, em cada no checa se é a cidade destino
• Visitar vizinhos dos vizinhos, não visitadas ainda, visita sempre
começa pelo vizinho a esquerda e se não for o objectivo faz o
Backtracking, para visitar os póximos vizinhos do outro nó.
• Algoritmo
• Um dicionário com Cidades no mapa ordenado de 1 a 11
• Lista de lista para indicar como está representado o grafo, indicando os
vizinhos de cada non
• A busca implementada é procedurar não recursiva, mais pode ser feita
de forma recursiva
• Crie uma lista que funcionará como uma fila e adiciona o no de partida,
usa o append que equivale a enfileirar
• Retira o no da fila utilizando o método pop(0), para indicar que será
retirado o 1º Elemento
• Temos uma estrutura que guarda a informação se o no já foi visitado ou
não, todos começam com zero para indicar que não foram visitados
ainda
 Busca do Espaço_ Estado
Busca do Objectivo

• Uma vez o problema bem formulado... o estado final deve

ser “buscado”
• Em outras palavras, deve-se usar um método de busca
para saber a ordem correcta de aplicação dos operadores
que levará do estado inicial ao final
• Uma vez a busca terminada com sucesso, é só executar a
solução (= conjunto ordenado de operadores a aplicar)

Fronteira do espaço de estados (borda)

• Nós (estados) a serem expandidos no momento. Coleção

de nós que foram gerados mas ainda não expandidos
 Algoritmos
Busca do Objectivo

• Selecionar o primeiro nó (estado) da fronteira do espaço de

estados;
• Se a fronteira está vazia, o algoritmo termina com falha
• 2. Testar se o nó é um estado final (solução)
• Se sim, então retornar nó – a busca termina com sucesso
• 3. Gerar um novo conjunto de estados pela aplicação dos
operadores ao estado selecionado; 4. Inserir os nós gerados na
fronteira, de acordo com a estratégia de busca usada, e voltar
para o passo (1).

Obs.

• O algoritmo começa com a fronteira contendo o estado inicial

do problema.
 Cont..
A ideia principal é achar caminhos
minimos. Dado um vertice é preciso saber a
sua distância em relação aos outros
A
B C D
K
• E.x várias caixas de água
conectadas por diversos
tubos, poderia querer saber
que caixa está mais
E F K+1

próxima da caixa, suponha

que a rede seja muito
grande
 Método BFS
Ordem de ramificação dos nós

• 1. Nó raiz
• 2. Todos os nós de profundidade 1
• 3. Todos os nós de profundidade 2, etc.

Algoritmo

• função Busca-em-Largura (problema)

• retorna uma solução ou falha
• Busca-Genérica (problema, Insere-no-Fim)

A A
A

B C B C
B C

G D E F G
D E F D E F G
 Método BFS
A estratégia é Completa

• Sempre encontra a solução mais “rasa” que nem sempre é a

solução de menor custo de caminho, caso os operadores
tenham valores diferentes
• ex. ir para uma cidade D passando por B e C pode ser mais
perto do que passando só por E

Óptima

• Em outras palavras, é óptima se custo de caminho cresce com

a profundidade do nó
• O que ocorre quando todos os operadores têm o mesmo custo
(=1)
 Método BFS
Definine o factor de ramificação da árvore de busca
• Número de nós gerados a partir de cada nó (b), ou seja,
número máximo de sucessores de qualquer nó.
Custo de tempo
• se o fator de ramificação do problema = b, e a primeira
solução para o problema está no nível d,
• então o número máximo de nós gerados até se encontrar a
solução = 1 + b + b2 + b3 + W + bd
• custo exponencial = O (bd).
Custo de Memória
• problema mais crucial: a fronteira do espaço de estados deve
permanecer na memória
• logo, busca em largura só dá bons resultados quando a
profundidade da árvore de busca é pequena.
Algoritmo BFS
A

B C D K

E F K+1
 Exemplo
Explora a vizinhança dos nós já visitados, na
ordem 1º a entrar 1º a sair
2
A

G
1
B 3
E
D

4 F
C

Nós Visitados Nós não

Visitados
 Exemplo
1 2 8 1
0

1
3 4 7
1

9
5 6
 Execução
1 2 3 4 5 6 7 8 9 10 S=7
Visitados 0 0 0 1 0 0 1 0 0 1
N N N 7 N N N N N 7
Predecessor

7
BFS: 7, 4,10, 11,
1
4 0 11
mD = {
0: 'F',
1: 'MO',
2: 'JU',
Python BFS
3: 'P',
5: 'CG',
4: 'N', F
7: 'A',
6: 'JP',
9: 'JP',
8: 'CA',
10: 'R', M
11: 'MA'}
grafo = [[2, 1], # vizinho do nó o
O
[5, 4, 0], # vizinho do nó 1
[3, 0], # vizinho do nó 2 N
[7, 5, 2], # vizinho do nó 3
[6, 1], # vizinho do nó 4
[8, 6, 3, 1], # vizinho do nó 5 J
[10, 5, 4], # vizinho do nó 6
U P CG
[11, 3], # vizinho do nó 7
[11, 10, 5], # vizinho do nó 8 JP
[10, 5, 4], # vizinho do nó 9
[11, 8, 6], # vizinho do nó 10
[10, 8, 7]] # vizinho do nó 11
def buscaEmLargura(nohDeDepartida, nohDeChegada): C
fila = []
[Link](nohDeDepartida)
A R
while len(fila) > 0:
noh = [Link](0)
nohsVisitados[noh] = 1 A M
print(mD[noh])
if noh == nohDeChegada:
A
print('Chegou ao Destino')
break
for n in grafo[noh]:
if nohsVisitados[n] == 0:
nohsVisitados[n] = 1
[Link](n) Ir de F até MA
nohDePartida = 0
nohDeChegada = 11
 Métodos DFS

Ordem de Ramificação dos Nóns

• Muito poderoso e tem diversas aplicações;
• Posso utilizar para saber se um grafo
enormes tem ciclo;
• Descobrir componentes fortemente
conexos de um grafo
 Métodos DFS
Passos

B C D

E F
 Métodos DFS
Ordem de Ramificação dos Nóns
• Sempre expande o nó no nível mais profundo da árvore:
• 1. nó raiz
• 2. primeiro nó de profundidade 1
• 3. primeiro nó de profundidade 2, etc.
• Quando um nó final não é solução, o algoritmo volta para
expandir os nós que ainda estão na fronteira do espaço
de estados (backtracking)

Algoritmo
• função Busca-em-Profundidade (problema)
• retorna uma solução ou falha
• Busca-Genérica (problema, Insere-no-Começo)
 Métodos DFS
Expansão dos Nóns

1 A • Os nós que foram

expandidos e não têm
9 descendentes na
C fronteira podem ser
2 removidos da
B
memória, eles são
13 indicados em cor
6 10 G vermelha.
D E F
3 • Supomos que os nós
8 na profundidade 3 não
tem sucessores e que
H I J K L M N O M é o único nó
objectivo
4 5 7 11 12 14 15
 Estratégias de Profundidade
Não é completa e tão pouco óptima
• Esta estratégia deve ser evitada quando as árvores geradas são
• muito profundas ou geram caminhos infinitos.

Custo de Memória
• necessita armazenar apenas b.m nós para um espaço de
• estados com fator de ramificação b e profundidade m, onde m
• pode ser maior que d (profundidade da 1a. solução).
Custo de Tempos
• O(bm ), no pior caso.
• Para problemas com várias soluções, esta estratégia pode ser
• bem mais rápida do que busca em largura.
Métodos DFS
 Métodos DFS
Implementação

Espaço de estado
• Podem ser representados como uma árvore onde os estados são nós e as
operações são arcos

Os nós da árvore podem guardar mais informações do que apenas o estado:

• São uma estrutura de dados com 5 componentes:
• 1. O estado correspondente
• 2. O seu nó pai (nó que gerou esse nó)
• 3. O operador aplicado para gerar o nó (a partir do pai)
• 4. A profundidade do nó (número de passos ao longo do caminho, desde o
estado inicial
• 5. O custo do nó (desde a raiz) tradicionalmente denotado por g(n)
 Exemplo
6
1
5

7
2
4

8
3

10 9
Exemplo
 Métodos DFS
4: 'N',
7: 'A',
6: 'JP',
9: 'JP',
8: 'CA',
10: 'R',
11: 'MA'}
grafo = [[1, 2], # vizinho do nó 0
[0, 4, 5], # vizinho do nó 1
F
[0, 3], # vizinho do nó 2
[2, 7, 5], # vizinho do nó 3
[1, 6], # vizinho do nó 4
[1, 3, 6, 8], # vizinho do nó 5 M
[4, 5, 10], # vizinho do nó 6
[3, 11], # vizinho do nó 7
O
[5, 10, 11], # vizinho do nó 8
[4,5, 10], # vizinho do nó 9 N
[6, 8, 11], # vizinho do nó 10
[7, 8, 10]] # vizinho do nó 11
J
nohsVisitados[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
U P CG
nohDePartida = 0
nohDeChegada = 11 JP
def buscaEmProfundidade(nohDeDepartida, nohDeChegada):
pilha = []
[Link](nohDeDepartida) C
while len( pilha) > 0:
noh = [Link]()
A R
if nohsVisitados[nohdaVez] = =0:
nohsVisitados[nohdaVez]=1
print(mD[nohdaVez]) A M
if nohdaVez == nohDeChegada:
print('Chegou ao Destino')
A
break
else:
for noh in grafo[nohdaVez]:
[Link](noh)
 Métodos DFS
Procedimento

• Para cada vertice pertencente ao conjunto de vertices

do grafo G ve o nó adjante , e pega o 1º adjacente , se
não está ainda descoberta colorir com uma cor e passa
para o próximo adjacente dele e repite o
procedimento, da a raiz até a útima folha e depois volta
pelos nós predecessores (volta fazendo a árvore de
predecessores)- do nó que estou a partir de que nó se
chegou nele
• Arestas de árvore. Liga os ancestrais aos seus
dependentes que estão no caminho da busca em
profundidade
• Arestas de <-Retorno: Aresta filho voltando para o pai
• Arestas direita
• Arestas cruzadas
 Limitações

BFS e DFS
• Não são considerada buscas inteligentes, por
percorrerem e visitarem todos os vertices dos
grafos
• Não tem objectivos predeterminados a
alcançar.
• Utiliza conceitos de pilhas e filas onde os
valores para percorrer todos os nóns
 Métodos A*
Procura no melhor primeiro (Best-First Search)
• Baseia no princípio de avaliar os nós já conhecidos do espaço de procura e expandir o
melhor deles.
• utilização de uma função de avaliação dos estados, a qual permite ao algoritmo escolher
para expandir, em cada passo, o nó mais promissor

Fusão de Avaliação (Função Custo)

• f(n) = g(n) + h(n), em que g(n) é o custo do caminho desde o estado inicial ao estado
representado no nó n; e h(n) é a estimativa do custo do melhor caminho que liga o nó n ao
estado final.
• Termina sempre, mesmo que não haja solução para um problema e não fica preso em
ciclos infinito
• Se a estimativa h(n) for sempre menor do que o custo real mínimo do caminho entre o nó
n e um nó objectivo, então o A* encontra a melhor solução para o problema, se ela existir.
• Se h(n)=0 para qualquer nó n, o algoritmo A* dá os mesmos resultados que o algoritmo de
caminho ótimo de Dijkstra.

Aplicações

• Sistemas de GPS
• Jogos (ex. jogos de tiro, faz traçado de menor rota para atingir o alvo)
• Unit de jogos implementa muitos algoritmos A*
 Métodos A*
A distância em linha recta é a heurística, uma forma
de resolver o problema para ajudar o algoritmo Distância em linha recta

Busca A estrela, algoritmo importante de IA, originou a implementação de GPS,

muito utilizado em jogos, traça a menor rota entre o inimigo e que atira, muito
implementado em Unit,
Utiliza a tabela de Heuristicas vistas na busca golusa
 Arad
Métodos A*
118
374 75 329
140 Timisoara Factores que aumentam o
Zerind 253 custo financeiro
Sibiu 447
449 - Entrar na cidade
393
- Pasar por portagem

151 99
80 178
380 193
Aradea Rinnicu Fagaras
531 273 277
7 147
98 160
Adicionar Heuristicas
Piteste Craiova
- Via com pontos turisticos
145 306
- O trecho é perigoso tem
0 101 assaltos frenquentes
Bucareste - Quantas portagens em
101 cada trecho
 Métodos Greedy Search
Estratégia de Busca Gulosa
• Estratégia gulosa é aquela usada por um montanhista que decide
caminhar sempre "para cima", na direção de "maior subida"
• Na esperança de assim chegar ao pico mais alto da montanha.
• Escolhe, em cada iteração, o objecto mais "apetitoso" que vê pela
frente
• Utiliza heurísticas (distância em linha recta), metríca muito utilizado
por sistemas de GPS para verificar a menor distância entre dois
trechos
• GPS armazena uma tabela com todas as heuristicas para suporte a
decisão
• Os valores são colocados numa estrutura ordenada (i.e Vector)
Heurísticas
• A distância em linha recta funciona se tem um mapa
cartesiano(localização das cidades na terra)
• Não se aplica a travesia de um avião de um continente a outro, pois a
distância será muito maior por considerar a curvatura da terra.
 Cont..
Aplicações

• Traçado de uma rota

• Encontrar o melhor caminho, p.e. ir de uma cidade para outra

Definição do Apetitoso

• É estabelecida a priori, antes da execução do algoritmo

• O objecto escolhido passa a fazer parte da solução que o
algoritmo constrói.
• Toma decisões com base nas informações disponíveis na
iteracção corrente, sem olhar as consequências que essas
decisões terão no futuro
• Jamais se arepende ou volta atrás, as escolhas que faz em cada
interação são definitivas
 Cont..
Procedimento

• Sempre escolhe a alternativa mais promissora naquela instante

• Nunca reconsidera essa decisão
• Uma escolha que foi feita nunca é revista
• Nunca há backtracking
• A escolha é feita de acordo com um criterio gulosa- decisão local óptima
• Nem sempre dão soluções óptima

Problema do Troco (troco mínimo)

• Moedas=(100,50,25,5,1)
• Troco: 75
• Quantidade mímina de moedas: 2 (1 de 50 + 1 de 25)
• 50 -> 75 < 50 – 1 de 50
• 75-50=25
• 50 -> 25 < 50
• 50-25= 25
• 25-> 25 <= 25 – 1 de 25
• 25-25=0
 Métodos Gulosa/Busca Heurística
Funcionamento Distância em linha recta
• Permite traçar uma rota, o algoritmo deve
encontrar o melhor caminho para se chegar
a um destino
• Heurística é uma determinada informação
que possui sobre o problema
• GPS já armazena uma tabela de Heurísticas
• Unit
 Guloso
Arad
118
374 75 329
140
253 Timisoara
Zerind
Sibiu

178
380 193
Fagaras
Aradea Rinnicu

0
Bucareste
 Factores a Considerar Gulosa
Devem ser adicionadas as Heurísticas o custo associado
a:

• Trechos com postagem

• Centros de cidade
• Perigo do trecho (Assaltos)
• Pontos turisticos

A adição dos factores as heurísticas podem aumentar o

custo
 Busca Competitiva
Todos os tipos de busca vistos até aqui envolvem apenas um
agente. Uma função objectivo que nunca muda

• Alguns problemas são multiagentes

• Sequência de decisões de agentes que controlamos e
outras decisões de agentes que não controlamos
• Traca de objetivos
• Objectivos conflitates
• Considera que há oponentes hostis e imprevisíveis ex.
jogos
 Métodos Minimax
0 0 x
Max
X: Ganha: +1 x 0
0: Ganha: -1
Empate: 0 x
0
0 +1

0 0 x
0 0 x 0 0 x Min
x 0
x x 0 x 0
x x
x x x
+1 +1 0 +1
0 +1 Max
0 0 x 0 0 x 0 0 x 0 0 x 0 0 x 0 0 x
x x 0 x x 0 x 0 0 x 0 x 0 0 x 0
0 x 0 x x x 0 x x x x x 0 x
0 +1 +1 0 +1
+1
0 0 x 0 0 x 0 0 x 0 0 x 0 0 x
0 0 x
x x 0 x x 0 x 0 0 x x 0 x 0 0
x x 0
0 x x x 0 x x x x 0 x x x x x
x 0 x
0 (Max)
Exemplo Jogo da Velha
-7

-10
1 (Min) -7

10
2 (Max) -10 5 -7

3 (Min) 10 5 -10 5 - -7

4 (Max)
10 + 5 -10 7 5 - -7 -5
 Exercício
Execute o Minimax dado o seguinte espaço de estado inicial

0 0 X

X 0

X
Representação de Conhecimento
RC
• O papel em IA é o de reduzir problemas de acção
inteligente a problemas de busca
Definições
• Conjunto de frase em uma linguagem formal para a
qual foram definidas uma semântica e um conjunto de
regras de inferência capazes de gerar novas frase a
partir das sentenças disponíveis;
• Conjunto de convenções sobre como descrever uma
classe de objectos “ Uma descrição faz uso das
convenções de uma representação para descrever um
objeto em particular.” Todas as representações
possibilitar representar: objectos, atributos e seus
relacionamentos
Conhecimento Certo

• Positivo: indivíduos que ressonam tem apneia obstrutiva

do sono
• Negativo: indivíduos que não ressoam não tem apneia
obstrutiva do sono
• Desconhecido: indivíduos que ressonam podem ter ou
não apneia obstrutiva de sono

Representações

• Relações e características de um problema através do uso

de expressões da lógica simbólica (Declarativa) ( Nagao,
90)
• Frames – ferramentas e métodos que descrevem o
cérebro humano - procedimental (Minsky, 90)
• Lógica Matemática (Israel 83)
Conhecimento incerto

• positivo: indivíduos que ressonam têm

70% de probabilidade de ter apneia
obstrutiva do sono
• negativo: indivíduos que não ressonam
tem 70% de probabilidade de não ter
apneia obstrutiva do sono (OSA)"
• desconhecido: individuos portugueses
têm 3% de probabilidade de ter apneia
obstrutiva do sono (prevalência)
Conhecimentos e Dados
• Conhecimento: representação simbólica
de aspectos de algum universo de
discurso"

Exemplo de conhecimento

• Todos alunos da UCAN sabem que

devem ter um bom aproveitamento
• Todos funcionários da UCAN tem
salários maiores de 100.000 KZ
• José não acha que tem um bom estilo de
vida
Conhecimentos e Dados
• Dados: representação simbólica de
aspectos simples de algum universo de
discurso"

Exemplo de dados

• José é casado com Maria

• José é funcionário da UCAN
Representação de
Conhecimento
• Expressar conhecimento de forma
tratável pelo computador
Formalismos de Representação de
Conhecimento
• Linguagem Natural
• Base de Dados
• Frames
• Scripts
• Redes Semánticas
• Algoritmos Genéticos
• Restrições
• Regras de Produção
• Árvores de Decisão
• Lógica (Linguagem de Representação Nativa de
Prolog)
• Ontologias
• Redes Casuais
• Redes Neurais
• Orientação a Objectos e etc.
Representação em Linguagem Natural- texto Clínico

• Enviada por densidade assimétrica no QSE da mama

esquerda. Esta alteração existe desde 2005 mas a
avaliação ecográfica do exterior sugere a necessidade de
biópsia. Exame mamário com alteração palpável com
cerca de 30 mm no QSE da mama esquerda.

Devantagens

• Ambígua, redundante, sintaxes e semántica não são claras

o suficiente

Tecnicamente, representações computacionalmente tratáveis podem ser

equivalentes, só que algumas representações são mais convenientes.
Base de Dados - pessoa
• pessoa
• registo = { nome : máximo 20 caracteres
• idade : 3 digitos no intervalo entre
000-120
• sexo : masculino ou femenino
• estado civil : casado, solteiro,
divorciado, viúvo, noivo
• primeiros nomes dos filhos : até 10
nomes cada com máximo até 15
caracters
• }
•.
 Instância
Masculino 025 João Jorge
Idade Nome
João Jorge Sexo
Primeiros nomes do filho
025 P
Estado civil Nando
Masculino
Casado Casado Fineza
Júnior
Ana
Nando
Teresa

- Apenas Aspectos simples podem ser representados (dados)

- Entidades e Relações
Representação em tabela

Paciente Localização Tamanho Data Classificação

P1 C 0.1 20050403 F,A
P2 C 0.2 20060412 F
P3 9 0.3 20060412 A
P4 19 0.4 20050415 M
…. …. ….
 Redes Semânticas - Conjunto de Nós
conectados por arcos

• São grafos rotulados em que os nós representam

conceitos, os arcos as relações semânticas entre os
objectos
• Por exemplo, considere algumas coisas que sabemos
sobre animais
• Animais comem
• Mamíferos e pássaros são animais
• Mamíferos têm pêlos
• Cães são mamíferos
 Pessoa
Exemplo

Instância -de
Tem_idade
Roda
28 Maria Motor

Parte_de Parte_de
Estacionado
tem-_dono
Av.5
Automóvel Carroceria
Carro1 Parte_de
tem-_KM Instância -de

tem-_Cor é-_um veículo

Zero

Branco Veículo
Exemplo

Mão
Pessoa Direita
ISA
Masculino Altura
Adulto 1.78

ISA

Jogador Altura 1.95

Basketebool
Média de
ISA arremessos .252
ISA

Armador Ala
Quilan 1966
• o significado poderia ser representado como
relacionamento entre dois objectos.
• Representações mais complicadas tais como
frames são realces desta idéia
Características
• Indexam as declarações pelas entidades que
descrevem;
• Facilitam a descrição de propriedades de
relações;
• Originaram os conceitos da programação
orientada a objectos;
• Facilitam a visualização directa dos conceitos e
dos relacionamentos entre eles.
 Aplicações
• Modelagem de conhecimento;
• Mapas Conceituais;
• Processamento da linguagem natural,
• Raciocínio por abstração;
• Programação orientada a objectos.

Propriedades
• Permite estruturar o conhecimento para refletir a parte do
universo que está a ser representada
• Valores default
• Sintaxe clara, já a semântica precisa ser trabalhada
 Exemplo RS simples

está Animal está comer

Animal Comer

Relações
❑ Ako (a-kind-of): relações entre classes
❑ é-um (is-a): relações entre classes e instâncias – uma entidade pertence a uma classe mais
alta ou uma categoria de objetos.
❑ tem-um (has-a): identifica características ou atributos das entidades
❑ parte-de (part-of): identifica características ou atributos das entidades
❑ variados: identifica características gerais
 Exemplo 2

Mobilia

Ako
Pessoa Couro
Cadeira É-um

É-um Estofamento
É-um
Dono
Cadeira
Ana Assento
_X
Tem-um
Cor

Preta
 Exemplo Planta

Planta É-um Ser É-um

Planta Edifício
Vivo
Te
m
Te É-uma
m Raizes

Folhas Fábrica
 Exemplo Planta

Or

Planta É-um Ser Planta É-um

1 Vivo 2 Edifício
Te
m
É-uma
Te
m Raizes
Fabricam
Fábrica

Folhas Bens
Lugar
 Exemplo
Função Bomba
Metabólico
Pode Ser
É –Regulado pela

Potencial
Potencial de
de Acção
Membrana
Pode Ser É -Um
É -Um
Potencial Potencial
Processo
de Acção de Acção Sinal de
Electro
Informação
Químico

Apresenta
Processo Processo
Electro Electro
Químico Químico
Exemplo RS simples

faz
Animal Comer

Ako Ako Animal faz comer

Passáro
Mamífero
tem
Ako

Cão Pêlos
 Transitividade

• Redes Semânticas são naturalmente transitivas

• Podemos concluir da rede desenvolvida que se “Cão é um
Mamífero” e “Mamífero é um Animal” então “Cão é um
Animal”
• Entretanto, não é possível concluir que: “Cão é um
Pássaro” “Pássaro tem pelos”
 Busca em Redes Semânticas
Extração de Informações

• Busca pode ser feita de várias maneiras

• como uma ferramenta explicativa
• para explorar um tópico exaustivamente
• para encontrar o relacionamento entre dois objecto

Ferramenta Exploratória

• Podemos supor que cães comem, e usar busca sobre a

rede para explicar isto (se ele pode)
• Buscando à partir do nó “Cão” , podemos dizer que “Cão
é um Mamífero”, “Mamífero é um
• Animal” e “Animal está a Comer”. É uma explicação
para “cães comem”
Busca em Largura
•Ajuda a encontrar tudo sobre
cães,
•Ex. que são mamíferos”, “tem
pelos”, “são animais” e “ comem
Intersecção de Busca

• Se quisermos encontrar se “Cães” e “Pássaros” estão

relacionados, então podemos executar, à partir de
ambos os nós, uma busca em largura (busca
bidirecional)
• A intersecção nos dá uma pista sobre o
relacionamento entre os nós
• sto é chamado ativação distribuída ou intersecção
de busca
• Partindo de “Cão” e “Pássaro” podemos
encontrar que ambos são animais:
Intersecção de Busca

• Tem que diferenciar conceitos de instâncias,

senão fica
impossível relacionar deferentes instâncias de
um mesmo conceito
• Exemplo Meu carro é preto
• possuidor cor
• Eu Carro Preto
 Intersecção de Busca

• Exemplo Acrescentar o carro da Maria é Azul

• possuidor cor
• Eu Carro Preto

Maria Azul

Animal está Comer

Ako

Passáro
Mamífero
Ako tem

Cão Pêlos
 Detectar Instanciais - Instance-of
Maria

Instace-of cor
Carro C2 Azul
azul
Instace-of
C1 Preto
cor
possuidor
Eu C1 e C2 são instâncias particulares,
Carro é um conceito
Exemplo
João

Instace-of É-um
Carro
Carro1 Veículo

cor
Preto Roda Meios_Trasp

O sentido de Instance Of, está invertido

mais é permitido
 Transitividade

Exemplo
Móvel
É-um É-parte
Pessoa Cadeira Assento
É-um Dono É-um
Cor
Ana Cadeira-X Preta
Estofado Meios_Trasp

Preto Couro

Conceito= Cadeira
Herança= É- parte e É-um
Transitividade Cadeira-X- Móvel
Exemplo

Dar

Agente É-um
João Deu Livro-X
Objecto
É-um

Preto Maria Livro

Instância particulares = deu e livro-x,

Conceito= livro, dar
Exercícios- Constroi uma RS

• Planta é usada em qualquer processo

industrial. Também pode significar o acto
de colocar uma semente ou planta na terra
para crescer. O mais comum é que é uma
estrutura viva que não é um animal,
frequentemente com folhas, retira seu
alimento do ar, da água e da terra.
Vantagens

• Representação Natural
• Oferece uma visão global do problema representado

Desvantagem

• O número de nós pode crescer muito para representar ideias simples

• Dificíl representar objectos que não são factos, mais ideias, crenças, tempo
• Representação não estruturada
• Tem sintaxe (nos, arcos e regras de combinação), a semántica não é clara o
suficiente o problema é a falta de distinção entre o intencional(sentido ou
significado) e o extensional(referência ou denotação). P.e. vermelho : todas as
coisas vermelhas (extensional) a propriedade de ser vermelho (intensional)
Representação em Lógica
• É_UM(Potencial_de_Membrana,Processo_EletroQuímico)
• É_UM(Potencial_de_Ação,Sinal_de_Informação)
• É_REGULADO_PELA(Potencial_de_Membrana,Bomba_Metabólica)
Exemplo tanque de água

• isa(tanque, componente)
• parede(tanque, blocos_de_concreto)
• parede(tanque, blocos_de_concreto)<- isa(X, tanque)
• Conteúdo (X, água) <- isa(X, tanque)
• isa(X, tanque) ← isa(X, tanque-domo)
Frame
• Colecções de questões a serem respondidas sobre uma
situação hipotética
• Estruturas de dados estáticas usado para representar
situações estereotipadas bem compreendidas (Minsky,
1975)
• Representa objectos do domínio.
• Uma estructura de dados para colocar o conhecimento
relevante da classe de objectos em vez de distribuir o
conhecimento em forma de regras de fórmulas lógicas.

Mamífero

É um Objectos do Domínio
Animal

tem Pêlos
 Exemplo de RS como Frame
Exemplo 1
Animal

Está Comer

Mamífero
Passáro É-um
É-um
Tem Pêlos

Cão
É-um
 Exemplo de RS como Frame
Exemplo 1
Animal

Está Comer

Mamífero
Passáro É-um
É-um
Tem Pêlos

Cão
É-um
 Expansão- Frames

Frame Cão
• O frame “Cão” poderia ser expandido acrescentando-se novos slots e
valores para o frame

Cão
É um Mamífero
Slotes
Nome Valores

Raça Default: Mogrel

Pêlos
Default: Longo
Sexo
Fêmea ou Macho
Aspectos Particulares
• Slots são atributos do frame que podem ter
valores particulares
• Valores podem ser um valor absoluto, um
intervalo ou um valor default
• Um frame genérico, tal como o frame “Cão”, é
uma classe frame
• Uma instância de uma classe frame é
simplesmente um frame com valores
específicos, assim como Rex, o cão, é uma
instância da classe de cães
 Cont..
Instâncias do Frame Cão - Rex

Cão
É um Mamífero

Nome Rex

Raça Pastor Alemão

Raça
Longo
Sexo
Macho
Demons

• Procedimentos que estão dentro de frames são chamados

demons
• Um exemplo de um demon é um procedimento para
calcular a área de um quadrado dado o tamanho de um
dos lados (via valores de slots)
• Assim o valor da área não precisa estar representado e
sim pode ser calculado a partir de outras informações na
instanciação do frame
Quadrado
Quadrado
Tamanho 5
Tamanho
Lado
Lado
Área Área 25
Herança
• No exemplo animal/mamífero/cão, o nível
mais baixo herda as propriedades dos
níveis superiores. Por exemplo: Cão tem
pêlos, pois eles são mamíferos e
mamíferos têm pêlos;
• Herança é uma característica poderosa de
frames, porque informações podem ser
especificadas num nível mais genérico,
evitando-se, assim, redundância
 Frames e Objectos

• Objectos na Programação Orientada a Objectos são

muito similares aos frames. Por essa razão, Liguagens
OO são uma boa opção para a implementação de
sistemas de frame
Rede de Cómodos de uma sala
aKo aKo
Comodo Sala_de_estar Sala_de_estar
*Tipo Maria
aKo
Sala_de_estar aKo aKo
Quarto Quarto
Suite
Cozinha aKo Suite Maria
Banheiro
Cozinha aKo
*…….
aKo
Hospede
Instância
Classe Banheiro
SubClasse
SubClasse
 Script
História
• Scripts (Schank e Abelson 1977) são uma especialização
de frames projectados para manipular situações além
de objectos
• Numa rede semântica ou em frames, nós são objectos,
e os links entre objetos representam uma gama de
relacionamentos
• Em scripts, os nós são eventos, e os links entre eles são
simplesmente causais isto é, um evento provoca o
próximo
• Um script é como um script cinematográfico
precisamos considerar vários elementos quando o
projectamos
Aplicações
• Contar histórias sobre uma seqüência de eventos
• Responder questões tais como “O que acontece
se o bife do freguês estiver queimado?”
• Seqüência dos eventos levem a alguma decisão
• Inferências em determinadas situações
• Scripts são muito similares a frames, são
codificados da mesma forma e são, às vezes,
considerados como uma sub-classe de frames
Scripts- Análise

• Quais são os papéis dos objectos/pessoas no script

• Quais objectos de cena se relacionam ao script
• Quais são as motivações ou entradas condicionais para
execução do script
• Quais cenas estão para ocorrer
• Em qual ordem elas devem ocorrer
Script Básico

• Antes de projetarmos o script, necessitamos de uma

sequência básica inicial
• Por exemplo, na ida a um restaurante há uma sequência
de eventos que podemos esperar:
Pagar pela
Refeição
Entrar no Pedir Comer :::
Restaurante refeição refeição

Gorjeta
Quebra

• É possível quebrar cada um dos eventos numa

série de sub-eventos. Por exemplo, com relação
ao evento entrar no restaurante, podese esperar:

Esperar por
Estacionar o Entrar no uma mesa
carro :::
Restaurante Ler o menu

Ir até a
Mesa
Restaurante
• Colocando os eventos juntos aos demais
elementos, poderíamos imaginar o script
“Restaurante” assinalando apenas algumas
coisas, tais como:
• Papéis: Freguês, garçom, cozinha...
• Objectos de cena: Mesas, cadeiras, garfos,
facas, pratos, copos, garrafas de vinho...
• Entradas condicionais: freguês está faminto;
freguês está vestido inapropriadamente; freguês
tem dinheiro..
 Exemplo de Script
Restaurante
• Cena1: Entrar
• Estacionar o carro
• Entrar no restaurante
• Esperar por uma mesa
• Ou
• Ir até a mesa
• Ler o menu
• Cena 2- Pedir refeição
• ..

• Resultado: fregues não tem fome, fregues tem menos

dinheiro
Script Ir ao Cinema

• Papéis. Objecto, Condições de entrada,

cenas, Resultados
Paradigma
• Procedimentos – Programação Imperativa
• Lógica- Provador de Teoremas
• Regras- Shells de Sistemas Especialistas
• Classes_Objectos- Redes Semánticas
• Classes_Objectos_Procedimentos-Programação
OO/Frames
• Classes_Objectos_Lógica- Lógicas Descritivas
• Regras_Procedimentos- Sistema de Produção
• Regras_Classes/Objectos_Procedimentos- Sistema de
Produção OO
• Regras_Lógica- Programação em Lógica
• Regras_Classes/Objectos_Lógica- Programação em Lógica
OO
Questão

• É possível transformar a representação de

conhecimento de Redes Semántica,
Frames e Script em Prolog?
• Como faze-lo ?
Representação em Lógica
• Linguagem com sintaxe e semântica precisas:
lógica.
• Mecanismo de inferencia: derivado da sintaxe
e da semântica.
• Importante: distinguir entre os fatos e sua
representação
• Não podemos colocar todos os fatos do
mundo no computador!
• Neste caso, devemos operar em
representações dos factos (codificação em
alguma linguagem)
• Raciocínio: processo de construir novas
configurações a partir de configurações já
existentes
Representação em Lógica

• Mecanismo de inferência:
• dada uma base de conhecimento KB, pode
gerar novas sentença que seguem de KB.
• dada uma base de conhecimento e uma
sentença , pode dizer se consequência logica
de KB.
Introdução a Prolog

• Linguagem de programação
utilizada para resolver problemas
envolvendo objectos e relações entre
objetos
Prolog vs. procedural
Procedural
• Programa=Algoritmo+ Estruturas de
Dados
Prolog
• Algoritmo= Lógica +Controlo
• Programa=Lógica+Controle+
Estruturas de Dados
• Em prolog programa-se de forma
declarativa ( especifica-se o que ?) e
não o como deve ser computado
Programar em Prolog

• Declarar alguns factos em relação aos

objectos e os seus relacionamentos
• Definir algumas regras sobre os
objectos e os seus relacionamentos
• Fazer perguntas sobre os objectos e
os seus relacionamentos
 Apredizado de Máquina
• campo de estudo que dá aos
Samuel computadores a habilidade de
aprender sem terem sido
(1959) programados para tal

Modelos • Não informamos ao computador os

passos a seguir para que ele aprenda
AM o que precisa, isso porque o
conhecimento é adquirido

• Modelos Estatístico ou matemáticos

reconhecem padrões em dados, criam
Funcionamento a possibilidade de aprenderem com
seus erros e fazem previsões em cima
do que foi aprendido.
 Tipos de Aprendizagem
• Subconjunto de IA
As Máquinas Aprendem • Reconhecem padrões nos dados para
sem serem programados aprenderem
para a tarefa • Une uma grande quantidade de dados e
algoritmos para reconhecer padrões
• Adquire informações de relacionamentos
Supervisionado entre entradas e saídas de um sistema, utiliza
conjunto de amostras de treinamento

• consiste em treinar uma máquina a

Não Supervisionado partir de dados que não estão
rotulados e/ou classificados.

• Poucos dados e trabalha-se pelo

Por Reforço método de tentativas e erros (robots e
jogos)
 Apredizado de Máquina
• Subconjunto de IA
As Máquinas • Reconhecem padrões nos dados para aprenderem
Apredem • Une uma grande quantidade de dados e algoritmos
para reconhecer padrões

• São os modelos de AM
Algoritmos
• Etapa em que os algoritmos aprendem com
os dados
Treinamento • Identifica-se nessa etapa os padrões nos
dos Modelos dados, depois pode-se fazer predições em
dados desconhecidos

• Construir um modelo capaz de fazer tomografia de

um pulmão e dizer se possui ou não um tumor.
Exemplo Para o efeito precisaremos de um número grande
de imagens com e sem tumor
Apredizado de Máquina
A máquina aprende por sí

Dados Saída

Programação
Modelo Tradicional

Dados Modelo

Apredizado de
Saídas Máquina
 Programação Tradicional
Dados Saída

Programação
Modelo Tradicional
Cálculo de Imposto de Renda:
Modelo
- Classe em função do salário
Dados de entrada
- NIF
- Salário
Saída
- Imposto
 Apredizado de Máquina
A máquina aprende por sí

Dados Modelo

Apredizado de
Saídas Máquina
Lógica Invertida – O algoritmo aprende a partir dos dados e
de saídas esperadas
- Sistema anti fraude
- Não é perciso programar todas as regras de anti-
fraude
- Basta pegar os dados de saída e gerará um modelo
que classifica o que é fraude e o que não é
Obs: Aprende as regras e a saída será o modelo
Apredizado Supervisionado
Analisa os dados de treino e produz uma função inferida que
será utilizada para analisar novos exemplos

Sistema • Marcar ( fraude, não fraude)

Antifraude

Imagens • Etiquetas (vermelho, verde,

de Frutas amarelo) – Uva. Maça, Laranja
 Exemplo
Caixa de Mensagens Inbox

Span

Classificador

Span Directoria de Span

Span

Span

Span
 Classificação
Processo
• De categorizar um determinado conjunto de dados em
classes.
• No exemplo da classificação de e-mails como spam,
teríamos um exemplo de classificação binária, no qual o
modelo através dos dados fornecidos, precisaria gerar
como resposta se o e-mail é spam ou não.

Algoritmos
• KNN
• Naive Bayes
• Logistic Regression
• Support Vector Machines
• Decision Trees
 Regressão
Modelos

• Utilizados quando queremos prever valores,

• por exemplo, prever o preço de uma casa ou o número de
produtos que serão vendidos em determinado mês.

Modelo de Regressão
Uma variável dependente Modelo de
Regressão Duas ou mais variáveis
• dependentes
Simples
Múltiplos

Linear Não Linear

Linear Não Linear
 Regressão
Algoritmos

• Linear Regression
• Polynomial Regression
• Logistic Regression
• Principal Components Regression (PCR)
 Classificador de Maça

Reconhecimento de Maça
Fala

Reconhecimento de Maça
Imagem

PLN Maça

Obs: Não se pode utilizar modelos de reconhecimento de fala para

imagem ou PLN. Se o reconhecimento de fala for para Inglês não
servirá para português
 Apredizado não Supervisionado
Buscam descobrir padrões ocultos que agrupam as
informações de acordo com semelhanças ou diferenças

O algoritmo será responsável por descobrir semelhanças, padrões

ou diferenças que permitam diferenciar cães e gatos
 Algoritmos

Algoritmos

AM não
Supervisionado

Clustering Regras de Redução da

Associação Dimensionalidade
Agrupamento
Algoritmos
• Agrupa dados não rotulados com base em suas
semelhanças ou diferenças.
• podem ser subdivididos em agrupamentos exclusivos,
sobrepostos, hierárquicos e probabilístico
Regras de Associação
• Busca descobrir relações que descrevem grandes porções
dos dados.
• A associação é muito utilizada em análises de cestas de
compras, no qual a empresa pode tentar entender relações
de preferências de compras entre os produtos Exemplos (
Apriori, Eclat e FP-Growth).
Redução de Dimensionalidade
• Quando envolve grande número de recursos. Ajudam a
eliminar overfitting de forma a preservar a integridade dos
dados
Apredizado por Reforço
Bom comportamento recebe reforço, mal comportamento
castigo
 Aplicações
Diagnóstico Médico
• Reconhecimento de doenças (modelos 3D para prever a
posição exacta de lesões cérebro tumor)
• Reconhecimento de padrões para identificar cancro de
pulmão , pele, etc.

Detecção de Fraude Online

• Detectar anomalias nas transacções.
• Baseado no histórico mensal das suas transacções em caso
de um valor maior . O sistema envia uma notificação para o
banco e a operação coloca a transacção em espera
Sistema de Recomendações
• Histórico com base nas compras anteriores
Reconhecimento de Fala
• Assistentes de voz
Métodos de Apredizado por Reforço

• Marcar ( fraude, não fraude)

• Etiquetas (vermelho, verde,

amarelo) – Uva. Maça, Laranja
 REGRESSÃO

▸ Prever o aumento da receita por tipo de anúncio

 CLASSIFICAÇÃO

Separable Unseparable

▸ Given data set of i.i.d. observations of object-labels pairs, estimate f(object)

↦ label
 CLASSIFICADOR NIVE BAYES
▸ For Boolean variables, specifies separating hyperplane on input
space

▸ No longer true with multi-valued variables

NEAREST NEIGHBOR REGRESSION
k=1 k=9
CLASSIFICADOR NEAREST NEIGHBOR
NEAREST NEIGHBOR CLASSIFIER
SETTING THE NUMBER OF NEIGHBORS

underfitted overfitted
 Mineração de Dados

Fundamentos

Ferramentas Weeka
 Mineração de Dados
Fundamentos
• Data Mining é uma tecnologia que emergiu da
intersecção de três áreas: estatística clássica,
inteligência artificial e aprendizado de máquina.
• É o processo de descobrir informações relevantes,
como padrões, associações, mudanças, anomalias e
estruturas, em grandes quantidades de dados
armazenados em baSE de dados, depósitos de dados
ou outros repositórios de informação.
• Análise inteligente visando manipulação automática
de quantidades imensas de dados
• Larga aplicação nos mais variados ramos da indústria,
comércio, medicina, governo, administração, etc.
• Integra várias técnicas e tecnologias
 Mineração de Dados
Fundamentos
• A maioria dos exemplos conhecidos de aplicações de
aprendizado de máquina são sistemas que realizam a
tarefa de classificação.
• Classificação consiste em determinar a que classe um
objeCto pertence dados os valores de um conjunto de
atributos do objecto
Exemplos
• Por exemplo, filtragem de spam: dado o conteúdo de
uma mensagem de email (conjunto de palavras) decidir
se esta mensagem é ou não é spam. Outros exemplos
são detectar se uma operação com cartão de crédito é
fraudulenta ou não, e detectar se um conjunto de pixels
é um rosto ou não
• Treinar um classificador é faze-lo aprender a função de
classificação, a partir de um conjunto de dados cuja
classe de cada objeto é conhecida.
 Mineração de Dados
Exemplos
• Banco central dos EUA
• Selecçionou entre seus clientes, aqueles com
menor risco de dar calotes
• Em três anos o banco lucrou 30 milhões de dólares
com a carteira de empréstimos
• Fraldas e cervejas
• Homens casados, entre 25 e 30 anos compravam
fraldas e/ou cervejas às sextas-feiras à tarde
• Wal-Mart
• Optimizou as gôndolas e o consumo cresceu 30%
Problema de Classificação
Definição Informal
• Dada uma colecção de Dados detalhados neste caso
5 exemplos de esperança e 5 de gafanhotos. Decida
a qual tipo de insecto o exemplo não rotulado
pertence
Problema de Classificação
Definição Informal
• Para qualquer domínio de interesse podemos medir
características
• Cor{verde, cinza, verde, etc..}
• Compimento{do abdomem, torax, antenas, pernas}
• Tamanho da mandíbula
• Diâmetro dos orifícios ed respiração

Podemos armazenar as caracteristicas numa BD

• O problema de classificação pode ser
expresso agora da seguinte forma
• Dada uma base de treinamento (Minha
Colecção) prediga o rótulo da classes dos
exemplos ainda não vistos
Problema de Classificação
ID-Insecto Comp_Abdomem Comp_antenas Classe de
Insecto
1 2.7 5.5 Gafanhoto
2 8.0 9.1 Esperança
3 0.9 4.7 Gafanhoto
4 1.1 3.1 Gafanhoto Exemplo
5 5.4 8.5 Esperança não visto

6 2.9 1.9 Gafanhoto

7 6.1 6.6 Esperança
8 0.5 1.0 Gafanhoto
9 8.3 6.6 Esperança
10 8.1 4.7 Esperança
11 5.1 7.0 ?????
 Problema de Classificação
10 Azul= esperança
9 Verde= Gafanhoto
Comprimento das antenas

8
7
6
5

4
3
2
1
1 2 3 4 5 6 7 8 9 10

Comprimento do Abdômem
 Problema de Classificação
Cada um desses objectos
10
de dados é chamado de
9 exemplar …
Comprimento das antenas

8 - Exemplo (de
treinamento)
7
- Instância
6 - Tupla

4
3
2
1
1 2 3 4 5 6 7 8 9 10
Comprimento do Abdômem
Problema de Pombo

8 1.5
De que classe é o objecto ?

4.5 7

De que classe é o objecto ?

Problema de Pombo
Regra

• Se a barra esquerda é menor

do que a da direita, é da
classe A, Senão classe B
Classificador Linear Simples

Espaços Dimensionais
maiores
Classificador Linear Simples
3D

Acurâcia
imperfeita

Classificador
Quadrático
Classificador Linear Simples
Classificador Vizinhos mais Próximos
K- Nearest Neighbor

Se o exemplo mais próximo de

um exemplo não visto antes é
uma esperança a classe é
esperança. Senão a classe é
gafanhoto
 Referências Bibliográficas
1. 1-Russell, S., Norvig P.; -Artificial Intelligence: A Modern Approach, 3rd Edition,
Prentice Hall, 20102
2. -Palazzo L.; -Introdução à Programação Prolog, Pelotas-Brasil, UCPEL, 1997
3. Luger, G. Artificial Intelligence: Structures and Strategies for Complex ProblemSolving,
Addison-Wesley Pub Co, 20084-
4. Casanova M., Giorno F., Furtado A.;-Programação em lógica e a linguagem Prolog,
PUC-RIO, 2006.
5. Bishop, C. M.;-Pattern Recognition and Machine Learning,Springer, 2006.6-
6. Bittencourt, G.;-Inteligência artificial: ferramentas e teorias,3ª Edição,
Florianópolis,Editora daUFSC, 2006.

[Link] Meet
 Frequência
Data 3/11

Conteúdo a Avaliar

❑ Agentes Inteligentes
❑ Algoritmos de Busca ( BFS,DFS, A* e Busca Gulosa)
❑ Redes Semânticas

[Link] Meet