UNIVERSIDAD NACIONAL ABIERTA VICERRECTORADO ACADEMICO SUBPROGRAMA DE DISEO ACADMICO AREA: INGENIERA / CARRERA: INGENIERA DE SISTEMAS

PLAN DE CURSO
I. Identificacin: Nombre: COMPUTACIN II Cdigo: 324 U.C: 4 Carrera: Ingeniera de sistemas Cdigo: 236 Semestre: III Prelaciones: Computacin I (323) Requisito: Ninguno Autor: Lic. Mara Eugenia Mazzei (especialista de contenido) Telfono: (0212) - 5552376 Correo electrnico: [email protected]

Asesores: Lic. Carmen Velsquez (Evaluadora de la carrera) Ing. Judit Carvallo (Coordinadora de la carrera) Dra. Egle Arellano (Diseadora de instruccin)

Nivel Central Caracas, Octubre 2006

II.

FUNDAMENTACIN

El curso Computacin II se centra en el estudio y aplicacin de las diferentes estructuras de datos, conjuntamente con el diseo e implementacin de los algoritmos apropiados para tratarlas. Bajo el enfoque actual, las estructuras de datos se conciben como colecciones de datos, sobre los cuales se pueden definir operaciones.

Es nuestro inters proporcionar un enfoque actualizado del curso en este nivel de la carrera, que sirva de punto de partida para el desarrollo de habilidades relacionadas con el diseo de algoritmos empleando estructuras de datos apropiadas, con una visin hacia la programacin orientada a objetos. El desarrollo de destrezas para el diseo de soluciones sencillas y su implantacin en el computador, con el diseo adecuado de las estructuras de datos, slo se logra a travs de la ejercitacin, sin olvidar la comprensin de los conceptos, de ah la naturaleza terico-prctica de la asignatura.

La asignatura Computacin II se ubica dentro de las asignaturas bsicas del ingeniero de sistemas y su asimilacin es fundamental para el buen desempeo en gran parte de las asignaturas de la carrera, en donde el estudiante deber implementar programas, de all su carcter obligatorio. Por otra parte fomenta el desarrollo de la lgica y la realizacin de acciones coherentes, indispensables para el diseo e implementacin de programas en computadores; esto jugar un papel muy importante en la formacin del futuro ingeniero. El dinamismo con el que se mueve el conocimiento en el campo de la Computacin ha sido determinante en la seleccin del material instruccional para este curso. En este sentido se considera conveniente proponer el empleo de libros producidos por editoriales del mercado, que complementados con guas adecuadas, fomenten el fortalecimiento y la actualizacin de los conocimientos. Tomando en consideracin estos elementos, se dise el siguiente paquete instruccional: El libro: Estructuras de Datos: Algoritmos, abstraccin y objetos, de Joyanes L. y Zahonero I., Editorial Mc. Graw Hill. La seleccin de

Plan de curso Computacin II

Elaborado por Prof..

Mara E. Mazzei. UNA 2006

3 este libro est basada en criterios de actualidad, presentacin, abundancia de ejemplos y disponibilidad. Como texto alternativo se recomienda el siguiente libro: Estructuras de Datos y Algoritmos, de Aho A. V., Hopcroft J. E. y de Ullman J. D., Addison Wesley Longman.

- Un Material Instruccional de Apoyo UNA, que servir de directriz para el empleo adecuado del libro. - Un paquete de software de programacin para la implementacin de los programas en el lenguaje PASCAL. - Referencias a pginas WEB y cursos WEB enriquecer los conocimientos adquiridos. que tendrn el efecto de

Plan de curso Computacin II

Elaborado por Prof..

Mara E. Mazzei. UNA 2006

