Algoritmos y Eficiencia de Funcion f

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

¿Por qué la expresión $n - i + 1$ no puede ser siempre considerada una cota válida?

Porque j siempre decrece en cada iteración.

Porque siempre se mantiene positiva durante el bucle.

Porque depende de los valores del vector v. (correct)

Porque j debe ser igual a n para ser válida.

¿Qué condición debe cumplir una función de cota válida?

Decrecer en cada iteración. (correct)

Aumentar en cada iteración.

Ser mayor que n.

Ser siempre positiva.

¿Cuál de las siguientes afirmaciones es incorrecta sobre la llamada $f([1, 2, 3, 4, 5], 1, 3)$?

No tiene valores posibles para a y b que cumplan las condiciones. (correct)

Devuelve el resultado correcto según las condiciones.

Cumple las precondiciones.

Es válida porque k y n son mayores que 0.

¿Cuál es la correcta llamada a la función f que satisface la especificación dada?

f([1, 1, 9, 0, 3, 4, 4], 2, 5) con resultado 4. Signup and view all the answers

¿Qué indica la expresión $b - a + 1 = k$ en el contexto de la función f?

Define la longitud del intervalo considerado. Signup and view all the answers

¿Por qué la llamada a la función f(en un vector, con k < 0) fallaría?

Porque k no puede ser negativo. Signup and view all the answers

Si $n ≤ 4$, ¿cuál es la posible consecuencia de la expresión inicial de la variable i?

Puede resultar en valores negativos. Signup and view all the answers

¿Cuál de las siguientes afirmaciones describe incorrectamente el intervalo [a, b]?

El intervalo debe incluir el índice n. Signup and view all the answers

¿Cuál es la respuesta para $T(n)$ cuando $n \leq 1$?

$T(n) = c$ Signup and view all the answers

¿Qué se puede deducir sobre $T(n)$ cuando $n > 1$?

$T(n)$ sigue una relación recursiva. Signup and view all the answers

La generalización se utiliza para:

Obtener funciones más generales que las deseadas. Signup and view all the answers

¿Cuál de las siguientes afirmaciones sobre la mejora de eficiencia de algoritmos recursivos es correcta?

Añadir parámetros puede mejorar la eficiencia. Signup and view all the answers

¿Qué implica la definición recursiva en algoritmos como quicksort y mergesort?

Requieren parámetros adicionales para su correcta ejecución. Signup and view all the answers

¿Cómo se describe el proceso para obtener versiones recursivas finales a partir de versiones no finales?

Se necesita añadir un parámetro acumulador. Signup and view all the answers

La relación $T(n) = 2T(n/2) + c'n$ es un ejemplo de cuál concepto?

Recursión binaria. Signup and view all the answers

En el contexto de algoritmos recursivos, ¿cuál es el efecto de no definir adecuadamente el caso base?

Podría ocasionar un bucle infinito. Signup and view all the answers

¿Qué relación establece la ecuación $T(n) = T(n-1) + T(n-2) + c_1$?

Es una relación recursiva de Fibonacci. Signup and view all the answers

¿Cuál es la notación que representa el crecimiento de $T(n)$ según el contenido?

$T(n) ext{ pertenece a } O(2^n)$ Signup and view all the answers

¿Bajo qué condición termina el algoritmo de búsqueda binaria descrito?

Si $c$ es mayor que $f$. Signup and view all the answers

¿Qué sucede si la precondición inicial $c ightarrow f$ se mantiene?

Podría causar un bucle infinito. Signup and view all the answers

¿Qué conclusión se puede obtener acerca de la función $f(int v[], int x, int c, int f)$?

El algoritmo requiere un arreglo ordenado. Signup and view all the answers

¿Qué componente asegura que el algoritmo termina en caso de que $c$ y $f$ sean iguales?

Se retorna el valor de $c$. Signup and view all the answers

¿Por qué es incorrecto afirmar que $T(n) otin O(n ext{ log } n)$?

