MOMENTO_1

MOMENTO 1

Luis Alberto Sanchez Correa - Código: 16.786.134

Jose Ramon Valencia -  Código: 16937012

Carlos Fernando Escalante - Código: 94476240

Jhon Faber Patiño - Código: 10490814

Carlos Arturo Cardona - 

Director: Diego Fernando Medina

Grupo Colaborativo: 90169A_223

Universidad Nacional Abierta y a Distancia – UNAD.

Programa: Ingeniería Electrónica

Cead: Palmira- Valle- Colombia

Julio -2015

INTRODUCCION

En el presente informe se busca iniciar y facilitar el proceso de aprendizaje con base en la identificación de conocimientos previos sobre la temática del curso; reconocer a los compañeros de equipo de trabajo, al tutor y al director del curso.

Desde hace algunas décadas algunas mentes brillantes han estudiado la IA (inteligencia artificial) encaminando sus esfuerzos en crear sistemas cada vez más autónomos e inteligentes que realicen tareas que el cerebro humano no podría en determinado tiempo.  Pero el órgano más poderoso de nuestro cuerpo, el cerebro, es inigualable por las relaciones que existen entre las millones de neuronas que interactúan para realizar procesos complejos, que tal vez las maquinas nunca lograrían, aunque en un futuro tal vez lejano o no, podríamos pensar en crear sistemas con una inteligencia aproximada a la humana.

Uno de los objetivos de la IA es el diseño de Agentes Inteligentes que a través de sus percepciones del ambiente, tome las decisiones adecuadas y realice las acciones correctas, es por esto que en esta actividad intentaremos diseñar, de forma general, un Agente Inteligente capaz de dar pronósticos sobre La Edición de la Vuelta Ciclista de España de acuerdo a información suministrada bajo este entorno.

El grupo colaborativo entregará el desarrollo de una solución que involucre el análisis y diseño. Durante el desarrollo cada participante tendrá la oportunidad de interactuar en el foro de trabajo colaborativo para resolver diferencias con los compañeros de grupo.

OBJETIVOS

Generales

Diseñar de forma general un agente inteligente sobre la Edición de la vuelta ciclista de España.

Específicos

 Identificar los tipos de Agentes Inteligentes.

 Descubrir las ventajas y desventajas de la inteligencia artificial.

 Participar e interactuar constante en el foro del desarrollo de la actividad, presentando respuesta a las preguntas solicitadas, debatiendo y retroalimentando las respuestas de los compañeros de grupo, en pro de enriquecer cada producto individual, teniendo como base el reconocimiento de los entornos del curso, y lectura apropiación del Syllabus del curso. 

 Conocer a los integrantes del grupo colaborativo.

 Identificar los tipos de problemas computacionales y su complejidad

HISTORIA CRONOLOGIA DE LA INTELIGENCIA ARTIFICIAL

Estudiante                Web links de las presentaciones
                Luis Alberto Sanchez          ==>           Redes Neuronales
                Jose Ramon Valencia          ==>          Sistemas Expertos
                Jhon Faber Patino              ==>           Robótica
                Carlos Arturo Cardona       ==>          Realidad Virtual
                Carlos Fernando Escalante  ==>         Vida Artificial

Diseño de un Agente Inteligente

Por definición un agente inteligente es una entidad que percibe y actúa sobre un entorno, un agente es todo aquello que puede considerarse que percibe su ambiente mediante sensores y que responde o actúa en tal ambiente por medio de efectores.  En este caso un agente de software, sus percepciones y acciones vienen a ser las cadenas de bits codificados.

 Describa las propiedades de los agentes que hace uso el agente seleccionado.

                                             

Se debe utilizar un Agente Inteligente de Información de Reflejo Simple, el cual podrá procesar consultas, poseer capacidad de proceso y conocimiento del entorno donde se mueve; además, contener información de un dominio, en este caso las Ediciones de la Vuelta Ciclista de España. Este agente también utilizara información de otros Agentes como base de conocimiento para tomar las decisiones más adecuadas.

Las propiedades de las que hará uso el Agente Inteligente de Información son:

Autonomía: Actuar sin ningún tipo de intervención humana directa, y tener control sobre sus propios actos.

Sociabilidad: Comunicarse por medio de un lenguaje común con otros agentes, e incluso con los humanos.

Capacidad de reacción: Percibir su entorno, y reaccionar para adaptarse a él.

Iniciativa: Emprender las acciones para resolver un problema.

La siguiente figura muestra un esquema generalizado de nuestro agente

2.2  Definir el problema del agente

Nuestro Agente inteligente debe percibir las entradas que han sido ingresadas al sistema como los datos personales de los ciclistas, condición física, kilómetros recorridos, numero de etapas, puesto que ocupo en la clasificación final; además debe percibir la información del equipo como la nacionalidad, el nombre del director y las pruebas que ha participado.

De acuerdo a esta información suministrada por el entorno de la Vuelta Ciclista de España, debe analizarla junto con la información obtenida de otros agentes inteligentes y tomar decisiones respecto a los pronósticos sobre la competencia, tal vez sugiriendo sobre los posibles ganadores de la Vuelta Ciclista a España.

El programa puede realizar tareas específicas para el usuario y posee un grado de inteligencia suficiente para ejecutar parte de sus tareas de forma autónoma y para interactuar con el entorno de forma útil.

CRUCIGRAMA

Horizontales

1. Es la combinación de la ciencia de los computadores, la psicología y la filosofía.

5. Propiedad de los agentes inteligentes que hace referencia a la interacción con otros agentes y otras entidades

6. Según las primeras investigaciones la IA necesita de

8. Una de las características en las que se puede dividir un problema.

10. Los agentes se clasifican según su

11. Investigador que definió la inteligencia como la capacidad de desarrollar conceptos y captar su significado

12. Maquina programable de propósito general que pose ciertas características antropomórficas

Verticales

2. Se caracterizan por actuar en un ambiente en particular y ser capaces de realizar varias acciones basadas en su entorno

3. Programas computacionales diseñados para actuar como expertos en un dominio en particular restringido.

4. Método propuesto para saber si una maquina es capaz de pensar

7. Sugiere que inteligencia es todo lo que puede ser medido mediante pruebas de inteligencia

9. Dentro del desarrollo histórico propuesto por Jackson periodo comprendido entre 1965-1975

13. Nombre del creador del Test de Turing

14. Sistema que intenta simular un comportamiento lingüístico humano

15. Inteligencia Artificial

RESPUESTAS

Horizontales

      1.Inteligencia artificial

5.   sociabilidad

6.   conocimiento

8.   Polinomial

10.  entorno

11.  Ternan

12.  robot

Verticales

2.  Agentes inteligentes
3.  Sistemas expertos
4.  Test de turing

7.   Marvin Minsky

9.   romántico

