Taller de algoritmos y estructuras de datos II Parcial 2

Se realiza la simulación de una implementación de la solución del problema de Josephus. Considerando N=5 y M=2, donde N representa el número de participantes y M el número de pasadas, ¿quién gana el juego, suponiendo que comienza el jugador 1?. El jugador de la posición 4. El jugador de la posición 3. El jugador de la posición 2.

¿Qué sucede cuando se aplica el algoritmo de Huffman a un conjunto de caracteres?. La salida obtenida es el mismo conjunto de símbolos de entrada codificados con un código binario de menor tamaño. El algoritmo genera un código de longitud fija para cada carácter del conjunto de entrada. La salida es un árbol AVL que permite la búsqueda de caracteres en tiempo O(log N).

Los algoritmos de compresión con pérdida permiten una reducción menor del tamaño del archivo a comprimir. Falso. Verdadero.

¿Qué se entiende por simulación?. La simulación es una técnica que, mediante el uso de computadoras, permite realizar experimentos a través de los cuales se pueden describir comportamientos de sistemas o procesos del mundo real. La simulación es un algoritmo matemático que garantiza encontrar el resultado óptimo en un conjunto de datos, sin tener en cuenta la variación aleatoria. La simulación es la representación física a escala real de un proceso complejo para eliminar la necesidad de un modelo computacional.

En el algoritmo de Huffman, ¿cuántas veces se seleccionan dos árboles para ser unidos? Selecciona la opción correcta. C−1, siendo C el número de caracteres. C, siendo C el número de caracteres. N+1, siendo N el número total de nodos en el árbol final.

Señala la opción correcta. Al invocar el código mostrado en la imagen dentro de un ciclo se puede generar una secuencia de números entre 1 y 10. Números enteros entre 1 y 10. Números de coma flotante entre 0 y 1. Números enteros entre 0 y 9.

En un bosque de árboles, ¿qué sucede si se tienen dos nodos con el mismo peso?. Si tienen el mismo peso, es indistinto qué árbol seleccionar. En el ejemplo, en la segunda combinación, se puede elegir tanto el árbol S como el árbol 1. Se debe seleccionar el nodo cuyo valor alfabético sea menor. En el ejemplo, si S e I tuvieran ambos peso 12, siempre se debería elegir el nodo I para la combinación por ser la letra que aparece primero en el alfabeto. La construcción del árbol se detiene porque el algoritmo no puede desempatar la selección. Se requiere cambiar los pesos de uno de los nodos para continuar, o el algoritmo falla.

Teniendo en cuenta que N representa el número de personas y M el número de pases, ¿qué sucede en una implementación de una simulación por computadora del problema de Josephus que utiliza listas enlazadas cuando el valor del parámetro M es 0?. Para M=0, el tiempo de ejecución es O(N). El resultado final siempre será el primer elemento de la lista (el número 1) porque nadie avanza, y el tiempo de ejecución es O(1), ya que no se realiza ningún cálculo. El algoritmo entra en un bucle infinito porque el bucle interno (for) solo se ejecuta una vez por cada persona eliminada, pero la condición de eliminación nunca se cumple o la lista nunca disminuye de tamaño.

Se tiene un generador de congruencia lineal de periodo completo. Si se consideran A y M constantes y X0 la semilla que satisface 1<=X10. M-1. La condición es X_0 debe ser un número primo. La condición es 0 ≤ X_0 ≤M.

¿A través de qué estructura de datos se representa el código binario obtenido en un proceso de compresión?. Árbol binario. Arreglo (o array). Tabla Hash.

¿Es posible conseguir la verdadera aleatoriedad?. La verdadera aleatoriedad es imposible de conseguir en una computadora, porque cualquier número obtenido dependerá del algoritmo empleado para generarlo y, por tanto, no puede llegar a ser verdaderamente aleatorio. Sí, es posible. La verdadera aleatoriedad se consigue simplemente utilizando la hora y la fecha actual del sistema como semilla, ya que este valor cambia constantemente y garantiza una distribución uniforme de los números generados. La verdadera aleatoriedad es fácilmente alcanzable en una computadora siempre que se utilice un algoritmo de cifrado fuerte (como AES o RSA) para generar los números. Estos algoritmos garantizan que el resultado sea impredecible.

Dado el siguiente árbol de Huffman, ¿cuál es la longitud de código de los caracteres sp, i, a?. Longitud i=2, longitud sp =2, longitud a=3. Longitud i=4, longitud sp =4, longitud a=5. Longitud i=1, longitud sp =1, longitud a=1.

Se realiza la simulación de una implementación de la solución del problema de Josephus. Considerando N=6N y M=2, donde N representa el número de participantes y M el número de pasadas, ¿quién gana el juego, suponiendo que comienza el jugador 1?. El jugador de la posición 1. El jugador de la posición 3. El jugador de la posición 6.

Al utilizar la clase Random para la generación de números aleatorios, si se instancia la clase varias veces con la misma semilla, ¿siempre se obtiene la misma secuencia de números aleatorios?. Verdadero. Falso.

