Dpto. Ing. de Sistemas y Automática. Universidad de ...jaar/Datos/IIC/Examenes.pdf · Informática. 1er curso Grado Ing. Civil. 26 de junio de 2013 APELLIDOS: NOMBRE: D.N.I.: Escriba

Dpto. Ing. de Sistemas y Automática. Universidad de Sevilla. Informática 1er curso Grado Ingeniería Civil. 26 de junio de 2013

APELLIDOS: NOMBRE: D.N.I.: Escriba las respuestas únicamente en los recuadros indicados. Utilice la parte de atrás como borrador. Puede emplear el lápiz. Compruebe que tiene todas las hojas. Entregue todas las hojas con su nombre, apellidos y DNI.

Tiempo de examen 3:00 Horas. Hoja 1/6

CUESTIÓN 1 (1 Punto) Resuelva la sopa de números al margen, completando los cálculos siguientes y rodeando el resultado en la tabla.

a) ____8 !10

2=1003

5 b) 100000

2 ! 40

16= ____

13 c) 2000

8 !100

2= ____

16 d) 2FA

16 + 20

3= ____

16 e) 1

10 KB = ____

16bits

CUESTIÓN 2 (1.5 Puntos) El señor Meyer desea convertir su vieja computadora CESIUS en una calculadora científica. Para ello conecta al registro E un procesador con capacidad para cálculos de funciones complejas como raíces, potencias, exponenciales, etc. A este tipo de dispositivo que complementa a la unidad de control (UC) se le denomina coprocesador matemático (CM). Para poder acceder a dichas funciones reprograma la UC del siguiente modo: • Las funciones del CM están dispuestas como el

alfabeto A, B, C, …, Z, de modo que si se desea acceder a la función correspondiente a la letra C el usuario introduce dicho carácter. El CM no trabaja con caracteres y por tanto el programa tiene que escribir en E el número 3 correspondiente a la tercera función. De forma automática el CM lo reconoce y selecciona la función 3.

• Para activar el cálculo en el CM, se reprograma la instrucción MOD de la UC, es decir MOD ya no ejecuta el resto de división entera, sino que se le indica al CM que ejecute el cálculo como MOD DIR, donde DIR es la dirección de memoria donde se encuentra el dato. El resultado lo devuelve a través del registro E.

Se pide que complete el programa en LS2 de la tabla al margen, que solicita un dato (X) al usuario y posteriormente una función a realizar (OP). El programa debe calcular el resultado y escribirlo en pantalla. Para ello suponga que el ciclo de instrucción del CM es mucho más rápido que el de la UC, de modo que el CM proporciona el resultado antes de que la UC ejecute la siguiente instrucción. NOTA: Códigos de caracteres ASCII en decimal ‘A’:65; ‘Z’:90.

2 1 1 4 3 E

7 4 F 4 B 0

0 2 A C F 8

4 5 2 0 0 0

1 0 0 9 F 0

D 3 1 1 0 4

E 0 … 0 0 0 0

Pseudo / Instrucción ORG 0 SAL INI

X: ESP 1 OP: ESP 1 A: CTE 65 ‘A Z: CTE 90 ‘Z

FUN: CTE 1 ‘Fun A CTE 2 ‘Fun B … … CTE 26 ‘Fun Z

DCF: DRE FUN PUN: ESP 1 AUX: ESP 1 INI:

A B C … Z

x xy ln(x) !!! ... !!! tan(x) COPROCESADOR MATEMÁTICO (ACME)

Dpto. Ing. de Sistemas y Automática. Universidad de Sevilla. Informática 1er curso Grado Ingeniería Civil. 26 de junio de 2013



CUESTIÓN 3 (2.5 Puntos) Para evaluar el rendimiento global de los alumnos que optan a ciertas becas se utiliza un criterio de decisión minimax o también denominado pesimista. Dicho criterio maximiza la mínima nota obtenida por el alumno, es decir selecciona la nota más alta entre todos los alumnos dentro de las más baja de cada alumno. Las notas están almacenadas en memoria en una matriz AMxN, con M alumnos y N materias. Supongamos que se tienen 3 alumnos y 5 materias de modo que la matriz sería

Matriz A Álgebra Cálculo Física Química Informática Alumno 1 6 8 7 9 9 Alumno 2 7 7 7 7 7 Alumno 3 10 9 5 10 10

El criterio seleccionaría primero las calificaciones más bajas de todos los alumnos, en este caso 6, 7, y 5, y posteriormente la calificación más alta entre ellas luego el 7, seleccionando al alumno 2. Como las notas de los alumnos se corresponden con los elementos aij de la matriz A, entonces el criterio se puede formular matemáticamente como

Se pide:

a) Realizar el diagrama de flujo de la función MinVec que recibe como argumentos un vector y su dimensión y devuelve un vector de dimensión dos, cuya primera componente es el valor más pequeño del vector que recibe y la segunda su posición dentro del vector.

