galvan

domingo, 28 de febrero de 2010

Importancia de las Matemáticas Discretas

El acelerado desarrollo tecnológico alcanzado en los últimos años las áreas de la computación y telecomunicaciones, de los cuales hemos sido testigos de estos sorprendentes avances; campos que han fundamentado su crecimiento en las ciencias puras siendo una de ellas las matemáticas, la misma que ha aportado con una variedad de temas que se encuentran incluidos dentro de las Matemáticas Discretas. Asignatura de Matemáticas Discretas que forma parte del plan de estudios de Ingeniería en Informática y que esta incluida dentro del pensum de estudios del Segundo Ciclo, con temas que proporcionan los conocimientos base, necesarios e indispensables para que los profesionales en formación puedan conocer y adentrarse en estas nuevas tecnologías, con un enfoque práctico, aplicado y computacional, además de un acentuado carácter formativo. Siendo las Matemáticas Discretas, la ciencia que trata sobre el conocimiento y explicación de fenómenos discretos y procesos finitos, que servirán para aplicaciones posteriores dentro de la formación de los futuros ingenieros en informática y al mismo tiempo permitirán conocer como trabajan estas modernas herramientas que son las computadoras y poder aprovechar su potencialidad para poder incursionar en áreas como de Sistemas y desarrollo de Software. Lo que hace que esta asignatura se plantee como respuesta a una variada serie de problemas de la «vida real» (diseño de bloques, flujo de redes, diseño de circuitos, asignaciones horarias o de tareas, ...), lo que le confiere el enfoque aplicado que señalamos arriba, aprendiendo el alumno, además, a buscar modelos matemáticos adecuados para gran número de situaciones diferentes, lo que suele ser muy habitual en el desarrollo profesional. Entre los principales aportes que nos brinda las Matemáticas Discretas a través de diversos métodos es ayudarnos a la creación de sistemas de elevada complejidad y que, sin embargo, alcancen los parámetros de eficiencia y eficacia deseados. El uso de métodos pero si bien formales no nos garantiza, a priori, la corrección del software, pero es una buena práctica que permite alcanzar mejores resultados en la construcción de sistemas complejos, ya que nos permite revelar inconsistencias, ambigüedades, etc. Dentro de este desarrollo nace la necesidad de un ajuste en el perfil de los profesionales que se dedican a la aplicación de la tecnología informática en las empresas y organizaciones; y, es ahí donde tenemos que sustentar los conocimientos necesarios e indispensables de nuestros profesionales que les permitan afrontar los retos del desarrollo. El carácter formativo de la asignatura se debe, no sólo al carácter formativo que tienen las Matemáticas en general sino, en concreto, a que el lenguaje y las herramientas que se usan en la asignatura son los habituales en gran parte de las asignaturas de la carrera como: programación, análisis de sistemas, etc. y en el desarrollo mismo de los profesionales en formación. Actualmente estamos asistiendo a una mejora de los métodos matemáticos para la verificación y especificación de sistemas de hardware y software de elevada complejidad; de hecho, muchos de estos métodos ya son capaces de afrontar ejemplos reales del mundo industrial. Esta mejora en los métodos se debe principalmente al desarrollo de nuevas metodologías y de nuevas y más potentes herramientas (como pueden ser mejores probadores de teoremas). Es difícil predecir, aún así, cual será el alcance, en el futuro, de estas técnicas; pero la situación permite un cierto optimismo que debería ser acompasado de un trabajo en investigación que permita que estas técnicas ayuden en mayor medida al mundo industrial. En el pasado el uso de estas técnicas no fue muy utilizado debido a los problemas que llevan asociados, como la dificultad de los métodos, su baja capacidad para escalar, etc. Actualmente estas técnicas están aumentando su grado de aceptación y mejorando su capacidad de éxito lo que convierte a los métodos formales en una técnica que no debemos dejar de tener en cuenta a la hora de buscar métodos para la creación de sistemas computacionales de calidad. La evolución de estos métodos y los frutos de la investigación que en ellos se está llevando a cabo nos dirán cual será el papel de estos métodos en la informática del futuro. La meta de esta asignatura es enseñar los elementos básicos de Matemáticas que, siendo importantes para la informática, no son cubiertos por los cursos tradicionales de Álgebra y Análisis Matemático, o por cursos más específicos de introducción a la programación y a la informática teórica. El programa trata de manera general materias de teoría de conjuntos, sistemas numéricos, estructuras algebraicas, combinatoria, teoría de grafos, árboles, modelos de redes y lenguajes. Se hace especial énfasis en principios generales tales como la inducción y la recursión. Esperamos que los alumnos adquieran la capacidad de aplicar los conceptos y técnicas aquí aprendidos en el contexto de otras asignaturas del plan de estudios. Uno de los temas que se tratan es la de los tipos de grafos más importantes, entre los que tenemos los árboles. Los árboles se utilizan en muchos campos de aplicación, como por ejemplo: en ciencias de la Computación, los árboles se utilizan para organizar la información de tal forma que sea posible efectuar eficientemente operaciones que involucren a esa información. Por otra parte, es frecuente que resulte muy posible el desglosar los problemas complejos y representarlos mediante una estructura en forma de árbol. Además, los árboles surgen en aplicación de redes que se modelan mediante grafos. Un ejemplo tipo lo encontramos en una red de comunicaciones, en la cual los nodos de la red esté conectada con el mínimo costo posible. Razones que nos han inducido a programar este curso, siguiendo el texto, de Matemáticas Discretas de Richard Johnsonbaugh, cuarta edición, por su enfoque didáctico por la claridad de sus contenidos y por la gran cantidad de ejercicios resueltos y propuestos.

