Licenciatura en Sistemas de Información

UNSE – FCEyT

PROGRAMACIÓN II – AÑO 2011 TALLER 1: TEORÍA DE LA COMPUTABILIDAD 1. DESCRIPCIÓN Este taller consta de dos partes. En cada una de ellas se especifican:  Actividades a realizar  Material bibliográfico y /o fuentes de información – consulta Se complementa con los ejercicios planteados en el “Cuadernillo de Ejercicios de Aplicación” 2. MATERIAL BIBLIOGRÁFICO      

Barchini – Alvarez. Fundamentos Teóricos de las Ciencias de la Computación. 1998. Baum, Gabriel; Complejidad. I EBAI. Editorial Kapelusz S.A. 1987 Knuth, Donald E. Algoritmos Fundamentales. VOL I. Mandrioli Dino y Ghezzi Carlo. Theoretical Foundations of Computer Science. Editorial Jhon Wiley & Sons, 1987. Sancho San Roman. Lógica Matemática y Computabilidad, Madrid, Diáz de Santos S. A. 1990. Sitios web de Internet

3. OBJETIVOS Que el estudiante logre:  Conocer los conceptos fundamentales de la Teoría de la Computabilidad.  Habilidad para formalizar y clasificar problemas  Seleccionar el algoritmo adecuado en el proceso de resolución de problemas  Habilidad para analizar la eficiencia de un algoritmo en particular y de una clase de algoritmos. 4. PRODUCTO ESPERADO Informe escrito individual con las respuestas requeridas en cada una de las partes. Archivo digital del informe completo. La evaluación dependerá del producto entregado en tiempo y en forma. 5. CRITERIOS DE EVALUACIÓN La evaluación dependerá del producto entregado en tiempo y en forma. Se analizará:  Presentación  Completitud  Manejo conceptual y metodológico  Manejo bibliográfico  Originalidad  Para la actividad I del Apartado B, se analizará, además, correcto funcionamiento de los programas. 6. FECHA DE PRESENTACIÓN: 17/06/2011

PARTE A 1. Determine si las siguientes proposiciones son verdaderas (V) o falsas (F). Justifique su respuesta. 1.1. Es soluble el siguiente problema: “Dada una máquina de Turing, se detiene ante alguna de las posibles cadenas de entrada”.

1.2. 2n es O(3n), pero 3n no es O(2n). 1.3. Un problema es irresoluble si se ha demostrado que no puede existir un algoritmo, procedimiento o función computable que lo resuelva.

1.4. Con esta expresión (d): (d  I  (  r) (r R  q(d,r))) se formaliza la solución de un problema.

TALLER 1: TEORÍA DE LA COMPUTABILIDAD________________________________________________

2

1.5. Se denomina complejidad en tiempo asintótica a los algoritmos cuyo tiempo de ejecución crece exponencialmente en función de la entrada.

1.6. La forma más general de procedimiento mecánico es una máquina abstracta. 1.7. Cualquier problema que cumple los requisitos para pertenecer a P también cumple los necesarios para pertenecer a NP.

1.8. Un conjunto D de elementos con una propiedad dada es enumerable, si y sólo si existe un algoritmo que pueda determinar si un elemento dado pertenece o no al conjunto.

1.9. La reducción de problemas es una técnica que permite reducir la solución de un problema a la solución de otro problema cuya solubilidad o insolubilidad ya se conoce.

1.10. La complejidad de cuatro algoritmos es O(2n), O(log n), O(n3) y O(n). Cuando n es lo suficientemente grande, el algoritmo más eficiente es el que tiene complejidad O(n).

2. Marque una y sólo una de las opciones. Justifique su respuesta. 2.1. La estimación a priori: a) Se lleva a cabo en el momento de la ejecución del programa en un computador y consiste en medir los tiempos de corrida del programa en cuestión. b) Permite lograr una base real de estimación. c) Hace uso de una función, basada en un computador idealizado y en un conjunto de operaciones con costos de ejecución perfectamente especificados. n 1

2.2. El tiempo de ejecución  (n  i)  n(n  1) / 2  n2 / 2  n / 2 tiene un orden igual a: i1

2

O(n / n)

O(n2 + n)

O(n2 - n)

O(n2 )

