Matriz de adyacencia:

Un grafo se puede representar fácilmente mediante una matriz. Inclusive, es la forma mas sencilla de representarlo. A esta matriz se le denomina matriz de adyacencia. Esta matriz consiste basicamente en un arreglo bidimensional de tamaño n x n, donde n es la maxima cantidad de nodos en el grafo. Cada casilla de la matriz se carga con valores verdadero (v) o falso (f) en caso de que posean un camino de un nodo (fila) con otro (columna9. En caso de los grafos no dirigidos la matriz sera simetrica. Sin embargo, esto no ocurre en los digrafos, donde se considera la direccion de cada uno d elos arcos. Para el caso de los grafos ponderados, la matriz podra ser cargada con el peso asociado a cada uno de los arcos. La ventaja principal de la representación de grafos mediante una matriz de adyacencia es su simplicidad, dado que facilita las operaciones que puedan realizarse sobre el grafo.

En teoría de la complejidad computacional, la clase de complejidad NP-completo es el subconjunto de los problemas de decisión en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP-completo. Se puede decir que los problemas de NP-completo son los problemas más difíciles de NP y muy probablemente no formen parte de la clase de complejidad P. La razón es que de tenerse una solución polinómica para un problema NP-completo, todos los problemas de NP tendrían también una solución en tiempo polinómico. Si se demostrase que un problema NP-completo, llamémoslo A, no se pudiese resolver en tiempo polinómico, el resto de los problemas NP-completos tampoco se podrían resolver en tiempo polinómico. Esto se debe a que si uno de los problemas NP-completos distintos de A, digamos X, se pudiese resolver en tiempo polinómico, entonces A se podría resolver en tiempo polinómico, por definición de NP-completo. Ahora, pueden existir problemas en NP y que no sean NP-completos para los cuales exista solución polinómica aún no existiendo solución para A.

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 2ⁿ-1 subconjuntos posibles hasta encontrar uno que cumpla con la condición.

Un problema de decisión C es NP-completo si:

1. C es un problema NP, y
2. Todo problema de NP se puede transformar polinómicamente en C.

Se puede demostrar que C es NP demostrando que un candidato a solución de C puede ser verificado en tiempo polinómico.

Una transformación polinómica de L en C es un algoritmo determinista que transforma instancias de l ∈ L en instancias de c ∈ C, tales que la respuesta a c es positiva si y sólo si la respuesta a l lo es.

Como consecuencia de esta definición, de tenerse un algoritmo en P para C, se tendría una solución en P para todos los problemas de NP.

Esta definición fue propuesta por Stephen Cook en 1971. Al principio parecía sorprendente que existieran problemas NP-completos, pero Cook demostró (teorema de Cook) que el problema de satisfacibilidad booleana es NP-completo. Desde entonces se ha demostrado que miles de otros problemas pertenecen a esta clase, casi siempre por reducción a partir de otros problemas para los que ya se había demostrado su pertenencia a NP-completo; muchos de esos problemas aparecen en el libro de Garey and Johnson's de 1979 Computers and Intractability: A Guide to NP-completeness.

Un problema que satisface la segunda condición pertenece a la clase NP-hard independientemente de que satisfaga la primera.

LA COMPLEJIDAD, UN CONCEPTO OPERATIVO Y APLICABLE

Habíamos empezado hablando de la complejidad y hora es de volver a ella.
Se habrá advertido que cada una de las teorías o conjuntos teóricos examinados se ocupa de algun aspecto, inédito y de carácter cualitativo, de la realidad. Desde la perspectiva aquí adoptada, esto es importante por varias razones:
a) Estas teorías tienen un enorme valor epistemológico, pues abren vías de acceso a la realidad, que permiten aprehender ésta sin prescindir de su complejidad.
b) A la par, estas teorías ponen de manifiesto propiedades desconocidas de la realidad y con ello ofrecen un nuevo concepto de la complejidad. En este sentido, afirmar que la realidad es compleja significa, al menos, cuatro cosas: 1) Que la realidad es borrosa. 2) Que la realidad es catastrófica. 3) Que la realidad es fractal. Y 4) que la realidad es caótica.
c) Pero hay más: a la luz de estas teorías se nos aparece una realidad paradójica; una realidad que no es nítida pero tampoco es dual, que no es continua ni discontínua, ni es estable ni inestable, ni reiterativa ni innovadora, ni ordenada ni desordenada (sobre este último aspecto: Munné, en prensa b). Las propiedades de la complejidad subsumen estas alternativas, las cuales únicamente parecen tener pleno sentido en la realidad artificialmente producida por el ser humano (edificios, máquinas, utensilios, objetos producidos, etc.).
Así las cosas, hay que avanzar en el camino abierto por las teorías examinadas. Por ejemplo, un paso más en esa dirección se puede dar profundizando en las relaciones entre los aspectos de la complejidad puestos de manifiesto por dichas teorías u otras teorías de la complejidad que se vayan formulando. Algunas de estas relaciones ya son conocidas: La dimensión geométrica de carácter fraccionado o intermedio de los fractales parece ser indicadora de borrosidad. La teoría de las catástrofes describe la morfogénesis de la estabilidad y, en este aspecto, procesos no caóticos; con todo, es relacionable con la teoría del caos, porque este "se cuela" a través de la catástrofe. Además, la teoría de las catástrofes probablemente pueda ser reentendida a través de una teoría más general de las bifurcaciones e incluso de las oscilaciones. También los atractores extraños son fractaliformes: nunca se cortan o yuxtaponen debido a su determinismo y las trayectorias se "aprietan" más y más al reducir la escala de observación. Las turbulencias consisten, como los fractales, en irregularidades. Etc.
Otra cuestión es la de las relaciones entre las teorías de la complejidad, las cuales lógicamente no están exentas de discrepancias. Han originado ya polémicas importantes, por ejemplo, entre Mandelbrot y Thom, o entre Mandelbrot y Feigenbaum. Pero más allá de disputas puntuales, una cuestión que late en toda esta temática es la que opone la borrosidad, la estabilidad, la iteración, el equilibrio, etc. a los límites, los puntos críticos, los ciclos límite, las transiciones del espacio de fases, etc. A nivel epistemológico, esta cuestión no es nueva: cuando Louis de Broglie explicó en un libro, ya clásico en la filosofía de la ciencia, el enfrentamiento entre las interpretaciones corpuscular y ondulatoria del mundo físico puso un título a su obra que revela que los conceptos en lid siguen siendo los mismos: Continu et discontinu en physique moderne (1941).
¿ Cómo las aportaciones de las anteriores teorías, nacidas en las ciencias naturales, pueden ser aplicadas, en el pleno sentido empírico de la palabra, a las ciencias del comportamiento ?
La mejor manera de comprender cómo o en que sentido hay que entender esta aplicación es darse cuenta de que los constructos aportados desde el enfoque de la complejidad (como son los conceptos de fractal, conjunto difuso, torbellino, caos, atractor extraño, etc.) son altamente formalizables. Esto significa que pueden ser aplicados de un modo transdisciplinar, sin necesidad de acudir a metáforas ni analogías.
Es lo mismo que sucede con el concepto de feedback: usted puede aplicarlo, con pleno sentido, tanto a un motor como al cuerpo humano, desde a una galaxia a un movimiento social. Sin embargo a usted no se le ocurrirá que el cuerpo humano es un motor o que un motor es igual que el cuerpo humano, ni que una galaxia y un movimiento social son confundibles. Y sin aquel concepto muchos fenómenos o procesos, si es que pueden ser planteados, no pueden llegar a ser bien comprendidos. Piénsese tan sólo en la revelancia social de los procesos de autorregulación o autocontrol.
Como epistemologías, las teorías examinadas proporcionan un nuevo modo de aprehender la realidad y ayudan a una comprensión menos reductora de los procesos básicos del comportamiento y la realidad sociales.
Y esto no se queda en el análisis. Conlleva, también, al menos potencialmente, nuevas formas de tratamiento de la realidad. Ya se ha dicho que las teorías del caos han entrado en el campo del diagnóstico. Puede añadirse que están asomando al ámbito de la intervención. Una muestra de lo que esto puede significar la tenemos en las recientes investigaciones de Brenda Zimmerman (por ej., 1992) sobre la dirección estratégica, basada en el caos y en la fractalidad de las organizaciones.