Una de las propiedades más importantes que deben cumplir los números aleatorios es la de tener una distribución uniforme. ¿Cómo se puede comprobar si una secuencia de números generados cumple con esta propiedad?. Creando una secuencia de números aleatorios lo suficientemente grande y contando la cantidad de veces que aparece cada uno de los números generados. Se debe calcular el coeficiente de correlación entre los números consecutivos de la secuencia. Si el coeficiente está cerca de cero, la secuencia cumple con la propiedad de distribución uniforme. Se debe comparar cada número generado con la semilla inicial (X_0). Si la mayoría de los números son diferentes a la semilla, entonces la secuencia tiene una distribución uniforme.

En el problema de Josephus, ¿cómo se puede garantizar que las operaciones de eliminación (remove), es decir, aquellas que implican eliminación de un jugador, sean logarítmicas? Considerando O(NlogN). Construyendo un árbol de búsqueda binaria mediante inserciones recursivas. Utilizando una lista enlazada doblemente enlazada (doubly linked list) y manteniendo un puntero al último nodo eliminado, lo que permite que el acceso y la eliminación sean de tiempo constante O(1). Esto resulta en un tiempo total de O(N). Empleando una tabla hash donde cada jugador se mapea a su posición actual en el círculo, lo que permite la eliminación en tiempo constante promedio O(1) y asegura un tiempo total de O(N).

En los trabajos de simulación, es común utilizar números pseudoaleatorios para llevar a cabo los procesos de simulación. ¿En qué consisten los números pseudoaleatorios?. Son números que parecen ser aleatorios porque satisfacen muchas de las propiedades de los números aleatorios. Son números generados a partir de fenómenos físicos no deterministas (como el ruido atmosférico o la desintegración radiactiva) que garantizan una verdadera impredecibilidad en cada número generado. Son secuencias de números que, por diseño, nunca se repiten y que siempre tienen un período infinitamente largo, independientemente del algoritmo o la semilla utilizada.

El lenguaje Java brinda en su paquete java.util la clase Random. Para hacer uso de la clase, es necesario instanciarla para crear un objeto que será utilizado en el programa. Este objeto creado, ¿qué permite generar?. Una secuencia de números pseudoaleatorios. El objeto Random permite generar una secuencia de Números Aleatorios Verdaderos (NAV), ya que utiliza fuentes de entropía del sistema operativo para garantizar la impredecibilidad. Permite generar una secuencia de números con una distribución exponencial, lo que es útil para simular tiempos de espera y fallas de sistemas.

Se trabaja en un proyecto de elaboración de software. El método creado por uno de los programadores para generar números aleatorios es el que se muestra en la figura S. El método se ejecuta en distintos momentos. ¿Qué secuencias se generan?. Al utilizar un constructor sin parámetros, en general retornará secuencias diferentes para cada ejecución que se realice. La misma secuencia de 10 números en cada ejecución del método, independientemente del momento en que se ejecute. Esto se debe a que el constructor sin parámetros (new Random()) utiliza un valor fijo como semilla predeterminada. Números Aleatorios Verdaderos (NAV) porque la inicialización del objeto Random sin parámetros obliga al sistema a usar la entropía física para obtener una fuente de aleatoriedad.

Se realiza la simulación de una implementación de la solución del problema de Josephus. Considerando N=6 y M=1, donde N representa el número de participantes y M el número de pasadas, ¿quién gana el juego, suponiendo que comienza el jugador 3?. El jugador de la posición 1. El jugador de la posición 4. El jugador de la posición 2.

¿A través de qué estructura de datos se representa el código binario obtenido en un proceso de compresión?. Árbol binario. Listas enlazadas. Colas.

¿En qué consiste el proceso de compresión sin pérdida?. En sustituir la información que se repite por un conjunto de instrucciones que pueden ser interpretadas posteriormente para determinar cuántas veces los datos idénticos entre sí se repiten. Consiste en eliminar la información redundante y menos relevante para el ojo o el oído humano (datos que no son fácilmente perceptibles), lo que permite reducir el tamaño del archivo, aunque se pierde parte de la calidad original. Se basa en la creación de un árbol de búsqueda binaria con los datos del archivo. El proceso recorre el árbol para identificar y descartar los nodos que no son accedidos con frecuencia, basándose en una probabilidad predefinida.

En un proceso de compresión sin pérdida, basado en repeticiones, ¿siempre es posible lograr una cantidad óptima de compresión?. No siempre es posible realizar la compresión de archivos, porque si en un archivo no existen repeticiones, no es posible realizar la compresión por evaluación de repeticiones. Sí, siempre es posible lograr una compresión óptima. Si no se encuentran repeticiones, el algoritmo automáticamente cambia a un método de codificación entrópica (como Huffman) para asegurar una reducción mínima de 10% en el tamaño del archivo. Sí, siempre se puede lograr una compresión óptima porque, si no hay repeticiones, el algoritmo reorganiza los bytes del archivo en un nuevo orden que se considera más compacto, haciendo que el archivo resultante sea siempre más pequeño.

Los algoritmos de compresión con pérdida permiten una reducción menor del tamaño del archivo a comprimir. Falso. Verdadero.

