• Author / Uploaded
• Daniel Rodriguez

Citation preview

Universidad Polit´ecnica de San Luis Potos´ı Academia de Tecnolog´ıas de la Informaci´on y Telem´atica An´alisis y Disen˜o de Algoritmos Tarea 1. Dr. Omar Montan˜o Rivas Urbano Villal´on nu´m. 500, Col Ladrillera, C.P. 78363 Universidad Polit´ecnica de San Luis Potos´ı San Luis Potos´ı, SLP Objetivos Recordar el contenido de materias como Programaci´on III, Matem´aticas Discretas y Probabilidad y Estad´ıstica. Particularmente, conceptos generales de programaci´on orientada a objetos, sumatorias, multiplicatorias, expectativa aleatoria, entre otros. Repasar conceptos vistos en clase como lo son el an´alisis de algoritmos y clasificaci´on de funciones por su tasa de crecimiento asint´otica.

1.

Java como lenguaje algor´ıtmico 1. Defina una clase organizadora para informaci´on personal que consiste en nombre, direcci´on, nu´mero telef´onico y direcci´on de correo electr´onico, haciendo supuestos razonables acerca de c´omo ser´ıa necesario desglosar estos elementos.

2.

Antecedentes matem´aticos 1. Para toda n > 0 y k > 0, demostrar que

2. Demuestre que logc x = logb x/logb c.

3. Demuestre que si S y T son estoc´asticamente independientes, entonces

Pr(S|T) = Pr(S)

y

Pr(T|S) = Pr(T)

4. ¿Qu´e probabilidad condicional tienen estos cuatro sucesos dado que A < B y D < C, en la situaci´on del ejemplo 1.5 (del libro de Baase y Van Gelder): A < C, A < D, B < C, B < D? 5. Suponga que hay tres monedas sobre una mesa. Se escoge una moneda al azar y se lanza. Queremosdeterminar la probabilidad de que, despu´es del lanzamiento, la mayor parte de las monedas (es decir, dos o tres de ellas) est´e con la cara hacia arriba, partiendo de diversas configuraciones iniciales. Para cada configuraci´on inicial que se d´a m´as adelante, d´e nombres a las monedas, defina los sucesos elementales, y d´e sus probabilidades. ¿Cu´al conjunto de sucesos est´a definido por la propiedad de que la mayor parte de las monedas muestren cara despu´es del lanzamiento, y qu´e probabilidad tiene este suceso? Suponga que originalmente las monedas muestran a) cara, sello, sello b) sello, sello, sello c) cara, cara, sello

6. Muestre que

(1) manipulando la serie arm´onica.

7. Muestra que

8. Evalua la sumatoria 9. Evalua el producto

.

3.

An´alisis de algoritmos y problemas 1. La mediana de un conjunto ordenado es un elemento tal que el nu´mero de elementos menores que la mediana difiere en cuando m´as 1 del nu´mero de elementos que son mayores, suponiendo que no hay empates. a) Escriba un algoritmo para hallar la mediana de tres enteros distintos, a, b y c. b) Describa D, el conjunto de entradas del algoritmo, a la luz de la explicaci´on de la secci´on 1.4.3 que sigue al ejemplo 1.9 (del libro de Baase y Van Gelder). c) ¿Cuantas comparaciones efectu´a su algoritmo en el peor caso? ¿En promedio? d) ¿Cuantas comparaciones son necesarias en el peor caso para hallar la mediana de tres nu´meros? Justifique su respuesta.

4.

Clasificacio´n de funciones por su tasa de crecimiento asint´otica 1. Sea p(n) = aknk +ak−1nk−1 +...+a1n+a0 un polinomio en n de grado k con ak > 0. Demuestre que p(n) est´a en Θ(nk). 2. Para cada una de las expresiones A y B de la tabla de abajo, indica si A es O, Ω , ´o bien Θ de B. Asume que k, m, y n son enteros positivos, 1 son constantes. Debes de escribir en cada una de las casillas s´olo SI o NO.

5.

Observaciones

La fecha limite para entregar esta tarea es el d´ıa 13/02/2017. ¡Por ningu´n motivo se aceptar´an trabajos fuera de tiempo!

Referencias [1] Sara Baase, Allen van Gelder. Algoritmos computacionales: Introducci´on al an´alisis y disen˜o, tercera edici´on. Addison Wesley. [2] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to algorithms, second edition. The MIT Press.

2