4 III. PLAN DE EVALUACION Orientaciones Generales Las pruebas son de modalidad presencial y de desarrollo. Ponderacin de los objetivos: La ponderacin consiste en la asignacin de pesos a los objetivos evaluables de la asignatura, de acuerdo a la importancia y/o complejidad que tienen. La escala de ponderacin de esta asignatura es de 1 a 10 puntos. Esta ponderacin est determinada por la incidencia de los objetivos evaluables en: el perfil de la carrera, el objetivo terminal de la asignatura y los objetivos terminales de las asignaturas sobre las que existe prelacin. El logro de los objetivos N 4,5 y 6, correspondientes a la realizacin del trabajo prctico, es requisito obligatorio para aprobar la asignatura. Las especificaciones del trabajo prctico se publican la primera semana de presentacin de las pruebas El estudiante consignar el trabajo resuelto con la segunda prueba integral. M I U 1 2 3 4 III 5 6 O 1 2 3 4 5 6 OBJETIVOS Elaborar un TAD(Tipo Abstracto de Datos) para representar un dato particular. Codificar en lenguaje de programacin un algoritmo, empleando el TAD Lista Enlazada, Pila o Cola para la resolucin de un problema que requiera el empleo de estructuras lineales de datos. Codificar algoritmos en lenguaje de programacin, empleando la estructura de rbol y la tcnica adecuada para la resolucin de problemas especficos. Codificar algoritmos en lenguaje de programacin, empleando la estructura de grafo para la resolucin de problemas especficos. Codificar algoritmos de Ordenacin en lenguaje de programacin, para la resolucin de problemas especficos. Codificar algoritmos de Bsqueda en lenguaje de programacin, para la resolucin de problemas especficos. MODALIDAD PRIMERA INTEGRAL SEGUNDA INTEGRAL OBJETIVOS 1,2 y 3 CONTENIDO MDULOS: I y II UNIDADES: 1,2 y3 MDULOS: I y II UNIDADES: 1,2 y3

1,2 y 3

TRABAJO PRCTICO

4,5 y 6

4,5 y 6

II

Objetivo 1 2 3 4 5 6 4 4 4 5 5 5 Peso Peso mximo: 27 puntos

Plan de curso Computacin II

Criterio de dominio acadmico: 19 puntos

Elaborado por Prof.. Mara E. Mazzei. UNA 2006

5 IV. DISEO DE LA INSTRUCCIN DEL CURSO

Objetivo del curso:

Codificar algoritmos con sentido lgico y coherente, utilizando las estructuras de datos apropiadas, as como los mtodos de clasificacin y bsqueda, aplicados a la resolucin de problemas especficos. Objetivo 1 Contenido La abstraccin. Modularidad. Tipos abstractos de datos. Uso de tipos de datos y estructuras de datos fundamentales: cadenas, arreglos simples y multidimensionales, registros y conjuntos, punteros o apuntadores. Orientacin a objetos: conceptos. Especificacin formal del TAD Lista. Implementacin del TAD Lista con estructuras dinmicas. Operaciones. Aplicaciones. Listas doblemente enlazadas. Listas circulares. Especificacin formal del TAD Pila. Implementacin de Pilas con Arreglos. Implementacin de Pilas con variables dinmicas. Operaciones Aplicaciones.Especificacin formal del TAD Cola y Dipolo o Bicola. Implementacin del TAD Cola o Dipolo con estructuras estticas y/o dinmicas. Operaciones. Aplicaciones. Recursividad: Concepto. Utilidad. Algoritmos tpicos. Implementacin de procedimientos recursivos. Concepto de rbol binario. rboles de Expresin. Construccin. Recorrido. Aplicaciones. rbol binario de bsqueda. Operaciones. Concepto de grafo. Representacin del TAD grafo. Matriz de caminos. Algoritmos fundamentales con grafos. Aplicaciones Ordenacin. Algoritmo de Burbuja. Algoritmo de Insercin. Algoritmo Shell. Algoritmo Quicksort. Algoritmo Heapsort. Otros Bsqueda. Bsqueda Lineal. Bsqueda Binaria. Hashing. Funcin de Hashing

4 5 6

Plan de curso Computacin II

Elaborado por Prof..

Mara E. Mazzei. UNA 2006

ORIENTACIONES GENERALES Los textos recomendados para este curso, estn disponibles en la Biblioteca del Centro Local, como Servicio de Prstamo en Sala y Prstamo Circulante. El Material Instruccional de Apoyo (MIA) lo entregarn en el almacn del Centro Local, previa presentacin del comprobante de inscripcin de la asignatura. Las especificaciones del Trabajo Prctico se suministrarn al estudiante a partir de la primera semana de presentacin de pruebas, a travs de la red: http://www.ciberesquina.una.edu.ve El software requerido para realizar el trabajo est disponible en el Laboratorio de Computacin del centro local. Lea las instrucciones que aparecen en el M.I.A. Realice los ejercicios propuestos en cada unidad, en el Material de Apoyo. Implemente algoritmos en lenguaje de programacin. Introduzca diferentes datos, para probar su algoritmo. Analice los resultados. Consulte en la direccin electrnica indicada, referenciada en la unidad del MIA. Si no se hacen referencias especficas, se recomienda buscar el tema en Internet, empleando un buscador. Ante cualquier duda consulte con su asesor en su Centro Local.

Plan de curso Computacin II

Elaborado por Prof..

Mara E. Mazzei. UNA 2006

7 OBJETIVO 1 ESTRATEGIAS INSTRUCCIONALES ESTRATEGIAS DE EVALUACIN