b) Realizar el diagrama de flujo de la función MaxMin que recibe como argumentos la matriz A, y

sus dimensiones M y N, y devuelve el alumno que cumple el criterio minimax. Para resolver este apartado debe usar obligatoriamente la función del apartado a).

Lo únicos objetos que pueden utilizarse son los proporcionados en la tabla al margen. Nótese que todos los objetos de dicha tabla están almacenados en memoria. NOTA: Para hacer los diagramas de flujo utilice únicamente las operaciones +,-, ·, /, asignación escalar (←), comparaciones <, >, ≤, ≥, =, lógicas “y”, “o”, acceso a vectores y matrices con subíndices y expresiones literales en lenguaje natural. El diagrama de flujo ha de estar estructurado, ser claro y legible y ocupar sólo el espacio interior del recuadro.

NOMBRE DESCRIPCIÓN DEL OBJETO TIPO

A Matriz de notas Matriz de números positivos v Vector de dimensión N Vector de números positivos M Filas de A Constante entera N Columnas de A Constante entera i Índice Vble entera j Índice Vble entera k Índice Vble entera w Vector de dimensión 2 Vector de números positivos

max Cálculo parcial Vble aux Cálculo auxiliar Vble

MinVec Función MaxMin Función

imax

jmin ija{ }

Dpto. Ingeniería de Sistemas y Automática. Universidad de Sevilla Informática. 1er curso Grado Ing. Civil. 26 de junio de 2013

APELLIDOS: NOMBRE: D.N.I.: Escriba las respuestas en los recuadros indicados. Utilice la parte de atrás como borrador. Los resultados han de ir únicamente en los recuadros habilitados. Entregue todas las hojas con su nombre, apellidos y DNI. Puede usar lápiz.


a) b)

INICIO

FIN

INICIO

FIN




CUESTIÓN 4 (2.5 Puntos) CUESTIONES CORTAS a) Escriba el código necesario en MATLAB que permita invertir una cadena de texto almacenada en

cad. El resultado debe quedar almacenado en la misma cadena cad sin usar ninguna otra cadena auxiliar.

b) Escriba una función en MATLAB que permita generar la serie numérica: 1, -2, 3, -4, 5, -6, …. La

función no deberá recibir ningún parámetro formal y se diseñará de modo que cada nueva llamada a la misma devuelva un término de la sucesión, comenzando por 1.

c) Complete el siguiente código para, empleando el método de interpolación lineal, calcular el valor de

la función y(t) en tast, suponiendo conocidos los valores de ésta para los instantes de tiempo dados por el vector t. Si tast excede los límites de t, se mostrará mensaje de advertencia.

cad=input(‘Introduzca texto’,’s’); L=length(cad);

function [termino] = serie()

t=[0, 0.5, 1, 1.5, 2, 3, 4, 5]; y=[0, 1, 2, 3, 2, 1, 0, 0]; tast=input(‘Introduzca valor de t*: ’);




CUESTIÓN 5 (2.5 Puntos) Una administración de loterías desea realizar un programa informático para permitir a sus clientes comprobar si los billetes que han adquirido están o no premiados. Supondremos que un billete de lotería se compone de un número de 5 cifras (de 00000 a 99999) y una serie de 2 cifras (de 00 a 99). Por simplicidad, que los premios se calculan con el siguiente procedimiento: 1. Con independencia de la serie, si coindice la cifra de las unidades del número con la del billete

premiado, recibe 10€ de premio. Si coinciden unidades y decenas, 100 €. El premio se multiplica por 10 con cada cifra coincidente hasta un máximo de 100.000€ si coinciden las 5 cifras.

Importante: es necesario que coincidan todas las cifras consecutivamente a partir de las unidades. Por ejemplo, si el número premiado es 12345 y estamos comprobando los billetes b1=12355 y b2=44445, el billete b1 recibiría 10€ al coincidir las unidades, pero no las decenas (la coincidencia en centenas, millares, etc no se tiene en cuenta en este caso). El billete b2 recibiría 100€ de premio al coincidir unidades y decenas.

2. Los premios anteriores se duplican si además coincide la serie. Se pide: a) Realizar la función calcula_premio que recibe como argumentos el número y serie del billete

premiado y del billete del cliente que se quiere comprobar. La función devolverá la cuantía del premio que corresponda, o cero si el billete no tiene premio. NOTA: Puede crear funciones auxiliares si lo requiere.

function premio=calcula_premio(nro_premiado,serie_premiada,nro_cliente,serie_cliente)




b) Realizar la función listado_premios que, recibiendo el número y serie del billete premiado, calcule los premios que corresponden a los billetes de un conjunto de clientes. Los datos de los números de los clientes se encuentran en dos vectores vector_numeros y vector_series, de modo que vector_numeros(i) y vector_series(i) contiene respectivamente el número y serie jugado por el cliente número i.

Para cada cliente y sólo si el vector ha recibido premio, se mostrará por pantalla una frase del tipo:

NOTA: Use la función del apartado a) para resolver esta cuestión.

El número 33474, serie 23, ha recibido un premio de 100 Eur

function listado_premios(nro_premiado,serie_premiada,vector_numeros, vector_series)

Dpto. Ing. de Sistemas y Automática. Universidad de Sevilla. Informática 1º Ingeniería Civil. 11 de septiembre de 2012


Tiempo de examen 2.5 h Hoja 1/3

CUESTIÓN 1 (1 punto) Dibuje en el recuadro adjunto el cronograma de las señales R, S’ y Q, sabiendo que todas las puertas lógicas tardan en dar el dato en sus respectivas salidas un ciclo del reloj definido. Considere el nivel alto como el “1” lógico y el nivel bajo como el “0” lógico.

CUESTIÓN 2 (1.5 puntos)

a) Codifique el diagrama de flujo de la figura en el lenguaje LS2 para la computadora CESIUS. DATOS: “Carácter” / Código ASCII en decimal : “.” / 46; “a” / 97; “z” / 122.

b) ¿Cuál es la estructura de programación equivalente para el bucle en MATLAB ?

Pseudo / Instrucción

Pseudo / Instrucción

Inicio

Fin

¿c ’.’?

Leer c

S N

0 k

1 k k

S

N

Escribir k

¿ c es una

letra

minúscula?

S’

CLK

R

S’

Q




CUESTIÓN 3 (0.5 puntos) Su jefe lo considera un experto en computadoras y le exige bajar el tiempo de ejecución de uno de sus programas favoritos, el cual es de 25 segundos. Usted reescribe el código y reduce el número de instrucciones en un 25%. a) ¿Cuál es el nuevo tiempo de ejecución

del programa? Detalle el cálculo. b) Pero a su jefe no le parece suficiente aún y le exige más reducción.

Como no puede optimizar más el código, decide engañarlo duplicando la frecuencia del reloj. ¿Cuánto ha mejorado ahora?

CUESTIÓN 4 (3 puntos) Una mejora del método de Euler para el cálculo de integrales definidas es el método de los trapecios. En dicho método se aproxima el diferencial área por un trapecio en vez de por un rectángulo, como se muestra en la figura.

Realizar el diagrama de flujo de la función TRAPECIO, que reciba como argumentos los límites de integración a y b, y el paso de integración h. La función debe devolver la integral de una función genérica f(x). NOTA: Para hacer los diagramas de flujo utilice únicamente las operaciones +,-, ·, /, asignación

( ), comparaciones <, >, ≤, ≥, =, lógicas “y”, “o”, acceso a vectores y matrices con subíndices y expresiones literales en lenguaje natural. El diagrama de flujo ha de estar estructurado, ser claro y legible y ocupar sólo el espacio interior del recuadro.

NOMBRE TIPO DESCRIPCIÓN DEL

OBJETO

a Constante Límite inferior

b Constante Límite superior

h Constante Paso de integración

f(x) Función Devuelve el valor de f en x

INICIO

FIN

f(xk)

f(xk+1)

xk xk+1




CUESTIÓN 5 (4 puntos)

a) Se desea hacer un programa para calcular una aproximación de NB

log con N>1 y B>0 dados. Para ello y

utilizando obligatoriamente el método de la bisección sucesiva, codifique en MATLAB la función LogB, que

recibe como argumento el número N, la base B, y la precisión requerida h, y devuelve la aproximación de la

función NyB

log .

NOTA: No puede usar funciones propias de MATLAB.

b) Escriba en el recuadro adjunto los comandos necesarios en MATLAB para crear la gráfica de la función

NyB

log en función de 10>N>1, usando obligatoriamente la función del apartado anterior. Los valores

de los parámetros son: B=10 y h=0.001. NOTA: Puede usar funciones de MATLAB excepto la función log10().

function y = LogB (....................................)

>>

Dpto. Ing. de Sistemas y Automática. Universidad de Sevilla. Informática 1er curso Grado Ingeniería Civil. 1ª Conv. Ordinaria - 18 de junio de 2012

APELLIDOS: NOMBRE: D.N.I.: Escriba las respuestas únicamente en los recuadros indicados. Puede emplear el lápiz. Compruebe que tiene todas las hojas. Entregue todas las hojas con su nombre, apellidos y DNI. Examen solidario con el alumnado por el RDL 14/2012.

Tiempo de examen 2h Hoja 1/4

Q =

P =


a) Deduzca el valor de la base N en la siguiente identidad:

€

123 7 = 231N b) Deduzca a qué bases numéricas representan las variables X, Y y Z en las siguientes identidades, donde todos

los números son positivos.

€

10001X = 11Y = 21Z c) Calcule el resultado de la siguiente operación donde el número binario está codificado en complementos a 2.

€

100000 2 + 52 6 = ___________________ ______

d) Resuelva el siguiente sistema de ecuaciones para x e y, dando la solución en base decimal.

€

24 8 ⋅ x + 112 ⋅ y = E016