Porque $T(n)$ crece más rápido que $n ext{ log } n$. Signup and view all the answers

¿Qué condición inicial es necesaria para aplicar el algoritmo de búsqueda binaria eficientemente?

$c ext{ debe ser menor que } f$. Signup and view all the answers

¿Cuál es la ventaja de añadir parámetros adicionales a los algoritmos recursivos?

Mejorar la eficiencia de los algoritmos recursivos. Signup and view all the answers

¿Qué caracteriza a un algoritmo recursivo cuando se reduce el tamaño del problema por sustracción?

Es exponencial si a > 1. Signup and view all the answers

¿Cuál es el coste para $a = 1$ en un algoritmo recursivo según la fórmula mencionada?

Es polinómico. Signup and view all the answers

¿Cuál de las siguientes afirmaciones sobre los parámetros adicionales en algoritmos de ordenación es correcta?

Ayudan a ordenar segmentos específicos de un vector. Signup and view all the answers

¿Qué sucede si se añade un parámetro acumulador al transformar un algoritmo recursivo no final en uno final?

Se optimiza el rendimiento del algoritmo. Signup and view all the answers

En un algoritmo recursivo, ¿qué implica que el coste sea exponental cuando 'a > 1'?

El tiempo de ejecución crecerá rápidamente al aumentar el tamaño del problema. Signup and view all the answers

¿Cuál es el principal propósito de utilizar métodos de ordenación como quicksort y mergesort?

Ordenar eficientemente segmentos de datos. Signup and view all the answers

¿Qué se puede definir como la característica clave en la transformación de un algoritmo recursivo no final a uno final?

El uso de un parámetro acumulador. Signup and view all the answers

Cuántos intervalos [a, b] se encuentran en el vector [1, 1, 9, 0, 3, 4, 4] tal que cumplen con la longitud k = 2 y n = 5?

4 Signup and view all the answers

Cuál de las siguientes afirmaciones sobre límites es cierta?

𝛩(n^2) = 𝛩(2 * n^2) Signup and view all the answers

Qué condición deben cumplir los valores k y n para ser válidos en la función mencionada?

k y n deben ser mayores o iguales que 0 Signup and view all the answers

Cuál de las siguientes afirmaciones es incorrecta?

𝑂(n) ⊆ 𝜔(log n) Signup and view all the answers

Qué resultado se obtiene al aplicar el teorema del límite a lim (log n) / n cuando n tiende a infinito?

0 Signup and view all the answers

Cuál es la relación válida entre las notaciones de complejidad 𝛩(n^2) y 𝛩(2 * n^2)?

Son equivalentes Signup and view all the answers

Cuál de las siguientes condiciones es parte de la postcondición de los intervalos?

Los valores del vector deben ser crecientes Signup and view all the answers

Cuál de las siguientes combinaciones es incompatible con las condiciones de k y n?

k = -1, n = 5 Signup and view all the answers

Bajo qué condición el algoritmo de búsqueda binaria nunca termina?

Cuando c es menor o igual a f Signup and view all the answers

¿Qué afirmación es cierta respecto al punto medio en el algoritmo de búsqueda binaria?

El punto medio se calcula como m = (c + f) / 2. Signup and view all the answers

¿Cuándo termina el algoritmo de búsqueda binaria según la implementación dada?

Solo termina si c es mayor que f Signup and view all the answers

¿Cuál es un error común en la interpretación de la terminación del algoritmo de búsqueda binaria?

Creer que el algoritmo solo puede terminar si hay un valor encontrado. Signup and view all the answers

¿Cuál es un caso base en el algoritmo que podría conducir a una recursión infinita?

Cuando c = f Signup and view all the answers

¿Qué ocurre en la llamada recursiva si v[m] es mayor que x?

Se invoca esta lógica nuevamente con f ajustado. Signup and view all the answers

¿Por qué es importante la condición 0 ≤ c ≤ f + 1 ≤ longitud(v)?

Para garantizar que el algoritmo tenga índices válidos. Signup and view all the answers

