UNIVERSIDAD AUTONOMA DE BAJA CALIFORNIA DIRECCION GENERAL DE ASUNTOS ACADEMICOS PROGRAMA DE ASIGNATURA I. DATOS DE IDENTIFICACION 1. Unidad Académica: Facultad de Ciencias 2. Programa (s) de estudio: Licenciatura en Ciencias Computacionales 4. Nombre de la asignatura: 6. HC:

2

HL : 2

HT: 2

7. Ciclo escolar: 2004-1 9. Carácter de la asignatura:

Estructura de datos y algoritmos HPC:

HCL:

HE: 2

CR: 8

3. Vigencia del plan: 2004-1 5. Clave:

.

8. Etapa de formación a la que pertenece: disciplinaria Obligatoria

10. Requisitos para cursar la asignatura: introducción a la programación

Formuló: Fecha:

M.C. José Ignacio Ascencio López 26 de enero de 2004

Vo. Bo. Cargo:

II. PROPOSITO GENERAL DEL CURSO Estructura de datos y algoritmos es un curso que todo programador debe tomar. En él se presentan distintos modelos algorítmicos para el manejo de datos (en un lenguaje algorítmico e independiente de cualquier lenguaje de programación) que al utilizarlos en volúmenes, hagan uso eficiente de los recursos computacionales.

III. COMPETENCIA (S) DEL CURSO Discriminar las diferentes estructuras de datos para identificar aquellas que faciliten la representación de la información y con ellas pueda generar nuevas soluciones algorítmicas que resuelvan problemas específicos.

IV. EVIDENCIA (S) DE DESEMPEÑO Estructuras de datos que facilitan la representación de la información y algoritmos que los usan en la solución de problemas específicos.

V. DESARROLLO POR UNIDADES UNIDAD I: Introducción a las estructuras de datos. Competencia: Que el alumno identifique los antecedentes generales de las estructuras de datos, descubra su importancia y utilice estructuras de datos simples aplicados en problemáticas reales. Contenido temático Duración 1. INTRODUCCIÓN A LAS ESTRUCTURAS DE DATOS 1.1 Propósito del curso y conceptos generales. 1.2 Tipos de datos simples y sus operaciones: representación de enteros positivos, enteros negativos, caracteres, numeración binaria y hexadecimal, manipulación de bits, representación de decimales con punto flotante y punto fijo. 1.3 Concepto general del tiempo de ejecución: concepto general de eficiencia y tiempo de ejecución, costo de las operaciones de suma y multiplicación en cada tipo de datos . 1.4 Programación en pseudocódigo: especificación de un lenguaje en pseudocódigo para la descripción de algoritmos. 1.5 Arreglos unidimensionales y bidimensionales: conceptos y su manejo en los dispositivos de almacenamiento, uso y aplicación en solución de problemas reales. 1.6 Registros: conceptos y su manejo en los dispositivos de almacenamiento, uso y aplicación en solución de problemas reales.

UNIDAD II: Estructuras de Información. Competencia: Que el alumno utilice las operaciones primitivas de acceso a diferentes estructuras de datos y los use en las solución de problemas.

Contenido temático

Duración

2. ESTRUCTURAS DE INFORMACION 2.1 Pilas: algoritmos generales de acceso y su implementación en diferentes tipos de datos simples (usando arreglos, registros, listas) 2.2 Colas: algoritmos de acceso (insertar, retirar), su implementación, y variedades (colas con prioridad, colas circulares,) 2.3 Asignación ligada: operaciones básicas (inserta inicio, inserta enseguida, inserta antes, inserta al final, borra inicio, etc.), sus variedades (con nodo cabecera, listas circulares, de doble liga) implementación utilizando memoria dinámica y aplicaciones en la solución a problemas.

UNIDAD III: Ordenación y búsqueda. Competencia: Que el alumno discrimine entre los diferentes algoritmos de clasificación y búsqueda comparando los casos de uso óptimo para cada alternativa. Contenido temático Duración 3. ORDENACION Y BUSQUEDA. 3.1 Ordenación por intercambio: Revisar en cada caso su algoritmo básico, su eficiencia y su implementación utilizando listas grandes de datos. 3.2 Ordenación por selección. 3.3 Ordenación por inserción. 3.4 Ordenaciones mejoradas (quicksort, mergesort, etc.). 3.5 Búsqueda secuencial. 3.6 Búsqueda binaria. 3.7 Búsquedas mejoradas (Hash, heapsort). 3.8 Recursividad y su simulación utilizando pilas