x − y = 210

e) Calcule el error relativo cometido al codificar el número 10.4 en punto fijo en

un registro de 1 byte y 4 posiciones fraccionarias.

f) Escriba en el recuadro adjunto la expresión de las funciones lógicas de Q y P en función de las variables de

entrada del circuito de la figura formado por puertas AND, NAND y NOR.

CUESTIÓN 2 (1 punto) El siguiente programa esta codificado en lenguaje LS2 para la computadora CESIUS. Escriba en el recuadro adjunto el número que sale por pantalla tras la ejecución completa del programa.

NOTAS: Códigos de Operación: CAR (0010), ALM (0001), RES (0110), MOD (1001), ESC (0011), SAL (1010), ALT (0000). MOD: resto de división entera entre el acumulador y la memoria, con el resultado en el acumulador.

Pseudo / Instrucción ORG 2 SAL INI DV: DRE NUM NUM: CTE -9 PUN: ESP 1 UNO: CTE 1 DOS: CTE 2 INI: CAR DV SUM UNO ALM I DOS RES NUM ALM PUN MOD DOS ESC I PUN ALT FIN

X = Y = Z =

N =

x = y =




CUESTIÓN 3 (1 punto) Para detectar posibles averías en una computadora CESIUS se carga en memoria el programa que aparece al margen derecho. Dicho programa ejecuta varias operaciones y el escribe el resultado final en la pantalla. Se pide, escribir en el recuadro de abajo: a) ¿qué escribe en la pantalla?; y b) ¿qué hay en la dirección 3 en decimal?

NOTA: Los códigos de operación ordenados de menor a mayor son: ALT, ALM, CAR, ESC, LEE, SUM, RES, MUL, DIV, MOD, SAL, SAN, SAC, SAP, ECA y LCA. CUESTIÓN 4 (2 puntos) Se desea simular en una computadora el juego de la vida. El juego consiste en simular la evolución de una colonia de células distribuidas aleatoriamente en una cuadrícula. Para ello dada la disposición en un tiempo T se calcula la evolución en un tiempo posterior T+1 siguiendo ciertas las reglas. Como ejemplo véase la cuadrícula de 10x10 casillas al margen donde se representa una situación en T. En ella se han distribuido aleatoriamente las células ⚇. La evolución en T+1 se calcularía según las reglas dando nuevas células que nacerán ☺ y otras que morirán ☹. Para hacer la simulación se considera que la cuadrícula está representada por una matriz cuadrada binaria M de dimensión N, donde cada elemento (i,j) es igual a uno si hay una célula y a cero en caso contrario. Los elementos de las filas y columnas de los extremos de la matriz son cero (véase el ejemplo al margen).

Se pide: Hacer el diagrama de flujo de una función denominada VECINAS, que reciba como argumentos la matriz M, su dimensión N y los índices i y j de un elemento de dicha matriz. La función debe devolver un entero n indicando el número de células vecinas que el elemento (i,j) tiene.

NOTA: Para hacer los diagramas de flujo utilice únicamente las operaciones +,-, ·, /, asignación (←), comparaciones <, >, ≤, ≥, =, lógicas “y”, “o”, acceso a vectores y matrices con subíndices y expresiones literales en lenguaje natural. El diagrama de flujo ha de estar estructurado, ser claro y legible y ocupar sólo el espacio interior del recuadro.

DIR Instrucción 0 1010 0 000 0000 0100 1 0100 0 000 0000 0000 2 0000 0 000 0000 0001 3 1111 1 111 1111 1111 4 0010 0 000 0000 0001 5 0111 0 000 0000 0011 6 0101 0 000 0000 0001 7 0001 1 000 0000 0010 8 0011 0 000 0000 0001 9 0000 0 000 0000 0000

⚇ ⚇

☺ ⚇ ⚇

⚇

☹ ⚇ ☺ ☹

☺

☺ ⚇ ⚇

⚇ ⚇ ⚇ ☺ ☹

☺ ⚇

NOMBRE TIPO DESCRIPCIÓN DEL OBJETO

M Matriz binaria Matriz de la colonia

N Constante Dimensión de la matriz M

i Constante Subíndice

j Constante Subíndice

n Matriz entera Número de vecinas

a) b)



Tiempo de examen 2h. Hoja 3/4

INICIO

FIN



Tiempo de examen 2h. Hoja 4/4


a) Se desea hacer un programa para calcular una aproximación de la

€

N de un número N>0 dado. Para ello y utilizando obligatoriamente el método de la bisección sucesiva, codifique en MATLAB la función Raiz2, que recibe como argumento el número N y la precisión requerida h, y devuelve la aproximación de la

€

N . NOTA: No puede usar funciones propias de MATLAB.

b) Escriba en el recuadro adjunto los comandos necesarios en MATLAB para crear la gráfica de la función

€

y = N en función de N>0, usando obligatoriamente la función del apartado anterior. Los valores de los parámetros son: N=0.5 y h=0.001. NOTA: Puede usar funciones de MATLAB excepto la función sqrt().