13.  Alan

14.  PLN (Procesamiento de lenguajes naturales)

15.  IA

COMPLEJIDAD COMPUTACIONAL

EFICIENCIA ALGORITMICA

La Teoría de la Complejidad Computacional es una rama de la teoría de la computación que se centra en la clasificación de los problemas computacionales de acuerdo a su dificultad inherente, y en la relación entre dichas clases de complejidad.   Un problema se cataloga como "inherentemente difícil" si su solución requiere de una cantidad significativa de recursos computacionales, sin importar el algoritmo utilizado. La teoría de la complejidad computacional formaliza dicha aseveración, introduciendo modelos de cómputo matemáticos para el estudio de estos problemas y la cuantificación de la cantidad de recursos necesarios para resolverlos, como tiempo y memoria.

Uno de los fines de la teoría de la complejidad computacional es determinar los límites prácticos de qué es lo que se puede hacer en una computadora y qué no. Otros campos relacionados con la teoría de la complejidad computacional son el análisis de algoritmos y la teoría de la computabilidad. Una diferencia significativa entre el análisis de algoritmos y la teoría de la complejidad computacional, es que el primero se dedica a determinar la cantidad de recursos requeridos por un algoritmo en particular para resolver un problema, mientras que la segunda, analiza todos los posibles algoritmos que pudieran ser usados para resolver el mismo problema.  La teoría de la complejidad computacional trata de clasificar los problemas que pueden, o no pueden ser resueltos con una cantidad determinada de recursos. A su vez, la imposición de restricciones sobre estos recursos, es lo que la distingue de la teoría de la computabilidad, la cual se preocupa por qué tipo de problemas pueden ser resueltos de manera algorítmica.

En Ciencias de la Computación, el término eficiencia algorítmica es usado para describir aquellas propiedades de los algoritmos que están relacionadas con la cantidad de recursos utilizados por el algoritmo. Un algoritmo debe ser analizado para determinar el uso de los recursos que realiza. La eficiencia algorítmica puede ser vista como análoga a la ingeniería de productividad de un proceso repetitivo o continuo.  Con el objetivo de lograr una eficiencia máxima se quiere minimizar el uso de recursos. Sin embargo, varias medidas (e.g. complejidad temporal, complejidad espacial) no pueden ser comparadas directamente, luego, cual de dos algoritmos es considerado más eficiente, depende de cual medida de eficiencia se está considerando como prioridad, e.g. la prioridad podría ser obtener la salida del algoritmo lo más rápido posible, o que minimice el uso de la memoria, o alguna otra medida particular.  Note que este artículo no trata de optimización, concepto que es abordado en optimización de programas, compiladores de optimización, optimización de bucles, optimización de códigos orientados a objetos, etc. El término optimización en si puede causar confusión, ya que todo lo que generalmente se puede hacer es en realidad una 'mejora'.

El análisis de algoritmos es una parte importante de la Teoría de complejidad computacional más amplia, que provee estimaciones teóricas para los recursos que necesita cualquier algoritmo que resuelva un problema computacional dado. Estas estimaciones resultan ser bastante útiles en la búsqueda de algoritmos eficientes. A la hora de realizar un análisis teórico de algoritmos es común calcular su complejidad en un sentido asintótico, es decir, para un tamaño de entrada suficientemente grande. La cota superior asintótica, y las notaciones omega (cota inferior) y theta (caso promedio) se usan con esa finalidad. Por ejemplo, la búsqueda binaria decimos que se ejecuta en una cantidad de pasos proporcional a un logaritmo, en O(logno), coloquialmente "en tiempo logarítmico". Normalmente las estimaciones asintóticas se utilizan porque diferentes implementaciones del mismo algoritmo no tienen por qué tener la misma eficiencia. No obstante la eficiencia de dos implementaciones "razonables" cualesquiera de un algoritmo dado está relacionada por una constante multiplicativa llamada constante oculta.

La medida exacta (no asintótica) de la eficiencia a veces puede ser computada pero para ello suele hacer falta aceptar supuestos acerca de la implementación concreta del algoritmo, llamada modelo de computación. Un modelo de computación puede definirse en términos de un ordenador abstracto, como la Máquina de Turing, y/o postulando que ciertas operaciones se ejecutan en una unidad de tiempo. Por ejemplo, si al conjunto ordenado al que aplicamos una búsqueda binaria tiene 'n' elementos, y podemos garantizar que una única búsqueda binaria puede realizarse en un tiempo unitario, entonces se requieren como mucho log2 N + 1 unidades de tiempo para devolver una respuesta.

Las medidas exactas de eficiencia son útiles para quienes verdaderamente implementan y usan algoritmos, porque tienen más precisión y así les permite saber cuánto tiempo pueden suponer que tomará la ejecución. Para algunas personas, como los desarrolladores de videojuegos, una constante oculta puede significar la diferencia entre éxito y fracaso.

Las estimaciones de tiempo dependen de cómo definamos un paso. Para que el análisis tenga sentido, debemos garantizar que el tiempo requerido para realizar un paso se encuentre acotado superiormente por una constante. Hay que mantenerse precavido en este terreno; por ejemplo, algunos análisis cuentan con que la suma de dos números se hace en un paso. Este supuesto puede no estar garantizado en ciertos contextos. Si por ejemplo los números involucrados en la computación pueden ser arbitrariamente grandes, dejamos de poder asumir que la adición requiere un tiempo constante (usando papel y lápiz, compara el tiempo que necesitas para sumar dos enteros de 2 dígitos cada uno y el necesario para hacerlo con dos enteros pero de 1000 dígitos cada uno).

¿Qué hace para un algoritmo BUENO?

• Debe Funcionar.
• Debe completar su tarea en una cantidad finita (razonable) de tiempo.
• Dos o más algoritmos que resuelven el mismo problema pueden ser muy diferentes y todavía satisfacer estos dos criterios. Por lo tanto, el siguiente paso es determinar qué algoritmo es "mejor". 
• En general, existen dos criterios utilizados para determinar si un algoritmo es "mejor" que otro.

1. Espacio necesario (es decir, la cantidad de memoria que se necesita para completar la tarea).
2. Requisitos de tiempo (es decir, cuánto tiempo se tarda en completar la tarea).
3. Un tercer criterio que se debe considerar es el costo del tiempo humano. Es decir, el tiempo para desarrollar y mantener el programa. 
4. Un truco de codificación inteligente que puede mejorar los requisitos de espacio y tiempo y / o frecuencia puede ser compensado por la pérdida de la legibilidad del programa que se traduce en el aumento del costo humano de mantener el programa. 

Debido al hecho de que los ordenadores de hoy en día tienen grandes cantidades de memoria (tanto internos como secundarias), este curso será principalmente preocupados con los requisitos de tiempo. En la mayoría de los casos, las diferencias en los requisitos de espacio de la mayoría de los algoritmos es insignificante.