UNIDAD IV: Introducción a las estructuras de datos. Competencia: Que el alumno se introduzca en el manejo de árboles y los use en el desarrollo de sistemas programáticos. Contenido temático 4. ÁRBOLES 4.1 Introducción y definiciones. 4.2 Recorridos de árboles binarios. 4.3 Representación binaria de árboles. 4.4 Árbol-B. 4.5 Árbol de Huffman.

Duración

VI. ESTRUCTURA DE LAS PRACTICAS No. de Práctica 1

2

Competencia(s) Constatar el espacio y la forma en que hacen uso del dispositivo de almacenamiento (memoria y disco) los tipos de datos simples

Descripción Material de Apoyo Duración Que los alumnos Diferentes 3 sesiones verifique que cada tipo compiladores con sus de datos ocupa manuales diferentes magnitudes y manejo de bits haciendo programas que los utilicen y que pongan a prueba el problema de desbordamiento. Obtener constancia de Que los alumnos elaboren Diferentes 1 sesión que la eficiencia en compiladores, equipo y un programa que mida el tiempo de un programa tiempo que tarda una s.o. función en ejecutarse. debe ser independiente Ejemplo de pseudocódigo de se implantación, funcionX() { i=0; MIENTRAS(++i < 100000) escribe("Hola mundo"); } Principal() { ti = TomaTiempo(); funcionX(); tf = TomaTiempo(); tiempo = tf - ti; escribe("El tiempo de ejecución de la función fue de " tiempo "milisegundos"); }

Concluya que programas

como este no pueden ser considerados medidas de complejidad de un programa pues dependen directamente del lenguaje, el compilador, el hardware, el sistema operativo y las características particulares de la ejecución

3

Uso de arreglos y registros en la representación y solución de problemas

4

Empleo de pilas en Computadora, Hacer un programa que soluciones algorítmicas implemente las operaciones lenguaje, compilador.

Realice programas que le ejerciten en el uso de estos tipos de datos (asignación, inserción, borrado, ordenar, buscar un elemento, utilizarlos en archivos, etc.)

Bibliografía

2 sesiones

2 sesiones

primitivas de la pila, Poner(pila, dato), Quitar(pila). Desarrolla una aplicación sencilla que utilice estas operaciones (ejem. Las notaciones infijas, postfijas prefijas y transformaciones entre ellas usando pilas)

5

Empleo de colas en Computadora, Hacer un programa que soluciones algorítmicas implemente las operaciones lenguaje, compilador. primitivas de la cola, Insertar(cola,dato), Retirar(cola). Desarrolla una aplicación sencilla que utilice estas operaciones

2 sesiones

(simulación de colas de espera en un mercado)

6

Empleo de listas en Computadora, Hacer un programa que soluciones algorítmicas implemente las operaciones lenguaje, compilador. primitivas de las listas, InsertarInicio(lista,dato), RetirarInicio(lista). Desarrolla una aplicación sencilla que utilice estas operaciones (ejem. Simulación de pilas y colas, manejo números largos utilizando varios nodos para su almacenamiento, etc)

7

Discriminar la forma funcional y la eficiencia de los diferentes métodos de ordenación y búsqueda

Utilizar los diferentes métodos de ordenación y búsqueda en la solución a problemas que manejen cantidades considerables de datos.

Computadora, lenguaje, compilador.

4 sesiones

8

Uso de estructuras no lineales (árboles) para el almacenamiento y acceso a la información

Utilizar al menos una estructura arborea para la solución de problemas (recomiendo utilizar huffman en la compresión de datos)

Computadora, lenguaje, compilador.

2 sesiones

VII. METODOLOGIA DE TRABAJO Buscar una actitud activa del estudiante ante los algoritmos, no es primordial que él los estudie, es muy importante que los redescubra, pues así estará en posibilidad de crear nuevas soluciones a nuevos problemas. Es también de suma importancia que lleve los algoritmos a implementaciones aunque sean de tipo didácticas (problemas ideados).

VIII. CRITERIOS DE EVALUACION Criterios propuestos: Exámenes 60 % Ejercicios 30 % Participación 10 %

VII. BIBLIOGRAFIA Básica - Data Structures using C Aron M. Tenenbaum, Yedidyah L. Moshe J. Prentice Hall - Estructura de Datos Osvaldo Cairó, Silvia Guardati MacGraw-Hill 1993 ISBN 970-10-0258-x

Complementaria - Pascal y Estructura de Datos. Dale/Lilly, McGraw-Hill] - Data Structures Techniques, Stadish, A. Thomas - Data Structures and Algoritmos, Aho, V. Alfred. - Estructura de Datos y Diseño de Programas, Robert L. Kruse Prentice Hall