Se presentarn situaciones, en donde el Lea en el libro I, el captulo: Ingeniera de Software: introduccin a la estudiante deber elaborar un TAD para metodologa de construccin de grandes programas. Este captulo presenta de representar un tipo de datos, empleando el manera general los principios fundamentales de la Ingeniera de Software, los lenguaje de programacin. cuales estn dirigidos hacia el buen diseo de programas. Este enfoque permitir al estudiante comprender la utilidad del correcto desarrollo del Software, sin Procedimiento: Se valorar la correcta importar el lenguaje empleado. Si utiliza el texto II, lea el captulo: Diseo y elaboracin de un TAD apropiado a la situacin. Anlisis de Algoritmos. Repase las instrucciones que se requieren para declarar los tipos de datos en el Instrumento: La realizacin de este ejercicio formar parte de una prueba presencial de lenguaje de programacin PASCAL. Estudie los captulos del libro I Abstraccin de datos y objetos y Estructuras desarrollo. de datos dinmicas. Si utiliza el libro II, estudie la seccin sobre los tipos Momento: Primera y segunda prueba integral. abstractos de datos. Los temas a estudiar en esta unidad resultan muy intuitivos. Es fcil observar en Se plantearn situaciones prcticas que la vida real, series de objetos enlazados, la formacin de colas: de personas, requieran una solucin algortmica empleando de trabajos y de objetos en general. Igualmente es frecuente acumular pilas de estructuras de datos lineales, previa definicin papeles o documentos, en donde el elemento que est en la cima de las mismas de las mismas. es el de ms reciente colocacin. Piense en agrupaciones de este tipo y cmo Procedimiento: Se valorar la correcta operarlas. Lea el captulo del libro I: Estructuras de Datos Dinmicas: punteros. Si utiliza el elaboracin de un TAD Lista o Pila o Cola, as como el algoritmo ajustado a la situacin, en texto II, lea la seccin sobre apuntadores y cursores. Realice los ejemplos presentados y los ejercicios. Como recurso de apoyo para trminos de su eficacia. la resolucin de los ejercicios, utilice representaciones grficas de las variables tipo puntero. La comprensin de este captulo servir de base para el Instrumento: La realizacin de este ejercicio formar parte de una prueba presencial de aprendizaje de los captulos que siguen. Estudie en el libro I, los captulos: Listas enlazadas y Listas doblemente desarrollo. enlazadas, la estructura LISTA o en el libro II, las secciones sobre El tipo de Momento: Primera y Segunda prueba integral. datos abstracto LISTA y Realizacin de listas. Si utiliza el texto II, lea las secciones sobre LISTAS y Realizacin de LISTAS. Estudie el captulo del libro I titulado: Pilas, la estructura PILA o en el libro II, las secciones relacionadas con PILAS. Estudie el captulo del libro titulado: Colas y colas de prioridades: el TAD COLA, o el libro II, las secciones relacionadas con COLAS.

Plan de curso Computacin II

Elaborado por Prof..

Mara E. Mazzei. UNA 2006

8 3
Un objeto recursivo es aquel que forma parte de s mismo. En la vida real existen objetos recursivos. Halle ejemplos de objetos que puedan considerarse as. Estudie el captulo del libro I: La herramienta de la recursividad. Si utiliza el texto II, estudie los procedimientos recursivos. Estudie el captulo del libro I: rboles binarios .Si utiliza el texto II estudie el captulo sobre el TDA ARBOL y rboles Binarios. Implemente algoritmos en lenguaje de programacin que puedan realizarse empleando recursividad. Compare con soluciones en donde emplee la iteracin. Emplee el paquete de Software para probar estos algoritmos. Implemente algoritmos recursivos, en lenguaje de programacin, relacionados con la estructura ARBOL binario. Observe la utilidad de emplear algoritmos recursivos para operar con un rbol. Emplee el paquete de Software para probar estos algoritmos. Investigue ejemplos de la vida real que puedan representarse como rboles. Intente operar sobre ellos, por ejemplo insertando o eliminando nodos. Es frecuente representar objetos que tienen mltiples relaciones con otros. Los grafos son abstracciones de estas relaciones y tienen gran aplicabilidad en diversos campos. Los modelos de rutas, las redes de comunicaciones, los circuitos elctricos, las relaciones entre individuos, son ejemplos, en donde los elementos se representan por puntos y sus relaciones por arcos. Piense en situaciones de este tipo y represntelas como indicamos. Lo que resulta es un grafo. Su representacin en el computador es muy intuitiva, como Ud. lo constatar al estudiar el material instruccional. Estudie en el libro I el captulo del libro Grafos. Representacin y operaciones, la estructura GRAFO. Si utiliza el texto II, estudie los GRAFOS dirigidos y no dirigidos, representacin Investigue ejemplos de la vida real que puedan representarse como grafos. Se plantearn situaciones prcticas que requieran una solucin algortmica empleando estructuras de datos tipo RBOL, previa definicin de las mismas. Procedimiento: Se valorar la correcta elaboracin de la estructura de datos, as como el algoritmo ajustado a la situacin, en trminos de su eficacia. En cualquiera de las situaciones que se planteen de aqu en adelante se exigir eventualmente una solucin algortmica recursiva. Instrumento: La realizacin de este ejercicio formar parte de una prueba presencial de desarrollo. Momento: Primera y Segunda prueba integral

