Presentación

La problemática abordada por esta materia se relaciona con los conocimientos relativos al desarrollo de programas.

La resolución automática de un problema obliga a analizar previamente y en forma exhaustiva las diferentes situaciones y condiciones que puede presentar. La forma que adopta la solución es un algoritmo que computa la función pretendida y que, por su complejidad, debe ser verificado metódicamente para asegurar su corrección y validez.

El instrumento utilizado para programar es un lenguaje que tiene características de los lenguajes formales y que, de acuerdo al tipo de problema que intenta representar y las estrategias en que se basa, tiene estructuras, reglas, operaciones y objetos propios.

Programar es una actividad compleja que combina procesos teóricos (propios de la matemática), de abstracción o experimentales (típicamente de la ciencia) y de diseño (de la ingeniería).

Esta materia, está orientada a desarrollar un esquema de razonamiento lógico apropiado no sólo para las actividades de programación sino que sirva de base para la comprensión de los objetos del trabajo y la capacidad profesional de abstracción requerida del técnico.

Objetivos

Al finalizar esta materia los estudiantes estarán en condiciones de encarar estrategias de resolución de problemas y resolver pequeños problemas de programación, esencialmente de carácter didáctico mostrando conocimientos en:

• El dominio de las estructuras de control y tipos de datos abstractos.
• Fundamentos y uso de la algoritmia como herramienta de optimización de software.
• La utilización de ambientes de programación funcional como pueden ser Haskell o ML.

Contenidos

Introducción a la Teoría de Complejidad

Introducción. Modelo de Costo. Análisis de Tiempo de Cómputo. Mejor Caso, Peor Caso y Caso Promedio. Notación Asintótica. Notación. Propiedades

Herramientas matemáticas

Propiedades de las sumas. Técnicas. Relaciones de Recurrencia. Aplicación.

Abstracción de datos TAD

Implementando tipos abstractos. TADs. Tipos Algebraicos como TADs. Pilas, Colas, BST y conjuntos. Estructuras Persistentes.

Inducción.

Inducción Natural. Inducción Estructural.

Ordenamiento.

Diseño de algoritmos

Fuerza Bruta. Decrase & Conquer. Divede & Conquer.

Programación Dinámica

Formulación recursiva. Subproblemas Óptimos. Solapamiento de subproblemas. Calculo: bottom-up.

Greedy

Hasing

Introducción. Tablas de Direccionamiento Directo. Listas Enlazadas. Tablas Hash. Funciones Hash Direccionamiento Abierto (Closed Hashing). Análisis del Direccionamiento Abierto.

Estructuras de Datos para Conjuntos Disjuntos.

Introducción. Definición de la Estructura. Aplicación. Representación por Arreglos. Representación por Listas. Representación por Arboles

Bibliografía

Ullman.Elements of ML Programming. Printece Hall. 1998

Paulson.ML for working programmer .Cambridge University Press. 1996

Recursos Web

Comunidades - UNR