|
Objetivo:
Estudiar las técnicas de diseño
necesarias para formular y expresar algoritmos computacionales, estructurando
en forma eficiente la representación elegida para la información.
Lograr la construcción de programas en forma correcta y metodológica.
Estudiar los conceptos teóricos requeridos para reconocer aque-llos problemas
para los cuales no existe solución algorítmica práctica.
1 Fundamentos de algorítmica
PI1 Historia de la computación. Formas primitivas
de cálculo y sistemas numéricos. El álgebra de Boole. Antecedentes
de las computadoras. Generaciones y clasificación de computadoras. Cambios
de tecnología. Evolución de lenguajes, sistemas operativos y otros
componentes de software de base. Tipos de procesamiento (monoprocesamiento,
concurrencia, multiprocesamiento, paralelismo). Multimedia. Redes. Cómputo
distribuido y cooperativo. Redes globales. Internet.
PI2 Algorítmica básica. Descripción de situaciones.
Acciones para la resolución de un problema. Expresión de acciones
y temporalidad. Representación de la información: datos. Concepto
de programa almacenado. Definición de algoritmo y expresión. Diagramas
de flujo. Pseudocódigo. Elementos de un lenguaje imperativo de programación.
Información y estructuras algorítmicas de control. Consideraciones
sobre metodología de objetos.
PI3 Enfoque estructurado. Elementos básicos de un lenguaje
imperativo (de procedimientos) de programación: variables, tipos simples
(enteros, reales, caracteres, cadenas, lógicos), expresiones, estructuras
algorítmicas de control (if, case, while, repeat,
for). Arreglos de tipos simples. Segmentación de programas. Procedimientos
y funciones: variables globales y locales, parámetros. Documentación
de programas. Programación en lenguaje C, Pascal y otros.
PI4 Enfoque por objetos. Concepto de objeto. Encapsulamiento
de la información. Tipos abstractos de datos. Clases. Herencia. Polimorfismo.
Comunicación entre objetos: mensajes. Lenguajes de programación
por objetos y sus variantes: filosofía de Simula, Modula, Smalltalk,
C++, Eiffel y otros.
2 Estructuras de datos
PI5Estructuras estáticas en memoria central. Información:
tipos y valores. Arreglos: homogeneidad de la información, estatismo
en memoria, acceso a elementos. Aplicaciones. Técnicas de búsqueda,
eliminación, inserción y clasificación en arreglos unidimensionales
y bidimensionales. Arreglos n-dimensionales. Registros: heterogeneidad
de la información. Acceso a elementos. Aplicaciones. Ortogonalización
de arreglos y registros. Conjuntos.
PI6 Estructuras dinámicas en memoria central. Dinamismo
en memoria. Apuntadores. Listas. Árboles. Propiedades matemáticas
de los árboles. Técnicas de rastreo, búsqueda, eliminación,
inserción, otras. Búsqueda e inserción en árboles,
en árboles balanceados, en árboles binarios, en árboles
B. Algoritmos iterativos y algoritmos recursivos. Recursividad e inducción
matemática. Concepto de recolector de basura (garbage collector).
Ortogonalización de tipos de información.
PI7 Estructuras en memoria secundaria. Archivos. Características
físicas y características lógicas. Medios de almacenamiento.
Tipos de organización de archivos: secuencial, secuencial con índices,
llaves, llaves múltiples. Relación entre los medios de almacenamiento
y las organizaciones. Archivos de información especial: directorios.
Tratamiento de listas y árboles en memoria secundaria. Accesos y recuperación
de información. Respaldos y seguridad de la información.
PI8 Organización de archivos. Tipos de archivos de acuerdo
con su organización. Operaciones sobre archivos. Apuntadores e índices.
Dispersión (Hashing). Técnicas de inspección. Archivos
B y B+. Recuperación de datos por llaves múltiples. Técnicas
especiales para acceso concurrente. Atributos de acceso. Bloqueos (record
blocking, file blocking). Estructuras adicionales para seguridad: bits de
protección, campos, encabezamientos, información redundante.
PI9 Clasificación. Estructuras de datos adecuadas. Métodos
de clasificación y consideraciones de complejidad (tiempo, espacio):
del orden de n2, del orden de n log n, etc.
Análisis comparativo. Diseño y construcción de algoritmos
en memoria (inserción, intercambio o burbuja, quicksort, mezcla,
clasificación topológica, etc.). Necesidad de métodos especiales
fuera de la memoria central.
PI10 Búsqueda. Métodos de búsqueda, estructuras
de datos relacionadas y consideraciones de complejidad. Análisis comparativo.
Diseño y construcción de algoritmos en memoria (ej., lineal, binaria,
en tablas de una o más dimensiones, por árboles binarios, hash:
colisiones, etc.). Necesidad de métodos especiales fuera de la memoria
central.
3 Complejidad
PI11 Medidas de complejidad. Notación "O" y "o".
Algoritmos de comportamiento asintótico "del orden de". Algoritmos de
tiempo polinomial y de tiempo exponencial. Algoritmos factibles y no factibles.
Cotas inferior y superior. Valor promedio, peor caso. Compromisos espacio-tiempo.
Clases de complejidad: P, NP, NP completos. Complejidad en métodos de
clasificación y búsqueda: tiempos en árboles binarios,
en quicksort y en otros. Métodos para encontrar soluciones aproximadas
a problemas no factibles.
PI12 Análisis de algoritmos. Algoritmos iterativos y recursivos.
Análisis de algoritmos recursivos: ecuaciones de recurrencia. Estimación
de costos. Predicción. Criterios de medición. Instrumentos de
software para efectuar mediciones. Eficiencia.
PI13 Estrategias para la construcción de algoritmos. Selección
de métodos basados en criterios de eficiencia. Tipos de algoritmos (ávidos,
"divide y vencerás", backtrack, búsqueda local, por transformaciones,
otros): definición, ejemplos, diseño (e implantación cuando
corresponda), corrección, eficiencia, complejidad.
|
