Parcial 2 - Algoritmo y Estructura de Datos I PDF

Preview

Summary

Parcial 2 - Algoritmo y Estructura de Datos I...

Description

( 3.1 ) ¿Cómo conocemos a un algoritmo que expresa la solución de un problema realizando reiteradas llamadas a sí mismo? –

Recursivo

( 3.1 ) Si un método se llama a si mismo, no esta repitiendo las mismas operaciones y datos y por ende obteniendo los mismos resultados? –

No, porque en cada llamada a si mismo opera con instancias diferentes

( 3.1 ) Una función recursiva puede ser reemplazada por una función: –

Iterativa

( 3.3 ) ¿En recursión, qué significa “es necesario creer”? –

Asume siempre que la llamada recursiva funciona

( 3.3 ) ¿De qué se componen las funciones recursivas? –

De al menos un caso base y un caso recursivo

( 3.3 ) ¿Qué buscamos al ejecutar sucesivos pasos recursivos? –

Acercarnos al caso base

( 3.3 ) ¿Cuál de los siguientes enunciados no es una regla fundamental de la recursión? –

Regresión

( 3.3 ) En funciones recursivas, ¿cómo se llama a una posible solución simple para un caso particular? –

Caso base

( 3.3 ) ¿Cómo podemos clasificar a las funciones recursivas de acuerdo a desde donde se hace la llamada recursiva? Seleccione las 2 (dos) opciones correctas – –

Directa Indirecta

( 3.5 ) Según la aritmética modular, a y b se encuentran en la misma clase de congruencia “modulo n”, si ambos dejan diferente resto al dividirlo entre n, o equivalentemente si a-b es un múltiplo de n. –

Falso

( 3.5 ) ¿Cómo se conoce a la secuencia de números en la que el k-ésimo número es la suma de los dos números anteriores? –

Fibonacci

( 3.6 ) ¿Cuál simbolo utilizamos para especificar que dos números enteros a y b son congruentes? –

≡

( 3.8 ) ¿Cuál es el MCD de 40 y 36? –

4

( 3.9 ) ¿Cuántas claves emplea el algoritmo DES? –

1

( 3.9) Si utilizamos el algoritmo RSA, ¿Cuáles son los pasos generales que se necesitan? –

Generación de claves, cifrado y descifrado

( 3.9 ) Indique 4 (cuatro) formas válidas en la que la comunicación entre un emisor y un receptor puede ser amenazada – – – –

Modificación Interrupción Intercepción Fabricación

( 3.10 ) ¿Cómo se conoce a la técnica recursiva de resolución de problemas general que se caracteriza por dividir un problema en subproblemas más sencillos? –

Divide y vencerás

( 3.11 ) Si tuvieramos la necesidad de desarrollar un algoritmo con la necesidad que este algoritmo pruebe sistemáticamente todas las posibilidades, usaríamos los conceptos de: –

Algoritmo de vuelta atrás

( 3.11 ) ¿De qué estamos hablando al afirmar que “en una secuencia de decisiones óptima toda subsecuencia debe ser óptima también? –

Programación dinámica

( 3.11 ) ¿Cómo se conoce a una mejora del algoritmo minimax? –

Poda alfa-beta

( 3.11 ) ¿Cómo se conoce la estrategia utilizada para el ta-te-ti (entre otros juegos por ejemplo) basada en la suposición de que ambos jugadores juegan de forma óptima? –

Minimax

(3.12 ) ¿Comó llamamos a los algoritmos que prueban alternativas y si encuentran una

incorrecta la busqueda retrocede hasta el paso anterior y toma otra para seguir evaluando? –

Backtracking

( 4.1 ) La problemática de ordenamiento esta relacionada a: –

La mejor busqueda de elementos

( 4.1 ) Seleccione 3 (tres) algoritmos de ordenamiento que tengan complejidad cuadrática: NO VAN: Quicksort /// Mergesort – Brbuja – Inserción – Selección ( 4.1 ) ¿Cómo se conoce cuando en un proceso de ordenamiento los datos no pueden almacenarse en la memoria principal? –

Externo

( 4.2 ) El ordenamiento por inserción (en el peor de los casos) –

