Ejercicios

                         EJERCICIOS RESUELTOS  PROGRAMACIÓN III 
      
  Curso 2008 ‐ 2009                   

 

 

Ejercicios resueltos de programación 3 Tema 3. Notación asintótica.

Alumna: Alicia Sánchez Centro: UNED-Las Rozas (Madrid)

El índice de los ejercicios será el siguiente. Se observa que sólo hay cuestiones de exámenes (de los ejercicios cortos), por lo que sedebería hacer hincapié en ellos: 1. Introducción teórica ………………………………………………………………………………. 3 2. Cuestiones de exámenes ………………………………………………………………………. 6

Ejercicios tema 3

Curso 2007/08

Página 2 de 9

Introducción teórica:
Previo a resolver los ejercicios pondremos un poco de teoría, que nos vendrá bien para luego hacer los ejercicios: Empezaremos viendo las distintas notaciones, para “el ordende”, cota inferior y orden exacto:

-

Notación para el orden de (cota superior): Es conveniente disponer de un símbolo matemático para representar el orden de. Sea : ℕ → ℝ una función arbitraria de los números naturales en los reales no ( ) el conjunto de todas las funciones negativos. Le indicará mediante : ℕ → ℝ tales que ( ) ≤ ∗ ( ), para todo ≥ para una constante positiva c y un umbralentero . En otras palabras: ( ) ≡ { : ℕ → ℝ |∃ Gráficamente sería: ( ) ( ) (umbral) siendo: : Cierto umbral del tamaño del problema. ( ): Acota superiormente a la función ( ). ∈ ℝ , ∈ ℕ, ∀ ≥ | ( ) ≤ ∗ ( )}

-

Notación para la cota inferior: Matemáticamente, esto significa que existe una constante real positiva umbral entero tal que ( ) ≥ ∗ ( ) siempre que ≥ . ( ) ≡ { : ℕ → ℝ |∃ Gráficamentesería: ( )≈ ( ) ∈ ( )∈ ( ) (umbral) ( ) : Cota inferior. ( ) : Cota superior. ∈ ℝ , ∈ ℕ, ∀ ≥ | ( )≥ ∗ ( )} y un

Ejercicios tema 3

Curso 2007/08

Página 3 de 9

-

Notación para el orden exacto: Diremos que ( ) está en Theta de ( ), o lo que es igual que ( ) está en el ( ) , si ( ) pertenece tanto a orden exacto de ( ) y lo denotamos ( ) ∈ ( ) como a Ω ( ) . La definición formal de ( ) =Por tanto, ( ) ≡ { : ℕ → ℝ |∃ , ∈ ℝ , ∈ ℕ, ∀ ≥ | ∗ ( )≤ ( )≤ ∗ ( )}. es: ( ) . ( ) ∩Ω

Decimos que el conjunto del orden exacto está acotado tanto inferior como superiormente por ( ). Podemos probarlo tanto por la definición como por la regla del límite. Para demostrar que una función dada no pertenece al orden de otra función tendremos estas formas: ( )

Demostración por contradicción: Es laforma más sencilla. Consiste en demostrar la veracidad de una sentencia demostrando que si negación da lugar a una contradicción. La regla del umbral generalizado: Implica la existencia de una constante real y positiva tal que ( ) ≤ ∗ ( ) para todos los ≥ 1 (tomaremos como 1, nos interesa más la definición dada por la regla del umbral sin generalizar). La regla del límite: Lo definiremoscompletamente tras analizar la cota superior y el coste exacto.

-

-

La primera y segunda manera no la usaremos por norma general, ya que no nos compensará. En cuanto a la última será la que usemos, de nuevo recordaremos la definición y lo que significa cada resultado:

Ejercicios tema 3

Curso 2007/08

Página 4 de 9

La regla del límite: Nos permite comparar dos funciones en cuanto a lanotación asintótica se refiere. Tendremos que calcular el siguiente límite: lim
( ) → ( )

.

Se nos darán 3 resultados: 1. lim ⇒
( ) → ( )

= ( ) ( )

∈

⇒ ( )∈ ( )∈ ( ) ( ) ( )∈ ( )∈ ( ) ( ) .

( )∈ ( )∈

Estas funciones se comportan igual. Se diferencian en una constante multiplicativa.
( ) → ( )

2. lim ⇒

=∞⇒ ( ) ( ) ( )∈ ( )∉ ( ) ( ) ( )∉ ( )∉ ( ) ( ) .

( )∉ ( )∈

Pormuy alta que sea la constante multiplicativa de ( ).
( ) → ( )

( ) nunca superará a

3. lim ⇒

=0⇒ ( ) ( ) ( )∉ ( )∈ ( ) ( ) ( )∉ ( )∉ ( ) ( ) .

( )∈ ( )∉

( ) crece más exponencialmente que ( ). Sería su cota superior.

Ejercicios tema 3

Curso 2007/08

Página 5 de 9

1ª parte. Cuestiones de exámenes:
Febrero 2002 -2ª (ejercicio 2) Enunciado: Un algoritmo de coste ( )...