Algoritmos

Los diagramas de flujo sirven para representar algoritmos de manera gráfica

En matemáticas, ciencias de la computación y disciplinas relacionadas, un algoritmo (del latín, dixit algorithmus y éste a su vez del matemático persa Al Juarismi^[1] ) es un conjunto preescrito de intrucciones o reglas bien definidas, ordenadas y finitas que permite realizar una actividad mediante pasos sucesivos que no generen dudas a quien lo ejecute.^[2] 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 objeto de estudio de la algoritmia.^[1]

En la vida cotidiana se emplean algoritmos en multitud de ocasiones 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áticas 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

Características principales y definición formal

En general, no existe ningún consenso definitivo en cuanto a la definición formal de algoritmo. Muchos autores los señalan como listas de instrucciones para resolver un problema abstracto, es decir, que un número finito de pasos convierten los datos de un problema (entrada) en una solución (salida).^[1] ^[2] ^[3] ^[4] ^[5] ^[6] Sin embargo cabe notar que algunos algoritmos no necesariamente tienen que terminar o resolver un problema en particular. Por ejemplo, una versión modificada de la criba de Eratóstenes que nunca termine de calcular números primos no deja de ser un algoritmo.^[7]

A lo largo de la historia varios autores han tratado de definir formalmente a los algoritmos utilizando modelos matemáticos como máquinas de Turing entre otros.^[8] ^[9] Sin embargo estos modelos están sujetos a un tipo particular de datos como son números, símbolos o gráficas mientras que, en general, los algoritmos funcionan sobre una basta cantidad de estructuras de datos.^[3] ^[1] En general, la parte común en todas las definiciones se puede resumir en las siguientes tres propiedades siempre y cuando no consideremos algoritmos paralelos:^[7]

Tiempo secuencial. Un algoritmo funciona en tiempo discretizado –paso a paso–, definiendo así una secuencia de estados "computacionales" por cada entrada válida (la entrada son los datos que se le suministran al algoritmo antes de comenzar).

Estado abstracto. Cada estado computacional puede ser descrito formalmente utilizando una estructura de primer orden y cada algoritmo es independiente de su implementación (los algoritmos son objetos abstractos) de manera que en un algoritmo las estructuras de primer orden son invariantes bajo isomorfismo.

Exploración acotada. La transición de un estado al siguiente queda completamente determinada por una descripción fija y finita; es decir, entre cada estado y el siguiente solamente se puede tomar en cuenta una cantidad fija y limitada de términos del estado actual.

En resumen, un algoritmo es cualquier cosa que funcione paso a paso, donde cada paso se pueda describir sin ambigüedad y sin hacer referencia a una computadora en particular, y además tiene un límite fijo en cuanto a la cantidad de datos que se pueden leer/escribir en un solo paso. Esta amplia definición abarca tanto a algoritmos prácticos como aquellos que solo funcionan en teoría, por ejemplo el método de Newton y la eliminación de Gauss-Jordan funcionan, al menos en principio, con números de precisión infinita; sin embargo no es posible programar la precisión infinita en una computadora, y no por ello dejan de ser algoritmos.^[10] En particular es posible considerar una cuarta propiedad que puede ser usada para validar la tesis de Church-Turing de que toda función calculable se puede programar en una máquina de Turing (o equivalentemente, en un lenguaje de programación suficientemente general):^[10]