Problema de la película "Una mente indomable"

Encontrar de la gráfica:

1)La matriz de Adyacencia.

2)La matriz dando el numero de los 3 pasos.

3)La función generadoraque pasa por los puntos i -> j.

4)La función generadora que pasa por los puntos 1 -> 3.

ISOMORFISMO

El concepto matemático de Isomorfismo ( del griego Iso-morfos: igual forma) pretende captar la idea de tener la misma estructura.

Dos estructuras matemáticas entre las que existe una relación de Isomorfismo se llaman Isomorfas.

Se puede definir concisamente como: un Isomorfismo es un homomorfismo biyectivo tal que su inversa es también homomorfismo (1).

Características del Isomorfismo:

El descubrimiento de un Isomorfismo entre dos estructuras significa esencialmente que el estudio de cada una puede reducirse al de la otra, lo que nos da dos puntos de vista diferentes sobre cada gestión y suele ser esencial en su adecuada comprensión. También significa una analogía como una forma de inferencia lógica basada en la asunción de que dos cosas son la misma en algunos aspectos, aquellos sobre los que está hecha la comparación.

Ejemplos de isomorfismos

Por ejemplo, si X es un número real positivo con el producto e Y es un número real con la suma, el logaritmo ln:X→Y es un isomorfismo, porque ln(ab) = ln(a) + ln(b) y cada número real es el logaritmo de un único número real positivo. Esto significa que cada enunciado sobre el producto de números reales positivos tiene (sin más que sustituir cada número por su logaritmo) un enunciado equivalente en términos de la suma de números reales, que suele ser más simple.

