Download sílabo

FACULTAD DE INGENIERÍA INDUSTRIAL Y
DE SISTEMAS
SÍLABO
1. GENERALIDADES
1.1. Denominación de Asignatura
1.2. Código
1.3. Fecha de Aprobación
1.4. Aplicado en el Periodo
1.5. Versión
1.6. Autor
1.7. Régimen de Estudio
1.8. Obligatorio/Electivo
1.9. Área Académica/Escuela
1.10. Año Académico-Ciclo
1.11. Créditos
1.12. Total de horas semanales
1.13. Horas de Teoría
1.14. Horas Práctica/Laboratorio
1.15. Tipo de Evaluación
1.16. Pre-requisitos
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
Introducción a la Matemática Discreta
I115
enero de 2011
2011-1
3
CC-FIIS
Regular
Obligatorio (O)
Ciencias Matemáticas – Ingeniería de Sistemas
2011 – III Ciclo
04
05
03
02
B
M200-M101
2. SUMILLA
Inducción Matemática. Análisis combinatorio. Código BCD. Complemento a 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. Grafos dirigidos.
Grafos no-dirigidos. Trayectorias de Euler. Circuitos de Hamilton. Alg. De la fuerza
bruta. Árboles dirigidos. Árboles n-arios. Árboles binarios. Recorridos de un árbol.
Árboles no dirigidos. Árboles de expansión. Alg. De Prim y Kruskal. Alg. De la ruta más
corta de Dijkstra. Código Pre-Fijo. Código de Huffman. Alfabeto. Máquinas de estados
finitos.
3. OBJETIVOS
3.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. 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. 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 Máquinas de estado finito con aplicaciones prácticas.
3.2. OBJETIVOS ESPECÍFICOS
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.
1
3.2.3.
3.2.4.
3.2.5.
3.2.6.
3.2.7.
3.2.8.
3.2.9.
Los principios de la teoría de grafos con aplicaciones del Problema del
Agente viajero.
La teoría de árboles, búsqueda en árboles y optimización.
La teoría de Máquinas de estado finito.
La inducción matemática.
Las técnicas de conteo.
La Codificación y Decodificación del bit de Paridad par.
Códigos Prefijos y Código de Huffman para comprimir archivos.
4. LA METODOLOGÍA DE ENSEÑANZA
A 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 B
Asignaturas teóricos-prácticos de aula y/o laboratorio
El Promedio Final será:
PF =
Donde:
EP + 2 EF + PP
4
EP= Examen Parcial
EF= Examen Final
PP= Promedio de Prácticas
El número de prácticas es 5 (cinco). Se elimina 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á:
4
PP =
2
∑ Pi
i =1
4
6. UNIDADES Y CONTENIDOS TEMATICOS POR SESIÓN
6.1. PROGRAMA SEMANAL (CLASES)
SEMANA HORAS
TEMA
REFERENCIA
BIBLIOGRÁFICA
1
05
Primer Principio de la Inducción Matemática.
Grimaldi,
Análisis
combinatorio.
Principios Johnsonbaugh,
fundamentales de conteo: Las reglas de la Kolman
suma y del producto. Permutación.
2
05
Permutaciones de n elementos tomados de r Grimaldi,
en
r.
Permutaciones
con
repetición. Johnsonbaugh,
Permutación Circular. Combinación. Números Kolman
Combinatorios. Binomio de Newton.
3
05
Aritmética Modular.
Sistema Criptográfico con clave pública y
clave privada RSA.
4
05
5
05
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.
6
05
Definición general de un Algebra de Boole.
Morris
Mano,
Axiomas.
Ronald Tocci
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.
Compuertas lógicas: Compuertas OR, AND,
NOT, NAND, NOR, XOR (Or Exclusivo),
XNOR (Nor Exclusivo). Circuito Combinatorio.
Tablas de verdad de las Compuertas lógicas.
Propiedad: El OR EXCLUSIVO es asociativo.
.
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.
1ra. Práctica calificada
3
Morris Mano,
Ronald Tocci
Johnsonbaugh
Morris Mano,
Ronald Tocci
7
05
8
05
9
10
11
05
02
05
Repaso
Kolman
EXAMEN PARCIAL
Grafos Dirigidos: Grado Interno y Externo de
un Vértice. Trayectoria. Longitud de una Kolman, Grimaldi
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). Grafos dirigidos conexos.
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.
12
05
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.
3ra. Práctica calificada
Teorema sobre la interpretación de An y las
trayectorias de longitud n.
Circuitos de Euler. Teoremas de Euler para
grafos conexos no dirigidos y para grafos
conexos dirigidos: Condiciones necesarias y
suficientes para que exista una trayectoria
abierta de Euler y para que exista una
trayectoria cerrada de Euler.
13
05
14
05
Funciones Booleanas. Minitérmino.
Simplificación algebraica de funciones
Booleanas.
2da. Práctica calificada
Simplificación de funciones Booleanas usando
Mapas de Karnaugh de 2 y 3 variables.
Kenneth
Charles
Wright
RossR.B.
Kolman
Grimaldi,
Johnsonbaugh,
Kolman
Grimaldi,
Johnsonbaugh,
Kolman
Circuitos de Hamilton: Algoritmo de la Fuerza Grimaldi,
Bruta para grafos conexos no dirigidos. El Johnsonbaugh,
problema del agente viajero para un grafo no Kolman
dirigido completo de 4 y de 5 vértices.
Teorema de la condición suficiente para que
haya circuitos de Hamilton: Si el grado de
cada vértice es mayor ó igual a la mitad del
número de vértices entonces existe una
trayectoria cerrada de Hamilton.
4ta. Práctica calificada
4
15
05
16
05
17
05
18
05
19
20
02
02
Á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.
Á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.
Algoritmo para la ruta más corta de Dijkstra.
5ta. Práctica calificada
Árboles con peso. Árboles de expansión
mínimos:
Algoritmo de Robert Prim y Algoritmo Joseph
Kruskal.
Códigos Prefijos y Código de Huffman para
comprimir archivos.
Alfabeto. Cadena. Longitud. Concatenación.
Prefijo. Sufijo. Subcadena.
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.
Diagrama de estados. Aplicaciones de
Máquinas de Estados finitos: Máquina
expendedora de refrescos, Sumador binario.
EXAMEN FINAL
EXAMEN SUSTITUTORIO
5
Grimaldi,
Johnsonbaugh,
Kolman
Grimaldi,
Grimaldi
Grimaldi
7. BIBLIOGRAFIA
7.1 ROSEN, KENETH.
7.2
7.3
7.4
7.5
7.6
7.7
7.8
: Discrete mathematics and its applications. Editorial
Mc Graw Hill Higher Education. 2000
ROSEN, KENETH.
: Handbook
of
discrete
and
combinatorial
mathematics. Editorial CRC Press. 2000.
GRIMALDI, RALPH.
: Matemática discreta y combinatoria. 3ª edición.
Editorial Addison Wesley Longman. Pearson. 1998.
JOHNSONBAUGH,
: Matemáticas discretas. 5ª edición. Editorial
RICHARD.
Prentice Hall. Pearson. 2000.
TREMBLAY/
: Matemáticas discretas. 3ª edición. Editorial Addison
GROSSMAN.
Wesley Longman. Pearson. 1998.
KOLMAN / BUSBY / : Estructuras de matemáticas discretas para la
CUTLER / ROSS.
computación. Editorial Prentice Hall. Pearson.
1998.
MORRIS MANO
: Fundamentos de Diseño lógico para Computadoras.
Prentice Hall, ISBN: 0131755633, 3rd Edition, 1992
RONALD TOCCI
: Sistemas Digitales. Prentice Hall Hispanoamérica,
SA. 1997. 833 págs.
6