Universidad de Costa Rica Recinto de Golfito Informática Empresarial

IF-3001 Algoritmos y estructuras de datos

REQUISITOS

OBJETIVO

      Introducir al estudiante a la abstracción de problemas mediante el uso de algoritmos y estructuras de datos básicas, para la solución de problemas computacionales.

DESCRIPCIÓN DEL CURSO

      En este curso se analiza en detalle el concepto de algoritmo, así como de sus propiedades. Señaliza la fuerte relación entre algoritmos y estructura de datos. Se hace un recorrido por algunos de los algoritmos más importantes de la teoría de la computación y se determina qué tipo de problemas pueden ser eficientemente resueltos en un computador. El estudiante desarrollará la programación de los algoritmos.

OBJETIVOS ESPECIFICOS

      Al finalizar el curso, el estudiante será capaz de:

1. Analizar la complejidad y el orden de duración de un algoritmo.
2. Estudiar las estructuras de datos básicas para la implementación de tipos de datos abstractas empleadas en aplicaciones computacionales.
3. Fomentar la valoración de los algoritmos con base en el contexto de la solución computacional donde son utilizados.
4. Implementar los algoritmos en un lenguaje de programación.

CONTENIDOS

1. Introducción a la teoría de algoritmos

1.1 Estudio del concepto de algoritmo

1.2 Tiempo y orden de ejecución de los algoritmos

1.3 Algoritmos recursivos (La base del tema fue desarrollada en el curso Programación I, le corresponde a este curso ahondar en el desarrollo complejos de algoritmos recursivos)

2. Tipos de algoritmos

2.1 Algoritmos voraces

2.2 Búsquedas exhaustivas

2.3 Programación dinámica

2.4 Algoritmos divide y vencerás

2.5 Algoritmos probabilísticos

3. Tipos de datos abstractos

3.1 Conceptos básicos de los TDA

3.2 Listas

3.3 Pilas

3.4 Colas

3.5 Árboles

3.6 Conjunto

3.7 Diccionario

4 Procesamiento de hileras

4.1 Búsquedas

4.2 Compresión de archivos

4.3 Criptografía

5 Algoritmos de ordenamiento

5.1 Hundimiento

5.2 Burbuja

5.3 Burbuja mejorada

5.4 Selección lineal con conteo

5.5 Selección lineal con intercambio

5.6 Quick sort

5.7 Radix sort

5.8 Merge sort

5.9 Shell sort

5.10 Colas de prioridad

6 Algoritmos de búsqueda

6.1 Búsqueda Secuencial

6.2 Búsqueda binaria

6.3 Árboles balanceados

6.4 Árboles de búsqueda binaria

6.5 Tablas de dispersión

7 Algoritmos para grafos

7.1 Recorridos

7.2 Conectividad

7.3 Árbol de expansión mínima

7.4 El problema de la ruta más corta

METODOLOGÍA

      El curso se desarrolla mediante presentaciones magistrales del profesor y presentaciones de los alumnos. Se utiliza una amplia gama de ayudas didácticas, que van desde la exposición de lecturas, análisis de investigaciones y dinámicas de grupo.

EVALUACIÓN

Descripción	%
I Parcial	20%
II Parcial	20%
Quices y Tareas	10%
Exposición II	10%
Asignaciones	10%
Proyecto Final	30%

ÍNDICE DE MATERIALES DEL CURSO

Tareas (Prof. Di Mare)

# 1: Convertidor de expresiones infijas

# 2: Mediciones de eficiencia para HerenciaOrdenada

# 3: Método de ordenamiento List.bubbleSort()

# 4: Encriptamiento

Proyecto: Grafos

REFERENCIAS Y BIBLIOGRAFÍA

Drozdek, Adam.

Estructura de datos y algoritmos en Java. Thomson, Mexico. 2007.

Allen Weiss, Mark.

Estructura de Datos en Java. Addison Wesley. Madrid. 2000.

Joyanes y Zahonero.

Fundamentos de Programación - Algoritmos, Estructuras de Datos y Objetos. Editorial Mc Graw Hill, tercera edición 2004.

Joyanes, Luis.

Programación en Java2. Algoritmos, Estructuras de Datos y Programación Orientada a Objetos. Editorial Mc Graw Hill, primera edición, 2002.

Aho, Hopcroft y Ullman.

Estructura de Datos y Algoritmos. Editorial Prentice – Hall, primera edición 1998.

Aho, Alfred.

Estructura de Datos y algoritmos. Addison Wesley, México. 1998.

Brassard y Bratley.

Fundamentos de Algoritmia. Prentice-Hall, primera edición 1998.

Sedgewick, Robert.

Algoritmos en C++. Editorial Prentice-Hall, primera edición 1995.

Martí, Ortega y Verdero.

Estructuras de Datos y Métodos Algorítmicos – Ejercicios resueltos. Editorial Pearson Prentice – Hall, 2003.

Deitel y Deitel.

Java: How to program? 5 ed. Prentice Hall. 2003.

Heileman, Gregory.

Estructuras de datos, algoritmos, programación orientada a objetos. McGraw Hill. 1998.

Joyanes Aguilar, Luis.

Programación en C++: Algoritmos, estruturas de datos y objetos. Mc Graw Hill. España. 2000.

Michael T. Goodrich; Roberto Tamassia.

Data Structures and Algorithms in Java. 4 ed. John Wiley & Sons, Inc.

Adolfo Di Mare <adolfo@di-mare.com>
Copyright © 2013
Derechos de autor reservados © 2013