Tiene una complejidad de o(n^2)

( 4.2 ) Para casos de datos pequeños, el algoritmo recomendado es: –

El algoritmo de ordenación por inserción

( 4.2 ) ¿Cuál es el ordenamiento en el cual recorremos el arreglo comparando el valor del iésimo elemento con el valor del elemento i+1 y si estos se encuentran desordenados, entonces los permutamos? –

Burbuja” o burbujero; o bien bubblesort

( 4.2 ) Dada la estructura: (100, 65, 40, 10) ¿Cuántas inversiones son necesarias para ordenar completamente los elementos? –

5

( 4.2 ) Dado un array de datos llamado A, de tamaño N. Si para cada i de [0..N-2] intercambiamos A[i] con el mínimo elemento subarray [A[i+1], …,A[N]]; ¿de qué algoritmo de ordenación estamos hablando? –

Selección

( 4.3 ) Identifique 4 (cuatro) enunciados válidos relacionados al algoritmo “shellsort”: NO VA: “Se basa en el principio de comparar pares de elementos adyacentes... – Algorirmo subcuadrático – Tiene mejor rendimiento que el método de insereción clásico – Se lo conoce como “ordenación con espacio decreciente”.

–

Depende fuertemente de la secuencia de incrementos”

( 4.4 ) ¿A cual metodo de ordenamiento podemos resumirlo de la siguiente manera: (1) dividir el conjunto de elementos (>1) por la mitad (2) ordenar cada subconjunto de manera recursiva (3) mezclar los subconjuntos uniéndolos en un único conjunto ordenado? –

Mergesort

( 4.5 ) ¿Qué complejidad representa el metodo quicksort en el peor de los casos? –

O(n^2)

( 4.5 ) ¿Qué complejidad represena el metodo quicksort en el mejor de los casos? –

O(n log n)

( 4.5 ) La mejor solución en quicksort es seleccionar como pivote al primer elemento –

Falso

( 4.5 ) En el algoritmo Quicksort utilizamos el termino PARTICION para indicar que: –

Dividimos al vector en dos grupos, excepto al pivote; en uno los menores al pivote y en otro los mayores al pivote.

( 4.7 ) ¿Cuál es la complejidad del algoritmo radixsort? –

Lineal

( 5.1 ) ¿Cuál es el tipo de distribución que su curva gráfica tiene forma de campana simétrica respecto al valor de la media? –

Distribución normal

( 5.1 ) El algoritmo que introduce un número conformado por 10 dígitos, lo eleva al cuadrado, toma exactamente los 10 dígitos ubicados en la mitad del número resultante, y ese número lo toma como un nuevo número aleatorio y como entrada al próximo ciclio lo conocemos como: –

Método del cuadrado medio

( 5.1 ) ¿Cuáles son números compuestos? Selecciones las 4 (cuatro) respuestas correctas NO VA: 11 – 6 – 8 – 9 – 4 ( 5.1 ) Indique 4 (cuatro) tipos de distribuciones de probabilidad válidas: –

Binomial

– – –

Normal De Poissson Hipergeométrica

( 5.1 ) ¿Cuáles son usos de los números aleatorios? Seleccione las 3 (tres) respuestas correctas. – – –

Simulación Criptografía Prueba de programas

( 5.1 ) ¿Cómo se conocen a los números que tienen muchas propiedades de los números aleatorios? –

Pseudoaleatorios

( 5.2) ¿Cómo se denomina a la longitud de la secuencia hasta que un número se repite? –

Periodo

( 5.2 ) Dada la secuencia 0, …. , 999 distribuida uniformemente; indique 2 (dos) propiedades correctas que se cumplirían – –

El primer número tiene una probabilidad de ser 0,1,2 …, 999 La media esperada de todos los números generados es 499,5.

( 5.2 ) Una SEMILLA la definimos como: –

El valor con el cual comenzamos el ciclo de generación de números aleatorios

( 5.2 ) ¿Cómo se denomina al valor inicial de números aleatorios? –

Semilla

( 5.2 ) ¿Qué valor de semilla no es recomendado ya que proporciona números aleatorios inadecuados? –

0

