APLICABILIDAD DE LAS MATEMATICAS DISCRETAS EN LA INGENIERIA DE SISTEMAS

La importancia de la matemática en el contexto del desarrollo científico y tecnológico de la humanidad, está determinada por la posibilidad de elaborar modelos matemáticos de los objetos estudiados por las diferentes ramas de la ciencia y la técnica es decir, describir mediante el lenguaje vigoroso de la matemática, las propiedades de los objetos reales. En la facultad de ingeniería a partir de la década de los ochenta se ha producido un paulatino desplazamiento de la matemática del continuo hacia la matemática discreta.

El acento en los algoritmos discretos usados en las ciencias de la computación hace necesario el trabajo con ciertas porciones de la matemática discreta suficientemente elementales como para poder formar parte con éxito de un programa inicial de matemáticas. La combinatoria clásica, la teoría elemental de números, la teoría de discretización de señales, etc., podrían ser considerados como candidatos para ello. No existe en la actualidad un texto adecuado que responda a estas necesidades que imponen los nuevos tiempos, sobre todo en las carreras de ingeniería electrónica e ingeniería de sistemas. No hay duda que en ingeniería, gran parte de la matemática del futuro tendrá otro sabor y este sabor será discreto.

La importancia de la "popularización" de la matemática discreta en los tiempos actuales creo que no admite discusión.

Veamos lo que dice Miguel De Guzmán en su texto "Tendencias innovadoras en educación matemática" en vez de elucubrar sobre su pertenencia:

"La matemática del siglo XX ha sido predominantemente la matemática del contínuo en la que el análisis, por su potencia y repercusión en las aplicaciones técnicas, ha jugado un papel predominante.
El advenimiento de los ordenadores, con su inmensa capacidad de calculo, con su enorme rapidez, versatilidad, potencia de representación gráfica, posibilidades para la modelización sin pasar por la formulación matemática de corte clásico,... ha abierto multitud de campos diversos, con origen ya no en la fisica, como los desarrollos de siglos anteriores, sino en otras muchas ciencias como la economía, las ciencias de la organización, biología, ... cuyos problemas resultaban opacos, en parte por las enormes masas de información que había que tratar hasta llegar a dar con las intuiciones matemáticas valiosas que pudieran conducir a procesos de resolución de los dificiles problemas propuestos en estos campos.
Por otra parte, el acento en los algoritmos discretos, usados en las ciencias de la computación, en la informática, asi como en la modelización de diversos fenómenos mediante el ordenador, ha dado lugar a un traslado de énfasis en la matemática actual hacia la matemática discreta. Ciertas porciones de ella son lo suficientemente elementales como para poder formar parte con éxito de un programa inicial de matemática. La combinatoria clásica, asi como los aspectos modernos de ella, tales como la teoría de grafos o la geometría combinatoria, podrían ser considerados candidatos adecuados. La teoría elemental de números, que nunca llegó a desaparecer de los programas en algunos países, podría ser otro.
Se han realizado intentos por introducir estos elementos y otros semejantes pertenecientes a la matemática discreta en la enseñanza matemática inicial. Sucede que esto parece solo posible a expensas de otras porciones de la matemática con más raigambre de las que no se ve bien como se puede prescindir. Aunque parece bastante obvio que el sabor de la matemática del futuro será bastante diferente del actual por razón de la presencia del ordenador, aún no se ve bien claro cómo esto va a plasmarse en los contenidos de la enseñanza primaria y secundaria"


En la matemática actual no basta desarrollar una teoría para encontrar la solución de un problema, sino que los métodos derivados de la teoría deben ser algoritmizados y estos algoritmos discretos deben ser eficientes para poder ser realizados con la capacidad de cálculo actual. De otra parte el estudiante de ingeniería actual se enfrenta desarmado al diseño de circuitos digitales en las carreras de ingeniería electrónica y de sistemas; porque no conoce algoritmos elementales que proporciona, por ejemplo, la aritmética. La importancia de ésta en el diseño de juegos de estrategia es fundamental. Experiencias en semestres anteriores con algunos estudiantes me han convencido de ésta realidad.


Lo que las Matematica Discretas pretenden lograr en la Ingenieria de Sistemas:

1. Introducir al alumno en técnicas de razonamiento lógico y razonamiento combinatorio, y en general, métodos discretos.

2. Se incluyen temas como algoritmos, inducción matemática, aritmética residual y sistemas numéricos.

3. Se hace un tratamiento matemático de lo que es un algebra de Boole, a partir del concepto de relación de orden.

4. Se introduce el concepto de grafos y de máquinas de tiempo finito que enfatiza la modelación y las aplicaciones.

5. Por ultimo, se tocan temas de discretización de señales haciendo énfasis en el concepto de sumatoria de convolución, ecuaciones en diferencias homogéneas y no homogéneas. Se finaliza con el estudio de la transformada Z.