Producto: Implantacin de un programa a travs del computador. Se valorar el correcto diseo del programa as como la eficacia y la eficiencia del mismo. Instrumento: Trabajo prctico. Momento: Las especificaciones sobre la realizacin del trabajo prctico se entregan en la primera semana de aplicacin de pruebas. El estudiante consignar el trabajo realizado con la segunda prueba integral.

Plan de curso Computacin II

Elaborado por Prof..

Mara E. Mazzei. UNA 2006

9 5
Uno de los procesos ms utilizados cuando se opera con grupos de elementos en el computador es la ordenacin de los mismos de acuerdo a una clave. Constantemente requerimos ordenar ascendentemente o descendentemente un conjunto de elementos para presentar la informacin organizada. El estudio de los algoritmos fundamentales de ordenacin proporciona destrezas en la elaboracin de los algoritmos que pretenden resolver situaciones especficas. Estudie en el captulo del libro I, titulado Ordenacin, bsqueda y mezcla todas las secciones relacionadas con la ordenacin. Si utiliza el texto II estudie el captulo sobre Clasificacin. Realice comparaciones de los algoritmos estudiados en trmino de su eficiencia. Producto: Implantacin de un programa a travs del computador. Se plantearn situaciones prcticas que requieran una solucin empleando al menos un mtodo de ordenacin, a travs de un programa. Procedimiento: Se valorar el correcto diseo del programa as como la eficacia y la eficiencia del mismo. Instrumento: Trabajo prctico. Momento: Las especificaciones sobre la realizacin del trabajo prctico se entregan en la primera semana de aplicacin de pruebas. El estudiante consignar el trabajo realizado con la segunda prueba integral.

Cuando tenemos un conjunto de elementos ordenados, en muchas ocasiones necesitamos localizar alguno de ellos, por ejemplo buscar un nmero de cdula de identidad dentro de una lista ordenada para conocer el nombre asociado u otros datos. El estudio de los algoritmos que conforman esta unidad resultan igualmente fciles de comprender, debido a la similitud que existe entre ellos y la realidad. Estudie en el captulo del libro I titulado Ordenacin, bsqueda y mezcla, todas las secciones relacionadas con la bsqueda y en el captulo del libro I titulado Tratamiento de Archivos de Datos lo referente a Hashing. Si utiliza el texto II, estudie la seccin del libro sobre rboles binarios de bsqueda, Mtodos de Dispersin o Hashing. Realice comparaciones de los algoritmos estudiados en trmino de su eficiencia.

Producto: Implantacin de un programa a travs del computador. Se plantearn situaciones prcticas que requieran una solucin empleando al menos un mtodo de bsqueda, a travs de un programa. Procedimiento: Se valorar el correcto diseo del programa as como la eficacia y la eficiencia del mismo. Instrumento: Trabajo prctico Momento: Las especificaciones se entregan la primera semana de aplicacin de pruebas. El estudiante entregar el trabajo resuelto con la segunda prueba integral.

Plan de curso Computacin II

Elaborado por Prof..

Mara E. Mazzei. UNA 2006

V. BIBLIOGRAFA Obligatoria Joyanes, L., y Zahonero, I. (1998). Estructuras de Datos: Algoritmos, abstraccin y objetos. Madrid. Mc. Graw Hill. Complementaria

Aho, A., Hopcroft, J. E., y Ullman, J. D. (1998). Estructuras de datos y algoritmos. Mxico. Addison Wesley Longman.

Cair, O., y Guadarti, S. (2001). Estructuras de Datos. Mxico. Mc Graw Hill.

Joyanes, L. (2003). Fundamentos de Programacin. Madrid. Mc Graw Hill.

Kolman, B., Busby, R. C. y Ross, S. (1997). Estructuras de Matemticas Discretas para la Computacin. Mxico. Prentice-Hall Hispanoamericana S.A.

Ruiz, A., y Chacn, C. R. (1987). Procesamiento de Datos I. Caracas. UNA.