Medición Requisitos Tiempo de un algorithmo

¿Cómo se determina los requisitos de tiempo de dos algoritmos?

Opción 1: Escribir y Ejecutar un Programa - Una manera obvia de probar la velocidad de dos algoritmos diferentes sería escribir dos programas y luego ejecutar estos programas con algún tipo de dispositivo de tiempo. Aunque esto puede ser una buena indicación de que el algoritmo es más rápido (vamos a menudo hacer esto), hay al menos cuatro problemas con este enfoque que necesitan ser considerados.

Overhead: La implementación real del algoritmo en un programa puede requerir algún tipo de gastos generales de programación que pueden influir en la velocidad aparente del algoritmo real.

Codificación: La velocidad del algoritmo podría verse afectada por la codificación real del programa y / o el lenguaje de programación utilizado. La diferencia podría ser simplemente el resultado de una mejor programación o el idioma.

El Ordenador: La velocidad del programa podría estar influenciado por el equipo que ejecuta el programa y cómo se ejecuta conjuntos particulares de declaraciones.

Los datos: Los datos de prueba reales puede tener una gran influencia en la eficiencia de un programa. Este es probablemente el problema más importante y el más difícil de superar (no se puede probar todos los posibles conjuntos de datos).

Opción 2: Análisis matemático - Un enfoque más fiable para el análisis de la eficiencia de los algoritmos es medir matemáticamente la velocidad del algoritmo en términos de "uints tiempo". 

Los diferentes tipos de operaciones o estados pueden requerir diferentes unidades de tiempo. Algunas unidades de tiempo comunes que a menudo son considerados incluyen:

comparaciones (más común)

asignaciones (al lado más común)

Operaciones de E / S

operaciones numéricas (es decir, adiciones, sustracciones, multiplicaciones, ...)

Por lo tanto, nuestra medida primaria de eficacia algoritmo será un análisis matemático del número de comparaciones y / o asignaciones requeridas por el algoritmo para completar su tarea. En la mayoría de los casos, solo se utilizarán comparaciones debido a que una comparación (es decir, la decisión) es mucho más costoso (en términos de tiempo) que una asignación o cálculo.

eor - Caso, Mejor - Caso y  Caso promedio:

Con algunos algoritmos, la eficiencia de la velocidad es una función de la cantidad de datos pero independiente de los datos reales. Por ejemplo, la búsqueda de la suma de los valores de una matriz de números enteros.

Con otros algoritmos, la eficiencia de velocidad no sólo se ve afectada por la cantidad de datos, pero también por el propio datos real. Por ejemplo, buscar una matriz de objetos para un artículo con un valor particular en algún campo clave. Lo que usted está buscando puede ser el primer punto marcado (que sólo requiere un cheque), o puede ser que no puede encontrar en todo (que requieren el máximo número de cheques).

En estos casos, es importante tener en cuenta:

peor de los casos: La situación que requeriría la mayor cantidad de procesamiento.

mejor de los casos: La situación que requeriría la menor cantidad de procesamiento.

promedio de los casos: La cantidad promedio de procesamiento requerido. Esta opción es la más difícil de calcular, ya que debe tener en cuenta las probabilidades de todos los casos posibles y la cantidad de procesamiento requerido para cada caso.

En estas situaciones, la aplicación de un algoritmo particular sería determinada por el cual extrema es más probable para el algoritmo particular.

Ejemplos: Búsquedas secuenciales y binarios de una matriz de n artículos

Búsqueda secuencial - Supongamos que los datos de la matriz es en ningún orden en particular.

peor de los casos: no encontrado o la búsqueda del elemento que se encuentra en la última posición. f ( n) = n

mejor de los casos: Se encuentra en la primera posición. f ( n) = 1

caso promedio: Suponiendo que la probabilidad de que el artículo se encuentra en cualquier posición es igualmente probable, f ( n) = 1 / n + 2 / n + 3 / n + ••• + n / n = (1 + 2 + 3 + ••• + n) / n = (n + 1) / 2

Ordenado Búsqueda secuencial - Requiere la condición previa de que los datos de la matriz se ordena por el campo de clave que se utilizará para la búsqueda. Esta sobrecarga adicional afectará a la eficacia de la búsqueda, pero por ahora no será considerado.

peor de los casos: Busca el elemento que es mayor o igual que el artículo en la última posición. f ( n) = n

mejor de los casos: Busca el elemento que es menor o igual al elemento de la primera posición. f ( n) = 1

caso promedio: --- no pueden, en general, se determinará ---

Binary Search - Requiere la condición previa de que los datos de la matriz se ordena por el campo de clave que se utilizará para la búsqueda. Esta sobrecarga adicional afectará a la eficacia de la búsqueda, pero por ahora no será considerado 

peor de los casos: no encontrado o la búsqueda del elemento que sería el último comprobado antes de determinar que no está en la matriz. f ( n) = log2N (ver más abajo para la obtención de este resultado)

mejor de los casos: Se encuentra en la posición n / 2 (el primer valor marcada). f ( n) = 1

caso promedio: --- no pueden, en general, se determinará ---

Determinar el cálculo del peor caso para la búsqueda binaria ...

La búsqueda binaria comienza por mirar el elemento medio en la matriz (en la posición n / 2). Esto da lugar a tres posibilidades:

Este es el artículo que usted está buscando, en cuyo caso está ahora terminado. Pero esto no sería el peor de los casos, por lo tanto, vamos a ignorar esta posibilidad.

El artículo que usted está buscando es inferior (es decir, viene antes) el elemento central. Por lo tanto, se puede tirar a la basura el elemento central y la segunda mitad de la lista y buscar en la primera mitad de la lista por el mismo proceso. Esto se traduce en la búsqueda de en medio de n / 2 artículos.

El artículo que usted está buscando es mayor que (es decir, viene después) el elemento central. Por lo tanto, se puede tirar a la basura el elemento central y la primera mitad de la lista y buscar en la segunda mitad de la lista por el mismo proceso. Esto se traduce en la búsqueda de en medio de n / 2 artículos.

Así que la cuestión se reduce a, "¿Cuántas veces puede byc producirse antes de ejecutar fuera de los datos a tener en cuenta?"

Los primeros resultados de la comparación de n / 2 artículos sobrantes.

Los resultados de comparación en segundo (n / 2) / 2 = n / (22) artículos sobrantes.

Los resultados tercio de comparación en ((n / 2) / 2) / 2 = n / (23) artículos sobrantes.

Los resultados del cuarto de comparación en n / (24) artículos sobrantes.

etc ........

Finalmente, los resultados de la comparación de orden k en n / (2k) artículos sobrantes. Si estos resultados en un artículo dejaron entonces sólo una comprobación más necesita ser hecho.