¿Qué se puede concluir sobre la técnica de búsqueda binaria en comparación con la búsqueda lineal?

Requiere que el array esté ordenado. Signup and view all the answers

Study Notes

Fundamentos de Algoritmia - Examen de Enero

Observaciones:
- En los exámenes, hay una única respuesta correcta por pregunta.
- Cada respuesta correcta vale 0.1 puntos.
- Cada respuesta incorrecta resta 0.033 puntos.

Pregunta 1

Especificación:
- {v.size ≥ 0}
- fun xxx(vector v) dev intr
- {r = maxp, q : 0 ≤ p ≤ q ≤ v.size ∧ ∀i : p < i < q : v[i] = 0 : q - p}
Vector de entrada: v = [5, 4, 0, 4, 3, 0, 0, 0, 0, 5, 3, 0, 0, 5]
Pregunta: ¿Cuál es el valor de r según la especificación?
Respuesta: (a) r = 7.

Pregunta 2

Pregunta: ¿Cuál es la complejidad en el peor caso de un algoritmo óptimo que busca el máximo en un vector ordenado de n elementos?
Respuesta: (c) Θ(n).

Pregunta 3

Algoritmo:
- int c = 0;
- for (int i = 1; i < n; i *= 2)
- for (int j = 0; j < m+2; ++j)
- c += 4;
Pregunta: ¿Cuál es la complejidad del algoritmo?
Respuesta: (b) Θ(mlog n).

Pregunta 4

Predicado:
- b = ∃w : 0 ≤ w < n : (∃k : 0 ≤ k : a[w] = 2 * k + 1)
Pregunta: ¿Qué significa el predicado para un vector a de n enteros con n ≥ 1 y una variable booleana b?
Respuesta: (a) Hay al menos una posición en el vector que contiene un número impar positivo.

Pregunta 5

Especificación:
- {a.size ≥ 0}
- fun contar Pares(vector a) dev int c
- {c = #i : 0 < i < a.size : a[i] % 2 = 0}
Algoritmo:
- int contarPares (vector const& a) {
- int c=0; int k=-1;
- while (k<a.size()-1)
- { if (a[k+1] % 2 == 0) {c=c+1;} k=k+1; }
- return c; }
Pregunta: Determina si el algoritmo anterior es correcto y, en su caso, cuál es el invariante.
Respuesta: (a) Es correcto con invariante {−1 ≤ k < a.size \ c = #i : 0 ≤ i ≤ k : a[i] % 2 = 0}.

Pregunta 6

Pregunta: Indica cuál de las siguientes afirmaciones sobre el algoritmo quicksort es falsa.
Respuesta: (a) Si los valores del vector están ordenados en orden creciente, tiene una complejidad cuadrática respecto al tamaño del vector.

Pregunta 7

Pregunta: ¿Qué dos algoritmos tienen el mismo orden de complejidad?
Respuesta: (a) se comportan de forma semejante para tamaños de entrada grandes.

Pregunta 8

Pregunta: ¿Cuál es el requisito imprescindible para utilizar el algoritmo de búsqueda binaria sobre un vector?
Respuesta: (c) Los valores del vector deben estar ordenados.

Pregunta 9

Algoritmo:
- int k = 0; int N = 100;
- for (int i = N-1; i > -N; --i) ++k;
Pregunta: Indica qué función de cota utilizarías para probar la terminación del bucle.
Respuesta: (d) f(i,N) = N-i

Pregunta 10

Recurrencia:
- T(n) = (n-1) + n si n > 0
- T(n) = 0 si n = 0
Pregunta: ¿Cuál es el coste del algoritmo con esa recurrencia?
Respuesta: O(n²).

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Description

Este cuestionario explora conceptos clave en análisis de algoritmos, incluyendo condiciones para cotas válidas y especificaciones en funciones recursivas. También se examina la mejora de la eficiencia en algoritmos como quicksort y mergesort. Ideal para estudiantes de algoritmos avanzados.