Algoritmo de inteligencia artificial

Seguramente de pequeño has jugado alguna vez al juego de las 20 preguntas, ya sabes, uno piensa en un objeto y otro trata de adivinarlo haciendo preguntas a las que sólo se puede responder “sí” o “no”. Si lo adivinas con un máximo de 20 preguntas has ganado.

20Q es una versión web de este juego utilizando inteligencia artificial. En este caso, tu compañero de juegos es virtual, piensas en un objeto y será el ordenador quien debe adivinar el objeto mediante preguntas. Si el ordenador consigue adivinarlo con un máximo de 20 preguntas, ha ganado. Si necesita más de 20 preguntas, habrás vencido al ordenador.

http://www.20q.net/

Si has estado jugando con 20Q seguro que te estarás preguntando ¿Cómo es posible?. Puedo asegurarte que no es un truco de magia, es inteligencia artificial.


Habrás oído hablar muchas veces de inteligencia artificial, pero ¿Qué es inteligencia artificial? La inteligencia artificial no es algo nuevo. Este término tiene su origen en 1956 y podríamos definirlo como “la ciencia que se encarga del estudio de las facultades mentales mediante el uso de modelos computacionales”.


20Q es, en realidad, una aplicación basada en una red neuronal artificial, que es una de las ramas de estudio de la inteligencia artificial. Si comprendemos el funcionamiento de una red neuronal, comprenderemos el funcionamiento de 20Q.


Las redes neuronales son un modelo de aprendizaje y procesamiento de información automático inspirado en el sistema nervioso biológico.



Los cerebros humanos están compuestos por decenas de billones de neuronas conectadas mediante sinopsis, estas conexiones pueden intensificarse o atenuarse dependiendo de una serie de factores. La neurona, dependiendo del estado global de sus conexiones, toma un nivel de activación. Luego, propagará esta información a todas las neuronas con las que esté conectada.


En las redes neuronales artificiales las neuronas se modelan mediante unidades de proceso, que están unidas mediante conexiones ponderadas. Cada conexión tiene un peso asociado, que equivale a la fuerza de la conexión. La función de red es la encargada de calcular la entrada global, que generalmente se calcula mediante una suma ponderada de todas las entradas recibidas. La función de activación, generalmente más compleja que la función de red, se encarga de determinar el nivel de activación basándose en la entrada global. Este valor de activación será el que se transmitirá a todas las unidades con las que esté conectada.

Para diseñar una red neuronal artificial debemos establecer las conexiones entre unidades y los pesos de estas. Lo normal es tener unidades en forma de capas: una capa de entrada, que actuará como buffer de entrada; una capa de salida, que actuará como buffer de salida y capas ocultas que serán las encargadas de extraer, procesar y memorizar la información.



Una de las características más importantes de las redes neuronales es el aprendizaje. El aprendizaje en las redes neuronales biológicas se produce mediante el ajuste de la efectividad de la sinopsis, de esta manera cambia la influencia que unas neuronas ejercen sobre otras. En las redes neuronales artificiales el aprendizaje consiste en el ajuste de los pesos en las conexiones.


Inicialmente, habremos establecido unos pesos para las conexiones de nuestra red neuronal artificial, pero a través de entrenamiento podemos conseguir que estos pesos cambien. En nuestro caso, entrenamos a 20Q cada vez que jugamos. Si para el mismo objeto repetidas veces obtiene la misma respuesta, esa conexión se irá reforzando y terminará reconociendo esa respuesta como válida. Por esta razón, cuando hemos acabado el juego nos dice las contradicciones que ha encontrado, mostrando para esa pregunta la respuesta que tiene más peso hasta el momento (que no coincide con lo que nosotros hemos contestado). Sin embargo, nuestra respuesta ha contribuido a aumentar el peso de esa respuesta.

Otras aplicaciones que podemos distimguir podrian estar dadas por programas programados bajo ciertos patrones de respuesta con el objetivo de poder interactuar con una persona y brindar muchas veces soluciones, la logica se basa en hallar respuestas a las preguntas de quien pregunta
“Mantén una conversación inteligente con tu PC”
Dr. Abuse es un programa de Inteligencia Artificial (AI) que demuestra apariencia humana, basado en el famoso programa Eliza de Joseph Weizenbaum. Permite mantener una conversación divertida e inteligente con el ordenador. Dr. Abuse ha sido entrenado en cientos de conversaciones con usuarios humanos o robóticos a través de internet y otros medios.