Aritmetizabilidad. Solamente operaciones innegablemente calculables están disponibles en el paso inicial.

Medios de expresión de un algoritmo

Los algoritmos pueden ser expresados de muchas maneras, incluyendo al lenguaje natural, pseudocódigo, diagramas de flujo y lenguajes de programación entre otros. Las descripciones en lenguaje natural tienden a ser ambiguas y extensas. El usar pseudocódigo y diagramas de flujo evita muchas ambigüedades del lenguaje natural. Dichas expresiones son formas más estructuradas para representar algoritmos; no obstante, se mantienen independientes de un lenguaje de programación específico.

La descripción de un algoritmo usualmente se hace en tres niveles:

Descripción de alto nivel. Se establece el problema, se selecciona un modelo matemático y se explica el algoritmo de manera verbal, posiblemente con ilustraciones y omitiendo detalles.
Descripción formal. Se usa pseudocódigo para describir la secuencia de pasos que encuentran la solución.
Implementación. Se muestra el algoritmo expresado en un lenguaje de programación específico o algún objeto capaz de llevar a cabo instrucciones.

También es posible incluir un teorema que demuestre que el algoritmo es correcto, un análisis de complejidad o ambos.

Diagrama de flujo

Diagrama de flujo que expresa un algoritmo para calcular la raíz cuadrada de un número x

Artículo principal: Diagrama de flujo

Los diagramas de flujo son descripciones gráficas de algoritmos; usan símbolos conectados con flechas para indicar la secuencia de instrucciones y están regidos por ISO.

Los diagramas de flujo son usados para representar algoritmos pequeños, ya que abarcan mucho espacio y su construcción es laboriosa. Por su facilidad de lectura son usados como introducción a los algoritmos, descripción de un lenguaje y descripción de procesos a personas ajenas a la computación.

Pseudocódigo

Artículo principal: Pseudocódigo

Pseudocódigo es la descripción de un algoritmo que asemeja a un lenguaje de programación pero con algunas convenciones del lenguaje natural (de ahí que tenga el prefijo pseudo, que significa falso). Tiene varias ventajas con respecto a los diagramas de flujo, entre las que se destaca el poco espacio que se requiere para representar instrucciones complejas. El pseudocódigo no está regido por ningún estándar.

Sistemas formales

La teoría de autómatas y la teoría de funciones recursivas proveen modelos matemáticos que formalizan el concepto de algoritmo. Los modelos más comunes son la máquina de Turing, máquina de registro y funciones μ-recursivas. Estos modelos son tan precisos como un lenguaje máquina, careciendo de expresiones coloquiales o ambigüedad, sin embargo se mantienen independientes de cualquier computadora y de cualquier implementación.

Implementación

Muchos algoritmos son ideados para implementarse en un programa. Sin embargo, los algoritmos pueden ser implementados en otros medios, como una red neuronal, un circuito eléctrico o un aparato mecánico y eléctrico. Algunos algoritmos inclusive se diseñan especialmente para implementarse usando lápiz y papel. El algoritmo de multiplicación tradicional, el algoritmo de Euclides, la criba de Eratóstenes y muchas formas de resolver la raíz cuadrada son sólo algunos ejemplos.

Matematicas discretas Vll

Árbol (informática)

En ciencias de la informática, un árbol es una estructura de datos ampliamente usada que imita la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él. Se dice que un nodo a es padre de un nodo b si existe un enlace desde a hasta b (en ese caso, también decimos que b es hijo de a). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja. Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama.

Definición

Formalmente, podemos definir un árbol de la siguiente forma:

Caso base: un árbol con sólo un nodo (es a la vez raíz del árbol y hoja).

Un nuevo árbol a partir de un nodo $n r$ y $k$ árboles $A_1, A_2 \dots A_k$ de raíces $n_1, n_2, \dots, n_k$ con $N_1, N_2, \dots ,N_k$ elementos cada uno, puede construirse estableciendo una relación padre-hijo entre $n r$ y cada una de las raíces de los $k$ árboles. El árbol resultante de $N = 1 + N_1 + \dots + N_k$ nodos tiene como raíz el nodo $n r$ , los nodos $n_1, n_2, \dots, n_k$ son los hijos de $n r$ y el conjunto de nodos hoja está formado por la unión de los $k$ conjuntos hojas iniciales. A cada uno de los árboles $A i$ se les denota ahora subárboles de la raíz.