Durante el desarrollo de un software de sistema de mensajería, se desarrolla un módulo de envío de mensajes de audio en formato de tipo MP3 ¿Qué estrategia debes utilizar para optimizar el envío de los audios?. Un proceso de compresión con pérdida, donde se eliminan frecuencias que se encuentran fuera del rango que el oído humano puede oír, además de la información que contiene la música del archivo, con el objetivo de alcanzar un nivel de compresión adecuado de modo tal que la música contenida en el archivo sea de calidad sin ocupar tanto espacio. Utilizar un proceso de compresión sin pérdida (como ZIP o LZW). Esta estrategia garantiza la integridad perfecta del archivo original, asegurando que la calidad del audio se mantenga al máximo nivel, y es el único método aceptable para la transmisión de archivos de audio. Se debe utilizar un algoritmo de cifrado de clave pública (como RSA) para codificar los bytes del audio. El cifrado automáticamente reduce el tamaño del archivo a la mitad y garantiza que el audio se transmita de forma segura.

Cualquier codificación empleada para disminuir el conjunto de bits de representación de un conjunto de símbolos puede ser decodificada de forma no ambigua. Falso. Verdadero.

En el proceso de construcción de un software, se debe crear una codificación para representar un conjunto de caracteres. Suponiendo que la cantidad de caracteres es C, ¿Cómo se puede calcular la cantidad de bits necesarios para su representación?. Para un conjunto de caracteres de tamaño C, se necesitan [log C] bits si se utiliza una codificación estándar de longitud fija. La cantidad de bits necesarios es igual a la frecuencia de aparición del carácter más común, ya que la codificación debe ser óptima y priorizar la compresión. Para calcular la cantidad de bits, se debe multiplicar el número total de caracteres $C$ por la tasa de muestreo utilizada por el sistema, lo que da como resultado el espacio de almacenamiento total.

Se tiene la siguiente tabla de caracteres con sus correspondientes códigos de representación de longitud variable. ¿Cuál es el total de bits para la secuencia completa de caracteres?. La secuencia completa requiere 146 bits. El total de bits es 48 bits. La secuencia completa requiere 58 bits.

Dada la siguiente tabla de caracteres con sus correspondientes códigos, ¿es posible realizar una decodificación no ambigua?. Con esta codificación, al realizar el proceso de decodificación, se puede obtener la cadena original porque cumple la regla del prefijo. No, la decodificación es siempre ambigua porque se utilizan códigos de diferente longitud (1, 2 y 3 bits). Para evitar ambigüedades, todos los códigos deben tener la misma longitud. No, no es posible realizar una decodificación no ambigua. La regla de sufijo establece que ningún código puede ser un sufijo de otro código, y en esta tabla, el código para X (10) es el sufijo del código para Y (110), lo que provoca ambigüedad.

¿Cómo funciona el algoritmo de Huffman?. El algoritmo de Huffman construye un código prefijo óptimo. Funciona combinando repetidamente los dos árboles de menor peso. El algoritmo funciona asignando códigos de longitud fija a cada carácter. Calcula la longitud de código necesaria para representar el carácter con mayor frecuencia y utiliza esa misma longitud para codificar todos los demás caracteres del conjunto. El algoritmo de Huffman opera ordenando los caracteres alfabéticamente. Luego, asigna el código "0" al primer carácter de la lista, el código "1" al segundo, el código "00" al tercero, y así sucesivamente, sin necesidad de calcular las frecuencias.

El algoritmo de Huffman es un algoritmo que puede ser implementado mediante la combinación de distintas estructuras de datos. ¿Cuáles son las estructuras principales utilizadas para la implementación? Seleccione las (2) dos opciones correctas: Cola de prioridad. Estructura Map. Árboles B. Pilas.

En el algoritmo de Huffman, ¿Cuántas veces se seleccionan dos árboles para ser unidos?. C-1, siendo C el número de caracteres. C veces, ya que cada carácter inicial debe ser unido al menos una vez para formar el código final. 2C veces, porque en cada paso se deben seleccionar dos nodos y, además, se debe seleccionar el nodo resultante, duplicando el número de caracteres.

El lenguaje JAVA brinda, en su paquete java.util, la clase Random. Para hacer uso de la clase, es necesario instanciarla para crear un objeto que será utilizado en el programa. Este objeto creado ¿Qué permite generar?. Una secuencia de números pseudoaleatorios. Una secuencia de Números Aleatorios Verdaderos (NAV), ya que utiliza fuentes de entropía del sistema operativo para garantizar una verdadera impredecibilidad. Una secuencia de números con una distribución exclusiva de Poisson, útil para simular eventos que ocurren a una tasa constante en el tiempo.

La clase Random posee un constructor que al momento de instanciar la clase se le puede o no especificar un parámetro de entrada. ¿Qué permite especificar el parámetro del constructor?. El parámetro permite indicar la semilla de generación, la cual define la secuencia de números aleatorios. El parámetro permite especificar el rango máximo del valor que puede tomar el número aleatorio generado. Por ejemplo, si se especifica 100, el método nextInt() solo generará números entre 0 y 100. El parámetro indica la distribución de probabilidad que debe seguir la secuencia de números, permitiendo elegir entre distribuciones como la normal, la exponencial o la uniforme.