6. Se incluyen gran variedad de aplicaciones, que buscan desarrollar la madurez matemática del estudiante mediante el estudio de un área tan diferente al cálculo.


Los prerequisitos de este curso son principalmente una buena formación en álgebra de secundaria e interés por abordar y resolver ciertos tipos de problemas.
La visión que se presenta aquí es amplia, como requiere un curso general; posiblemente muchas personas tendrán una visión diferente de lo que acá se presenta de acuerdo a sus intereses y necesidades.

Pienso que para los cursos de la Universidad de Antioquia en Ingeniería de Sistemas e Ingeniería Electrónica, este es un adecuado tema a tratar.

ALGORITMOS

Nuestra herramienta mental más importante para competir con la complejidad es la abstracción. Por tanto, un problema no deberá considerarse inmediatamente en términos de instrucciones de un lenguaje, sino de elementos naturales del problema mismo, abstraídos de alguna manera. [Niklaus Wirth, Creador del Lenguaje Pascal]


Algoritmo

Definicion:

Podemos encontrar muchas definiciones de algoritmo en los textos de programacion, todas ellas muy similares:

•Conjunto ordenado y finito de pasos que permite hallar la solución de un problema.
•Una secuencia de pasos que conducen a la realización de una tarea.
•Descripción exacta de la secuencia en que se ha de realizar un conjunto de actividades tendientes a resolver un determinado tipo de problema o procedimiento.
•Conjunto de sentencias / instrucciones en lenguaje nativo, los cuales expresan la lógica de un programa.
•Es un sistema por el cual se llega a una solución, teniendo en cuenta que debe de ser definido, finito y preciso.
•Toda receta, proceso, rutina, método, procedimiento, técnica, formula que resuelven un determinado problema.
•Conjunto de instrucciones concretas y detalladas mediante el cual se consigue una acción determinada.
•Conjunto de reglas que permiten obtener un resultado determinado a partir de ciertas reglas definidas.
•Descripción precisa de una sucesión de instrucciones que permite llevar a cabo un trabajo en un número finito de pasos.
•Un conjunto de símbolos y procedimientos usados en la realización de un cálculo.
Las definiciones mas completas o formales:

•Secuencia finita de instrucciones, reglas o pasos que describen de forma precisa las operaciones de un ordenador debe realizar para llevar a cabo un tarea en un tiempo mas finito. [Donald E. Knuth, 1968]
•Descripcion de un esquema de comportamiento expresado mediante un reportorio finito de acciones y de informaciones elementales, identificadas, bien comprendidas y realizables a priori. Este repertorio se denomica lexico [Pierre Scholl, 1988]
•Un algoritmo es un conjunto finito de pasos definidos, estructurados en el tiempo y formulados con base a un conjunto finito de reglas no ambiguas, que proveen un procedimiento para dar la solución o indicar la falta de esta a un problema en un tiempo determinado. [Rodolfo Quispe-Otazu, 2004]

Caracteristicas:

Las características fundamentales que debe cumplir todo algoritmo son:

•Ser definido: Sin ambigüedad, cada paso del algoritmo debe indicar la acción a realizar sin criterios de interpretación.
•Ser finito: Un número específico y numerable de pasos debe componer al algoritmo, el cual deberá finalizar al completarlos.
•Tener cero o más entradas: Datos son proporcionados a un algoritmo como insumo (o estos son generados de alguna forma) para llevar a cabo las operaciones que comprende.
•Tener una o más salidas: Debe siempre devolver un resultado; de nada sirve un algoritmo que hace algo y nunca sabemos que fue. El devolver un resultado no debe ser considerado como únicamente “verlos” en forma impresa o en pantalla, como ocurre con las computadoras. Existen muchos otros mecanismos susceptibles de programación que no cuentan con una salida de resultados de esta forma. Por salida de resultados debe entenderse todo medio o canal por el cual es posible apreciar los efectos de las acciones del algoritmo.
•Efectividad: El tiempo y esfuerzo por cada paso realizado debe ser preciso, no usando nada más ni nada menos que aquello que se requiera para y en su ejecución.

Historia:

La palabra algoritmo proviene del nombre del matemático llamado Abu Abdullah Muhammad bin Musa al-Khwarizmi (hay muchas variantes para el nombre al usar el alfabeto latin, tales como Al-Khorezmi, Al-Khwarizmi, Al-Khawarizmi, Al-Khawaritzmi o Al-Khowarizmi) que vivió entre los siglos VIII y IX.