Por lo tanto, se necesitan aproximadamente comparaciones k para buscar en la matriz. Después comparaciones k, habría sólo 1 artículo sobra. Por lo tanto ...

n / (2k) = 1

2k = n

k = log2N

Desde log2N es menor que n, podemos concluir que una búsqueda binaria es más eficiente que una búsqueda lineal (en el peor caso posible).

.

-----------------------------------------------

PROBLEMAS INTRATABLES: Los NP-Difíciles

 Elaborado por José Ramón Valencia

Supón que tu jefe te pide que escribas un algoritmo eficiente para un problema extremadamente importante para tu empresa. Después de horas de romperte la cabeza solo se te ocurre un algoritmo de “fuerza bruta”, que analizándolo ves que cuesta tiempo exponencial. Te encuentras en una situación muy embarazosa: “No puedo encontrar un algoritmo eficiente, me temo que no estoy a la altura” .Te gustaría poder decir “No puedo encontrar un algoritmo eficiente porque no existe” Eso es decir que el problema es intratable.

 En realidad es muy poco frecuente poder decir algo tan tajante, para la mayoría de los problemas, es muy difícil demostrar que son intratables, pero la teoría de los NP-completos te puede ayudar a no perder tu trabajo diciendo: 

“No puedo encontrar un algoritmo eficiente pero tampoco pueden ninguno de estos informáticos famosos”

La teoría de los NP-completos es muy útil para diseñar algoritmos, aunque solo de resultados negativos.  Permite al diseñador centrar sus esfuerzos más productivamente, no darse de cabezazos contra la pared.  Si no conseguimos demostrar que un problema es difícil o intratable, entonces hay que centrarse en encontrar un algoritmo eficiente.

La teoría de los NP-completos nos permite identificar que propiedades hacen un problema difícil. Tener una intuición de que problemas van a ser intratables es importante para un diseñador, y solo se consigue con experiencia demostrando intratabilidad.

El concepto fundamental es el de reducción entre un par de problemas, que permite compararlos.

·         Si A es reducible a B y tenemos un algoritmo eficiente para B entonces tenemos un algoritmo eficiente para A.

·         Si A es reducible a B y no existe un algoritmo eficiente para A entonces no existe un algoritmo eficiente para B

A ≤ B

Reducción Sencilla para Intratabilidad          

Queremos demostrar que algunos problemas son intratables, es decir, que no tienen algoritmos eficientes Partimos de que Ciclo Hamiltoniano y Cobertura de Vértices son intratables.

·         Si Ciclo Hamiltoniano es reducible a B entonces B es intratable.

·         Si Cobertura de Vértices es reducible a B entonces B es intratable

Reducción de ciclo Hamiltoniano

CicloHam ≤ B

Transformamos la entrada de Ciclo Hamiltoniano en entrada de B.

·         La solución de B nos da la solucion para Ciclo Hamiltoniano

·         Como Ciclo Hamiltoniano es intratable entonces B es intratable

                                     

Ejemplo de Problema Intratable

Imagínate que eres es un actor muy cotizado, que tienes ofertas para protagonizar n películas En cada oferta viene especificado en el primer y último día de rodaje. Para aceptar el trabajo, debes comprometerte a estar disponible durante todo este periodo entero, por lo tanto no puedes aceptar simultáneamente dos papeles cuyos intervalos se superpongan.

Para un artista como tú, los criterios para aceptar un trabajo son claros: quieres ganar tanto dinero como sea posible. Debido a que cada una de estas películas paga la misma tarifa por película, esto implica que buscas la mayor cantidad posible de puestos de trabajo (intervalos) de tal manera que dos cualesquiera de ellos no estén en conflicto entre sí.

Tú (o tu agente) debes resolver el siguiente problema de algoritmia:

·         Problema: Planificación de películas

·         Entrada: Un conjunto I de n intervalos, k ∈ N

·         Salida: ¿Cuál es el mayor conjunto de intervalos de I que dos a dos sean disjuntos? o ¿qué películas puedo hacer ganando la mayor cantidad de dinero?

·         No es muy difícil encontrar un algoritmo eficiente.

Pero vamos a considerar otro problema más difícil.

Más difícil: un proyecto de película no tiene por qué rodarse en un solo intervalo, puede tener un calendario discontinuo

·         Por ejemplo “Tarzàn de la jungla” se rodara en Enero-Marzo y Mayo-Junio, “Terminator” se rodará en Abril y en Agosto, “Babe” se rodará en Junio-Julio

·         El mismo actor puede rodar “Tarzàn de la jungla” y “Terminator” pero no “Tarzàn de la jungla” y “Babe”

·          Vamos a ver que la versión decisional es intratable

Ø  Problema: Planificación general de películas Entrada: Un conjunto I de n conjuntos de intervalos, k ∈ N Salida: ¿Existen k conjuntos de intervalos de I que dos a dos sean disjuntos?

Ø  Necesitamos hacer una reducción desde otro problema que sepamos intratable

Ø  Vamos a intentarlo desde Conjunto Independiente ¿En que se parecen los dos problemas?

·         Los dos pretenden seleccionar el subconjunto más grande posible  de vértices y de películas.

·         Intentemos traducir los vértices en películas

·         Intentemos traducir vértices con una arista en películas incompatibles

Conjunto Independiente(G, k)

·         m =número de aristas de G

·          n =número de vértices de G

·          I = ∅

·         for j = 1 to n 5

·                           pelicula(j) = ∅

·                           I = anadir(I, pelicula(j))

·          for la ièsima arista de G (x, y), 1 ≤ i ≤ m

·                  pelicula(x) = anadir(pelicula(x), [i, i + 0,5])

·                  pelicula(y) = anadir(pelicula(y), [i, i + 0,5])        

·           Resultado GralPlanifPeliculas(I, k).

·         Cada arista se traduce en un intervalo

·         Cada vértice es una película que contiene los intervalos de las aristas desde ese vértice

·         Dos vértices unidos por una arista (prohibido en el Conjunto Independiente) definen un par de películas que comparten un intervalo (prohibido en el calendario del actor) y viceversa

·         Los mayores subconjuntos que satisfacen los dos problemas son los mismos

·         Tenemos una reducción, un algoritmo eficiente para el problema Gral. de planificación de películas nos da un algoritmo eficiente para Conjunto Independiente

·         Como Conjunto Independiente es intratable, problema Gral. de planificación de películas es intratable

3.3 Complejidad – Problemas NP

Problemas de decisión que tienen un algoritmo de tiempo Polinomial en una maquina no determinista que los acota.

Un problema de decisión pertenece a la clase P (Polinomial) si existe un algoritmo polinomial para resolverlo.

Un problema de decisión pertenece a la clase NP (polinomial no-deterministamente) si dada una instancia de SI y evidencia de la misma, puede ser verificada en tiempo polinomial.