En el problema de Josephus, ¿Cómo se puede garantizar que las operaciones remove, es decir, aquellas que implican eliminación de un jugador, sean logarítmicas? Considerando O(Nlog⁡N)O(N \log N)O(NlogN). Construyendo un árbol de búsqueda binaria mediante inserciones recursivas. Utilizando un arreglo estático y marcando como eliminados a los jugadores. La eliminación se logra en O(1) porque solo se cambia el estado de una celda del arreglo. El tiempo total es entonces O(N). Empleando una lista enlazada circular y reiniciando el puntero de búsqueda al inicio de la lista después de cada eliminación para asegurar que el avance de M pasos siempre se haga sobre una lista de tamaño reducido N. Esto mantiene la eliminación en O(1).

¿Cómo garantizamos que las operaciones remove (Que elimina un jugador en el problema de Josephus) sean logarítmicas? O (N log N). Construyendo un árbol de búsqueda binaria mediante inserciones recursivas. Utilizando una tabla hash con la posición del jugador como clave, lo que garantiza la búsqueda y eliminación en un tiempo constante promedio O(1). Esto resulta en un tiempo total de O(N). Empleando una lista enlazada doblemente circular donde, después de cada eliminación, se utiliza la última posición eliminada como semilla para comenzar el conteo de M pasos. Esto asegura que solo se recorran M nodos, logrando un tiempo O(M) por eliminación.

¿Cómo logra su objetivo el algoritmo de Huffman?. Combinando árboles de menor peso. Dividiendo recursivamente el conjunto de caracteres en dos mitades, buscando equilibrar la cantidad de caracteres en cada lado del árbol hasta que cada nodo contenga solo un carácter. Asigna códigos incrementales a los caracteres ordenados alfabéticamente (por ejemplo, 0, 1, 10, 11, 100, etc.). Luego, elimina los códigos que son prefijos de otros para eliminar la ambigüedad.

¿Cómo se denomina a la longitud de una secuencia hasta que se repite un número? Seleccione la respuesta correcta. Período. Frecuencia. Semilla.

¿Cómo se denomina al valor inicial de un generador de números aleatorios?. Semilla. Módulo. Periodo.

¿Con cuál de las siguientes funciones podemos generar números aleatorios? Seleccione las 4 (cuatro) opciones correctas. random.nextInt();. random.Double();. random.nextLong();. random.Float();. random.nextString(int length);.

Conceptos de Simulación. Seleccione las 3 (tres) opciones correctas. Algoritmo de Josefo. Simulación dirigida por procesos. Tic. Tablas Hash. Colisiones.

¿Cuál de los siguientes códigos es correcto para el método constructor de la clase HuffmanTree si se le pasa como parámetro el objeto CharCounter?. No encontre imagen del enunciado, pero esta imagen es la respuesta correcta. ..........

¿Cuál sería la codificación del siguiente árbol de Huffman?. Carácter, Código A,1 B,010 C,011 D,000 E,001. Carácter, Código A,0 B,101 C,100 D,111 E,110. Carácter,Código A,1 B,010 C,110 D,000 E,100.

¿Cuáles de las siguientes clases intervienen en la implementación del algoritmo de Huffman? Selección 4 (cuatro) opciones correctas. BitlnputStream. BitOutputStream. HuffmanTree. CharCounter. HuffmanNode.

¿Cuáles de los siguientes conceptos se refieren a la distribución de Poisson? Seleccione las 4 (cuatro) opciones correctas. Modela la ocurrencia de sucesos ocasionales. Se emplea en simulación. Representa distribuciones no uniformes. El número de sucesos en una región de cierto tamaño es conocido. Se utiliza para modelar el tiempo transcurrido entre dos sucesos consecutivos.

¿Cuáles de los siguientes es una forma de representar a los jugadores en la implementación del problema de Josephus con un algoritmo simple?. Mediante una lista enlazada. Mediante una Tabla Hash. Mediante un Árbol de Búsqueda Binaria Balanceado.

¿Cuáles de los siguientes son usos importantes de los números aleatorios.? Seleccione 4 (cuatro) opciones correctas. Rendimiento de algoritmos. Simulación. Criptografía. Prueba de programas. Optimización de hardware y diseño de circuitos lógicos.

¿Cuántos bits necesitamos para poder representar todos los caracteres ASCII en una codificación de longitud fija?. 8 bits. 16 bits. 32 bits.

Dada la siguiente tabla de códigos para caracteres, ¿Cuál es el árbol que la representa?. La imagen añadida es el árbol que representa (la respuesta correcta). ........

Dado el siguiente árbol, ¿Cuál es el código para la palabra FAL?. 1101001. 10011011. 01110001.

Dado el siguiente árbol, ¿Cuál es el código para la palabra MAP?. No se puede resolver ya que el árbol no cumple con la condición de código de prefijo. El código para la palabra MAP es 0010111. Sí se puede resolver, ya que el árbol cumple la regla de la misma longitud. Todos los códigos tienen 3 bits, lo que elimina la ambigüedad en la decodificación.

Dado el siguiente árbol, ¿Cuál es el código para la palabra MAP?. No se puede resolver ya que el árbol no cumple con la condición de código de prefijo. El código para la palabra MAP es 010111. Sí se puede resolver. El árbol cumple la regla de la longitud variable óptima y el código de cada letra es simplemente la longitud del camino desde la raíz, lo que elimina la ambigüedad.

