matematica discreta sialbus

SÍLABO

1. GENERALIDADES1.1. Denominación de Asignatura : Introducción a la Matemática

Discreta1.2. Código : I1151.3. Fecha de Aprobación : 02/01/061.4. Aplicado en el Periodo : 2006-II1.5. Versión : 21.6. Autor : CC-FIIS1.7. Régimen de Estudio : Regular1.8. Obligatorio/Electivo : Obligatorio (O)1.9. Área Académica/Escuela : Ciencias Matemáticas – Ingeniería de

Sistemas1.10.Año Académico-Ciclo : 2006 – III Ciclo1.11.Créditos : 041.12.Total de horas semanales : 051.13.Horas de Teoría : 031.14.Horas Práctica/Laboratorio : 021.15.Tipo de Evaluación : B1.16.Pre-requisitos : M200-M101

2. SUMILLAInducción Matemática. Análisis combinatorio. Código BCD. Complemento a 2 en base 2. Sumas y Restas de números enteros (positivos y negativos) usando el Complemento a 2. Codificación y Decodificación del bit de Paridad par. Aritmética Modular. Sistema Criptográfico con clave pública y clave privada RSA. Algebra de Boole. Definiciones recursivas. Relaciones de recurrencia. Relaciones. Grafos dirigidos. Circuitos de Euler. Circuitos de Hamilton. Árboles dirigidos. Árboles n-arios. Árboles binarios. Recorridos de un árbol. Árboles no dirigidos. Alfabeto. Máquinas de estados finitos.

3. OBJETIVOS3.1. OBJETIVOS GENERALES

El estudiante tendrá las herramientas necesarias para continuar los cursos en los cuales el presente curso sea considerado como requisito. Así mismo el estudiante estará en capacidad de manejar con eficiencia los conceptos de la Matemática Discreta en diversas áreas: Lógica. Relaciones. Inducción Matemática. Los números en relación de las aplicaciones modernas de la Criptografía en la seguridad de la información. Análisis combinatorio. Relaciones de recurrencia. La teoría de grafos y árboles los cuales servirá para el entendimiento y la utilización en los distintos tipos de sistemas, aplicaciones de software y búsqueda en árboles, optimización; circuitos digitales, Redes, Redes eléctricas, sistemas de Control. La Codificación y Decodificación Bit de paridad utilizados en telecomunicaciones para los procesos de transmisión digital. La Teoría de Lenguajes y Máquinas de estado finito con aplicaciones prácticas.

3.2. OBJETIVOS ESPECÍFICOS

1

FACULTAD DE INGENIERÍA INDUSTRIAL Y DE SISTEMAS

Al finalizar el curso el estudiante estará en capacidad de entender, analizar y estudiar:

3.2.1. Las técnicas de Criptografía utilizada en la seguridad de las comunicaciones.

3.2.2. El Álgebra de Boole y sus aplicaciones en los circuitos digitales.3.2.3. Los principios de la teoría de grafos con aplicaciones del

Problema del Agente viajero.3.2.4. La teoría de árboles, búsqueda en árboles y optimización.3.2.5. La teoría de Lenguajes y Máquinas de estado finito.3.2.6. La inducción matemática.3.2.7. Las técnicas de conteo.3.2.8. La teoría de relaciones con sus aplicaciones a gráficas, árboles

y redes.3.2.9. Las relaciones de recurrencia.3.2.10. La Codificación y Decodificación del bit de Paridad par.

4. LA METODOLOGÍA DE ENSEÑANZAA fin de que el estudiante pueda participar activamente en el desarrollo del curso se plantea lo siguiente:4.1. Medios. Las clases teóricas y prácticas se dictarán en el aula con

participación de los alumnos. Además se incentivará a la investigación con la propuesta de trabajos dirigidos.

4.2. Materiales. Se utilizará semanalmente ejercicios de desarrollo y la bibliografía adecuada debidamente actualizada.