Al utilizar este programa quedará gratamente sorprendido por la agudeza de sus respuestas y llegará a dudar si realmente las máquinas piensan o no. Pero no sólo para contestar está programado, ya que también puede realizar funciones de mayordomo (abrir programas, navegar, enviar correo, conversar con otros robots, realizar cálculos…)

Dr. Abuse incluye, entre otras cosas, un “Mad Doctor” bastante peculiar, una potente base de datos de respuestas, una potente base de datos de temas que tratar y un módulo de comprensión de lenguaje natural.

Además del texto escrito, también habla en viva voz las frases. Para que el Dr. Abuse reproduzca las frases necesitarás tener instalado Microsoft Speech API 4.0 y Microsoft Text-to-Speech Engine 4.0. algunas versiones de Windows ya los tienen instalados por defecto, como Windows 2000, por lo que puede que no necesites instalarlos.

http://www.mediafire.com/download.php?wwyrnd2iy2j
descargalo aca

gracias por toda la atencion

Un poco de blues...

Algoritmo de Bellman ford

Para poder tomar el tema de esta clase de algoritmos, es necesario poder prestar atención a lo que se denomina como, TEORIA DE GRAFOS, la misma nos enseñara a manipular el orden de distintos procesos a efectuar.

En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (edges en inglés) que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).


mas info en...http://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafos

Para comenzar debemos tener bien definido que el algoritmo de Bellman-Ford (algoritmo de Bell-End-Ford), genera el camino más corto en un Grafo dirigido ponderado (en el que el peso de alguna de las aristas puede ser negativo).

Si entendemos bien dicho concepto, entonces podemos decir que el algoritmo de Dijkstra resuelve este mismo problema en un tiempo menor, pero requiere que los pesos de las aristas no sean negativos. Por lo que el Algoritmo Bellman-Ford normalmente se utiliza cuando hay aristas con peso negativo. Este algoritmo fue desarrollado por Richard Bellman, Samuel End y Lester Ford.


Este tipo de algoritmo eran originales de ruteo de la ARPANET. Su modo de funcionamiento es el siguiente:

1. Cada ruteador mantiene una tabla (un vector) que almacena las mejores distancias conocidas a cada destino y las líneas a usar para cada destino. Se actualizan las tablas intercambiando información con los vecinos.
2. La tabla de un ruteador almacena una entrada para cada uno de los ruteadores en la subred (los ruteadores son los índices). Las entradas almacenan la línea preferida de salida y una estimación del tiempo o la distancia al destino. Se pueden usar métricas distintas (saltos, retrasos, etc.).
3. Cada ruteador tiene que medir las distancias a sus vecinos. Por ejemplo, si la métrica es el retraso, el ruteador la puede medir usando paquetes de eco.
4. Cada T msegs los ruteadores intercambian sus tablas con sus vecinos. Un ruteador usa lastablas de sus vecinos y sus mediciones de las distancias a sus vecinos para calcular una nueva tabla.

A modo de finalizar, la siguiente imagen, muestra el analisis grafico de un grafo aplicado en los canales de Venecia

Algoritmo de Cadenas Polacas y Rotación

"CERATI -UNO ENTRE MIL-" algo de buena música como siempre...

El método de cadenas polacas y rotación, tendra por objetivo entregarnos datos de salida con una característica especial, los mismos podran ser reversibles de una manera única, que solo nosotros podremos determinar, esto hará referencia a una llave lógica que nos permitirá darle un uso especifico a este algoritmo, será usado como un método alternativo de encriptación de seguridad para datos.

Como ya definimos anteriormente, un algoritmo se encargara mediante un método especifico transformar una entrada de datos en una salida, en forma iterativa casi en la mayoria de los casos, para ello debemos crear reglas especificas a este algoritmo, en este el algoritmo utilizara un operador y un operante

OPERADOR: será un valor numérico en un medio de recursos concretos (numeros naturales, reales, imaginarios, etc)

OPERADOR: Es una función de transformación en la relacion de operantes que pueden ser clasicos o particulares (estos ultimos tendran las mismas atribuciones de los clasicos pero con simbolos modificados o personalizados para un entendimiento personal) + - / *

Principio 1

Relacion del operador con el operante

Es una operacion secuencial consecutiva de pares, ejemplo:

ℓ = (+, -)