Una sucesión de nodos del árbol, de forma que entre cada dos nodos consecutivos de la sucesión haya una relación de parentesco, decimos que es un recorrido árbol. Existen dos recorridos típicos para listar los nodos de un árbol: primero en profundidad y primero en anchura. En el primer caso, se listan los nodos expandiendo el hijo actual de cada nodo hasta llegar a una hoja, donde se vuelve al nodo anterior probando por el siguiente hijo y así sucesivamente. En el segundo, por su parte, antes de listar los nodos de nivel $n + 1$ (a distancia $n + 1$ aristas de la raíz), se deben haber listado todos los de nivel $n$ . Otros recorridos típicos del árbol son preorden, postorden e inorden:

El recorrido en preorden, también llamado orden previo consiste en recorrer en primer lugar la raíz y luego cada uno de los hijos $A_1, A_2 \dots A_k$ en orden previo.
El recorrido en inorden, también llamado orden simétrico (aunque este nombre sólo cobra significado en los árboles binarios) consiste en recorrer en primer lugar $A 1$ , luego la raíz y luego cada uno de los hijos $A_2 \dots A_k$ en orden simétrico.
El recorrido en postorden, también llamado orden posterior consiste en recorrer en primer lugar cada uno de los hijos $A_1, A_2 \dots A_k$ en orden posterior y por último la raíz.

Finalmente, puede decirse que esta estructura es una representación del concepto de árbol en teoría de grafos. Un árbol es un grafo conexo y acíclico (ver también teoría de grafos y Glosario en teoría de grafos).

Tipos de árboles

Árbol de búsqueda binario auto-balanceable

Árboles AVL

Árboles Rojo-Negro

Árbol AA

Árboles B

Árbol-B+

Árbol-B*

Árboles Multicamino

Árboles Binarios : En ciencias de la computación, un árbol binario es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno.

Ejemplo de árbol (binario).

Operaciones de árboles. Representación

Las operaciones comunes en árboles son:

Enumerar todos los elementos.
Buscar un elemento.
Dado un nodo, listar los hijos (si los hay).
Borrar un elemento.
Eliminar un subárbol (algunas veces llamada podar).
Añadir un subárbol (algunas veces llamada injertar).
Encontrar la raíz de cualquier nodo.

Por su parte, la representación puede realizarse de diferentes formas. Las más utilizadas son:

Representar cada nodo como una variable en el heap, con punteros a sus hijos y a su padre.
Representar el árbol con un array donde cada elemento es un nodo y las relaciones padre-hijo vienen dadas por la posición del nodo en el array.

Uso de los árboles

Usos comunes de los árboles son:

Representación de datos jerárquicos.
Como ayuda para realizar búsquedas en conjuntos de datos

Grafo

Para otros usos de este término, véase Grafo (desambiguación).

Para la teoría entorno a este objeto matemático, véase Teoría de grafos.

Grafo etiquetado con 6 vértices y 7 aristas.

En matemáticas y ciencias de la computación, un grafo (del griego grafos: dibujo, imagen) o gráfica es el principal objeto de estudio de la teoría de grafos.

Informalmente, un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.

Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).

Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan terminales y las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).

Prácticamente cualquier problema puede representarse mediante un grafo, y su estudio trasciende a las diversas áreas de las ciencias exactas y las ciencias sociales.

Definiciones

Un grafo G es un par ordenado G = (V,E), donde:

V es un conjunto de vértices o nodos, y
E es un conjunto de arcos o aristas, que relacionan estos nodos.

Normalmente V suele ser finito. Muchos resultados importantes sobre grafos no son aplicables para grafos infinitos. Se llama orden de G a su número de vértices, | V | .

Lazos o bucles

Un lazo o bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden.

Grafo no dirigido

Grafo no dirigido

Un grafo no dirigido o grafo propiamente dicho es un grafo G = (V,E) donde:

$V\neq\emptyset$
$E\subseteq \{x\in\mathcal P(V): |x|=2\}$ es un conjunto de pares no ordenados de elementos de $V\,$ .

Un par no ordenado es un conjunto de la forma {a,b}, de manera que {a,b} = {b,a}. Para los grafos, estos conjuntos pertenecen al conjunto potencia de V de cardinalidad 2, el cual se denota por $\mathcal P(V)$ .

Grafo dirigido

Grafo dirigido

