inteligencia artificial - semana 2
DESCRIPTION
www.inteligenciaartificial.comoj.comTRANSCRIPT
UNIVERSIDAD NACIONAL MAYOR DE SAN MARCOS(DECANA DE AMERICA)
FACULTAD DE INGENIERIA DE SISTEMAS E INFORMATICA
INTELIGENCIA ARTIFICIAL
REPRESENTACION DEL CONOCIMIENTO
Clasificación de problemas
META CONOCIMIENTO
CONOCIMIENTO
INFORMACIÓN
RUIDO
DATOS
JERARQUÍA DEL CONOCIMIENTO
Ruido:Esta conformado por todos los elementos asociado a un evento, que son de poco interés y que ocultan datos
Datos:Esta conformado por los elementos de interés potencial asociado a un evento y por lo cual se registra.
Información:Datos procesados de interés.
Conocimiento: Información muy especializada.
Meta conocimiento:Es el conocimiento acerca del conocimiento y la experiencia
JERARQUÍA DEL CONOCIMIENTO
Definición
Son métodos usados para "modelar" en forma eficiente los conocimientos de especialistas en alguna área del saber, de forma que pueda ser usado por el usuario de un sistema inteligente.
El conocimiento puede ser considerado como una entidad simbólica -> Procesamiento simbólico
REPRESENTACIÓN DEL CONOCIMIENTO
Formas de Representación
• Red Semántica o Grafo• Registro • Predicado• Relación objeto-atributo-valor• Esquemas• Marcos• Lógica de predicado• Otros
REPRESENTACIÓN DEL CONOCIMIENTO
Red Semántica
Los nodos representan objetos y los arcos la relación entre los objetos
REPRESENTACIÓN DEL CONOCIMIENTO
Red Semántica
Ejemplo- Juan es hijo de Raúl y Susy- Juan estudia informática
SusyJuan
Informática
RaúlEs hijo
Es hijo
Estudia
REPRESENTACIÓN DEL CONOCIMIENTO
Registro
Los objetos y relaciones se representan mediante una colección de datos simples llamados campos o átomos. Un campo o
átomo puede ser una colección de campos.
REPRESENTACIÓN DEL CONOCIMIENTO
Registro
Ejemplo- Juan es hijo de Raúl y Susy- Juan estudia informática
(Juan (es hijo de Raúl) (es hijo de Susy)
(estudia Informática))
REPRESENTACIÓN DEL CONOCIMIENTO
Predicado
Cada relación se representa como un predicado o función de valores lógicos y con
argumentos los objetos:
Relación (objeto1, objeto2,...,)
Esta función asume valor verdadero o falso, según se verifique o
no para los objetos involucrados.
REPRESENTACIÓN DEL CONOCIMIENTO
Predicado
Ejemplo- Juan es hijo de Raúl y Susy- Juan estudia informática
Hijo (Juan, Susy, Raúl) Verdadero
Estudia (Juan, Informática) Verdadero
Hijo (Juan, Maria, Raúl) Falso
REPRESENTACIÓN DEL CONOCIMIENTO
CLASIFICACION DE PROBLEMAS ALGORTIMICOS
Por su Naturaleza Los problemas algorítmicos son clasificados de acuerdo a su naturaleza intrínseca respecto a la posibilidad y dificultad de resolverlos.
Por el tipo de RespuestaLos problemas son clasificados de acuerdo a la respuesta requerida por el problema.
Por su Tratabilidad Los problemas que admiten solución son
clasificados de acuerdo a la complejidad que presentan los algoritmos para resolverlos.
CLASIFICACIÓN POR SU NATURALEZA
Los problemas de naturaleza algorítmica que no admiten solución por algoritmo son llamados no - computables.
Los problemas de decisión y no-computables son llamados de indecidíbles.
Los problemas para los cuales existen algoritmos de complejidad polinomial para resolverlos son llamados de tratables.
Los problemas que admiten solución y para los cuales comprobadamente no pueden ser resueltos por algoritmos de complejidad polinomial son rotulados de intratables.
CLASIFICACIÓN POR SU NATURALEZA
No computableProblemas que no admitenSolución algorítmica Indecidíble
TratableProblemas que admitenSolución algorítmica Intratable
CLASIFICACIÓN POR EL TIPO DE RESPUESTALos Problemas por el tipo de respuesta
se clasifican en:
Problemas de Decisión Problemas de Localización Problemas de Optimización
CLASIFICACIÓN POR EL TIPO DE RESPUESTAProblemas de DecisiónObjetivo:
Responder SI o NO a una determinada indagación.
Problemas de LocalizaciónObjetivo:
Encontrar, caso exista, una estructura que verifique las restricciones del problema, dicha estructura es denominada de solución viable.
Problemas de Optimización Objetivo:
Encontrar una estructura que verifique las restricciones del problema y optimice un criterio pre-definido. Esto es, encontrar una solución viable que optimice un criterio pre-determinado
CLASIFICACIÓN POR SU TRATABILIDAD: P Y NP
La Clase P
Está constituida por todos los problemas comprobadamente tratables, esto es, problemas que pueden ser resueltos por algoritmos de complejidad polinomial.
CLASIFICACIÓN POR SU TRATABILIDAD: P Y NPAlgunos Problemas de la Clase P
Resolución de Sistemas de Ecuaciones Lineales
Contabilidad (registrar y/o modificar transacciones)
Ordenar números, buscar palabras en un texto
Juntar Archivos En general los sistemas operacionales
(facturación, control de almacenes, planillas, ventas, etc.) Cualquier problema de la Programación
Lineal Sistemas de transacciones bancarias En general los sistemas de información
gerencial
CLASIFICACIÓN POR SU TRATABILIDAD: P Y NP
La Clase NP
Está constituido por todos los problemas que pueden ser resueltos por algoritmos enumerativos, cuya búsqueda en el espacio de soluciones es realizada en un árbol con profundidad limitada por una función polinomial respecto al tamaño de la instancia del problema y con ancho eventualmente exponencial.
CLASIFICACIÓN POR SU TRATABILIDAD: P Y NPRelación P y NP
Ciertamente la clase NP incluye todos los problemas intratables. Además los problema de la clase P pueden ser resueltos también por algoritmos enumerativos. Por consiguiente se puede afirmar que:
NP - P
CLASIFICACIÓN POR SU TRATABILIDAD: P Y NPAlgunos Problemas de la Clase NP-difícil
Clique Cobertura de Vértices y Aristas Coloración de Grafos Mochila Lineal y Cuadrática Optimización de Desperdicios Agente Viajero Gestión Optima de cortes Programación de Tareas Aprendizaje
EJEMPLOS : TIPO DE RESPUESTAEjemplo: El Problema de los Misioneros y Caníbales
Considere tres misioneros, tres caníbales y una canoa de
capacidad máxima de dos pasajeros; todos ellos se encuentran en una de las orilla de un río. El problema
consiste en encontrar una secuencia de viajes quepermita trasladar a todos los misioneros y caníbales alotro lado de la orilla del río. Se debe respetar que en
cada orilla el número de misioneros (si lo hubiera) debe ser
siempre no menor al número de caníbales
EJEMPLOS : TIPO DE RESPUESTAAsociado al problema de los Misioneros y Caníbales,
tenemos los siguientes problemas:
Problema 1:Determinar una secuencia de viajes que permita trasladar a
todos los misioneros y caníbales a la otra orilla del río.
Problema 2:Existirá una secuencia de viajes que permita trasladar a
todos los misioneros y caníbales a la otra orilla del río.
Problema 3:Determinar la menor secuencia de viajes que permita
trasladar a todos los misioneros y caníbales a la otra orilla
del rio.