(1): Homomorfismo: Dados dos conjuntos no vacíos A y A', y las leyes de composición interna

La función es un homomorfismo respecto de + y * si y solo si la imagen de la composición en A es igual a la composición de las imagenes en A'. Es decir: es homomorfismo respecto de + y *.

Problema del viajante.

LA BASE DEL PROBLEMA:

El problema del viajante es un ejemplo que muestra y analiza la problemática que subyace tras algunos tipos de problemas matemáticos que a priori parecen tener una solución relativamente fácil, y en la práctica presentan un gran problema.

La respuesta al problema es conocida, es decir se conoce la forma de resolverlo, pero sólo en teoría, en la práctica la solución no es aplicable debido al tiempo que computacionalmente se precisa para obtener su resultado.

El problema del viajante o también conocido como problema del viajante de comercio o por sus siglas TSP: Travelling Salesman Problem. es uno de los problemas mas famosos en el campo de la optimización combinatoria computacional.

A pesar de su aparente sencillez del planteamiento , este es uno de los mas complejos desde hace siglos.

ENUNCIADO:

Sean N ciudades de un territorio. El objetivo es encontrar una ruta que, comenzando y terminando en una ciudad concreta, pase una sola vez por cada una de las ciudades y minimice la distancia recorridad por el viajante. Es decir, encontar una permutación P={ C₀, C₂,...,Cn-₁} tal que...

sea mínimo. La distancia entre cada ciudad viene dada por la matríz D: NxN, donde d [x, y] representa la distancia que hay entre la ciudad X y la ciudad Y.

Enrico Bombieri Teoría de Números, Geometría Algebráica, Ecuaciones en Derivadas Parciales, Variable Compleja, Teoría de los Grupos Finitos.

De Milan, Italia Se interesó por la Teoría de números desde la temprana edad de 13 años. Bombierí está considerado como uno de los matemáticos más versátiles y extraordinarios de la actualidad. Practicamente ha influido en todos los campos en donde ha trabajado. Ha demostrado siempre una gran habilidad para dominar rápidamente los aspectos esenciales de campos complicados por su novedad, aplicando una gran energía e intuición en la obtención de resultados de envergadura. Es un buen escritor de matemática, distinguiéndose por una gran claridad expositiva. Medalla Fields 1974 Trabaja actualmente en Princeton, en elInstituto de Estudios Avanzados.

DONALD KNUTH

DONALD KNUTH

Donald Ervin Knuth, (nacido el 10 de enero de 1938 en Milwaukee, Wisconsin) es uno de los más reconocidos expertos en ciencias de la computación por su seminal investigación dentro del análisis de algoritmos y compiladores. Es Profesor Emérito de la Universidad de Stanford.
Se le conoce principalmente por ser el autor de la obra "The art of computer programming" (El arte de programar computadoras), una de las más respetadas referencias en el campo de las ciencias de la computación. Sentó las bases y dio nombre al análisis de algoritmos, y ha realizado numerosos aportes a varias ramas teóricas de la informática. Es el creador de TEX, del sistema de diseño de tipos METAFONT y del estilo de programación conocido como programación literaria (Literate programming).