Relaciones entre las clases:

 

Problema abierto: ¿Es P = NP? (problema abierto más importante de teoría de la computación)

Ejemplo de problemas NP:

·         Suma de enteros

·         Multiplicación de enteros

·         Árbol generador mínimo

·         Clique máxima

·         Camino mínimo entre un par de nodos

·         Problema del viajante de comercio

·         Conjunto independiente de cardinal máximo

Problema de satisfabilidad (SAT): Dado un conjunto de cláusulas C1,……,Cm formadas por literales basados en las variables booleanas X = {x1,….,x_n}, determinar si hay una asignación de valores de verdad a las variables de X tal que la expresión C1 ^ C2 ^…. ^ C_m sea verdadera.

Clase NP - Otra caracterización

Un problema de decisión está en la clase NP si las instancias de SI son reconocidas por una máquina de Turing no-determinística polinomial.

La clase NP se puede definir como el conjunto de problemas de decisión que se pueden resolver por un algoritmo polinomial no-determinístico.

Lema: Si ∏ es un problema de decisión que pertenece a la clase NP, Entonces ∏ puede ser resuelto por un algoritmo determinístico en tiempo exponencial respecto del tamaño de la entrada.

3.4 PROBLEMAS DEMOSTRABLEMENTE IRRESOLUBLES

Estos se dividen en recursivamente irresolubles y recursivamente resolubles.

3.4.1- Recursivamente irresoluble: Un ejemplo claro es;

PROBLEMA DE LA DETENCIÓN DE LA MT

Problema de la parada o problema de la detención. Este famoso problema (halting problem, en inglés), considerado por el propio Turing, consiste en preguntar si existe un algoritmo para el siguiente problema de decisión: Dada una MT M cualquiera, sobre el alfabeto de cinta Σ, y una cadena w ∈ Σ ∗, ¿se detiene M al procesar la entrada w? El problema universal se puede reducir al problema de la parada. En otros términos, asumiendo la existencia de una MT M que resuelva el problema.

De la parada se puede resolver el problema universal. La gráfica siguiente esboza el razonamiento.

Sea M0w una entrada arbitraria (M y w codifican MT y cadenas sobre Σ, respectivamente). La máquina M0 solamente devuelve la entrada M0w, ya que las entradas para el problema universal y para el problema de la parada coinciden. Puesto que M es capaz de decidir si M se detiene o no con entrada w, se tendría:

Si M no se detiene con entrada w =⇒ M no acepta a w.

Si M se detiene con entrada w =⇒ M procesa w y decide si la acepta o no.

Conclusión: si el problema de la parada fuera decididle, también lo sería el problema universal.

Lo anterior también permite concluir que el lenguaje Lp = {M0w : M se detiene con entrada w} no es recursivo.

3.4.2- Recursivamente Resolubles

Esta clase de problema se puede resolver mediante la aplicación de técnicas sencillas pero ingeniosas y cuyos algoritmos  son los que usa una sencillos. Cabe precisar que están divididos en Soluciones aproximadas iterativas y probabilísticas.

Las características de la recursividad son:

-La recursividad es una característica de los lenguajes de programación que permite que un subprograma se invoque a sí mismo.

- La recursividad es útil para resolver problemas definibles en sus propios términos.

- La recursividad es, en cierta medida, análoga al principio de inducción.

- No existen problemas intrínsecamente recursivos o iterativos; cualquier proceso iterativo puede expresarse de forma recursiva y viceversa.

- La recursividad aunque da lugar a algoritmos más simples y compactos resulta más lenta y consume más recursos al ejecutarse sobre el ordenador.

- Para desarrollar algoritmos recursivos hay que partir del supuesto de que ya existe un algoritmo que resuelve una versión más sencilla del problema. A partir de esta suposición debe hacerse lo siguiente:

1. Identificar Subproblemas atómicos de resolución inmediata (casos base).

2. Descomponer el problema en Subproblemas resolubles mediante el algoritmo pre-existente; la solución de estos Subproblemas debe aproximarnos a los casos base.

3. Probar de manera informal que tanto los casos base como los generales pueden solucionarse con el algoritmo desarrollado.

Un ejemplo sencillo es el cálculo de la factorial de un número:

Factorial de un número, n!

Algoritmo pre-existente: (n-1)! Caso base: 0! = 1!

Subproblemas resolubles mediante el algoritmo pre-existente y que aproximen al caso base: n! = n · (n-1)!   

Prueba informal: Conociendo las dos expresiones anteriores es posible calcular 0!, 1!, 4!, etc.

3.4.2.1- Lógica de Modelos probabilísticos.

Muchos analistas tratan de describir y predecir el comportamiento de los consumidores usando variables observables – regresión, arboles de decisión, etc.  En esta primera parte consideraremos el comportamiento como si fuera “aleatorio”

– Enfoque alternativo: decisiones racionales.

·         Buscamos modelos que nos permitan tomar decisiones.

·         Que nos permitan explicar elementos identificables del comportamiento del consumidor (contar una historia)

·         Que nos permitan hacer inferencia a nivel del individuo (o al menos al nivel de grupos de individuos).

USO:

• Entender patrones de comportamiento a nivel desagregado.

• Hacer predicciones de comportamiento más allá de los datos que observamos.

• Generar benchmarks para la evaluación de estrategias comerciales.

METODOLOGÍA

1)    Determinar el problema de decisión de marketing y la información requerida.

2)    Identificar el comportamiento observable de interés a nivel individual (típicamente denotamos esto como x).

3)    Seleccionar una distribución de probabilidad que caracterice este comportamiento a nivel individual. – Típicamente denotamos esto como f (x|θ). – Consideramos los parámetros de esta distribución como características latentes de nivel individual.

4)    Especificar una distribución para caracterizar la distribución de las características latentes en la población. – Típicamente denotamos esto por g(θ) y le llamamos la distribución de mezcla (o modelo de heterogeneidad).

5)    Derivar la distribución agregada o distribución observable de del comportamiento de interés. 

6)    Estimar los parámetros (de la distribución de mezcla) ajustando la distribución agregada a los datos que observamos.

7)    Usar los resultados de los modelos para resolver el problema de marketing planteado.

MODELOS A CONSIDERAR

-          Modelo de duración en tiempo discreto –  Ejemplo Proyección de tasas de retención de clientes:

Adquirimos un cliente: ¿Por cuantos periodos va a este cliente a estar afiliado a la compañía?

Un usuario baja una aplicación para el i-phone.  ¿Por cuantos periodos la va a usar?  Adquirimos un cliente en un banco. ¿Por cuantos periodos permanecerá con el banco?

Un cliente compra un teléfono / plan de internet / consola de video juegos / sistema operativo. ¿Por cuantos periodos lo va a usar?