Dado el siguiente árbol, ¿Cuál es el código para la palabra SLAG?. 0001101110. 1111101000. 00000101.

El Algoritmo de división es el más simple para comprobar la primalidad, ¿Con qué tamaño de números es recomendable?. Seleccione la opción correcta. <= 32Bits. => 512 bits. Para cualquier tamaño de número, siempre que se utilice un lenguaje de programación de alto rendimiento como C++.

El algoritmo de Huffman es: Un algoritmo para construir un árbol de codificación. Un algoritmo de cifrado de clave pública utilizado para proteger la confidencialidad de los datos durante la transmisión. Un algoritmo de ordenamiento que utiliza una estrategia de dividir y conquistar (divide and conquer) para organizar los elementos de una lista de manera eficiente.

El algoritmo de Shannon-Fano: En el que se construye un código sin prefijo basado en un conjunto de símbolos y sus probabilidades. Es un algoritmo de codificación que utiliza la estrategia bottom-up (de abajo hacia arriba), combinando los dos símbolos de menor probabilidad en cada paso. El objetivo principal es lograr una compresión con pérdida, eliminando los símbolos de menor frecuencia para reducir significativamente el tamaño final del archivo.

El árbol de la siguiente figura no está completo ¿Qué podemos realizar para que lo esté?. Situando G más arriba reemplazando a su padre. Se debe añadir un tercer hijo a todos los nodos internos que actualmente solo tienen dos hijos, para crear un árbol ternario en lugar de uno binario. Añadir un nuevo nodo hoja, etiquetado como "Fin de Archivo (EOF)", a la rama izquierda del nodo que contiene a S.

El árbol de la siguiente figura no está completo ¿Qué podemos realizar para que lo esté?. Situando G más arriba reemplazando a su padre. Añadir un tercer hijo a todos los nodos internos que actualmente solo tienen dos hijos, convirtiéndolo en un árbol terciario. Eliminar los nodos internos y conectar directamente los caracteres a la raíz principal del árbol, ya que la codificación con prefijo funciona mejor cuando los códigos tienen la misma longitud.

El error más común en una simulación es... Seleccione la respuesta correcta. Utilizar un método inadecuado. Que la computadora se quede sin memoria RAM durante la ejecución, lo que provoca que la simulación se detenga antes de completarse. El uso de un Generador de Números Pseudoaleatorios (GNPA) que no satisface la propiedad de la distribución uniforme.

El generador de congruencia lineal es un buen algoritmo para generar ¿Qué tipo de distribución? Seleccione la respuesta correcta. Distribución Uniforme. Distribución Normal o Gaussiana. Distribución de Frecuencia Logarítmica.

El método getCode de HuffmanTree devuelve el código de un carácter determinado ¿Qué significa que retorne null?. Que el carácter no está representado. Que el carácter tiene el código binario "0" (un solo bit), y la función lo interpreta como nulo para indicar el código más corto posible. Que el árbol de Huffman tiene una distribución no uniforme de frecuencias, lo que causa un error en el cálculo del código.

El método getCode de HuffmanTree devuelve el código de un carácter determinado ¿Qué significa que retorne una matriz de longitud cero?. Que no se encuentra el código para el carácter. Que el carácter es el más frecuente de todos y, por lo tanto, se le asigna un código vacío para lograr la máxima compresión. Que el código binario del carácter es tan largo que la función no puede representarlo en un byte y, por seguridad, devuelve un arreglo vacío.

¿El siguiente árbol podemos considerarlo como árbol completo?. No, es un árbol completo porque no cumple con las condiciones de que todos sus nodos sean hojas ni que cada nodo tenga 2 hijos. Sí, es un árbol completo porque todos los nodos hoja están conectados a la misma raíz principal. Sí, es un árbol completo porque su altura es 4 y la cantidad de nodos es 8, cumpliendo la relación 2^h - 1 = N.

El siguiente código es la implantación del algoritmo de Josephus mediante una lista enlazada. ¿Este algoritmo funciona? [NOTA: Cuidado con el encabezado del método, que le falta un parámetro]. No, porque se debe pasar como parámetro el número de pases a realizar. Sí, el algoritmo funciona perfectamente porque el número de pases se puede deducir internamente a partir del parámetro people y el uso de un iterador circular. Sí, el algoritmo funciona, pero es muy ineficiente. El error principal está en el bucle while, que debería usar theList.size() > 1 en lugar de la variable people-- != 1.

El siguiente código es la implantación del algoritmo de Josephus mediante una lista enlazada. ¿Este algoritmo funciona? [NOTA: Aquí, la el encabezado del método tiene todos los parámetros]. Sí, el código está completo y bien desarrollado. No, el algoritmo no funciona porque la eliminación del nodo (itr.remove()) no hace que el iterador retroceda un paso, lo que provocaría que la siguiente iteración del bucle while saltee una persona. No, el algoritmo no funciona porque el tiempo de ejecución es de O(N^2) en el peor de los casos, y para que un algoritmo sea correcto, siempre debe tener una complejidad de O(N log N) o mejor.

El tiempo de ejecución de caso peor de un algoritmo aleatorizado es siempre el mismo que el tiempo de ejecución de caso peor de un algoritmo no aleatorizado. Verdadero. Falso.