5. EVALUACIÓN DE APRENDIZAJE: TIPO BAsignaturas teóricos-prácticos de aula y/o laboratorioEl Promedio Final será:

Donde:

EP= Examen ParcialEF= Examen FinalPP= Promedio de Prácticas

El número mínimo de prácticas es 5 (cinco). Puede eliminarse la nota más baja de las cinco notas obtenidas.

El promedio de prácticas de las Asignaturas tipo B se determina en función de las prácticas desarrolladas en las horas asignadas para este fin.

La programación de estas prácticas debe comprender:

2 prácticas de Aula antes del Examen Parcial 3 prácticas de Aula antes del examen Final

Entonces, el promedio de Práctica será:

2

6. UNIDADES Y CONTENIDOS TEMATICOS POR SESIÓN6.1. PROGRAMA SEMANAL (CLASES)

SEMANA

HORAS

TEMAREFERENCIA

BIBLIOGRÁFICA1 03 Inducción Matemática. Análisis

combinatorio. Principios fundamentales de conteo: Las reglas de la suma y del producto. Permutación.

Grimaldi, Johnsonbaugh, Kolman

2 03 Permutaciones de n elementos tomados de r en r. Permutaciones con repetición. Permutación Circular. Combinación. Números Combinatorios. Binomio de Newton.


3 03 Resumen de Sistemas de Numeración. Conversión para números enteros entre las bases 10, 2, 8 y 16. Sumas y restas en las bases 2, 8 y 16.Código BCD. Complemento a 2 en base 2. Sumas y Restas de números enteros (positivos y negativos) usando el Complemento a 2.Codificación y Decodificación del bit de Paridad par. Casos en los cuales se puede detectar el error y casos en los cuales no se puede detectar el error. .

Morris Mano, Ronald Tocci

4 03 Aritmética Modular. Sistema Criptográfico con clave pública y clave privada RSA.

Johnsonbaugh

5 03 Definición general de un Algebra de Boole. Axiomas. El Álgebra de Boole aplicado al conjunto {0,1}: La lógica binaria y las operaciones Booleanas. Suma, Producto y Complemento. Expresión Booleana. El Dual de una expresión Booleana. Propiedades del Álgebra de Boole.


6 03 Compuertas lógicas: Compuertas OR, AND, NOT, NAND, NOR, XOR (Or Exclusivo), XNOR (Nor Exclusivo). Tablas de verdad de las Compuertas lógicas. Propiedad: El OR EXCLUSIVO es asociativo. Circuito


3

Combinatorio.Funciones Booleanas. Minitérmino. Simplificación algebraica de funciones Booleanas. Simplificación de funciones Booleanas usando Mapas de Karnaugh de 2 y 3 variables.

7 03 -Definiciones recursivas-Relaciones de recurrencia lineal homogénea de 1er. y 2do. orden de coeficientes constantes. Casos: Raíces reales distintas y raíces reales diferentes. -Definiciones generales de recursión.

Kenneth Ross-Charles R.B. Wright

8 03 Relaciones. Representación matricial y Digráfica de una Relación. Vértice, arista, lazo. Clases de Relaciones: Reflexiva. Irreflexiva. Simétrica, Antisimétrica, Asimétrica, transitiva, Relación de Equivalencia, Orden Parcial y Orden Total.

Kolman

9 03 Multiplicación Booleana de matrices A B . Matriz de la Composición de Relaciones.Grafos Dirigidos: Grado Interno y Externo de un Vértice. Trayectoria. Longitud de una trayectoria. Trayectoria abierta. Trayectoria cerrada (Circuito ó Ciclo). Trayectoria Simple (Trayectoria en donde no se repite ningún vértice a excepción del primero y el último que pueden ser iguales).

Kolman

10 02 EXAMEN PARCIAL11 03 Grafos no dirigidos.

