Formulario matemática discreta

Una sucesión es una lista ordenada de números, donde cada número se llama término. Se puede representar como, dondees un número entero positivo que indica la posición del término en la sucesión.

Definición

Una sucesión se define como:

Ejemplo: La sucesión de los números naturales:

Sucesiones aritméticas

Se caracterizan por tener una diferencia constante entre los términos consecutivos.

dondees la diferencia común.

Sucesiones geométricas

Se caracterizan por tener una razón constante entre los términos consecutivos.

dondees la razón común.

Sucesiones alternadas

Se caracterizan por alternar entre dos o más valores.

Ejemplo:produce la sucesión

Sucesiones monótonas

• Monótonas crecientes:
• Monótonas decrecientes:

Convergencia

Una sucesión converge a un límitesi, para cualquier, existe un número naturaltal que para todo:

Divergencia

Una sucesión diverge si no converge a un límite finito.

Una serie es la suma de los términos de una sucesión. Se denota generalmente comoy puede representarse de la siguiente manera:

Series finita

Suma de un número finito de términos.

Ejemplo:

Series infinita

Suma de infinitos términos. Se define como el límite de la suma de lostérminos a medida quetiende a infinito:

Series aritméticas

La suma de una serie aritmética se puede calcular con la fórmula:

dondees el-ésimo término.

Series geométricas

La suma de una serie geométrica, donde, se puede calcular como:

Series alternadas

Las series alternadas tienen términos que cambian de signo. Un criterio importante para la convergencia es el Criterio de Leibniz:

• Una serie alternadaconverge si:
  1. es monótona decreciente.
  2. .

Series de potencias

Una serie de potencias tiene la forma:

dondees el centro de la serie.

La convergencia se determina en el intervalo de convergencia, dado por el radio:

Teorema de convergencia de series

Una serieconverge si la sucesión de las sumas parcialesconverge a un límite.

Criterios de convergencia

• Criterio de la comparación: Siyconverge, entoncestambién converge.
• Criterio de raíz: Para:

Teorema de Abel

Siconverge yes monótonamente decreciente y converge a 0, entoncesconverge.

Divisibilidad

Números primos

Un númeroes primo si solo es divisible por 1 y por sí mismo.

Números compuestos

Un númeroes compuesto si tiene más de dos divisores.

Teorema de Fermat pequeño

Sies un número primo yes un entero tal que, entonces:

El Máximo Común Divisor (MCD) de dos o más números enteros es el mayor número entero que divide a todos esos números sin dejar residuo.

Para dos enterosy:

Propiedades del MCD

• no negatividad:.
• Intercambiabilidad:.
• Propiedad de la divisibilidad: Si, entoncesdivide a cualquier combinación lineal dey.

Algoritmo de Euclides

Para encontrar el MCD de dos númerosy:

El Mínimo Común Múltiplo de dos o más números enteros es el menor número entero positivo que es múltiplo de todos esos números.

Para dos enterosy:

Propiedades del MCM

• No negatividad:ysolo sio.
• Intercambiabilidad:.

Relación entre MCD y MCM

Congruencia modular

Propiedades

Siy, entonces:

Teorema Chino del resto

Sison números enteros primos entre sí de dos en dos, entonces para cualquier sistema de congruencias:

Existe una única solución, donde.

Conjunto

Una colección de elementos. Se denota generalmente por letras mayúsculas, como.

Elemento

Se denotasies un elemento del conjunto.

Unión

Intersección

Diferencia

Complemento

Conmutativa

Asociativa

Distributiva

Leyes de de Morgan

Un subconjunto del producto cartesiano.

Reflexiva

Simétrica

Antisimétrica

Transitiva

Composición de relaciones

Inversa de una relación

Grafo

, dondees el conjunto de vértices yes el conjunto de aristas.

Grado de un vértice

El número de aristas incidentes a un vértice, denotado.

Camino

Una secuencia de vérticesdonde cada par consecutivo.

Ciclo

Un camino donde el vértice inicial es igual al vértice final.

Suma de los Grados

En un grafo simple:

Grafo simple

Un grafo sin bucles ni aristas múltiples.

Grafo dirigido

Un grafo donde las aristas tienen una dirección (aristas orientadas).

Grafo completo

Un grafo en el que existe una arista entre cada par de vértices.

Búsqueda en profundidad (DFS)

Un algoritmo que explora tan profundo como sea posible en cada rama antes de retroceder

Búsqueda en anchura (BFS)

Un algoritmo que explora todos los vecinos de un vértice antes de moverse a los vértices vecinos de estos.

Un grafo es plano si puede ser dibujado en el plano sin que las aristas se crucen.

Fórmula de Euler

Para un grafo plano conectado convértices,aristas ycaras:

Grafo cúbico

Un grafo en el que todos los vértices tienen grado 3.

Teorema de Kuratowski

Un grafo no es plano si contiene un subgrafo que es una subdivisión deo.

Conjunción (AND)

es verdadero siyson verdaderos.

Disyunción (OR)

es verdadero si al menos uno deoes verdadero.

Negación (NOT)

es verdadero sies falso.

Implicación

Doble Implicación (Equivalencia)

Identidad

Idempotente

Conmutativa

Asociativa

Distributiva

Leyes de De Morgan

Una recurrencia es una ecuación que define una secuencia en términos de sus valores anteriores. Existen diferentes métodos para resolverlas:

1. Adivinar la solución de la recurrencia.
2. Usar inducción matemática para verificar la solución.

Ejemplo:

Adivinamos que la solución es.

Expandimos la recurrencia sustituyendo recursivamente en sí misma hasta alcanzar el caso base.

Ejemplo:

Expandiendo:

Continuamos hasta llegar al caso base y sumamos los términos.

1. Dibujamos el árbol de recursión para visualizar el costo en cada nivel.
2. Calculamos el costo total sumando los costos en todos los niveles del árbol.

Ejemplo (continuación del anterior):

El árbol tieneniveles, y en cada nivel el costo es proporcional a, por lo que el costo total es.

Este teorema se aplica a recurrencias de la forma:

Donde:

El comportamiento asintótico de la solución es:

• Si, entonces.
• Si, entonces.
• Si, entonces.

Ejemplo:

Aquí,,, y. Como, el resultado es.

Una recurrencia lineal homogénea es de la forma:

Tienen la forma:

La solución es la suma de la solución de la parte homogénea más una solución particular para.

Complejidad

Temporal Medida del tiempo que un algoritmo toma para ejecutar en función del tamaño de la entrada.

Complejidad espacial

Medida de la cantidad de memoria que un algoritmo necesita en función del tamaño de la entrada.