( 5.2 ) Al utilizar un generador de congruencia lineal, si volvemos a utilizar la misma semilla en diferentes instancias, ¿qué sucede? –

Genera siempre los mismos números aleatorios

( 5.2 ) ¿Qué caracteristicas deben cumplir los números generados uniformemente distribuidos en el intervalo [0,1]? Seleccione las 4 (cuatro) respuestas correctas NO VA: Su medida debe ser estadísticamente igual a 1 – Su medida debe ser estadisticamente igual a 1/2. – Su varianza debe ser estadisticamente igual a 1/12. – Estadisticamente independientes – Uniformemente distribuidos

( 5.2 ) ¿Cuáles son errores comunes a la hora de trabajar con generadores de números aleatorios? Seleccione las 3 (tres) respuestas correctas NO VAN: No manipular el generador de números aleatorios para mejorar sus propiedades estadisticas // – El uso de una semilla igual a cero – Reinicializar la semilla antes de generar una permutación aleatoria – Utilizar los bits de “menor peso” de los generadores de congruencia lineal ( 5.2 ) ¿Qué necesita un generador de números pseudo aleatorios para funcionar? –

Semilla

( 5.2 ) Los GENERADORES DE NUMEROS ALEATORIOS producen: –

Números pseudoaleatorios

( 5.2 ) ¿Cómo podemos conseguir números aleatorios en una computadora? –

La verdadera aleatoridad es imposible de conseguir en una computadora, si bien Von Neumann creyo que esto era correcto, corroboro que la secuencia...

( 5.2 ) Una prueba de primalidad (o test verdadero de primalidad), verifica: –

Número Primo

( 5.3 ) La DISTRIBUCION EXPONENCIAL se caracteriza por: –

Coincidir la media y la varianza

( 5.3 ) En un algoritmo aleatorizado el peor caso se da: –

No por malos datos de entrada, si no por inadecuados números aleatorios

( 5.3 ) La distribución exponencial negativa tiene la misma media y varianza –

Verdadero

( 5.4 ) Si LOBO luego de una operación queda OBOL y BOLO ; ¿ante qué clase de permutación estamos? ( 5.4 ) Si BUDA luego de una operación queda UDAB y DABU; ¿ante qué clase de permutación estamos? ( 5.4 ) Si CASA luego de una operación queda ASAC y SACA ¿ante qué clase de permutación estamos? –

Permutación cíclica

( 5.4 ) Dado el conjunto {1,2,3,4}, ¿Cuántas permutaciones son posibles? –

24

( 5.4 ) Dado el conjunto A={10,20,30}, ¿Cuántas permutaciones son posibles? –

6

( 5.4 ) Indique las permutaciones válidas para el conjunto {a,b,c} –

“a,b,c”, “a,c,b”, “b,a,c”, “b,c,a”, “c,a,b”, “c,b,a”

( 5.4 ) Indique las permutaciones validas para el conjunto (1,2,3) –

“1,2,3”, “1,3,2”, “2,1,3”, “2,3,1”, “3,1,2”, “3,2,1”

( 5.4 ) ¿Qué es una permutación de 1,2, …, N? –

Una secuencia de N enteros que incluye a cada uno de los valores exactamente una vez

( 5.4 ) Una PERMUTACION ALEATORIA debe ser: –

Equiprobable

( 5.4 ) ¿Cuántos números de 5 cifras diferentes podemos formar con los digitos 1,2,3,4,5? –

120

( 5.4 ) Si dispongo de un conjunto dado de 3 elementos, ¿Cuántas permutaciones son posibles? –

6

( 5.4 ) La aleatoridad de la permutación esta limitada por: –

La aleatoridad de una permutación esta relacionada directamente a la aleatoridad del generador de números pseudoaleatorios.

( 5.4 ) ¿De que depende el grado de aleatoriedad en la generación de permutaciones aleatorias? –

De la calidad de los números aleatorios arrojados por el generador que usemos

( 5.5 ) ¿Cuál es la principal limitación de los generadores de congruencia lineal? –

Los valores se repiten

( 5.5 ) ¿De qué depende el tiempo de ejecución de un algoritmo aleatorizado? –

De su entrada y de los números aleatorios presentados