-           Modelo de duración en tiempo continuo – Ejemplo Predicción de adopción de nuevos productos

-          Modelo de conteo – Ejemplo Estimación de exposición publicitaria.

-           Modelo de elección – Ejemplo Respuesta a campaña de marketing directo.

Problemas P y NP Completos – Elaborado por John Faber Patiño

La relación entre las clases de complejidad P y NP es una pregunta que aún no se ha podido responder por la teoría de la complejidad computacional. En esencia, la pregunta ¿es P = NP ? significa: si es posible "verificar" rápidamente soluciones positivas a un problema del tipo SI/NO (donde "rápidamente" significa "en tiempo polinómico"), ¿es que entonces también se pueden "obtener" las respuestas rápidamente?

Los recursos comúnmente estudiados en complejidad computacional son:

–     El tiempo: mediante una aproximación al número de pasos de ejecución que un algoritmo emplea para resolver un problema.

–     El espacio: mediante una aproximación a la cantidad de memoria utilizada para resolver el problema.

Los problemas se clasifican en conjuntos o clases de complejidad (L, NL, P, PCompleto, NP, NP-Completo, NP Duro...)

EJEMPLO

Consideremos, por ejemplo, el Problema de la suma de subconjuntos, que es un ejemplo de un problema fácil de verificar, pero cuya respuesta se cree (pero no ha sido demostrado) es difícil de calcular/hallar. Dado un conjunto de números enteros, ¿existe un subconjunto no vacío de ellos donde la suma de sus elementos es igual a 0? por ejemplo, ¿existe un subconjunto del conjunto {−2, −3, 15, 14, 7, −10} tal que la suma de sus elementos sea 0?

La respuesta es SI, si bien puede llevar algún tiempo encontrar un subconjunto que satisface el requerimiento, según cual sea el tamaño del conjunto y subconjunto. Por otra parte, si alguien afirma que la respuesta es: «sí, porque la suma de {−2, −3, −10, 15} es igual a cero», entonces lo podemos comprobar en forma muy rápida y mediante unas pocas cuentas. Verificar que la suma del subconjunto es cero es un proceso mucho más rápido que encontrar el subconjunto. La información necesaria para verificar un resultado positivo/afirmativo es llamada un certificado. Por lo que podemos concluir que dado los certificados apropiados, es posible verificar rápidamente las respuestas afirmativas de nuestro problema (en tiempo polinomial) y es ésta la razón por la que el problema se encuentra en NP. Una respuesta a la pregunta P = NP sería determinar si en problemas del tipo SUMA-SUBCONJUNTO es tan fácil hallar la solución como verificarla. Si se encuentra que P no es igual a NP, ello significa que algunos problemas NP serían significativamente más difíciles de hallar su solución que verificar la misma. La respuesta sería aplicable a todo este tipo de problemas, no solo al ejemplo específico de SUMA-SUBCONJUNTO.

La restricción a problemas de tipo SI/NO realmente no es importante; aún si se permiten respuestas más complicadas, el problema resultante resulta equivalente (o sea si FP = FNP).

Contexto del problema

La relación entre las clases de complejidad P y NP es estudiada por la teoría de la complejidad computacional, la parte de la teoría de la computación que trata de los recursos requeridos durante el cálculo para resolver un problema dado. Los recursos más usuales son tiempo (¿cuántos pasos son necesarios para resolver un problema?) y espacio (¿cuánta memoria es necesaria para resolver un problema?).

En este tipo de análisis, se requiere un modelo de la computadora para la que desea estudiar el requerimiento en términos de tiempo. Típicamente, dichos modelos suponen que la computadora es determinista (dado el estado actual de la computadora y las variables de entrada, existe una única acción posible que la computadora puede tomar) y secuencial (realiza las acciones una después de la otra). Estas suposiciones son adecuadas para representar el comportamiento de todas las computadoras existentes, aún incluye a las máquinas con computación en paralelo.

En esta teoría, la clase P consiste de todos aquellos problemas de decisión que pueden ser resueltos en una máquina determinista secuencial en un período de tiempo polinomial en proporción a los datos de entrada. En la teoría de complejidad computacional, la clase P es una de las más importantes; la clase NP consiste de todos aquellos problemas de decisión cuyas soluciones positivas/afirmativas pueden ser verificadas en tiempo polinómico a partir de ser alimentadas con la información apropiada, o en forma equivalente, cuya solución puede ser hallada en tiempo polinómico en una máquina no determinista. Por lo tanto, la principal pregunta aún sin respuesta en la teoría de la computación está referida a la relación entre estas dos clases:

¿Es P igual a NP?  En una encuesta realizada en el 2002 entre 100 investigadores, 61 creían que la respuesta era NO, 9 creían que la respuesta era SI, 22 no estaban seguros, y 8 creían que la pregunta podía ser independiente de los axiomas actualmente aceptados, y por lo tanto imposible de demostrar por el SI o por el NO2.

Definiciones formales

Más precisamente, un problema de decisión es un problema que especifica una cadena de caracteres de datos de entrada y requiere como solución una respuesta por el SI o por el NO. Si existe un algoritmo (por ejemplo una máquina de Turing, o un programa en lenguajes Lisp o Pascal con memoria irrestricta) que es capaz de entregar la respuesta correcta para toda cadena de datos de longitud n en a lo sumo c \cdot n^k pasos, donde k y c son constantes independientes del conjunto de datos, entonces se dice que el problema puede ser resuelto en tiempo polinómico y lo clasificamos como perteneciente a la clase P. En forma intuitiva, consideramos que los problemas contenidos en P son aquellos que pueden ser resueltos en forma razonablemente rápida.

P suele ser la clase de problemas computacionales que son “eficientemente resolubles” o “tratables”, aunque haya clases potencialmente más grandes que también se consideran tratables, como RP Y BPP. Aunque también existen problemas en P que no son tratables en términos prácticos; por ejemplo, unos requieren al menos n^{1000000} operaciones.

En forma intuitiva, se puede pensar que NP es un problema de decisión que es difícil de resolver si no se posee ningún otro dato o información adicional. Sin embargo, si se recibe la información adicional llamada un certificado, entonces el problema puede ser resuelto fácilmente. Por ejemplo, si se nos da el número 323 y se nos pregunta si 323 es un número factorizable, sin darnos ningún dato o información adicional, deberíamos analizar todos los números enteros positivos mayores que 2 pero menores que 323 para estudiar si alguno de ellos divide exactamente al 323. Sin embargo, si se nos da el número 17, podemos dividir 323 por 17 y rápidamente verificar que 323 es factorizable. El número 17 es llamado un certificado. El proceso de división para verificar que 323 es factorizable es en esencia una máquina Turing y en este caso es denominado el verificador para 323. Técnicamente se dice que el problema es fácil si se puede resolver en tiempo polinómico y que es difícil si se resuelve en tiempo exponencial. Formalmente, se define NP como un conjunto de lenguajes que satisfacen ciertas condiciones.