function .......... = Raiz2 (....................)

>>

Dpto. Ing. de Sistemas y Automática. Universidad de Sevilla. Informática 1º Ingeniería Civil. 13 de diciembre de 2011



CUESTIÓN 1 (3 Puntos) El siguiente programa esta codificado en lenguaje LS2 para la computadora CESIUS. Escriba en el recuadro adjunto el número, en decimal (no en binario), que sale por pantalla tras la ejecución completa del programa.

NOTAS: Códigos de Operación: CAR (0010), ALM (0001), RES (0110), MOD (1001), ESC (0011), SAL (1010), ALT (0000). MOD: resto de división entera entre el acumulador y la memoria, con el resultado en el acumulador. CUESTIÓN 2 (1 puntos) Dado el problema de valor inicial descrito por la ecuación diferencial siguiente

€

dx(t)dt

= a ⋅ x(t) + b ⋅ u(t), x(0) = x0, t ≥ 0,

donde son constantes y

€

u(t) es una variable que varía con el tiempo. La solución

€

x(t) desde el tiempo hasta el tiempo viene dada por la ecuación

€

x(t) = eat ⋅ x0 + e−aτ0

t

∫ b u(τ) dτ⎛

⎝ ⎜

⎞

⎠ ⎟

Se desea hacer un programa que calcule una aproximación de la solución

€

x(t) . Se pide aproximar dicha solución mediante una fórmula iterativa y escribir dicha fórmula en el recuadro adjunto. No puede integrar la ecuación y después aproximar, es obligatorio hacer la aproximación de la integral.

Pseudo / Instrucción ORG 1 SAL INI DV: DRE NUM NUM: CTE -9 PUN: ESP 1 DOS: CTE 2 UNO: CTE 1 INI: CAR DV SUM UNO ALM I DOS MOD UNO RES NUM ALM PUN ESC I PUN ALT FIN

€

a, b , x0

€

t = 0

€

t





a Constante Parámetro ecuación

b Constante Parámetro ecuación

T Constante Tiempo final

N Constante Número de puntos

p Constante Parámetro

t Vector de números

reales Vector de tiempos

x Vector de números

reales Vector solución

CUESTIÓN 3 (3 puntos) Se desea hacer un programa que calcule una aproximación de la fórmula dada en la cuestión anterior entre un intervalo de tiempo desde

€

t = 0 hasta

€

t = T . Para ello se pide realizar el diagrama de flujo de la función Xsol que reciba como argumentos

€

a, b, x0, el tiempo final

€

T , el número de puntos

€

N , y un parámetro

€

p definido más abajo. La función deberá devolver el vector de tiempos

€

t , el vector solución

€

x(t) y el vector de entrada

€

u(t) . El vector

€

u(τ) de la fórmula dada en la cuestión anterior debe construirse tal que

€

u(τ) = 0 para

€

τ < p⋅ T y

€

u(τ) =1 para

€

τ ≥ p⋅ T , con el parámetro

€

p tomando valores entre 0 y 1.

Además se dispone de la función Exp que recibe como argumento una variable escalar k y devuelve el valor

€

ek . Deberá utilizar obligatoriamente esta función en la resolución del diagrama de flujo.


INICIO

FIN




CUESTIÓN 4 (3 puntos) a) Codifique en MATLAB la función Xsol, desarrollada en el diagrama de flujo de la cuestión anterior. Para ello,

MATLAB dispone de la función exp(k)que devuelve la exponencial de una constante k, es decir

€

ek .

b) Escriba en el recuadro adjunto los comandos necesarios en MATLAB para crear una gráfica de la solución

€

x(t) (con línea continua) y de la entrada

€

u(t) (línea discontinua) frente al tiempo, usando obligatoriamente la función del apartado anterior. Los valores de los parámetros son: a=1, b=1, x0=0, T=10, N=1000 y p=1/4.

>>

function .......... = Xsol (................................)

Dpto. Ing. de Sistemas y Automática. Universidad de Sevilla. Informática 1er curso Grado Ingeniería Civil. 2ª Conv. Ordinaria - 5 de septiembre de 2011



CUESTIÓN 1 (1 Punto) El siguiente programa esta codificado en lenguaje LS2 para la computadora CESIUS. Escriba en el recuadro adjunto el número, en decimal (no en binario), que sale por pantalla tras la ejecución completa del programa.

NOTAS: Códigos de Operación: CAR (0010), ALM (0001), RES (0110), MOD (1001), ESC (0011), SAL (1010), ALT (0000). MOD: resto de división entera entre el acumulador y la memoria, con el resultado en el acumulador. CUESTIÓN 2 (1 punto) Un sistema de comunicaciones utiliza 2 computadoras CESIUS, una como emisor (E) y otra como receptor (R). Para que funcione correctamente se necesita sincronizar la ejecución de los programas de ambas computadoras. Dado que el número de instrucciones de los programas de las computadoras son diferentes, se modifica el periodo del reloj de las Unidades de Control, para que así ambos programas se ejecuten en el mismo tiempo. Se pide calcular el ciclo por instrucción medio de cada computadora, detallando el cálculo en el recuadro adjunto. NOTA: Los datos de la computadora CESIUS y de los programas son:

• Las instrucciones directas se ejecutan en 1 ciclo del reloj y las indirectas en 2 ciclos del reloj. • Emisor: 80% instrucciones directas, 20% indirectas y número total de instrucciones 140. • Receptor: 60% instrucciones directas, 40% indirectas y número total de instrucciones 60.

Pseudo / Instrucción ORG 1 SAL INI DV: DRE NUM NUM: CTE -9 PUN: ESP 1 DOS: CTE 2 UNO: CTE 1 INI: CAR DV SUM UNO ALM I DOS MOD UNO RES NUM ALM PUN ESC I PUN ALT FIN




CUESTIÓN 3 (4 puntos) Entre las numerosas aportaciones de von Neumann están las serie convergente que se explica a continuación. Dada una matriz A cuadrada de dimensión N se define la serie convergente de von Neumann como

donde

€

IN es una matriz identidad de dimensión N, es decir formada por unos en los elementos de la diagonal principal y ceros en el resto. Por ejemplo, si N=2 la serie viene dada por

€

S =1 00 1⎛

⎝ ⎜

⎞

⎠ ⎟ −

a11 a12

a21 a22

⎛

⎝ ⎜

⎞

⎠ ⎟

⎡

⎣ ⎢

⎤

⎦ ⎥

−1

= 1 00 1⎛

⎝ ⎜

⎞

⎠ ⎟ +

a11 a12

a21 a22

⎛

⎝ ⎜

⎞

⎠ ⎟

1

+a11 a12

a21 a22

⎛

⎝ ⎜

⎞

⎠ ⎟

2

+a11 a12

a21 a22

⎛

⎝ ⎜

⎞

⎠ ⎟

3

++a11 a12

a21 a22

⎛

⎝ ⎜

⎞

⎠ ⎟

∞

.

Se desea hacer un programa que calcule una aproximación de la serie de orden p, es decir que el índice k varíe desde 0 hasta un valor entero predeterminado p, y no hasta infinito. Se pide:

a) Realice el diagrama de flujo de la función Pot que reciba como argumento una matriz cuadrada A, su dimensión N y la potencia a la que se quiere elevar dicha matriz k, k≥1. La función debe devolver la matriz elevada a la potencia k, es decir

€

Ak .

b) Realice el diagrama de flujo de la función NmnS que reciba como argumentos la matriz A, su dimensión N y el orden p, y que devuelva la matriz aproximada de la serie S. Para resolver este apartado debe utilizar obligatoriamente la función del apartado anterior.

Además, se dispone de las siguientes funciones, que también deberá utilizar obligatoriamente en la resolución de los apartados anteriores:

• La función Mul que recibe como argumento dos matrices cuadradas y su dimensión, y devuelve la matriz producto de ambas.

• La función Sum que recibe como argumento

dos matrices cuadradas y su dimensión, y que devuelva la matriz suma de ambas.

• La función Id que genera una matriz

identidad de dimensión N. Recibe como argumento la dimensión N y devuelve la matriz identidad.



A Matriz de

constantes enteras

Matriz para la serie

N Constante

entera Dimensión de la matriz

i Constante

entera Subíndice para matriz

j Constante

entera Subíndice para matriz

k Constante

entera Potencia de la matriz

Pot Devuelve una matriz

Función que calcula la potencia de la matriz

Sum Devuelve una matriz

Función que suma dos matrices

Mul Devuelve una matriz

Función que multiplica dos matrices

NmnS Devuelve una matriz

Función que calcula la matriz de la serie

Id Devuelve una matriz

Función que genera una matriz identidad




Apartado a) Apartado b)

FIN

INICIO

FIN

INICIO




CUESTIÓN 4 (4 Puntos) Conecta-4 es un juego en el que dos jugadores colocan fichas alternativamente, cada uno de un color, sobre un tablero vertical de 7 columnas y 6 filas. Gana el juego aquel jugador que consiga colocar 4 fichas de su color alineadas consecutivamente bien en horizontal, en vertical o en diagonal. Cada vez que un jugador realiza una jugada, éste elige una columna del tablero (de 1 a 7) e introduce la ficha por la parte superior, dejándola caer por gravedad hasta depositarse sobre la última ficha introducida en esa columna, si la hubiese. Por ejemplo, en el tablero de la derecha, si se elige jugar con la columna número 2, la ficha introducida terminaría colocada en la fila número 5, encima de la única ficha de esa columna. Se desea realizar un programa en MATLAB que permita a un ordenador jugar a este juego contra un jugador humano. Para ello se propone representar el tablero del juego como una matriz de 6 filas y 7 columnas, de modo que una casilla vacía estará representada por un 0, un 1 corresponderá a una ficha jugada por la máquina y un 2 a una ficha jugada por el jugador humano. Plantear un algoritmo eficaz para jugar a este juego sería largo de explicar y más aún de programar. Por este motivo, puede suponer ya programada una función llamada