2.3. El orden típico de un algoritmo f(n) = O(n log n) sucede cuando: a) Los algoritmos se dicen de complejidad constante. b) Los algoritmos resuelven un problema transformándolo en otros menores. c) Los algoritmos son útiles para resolver sólo algunos problemas con un volumen de datos de entrada extremadamente pequeña. d) Ninguna de las anteriores.

2.4. Se dice que un problema es de tipo P: Si se trata de un problema de decisión. Si existe un algoritmo determinista que lo resuelve en tiempo polinómico. Si existe un algoritmo no determinista que lo resuelva en tiempo polinómico. Si se trata de un problema decidible.

2.5. Dado el siguiente algoritmo, expresado en pseudocódigo, indique cuál es la complejidad del mismo.

O(n)

TALLER 1: TEORÍA DE LA COMPUTABILIDAD________________________________________________

3

O(n/2) O (log n)

PARTE B ACTIVIDAD I.

1) 2) 3) 4) 5) 6)

Serie Fibonacci Realice un algoritmo recursivo y un algoritmo iterativo para calcular la serie Fibonacci y exprese los mismos en diagramas de flujo o seudocódigo Realice la estimación a priori del algoritmo iterativo. Codifique los algoritmos utilizando un lenguaje de programación. Obtenga los tiempos reales de ejecución (comprobación a posteriori) tanto del algoritmo iterativo como del recursivo, realice las gráficas correspondientes y compárelos. Compare los resultados obtenidos en 2) y 4) para el algoritmo iterativo. Elabore las conclusiones.

ACTIVIDAD II.

Tipos de algoritmos

1) Investigue sobre el tema algoritmos, técnicas de diseño, tipos de problemas, etc. 2) Realice una clasificación, lo más exhaustiva posible, sobre los tipos de algoritmos que existen. Especifique que criterios ha utilizado para la clasificación y cite las fuentes consultadas.

3) Elabore una monografía con los puntos anteriores, según las pautas anexadas.

TALLER 1: TEORÍA DE LA COMPUTABILIDAD________________________________________________

Licenciatura en Sistemas de Información PROGRAMACIÓN II

4

UNSE – FCEyT

PAUTAS PARA LA ELABORACIÓN DE LA MONOGRAFÍA 1.

¿Qué es una monografía? Es un trabajo de investigación científica con tema restringido y extensión variable. Si está destinada a un público muy especializado y competente en la materia, la misma suele llamarse disertación o artículo técnico. El término científico supone el desarrollo de un proceso lógico de conocimiento de la verdad sobre algo.

En la monografía el redactor presenta los resultados de forma organizada y sistemática. Para sustentar la descripción y posición asumida se requiere evidencia bibliográfica de trabajos profesionales y de estudios de investigación. En general, las monografías son investigaciones exploratorias o recopilativas. Se aborda un tema poco conocido, se realiza una investigación bibliográfica en hemerotecas reales o virtuales proveniente de distintos orígenes. Se trata de agotar el tema: consultando todas las fuentes disponibles que aborden el problema elegido. Luego de recopilada la información es analizada y expuesta, de manera tal que muestran el estado actual del tema; es conveniente agregar la opinión personal o la del grupo. La particularidad de la monografía es la de referirse a un tema único, delimitado y preciso, generalmente breve donde se prioriza la profundidad. Para algunos la monografía es producto de una investigación bibliográfica, no de campo, aunque nada hay en el concepto de monografía que lleve a aceptar esta restricción. Desde el punto de vista de la presentación formal, las monografías son trabajos donde se valora claramente la buena organización y el uso de un aparato crítico bien estructurado. Es decir, una monografía es un trabajo de investigación bibliográfica sobre un determinado tema. No es una mera copia o acumulación de datos, sino que, por el contrario, lo que caracteriza el trabajo de investigación es:

2.



La selección de la información



Su análisis



La elaboración de conclusiones personales con relación a lo investigado ESTRUCTURA DE UNA MONOGRAFÍA

Independientemente del tipo de trabajo escrito que sea realizado, se puede comprobar que existen lineamientos generales, (una estructura básica que se mantiene) que el autor o los autores deben respetar. Para preparar una monografía deben seguirse ciertas pautas. Por lo general, se la divide en tres cuerpos principales:

a) INTRODUCCIÓN En la introducción, se PLANTEA EL PROBLEMA, es decir, se hace una breve referencia a la elección del tema y a los motivos que nos llevaron a dicha elección, y se menciona todo aquello que puede aportar a la investigación. Por otro lado, se DELIMITA EL PROBLEMA. Dentro del tema que se selecciona, se elige un subtema, que será más específico. Esto supone una opción o preferencia, y se especifica desde qué enfoque o ángulo se va a tratar el tema general. De aquí surge el TÍTULO de la monografía, que será un indicador del contenido real de lo investigado y no, algo general.

TALLER 1: TEORÍA DE LA COMPUTABILIDAD________________________________________________

5

En la introducción se puede expresar también, por ejemplo, si se han tenido problemas con la recopilación de datos, el manejo de bibliografía, o con el desarrollo de los temas. También se puede manifestar la conformidad con el resultado de la investigación realizada.

b) DESARROLLO TEMÁTICO Es el cuerpo principal del trabajo, donde se refleja la tarea de selección, de análisis del material, de su elaboración. Es importante seguir las pautas generales con respecto a la transcripción de textos para no plagiar las palabras del autor y que éstas pasen como propias. Por esa razón, se debe citar la fuente de la cual se ha obtenido dicha información o hacer referencia a ella. De este modo, se distingue lo que es elaboración personal (quizás inspirado en algún autor) de las palabras o ideas de otros. Si tomamos la idea de un autor, es preciso mencionarlo y aclarar de dónde hemos extraído dicha información.

c) CONCLUSIÓN En esta parte de la monografía, se incluyen las inferencias que realiza quien investiga. Aquí se sintetizan las conclusiones a las que arribó después de haber expuesto los distintos aspectos durante el desarrollo temático. Las conclusiones siempre deben estar fundamentadas y apoyadas en la opinión de autores, o en investigaciones anteriores. Como ya se ha dicho, no se deben transcribir las opiniones de otros autores, excepto para convalidar o apoyar las propias. En síntesis, podemos decir que la conclusión será aquello que el investigador infiere de su elaboración, lo que concluye al finalizar la elaboración de todos los temas.

3.

Fases en el proceso de la monografía. Recomendaciones



Selección del tema. Considerar: relevancia e importancia, interés , accesibilidad a las fuentes de información, suficiente material disponible



Limitación del tema: Objetivo de la monografía y tiempo disponible



Formulación de la hipótesis y / objetivos: ¿Qué quiere probar / lograr con este trabajo? ¿Qué quiere probar / lograr con este tema en específico?



Búsqueda y recopilación de la información. Consultar las diversas herramientas y fuentes de información de la biblioteca, tales como:     

Catálogo Público en Línea Bases de Datos en Línea Investigación en Internet Revistas Profesionales Periódicos



Evaluación del material disponible: Lea las fuentes bibliográficas y el material disponible en la biblioteca, comenzando por las obras generales o de referencia. Haga anotaciones pertinentes que le ayudarán en el momento de redactar.



Bosquejo del trabajo escrito: Delimite finalmente el tema. Organice el bosquejo por capítulos, subcapítulos, apartados, subapartados, etc. , según la extensión del trabajo.



Redacción del trabajo: Use un estilo formal, con lenguaje claro, sencillo y sin errores. Realice las citas de referencia en el texto para sustentar algún punto o argumento (pueden ser citas textuales o parafraseadas. ASPECTOS FORMALES PARA TENER EN CUENTA



La monografía debe entregarse en la fecha y la forma requeridas. El documento debe estar en formato Word 6.0 o superior. Una copia en papel y otra en formato magnético (disquete o CD).



El orden de la presentación del documento debe ser el siguiente: carátula, texto del documento, bibliografía y anexos (si corresponde).

TALLER 1: TEORÍA DE LA COMPUTABILIDAD________________________________________________

6



La extensión del debe ser como mínimo 10 (diez) páginas y cómo máximo 30 (treinta) páginas, escritas en tipografía Times New Roman con cuerpo de letra N° 11 .



Debe emplearse papel tamaño A4, Los márgenes superior, inferior y laterales deben ser de 2 cm., cada uno.



El espaciado entre líneas debe ser de 1,5.



Es necesario indicar la bibliografía utilizada. Se debe incluir todo el material empleado, según las pautas observadas para las citas bibliográficas (autor, título, editorial, fecha de edición, etc.).



El índice no debe faltar, porque será una guía para el que lea el trabajo.



En la carátula colocar: nombre del seminario, el tema y el título elegidos, nombres y apellidos del autor (dirección electrónica), lugar y fecha.