Sea L un lenguaje definido sobre un alfabeto finito, \Sigma.

Si existe una relación binaria R\subset\Sigma^{*}\times\Sigma^{*} y un entero positivo k tal que para todo x\in\Sigma^{*}, se satisfacen las siguientes condiciones:

(i) x\in L \Leftrightarrow\exists y\in\Sigma^{*} tal que (x,y)\in R\; y \left|y\right|\in\; O(\left|x\right|^{k}).

(ii) El lenguaje L_{R}=\{ x\# y:(x,y)\in R\} en \Sigma\cup\{\#\} es decible.

Entonces, la máquina de Turing que decide L_{R} (que la llamaremos V) es llamada el Verificador para L y y es llamado el Certificado de membresía de x en L.

Finalmente, L se encuentra en NP "si y solo si" V corre en tiempo polinómico.

Ejemplo.

Sea \mathit{COMPOSITE} = \{x\in N:x=pq \;\text{para enteros}\; p, q > 1 \}

R = \{(x,y)\in N\times N: 1<y<x\; ; \;y\; \text{divide a}\; x\}

Claramente, la pregunta de si un dado x es factorizable es equivalente a la pregunta sobre si x es un miembro de \mathit{COMPOSITE}. De hecho, se puede demostrar fácilmente que \mathit{COMPOSITE}\in\mathbf{NP} si se verifica que \mathit{COMPOSITE} satisface la condición indicada previamente.

•           Un algoritmo eficiente es un algoritmo de complejidad polinomial.

•           Un problema está bien resuelto si se conocen algoritmos eficientes para resolverlo.

•           El objetivo es clasificar los problemas según su complejidad.

•           Un problema de decisión es un problema cuya respuesta es sí o no

•           La clasificación y el estudio de teoría de complejidad se hace para problemas de decisión.

La clase P

P es conocido por contener muchos problemas naturales, incluyendo las versiones de decisión de programa lineal, cálculo del máximo común divisor, y encontrar una correspondencia máxima.

Problemas notables en P

Algunos problemas naturales son completos para P, incluyendo la conectividad (o la accesibilidad) en grafos no dirigidos.

Una generalización de P es NP, que es la clase de lenguajes decidibles en tiempo polinómico sobre una máquina de Turing no determinista. De forma trivial, tenemos que P es un subconjunto de NP. Aunque no está demostrado, la mayor parte de los expertos creen que esto es un subconjunto estricto.

Aquí, EXPTIME es la clase de problemas resolubles en tiempo exponencial. De todas las clases mostradas arriba, sólo se conocen dos contenciones estrictas:

P estrictamente está contenido en EXPTIME.

L estrictamente está contenida en PSPACE.

Los problemas más difíciles en P son los problemas P-completos

Otra generalización de P es el Tiempo polinómico No uniforme (P/Poly)[1]. Si un problema está en P/poly, entonces puede solucionarse en un tiempo polinomial determinado el cual, dado una cadena, este solo depende de la longitud de la entrada. A diferencia de NP, no se comprueban las cadenas defectuosas que entran en la máquina de Turing, puesto que no es un verificador.

P/poly es una clase grande que contiene casi todos los algoritmos prácticos, incluyendo todo el BPP. Si esta contiene a NP, la jerarquía polinomial se colapsa con el segundo nivel. Por otra parte, esta también contiene algunos algoritmos poco prácticos, incluyendo algunos problemas no decidibles.

Propiedades

Los algoritmos de tiempo polinómico son cerrados respecto a la composición. Intuitivamente, esto quiere decir que si uno escribe una función con un determinado tiempo polinómico y consideramos que las llamadas a esa misma función son constantes y, de tiempo polinómico, entonces el algoritmo completo es de tiempo polinómico. Esto es uno de los motivos principales por los que P se considera una máquina independiente; algunos rasgos de esta máquina, como el acceso aleatorio, es que puede calcular en tiempo polinómico el tiempo polinómico del algoritmo principal reduciéndolo a una máquina más básica.

Las pruebas existenciales de algoritmos de tiempo polinómico

Se conoce que algunos problemas son resolubles en tiempo polinómico, pero no se conoce ningún algoritmo concreto para solucionarlos. Por ejemplo, el teorema Robertson-Seymour garantiza que hay una lista finita de los menores permitidos que compone (por ejemplo) el conjunto de los grafos que pueden ser integrados sobre un toroide; además, Robertson y Seymour demostraron que hay una complejidad O (n3) en el algoritmo para determinar si un grafo tiene un grafo incluido. Esto nos da una prueba no constructiva de que hay un algoritmo de tiempo polinómico para determinar si dado un grafo puede ser integrado sobre un toroide, a pesar de no conocerse ningún algoritmo concreto para este problema.

Ejemplos

·         Camino Mínimo: encontrar el camino mínimo desde un vértice origen al resto de los vértices.

·         Ciclo Euleriano: Encontrar un ciclo que pase por cada arco de un grafo una única vez.

Clase NP-Completo

Para abordar la pregunta de si P=NP, el concepto de la completitud de NP es muy útil. Informalmente, los problemas de NP-completos son los problemas más difíciles de NP, en el sentido de que son los más probables de no encontrarse en P. Los problemas de NP-completos son esos problemas NP-duros que están contenidos en NP, donde los problemas NP-duros son estos que cualquier problema en NP puede ser reducido a complejidad polinomial. Por ejemplo, la decisión del Problema del viajante de comercio es NP-completo, así que cualquier caso de cualquier problema en NP puede ser transformado mecánicamente en un caso del Problema del viajante de comercio, de complejidad polinomial. El Problema del viajante de comercio es de los muchos problemas NP-completos existentes. Si cualquier problema NP-completo estuviera en P, entonces indicaría que P=NP. Desafortunadamente, se sabe que muchos problemas importantes son NP-completos y a fecha de 2008, no se conoce ningún algoritmo rápido para ninguno de ellos. Basándonos solo en esta idea, no es obvio que exista un problema NP-completo.

Un problema NP-completo trivial e ideado, se puede formular como: Dada una descripción de una máquina de Turing M que se detiene en tiempo polinómico, ¿existe una entrada de tamaño polinómico que M acepte? Es NP porque, dada una entrada, es simple comprobar si M acepta o no la entrada simulando M, es NP-duros porque el verificador para cualquier caso particular de un problema en NP puede ser codificado como una maquina M de tiempo polinomial que toma la solución para ser verificada como entrada. Entonces la pregunta de si el caso es o no un caso, está determinado por la existencia de una entrada valida. El primer problema natural que se demostró ser NP-completo fue el Problema booleano de satisfacibilidad.

Este resultado es conocido como el teorema de Cook-Levin; su prueba de que la satisfacibilidad es NP-completo contiene los detalles técnicos sobre máquinas de Turing y como se relacionan con la definición de NP. Sin embargo, después se demostró que el problema era NP-completo, la prueba por reducción, proporcionó una manera más simple de demostrar que muchos otros problemas están en esta clase. Así, una clase extensa de problemas aparentemente sin relación es reducible a otra, y son en este sentido el mismo problema.

Como ejemplo de un problema NP-completo encontramos el problema de la suma de subconjuntos que se puede enunciar como sigue: dado un conjunto S de enteros, ¿existe un subconjunto no vacío de S cuyos elementos sumen cero? Es fácil verificar si una respuesta es correcta, pero no se conoce mejor solución que explorar todos los 2n-1  subconjuntos posibles hasta encontrar uno que cumpla con la condición.

TEOREMA DE COOK

En teoría de la complejidad computacional, el Teorema de Cook establece lo siguiente:

•           El Problema de satisfacibilidad booleana (SAT) es NP-completo.

Lo cual quiere decir que

Un problema de decisión pertenece a NP si puede ser resuelto en una Máquina de Turing indeterminista en tiempo polinomio.

Se dice que un problema de decisión es NP-completo si pertenece a NP y si todo problema perteneciente a NP puede ser reducido a él utilizando una transformación polifónica.

Una instancia del problema SAT es una expresión booleana que combina variables booleanas con operadores booleanos. Una expresión es satisfacible si existe una asignación de valores booleanos para las variables de esa expresión que hace que la expresión completa sea verdadera.

EJEMPLOS:

Un problema interesante en teoría de grafos es el de isomorfismo de grafos: Dos grafos son isomorfos si se puede transformar uno en el otro simplemente renombrando los vértices. De los dos problemas siguientes:

·         Isomorfismo de grafos: ¿Es el grafo G1 isomorfo al grafo G2?

·         Isomorfismo de subgrafos: ¿Es el grafo G1 isomorfo a un subgrafo del grafo G2?

Se sospecha que el problema de isomorfismo de grafos no está ni en P ni en NP-completo, aunque está en NP. Se trata de un problema difícil, pero no tanto como para estar en NP-completo.

La forma más sencilla de demostrar que un nuevo problema es NP-completo es primero demostrar que está en NP y luego transformar en tiempo polinómico un problema que ya esté en NP-completo a éste. Para ello resulta útil conocer algunos de los problemas para los que existe prueba de pertenencia a NP-completo. Algunos de los más famosos son:

·         Problema de satisfacibilidad booleana (SAT)

·         Problema de la mochila (knapsack)

·         Problema del ciclo hamiltoniano

·         Problema del vendedor viajero

·         Problema de la clique

Conclusiones

• El agente inteligente en este caso es la base de datos que permita la información permanente y genere resultados de pronósticos respecto a los posibles resultados.
• Un software como la base de datos ACCESS como en este caso puede desarrollar la tarea requerida en este trabajo grupal.
• La inteligencia artificial se va a masificar en usos y aplicaciones y vamos a poder hacer cosas que antes ni siquiera pensábamos que fueran posibles. 
• La aplicabilidad de las técnicas computacionales, nos lleva a comprender y afianzar los conocimientos de una manera teórica, logrando 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.
• Los modelos recursivos nos llevan a soluciones aproximadas ya sea por iteración o modelos probabilísticos, se parte de la solución de un problema sencillo conocido y se obtiene una generalización de orden n.
• La eficiencia de los algoritmos permite comparar diferentes técnicas y software utilizados para la solución de problemas específicos, sin lugar a duda permite optimizar recursos y desechar algoritmos con procedimientos obsoletos o que no son lo suficientemente eficientes en el uso de recursos computacionales y en el tiempo en obtener las respuestas esperadas por el usuario final.

Referencias Bibliográficas

Ø  Modulo: Análisis de Inteligencia Artificial. UNAD.

Ø  Hipola, Pedro. 1999. Agentes Inteligentes: Definición y Tipología. Los agentes de Información. [En línea].  Abril 1999. Universidad de Granada. Recuperado de: http://www.elprofesionaldelainformacion.com/contenidos/1999/abril/agentes_inteligentes_definicion_y_tipologia_los_agentes_de_informacion.html http://www.rvazquez.org/Misitio/Materialbi_files/objetodeestudio2crnew.pdf

Ø  Biografías y vidas- la enciclopedia biográfica en línea http://www.biografiasyvidas.com/biografia/l/llull.htm

Ø  Biografías y vidas- la enciclopedia biográfica en línea http://www.biografiasyvidas.com/biografia/t/turing.htm

Avila, Mauricio. 2013. Calidad de Software-caja negra. . [En línea]. Octubre 22 de 2013. Formato PDF. Recuperado de:

https://www.youtube.com/watch?v=lVEIzJGqJcM

Biografías y vidas- la enciclopedia biográfica en línea http://www.biografiasyvidas.com/biografia/l/llull.htm

Biografías y vidas- la enciclopedia biográfica en línea http://www.biografiasyvidas.com/biografia/t/turing.htm

Fernandez, Carmen. Villena, Julio. Pruebas de Programas. [En línea]. Formato PDF. Recuperado de: http://www.it.uc3m.es/ttrd/material/05-pruebas-de-programas.pdf

Hipola, Pedro. 1999. Agentes Inteligentes: Definición y Tipología. Los agentes de Información. [En línea].  Abril 1999. Universidad de Granada. Recuperado: de: http://www.elprofesionaldelainformacion.com/contenidos/1999/abril/agentes_inteligentes_definicion_y_tipologia_los_agentes_de_informacion.html

Mayordomo, Elvira. 2013. Problemas intratables: Los NP-Dificiles. [En línea]. Mayo 15 de 2013. Universidad de Zaragoza, España. Formato PDF. Recuperado de: http://webdiis.unizar.es/asignaturas/APD/NPcompletosI.pdf

Vasquez, R.    Control de Robots. [En línea]. Formato pdf. Recuperado de:

 http://www.rvazquez.org/Misitio/Materialbi_files/objetodeestudio2crnew.pdf

WikiMedia Org.. Eficiencia Algoritmica. [En línea]. Formato HTML. Recuperado de:

https://es.wikipedia.org/wiki/Eficiencia_Algor%C3%ADtmica

WikiMedia Org.. Teoria de la Complejidad Computacional. [En línea]. Formato HTML. Recuperado de:

https://es.wikipedia.org/wiki/Teor%C3%ADa_de_la_complejidad_computacional

WikiMedia Org. Clases de Complejidad P y NP. [En línea]. Formato HTML. Recuperado de: https://es.wikipedia.org/wiki/Clases_de_complejidad_P_y_NP