Un grafo dirigido o digrafo es un grafo G = (V,E) donde:

$V\neq\emptyset$
$E \subseteq \{(a,b) \in V \times V: a \neq b \}\,$ es un conjunto de pares ordenados de elementos de $V\,$ .

Dada una arista (a,b), a es su nodo inicial y b su nodo final.

Por definición, los grafos dirigidos no contienen bucles.

Un grafo mixto es aquel que se define con la capacidad de poder contener aristas dirigidas y no dirigidas. Tanto los grafos dirigidos como los no dirigidos son casos particulares de este.

Pseudografo

Un pseudografo es un grafo G = (V,E) donde:

$V\neq\emptyset$
$E \subseteq \{x\in\mathcal P(V):1\leq |x|\leq2\}$ es un conjunto de pares no ordenados de elementos de $V\,$ .

Es decir, un pseudografo es un grafo no dirigido que acepta bucles en $E\,$ .

Pseudografo dirigido

Un pseudografo dirigido es un grafo G = (V,E) donde:

$V\neq\emptyset$
$E \subseteq V\times V\,$ es un conjunto de pares ordenados y etiquetados de elementos de $V\,$

Es decir, un pseudografo dirigido es un grafo dirigido que acepta bucles en $E\,$ .

Variantes sobre las definiciones principales

Algunas aplicaciones requieren extensiones más generales a las dos propuestas clásicas de grafos. Aunque la definición original los permite, según la aplicación concreta pueden ser válidos o no. A veces V o E pueden ser un multiconjunto, pudiendo haber más de una arista entre cada par de vértices. La palabra grafo (a secas) puede permitir o no múltiples aristas entre cada par de vértices, dependiendo del autor de la referencia consultada. Si se quiere remarcar la inexistencia de múltiples aristas entre cada par de vértices (y en el caso no dirigido, excluir bucles) el grafo puede llamarse simple. Por otra parte, si se quiere asegurar la posibilidad de permitir múltiples aristas, el grafo puede llamarse multigrafo (a veces se utiliza el término pseudografo para indicar que se permiten tanto bucles como múltiples aristas entre cada par de vértices).

Propiedades

Adyacencia: dos aristas son adyacentes si tienen un vértice en común, y dos vértices son adyacentes si una arista los une.
Incidencia: una arista es incidente a un vértice si ésta lo une a otro.
Ponderación: corresponde a una función que a cada arista le asocia un valor (costo, peso, longitud, etc.), para aumentar la expresividad del modelo. Esto se usa mucho para problemas de optimización, como el del vendedor viajero o del camino más corto.
Etiquetado: distinción que se hace a los vértices y/o aristas mediante una marca que los hace unívocamente distinguibles del resto.

Ejemplos

La imagen es una representación del siguiente grafo:

V:={1,2,3,4,5,6}
E:={{1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6}}

El hecho que el vértice 1 sea adyacente con el vértice 2 puede ser denotado como 1 ~ 2.

En la Teoría de las categorías una categoría puede ser considerada como un multigrafo dirigido, con los objetos como vértices y los morfismos como aristas dirigidas.
En ciencias de la computación los grafos dirigidos son usados para representar máquinas de estado finito y algunas otras estructuras discretas.
Una relación binaria R en un conjunto X es un grafo dirigido simple. Dos vértices a, b en X están conectados por una arista dirigida ab si aRb.

Grafos importantes

Existen grafos que poseen propiedades destacables. Algunos ejemplos básicos son:

Grafo nulo: aquel que no tiene vértices ni aristas. Nótese que algunas personas exigen que el conjunto de vértices no sea vacío en la definición de grafo.
Grafo vacío: aquel que no tiene aristas.
Grafo trivial: aquel que tiene un vértice y ninguna arista.
Grafo simple: aquel que no posee bucles o lazos.
Grafo completo: grafo simple en el que cada par de vértices están unidos por una arista, es decir, contiene todas las posibles aristas.
Grafo bipartito completo: sea (W,X) una partición del conjunto de vértices V, es aquel donde cada vértice en W es adyacente sólo a cada vértice en X, y viceversa.
Grafo bipartito: sea (W,X) una partición del conjunto de vértices V, es aquel donde cada arista tiene un vértice en W y otro en X.
Grafo plano: aquel que puede ser dibujado en el plano cartesiano sin cruce de aristas.
Árbol: grafo conexo sin ciclos.

Una generalización de los grafos son los llamados hipergrafos.