Download Guía de estudio para el examen al Posgrado de Computación

Guía de estudio para el examen al Posgrado de Computación
Se indica el porcentaje de preguntas por cada tema general incluido en el examen. Son tres
temas generales. El examen consiste de 75 preguntas de opción múltiple a contestar en tres
horas.
1 SISTEMAS DE SOFTWARE Y METODOLOGÍA (25 %)
1.1 Organización de datos
1.1.1
Tipos de datos abstractos (por ejemplo: pilas, colas, listas, cadenas de caracteres,
árboles, conjuntos).
1.1.2
Implementación de tipos de datos (por ejemplo: apuntadores, hashing, codificación,
empaquetamiento, aritmética de direcciones).
1.1.3
Organización de archivos (por ejemplo: tipos de archivos, métodos de acceso,
permisos, etc.).
1.1.4
Modelos de datos (por ejemplo: jerárquico, relacional, red, etc.).
1.2 Organización del control de un programa.
1.2.1
Iteración y recursión.
1.2.2
Funciones y procedimientos (por ejemplo: declaraciones, paso de parámetros, etc.).
1.2.3
Procesos concurrentes, comunicación y sincronización entre procesos.
1.3 Metodología y lenguajes de programación.
1.3.1
Diseño orientado a objetos, de arriba abajo, etc.
1.3.2
Estructuras de datos (ver punto 1.1.1) y estructuras de control (por ejemplo: if,
While, do-while, switch).
1.3.3
Lenguajes funcionales, declarativos, imperativos y orientado a objetos.
1.3.4
Evaluación de expresiones (por ejemplo: aritméticas, lógicas, por eliminación, por
orden de evaluación, etc.).
1.4 Sistemas
1.4.1 Compiladores, sistemas operativos, cargadores, ligadores (por ejemplo: tipos,
etapas, etc.).
1.4.2 Manejo de recursos (por ejemplo: calendarización de procesos, administración de la
memoria principal, manejo de memoria virtual).
1.4.3 Ingeniería de software.
1.4.4 Base de datos (por ejemplo: tipos, normalización, implementación, etc.).
2 ORGANIZACIÓN Y ARQUITECTURA DE COMPUTADORAS (25 %)
2.1 Diseño Lógico.
2.1.1 Diseño e implementación de circuitos secuenciales y combinatorios.
2.1.2 Propiedades funcionales de circuitos digitales integrados.
2.2 Procesadores y unidades de control.
2.2.1 Arquitectura de procesadores (por ejemplo: RISC, CISC, etc.).
2.2.2 Conjuntos de instrucciones, organización de registros y de la unidad aritméticológica (ALU).
2.3 Memorias y su jerarquía.
2.3.1 Velocidad, capacidad y costo.
2.3.2 Tipos de memorias (por ejemplo: caché, principal, secundaria, etc.).
2.3.3 Paginación y segmentación.
2.4 Dispositivos de Entrada/Salida y sus interfaces.
2.4.1 Características funcionales y capacidades.
2.4.2 Mecanismo de acceso, interrupciones.
2.5 Redes de computadoras.
2.5.1 Tipos de redes de computadoras.
2.5.2 Principios de redes y protocolos.
2.5.3 Recursos distribuidos.
3 MATEMÁTICAS COMPUTACIONALES (25%)
3.1 Estructuras discretas --- elementos básicos de:
3.1.1 Relaciones de recurrencia.
3.1.2 Lógica matemática incluyendo álgebra booleana.
3.1.3
3.1.4
3.1.5
3.1.6
Teoría de grafos.
Teoría de conjuntos.
Teoría de conteo (por ejemplo: permutaciones, combinaciones, etc.).
Teoría de números (por ejemplo: factorización, divisibilidad, números primos,
número enteros, etc.).
3.2 Matemáticas numéricas.
3.2.1 Aritmética de computadora.
3.2.2 Álgebra lineal.
3.2.3 Funciones (por ejemplo: tipos, soluciones, etc.).
3.3 Probabilidad y estadística.
3.3.1 Distribuciones y eventos.
3.3.2 Estimaciones.
4 TEORÍA DE LA COMPUTACIÓN (25 %)
4.1 Teoría de autómatas y lenguajes.
4.1.1 Lenguajes regulares (por ejemplo: autómatas finitos, autómatas finitos no
determinísticos, expresiones regulares).
4.1.2 Lenguajes libres de contexto (por ejemplo: notaciones para gramáticas,
propiedades como vaciedad, ambigüedad).
4.1.3 Clases especiales de gramáticas libres de contexto (por ejemplo: LL, LR,
precedencia).
4.1.4 Máquinas de Turing y decidibilidad.
4.1.5 Procesadores de lenguajes formales (por ejemplo: analizadores léxicos y
generadores de analizadores léxicos).
4.2 Especificación correcta de programas.
4.2.1 Especificación formal y afirmaciones (por ejemplo: pre- y post-afirmaciones,
elementos no variables en ciclos, relaciones no variables de estructuras de datos).
4.2.2 Técnicas de verificación (por ejemplo: transformadores de predicados, axiomas de
Hoare).
4.3 Análisis de algoritmos.
4.3.1 Análisis exacto y asintótico del mejor caso, del peor caso o del caso promedio de la
complejidad del tiempo y espacio de algoritmos específicos.
4.3.2 Límite alto y bajo de la complejidad de problemas específicos.
4.3.3 Completitud NP.
Bibliografía
Sistemas de sofware y metodología
1
N. Wirth, Algoritmos + estructuras de datos = programas. Ed. Dossat, 1999.
2
C. J. Date. An Introduction to Data Base Systems. Addison-Wesley, 2003.
3
M. Ben-Ari. Understanding Programming Languages. John Wiley and Sons, 1996.
4
B. W. Kernighan y D. M. Ritchie. El Lenguaje de Programación C. Prentice Hall
Hispanoamericana, 1988.
5
A. Tanenbaum y A. S. Woodhull, Operating Systems: Design and Implementation,
Prentice-Hall 2006.
6
A. V Aho. Compiladores, Principios, Técnicas y Herramientas. Addison-Wesley
Longman, 2000.
Organización y arquitectura de computadoras
7
M. M. Mano. Lógica Digital y Diseño de Computadoras. Prentice-Hall, 1989.
8
D. A. Patterson y J. L. Hennessy. Computer Organization & Design: The
Harware/Software Interface. Morgan Kaufmann Publisher, 1998.
9
A. S. Tanenbaum. Computer Networks. Prentice Hall, 2002.
Matemáticas computacionales
10 K. Ross y Ch. Wright. Matemáticas Discretas. Prentice Hall Hispanoamericana S.A,
1992.
11
12
13
E. Mendelson. Introduction to Mathematical Logic. Wadsworth & Brooks/Cole Advanced
Books & Software, 1997.
Carnahan. Applied Numerical Methods. McGraw-Hill, 1969.
B. Noble y J. Daniel. Algebra Lineal Aplicada. Prentice Hall Hispanoamericana S.A,
1989.
Teoría de la computación
14 D. Gries. The Science of Programming. Springer-Verlag, 1998.
15 A. V. Aho, J. E. Hopcroft y J. D. Ullman. The Design and Analysis of Algorithms.
Addison-Wesley, 1998.
16 J. E. Hopcroft, R. Motwani y J. D. Ullman, Introduction to Automata Theory, Languages,
and Computation, Addison-Wesley, 2000.
17 J. Martin, Introduction to Languages and the Theory of Computation, McGraw-Hill,
2003.