A = (7, 4, 1)

R (ℓ, A) = R (+, -) (7, 4, 1)

R(+, -)(7, 4, 1) = 4

Principio 2

Algoritmo de la cadena polaca

(+, -)(7, 4, 1) donde se repartira los signos de la siguiente forma

7-4+1 = 4

a travez de la rotacion de los signos, obtenemos el resultado, definiendo ademas asi, que una cadena polaca posee una notacion prefija en sus procesos

la aplicación mas directa a este tipo de procesos, podemos mencionarla por ejemplo, en la encriptación de información que podria requerir de un algoritmo de cadena polaca y el uso de llaves logicas tras la construccion de matrices numericas que apliquen esa definicion de cadena polaca


vamos a utilizar a continuación un ejemplo aplicando un sistema de encriptacion o criptosistema

"Un Criptosistema se define como la quíntupla (m,C,K,E,D), donde:

* m representa el conjunto de todos los mensajes sin cifrar (texto plano) que pueden ser enviados.
* C Representa el conjunto de todos los posibles mensajes cifrados, o criptogramas.
* K representa el conjunto de claves que se pueden emplear en el Criptosistema UNA LLAVE LOGICA DE NUESTRA CADENA POLACA POR EJEMPLO.
* E es el conjunto de transformaciones de cifrado o familia de funciones que se aplica a cada elemento de m para obtener un elemento de C. Existe una transformación diferente Ek para cada valor posible de la clave K.
* D es el conjunto de transformaciones de descifrado, análogo a E.

Todo Criptosistema cumple la condición Dk(Ek(m))=m es decir, que si se tiene un mensaje m, se cifra empleando la clave K y luego se descifra empleando la misma clave, se obtiene el mensaje original m." (1)

Existen dos tipos fundamentales de Criptosistemas utilizados para cifrar datos e información digital y ser enviados posteriormente después por medios de transmisión libre.

1. Simétricos o de clave privada: se emplea la misma clave K para cifrar y descifrar, por lo tanto el emisor y el receptor deben poseer la clave. El mayor inconveniente que presentan es que se debe contar con un canal seguro para la transmisión de dicha clave.
2. Asimétricos o de llave pública:se emplea una doble clave conocidas como Kp (clave privada) y KP (clave Pública). Una de ellas es utilizada para la transformación E de cifrado y la otra para el descifrado D. En muchos de los sistemas existentes estas clave son intercambiables, es decir que si empleamos una para cifrar se utiliza la otra para descifrar y viceversa.

Los sistemas asimétricos deben cumplir con la condición que la clave Publica (al ser conocida y sólo utilizada para cifrar) no debe permitir calcular la privada. Como puede observarse este sistema permite intercambiar claves en un canal inseguro de transmisión ya que lo único que se envía es la clave pública.

Los algoritmos asimétricos emplean claves de longitud mayor a los simétricos. Así, por ejemplo, suele considerarse segura una clave de 128 bits para estos últimos pero se recomienda claves de 1024 bits (como mínimo) para los algoritmos asimétricos. Esto permite que los algoritmos simétricos sean considerablemente más rápidos que los asimétricos.

En la práctica actualmente se emplea una combinación de ambos sistemas ya que los asimétricos son computacionalmente más costosos (mayor tiempo de cifrado). Para realizar dicha combinación se cifra el mensaje m con un sistema simétrico y luego se encripta la clave K utilizada en el algoritmo simétrico (generalmente más corta que el mensaje) con un sistema asimétrico.

Después de estos Criptosistemas modernos podemos encontrar otros no menos importantes utilizados desde siempre para cifrar mensajes de menos importancia o domésticos, y que han ido perdiendo su eficacia por ser fácilmente criptoanalizables y por tanto "reventables". Cada uno de los algoritmos clásicos descriptos a continuación utilizan la misma clave K para cifrar y descifrar el mensaje.

Transposición

Son aquellos que alteran el orden de los caracteres dentro del mensaje a cifrar. El algoritmo de transposición más común consiste en colocar el texto en una tabla de n columnas. El texto cifrado serán los caracteres dados por columna (de arriba hacia abajo) con una clave K consistente en el orden en que se leen las columnas.

Ejemplo: Si n = 3 columnas, la llave logica K es (3,1,2) y el mensaje a cifrar "SEGURIDAD INFORMATICA".



El mensaje cifrado será: " GIDNRTASUD FMIERAIOAC "