El trie binario es una estructura de datos en la que la rama izquierda representa un 1 y la rama derecha representa un 0. El camino recorrido hasta un nodo indica su representación. Falso. Verdadero.

En comprensión de archivo, si los caracteres del árbol se encuentran en un nodo hoja, salvo uno. ¿Qué sucede?. No se puede garantizar que cada carácter se identifique de forma no ambigua. El árbol funciona perfectamente y es óptimo en cuanto a compresión, porque el único carácter en el nodo interno es automáticamente el código de longitud más corta ("0"). Se debe añadir un tercer hijo al nodo interno que contiene al carácter problemático, convirtiendo el árbol en un árbol terciario para restaurar la Propiedad de Prefijo.

En el algoritmo de Huffman ¿Cuántas veces se seleccionan dos árboles para ser unidos?. C-1, siendo C el número de caracteres. C veces, porque cada uno de los C caracteres debe participar en una unión para formar parte del árbol final. 2C veces, ya que en cada paso el algoritmo selecciona dos elementos de la cola de prioridad, duplicando el número total de selecciones.

En la clase Random de java.utils ¿Cuántas formas tenemos de generar números aleatorios?. 4. 1. 6.

En la implementación del algoritmo de Huffman ¿De qué se encarga la clase BitOutputStream?. Envuelve un OutputStream y permite la salida bit a bit. Se encarga de leer el archivo binario comprimido bit a bit y de reconstruir los caracteres originales a partir de la secuencia de bits. Se encarga de calcular la frecuencia de cada carácter en el archivo de entrada y de construir la Cola de Prioridad utilizada por el algoritmo.

¿En la implementación del problema de Josephus, si llegamos al final del arreglo y todavía no llegamos al valor de K, por donde se continua el recorrido?. Continuamos al principio del arreglo. El recorrido se detiene, y el jugador actual (en la posición final del arreglo) es el que se elimina automáticamente. Se debe duplicar el arreglo virtualmente, concatenando una copia de la lista existente para asegurar que el conteo de K pasos siempre permanezca dentro de los límites del nuevo arreglo doble.

En la práctica ¿De cuántas fases se compone la teoría de compresión de archivos?. 2 (dos). 4 (cuatro). 1 (uno).

En la práctica ¿De cuántas fases se compone la técnica de compresión de archivos?. 2 (dos). 4 (cuatro). 1 (uno).

En la rutina que crea el árbol de codificación de Huffman (create Tree) debemos mantener una lista de prioridad de nodos, ¿Qué debemos hacer para lograrlo?. Debemos hacer que HuffNode Implemente Comparable. Debemos hacer que HuffNode sea una clase de tipo static, para que los nodos puedan ser accedidos globalmente por la cola de prioridad. Debemos asegurarnos de que el peso del nodo sea un valor de tipo String, ya que solo los objetos String pueden ser ordenados en una cola de prioridad.

En simulación, la instrucción random.nextDouble(); es utilizada para: Generar un numero aleatorio de tipo doublé entre 0.0 u 1.0. Generar un número aleatorio que sigue la Distribución Normal (Gaussiana), la cual es útil para modelar errores o mediciones. Generar un número entero (tipo int) dentro del rango de valores definidos por el tamaño máximo del double.

En un árbol completo: Todos los nodos son hojas o tienen 2 hijos. Todos los nodos hoja se encuentran en el mismo nivel o profundidad. La altura del árbol es siempre igual al logaritmo en base 2 del número total de nodos.

En un código de longitud variable, ¿Cómo se representan los caracteres más comunes?. Con códigos de pequeña longitud. Con códigos de la misma longitud que los caracteres menos comunes, para garantizar la distribución uniforme de los bits. Con códigos de gran longitud (muchos bits), para asegurar que el código no sea un prefijo de ningún otro código.

En un generador de congruencia lineal completo. ¿Qué significa que un periodo sea completo? Recordemos que el generador de congruencia lineal es un generador de números aleatorios que satisfacen la siguiente ecuación. 𝑋𝑖+1 = 𝐴𝑋𝑖 (𝑚𝑜𝑑 𝑀). Que se genera todos los números entre 1 (uno) y M-1. Que el periodo es igual al Módulo (M), lo que garantiza que se generen todos los números posibles en el rango [0, M-1]. Que la secuencia de números generados es infinitamente larga y nunca se repite.

En un trie binario ¿Cómo obtenemos la representación de un carácter?. El camino seguido hasta el nodo. Es la frecuencia de aparición de dicho carácter dentro de la secuencia total de bits. Se obtiene mediante la concatenación de los códigos de todos sus nodos hermanos dentro del mismo nivel de profundidad.

En un trie binario ¿En dónde se ubican los caracteres?. En los nodos hoja. En los nodos internos del árbol. En una tabla hash auxiliar que se enlaza a la raíz del árbol.

En una distribución uniforme todos los números aleatorios dentro del rango especificado, tienen... Seleccione la respuesta correcta. ... la misma posibilidad de aparecer. ... una mayor posibilidad de aparecer cerca de los valores centrales del rango. ... una probabilidad de aparición que aumenta exponencialmente a medida que nos acercamos al valor máximo del rango.

