Guia de estudios para el examen de admisión Ciencias Computacionales 2008

Los exámenes de selección para ingresar al programa de Maestría en Ciencias de la Computación son dos: Matemáticas y Programación. En los siguientes párrafos se encuentra una guía de estudio para cada uno de estos exámenes

Guía para matemáticas

El examen de matemáticas incluirá preguntas y problemas sobre los temas que se muestran a continuación:

1. 1. Introducción a la Lógica.
2. 1.1 Proposiciones.
   1. 1.1.1 Conectivas.
   2. 1.1.2 Fórmulas proposicionales y tablas de verdad.
   3. 1.1.3 Condicional y bicondicional.
   4. 1.1.4 Tautologías.
   5. 1.1.5 Equivalencia de fórmulas.
   6. 1.1.6 Ley de dualidad.
   7. 1.1.7 Implicaciones tautológicas.
   8. 1.1.8 Validación usando tablas de verdad.
3. 1.2 La teoría de inferencia para el cálculo proposicional.
   1. 1.2.1 Validación usando tablas de verdad.
   2. 1.2.2 Reglas de inferencia.
   3. 1.2.3 Consistencia de premisas y el método indirecto de demostración.
   4. 1.2.4 Cláusulas de Horn y principio de resolución.
4. 1.3 El cálculo de predicados.
   1. 1.3.1 Predicados.
   2. 1.3.2 La función proposicional, variables y cuantificadores.
   3. 1.3.3 Fórmulas de predicados.
   4. 1.3.4 Variables libres y acotadas.
   5. 1.3.5 El universo (contexto) del discurso.
   6. 1.3.6 Negación de formulas que contienen cuantificadores.
   7. 1.3.7 El empleo de predicados en matemáticas y en computación.
5. 2. Conjuntos y relaciones.
   1. 2.1 Conjuntos y subconjuntos.
   2. 2.2 Conjunto potencia.
   3. 2.3 Álgebra de conjuntos.
   4. 2.4 Relación entre el álgebra de conjuntos y el álgebra de proposiciones.
   5. 2.5 Pares ordenados y n-adas ordenadas.
   6. 2.6 Producto cartesiano.
   7. 2.7 Relaciones.
      1. 2.7.1 Relaciones binarias y propiedades.
         1. 2.7.1.1 Particiones.
      2. 2.7.2 Representación matricial y gráfica de una relación.
      3. 2.7.3 Relación de equivalencia.
      4. 2.8 Relaciones de orden parcial y representación.
6. 3. Funciones.
   1. 3.1 Función inyectiva.
   2. 3.2 Función sobreyectiva.
   3. 3.3 Función biyectiva.
   4. 3.4 Composición de funciones.
   5. 3.5 Función inversa.
   6. 3.6 Función característica de un conjunto.
7. 4. Inducción.
   1. 4.1 Números naturales.
   2. 4.2 Inducción matemática.
      1. 4.2.1 Ejemplos de teoremas demostrados por inducción.
8. 5. Introducción al álgebra lineal.
   1. 5.1 Ecuaciones lineales.
   2. 5.2 Operaciones de matrices: suma, multiplicación, inversa, transpuesta.
   3. 5.3 Representación de transformaciones lineales por matrices.
   4. 5.4 Transpuesta de transformación lineal.
   5. 5.5 Valores propios y polinomios característicos.

Bibliografía.

• Kenneth H. Rosen, "Discrete Mathematics and its Applications", 3era. ed., Mc GrawHill, Inc., New York, ISBN 0-07-113974-5, 1995.
• Kenneth A. Ross y Charles R. B. Wright, "Matemáticas Discretas", 2da. ed., Prentice Hall, ISBN 968-880-180-1, México, 1990.
• Richard Johnsonbauugh, "Matemáticas Discretas", 4ta. ed., Prentice Hall, ISBN 970-17-0253-0, México, 1990.
• Winfried Karl Grassmann y Jean Paul Tremblay, "Matemática Discreta y Lógica", Prentice Hall, ISBN 84-89660-04-2, Madrid, España, 1997.
• Jean-Paul Tremblay y Raun Manohar, "Matemáticas Discretas, con Aplicación a las Ciencias de la Computación", 1ra. ed. en español, Compañía Editorial Continental S.A. de C.V. (CECSA), ISBN 0-07-065142-6, 1ra. reimpresión, México, 1999.

Guía para programación

El examen de programación consistirá en escribir un programa en papel para cada uno de los problemas del examen. Cada programa deberá escribirse usando el lenguaje que se describe a continuación.

Descripción del lenguaje de programación.

El lenguaje cuenta con los siguientes tipos de datos simples: enteros, carácter y real. Además, en el lenguaje también se pueden usar variables con el tipo de datos estructurado arreglo, éste debe declararse en los comentarios definiendo el límite inferior y el superior. Las variables de tipos de dato simples no necesitan ser definidos, ya que el tipo se sobreentiende en las operaciones realizadas con las variables. Los operadores básicos son los siguientes:

Nota: los operadores lógicos y de comparación sólo pueden regresar valores de False o True (éstas son constantes definidas en el lenguaje).

Las instrucciones de entrada/salida son las siguientes:

• input (una o más varibles).
• output (una o más varibles, [constantes de texto]).

Las instrucciones de control son las siguientes (las palabras reservadas están en negritas):

• Instrucción de decisión simple:
  • if condición then de una a varias instrucciones
  • else de una a varias instrucciones

  o también:

  • if condición then de una a varias instrucciones

• Instrucción de decisión múltiple:
  • case
    • : condición 1: de una a varias instrucciones
    • : condición 2: de una a varias instrucciones
    • . . .
    • : condición N: de una a varias instrucciones
    • else de una a varias instrucciones
  • end

• Instrucción de iteración de 0 a N veces:
  • while condición do
    • de una a varias instrucciones
  • end

• Instrucción de iteración de 1 a N veces:
  • repeat
    • de una a varias instrucciones
  • until condición

• Instrucción de iteración sin final explícito:
  • loop
    • de una a varias instrucciones
    • if condición then exit
    • de una a varias instrucciones
  • forever

• Instrucción de iteración de M a N veces:
  • for variable <- M to N by incremento do
    • de una a varias instrucciones
  • end

La instrucción para definir un programa es la siguiente:

• Program nombre_del_programa
  • de una a varias instrucciones
• end

Además, el lenguaje cuenta con la capacidad de definir procedimientos de la siguiente manera:

• Procedure nombre_del_procedimiento(lista de parámetros por valor)
  • de una a varias instrucciones
• end

Los procedimientos también pueden trabajar como funciones de la siguiente manera:

• Procedure nombre_del_procedimiento(lista de parámetros por valor)
  • de una a varias instrucciones
  • return(expresión)
• end

Además en este lenguaje se aplican las siguientes reglas:

• Todas las variables son globales; es decir, pueden ser utilizadas en los demás procedimientos que constituyen el programa.
• No hay distinción entre mayúsculas y minúsculas; es decir, ReadInput es idéntica que readinput.

Problema de Ejemplo: El Triángulo de las Bermudas

La Figura siguiente muestra un triángulo. Escriba un programa que calcule la suma más grande de números siguiendo una ruta que comience en la punta y termine en algún número de la base del triángulo. Cada paso puede ir diagonalmente abajo hacia la izquierda o derecha. El número de renglones en el triángulo es mayor que 1 y menor o igual a 100. Los números en el triángulo son todos enteros entre 0 y 99.

Si al programa se alimentara la siguiente serie de datos de entrada:

5
7
3		8
8		1		0
2		7		4		4
4		5		2		6		5

El resultado de su ejecución debería ser el siguiente:
30.

Solución del Problema de Ejemplo:

Una forma de resolver el problema es considerar el triángulo como un árbol binario, en donde la raíz del árbol se encuentra en el vértice superior del árbol (en este ejemplo ocupado por el número 7), el cual tiene dos hijos (ocupados por los números 3 y 8), cada hijo tiene a su vez dos hijos, y así sucesivamente, execepto los de la base (denominados hojas) que no tienen ningún hijo. En estas circunstancias, el resultado se puede obtener efectuando un recorrido en profundidad del árbol de la siguiente manera:

• Junto a cada nodo n del árbol se guarda la suma suma(n) de los números que se encuentran en la ruta al nodo n desde la raíz.
• Al nodo raíz se le asigna un valor de suma igual al número que se encuentra en la raíz; es decir, suma(raíz) = número(raíz).
• En cada movimiento del recorrido en profundidad se calcula la suma de los números correspondientes a los nodos visitados desde la raiz, y se asigna la suma al nodo en donde se encuentra el recorrido. (Nótese que la suma correspondiente al nodo en donde se encuentra el recorrido es igual al número correspondiente a este nodo más la suma correspondiente al padre de este nodo; es decir suma(n) = número(n) + suma(padre de n).)
• Al término del recorrido se busca la hoja que tiene el valor de suma más grande.

A continuación se muestra el programa que encuentra la suma más grande. Este programa es una variante del algoritmo anterior en donde, en cada movimiento del recorrido, se registra el valor suma más grande que se haya encontrado.

program MaxSum
     call ReadInput()
     call ComputeAnswer()
     call WriteOutput()
end

// T= [1..100, 1..100] //

// lee los valores del triángulo //

procedure ReadInput
     input(inp, N)
     output('Número de renglones: ', N)
     for r <- 1 to N do
         for p <- 1 to r do read(T[r, p])
     output('Leídos todos los datos')
end // ReadInput //

// obtiene la suma de la ruta máxima //
procedure ComputeAnswer
     // m <- la suma de la ruta máxima //
     m <- MaxRS(1, 1)
end // ComputeAnswer //

// calcula la sumatoria de una ruta //
procedure MaxRS(r, p)
     if r = N then return(MaxRS <- T[r, p])
     else return(MaxRS <- T[r, p] + call Max(MaxRS(r+1, p), MaxRS(r+1, p+1)))
end // MaxRS //

// obtiene el valor más grande de dos números //
procedure Max(x, y)
     if x > y then return (Max <- x)
     else return (Max <- y)
end // Max //

// escribe el resultado //
procedure WriteOutput
     output('La suma de la ruta máxima es ', m)
end // WriteOutput //