Su trabajo consistió en preservar y difundir el conocimiento de la antigua Grecia y de la India. Sus libros eran de fácil comprensión, de ahí que su principal valor no fuera el de crear nuevos teoremas o nuevas corrientes de pensamiento, sino el de simplificar las matemáticas a un nivel lo suficientemente bajo para que pudiera ser comprendido por un amplio público. Cabe destacar cómo señaló las virtudes del sistema decimal indio (en contra de los sistemas tradicionales árabes) y cómo explicó que, mediante una especificación clara y concisa de cómo calcular sistemáticamente, se podrían definir algoritmos que fueran usados en dispositivos mecánicos similares a un ábaco en vez de las manos. También estudió la manera de reducir el numero de operaciones necesarias que formaban el cálculo.

Por esta razón, aunque no haya sido él el inventor del primer algoritmo, merece que este concepto esté asociado a su nombre. Al-Khorezmi fue sin duda el primer pensador algorítmico.

Ya en el siglo XIX, se produjo el primer algoritmo escrito para un computador. La autora fue Ada Byron, en cuyos escritos se detallaban la máquina analítica en 1842. Por ello que es considerada por muchos como la primera programadora aunque, desde Charles Babbage, nadie completó su máquina, por lo que el algoritmo nunca se implementó.

La idea de resolver un problema o de disponer de un algoritmo es bastante antigua, tal es así, que existía la errada creencia que no había problema que no se pudiera resolver y en base a ello, el matemático David Hilbert quiso descubrir un algoritmo para los algoritmos. Hoy en dia gracias a los trabajos de Kurt Gödel, Alonzo Church (calculo lamba), Alan Turing (maquina de turing), se sabe que dentro del universo de problemas, una pequeña parte es computable, luego que el objetivo que perseguia David Hilbert no era computable, es lo que se ha denominado como la computabilidad de los algoritmos.

ARBOLES

Arboles

En teoría de grafos, un árbol es un grafo en el que dos vértices están conectados por exactamente un camino. Un bosque es un grafo en el que dos vértices cualquiera están conectados por como máximo un camino. Una definición equivalente es que un bosque es una unión disjunta de árboles (de aquí el nombre). Un árbol a veces recibe el nombre de árbol libre.

Un árbol es un grafo simple unidireccional G que satisface alguna de las siguientes condiciones equivalentes:

G es conexo y no tiene ciclos simples.
G no tiene ciclos simples y, si se añade alguna arista se forma un ciclo simple.
G es conexo y si se le quita alguna arista deja de ser conexo.
G es conexo y el grafo completo de 3 vértices K3 no es un menor de G.
Dos vértices cualquiera de G están conectados por un único camino simple.
Si G tiene muchos vértices, n, entonces las definiciones anteriores son también equivalentes a cualquiera de las siguientes condiciones:

G es conexo y tiene n − 1 aristas.
G no tiene aristas simples y tiene n − 1 aristas.
La cantidad de hojas de un árbol siempre es mayor o igual a la mitad de la totalidad de los nodos

En gráfico unidireccional simple G se recible el nombre de bosque si no tiene ciclos simples.

Un árbol direccional es un grafo direccional que sería un árbol si se hiciera caso omiso de las direcciones de las aristas. Algunos autores restringen la frase al caso en el que todos las aristas se dirigen a un vértice particular, o todas sus direcciones parten de un vértice particular.

Un árbol recibe el nombre de árbol con raíz si cada vértice ha sido designado raíz, en cuyo caso las aristas tienen una orientación natural hacia o desde la raíz. Los árboles con raíz, a menudo con estructuras adicionales como orden de los vecinos de cada vértice, son una estructura clave en informática; véase árbol (programación).

Un árbol etiquetado es un árbol en el que cada vértice tiene una única etiqueta. Los vértices de un árbol etiquetado de n vértices reciben normalmente las etiquetas {1,2, ..., n}.

Un árbol regular ( homogéneo) es un árbol en el que cada vértice tiene el mismo grado.

Propiedades [editar]Todo árbol es a su vez un grafo bipartito. Todo árbol con sólo un conjunto contable de vértices es además un grafo plano.

Todo grafo conexo G admite un árbol de cobertura, que es un árbol que contiene cada vértice de G y cuyas aristas son aristas de G.

Dado n vértices etiquetados, hay n n−2 maneras diferentes de conectarlos para construir un grafo. El resultado se llama fórmula de Cayley.

El número de árboles con n vértices de grado d1,d2,...,dn es:

que es un coeficiente multinomial.

No se conoce fórmula para el número t(n) de árboles con n vértices de un isomorfismo de grafos. Sin embargo, el comportamiento asintótico de t(n) se conoce; hay números α ≈ 3 y β ≈ 0.5 tales que

GRAFOS

INTRODUCCION

Hoy en día podemos ver muchas cosas que nos pueden parecer de lo mas cotidianas, carreteras, líneas telefónicas, líneas de televisión por cable, el transporte colectivo metro, circuitos eléctricos de nuestras casas, automóviles, y tantas cosas mas; lo que no pensamos frecuentemente es que estos forman parte de algo que en matemáticas se denomina como grafos.

