Casos De Estudio Sobre Análisis Caso

Casos de estudio sobre Análisis Caso-Promedio para un curso elemental de Algoritmos
Abstract—Análisis algoritmo de Promedio de los casos es por lo general visto como un tema difícil por los estudiantes en los primeros cursos de la informática. Tradicionalmente, estos temas se desarrollan plenamente en cursos avanzados con una orientación matemática clara. El trabajo que aquí se presenta no esuna alternativa a esto, sino que se presenta el análisis de algoritmos (y la media de los casos, en particular) adaptado a la formación matemática de los estudiantes en un curso elemental de algoritmos o de programación mediante el uso de dos estudios de caso seleccionados.
I. INTRODUCTION
En este trabajo se complementa el contenido de una parte significativa de un curso elemental sobre Análisis delalgoritmo. Un curso como este se está enseñando en la Universidad de Valencia en el marco de los planes de estudios actualizados recientemente en Ciencias de la Computación en España ("Ingeniería en Informática"). De acuerdo con el calendario actual de estos estudios, algunos de los temas obligatorios sobre Análisis Algoritmo tienen que ser incluidos en los primeros años de estudio con casininguna experiencia previa con
Programación avanzada y con un conocimiento limitado sobre Álgebra, Cálculo y Matemática Discreta.
En este contexto, el documento propone la utilización de algunos estudios de casos seleccionados para practicar análisis de caso promedio. Dependiendo en el fondo de los estudiantes, el material presentado en este trabajo podría ser cubierto mediante sesiones deaula-laboratorio mixto de alrededor de cuatro a ocho horas. Otros algoritmos similares podrían también se han considerado ya sea como alternativa o para profundizar en este tema. El único requisito del enfoque que aquí se presenta es que el estudiante se supone que debe conocer técnicas básicas de programación y, al menos, un lenguaje de programación de alto nivel (Pascal, por ejemplo)
Algoritmos iterativossencillos se han seleccionado con el fin de obtener fácilmente expresiones exactas sobre su desempeño.
Sin embargo, estos algoritmos seleccionados presentan casos interesantes desde el punto de vista de la obtención de su peor y promedio de rendimiento. La implementación de los algoritmos que utilizan un lenguaje de programación de alto nivel y las medidas empíricas sobre ellos ayudar al estudiantea entender la importancia de analizar los algoritmos y las diferencias entre algoritmos eficientes y no eficientes.
Mientras que el material que se presenta en este documento no puede realmente ser considerado nuevo, algunas contribuciones esperemos originales son:
1) la selección de los algoritmos a estudiar, de manera que un análisis preciso se puede hacer a un nivel elemental y
2) lapresentación del análisis teórico que se basa en conceptos y herramientas matemáticas elementales, por lo que las mismas observaciones que en 1) sostienen. Otra contribución de este trabajo es la derivación de las varianzas de los dos algoritmos que utilizan las mismas herramientas matemáticas.
Este artículo está organizado de la siguiente forma: En la siguiente sección, se explican las principalesmotivaciones y objetivos de este trabajo.
Sección III describe brevemente el contenido de las clases teóricas que deben preceder a las prácticas presentadas. El contenido de los dos estudios de casos considerados son exhaustivamente descritos en la Sección IV. El documento termina con la Sección V, donde se describen las principales conclusiones y posibilidades de nuevas prórrogas.
II. MOTIVATION ANDOBJECTIVES
El estudio de los algoritmos es una de las bases de programación moderno y es ampliamente entendido como un pre-requisito común a muchos otros temas en Estudios de Ciencias de la Computación [2]. El análisis del comportamiento de los algoritmos en términos de complejidad de tiempo es un campo bien establecida tanto en ambientes de enseñanza y de investigación. El caso particular de...