Definición G= (V, A, f). V: Conjunto de vértices, A: Conjunto de aristas, f: La función que asigna a cada arista un par de vértices. Lazo. Aristas paralelas. Grado de un vértice. Trayectorias: Abierta, Cerrada y Simple. Longitud de una trayectoria.Subgrafos. Grafos Conexos y Disconexos. Puente. Componentes de una gráfica. Gráfica Discreta. Gráfica Completa y Gráfica Lineal. Matriz de adyacencia A de un grafo. Teorema sobre la interpretación de An y las trayectorias de longitud n.

Kolman, Grimaldi

12 03 Circuitos de Euler. Teoremas de Euler: Condiciones necesarias y suficientes para que exista una trayectoria abierta de Euler y para que exista una trayectoria cerrada de Euler.Circuitos de Hamilton: Algoritmo de la


4

Fuerza Bruta. El problema del agente viajero para un grafo no dirigido completo de 4 y de 5 vértices.

13 03 Árboles dirigidos. Raíz de un árbol, hijos, hojas, nivel, Altura de un árbol. Sub Árbol.Árboles n-arios. Árboles binarios. Recorridos de un árbol. Recorridos Pre- Orden y Post-Orden. Notación Infija, Polaca y Polaca inversa.


14 03 Árboles no dirigidos. Árboles de expansión de un grafo no dirigido conexo. Determinación de un árbol de expansión mediante el método de búsqueda a lo ancho. La ruta más corta para ir de un vértice a otro en un grafo conexo sin pesos.Árboles con peso. Árboles de expansión mínimos: Algoritmo de Robert Prim y Algoritmo Joseph Kruskal.


15 03 Algoritmo para la ruta más corta de Dijkstra.Códigos Prefijos y Código de Huffman para comprimir archivos.


16 03 Alfabeto. Cadena. Longitud. Concatenación. Prefijo. Sufijo. Subcadena. Lenguajes. Máquinas de estados finitos. M = (S, I, O, v, w), S: conjunto de estados internos, I: Alfabeto de entrada, O: Alfabeto de salida, v: Función siguiente estado, w: Función de salida.

Grimaldi,

17 03 Diagrama de estados. Aplicaciones de Máquinas de Estados finitos.

Grimaldi

18 03 Exposición de los trabajos de Investigación

19 02 EXAMEN FINAL20 02 EXAMEN SUSTITUTORIO

6.2. PROGRAMA SEMANAL (PRÀCTICAS)

SEMANA

HORAS

TEMATIPO DE

PRÁCTICA1 02 Inducción Matemática. Análisis

combinatorio. Principios fundamentales de conteo: Las reglas de la suma y del

Dirigida

5

producto. Permutación.

2 02 Permutaciones de n elementos tomados de r en r. Permutaciones con repetición. Permutación Circular. Combinación. Números Combinatorios. Binomio de Newton.

Dirigida

3 02 Sumas y restas en las bases 2, 8 y 16.Código BCD. Complemento a 2 en base 2. Sumas y Restas de números enteros (positivos y negativos) usando el Complemento a 2.Codificación y Decodificación del bit de Paridad par.

Dirigida

4 02 Aritmética Modular. Sistema Criptográfico con clave pública y clave privada RSA.

Dirigida

5 02 1ra. Práctica Calificada : Inducción Matemática, Análisis Combinatorio, Complementos, Codificación y Decodificación del Bit de Paridad.

1ra. Práctica Calificada

6 02 Simplificación algebraica de funciones Booleanas. Simplificación de funciones Booleanas usando Mapas de Karnaugh de 2 y 3 variables.

Dirigida

7 02 -Definiciones recursivas-Relaciones de recurrencia lineal homogénea de 1er. y 2do. orden de coeficientes constantes. Casos: Raíces reales distintas y raíces reales diferentes. -Definiciones generales de recursión.

Dirigida

8 02 2da. Práctica Calificada: Sistema Criptográfico RSA, Algebra de Boole, Definiciones recursivas y Relaciones de Recurrencia

