INTRODUCCION

Matemáticas Discretas es la parte de la matemática encargada del estudio de los conjuntos discretos: finitos o infinitos numerables.
En oposición a la matemática continua, que se encarga del estudio de conceptos como la continuidad y el cambio continuo, la matemática discreta estudia estructuras cuyos elementos pueden contarse uno por uno separadamente. Es decir, los procesos en matemática discreta son finitos y contables.
Mientras que el cálculo es primordial en el estudio de procesos analógicos, la matemática discreta es la base de todo lo relacionado con los procesos digitales, y por tanto, se constituye en parte fundamental de la ciencia de la computación, una de las ramas de estudio impartidas en los estudios de Ingeniería Informática.
Generalmente se incluyen los siguientes temas de estudio:
• Lógica proposicional
• Teoría de la computabilidad
• Teoría de complejidad computacional
• Teoría de conjuntos
• Teoría de grupos
• Teoría de grafos
• Teoría de autómatas finitos
• Combinatoria y nociones de probabilidad
• Análisis de ciertos algoritmos
• Teoría de la información

Las matemáticas discretas, a diferencia del cálculo infinitesimal, estudia procesos con conjuntos contables o numerables, ya sean finitos o infinitos.
Su entorno de trabajo son los números naturales o los enteros:
N = { 1,2,3,... }
Z = { ..., -3,-2,-1,0,1,2,...}
Esto a raíz de que los objetos en matemáticas discretas son contables, ya sean finitos o infinitos, es decir, se pueden contar de uno en uno por separado.
La clave en matemáticas discretas es que no es posible manejar, al igual que en el cálculo, las ideas de proximidad o límite y suavidad en las curvas. Por ejemplo, en matemáticas discretas una incógnita puede ser 2 o 3, pero nunca te aproximarás a 3 por la izquierda con 2.9, 2.99, 2.999, etc. Las gráficas en matemáticas discretas vienen dadas por un conjunto finito de puntos que puedes contar por separado, mientras que las gráficas en cálculo son trazos continuos de rectas o curvas.
La idea clave del cálculo es el límite y su entorno son los números reales. Sus variables son continuas o analógicas.
La idea clave en matemáticas discretas es el conjunto numerable y su entorno son los números enteros. (Los naturales son un subconjunto de los enteros). Sus variables son discretas o digitales.
Estudios recientes confirman que la mente de los individuos se orienta más hacia alguna de las dos tendencias: a la matemática discreta o a la matemática de la continuidad y el cambio, es decir, al cálculo.
No se puede decir que alguna de las dos sea más fácil, pues el nivel de complejidad de ambas materias es sumamente elevado. Sin embargo, parece que ha tenido más preponderancia hasta la década del 90 el cálculo y ahora se estudian más las matemáticas discretas como una tendencia reciente, especialmente por la computación digital y la informática.

Algoritmo

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) es un conjunto preescrito de intruccciones o reglas bien definida, ordenada y finita que permite realizar una actividad específica mediante pasos sucesivos que no generen dudas a quien lo ejecute. Dado un estado inicial y una entrada, a través de lo mencionados pasos sucesivos se llega a un estado final, obteniendo una solución. Los algoritmos son objeto de estudio de la algoritmia.

En la vida cotidiana se emplean algoritmos en multitud de ocasiones para resolver diversos problemas. Algunos ejemplos se encuentran en los instructivos (manuales de usuario), los cuales muestran algoritmos para usar el aparato en cuestión o incluso en las instrucciones que recibe un trabajador por parte de su patrón. También existen ejemplos de índole matemática, como el algoritmo de la división para calcular el cociente de dos números, el algoritmo de Euclides para calcular 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). 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.

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. 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. 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:
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. 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):

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:

1.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.
2.Descripción formal. Se usa pseudocódigo para describir la secuencia de pasos que encuentran la solución.
3.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

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.

Aplicabilidad De Las Matemàticas Discretas En La Ing. 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.

Teoria De Árboles y Gráfos

Grafo
Un grafo es una pareja de conjuntos G = (V, A), donde V es el conjunto de vértices, y A es el conjunto de aristas.

En teoría de grafos, sólo queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importa a qué vértices están unidas. La posición de los vértices tampoco importa, y se puede variar para obtener un dibujo más claro.
Muchas redes de uso cotidiano pueden ser modeladas con un grafo: una red de carreteras que conecta ciudades, una red eléctrica o la red de drenaje de una ciudad.

Sub grafo
Un subgrafo de un grafo G es un grafo cuyos conjuntos de vértices y aristas son subconjuntos de los de G. Se dice que un grafo G contiene a otro grafo H si algún subgrafo de G es H o es isomorfo a H (dependiendo de las necesidades de la situación).
El subgrafo inducido de G es un subgrafo G' de G tal que contiene todas las aristas adyacentes al subconjunto de vértices de G.
Definición:
Sea G= (V, A). G’= (V’, A’) se dice subgrafo de G si:
1- V’ V
2- A' A
3- (V’, A’) es un grafo
• Si G’=(V’,A’) es subgrafo de G, para todo v G se cumple gr (G’,v)≤ gr (G, v)

Caracterización de grafos
Grafos simples
Un grafo es simple si a lo sumo sólo 1 arista une dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos.
Un grafo que no es simple se denomina Multigráfica o Grafo múltiple.
Grafos conexos
Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b.
Un grafo es fuertemente conexo si cada par de vértices está conectado por al menos dos caminos disjuntos; es decir, es conexo y no existe un vértice tal que al sacarlo el grafo resultante sea disconexo.
Grafos completos
Un grafo es completo si existen aristas uniendo todos los pares posibles de vértices. Es decir, todo par de vértices (a, b) debe tener una arista e que los une.
El conjunto de los grafos completos es denominado usualmente , siendo el grafo completo de n vértices.
Homeomorfismo de grafos
Dos grafos G1 y G2 son homeomorfismo si ambos pueden obtenerse a partir del mismo grafo con una sucesión de subdivisiones elementales de aristas.

Grafos planos
Cuando un grafo o multigrafo se puede dibujar en un plano sin que dos segmentos se corten, se dice que es plano.

ARBOL
Un grafo que no tiene ciclos y que conecta a todos los puntos, se llama un árbol. En un grafo con n vértices, los árboles tienen exactamente n - 1 aristas, y hay nn-2 árboles posibles. Su importancia radica en que los árboles son grafos que conectan todos los vértices utilizando el menor número posible de aristas. Un importante campo de aplicación de su estudio se encuentra en el análisis filogenético, el de la filiación de entidades que derivan unas de otras en un proceso evolutivo, que se aplica sobre todo a la averiguación del parentesco entre especies; aunque se ha usado también, por ejemplo, en el estudio del parentesco entre lenguas.

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 cualesquiera de G están conectados por un único camino simple.