En este trabajo se tratará brevemente de explicar lo que son los grafos, sus tipos, y algunas derivaciones de ellos, así como su representación gráfica y en algunos casos, su representación en algún programa informático, así como en la memoria.

En este trabajo, traté de ser lo más breve posible explicando de manera muy sencilla los conceptos y algunas metodologías con un lenguaje no tan rebuscado para su mayor entendimiento.

GRAFOS

CONCEPTO.

Un grafo, G, es un par ordenado de V y A, donde V es el conjunto de vértices o nodos del grafo y A es un conjunto de pares de vértices, a estos también se les llama arcos o ejes del grafo. Un vértice puede tener 0 o más aristas, pero toda arista debe unir exactamente a dos vértices.

Los grafos representan conjuntos de objetos que no tienen restricción de relación entre ellos. Un grafo puede representar varias cosas de la realidad cotidiana, tales como mapas de carreteras, vías férreas, circuitos eléctricos, etc.

La notación G = A (V, A) se utiliza comúnmente para identificar un grafo.

Los grafos se constituyen principalmente de dos partes: las aristas, vértices y los caminos que pueda contener el mismo grafo.

Aristas

Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos.

Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une.

Si {a ,b} es una arista, a los vértices a y b se les llama sus extremos.

•Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice.

•Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo.

•Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.

•Cruce: Son dos aristas que cruzan en un punto.


Vértices

Son los puntos o nodos con los que esta conformado un grafo.

Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o `impar' según lo sea su grado.

•Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente.

•Vértice Aislado: Es un vértice de grado cero.

•Vértice Terminal: Es un vértice de grado 1.


Caminos

Sean x, y " V, se dice que hay un camino en G de x a y si existe una sucesión finita no vacía de aristas {x,v1}, {v1,v2},..., {vn,y}. En este caso

•x e y se llaman los extremos del camino

•El número de aristas del camino se llama la longitud del camino.

•Si los vértices no se repiten el camino se dice propio o simple.

•Si hay un camino no simple entre 2 vértices, también habrá un camino simple entre ellos.

•Cuando los dos extremos de un camino son iguales, el camino se llama circuito o camino cerrado.
•Llamaremos ciclo a un circuito simple

•Un vértice a se dice accesible desde el vértice b si existe un camino entre ellos. Todo vértice es accesible respecto a si mismo


CLASIFICACION DE GRAFOS

Podemos clasificar los grafos en dos grupos: dirigidos y no dirigidos. En un grafo no dirigido el par de vértices que representa un arco no está ordenado. Por lo tanto, los pares (v1, v2) y (v2, v1) representan el mismo arco. En un grafo dirigido cada arco está representado por un par ordenado de vértices, de forma que y representan dos arcos diferentes.

Ejemplos

G1 = (V1, A1)

V1 = {1, 2, 3, 4} A1 = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}

G2 = (V2, A2)

V2 = {1, 2, 3, 4, 5, 6} A2 = {(1, 2), (1, 3), (2, 4), (2, 5), (3, 6)}

G3 = (V3, A3)

V3 = {1, 2, 3} A3 = { <1,>, <2,>, <2,> }

Gráficamente estas tres estructuras de vértices y arcos se pueden representar de la siguiente manera:

Algunos de los principales tipos de grafos son los que se muestran a continuación:

•Grafo regular: Aquel con el mismo grado en todos los vértices. Si ese grado es k lo llamaremos k-regular.

•Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto

•Grafo completo: Aquel con una arista entre cada par de vértices. Un grafo completo con n vértices se denota Kn.

•Un grafo bipartito regular: se denota Km,n donde m, n es el grado de cada conjunto disjunto de vértices.

•Grafo nulo: Se dice que un grafo es nulo cuando los vértices que lo componen no están conectados, esto es, que son vértices aislados.

•Grafos Isomorfos: Dos grafos son isomorfos cuando existe una correspondencia biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan unidos por una arista en común.

•Grafos Platónicos: Son los Grafos formados por los vértices y aristas de los cinco sólidos regulares (Sólidos Platónicos), a saber, el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro.


GRAFOS EULERIANOS.

Para definir un camino euleriano es importante definir un camino euleriano primero. Un camino euleriano se define de la manera más sencilla como un camino que contiene todos los arcos del grafo.

Teniendo esto definido podemos hablar de los grafos eulerianos describiéndolos simplemente como aquel grafo que contiene un camino euleriano. Como ejemplos tenemos las siguientes imágenes:


GRAFOS CONEXOS.

Un grafo se puede definir como conexo si cualquier vértice V pertenece al conjunto de vértices y es alcanzable por algún otro. Otra definición que dejaría esto más claro sería: “un grafo conexo es un grafo no dirigido de modo que para cualquier par de nodos existe al menos un camino que los une”.