¿Es posible comprobar la uniformidad de los números aleatorios?. Sí, generando una secuencia grande de números entre 0 y 9 y contando la frecuencia de cada uno. No, no es posible comprobar la uniformidad, ya que, por definición, los números pseudoaleatorios son impredecibles y cualquier prueba estadística es inútil. Sí, es posible. Se comprueba que cada número sea diferente al número generado inmediatamente anterior en la secuencia, lo que valida la uniformidad.

¿Es posible utilizar un generador de congruencia lineal de 32 bits?. Sí, utilizando una ecuación adecuada. No es posible, porque los números de 32 bits son demasiado pequeños y el periodo máximo que se puede alcanzar con ellos es inferior a 2^10. No, el generador de congruencia lineal solo puede utilizar aritmética de 64 bits o más para evitar el fallo de desbordamiento (overflow) en la multiplicación de la fórmula.

Hablando de compresión de archivos ¿Qué nos asegura un código prefijo?. Que no haya ambigüedades al decodificar un código. Asegura la máxima compresión posible para cualquier distribución de frecuencias en el archivo. Asegura que todos los caracteres en la secuencia tengan códigos de la misma longitud para facilitar la indexación.

Implementando el problema de Josephus, quien ganaría un juego de N=5 y M=1 Siendo N el número de participantes y M el número de pasadas. Comienza el juego el jugador en la posición 1. El jugador de la posición 3. El jugador de la posición 2. El jugador de la posición 4.

Implementando el problema de Josephus, quien ganaría un juego de N=5 y M=2 Siendo N el número de participantes y M el número de pasadas. Comienza el juego el jugador en la posición 1. El jugador de la posición 4. El jugador de la posición 5. El jugador de la posición 6.

Implementando el problema de Josephus, quien ganaría un juego de N=6 y M=2 Siendo N el número de participantes y M el número de pasadas. Comienza el juego el jugador en la posición 1. El jugador de la posición 1. El jugador de la posición 2. El jugador de la posición 6.

La clase para arboles de Huffman tiene 4 operaciones públicas. ¿Cuáles son? Seleccione 4 (cuatro) opciones correctas. GetCode. GetChar. WriteEncodingTable. ReadEncodingTable. CompressFile(File input, File output).

La distribución de Poisson se aplica generalmente ¿A qué tipo de sucesos? Seleccione la respuesta correcta. Que tienen una baja probabilidad. Que tienen una distribución uniforme. Que tienen una alta probabilidad de ocurrir.

La técnica general denominada Algoritmo Aleatorio, utiliza un número... Seleccione la opción correcta. Aleatorio. Un número Primo. Un número Entero de 64 bits con desbordamiento.

La verdadera aleatoriedad en una computadora es: Imposible de alcanzar. Es fácilmente alcanzable mediante el uso de un algoritmo matemático avanzado que utiliza una semilla basada en la hora actual del sistema. Es posible y se logra al ejecutar el generador de números aleatorios en un lenguaje de programación de bajo nivel (como Assembler), ya que permite la interacción directa con el hardware de la CPU.

Los 2 constructores random son: public random() y public random(long Parametro). public Random() y public Random(int parametro). public Random(double parametro) y public Random(String parametro).

¿Los BUENOS generadores de números aleatorios son...? Selecciona la opción correcta. Difícil de encontrar. Son fácil de encontrar. Son simplemente generadores de números primos.

Los generadores de congruencia Lineal son inadecuados para algunas aplicaciones. Verdadero. Falso.

¿Para qué se realiza la compresión de archivos? Seleccione las 2 (dos) opciones correctas. Para aumentar la capacidad del disco. Incrementar la tasa efectiva de transmisión a través de módems. Para cifrar y proteger el contenido del archivo, haciéndolo ilegible para cualquier usuario no autorizado. Para corregir errores en los datos de un archivo corrupto, rellenando los bits faltantes mediante la comparación con la copia original.

¿Para qué sirve la función setSeed de la clase random?. Cambiar la semilla de los números aleatorios. Permite establecer el periodo de la secuencia de números, garantizando que esta no se repita antes de la longitud especificada. Se utiliza para limitar el rango de los números generados, asegurando que solo se produzcan valores entre 0 y el valor de la semilla.

¿Para qué son útiles las rutinas writeEncodingTable y readEncodingTable?. Para leer (readEncodingTable) y escribir (writeEncodingTable) la tabla de codificación. Para crear el árbol de Huffman y calcular el código binario para cada carácter en función de sus frecuencias. Para leer el archivo original y escribir el archivo comprimido (bit a bit), realizando la compresión física de los datos.

Podemos crear un objeto HuffmanTree sin proporcionar un objeto CharCounter. Verdadero. Falso.

¿Qué árboles serían resultantes de aplicar el algoritmo de Huffman en el siguiente bosque? Se pide el resultado en la segunda combinación. Seleccione 3 (tres) opciones correctas. En la imagen esta la imagen del enunciado y las otras tres imágenes con márgenes azules las opciones correctas. ...............

¿Qué conceptos se utilizan para trabajar con números aleatorios? Seleccione las 4 (cuatro) opciones correctas. Algoritmo aleatorizado. Algoritmo de división. Distribución de Poisson. Distribución uniforme. Árbol de Búsqueda Binaria Balanceado.

