Cuestionario de salvamento.

Complejidad

Lea cuidadosamente. a**n se lee como "a elevado a la n".

1. Se sabe que P=NP.

Verdadero
Falso


2. Todo algoritmo ejecutable en espacio constante es lineal en tiempo total de ejecución.

Falso
Verdadero


3. O(n) contiene O(n**2).

Falso
Verdadero


4. Existen 2**n-2 subconjuntos propios de un conjunto de n elementos.

Verdadero
Falso


5. Prolog es el único lenguaje de programación determinista.

Falso
Verdadero


6. Toda función periódica de los naturales a los naturales expresa una función recursiva primitiva.

Verdadero
Falso


7. Con f(1)=1, y f(n) = f(n-1) se tiene una función recursiva primitiva, con valor f(n)=n.

Verdadero
Falso


8. Es bueno utilizar apuntadores en el análisis de complejidad de un algoritmo.

Verdadero
Falso


9. El polinomio h(x) = a+b*x+c*x**2 es una función computable según Kleene.

Verdadero, si a,b,c y x toman valores enteros.
Falso, si a, b, c y x son números reales.


10. Considera la cadena "abaaaaabbbac".

Puedo formar con esto un palíndromo.
No puedo formar un palíndromo.

Después de terminar tu cuestionario,mantén durante un periodo de tiempo la pantalla. Salva tu resultado mediante PrScr.

s

Verdadero o falso?

1) P=NP.

2). Todo algoritmo ejecutable en espacio constante es lineal en tiempo total de ejecución

3) O(n) contiene a O(n**2).

4) Existen 2**n-2 subconjuntos propios de un conjunto de n elementos.

5) Con f(1)=1,  y f(n) = f(n-1) se tiene una función recursiva primitiva, con valor f(n)=n.

6) Toda función periódica de los naturales a los naturales puede expresarse como una función recursiva primitiva.

7) Considera la cadena "abaaaaabbbac". Halla un palíndromo con los caracteres (todos) de esta cadena. 

Te costó lo mismo hallar el palíndromo que verificar que lo es.

8) Es bueno utilizar apuntadores en el análisis de complejidad de un algoritmo.

9) Es bueno utilizar Python en el análisis de complejidad de un algoritmo.

10) El polinomio h(x) = a+b*x+c*x**2 es una función computable según Kleene (a,b,c: constantes enteras, x variable entera).