[r] = evalua_jugada(M, col, color_jugador) que devuelve un valor numérico, r , que indica si es buena o mala jugada que el jugador dado por el parámetro color_jugador (1=ordenador, 2=humano), coloque su ficha en la columna col, suponiendo que el tablero se encuentra en la situación indicada por la matriz M. La mejor jugada será aquella columna que haga máximo el valor de r según la función anterior. Para completar el programa se pide que escriba las funciones que se detallan a continuación: 1. Diseñar la función actualiza_tablero que devuelve la matriz del tablero una vez se ha introducido una nueva

ficha. La función recibe como parámetros la matriz del tablero antes de introducir la ficha, la columna en la que se introducirá la ficha, y el color de la ficha (1=ordenador, 2=humano). La función debe devolver dos datos: La matriz del tablero actualizada y un valor numérico que valdrá 1 si se logró colocar la ficha con éxito, y 0 en caso contrario (si la columna ya estaba llena de fichas).

1 2 3 4 5 6 7

1

2

3

4

5

6

Function [______________]=actualiza_tablero(_____________________________)




2. Diseñar la función max_alineadas que determinará el tamaño del mayor grupo de fichas de un determinado

color que están alineadas, bien en horizontal, vertical o diagonal. La función recibe como parámetros la matriz del tablero y el color de las fichas de las que se quiere buscar la alineación (1=ordenador, 2=humano). La función devolverá el valor entero del mayor número de fichas alineadas del tablero.

function [_________]=max_alineadas(_______________________________________)




3. Diseñar la función juega_conecta_4 que, llamando obligatoriamente y convenientemente a las funciones

anteriores articule el programa principal del juego. Para ello la función deberá por este orden: • Preguntar por teclado qué jugador comenzará a jugar el juego (1=ordenador, 2=jugador humano) • Dar paso alternativamente a cada jugador, ordenador y humano, para que efectúen sus jugadas. En el

caso del jugador humano, se pedirá por teclado el número de la columna que juega. Si el jugador humano selecciona una jugada imposible (número de columna no existente o intenta colocar una ficha en una columna ya completa), deberá indicarse con un mensaje y permitir que el jugador introduzca otra columna.

• Tras cada jugada, se actualizará el tablero mostrándolo por pantalla (basta con mostrar la matriz que representa el tablero).

• En caso de que un jugador gane, deberá mostrarse un mensaje indicando quién ha ganado. Si se produce empate (se completa el tablero sin que ningún jugador alinee 4 fichas de su color), se mostrará también un mensaje.

function juega_conecta_4

Dpto. Ing. de Sistemas y Automática. Universidad de Sevilla. Informática 1er curso Grado Ingeniería Civil. 21 de enero de 2011



Respuesta e)

bits

CUESTIÓN 1 (3 Puntos) Se desea diseñar una Unidad de Control de una computadora que tiene una arquitectura idéntica a la de la computadora CESIUS, pero con registros de distinto tamaño y con distinto juego de instrucciones. En concreto, la Unidad Aritmético-Lógica no necesita operaciones aritméticas, sólo operaciones lógicas. La Unidad de Control debe ser capaz de ejecutar las siguientes operaciones:

DESCRIPCIÓN FUNCIONAMIENTO JUEGO DE INSTRUCCIONES (apartado a)

Leer dato de teclado E → M(D) Escribir dato a pantalla M(D) → E

Cargar en el acumulador M(D) → A Almacenar en memoria (A) → M(D) Operación lógica AND (A) AND M(D) → A Operación lógica OR (A) OR M(D) → A

Operación lógica NOT NOT (A) → A Parar la máquina (P) → P

D: Dirección de memoria. E: Registro de E/S. A: Registro acumulador. P: Registro puntero de instrucciones. La memoria de programa es de tipo RAM y se direcciona a través de un bus de direcciones de 5 bits. La memoria comienza en la dirección 0 y la computadora empieza a ejecutar el programa en la dirección 0. La máquina opera sólo con números enteros binarios positivos y negativos codificados en complemento a 2. Se pide:

a) Diseñe el juego de instrucciones de la Unidad de Control tal que ocupe el menor espacio posible en memoria. Conteste este apartado en el espacio en blanco de la tabla de arriba.

b) Capacidad de la memoria. c) Mínimo valor entero que es posible almacenar (en decimal). d) Realizar un programa que lea del teclado el valor de dos números, evalúe para esos valores introducidos la

función lógica para cada par de bits a, b de los números, y escriba el resultado en la pantalla. e) Diseñe en el interior del recuadro al margen, el circuito lógico de las operaciones AND y NOT de la Unidad

