Matemática discreta y Algoritmos - Julio M.Pérez

CAPÍTULO 1. GENERALIDADES

1.1. Introducción

1.2. Algoritmos

1.3. Diagramas de algoritmos. Estructuras de  decisión SI, SI NO. Estructuras

       de repetición condicional MIENTRAS HACER y REPETIR HASTA QUE.

       Estructuras de repetición incondicional PARA HASTA

1.4. Métodos de demostración. Demostración directa. Demostración por el

       absurdo. Demostración por contraejemplo o contraprueba. Demostración por

       inducción

1.5. Métodos de contar. El principio de la multiplicación. Extracción de muestras

       con orden y reemplazo. Extracción de muestras con orden y sin reemplazo

       (permutaciones, variaciones o disposiciones). Extracción de muestras sin

       orden y sin reemplazo. Extracción de muestras sin orden y con reemplazo

1.6. Expansión de fracciones continuas simples

1.7. Coeficientes binomiales. Triángulo de Pascal o Tartaglia

1.8. Ejercicios

CAPÍTULO 2. CONJUNTOS Y LÓGICA

2.1. Introducción

2.2. Relaciones entre conjuntos

2.3. Operaciones con conjuntos

2.4. Conjunto potencial, producto cartesiano y pares ordenados

2.5. Relaciones y funciones

2.6. Lógica proposicional

2.7. Reglas de inferencia y cuantificadores

2.8. Ejercicios

CAPÍTULO 3. COMPLEJIDAD DE LOS ALGORITMOS 

3.1. Introducción 

3.2. Función orden de magnitud 

3.3. Comparación de ordenes de magnitud

3.4. Función techo y piso 

3.5. Estudio de la complejidad de algoritmos 

3.6. Longitud de números. Complejidad de operaciones 

3.7. Clases P y NP 

3.8. Ejercicios                                                                        

CAPÍTULO 4. DIVISIBILIDAD, NÚMEROS PRIMOS Y RELACIONES DE RECURRENCIA 

4.1. Introducción 

4.2. Máximo común divisor 

4.3. Algoritmo de Euclides 

4.4. Números primos 

4.5. Relaciones de recurrencia homogéneas 

4.6. Relaciones de recurrencia no homogéneas 

4.7. Algoritmos recurrentes o recursivos. Algoritmo recursivo para el cálculo del

      factorial. Las Torres de Hanoi. Los números de Fibonacci

4.8. Ejercicios  

CAPÍTULO 5. CONGRUENCIAS Y CRIPTOGRAFÍA 

5.1. Introducción 

5.2. Propiedades de la congruencia módulo m 

5.3. Teorema chino del resto 

5.4. Teorema de Fermat y generalizado de Euler 

5.5. Potencias y raíces módulo m 

5.6. Criptografía por clave pública  

5.7. Números pseudoaleatorios 

5.8. Ejercicios   

CAPÍTULO 6. TEORÍA DE GRAFOS 

6.1. Introducción 

6.2. Planaridad y dualidad 

6.3. Matrices asociadas a grafos 

6.4. Grafos eulerianos y hamiltonianos 

6.5. Grafos ponderados 

6.6. Algoritmo de Kruskal 

6.7. Redes de flujo 

6.8. Algoritmo de Ford Fulkerson

6.9. Ejercicios 

CAPÍTULO 7. ÁRBOLES, ÁRBOLES BINARIOS Y ENRAIZADOS 

7.1. Introducción 

7.2. Árboles enraizados 

7.3. Árboles binarios 

7.4. Ordenamiento en árbol binario 

7.5. Cantidad de árboles binarios de n vértices 

7.6. Ejemplo de aplicación al caso de codificación 

7.7. Árboles B

7.8. Ejercicios 

CAPÍTULO 8. MÁQUINAS DE ESTADOS FINITOS Y AUTÓMATAS 

8.1. Máquina de estados finitos 

8.2. Autómata de estados finitos 

8.3. Nociones de lenguajes y su relación con autómatas 

8.4. Máquina de Turing 

8.5. Ejercicios 

CAPÍTULO 9. APLICACIONES INFORMÁTICAS 

9.1. Introducción 

9.2. Multiplicación de grandes números 

9.3. Cálculo en paralelo 

9.4. Función de “hash” o de dispersión 

9.5. Ordenamiento. Ordenamiento por intercambio o burbuja (bubble sort).

       Ordenamiento por inserción directa.. Ordenamiento por mezcla (merge sort).

       Ordenamiento rápido (quicksort) 

9.6.Ejercicios 

CAPITULO 10. LÓGICA COMBINACIONAL Y LÓGICA SECUENCIAL 

10.1. Introducción 

10.2. Funciones lógicas 

10.3. Formas canónicas 

10.4. Reducción sistemática 

10.5. Lógica combinacional 

10.6. Lógica secuencial

10.7. Ejercicios 

CAPÍTULO 11. CUERPOS FINITOS Y APLICACIONES 

11.1. Introducción 

11.2. Anillos y cuerpos 

11.3. Polinomios 

11.4. Secuencias recursivas lineales  

11.5. Codificación 

11.6. Ejercicios  

ANEXO A. NUMEROS PRIMOS 

Tabla de números primos hasta el 20030 

ANEXO B. POLINOMIOS IRREDUCIBLES Y PRIMITIVOS 

Polinomios irreducibles módulo 2 

Polinomios irreducibles módulo 3

Polinomios irreducibles módulo 5 

Polinomios irreducibles módulo 7 

Primeros 85 polinomios primitivos sobre F2 

ANEXO C. SISTEMAS DE NUMERACIÓN 

Historia. 

Bases binaria, octal, decimal y hexadecimal. BCD 

Coma o punto flotante. Su representación 

ANEXO D. ÁLGEBRA MATRICIAL 

Álgebra matricial

ANEXO E. EJERCICIOS RESUELTOS

Ejercicios Capítulos 1 al 11 

  Volver