2da. Práctica Calificada:

9 02 Matriz de la Composición de RelacionesTrayectorias y Longitud de una trayectoria.

Dirigida

10 02 EXAMEN PARCIAL11 02 Grafos no dirigidos.

G= (V, A, f). Lazo. Aristas paralelas. Grado de un vértice. Trayectorias: Abierta, Cerrada y Simple. Longitud de una trayectoria.Subgrafos. Grafos Conexos y Disconexos. Puente. Gráfica Discreta. Gráfica Completa y Gráfica Lineal. Matriz de adyacencia y las trayectorias de longitud n.

Dirigida

6

12 02 3ra. Práctica Calificada: Relaciones, Grafos dirigidos y Grafos no Dirigidos, Matriz de Adyacencia y trayectorias de longitud n.

3ra. Práctica Calificada

13 02 Árboles dirigidos. Árboles n-arios. Árboles binarios. Recorridos de un árbol. Recorridos Pre- Orden y Post-Orden. Notación Infija, Polaca y Polaca inversa.

Dirigida

14 02 Árboles no dirigidos. Determinación de un árbol de expansión mediante el método de búsqueda a lo ancho. La ruta más corta para ir de un vértice a otro en un grafo conexo sin pesos.Árboles con peso: Árboles de expansión mínimos: Algoritmo de Robert Prim y Algoritmo Joseph Kruskal.

Dirigida

15 02 4ta. Práctica Calificada: Circuitos de Euler. Circuitos de Hamilton, Árboles dirigidos, Recorridos de un Árbol.Árboles no dirigidos, La ruta más corta para ir de un vértice a otro en un grafo conexo sin pesos.Árboles con peso: Árboles de expansión mínimos: Algoritmo de Robert Prim y Algoritmo Joseph Kruskal.

4ta. Práctica Calificada

16 02 Alfabeto. Cadena. Longitud. Concatenación. Prefijo. Sufijo. Subcadena. Lenguajes. Máquinas de estados finitos. M = (S, I, O, v, w), S: conjunto de estados internos, I: Alfabeto de entrada, O: Alfabeto de salida, v: Función siguiente estado, w: Función de salida.

Dirigida

17 02 Diagrama de estados. Aplicaciones de Máquinas de Estados finitos.

Dirigida

18 02 5ta. Práctica Calificada:Exposición de los Trabajos de Investigación

5ta. Práctica Calificada

19 02 EXAMEN FINAL20 02 EXAMEN SUSTITUTORIO

7. BIBLIOGRAFIA

7

/tt/file_convert/5525cd8f550346a76e8b49c7/document.doc

8

7.1

ROSEN, KENETH. : Discrete mathematics and its applications. Editorial Mc Graw Hill Higher Education. 2000

7.2

ROSEN, KENETH. : Handbook of discrete and combinatorial mathematics. Editorial CRC Press. 2000.

7.3

GRIMALDI, RALPH. : Matemática discreta y combinatoria. 3ª edición. Editorial Addison Wesley Longman. Pearson. 1998.

7.4

JOHNSONBAUGH, RICHARD.

: Matemáticas discretas. 5ª edición. Editorial Prentice Hall. Pearson. 2000.

7.5

TREMBLAY/ GROSSMAN.

: Matemáticas discretas. 3ª edición. Editorial Addison Wesley Longman. Pearson. 1998.

7.6

KOLMAN / BUSBY / CUTLER / ROSS.

: Estructuras de matemáticas discretas para la computación. Editorial Prentice Hall. Pearson. 1998.

7.7

MORRIS MANO : Fundamentos de Diseño lógico para Computadoras. Prentice Hall, ISBN: 0131755633, 3rd Edition, 1992

7.8

RONALD TOCCI : Sistemas Digitales. Prentice Hall Hispanoamérica, SA. 1997. 833 págs.

matematica discreta sialbus

Documents