Aritmético-Lógica, sólo para el bit menos significativo o de menor peso de los registros correspondientes. Detallar explícitamente los registros de entrada y salida a los circuitos lógicos.

NOTA: No existe un programa traductor.

Respuesta d) COMENTARIO DIRECCIÓN MEMORIA




CUESTIÓN 2 (1 punto) Un sistema de comunicaciones utiliza 2 computadoras CESIUS, una como emisor (E) y otra como receptor (R). Para que funcione correctamente se necesita sincronizar la ejecución de los programas de ambas computadoras. Dado que el número de instrucciones de los programas de las computadoras son diferentes, se modifica el periodo del reloj de las Unidades de Control, para que así ambos programas se ejecuten en el mismo tiempo. Se pide:

a) Calcule el ciclo por instrucción medio de cada computadora.

b) Sabiendo que el consumo de energía en proporcional al cubo de la frecuencia del reloj, ¿cuál de las computadoras consumirá más energía ?

NOTA: Los datos de la computadora CESIUS y de los programas son:

• Las instrucciones directas se ejecutan en 1 ciclo del reloj y las indirectas en 2 ciclos del reloj. • Emisor: 80% instrucciones directas, 20% indirectas y número total de instrucciones 140. • Receptor: 60% instrucciones directas, 40% indirectas y número total de instrucciones 60.

CUESTIÓN 3 (2 puntos) Se desea hacer un programa para calcular una aproximación de la

€

N de un número N>1 dado. Para ello, utilizando el método de la bisección sucesiva, codifique en MATLAB la función Raiz2, que reciba como

argumento el número N y la precisión requerida h, y devuelva la aproximación de la

€

N .

function .......... = Raiz2 (....................)

E : R :




CUESTIÓN 4 (4 puntos) A todo grafo orientado de N vértices se le puede asociar una matriz booleana A cuadrada de dimensión N, de modo que cada elemento aij de la matriz toma el valor 1 si existe arco entre los vértices (i,j), y 0 en caso contrario. Por ejemplo para un grafo con 4 vértices, vértices 1,2,3 y 4 denominados a,b,c, y d en la figura, la matriz asociada será:

€

a b c d[ ]

A =

0 1 0 00 0 1 11 0 0 10 0 0 0

⎡

⎣

⎢ ⎢ ⎢ ⎢

⎤

⎦

⎥ ⎥ ⎥ ⎥

abcd

⎡

⎣

⎢ ⎢ ⎢ ⎢

⎤

⎦

⎥ ⎥ ⎥ ⎥

La matriz A indica los caminos de longitud 1 entre los vértices (i,j). Hallando: A2 = A·A, cada elemento de la matriz indica el número de caminos de longitud 2 entre los vértices (i,j); A3, cada elemento de la matriz indica el número de caminos de longitud 3 entre los vértices (i,j); y así sucesivamente. Se pide:

a) Realice el diagrama de flujo de la función Diag0 que reciba como argumento una matriz cuadrada y su dimensión, y que devuelva un valor 1 si los elementos de la diagonal son cero, y un valor 0 en caso contrario.

b) Realice el diagrama de flujo de la función Cero que reciba como argumento una matriz cuadrada y su dimensión, y que devuelva un valor 1 si todos los elementos de la matriz son cero, y un valor 0 en caso contrario.

c) Se pueden detectar si existen circuitos en el grafo hallando las potencias sucesivas de A. Si no existen circuitos habrá un número k ≤ N, tal que Ak es nula a partir de la potencia k y además todas las sucesivas potencias deben tener su diagonal principal nula. En el ejemplo hay un circuito de longitud 3 (abc). Realice el diagrama de flujo de la función Circuito que reciba como argumentos la matriz A y su dimensión N, y que devuelva un valor cero si no encuentra ningún circuito, y si encuentra un circuito la longitud del mismo. En el caso de que exista circuito sólo debe calcular la longitud del circuito de longitud mínima. Se dispone, además, de la función Mul que recibe como argumento dos matrices cuadradas y su dimensión, y devuelve la matriz producto de ambas. Para resolver este apartado debe utilizar obligatoriamente las funciones de los apartados anteriores.


a b

c

d


A Matriz de

constantes enteras

Matriz del grafo

N Constante entera Dimensión de la matriz

i Constante entera Subíndice para matriz

j Constante entera Subíndice para matriz

k Constante entera Potencia de la matriz

Diag0 Devuelve un entero

Función que comprueba ceros en la diagonal

Cero Devuelve un entero

Función que comprueba si matriz es cero

Mul Devuelve una matriz

Función que multiplica dos matrices




Apartado a) Apartado c)

FIN

INICIO

FIN

INICIO

INICIO

FIN

Apartado b)

Documents

Dpto. Ing. de Sistemas y Automática. Universidad de ...jaar/Datos/IIC/Examenes.pdf · Informática. 1er curso Grado Ing. Civil. 26 de junio de 2013 APELLIDOS: NOMBRE: D.N.I.: Escriba