( 5.5 ) ¿De qué depende el tiempo de ejecución de un algoritmo aleatorizado además de la entrada en sí? –

De los números aleatorios presentados

( 5.5) ¿Cómo se conocen a los errores cometidos aleatoriamente por algunos algoritmos aleatorizados que funcionan en una cantidad fija de tiempo? –

Falsos positivos/negativos

( 5.5 ) ¿Cómo se conocen a los algoritmos que de alguna manera tienen incorporada a su lógica el uso de números aleatorios? –

Aleatorizados

( 5.5 ) ¿Cuál es la principal limitación de los generadores de congruencia lineal? –

Los valores se repiten

(5.6 ) Los errores cometidos aleatoriamente (con baja probabilidad) por algunos algoritmos aleatorios de duración fija, lo conocemos como: –

Falsos positivos, falsos negtivos

( 5.6 ) ¿Hasta qué tamaño de números puede utilizarse el algoritmo de división de manera rápida para comprobar la primalidad? –

32 bits

( 5.6 ) ¿Qué es un test de pseudoprimalidad? –

Es un criterio, para decir con un alto grado de probabilidad, si un número dado es o no primo

( 5.6 ) Un test de primalidad es un algoritmo que, dado un número de entrada n, no consigue verificar la hipótesis de un teorema cuya conclusión es que n es compuesto –

Verdadero

( 5.6 ) En un test de primalidad basado en divisiones sucesivas ¿desde que valor comenzamos utilizando como divisor m para un número n a probar? –

Desde 3 hasta el entero más cercano de la raíz de n

( 5.6 ) En un test de primalidad basado en divisiones sucesivas ¿hasta qué valor debe ir m (divisor) para un número n dado a probar? – ( 5.6 ) Seleccione 2 (dos) sentencias correctas respecto a los números primos: – –

El número 1 no es primo Se dividen únicamente por 1 y por ellos mismos.

( 5.6 ) Para que se suele utilizar el teorema de Fermat?

–

Para determinar primalidad

( 5.6 ) ¿Cuál es el enunciado del pequeño teorema de Fermat? –

Si P es primo y 0< A< P, entonces A^ (P-1) 1≡ 1 (mod P)

( 5.6 ) ¿Qué es un testigo de composición? –

Un valor de A que demuestra que un número no es primo utilizando el pequeño Teoremat de Fernat

( 5.6 ) ¿Para qué sirve el “algoritmo de división”? –

Para comprobación de primalidad

( 5.6 ) El TEST DE DIVISIBILIDAD tiene un buen rendimiento para: –

Números pequeños

( 5.6 ) El METODO DE MONTE CARLO es aplicable a: –

Problemas deterministicos y estocasticos

¿Qué significa la siguiente relación? a ≡ b (mod n) –

Define una relación de congruencia

Dada la estructura: {100, 65, 40, 10} ¿Cuántas inversiones son necesarias para ordenar completamente los elementos? –

5

En general, para todo algoritmo recursivo podemos encontrar un algoritmo iterativo equivalente que resuelve el mismo problema sin tener que auto invocarse –

Verdadero

En ordenamiento rápido: ¿Cómo conocemos al elemento que divide a los elementos de una matriz entre los que son más a él y más pequeños? –

Pivote

La suma de dos números aleatorios consecutivos uniformemente distribuidos tiene la misma probabilidad de ser par o impar –

Verdadero

¿Cómo se conoce a un número X que cumple que, para cierto n, la “división de Fermat” da resto 1?

–

Testigo de Fermat

¿Cómo se llaman las ecuaciones que nos permiten indicar el tiempo de ejecución para los distintos casos del algoritmo recursivo? –

De recurrencia

¿De qué método es una versión mejorada el método de ordenamiento shell? –

Ordenamiento por inserción

¿Qué es un test de primalidad? –

Criterio para decidir si un número dado es o no primo.

¿Qué sucede si para un generador congruencial lineal elegimos como módulo (m) un valor igual a 7? –

Los números generados iran de 0 a 6

¿Qué sucede si para un generador congruencial lineal elegimos como módulo (m) un valor igual a 11? –

Los números generados irán de 0 a 10.

< > ^ [ ]

{ } ≡...