Estructuras de datos y algoritmos | conjunto 6

Se han hecho las siguientes preguntas en el examen GATE CS.

1. La implementación habitual Θ(n^2) de Ordenación por inserción para ordenar una array utiliza la búsqueda lineal para identificar la posición en la que se insertará un elemento en la parte ya ordenada de la array. Si, en cambio, usamos la búsqueda binaria para identificar la posición, el tiempo de ejecución en el peor de los casos (GATE CS 2003)
(a) seguirá siendo Θ(n^2)
(b) se convertirá en Θ(n(log n)^2)
(c ) se convierte en Θ(n log n)
(d) se convierte en Θ(n)

Respuesta (a)
Si usamos la búsqueda binaria, habrá ⌈ Log ₂ (n!) ⌉ comparaciones en el peor de los casos, que es Θ(n log n) ( Si quiere saber cómo ⌈ Log ₂ (n!) ⌉ puede ser igual a Θ(n log n)), luego vea esto como prueba). Pero el algoritmo en su conjunto aún tendrá un tiempo de ejecución de Θ(n^2) en promedio debido a la serie de intercambios necesarios para cada inserción.

Referencia:
http://en.wikipedia.org/wiki/Insertion_sort

2. El límite inferior más estricto del número de comparaciones, en el peor de los casos, para la clasificación basada en comparaciones es del orden de
a) n
b) n^2
c) nlogn
d) n(log^2)n

Respuesta (c)
El número de comparaciones que requiere un algoritmo de ordenación por comparación aumenta en proporción a nlog(n), donde n es el número de elementos a ordenar. Este límite es asintóticamente estrecho:

Dada una lista de números distintos (podemos suponer esto porque este es un análisis del peor de los casos), hay n permutaciones factoriales, exactamente una de las cuales es la lista en orden ordenado. El algoritmo de clasificación debe obtener suficiente información de las comparaciones para identificar las permutaciones correctas. Si el algoritmo siempre se completa después de un máximo de f(n) pasos, no puede distinguir más de 2^f(n) casos porque las claves son distintas y cada comparación tiene solo dos resultados posibles. Por lo tanto,

    2^f(n) >= n!, or equivalently f(n) > Log2(n!). 

Referencias:
http://en.wikipedia.org/wiki/Comparison_sort
http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15451-s07/www/lecture_notes/lect0130.pdf

3. El problema 3-SAT y 2-SAT son
a) ambos en P
b) ambos NP completos
c) NP-completos y en P respectivamente
d) indecidibles y NP-completos respectivamente

Respuesta (c)
El problema booleano de satisfacibilidad (SAT) es un problema de decisión, cuya instancia es una expresión booleana escrita usando solo AND, OR, NOT, variables y paréntesis. El problema es: dada la expresión, ¿hay alguna asignación de valores VERDADERO y FALSO a las variables que harán que toda la expresión sea verdadera? Se dice que una fórmula de lógica proposicional es satisfactoria si se pueden asignar valores lógicos a sus variables de manera que la fórmula sea verdadera.

3-SAT y 2-SAT son casos especiales de k-satisfactibilidad (k-SAT) o simplemente satisfacibilidad (SAT), cuando cada cláusula contiene exactamente k = 3 yk = 2 literales respectivamente.

2-SAT es P mientras que 3-SAT es NP Completo. (Ver esto para una explicación)

Referencias:
http://en.wikipedia.org/wiki/Boolean_satisfiability_problem

4. Considere el siguiente gráfico


Entre las siguientes secuencias
I) abeghf
II) abfehg
III) abfhge
IV) afghbe
¿Cuáles son los primeros recorridos en profundidad del gráfico anterior? (GATE CS 2003)
a) Solo I, II y IV
b) Solo I y IV
c) Solo II, III y IV
d) Solo I, III y IV

Respuesta (d)

Escriba comentarios si encuentra que alguna de las respuestas/explicaciones anteriores es incorrecta.