¿Qué es la compresión?. La acción de reducir el número de bits que representan a un carácter. La acción de cifrar o proteger un archivo mediante un algoritmo de clave pública, haciendo que su contenido sea ilegible. La acción de dividir un archivo grande en múltiples archivos más pequeños para facilitar su almacenamiento y transmisión.

¿Qué estructura de datos debemos utilizar para obtener una búsqueda en O(log N) en el problema de Josephus?. Una estructura de árbol. Una Lista Enlazada Circular. Una Tabla Hash.

¿Qué función miembro de la clase random debemos utilizar si queremos simular una tirada de dado?. nextlnt(6)+1. nextDouble() * 6. nextLong(7).

¿Qué genera un objeto de la clase Random de java utils?. Una secuencia de números pseudoaleatorios. Una secuencia de Números Aleatorios Verdaderos (NAV), asegurando la impredecibilidad gracias a la entropía del hardware. Una secuencia de números que sigue la Distribución de Poisson por defecto, útil para modelar la ocurrencia de eventos en el tiempo.

¿Qué logra el algoritmo de Huffman?. Construir un código prefijo óptimo. Construir un árbol perfectamente balanceado. La eliminación de las frecuencias bajas de un archivo.

¿Qué métodos componen la clase BitlnputStream? Seleccione 4 (cuatro) opciones correctas. ReadBIt. Close. BitlnputStream. GetBit. Open.

¿Qué rango de valores devuelve la función random.nextLong()?. Enteros de 2^-64 y 2^64. Devuelve números de coma flotante (double) entre 0.0 y 1.0. Devuelve solo enteros positivos entre 0 y 2^64.

¿Qué sucede con la semilla si se invoca la clase random con el constructor sin parámetros. Random random = new Random();.?. La semilla se inicializa en base al tiempo actual. La semilla se inicializa con un valor fijo y constante. La semilla se inicializa con un valor de aleatoriedad verdadera.

¿Qué sucede si creamos objetos Random siempre con la misma semilla?. Siempre obtendremos la misma secuencia de números. Obtendremos una secuencia completamente aleatoria y diferente en cada ejecución. Se generará una secuencia de números que sigue la Distribución Normal.

¿Qué sucede si empleamos un árbol de búsqueda binaria en vez de una lista enlazada en la solución del problema de Josephus.?. Obtenemos un logaritmo más eficiente. El tiempo de ejecución empeora drásticamente. La simulación falla porque el árbol de búsqueda binaria no puede representar la naturaleza circular del problema de Josephus.

¿Qué sucede si en un bosque de árboles tenemos dos nodos con el mismo peso? Ej.: Si tienen el mismo peso, es indistinto que árbol seleccionar. En el ejemplo en la segunda combinación se puede elegir tanto S como I. Se debe seleccionar el nodo que se encuentre en la posición más a la izquierda dentro del bosque para garantizar la estabilidad del algoritmo. Se debe detener la construcción del árbol y solicitar al usuario que modifique el peso de uno de los nodos empatados, ya que el algoritmo no puede resolver la ambigüedad de la elección.

Según el algoritmo de Huffman, podemos decir que un árbol binario es una forma de representar el código prefijo que significa el proceso de descodificación, en este árbol los caracteres se almacenan en: Las hojas. Los nodos internos del árbol. Una Tabla Hash que se enlaza al árbol, con el código binario como la clave.

Según el siguiente árbol de Huffman, cual es la codificación del carácter "c". 1011. 0010. 1101.

Según el siguiente árbol de Huffman, ¿Cuál es símbolo con mayor ocurrencia?. a. c. r,b.

Según el siguiente árbol de Huffman, ¿Cuál es símbolo con menor probabilidad de ocurrencia?. !,c. a. r,b.

Si comparamos la codificación Huffman con la codificación binaria. Podemos decir que: En la codificación binaria, todos los posibles valores reciben códigos del mismo número de bits, mientras que en la codificación Huffman, cada valor tiene un numero diferente de bits: los códigos más frecuentes poseen menos bits. En la codificación Huffman se requiere que todos los códigos tengan la misma longitud para que se cumpla la Propiedad de Prefijo, mientras que la codificación binaria utiliza códigos de longitud variable. La codificación Huffman es más fácil de implementar y requiere menos memoria porque no necesita analizar previamente las frecuencias, mientras que la codificación binaria exige la construcción de un árbol.

Si consideremos A y M constantes y X0 la semilla que satisface 1 ≤ X0 < M. Un generador de congruencia lineal de período completo tiene un período de: M-1. M. M/2.

Teniendo un mismo bosque, ¿De qué depende el árbol generado con el método createTree de HuffmanTree?. De cómo se rompa los empates. Del orden alfabético de los caracteres iniciales. De la altura máxima deseada para el árbol.

Una codificación óptima cumple la propiedad de que el árbol mediante el cual se representa la codificación, debe ser completo. En caso de que el árbol no sea completo, ¿Qué solución podríamos implementar para este caso?. Los nodos que tienen un único hijo pueden subirse de nivel. Se debe eliminar la rama incompleta y redistribuir las frecuencias de los nodos restantes. Añadir un tercer hijo nulo a todos los nodos internos que actualmente solo tienen un hijo.