Algortimos, el algoritmo de Solin

OPETH "Hopes Leaves"

Bueno, vamos a dar inicio (acompañados de algo de buena musica) a este material de investigacion respecto a los algoritmos, primeramente, definamos el termino, Algoritmo; En matemáticas, ciencias de la computación y disciplinas relacionadas, un algoritmo (del griego y latín, dixit algorithmus y éste a su vez del matemático persa Al Juarismi ) es un conjunto preescrito de instrucciones o reglas bien definidas, ordenadas y finitas que permite realizar una actividad mediante pasos sucesivos que no generen dudas a quien deba realizar dicha actividad. Dados un estado inicial y una entrada, siguiendo los pasos sucesivos se llega a un estado final y se obtiene una solución. Los algoritmos son el objeto de estudio de la algoritmia.



En la vida cotidiana, se emplean algoritmos frecuentemente para resolver problemas. Algunos ejemplos son los manuales de usuario, que muestran algoritmos para usar un aparato, o las instrucciones que recibe un trabajador por parte de su patrón. Algunos ejemplos en matemática son el algoritmo de la división para calcular el cociente de dos números, el algoritmo de Euclides para obtener el máximo común divisor de dos enteros positivos, o el método de Gauss para resolver un sistema lineal de ecuaciones.





Teoria de grafos en general

La teoría de grafos ayudará a resolver problemas que se puedan representar mediante una red o grafo: camino mínimo, inventarios, etc.
La Teoría de Grafos proporciona algoritmos eficientes para resolver problemas en distintos campos de la ciencia.
La eficiencia puede medirse en función de:
i) La capacidad de almacenamiento requerida.
ii) El tiempo de ejecución: complejidad.
La complejidad depende del número de operaciones elementales f(n) y de la dimensión del problema n.
Damos, a continuación una serie de definiciones.
Definición 1.1. Un grafo G es un triple conjunto (V (G); A(G); I(G)) donde:
V (G) es un conjunto cuyos elementos son llamados vértices.
A(G) es otro conjunto cuyos elementos son llamados aristas o arcos.
I(G) es una relación (la relación de incidencia), que le asocia a cada arista a∈A(G) dos vértices, llamados los extremos de a.

Los arboles de grafos de esta manera son un grafo en el que existe un único nodo desde el que se puede acceder a todos los demás y cada nodo tiene un único predecesor, excepto el primero, que no tiene ninguno. También podemos definir un árbol como:

- Un grafo conexo y sin ciclos.

- Un grafo sin ciclos y con n-1 aristas, siendo n el número de vértices.

Un árbol consta de un nodo raíz del que vamos a partir, de manera que con los restantes nodos se puedan formar conjuntos disjuntos de nodos de forma que cada subconjunto sea a su vez un árbol. En un árbol todo par de vértices se encuentra unido mediante una cadena y sólo una. Los árboles son estructuras de tipo jerárquico.



El algoritmo de Solin

Una vez definidos estos conceptos, ya podemos definir lo que representará nuestro algoritmo de Solin, Este algoritmo obtiene el árbol minimal de un grafo mediante la representación matricial, matriz de coste, del grafo. Consta de los pasos siguientes:

1) Marcamos el elemento de valor mínimo. En el caso de que existan varios, tomamos uno cualquiera. Se elimina la columna que posea el valor marcado y marcamos la fila correspondiente a la columna eliminada.

2) Del conjunto de elementos de las filas marcadas y que no hayan sido eliminados, tomamos aquel de valor mínimo y lo marcamos. Se elimina la columna que posea este valor marcado.
3) Reiteramos el proceso desde el punto 2) hasta que no podamos seleccionar más valores.

Ejercicio de prueba: Determinaremos con el siguiente grafo, el árbol minimal que podamos hallar usando el algoritmo indicado de Solin



La matriz asociada al grafo es:



Siguiendo los pasos del algoritmo llegamos a la matriz final:



En la matriz anterior, la matriz columna recoge el orden de los pasos que se han seguido para obtener la matriz definitiva:



La matriz anterior reprensentada gráficamente es:



Asi tenemos el resultado de nuestro arbol utilizando el metodo algoritmico, el mismo puede tener diversas aplicaciones en una investigación operativa mas avanzada, ademas del método presente, podemos denotar el método de kruskal. que de igual manera, buscara hacer del grafo un arbol minimal.