Upload
dokhanh
View
228
Download
1
Embed Size (px)
Citation preview
TRABAJO COLABORATIVO No 1
INTELIGENCIA ARTIFICIAL
FRANCO ALIRIO CALPA TARAPUES
JOSE GIRALDO ROSERO GUERRERO
JOSE FERNEY RODRIGUEZ
LUIS ALBERTO LOAIZA
EFRAIN SIERRA
GRUPO: 90169-17
TUTOR
ANGELA MARIA GONZÀLES
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA - CEAD PASTO
ESCUELA DE CIENCIAS BÁSICAS, TECNOLOGÍA E INGENIERÍA
INGENIERIA DE SISTEMAS
CUMBAL - NARIÑO
05 DE MARZO DE 2014
INTRODUCIÒN
La Inteligencia Artificial (IA). Es una combinación de la ciencia de los computadores, la
psicología y la filosofía. Cubriendo muchos campos de estudio como la visión por
computador, las redes neuronales y los sistemas expertos, con algo en común que es crear
maquinas que puedan pensar, tengan la habilidad de razonar, deducir, inferir, adivinar y si
es posible pedir perdón al equivocarse. Enfrentando las diferentes alarmas que puedan
surgir en su entorno.
En general la Inteligencia Artificial es la ciencia que investiga la posibilidad de que un
ordenador simule el proceso de razonamiento humano. Pretende también que el ordenador
sea capaz de modificar su programación en función de su experiencia y que "aprenda".
OBJETIVOS
GENERAL
Establecer los principios que rigen la inteligencia artificial sus aplicaciones y
evolución.
ESPECIFICOS
Reconocer las diferentes definiciones de inteligencia artificial y la evolución
histórica de la inteligencia artificial.
Descubrir y usar las técnicas de resolución de problemas con el ànimo de establecer
normas para este propósito.
Reconocer el uso de los agentes inteligentes y su aplicación.
Estudiar la complejidad de los problemas y representar su estructura y las posibles
soluciones.
ACTIVIDADES A DESARROLLAR
INTRODUCCIÓN INTELIGENCIA ARTIFICIAL
1. ÁREAS DE INVESTIGACIÓN
SISTEMAS EXPERTOS:
Son aplicaciones informáticas capaces de solucionar un conjunto de problemas que exigen
un gran conocimiento sobre un determinado tema. Estos sistemas imitan las actividades de
un ser humano para resolver problemas de distinta índole. De esta manera deben tener las
capacidades de explicar sus razonamientos y adquirir nuevos conocimientos.
Un sistema experto está conformado por:
- Especialistas Humanos
- Ingenieros en Conocimientos
- Base de conocimientos
- Base de hechos
- Motor de inferencia
- Módulos de justificación
- Interfaz de usuario
Tipos de sistemas expertos:
- Basados en reglas previamente establecidas.
- Basados en casos o CBR (Case Based Reasoning).
- Basados en redes bayesianas.
En cada uno de ellos, la solución a un problema planteado se obtiene:
- Aplicando reglas heurísticas apoyadas generalmente en lógica difusa para su
evaluación y aplicación.
- Aplicando el razonamiento basado en casos, donde la solución a un problema
similar planteado con anterioridad se adapta al nuevo problema.
- Aplicando redes bayesianas, basadas en estadística y el teorema de Bayes.
Ventajas de un sistema experto:
- Permanencia: A diferencia de un experto humano un SE (sistema experto) no
envejece, y por tanto no sufre pérdida de facultades con el paso del tiempo.
- Replicación: Una vez programado un SE lo podemos replicar infinidad de veces.
- Rapidez: Un SE puede obtener información de una base de datos y realizar cálculos
numéricos mucho más rápido que cualquier ser humano.
- Bajo costo: A pesar de que el costo inicial pueda ser elevado, gracias a la capacidad
de duplicación el coste finalmente es bajo.
- Entornos peligrosos: Un SE puede trabajar en entornos peligrosos o dañinos para el
ser humano.
- Fiabilidad: Los SE no se ven afectados por condiciones externas, un humano sí
(cansancio, presión, etc.).
Limitaciones de un sistema experto:
- Sentido común: Para un Sistema Experto no hay nada obvio.
- Lenguaje natural: Con un experto humano podemos mantener una conversación
informal mientras que con un SE no podemos.
- Capacidad de aprendizaje: Cualquier persona aprende con relativa facilidad de sus
errores y de errores ajenos, que un SE haga esto es muy complicado.
- Perspectiva global: Un experto humano es capaz de distinguir cuales son las
cuestiones relevantes de un problema y separar las de cuestiones secundarias.
- Capacidad sensorial: Un SE carece de sentidos.
- Flexibilidad: Un humano es sumamente flexible a la hora de aceptar datos para la
resolución de un problema.
- Conocimiento no estructurado: Un SE no es capaz de manejar conocimiento poco
estructurado.
Tareas que realiza un sistema experto:
- La monitorización es un caso particular de la interpretación, y consiste en la
comparación continua de los valores de las señales o datos de entrada y unos valores
que actúan como criterios de normalidad o estándares.
- Diseño es el proceso de especificar una descripción de un artefacto que satisface
varias características desde un número de fuentes de conocimiento.
- La planificación es la realización de planes o secuencias de acciones y es un caso
particular de la simulación. Está compuesto por un simulador y un sistema de
control. El efecto final es la ordenación de un conjunto de acciones con el fin de
conseguir un objetivo global.
- Un sistema de control participa en la realización de las tareas de interpretación,
diagnóstico y reparación de forma secuencial. Con ello se consigue conducir o guiar
un proceso o sistema.
- La simulación es una técnica que consistente en crear modelos basados en hechos,
observaciones e interpretaciones sobre la computadora, a fin de estudiar el
comportamiento de los mismos mediante la observación de las salidas para un
conjunto de entradas. Las técnicas tradicionales de simulación requieren modelos
matemáticos y lógicos, que describen el comportamiento del sistema bajo estudio.
- Un sistema de instrucción realizara un seguimiento del proceso de aprendizaje. El
sistema detecta errores ya sea de una persona con conocimientos e identifica el
remedio adecuado, es decir, desarrolla un plan de enseñanza que facilita el proceso
de aprendizaje y la corrección de errores.
- Los Sistemas Expertos, con su capacidad para combinar información y reglas de
actuación. Deben ser capaces de generar información no explícita, razonando con
los elementos que se le dan. Pueden utilizarse para ayudar al usuario, en selección
de recursos de información, en filtrado de respuestas, etc.
2. CRUSIGRAMA
1. Pensar: Formarse y relacionar ideas en la mente. Examinar algo en la mente antes de
tomar una decisión o darle una solución, concebir un plan, procedimiento o medio
para algo, tener alguien una opinión sobre algo o manifestarla. Pensar mal o bien
loc. Interpretar negativa o positivamente las acciones o las palabras de una persona,
desconfiando de ellas o no.
2. Sistemas expertos: Son programas computacionales diseñados para actuar como
expertos en un dominio particular restringido. Es importante debido a que trabaja
con conocimiento en lugar del tradicional dato.
3. VC: Visión por computador
4. IA: Inteligencia Artificial
5. Robótica: La robótica es la rama de la tecnología que se dedica al diseño,
construcción, operación, disposición estructural, manufactura y aplicación de los
robots.
6. Búsqueda: Proporciona una forma de resolver problemas en los que no se dispone
de un método directo.
7. Abstracción: Proporciona una forma de separar aspectos y variaciones importantes
de aquellos otros sin importancia y que en caso contrario podría colapsar el proceso.
8. Marvin Minsky: (n. en Nueva York el 9 de agosto de 1927- ) científico
estadounidense considerado uno de los padres de las ciencias de la computación y
cofundador del laboratorio de inteligencia artificial del Instituto Tecnológico de
Massachusetts o MIT. Minsky ha contribuido en el desarrollo de la descripción
gráfica simbólica, geometría computacional, representación del conocimiento,
semántica computacional, percepción mecánica, aprendizaje simbólico y
conexionista. En 1951 creó SNARC, el primer simulador de redes neuronales.
9. John McCarthy: (Boston, Massachusetts, 4 de septiembre de 1927 - Stanford,
California, 24 de octubre de 2011), Fue un prominente informático que recibió el
Premio Turing en 1971 por sus importantes contribuciones en el campo de la
Inteligencia Artificial. De hecho, fue el responsable de introducir el término
“inteligencia artificial”, concepto que acuñó en la Conferencia de Dartmouth en
1956. McCarthy inventó el lenguaje de programación Lisp y publicó su diseño en
Comunicaciones del ACM en 1960. En los años 90 luchó para que se introdujera
una enmienda a la Carta de Derechos de los Estados Unidos que protegiera
específicamente los datos y comunicaciones informáticas, así como el derecho de
los usuarios a poder leer, corregir y limitar el acceso a los propios archivos.
10. Claude Shannon: (Míchigan, 30 de abril de 1916 - 24 de febrero de 2001) fue un
ingeniero electrónico y matemático estadounidense, desarrolló la entropía de la
información. trabajó en el computador analógico más avanzado de esa era, el
Differential Analyzer de Vannevar Bush. En su tesis de maestría en el MIT,
demostró cómo el álgebra booleana se podía utilizar en el análisis y la síntesis de la
conmutación y de los circuitos digitales. , en su libro Las computadoras desde
Pascal hasta Von Neumann, citó su tesis como una de las más importantes de la
historia que ayudó a cambiar el diseño de circuitos digitales. En el área de las
computadoras y de la inteligencia artificial, publicó en 1950 un trabajo que
describía la programación de una computadora para jugar al ajedrez. En el campo de
la biblioteconomía y la documentación, el desarrollo booleano revolucionó las
búsquedas en catálogos de bibliotecas o en bases de datos de centros de
documentación.
11. Test de Turing: Metodo propuesto por Alan Turing, para determinar si una maquina
es capaz de pensar.
12. Ajedrez: El ajedrez es un juego entre dos personas, cada una de las cuales dispone
de 16 piezas móviles que se colocan sobre un tablero dividido en 64 partes. Está
considerado como un deporte. Originalmente inventado como un juego para
personas, a partir de la creación de computadoras y programas comerciales de
ajedrez una partida de ajedrez puede ser jugada por dos personas, por una persona
contra un programa de ajedrez o por dos programas de ajedrez entre sí.
13. Agente Inteligente: Se caracteriza por desenvolverse en un entorno, ejecutar
acciones sobre él, basándose en percepciones para lograr metas deseadas por el
usuario.
14. Conocimiento: Hechos o información adquiridos por un ser vivo a través de la
experiencia o la educación, la comprensión teórica o práctica de un asunto referente
a la realidad. Lo que se adquiere como contenido intelectual relativo a un campo
determinado o a la totalidad del universo. Conciencia o familiaridad adquirida por la
experiencia de un hecho o situación. Representa toda certidumbre cognitiva
mensurable según la respuesta a: ¿Por qué?, ¿Cómo?, ¿Cuándo?, ¿Dónde?.
15. Nataniel Rochester: (14 enero 1919 hasta 8 junio 2001) diseñó el IBM 701, escribió
el primer ensamblador y participó en la fundación del campo de la inteligencia
artificial. fue responsable del diseño y construcción de equipos de radar y otros
equipos militares. Diseñó el IBM 701, el primero de uso general, equipo de
producción masiva. Escribió el primer simbólico ensamblador, lo que permitió a los
programas que se escriben en, comandos legibles cortos en lugar de números puros
o códigos de perforación. Más tarde se unió a la división de sistemas de datos de
IBM. Desarrollando lenguajes de programación y de informática avanzada.
16. Allen Newel: (19 de marzo de 1927 - 19 de julio de 1992) fue un investigador en
informática y psicología cognitiva en la corporación WWE y en la escuela de
informática de Carnegie Mellon. Contribuyó al lenguaje de procesamiento de
información (IPL) (1956) y a dos de los primeros programas de inteligencia
artificial, la máquina de lógica teórica (1956) y el resolutor general de problemas
(1957), con Herbert Simon.
17. Herbert Simon: (15 de junio de 1916 – 9 de febrero de 2001), economista,
politólogo y teórico de las ciencias sociales estadounidense. En 1978 le fue
concedido el Premio Nobel de Economía por ser uno de los investigadores más
importantes en el terreno interdisciplinario y porque su trabajo ha contribuido a
racionalizar el proceso de toma de decisiones. Recibió el Premio Turing de la ACM
en 1975, junto con Allen Newell por hacer contribuciones básicas a la inteligencia
artificial, la psicología cognitiva humana y el procesamiento de listas, y el Award
for Distinguished Scientific Contribution de la Asociación Norteamericana de
Psicología (APA) en 1969.
HORIZONTALES
2. Hechos o información adquiridos por un ser vivo a través de la experiencia o la
educación, la comprensión teórica o práctica de un asunto referente a la realidad. Lo que se
adquiere como contenido intelectual relativo a un campo determinado…
4. Inteligencia Artificial.
6. (Boston, Massachusetts, 4 de septiembre de 1927 - Stanford, California, 24 de octubre de
2011), Fue un prominente informático que recibió el Premio Turing en 1971 por sus
importantes contribuciones en el campo de la Inteligencia Artificial. De hecho…
9. Proporciona una forma de separar aspectos y variaciones importantes de aquellos otros
sin importancia y que en caso contrario podría colapsar el proceso.
10. Formarse ideas en la mente.
11. Visión por computador.
12. La robótica es la rama de la tecnología que se dedica al diseño, construcción, operación,
disposición estructural, manufactura y aplicación de los robots.
13. El ajedrez es un juego entre dos personas, cada una de las cuales dispone de 16 piezas
móviles que se colocan sobre un tablero dividido en 64 partes. Está considerado como un
deporte. Originalmente inventado como un juego para personas…
14. (19 de marzo de 1927 - 19 de julio de 1992) fue un investigador en informática y
psicología cognitiva en la corporación WWE y en la escuela de informática de Carnegie
Mellon. Contribuyó al lenguaje de procesamiento de información…
15. Método propuesto por Alan Turing, para determinar si una maquina es capaz de pensar.
VERTICALES
1. Son programas computacionales diseñados para actuar como expertos en un dominio
particular restringido.
3. (n. en Nueva York el 9 de agosto de 1927- ) científico estadounidense considerado uno
de los padres de las ciencias de la computación y cofundador del laboratorio de inteligencia
artificial del Instituto Tecnológico de Massachusetts o MIT.
5. (14 enero 1919 hasta 8 junio 2001) diseñó el IBM 701, escribió el primer ensamblador y
participó en la fundación del campo de la inteligencia artificial. Fue responsable del diseño
y construcción de equipos de radar y otros equipos militares.
7. Proporciona una forma de resolver problemas en los que no se dispone de un método
directo.
8. (Míchigan, 30 de abril de 1916 - 24 de febrero de 2001) fue un ingeniero electrónico y
matemático estadounidense, desarrolló la entropía de la información. Trabajó en el
computador analógico más avanzado de esa era…
3. DEMOSTRACION TEORIA
Existen sistemas y procesos que la computadora no puede realizar, y evidencias que
demuestran que el computador no puede tomar decisiones, pero también existen evidencias
que demuestran lo contrario, que gracias a los avances tecnológicos la computadora puede
hacer mucho más y realizar tareas como las que realiza el ser humano, como lo muestra el
siguiente video.
http://www.youtube.com/watch?v=XpbVxYeuDVg.
1. Dos ejemplos más:
El buscador de Internet más utilizado y una de las marcas más conocidas a nivel mundial.
Google además se está posicionando en la mayoría de los sectores de la industria
tecnológica (Android, Chrome) y regala múltiples servicios. El logro de dar a los usuarios
un correo ilimitado lo ha masificado y la gente lo agradece. Permite además difundir
información libre no estando ligado a ningún régimen, país, religión o partido político.
Los videos juegos
Violentos o no, los video juegos de acción y de disparos tienen un objetivo primordial que
es divertir. Permiten a los que interactúan inteligentemente mejorar ciertas habilidades
relacionadas con el cerebro y la percepción, de tal manera que los sistemas expertos y los
agentes inteligentes creados por el hombre están demostrando que la computadora o el
hardware por medio del software si piensa y compiten igual con el ser humano o en algunos
casos mejor siendo más exactos como también en otros el ser humano es también es
superior. Pero ambos deben estar relacionados para ayudarse por ahora el hombre no puede
prescindir de la maquina ni la máquina del hombre para crear inteligencia. Un video más
que nos confirma que las maquinas si piensan e interactúan al jugar con el hombre.
http://www.rtve.es/alacarta/videos/redes/redes-como-influyen-videojuegos/1557690/
2. Percepción con respecto al tema:
Si el objetivo de la Inteligencia Artificial es la construcción de hardware como software que
puedan replicar la inteligencia humana y en la actualidad si se está logrando. Como no creer
y estar convencidos que en un futuro no muy lejano se construirá sistemas más perfectos
que se comporten igual que el ser humano en la resolución de problemas concretos y la
representación del conocimiento.
AGENTES INTELIGENTES
1. QUE ES UN AGENTE INTELIGENTE
Los agentes inteligentes se caracterizan por desenvolverse en un entorno, ejecutar acciones
sobre él, basándose en percepciones para lograr metas deseadas por el usuario. Según
Franklin and Grasser. Un agente inteligente es un sistema situado en y parte de un entorno
que siente ese entorno y actúa sobre él, a través del tiempo, persiguiendo sus propios
objetivos de forma que afecte la que siente en el futuro.
Ejemplos:
Un agente inteligente situado en internet, la percepción se puede ver cuando actúa sobre el
entorno a medida que va recibiendo e instruyéndose de las peticiones que hace el usuario
sobre él y las acciones se clarifican cuando el agente nos muestra información que el
mismo ha buscado en internet.
- Como ejemplos de entidades físicas pueden nombrarse:
1. Un robot de comportamiento variable autoregulado (ya sea que su comportamiento
sea determinado por software o incorporado directamente en la electrónica),
2. Una computadora que ejecuta un software de diagnóstico médico y muestra
resultados en una pantalla para ayudar a decidir a un médico,
3. una computadora especializada que controla un helicóptero en maniobras peligrosas
para un hombre.
- Ejemplos de entidad puramente virtual serían:
1. un software de descubrimiento de patrones en Internet que sólo interactúa con otros
software.
2. Un software softbot que simula a una persona en un juego de computadora, tal
como un jugador de ajedrez, un jugador de fútbol contrincante o un conductor de
carreras de automóviles, etc.
2. MAPA MENTAL – AGENTE INTELIGENTE
3. EJEMPLO DE PAMA
PAMA: Percepciones, acciones, metas, y ambiente.
Estructura de los agentes:
Programa = algoritmo + datos
Objeto = atributos + métodos
Agente = arquitectura + programa
Donde la arquitectura puede ser una computadora sencilla, o hardware especial para la
ejecución de ciertas tareas, como el procesamiento de imágenes de una cámara, o el filtrado
de señales de entrada de audio. Puede incluirse también un software que ofrezca cierto
grado de aislamiento entre la computadora y el programa agente, lo que permitiría la
programación aun nivel superior. Pone al alcance del programa las percepciones obtenidas
mediante los sensores, lo ejecuta y alimenta al efector con las acciones elegidas por el
programa conformes éstas se van generando.
En cuanto al programa, se refiere a la función que permita implantar el mapeo del agente
para pasar de percepciones a acciones y que se ejecutará en algún tipo de dispositivo de
cómputo.
Antes de diseñar un agente hay que centrarse en el entorno de trabajo, que son
esencialmente los problemas para los que los agentes son las soluciones, debe de
especificarse de la forma más completa posible.
El entorno de trabajo está conformado por cuatro elementos:
1. Medida de rendimiento (METAS). Cualidades deseables del agente. medidas de
rendimiento, objetivos, metas - Incluyen criterios que determinan el éxito en el
comportamiento del agente. Como regla general, es mejor diseñar medidas de utilidad de
acuerdo con lo que se quiere para el entorno, más que de acuerdo con cómo se cree que el
agente debe comportarse, por ejemplo en el agente aspiradora, su meta principal o medida
de rendimiento es: mantener siempre el “Suelo limpio”. (R)
2. Entorno sobre el cual actuará o se moverá el agente (E)
3. Actuadores – Herramientas o elementos para efectuar el trabajo, acciones a realizar (A)
4. Sensores – Como percibe el ambiente el agente, con qué lo percibe (S)
A estos cuatro elementos se les engloba con el acrónimo REAS (Rendimiento, Entorno,
Actuadores, Sensores) (libro: Stuart Russel y Pete Norving. Inteligencia Artificial un
enfoque moderno. Ed. Prentice-Hall) o PAAM (Percepción, Acción, Meta, Ambiente).
REAS = Rendimiento Entorno Actuadores Sensores
PAMA = Percepción Acción Meta Ambiente
Ejemplos de descripción REAS (O PAMA) de algunos agentes.
Tipo agente Rendimiento
(Metas)
Entorno
(Ambiente)
Actuadores
(Acciones)
Sensores
(Percepciones)
Sistema de
diagnóstico
médico
Paciente
saludable,
reducción al
mínimo de los
costos y de las
demandas.
Paciente,
hospital,
personal
Preguntas,
pruebas,
tratamientos,
diagnósticos,
casos.
Impresora,
monitor
Síntoma,
evidencias y
respuestas del
paciente.
Teclado para
emitir dicha
información.
Sistema para el
análisis de
imágenes
satelitales
Clasificación
correcta de la
imagen.
Imágenes
enviadas desde
un satélite en
órbita,
conexión con
el satélite en
órbita.
Visualizar e
imprimir una
clasificación de
escena.
Pixel de
intensidad y
colores
diversos
(matriz de bits)
Robot
clasificador
(seleccionador)
de partes
Poner las
partes en el
bote que les
corresponda.
Porcentaje de
piezas clasificadas.
Banda
transportadoras
sobre la que se
encuentran las
partes, las
partes, y los botes sobre en
los que se
depositarán las
Recoger partes
y clasificarlas
poniéndolas en
botes.
Brazos y
manos articulados.
Pixel de
intensidad
variable (mapa
de bits).
Cámara, sensor
angular.
partes
clasificadas.
Controlador de
un refinería
Maximizar la
seguridad,
pureza y
rendimiento
(producción).
Refinería,
operadores
Abrir y cerrar
válvulas,
ajustar la
temperatura.
Válvulas,
bombas,
calentadores,
monitores.
Lectura de
temperatura y
presión.
Sensores
químicos.
Tutor
interactivo de
inglés
Que el
estudiante
obtenga la
máxima
calificación en
una prueba.
Grupo de
estudiantes,
agencia
examinadora.
Ejercicios en
línea,
impresos, de
audio,
visualizar
correcciones y
sugerencias.
Bocinas,
monitor,
impresora.
Palabras
escritas a
través del
teclado, y
emisión de
voz.
Teclado,
micrófono.
Conductor de
taxi
Viaje seguro,
rápido, sin
infracciones,
cómodo,
obtención
máxima de
ganancias.
Caminos,
tráfico,
peatones,
cliente,
semáforos.
Manipulación
del volante,
acelerar, frenar,
hablar con el
pasajero.
Acelerador,
freno, bocina,
visualizador
(pantalla)
Cámaras,
velocímetro,
sistema
satelital global
de ubicación,
sonar,
micrófono,
sensores de
motor, teclado,
tacómetro,
visualizador de
la aceleración.
COMPLEJIDAD DE LOS PROBLEMAS
1. EXOLICACION - DEFINICION FORMAL DE UN PROBLEMA
El primer pasa para diseñar un programa que resuelva un problema es crear una descripción
formal y manejable del propio problema. Sería adecuado contar con programas que
produzcan descripciones formales a partir de descripciones informales, procesos
denominado operacionalizaciòn. Dado que por ahora no se conoce la forma de construir
estos programas este proceso debe hacerse manualmente.
Hay problemas que por ser artificiales y estructurados son fáciles de especificar como por
ejemplo el ajedrez. Otros problemas naturales como por ejemplo la comprensión del
lenguaje, no son tan sencillos de especificar.
Para producir una especificación formal de un problema se deben definir:
- Espacio de estados válidos
- Estado inicial del problema
- Estado objetivo o final
- Reglas que se pueden aplicar para pasar de un estado a otro
Un estado es la representación de un problema de un problema en un instante dado. Para
definir el espacio de estados no es necesario hacer una enumeración exhaustiva de todos los
estados válidos, sino que es posible definirlo de manera más general.
El estado inicial consiste en uno o varios estados finales que se consideran solución
aceptable.
Las reglas describen las acciones u operadores que posibilitan un pasaje de estados. Una
regla tiene una parte izquierda y una parte derecha. La parte izquierda determina la
aplicabilidad de la regla, es decir, describe los estados a los que puede aplicarse la regla. La
parte derecha describe la operación que se lleva a cabo si se aplica la regla, es decir, como
obtener el estado sucesor.
La representación como espacio de estados forma parte de la mayoría de los métodos de IA
su estructura se corresponde con la resolución de problemas porque:
1. Permite definir formalmente el problema, mediante la necesidad de convertir una
situación dada en una situación deseada mediante un conjunto de operaciones
permitidas.
2. Permite definir el proceso de resolución de un problema como una combinación de
técnicas conocidas y búsqueda (la técnica general de exploración del espacio
intenta encontrar alguna ruta desde el estado actual hasta un estado objetivo).
2. PRESENTACION - P – NP – NP COMPLETO
Hablar de algoritmos, se refiere a enfrentarnos a un problema concreto. Habrá una serie de
algoritmos aplicables. Se dice que el orden de complejidad de un problema es el del mejor
algoritmo que se conozca para resolverlo. Así se clasifican los problemas y los estudios
sobre algoritmos que se aplican a la realidad.
Estos estudios han llevado a la constatación de que existen problemas muy difíciles,
problemas que desafían la utilización de los ordenadores para resolverlos. En lo que sigue
esbozaremos las clases de problemas que hoy por hoy se escapan a un tratamiento
informático.
Clase P:
Los algoritmos de complejidad polinónica se dice que son tratables en el sentido de que
suelen ser abordables en la práctica. Los problemas para los que se conocen algoritmos con
esta complejidad se dice que forman clase P. Aquellos problemas para los que la mejor
solución que se conoce es de complejidad superior a la polinónica, se dice que son
problemas intratables. Sería muy interesante encontrar alguna solución polinomica a mejor
que permitiera abordarlos.
Clase NP
Algunos de estos problemas intratables pueden caracterizarse por el curioso hecho de que
puede aplicarse en algoritmo polinomico para comprar si una posible solución es válida o
no. Esta característica lleva a un método de resolución no determinista consistente en
aplicar heurísticos para obtener soluciones hipotéticas que se van desestimando consistente
en aplicar heurísticos para obtener soluciones hipotéticas que se van desestimando o
aceptando a ritmo polinomico. Los problemas de esta clase de denominan NP la N no-
deterministas y la P de polinomicos.
Clase NP-Complementos
Se conoce una amplia variedad de problemas de tipo NP, de los cuales destacan algunos de
ellos de extrema complejidad. Graficamente podemos decir que algunos poblemas se hayan
en la “frontera extrema” de clase NP. Son problemas NP, y son los peores problemas
posibles de clase NP. Estos problemas se caracterizan por ser todos “iguales” en el sentido
de que si se descubriera una solución P para alguno de ellos, esta solución sería fácilmente
aplicables a todos ellos. Actualmente hay un premio de prestigio equivalente al Novel
reservado para el que descubra semejante solución.
Si se descubriera una solución para los problemas NP-Completos, esta sería aplicable a
todos los problemas NP y por tanto, la clase NP desaparecería del mundo científico al
carecerse de problemas de ese tipo. Realmente, tras años de búsqueda exhaustiva de dicha
solución, es hecho ampliamente aceptado que no debe existir, aunque nadie ha demostrado,
todavía, la imposibilidad de su existencia.
3. PROBLEMAS NP
Mientras que la pertenencia del problema SAT o de satisfacibilidad booleana a la clase de
los NP-completos fue demostrada utilizando mecanismos particulares, las pertenencias de
los 21 problemas siguientes fueron demostradas mediante reducciones polinomiales. Así, el
problema SAT se redujo polinomialmente a los problemas 0-1 INTEGER
PROGRAMMING, CLIQUE y 3-SAT, y estos a su vez se redujeron a otros varios. La lista
completa es la que se muestra a continuación. Las sangrías denotan el hecho que la NP-
completitud del problema fue demostrada por reducción polinomial del problema en el
nivel directamente superior. Note que los nombres de los problemas están escritos con
letras mayúsculas y corresponden a abreviaciones del nombre en inglés, como es lo usual;
junto a ellos, entre paréntesis, se escribe la traducción del nombre en español.
- SAT (Problema de satisfacibilidad booleana, para fórmulas en forma normal
conjuntiva)
o 0-1 INTEGER PROGRAMMING (Problema de la programación lineal
entera)
o CLIQUE (Problema del clique, Problema del conjunto independiente)
SET PACKING (Problema del empaquetamiento de conjuntos)
VERTEX COVER (Problema de la cobertura de vértices)
SET COVERING (Problema del conjunto de cobertura)
FEEDBACK NODE SET
FEEDBACK ARC SET
DIRECTED HAMILTONIAN CIRCUIT (Problema del
circuito hamiltoniano dirigido)
o UNDIRECTED HAMILTONIAN CIRCUIT
(Problema del circuito hamiltoniano no dirigido)
- 3-SAT (Problema de satisfacibilidad booleana de 3 variables por cláusula)
o CHROMATIC NUMBER (Problema de la coloración de grafos)
CLIQUE COVER (Problema de la cobertura de cliques)
EXACT COVER (Problema de la cobertura exacta)
HITTING SET
STEINER TREE
3-DIMENSIONAL MATCHING (Problema del matching
tridimensional)
KNAPSACK (Problema de la mochila)
o JOB SEQUENCING (Problema de las secuencias de
trabajo)
o PARTITION (Problema de la partición)
MAX-CUT (Problema del corte máximo)
Tras un tiempo se descubrió que muchos de estos problemas podían ser resueltos si su
enunciado se particularizaba a unas ciertas clases, o podían ser resueltos aproximadamente
con un error máximo de un cierto porcentaje. Sin embargo David Zuckerman demostró en
1996 que cada uno de estos 21 problemas tiene una versión restringida de optimización que
es no aproximable a menos que P = NP, demostrando que la versión de la reducción, dada
por Karp, generaliza un tipo específico de reducción por aproximación.
CONCLUSIONES
Después de realizar las diferentes actividades grupales e individuales propuestas por
nuestra tutora. En la temática de la unidad uno Introducción a la inteligencia Artificial
donde se ha realizado una lectura comprensiva que nos ha permitido interiorizar los
diferentes conceptos. Podemos concluir lo siguiente.
1. Conocer algunos métodos para construir sistemas inteligentes. Por medio de las
técnicas más comunes de programación para representar el conocimiento.
2. Concientizarnos de la aplicabilidad de las técnicas, comprendiendo y afianzando los
conocimientos.
3. Entender los problemas computacionales de una manera teórica y lograr la
comprensión de los mismos según ciertos ejemplos en la ciencia de la computación
con modelos básicos y complejidad de problemas.
BIBLIOGRAFIA
Gonzales, Ángela María (2013), Inteligencia Artificial, Universidad Nacional Abierta y a
Distancia, Bogotá D.C.
Web grafía
www.wikipedia.org/wiki/Conocimiento
http://www.crosswordpuzzlegames.com/cgi-crosswordpuzzlegames/create
http://www.rtve.es/alacarta/videos/redes/redes-como-influyen-videojuegos/1557690/
http://isc-ia.wikispaces.com/Agente+inteligente+(inteligencia+artificial)
http://poiritem.wordpress.com/2009/11/16/6-4-2-agentes-inteligentes-y-la-naturaleza-de-su-
entorno/