xámenes 1er cuatrimestre cursos 2004/07

DISA. ESI. US. Examen de Fund. de Informática. Primer curso de Ing. Industrial . Febrero de 2004. 1/6 Apellidos Nombre DNI

Escriba sus datos personales en todas y cada una de las hojas al comienzo del examen. Se recomienda que use lápiz. Escriba las respuestas únicamente en el espacio indicado.

CUESTIÓN 1 (2 puntos) En la figura adjunta se muestra un dispositivo para mostrar dígitos decimales. El dispositivo consta de 7 bombillitas, llamadas en la figura a,b,c,d,e,f y g. Se desea diseñar un circuito lógico que recibe un número binario natural positivo de 3 bits (en la figura A1, A2, A3) tal que represente en el dispositivo el número correspondiente en decimal, encendiendo las bombillitas que correspondan.

Se pide:

a) Realizar la tabla de verdad de todas las bombillitas. Responda en la tabla inferior. No tienen que estar rellenas todas las filas.

b) Calcular las expresiones de las funciones lógicas de las bombillitas “e” y “c”, de la

forma más sencilla que crea posible, e implementar el circuito con puertas lógicas de las mismas.

a)

A3 A2 A1

CIRCUITO

LÓGICO

a

A3

A2

A1

c

g



b)



#include <stdio.h> void main(void) { printf("Primer dato:"); scanf("%d",&x); printf("Segundo dato:"); scanf("%d",&y); printf("Media = %f", m); } void media(int a, int b) { }

CUESTIÓN 2 (2 puntos)

a) El siguiente programa en C debe calcular el número de vacas exacto a partir del número de patas en total. Se han numerado las líneas de código para que rellene las casillas de abajo con los fallos de codificación que cree que hay en el programa, y las correspondientes correcciones, indicando la línea de código.

1. #include <stdio.h> 2. void main(void) 3. { vacas; 4. patas int; 5. printf(“¿Cuantas patas has contado?\n”); 6. scanf("%c", patas); 7. vacas = patas/4; 8. printf("Me parece que debe haber %f vacas.\n", vacas); 9. }

Número de línea de código Fallo Corrección

b) Modifique el siguiente programa en C para que la función definida como media no devuelva ningún valor, pero la calcule adecuadamente. Sólo debe rellenar los huecos.

#include <stdio.h> void main(void) { int x; int y; float m; float media(int, int); printf("Primer dato:"); scanf("%d",&x); printf("Segundo dato:"); scanf("%d",&y); m = media(x,y); printf("Media = %f", m); } float media(int a, int b) { float m; m = (a+b)/2.0; return m; }



1 0 0 1 1 1 1 1 0 0 1 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11

CUESTIÓN 3 (3 puntos) Dibujar los diagramas de flujo que resuelven los siguientes problemas y rellenar las tablas de variables de cada uno: a) Suponga leída una secuencia binaria v de N bits, encontrar la primera secuencia de S

unos seguidos y escribir por pantalla la posición del primer uno dentro de la secuencia v. Si no se encuentra ninguna secuencia de S unos seguidos, mostrar por pantalla un cero.

b) Si la secuencia binaria leída representa un nº en base 2 tal que vN es el bit menos

significativo, calcular el número que representa en base 10 y escribirlo en pantalla. Ejemplo: N=11

S =3

a) Por pantalla: 4 b) Por pantalla: 1273 No utilice más espacio que el indicado. Use acceso a vectores y matrices mediante subíndices. Emplee únicamente expresiones en lenguaje natural, operaciones aritméticas (+, -, ·, /, resto de la división entera), asignación (←) y comparaciones (>, <, =, ≠, ≤, ≥). Se puntuará la claridad y legibilidad de los diagramas. a)

v Vector de variables enteras

Dato. Secuencia leída de bits.

N Variable entera Dato. Número de bits de la secuencia leída. S Variable entera Dato. Número de bits a 1 que localizar en v.

b) v Vector de

variables enteras Dato. Secuencia leída de bits.

N Variable entera Dato. Número de bits de la secuencia leída.



Inicio a Inicio b

Fin a Fin b



CUESTIÓN 4 ( 3 puntos) Dado el programa en LS-2 del recuadro de la derecha: a) Indique en la tabla de abajo el contenido de cada registro de la máquina CESIUS tras la ejecución de cada instrucción del programa. Tenga en cuenta lo siguiente: • En la primera columna de la tabla de abajo se debe anotar la dirección de memoria de la instrucción que se ha ejecutado. • El contenido de los registros se debe representar mediante códigos mnemónicos y números decimales. • Recuerde que se representará el estado del registro TRAS haber completado la instrucción. • Utilice el mnemotécnico para representar el código de operación y modo de direccionamiento en caso de que el contenido del registro sea una instrucción. • Suponga que al inicio de la ejecución del programa, todos los registros de la máquina tienen el valor 0 excepto P y la memoria, que tendrán el valor adecuado que le corresponda.

b) Indique el contenido binario de las siguientes direcciones de memoria

(el código de operación de la instrucción carga es 0010) Dirección

Instrucción P I A T S E

ORG 10 SAL INI TABLA: CTE 2 CTE 5 CTE -3 CTE 0 CTE 2 CTE -25 M: CTE 2 N: CTE 3 K: ESP 1 J: ESP 1 PUN: ESP 1 DT: DRE TABLA UNO: CTE 1 INI: LEE K LEE J CAR K RES UNO MUL N SUM J RES UNO SUM DT ALM PUN CAR I PUN SAN END SAL INI END: ALT FIN

16 22 33

Dpto. Ing. de Sistemas y Automática. U. de Sevilla. Examen Final de Junio. Fundamentos de Informática 1er curso Ingeniero Industrial. 21 de Junio de 2004

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. Entregue todas las hojas con su nombre y apellidos.

Hoja 1/4

CUESTIÓN 1 (3.5 Puntos)

Figurita original

1 0 0

1 0 0

1 1 0

Rotación a derechas

1 1 1

1 0 0

0 0 0

Flip horizontal

0 0 0

1 0 0

1 1 1

Se desea hacer un cierto algoritmo para un juego. El algoritmo recibe una matriz A de dimensiones 3x3. La matriz describe una cierta figurita en blanco y negro. Los elementos de la matriz aij contienen unos (color negro) para representar elementos de la figurita y ceros (color blanco) en otro caso. Por ejemplo véase en la figura de la derecha que se representa con unos una sencilla figura, que podría ser el carácter “L”, y el resto de componentes de la matriz son cero. El algoritmo lee desde el teclado los elementos aij de la matriz A y una variable p. Según el valor de p el algoritmo debe hacer lo siguiente:

• Si p=1, debe rotar la figura a derechas 90 grados.

• Si p=2, debe hacer un Flip horizontal respecto de la fila central, es decir hacer una imagen especular de las filas superior e inferior.

• Si p>2, el algoritmo continua y escribe la matriz resultante B.

El algoritmo se representa en la figura de abajo a la izquierda, en forma de diagrama de flujo. En dicho diagrama de flujo ya está implementada la parte de lectura desde el teclado de los elementos aij de la matriz A y la variable p. También se tienen inicializados a cero los subíndices i y j.

Se pide que se completen los dos diagramas de flujo correspondientes a la rotación y al flip de la figurita representada en la matriz A, de modo que no pueden definirse más subíndices que los ya inicializados i y j. Además la matriz resultante de la rotación o del flip debe almacenarse en los elementos bij de una matriz B, ya inicializada.

Eje de giro

FIN MODULO

LEE MATRIZ A

y variable p

¿p>2?

ROTACIÓN

A DERECHAS

FLIP

HORIZONTAL

¿p=1? SI NO

INICIO ROTACIÓN A DERECHAS INICIO FLIP HORIZONTAL

FIN ROTACIÓN A DERECHAS FIN FLIP HORIZONTAL

SI

NO

ESCRIBE MATRIZ B

INICIO MODULO

SI

Dpto. Ing. de Sistemas y Automática. U. de Sevilla. Examen Final de Junio. Fundamentos de Informática 1er curso Ingeniero Industrial. 21 de Julio de 2004

NOMBRE: Nº MATRÍCULA/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. Entregue todas las hojas con su nombre y apellidos.

Hoja 2/4


Se desea realizar un algoritmo que lea un número entero (positivo o negativo) y escriba dicho número en binario codificado en modo signo-valor absoluto en N bits. Asuma que el número se puede representar con N bits.

La representación en modo signo-valor absoluto consiste en considerar el bit más significativo (el 1º) como bit de signo (0 positivo, 1 negativo) y en los N-1 bits restantes codificar en binario el valor absoluto del número (ver ejemplos).

Para solucionar este problema se propone lo siguiente:

1) Realice un diagrama de flujo correspondiente a un módulo que tome un número positivo num y determine un vector b de N componentes que contiene la codificación binaria en base 2 del mismo. Considere que la componente b1 corresponde al bit menos significativo (el último), y la bN al signo.

2) Utilizando el módulo anterior, realice un diagrama de flujo que solucione el problema

Por ejemplo: Si se lee el número 100 y se consideran 8 bits, el módulo del apartado 1) genera el vector

b=[0,0,1,0,0,1,1,0] y el diagrama completo escribe la secuencia 01100100. Si se lee el número -100 y se consideran 8 bits, el módulo del apartado 1) genera el mismo vector b=[0,0,1,0,0,1,1,0] y el diagrama completo escribe la secuencia 11100100.

INICIO DEL MÓDULO

FIN DEL MÓDULO

INICIO DEL DIAGRAMA PRINCIPAL

FIN DEL DIAGRAMA PRINCIPAL



Hoja 3/4

CUESTIÓN 3 (3 Puntos) Responda las siguientes cuestiones en los cuadros o tablas indicadas. 3.1. ¿Cuántos caracteres (bytes) forman 1 Gigacaracter (Gigabyte)? 3.2. Rellene la tabla de verdad correspondiente al circuito de puertas lógicas de la figura

a b S1 S2 S3

3.3. Indique las transferencias elementales entre registros y las señales de gobierno necesarias en orden de

activación y separadas por comas correspondientes a cada transferencia para la ejecución de la instrucción SAL ETI en la máquina CESIUS.

Transferencias Señales de gobierno

3.4. ¿En qué se diferencian los conceptos de instrucción y pseudoinstrucción? 3.5. ¿Cuál de estos diagramas de flujo está desestructurado? Razone su respuesta.

A

Inicio

Fin

b <- b+1

¿ a>2 ?

¿ b<1 ?

¿ a>2 ?

SI

SI

SI

NO

NO

NO

B

Inicio

Fin

R <- R-1

¿ R = 0 ?

SI

NO

R <- 0

R <- 2

3.6. Indique 3 funciones genéricas de un sistema operativo o de explotación.



Hoja 4/4

3.7. Si las variables utilizadas en un programa se definen en la tabla de la figura, ¿con qué conjunto de instrucciones se actualizaría en LS2 el puntero para acceder al elemento (CF,CC) de una matriz y escribirlo por pantalla?

PUN Puntero a un elemento de la matriz DCM Dirección de comienzo de la matriz en memoria M Nº de elementos de una fila N Nº de elementos de una columna CF Índice de filas de 1 a M CC Índice de columnas de 1 a N UNO Constante 1

3.8. En el cuadro A, dibuje el diagrama de flujo que resuelve el problema “Leer las 10 componentes de un vector de

dimensión 10”. En el cuadro B, escriba el programa en LS2 y en cuadro C, escriba el programa en lenguaje C. Las variables se nombrarán según

PUN Puntero a un elemento del vector DV Dirección de comienzo del vector K Entero índice de las componentes del vector V Vector de 10 enteros

A: Diagrama de Flujo B: LENGUAJE LS2 C: LENGUAJE C

ORG 0 SAL INI

V: ESP 10

DISA. ESI. US. Examen de Fund. de Informática. Primer curso de Ing. Industrial. Septiembre de 2004. 1/6 Apellidos Nombre DNI

Escriba sus datos personales en todas y cada una de las hojas al comienzo del examen. Se recomienda que use lápiz. Escriba las respuestas únicamente en el espacio indicado. CUESTIÓN 1 (1.75 puntos) Considere una secuencia de N bits almacenados en un vector b de N componentes de forma que bN almacena el bit más significativo de la secuencia. Se pide realizar un algoritmo que obtenga el número en octal (en base 8), lo almacene en el vector d y lo escriba en pantalla. Para pasar de un número en base 2 a base 8, basta con tomar los bits de la secuencia de 3 en 3 e interpretarlos como un número decimal. Véase el siguiente ejemplo, en el que el número binario 01011110 se transforma en el 136 en base 8. Para realizar el algoritmo se pide

a) Un módulo que tome un número binario de 3 bits almacenado en un vector v y calcule el dígito decimal que representa.

b) Basándose en el anterior, hacer el diagrama de flujo que resuelve el problema.

b Vector de N enteros M Entero. Número de componentes de d d Vector de M enteros

b8 b7 b6 b5 b4 b3 b2 b1 b 0 1 0 1 1 1 1 0 d

1=01)2 3=011)2 6=110)2 d3 d2 d1


Escriba sus datos personales en todas y cada una de las hojas al comienzo del examen. Se recomienda que use lápiz. Escriba las respuestas únicamente en el espacio indicado. CUESTIÓN 2 (1.5 puntos) 2.1. ¿Cuáles son las partes fundamentales de la estructura de un ordenador propuesta por Von Neumann?

2.2. Dada la tabla de verdad de la figura, dibuje una realización con puertas lógicas.

a b c L

0 0 0 0

0 0 1 0

0 1 0 0

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 1 2.3. Indique las fases de ejecución de la instrucción SUMA ETI y las transferencias entre

registros en cada una de ellas.

2.4. ¿Qué es un puntero? Si llamamos al puntero con la etiqueta PUN, indique cómo se indicaría, usando transferencias entre registros, el objeto al que se apunta en un direccionamiento indirecto.

Objeto =


Escriba sus datos personales en todas y cada una de las hojas al comienzo del examen. Se recomienda que use lápiz. Escriba las respuestas únicamente en el espacio indicado. 2.5. ¿Qué indica el símbolo en un diagrama de flujo? Explique. ¿y el símbolo ? 2.6. ¿Para qué sirve la pseudoinstrucción DRE en LS2? 2.7. ¿En qué consiste un sistema multitarea?


Escriba sus datos personales en todas y cada una de las hojas al comienzo del examen. Se recomienda que use lápiz. Escriba las respuestas únicamente en el espacio indicado. 2.8. Realice el diagrama de flujo, el programa en LS2 y el programa en C que resuelva el

siguiente problema: Leer un número entero N. Leer las N componentes de un vector de reales de dimensión N de la 1 a la N y escribirlas luego en pantalla de la N a la 1. Se supone que N siempre va a ser menor o igual que 100 (no hay que comprobarlo).

PUN Puntero a un elemento del vector N Entero, tamaño del vector DV Dirección de comienzo del vector K Entero índice de las componentes del vector V Vector de 10 números reales DIAGRAMA DE FLUJO CÓDIGO EN LS2 CÓDIGO EN C ETIQUETAS, INST o PSEUDOINST


Escriba sus datos personales en todas y cada una de las hojas al comienzo del examen. Se recomienda que use lápiz. Escriba las respuestas únicamente en el espacio indicado. CUESTIÓN 3 (1.75 puntos) a) El circuito lógico de la figura convierte un número binario de 4 bits (A4 A3 A2 A1) en un

código binario de 7 bits, el cual representa un dígito decimal en un marcador electrónico. El marcador consta de 7 bombillitas, llamadas en la figura a,b,c,d,e,f y g. Por ejemplo, si el circuito lógico recibe como entrada, en el registro de 4 bits, el código binario “0001” aparece en el marcador electrónico el número “1”, encendiendo dicho circuito las

bombillitas b y c. Complete las casillas vacías de la tabla lógica adjunta que describe el funcionamiento del circuito lógico. NOTA: el estado de las bombillitas es: “0” apagada y “1” encendida.

NÚMERO NÚMERO REPRESENTADO EN EL MARCADOR

BINARIO CÓDIGO BINARIO BOMBILLAS DECIMAL

A4 A3 A2 A1 g f e d c b a NÚMERO DECIMAL

CORRESPONDIENTE 0 0 0 0 0 0 1 1 1 1 1 1 X0 = 63 1 0 0 0 1 0 0 0 0 1 1 0 X1 = 2 0 0 1 0 X2 = 91 3 0 0 1 1 X3 = 4 0 1 0 0 X4 = 5 0 1 0 1 X5 = 109 6 0 1 1 0 1 1 1 1 1 0 1 X6 = 7 0 1 1 1 0 0 0 0 1 1 1 X7 = 8 1 0 0 0 1 1 1 1 1 1 1 X8 = 127 9 1 0 0 1

1 1 0 1 1 1 1 X9 = b) Para poder utilizar el marcador en el estadio de fútbol municipal, se substituye el circuito

lógico por la computadora CESIUS. Además se usarán dos marcadores electrónicos, uno para el equipo local y el otro para el equipo visitante. La conexión con la computadora CESIUS se hace del modo siguiente: se desconecta la pantalla del registro de entrada salida (E) y se conectan los marcadores como se ve en la figura adjunta. Desde el punto de vista del funcionamiento de la computadora CESIUS no ha cambiado nada, sólo ha cambiado el periférico pantalla por otro periférico formado por los dos marcadores. Dichos marcadores están conectados físicamente al registro E como se ve en la figura, donde las 7 primeras celdas se conectan a las bombillitas correspondientes y la octava celda denominada EN se conecta a la entrada EN de los marcadores. La nueva entrada EN de los marcadores funciona como un interruptor tal que, si el bit EN del registro E está a “0” los datos pasan al marcador local, y si está a “1” pasan al visitante. Termine el programa en LS2 que está comenzado. El programa espera a leer desde el teclado los tanteos del equipo local y visitante. Una vez leídos ambos tanteos debe escribir dicho tanteo en sendos marcadores.

CIRCUITO

LÓGICO

a

A3

A2

A1

c

g

A4


Escriba sus datos personales en todas y cada una de las hojas al comienzo del examen. Se recomienda que use lápiz. Escriba las respuestas únicamente en el espacio indicado. NOTAS: Todos los registros de la computadora están por defecto a cero. No se pueden usar más reservas de espacio en memoria ni constantes adicionales. La dirección de memoria DIRLIBRE está libre para almacenar lo que estime oportuno.

PROGRAMA EN LS2 ETIQUETAS INSTRUCCIÓN DIR/DATO COMENTARIO

ORG 0 SAL INI DATOS : CTE ______ ’X0 CTE ______ ‘X1 CTE ______ ‘X2 CTE ______ ‘X3 CTE ______ ‘X4 CTE ______ ‘X5 CTE ______ ‘X6 CTE ______ ‘X7 CTE ______ ‘X8 CTE ______ ‘X9 DIRDATOS : DRE DATOS PUN : ESP 1 EN : CTE 128 LOCAL : ESP 1 VISITANTE : ESP 1 DIRLIBRE : ESP 1 INI : LEE LOCAL LEE VISITANTE … (Continúe el programa a partir de aquí)

INSTRUCCIÓN DIR/DATO

A P

S

I T

E … EN g f e d c b a

LOCAL

CESIUS

VISITANTE

EN g f e d c b a

ENg f e d c b a

Dpto. Ingeniería de Sistemas y Automática. Universidad de Sevilla. Examen 1er Parcial. Fundamentos de Informática - 1er curso Ingeniero Industrial. 10 de Febrero de 2005

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. Entregue todas las hojas con sus apellidos, nombre, y D.N.I.

Hoja 1/6

CUESTIÓN 1 (1 punto)

A) Complete los huecos de la tabla sabiendo que en cada fila se representa una misma cantidad, en cada columna se utiliza un mismo sistema de representación. Los sistemas binarios empleados son: complemento a uno, complemento a dos y signo-valor absoluto todos ellos con ocho celdas. Los huecos tachados NO han de completarse.

decimal complemento a uno complemento a dos signo-valor absoluto

-11 ------------- -------------

27 ------------- -------------

------ 10100110

------------- 10000000 -------------

------ ------------- 00101110

------ ------------- 10101111

B) Escriba la tabla de verdad correspondiente y el circuito de puertas lógicas asociado a cada salida en el

recuadro. Las entradas son las variables lógicas a, b y c1 (acarreo de la suma anterior) y la salidas son la suma de dos dígitos binarios s y el acarreo c2.

a b c1 s c2


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. Entregue todas las hojas con sus apellidos, nombre, y D.N.I.

Hoja 2/6

CUESTIÓN 2 (1 punto) Se presenta el problema de regular el acceso a un tramo de vía férrea compartida por parte de trenes que circulan en sentido contrario. La regulación se lleva a cabo mediante dos semáforos en los extremos del tramo de vía (señales S1 y S2), que deberán valer “1” para poner el semáforo respectivo en rojo y “0” para ponerlo en verde. La detección de la presencia de trenes se efectúa mediante sensores colocados en los extremos del cruce (T1 y T2) y dentro del tramo de vía compartida (TC), que indicarán con valor “1” si el tren está presente en el lugar correspondiente al sensor, o “0” si no lo está. En caso de conflicto debido a que dos trenes quieran acceder simultáneamente al tramo compartido, se dará prioridad de paso al entrante por la derecha (T1).

A) Tabla de Verdad del sistema.

T2 TC T1 S1 S2 1 1 1 1 1

B) Función lógica de las señales que gobiernan el estado de los semáforos. S1 = S2 =


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. Entregue todas las hojas con sus apellidos, nombre, y D.N.I. CUESTIÓN 3 (2 puntos) El programa en LS-2 del recuadro de la derecha es traducido y ejecutado. Indique en la tabla de abajo el contenido de los registros indicados de la máquina CESIUS tras la ejecución de cada una de las instrucciones del programa. Tenga en cuenta lo siguiente:

• En la primera columna de la tabla de abajo se debe anotar la dirección de memoria de la instrucción que se ha ejecutado.

• Si el registro contiene un número emplee el sistema decimal. Si el registro contiene una instrucción emplee códigos mnemónicos y números decimales.

• Recuerde que se representará el estado del registro TRAS haber completado la instrucción.

La primera línea ha sido ya rellenada a modo de ejemplo.

Dirección P I T 2 9 SAL 9 SAL 9

ORG 2

SAL INI DA: CTE 10

DB: CTE 0 DD: DRE DA

P: ESP 1 UNO: CTE 1

N: CTE 4 INI: CAR DD

ALM P IB: CAR I P

SAC SB ESC I P

CAR P SUM UNO

ALM P RES DD

RES N SAN IB

SB: ALT FIN

Hoja 3/6

A E 0 0


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. Entregue todas las hojas con sus apellidos, nombre, y D.N.I. CUESTIÓN 4 (3 puntos) Obtenga un algoritmo que resuelva el problema cuyo enunciado es: Calcular el producto de los e primeros elementos de una sucesión cuyo término general cumple: ak = ak-1 + 2·ak-2 + ... + n·ak-n , siendo a1=1 , a2=2, ..., an=n El algoritmo ha de leer únicamente el valor de e y de n. Suponga que ambos son enteros y positivos. El algoritmo ha de escribir como único resultado el producto:

∏=

=e

hhap

1

Se pide: dibujar el diagrama de flujo en el recuadro y escribir la lista de objetos usados en la tabla. Para la confección del diagrama utilice únicamente las operaciones +,-, ·, /, asignación (←), comparaciones >, <, >=, <=, acceso a memoria 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. Se puntuará el buen funcionamiento, la claridad y la estructuración.

Hoja 4/6


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. Entregue todas las hojas con sus apellidos, nombre, y D.N.I. CUESTIÓN 5 (3 puntos)

i

Se ha desarrollado un algoritmo para incluirlo en un cierto programa de dibujo. El algoritmo resuelve el problema de relleno de una figura cerrada en dos dimensiones. La figura viene descrita por un “mapa de bits” en blanco y negro (ver recuadro abajo). Dicha figura se describe con una matriz A de dimensiones m x n, cuyos elementos aij pueden valer “0” (color blanco) ó “1” (color negro). El algoritmo completo se muestra en el recuadro del margen derecho, el cual contiene un módulo interno, PUNTO INTERIOR, que determina si un elemento aij está en el interior de la figura o no. Dicho módulo se subdivide en otros cuatro, denominados ARRIBA, ABAJO, IZQUIERDA y DERECHA. Cada uno de estos módulos recorre la figura desde un elemento aij cualquiera hacia donde indica su nombre y hasta que encuentra un borde de la figura (ver recuadro explicativo abajo), si es que dicho borde existe. Cada módulo ARRIBA, ABAJO, IZQUIERDA y DERECHA, modifica el valor de cierta variable F. Así el primer módulo, ARRIBA, si encuentra un borde incrementa el valor de la variable F. Después el segundo módulo, ABAJO, haría lo mismo, y así sucesivamente. Si cualquiera de los módulos no detecta borde alguno, no incrementa dicha variable. De este modo, si al pasar por los cuatro módulos el punto considerado está en el interior de la figura (es decir dentro de los bordes), F deberá valer 4.

NOTA: Para la confección del diagrama de flujo utilice únicamente las operaciones +,-, ·, /, asignación (←), comparaciones <, >, ≤, ≥, =, lógicas “y”, “o”, acceso a memoria con subíndices y expresiones literales en lenguaje natural. El diagrama de flujo ha de estar estructurado, ser claro y legible y ocupar dro.

a) RelosDEmóacoen

b) El INTqudeeleintemóIZQ

IZQUIERDA

ABAJO

ARRIBA

DERECHA

FIN PUNTO INTERI

INICIO PUNTO INTER

I

INICIO

SI

SI

F = 4

ai

PUNTO

INTERIOR

j>n

i>m

O

FIN

aij

j ABAJO

IZQUIERDA

ARRIBA

Figura original 0 0 0 0 0 1 0 00 1 1 0 1 0 1 00 1 1 0 1 0 1 00 1 1 0 1 0 0 10 1 0 1 1 0 0 10 1 0 0 0 0 0 10 0 1 0 0 1 1 00 0 0 1 1 1 0 00 0 0 0 0 0 0 0

Figura rellenada 0 0 0 0 0 1 0 00 1 1 0 1 1 1 00 1 1 0 1 1 1 00 1 1 0 1 1 1 10 1 1 1 1 1 1 10 1 1 1 1 1 1 10 0 1 1 1 1 1 00 0 0 1 1 1 0 00 0 0 0 0 0 0 0

S

j ← 1

NO

N

NO

j←j+1

i←i+1

j←1

i←1

IOR

F ← 0

DERECHA

sólo el espacio interior del recua

alizar los diagramas de flujo de módulos ARRIBA y RECHA. Nótese que son dulos y no subprogramas. Se nseja utilizar bucles con salida

cabeza o en medio.

diagrama del módulo PUNTO ERIOR, puede optimizarse, ya

e si cualquiera de sus módulos tecta que no existe un borde, el mento aij no será un punto rior. Optimícelo usando los dulos ARRIBA, ABAJO, UIERDA y DERECHA.

Hoja 5/6

OR


NOMBRE: Nº MATRÍCULA/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. Entregue todas las hojas con sus apellidos, nombre, y D.N.I.

Hoja 6/6

a)

FIN ARRIBA

INICIO ARRIBA

FIN DERECHA

INICIO DERECHA

b)

INICIO PUNTO INTERIOR OPTIMIZADO

FIN PUNTO INTERIOR OPTIMIZADO

NOMBRE VALOR DESCRIPCIÓN DEL OBJETO

m Constante entera Número de filas

n Constante entera Número de columnas

A Matriz m x n entera

Describe la figura a rellenar

aij Enteros Elementos “0” o “1” de la matriz A

i Entera Índice de filas

j Entera Índice de columnas

F Entera Variable que describe si un punto es interior

Dpto. Ing. de Sistemas y Automática. U. de Sevilla. Examen FINAL. Fundamentos de Informática 1er curso Ing. Ind. 23 de Junio de 2005

APELLIDOS: NOMBRE: D.N.I.: Escriba las respuestas en los recuadros indicados. Entregue todas las hojas con su nombre y apellidos. Puede usar el

lápiz para responder a las preguntas del examen.

Las notas saldrán el día 12 de Julio de 2005 a las 21:00 Horas. Hoja 1/4

CUESTIÓN 1 (3.0 Puntos) a) Complete los huecos de la tabla sabiendo que en cada fila se representa una misma cantidad, y en

cada columna se utiliza un mismo sistema de representación. Los sistemas binarios empleados son: complemento a uno, complemento a dos y signo-valor absoluto todos ellos con ocho dígitos. Los huecos tachados NO han de completarse. Indique “Fuera de rango” si fuera el caso.

Decimal Complemento a uno Complemento a dos Signo-valor absoluto

-12 ------------- -------------

26 ------------- -------------

------ 10101010 -------------

------------- 10000000 -------------

------ ------------- 10101001

b) Se desea diseñar un circuito lógico que realice la siguiente operación matemática s=-1⋅e (cambio de

signo). Los números s y e se expresan mediante complemento a dos con tres dígitos. Calcule la tabla de verdad. Calcule la función lógica correspondiente al dígito s1. Si se sale del rango indíquelo.

e2 e1 e0 s2 s1 s0

s1=





ORG 0 SAL INI

CERO: CTE 0 UNO: CTE 1 DOS: CTE 2 CINCO: CTE 10 VEC: ESP 5 BASE: DRE VEC PUN: ESP 1 IND1: ESP 1 IND2: ESP 1 DATO: ESP 1 INI: CAR UNO

ALM IND1 CAR BASE ALM PUN

BUC1: CAR IND1 ALM IND2 CAR UNO ALM DATO

BUC2: CAR DATO MUL DOS ALM DATO CAR IND2 RES UNO ALM IND2

SAP BUC2 CAR DATO ALM I PUN

CAR PUN SUM UNO ALM PUN CAR IND1 SUM UNO ALM IND1 RES CINCO SAP FINAL SAL BUC1

FINAL : ALT FIN

CUESTIÓN 2 (3.0 Puntos) Para el programa que se muestra a continuación, indique en decimal los valores de los registros tras ejecutar cada una de las instrucciones resaltadas sólo considerando la segunda vez que se pasa por el bucle BUC2.

Instrucción Dirección instrucción

S T I A

CAR DATO

MUL DOS

ALM DATO

CAR IND2

RES UNO

ALM IND2

SAP BUC2

NOTA: Para los códigos de operación puede emplear directamente el nombre de la instrucción. Responda sólo sobre la tabla.





CUESTIÓN 3 (4.0 Puntos) El código de cuenta corriente de una cuenta bancaria está compuesto por el código de entidad (4 dígitos), el código de sucursal (4 dígitos), el código de control (2 dígitos) y el número de cuenta (10 dígitos), como se muestra en la figura adjunta:

Para el cálculo de los 2 dígitos del código de control se utiliza el siguiente algoritmo, el cual calcula un dígito de control dado un número cualquiera de 10 dígitos:

1. Calcular el número N dado por la fórmula siguiente:

⎭⎬⎫

⎩⎨⎧

×−= ∑=

111110

1iii pdmodN

donde di el es el dígito i-ésimo del número cuyo dígito de control se desea calcular, pi es la componente i-ésima de un vector p de 10 componentes conocido para la entidad bancaria, y mod es la operación de resto de división entera (véase nota abajo).

2. Según el valor de N, el dígito de control valdrá: a. Si N = 11, entonces el dígito de control es 0. b. Si N = 10, entonces el dígito de control es 1. c. En cualquier otro caso el dígito de control es el propio número N.

Para obtener el primer dígito de control se utilizan los códigos de entidad y de sucursal del código de cuenta corriente añadiéndoles dos ceros por la izquierda, y después se le aplica el algoritmo dado. Para el segundo dígito de control se aplica el algoritmo a los 10 últimos dígitos correspondientes al número de cuenta. Se pide:

a) Realizar el diagrama de flujo del algoritmo dado para un número cualquiera cuyos dígitos están almacenados como un vector U de 10 componentes. Dicho algoritmo debe almacenar en una variable denominada DC el valor del dígito de control obtenido.

b) Usar el diagrama de flujo del apartado anterior como un módulo y realizar el diagrama de flujo para

comprobar que los dígitos de control de un código de cuenta corriente dado, son correctos. El código de cuenta corriente está almacenado en un vector V. Es obligatorio usar el módulo creado en el apartado anterior tantas veces como sea necesario.

NOTA: Para la confección del diagrama de flujo utilice únicamente las operaciones +,-, ·, /, asignación (←), comparaciones <, >, ≤, ≥, =, lógicas “y”, “o”, acceso a memoria con subíndices y expresiones literales en lenguaje natural. Además dispone de la operación resto de división y represéntela como mod(X/Y), es decir resto de dividir la cantidad X entre la cantidad Y. El diagrama de flujo ha de estar estructurado, ser claro y legible y ocupar sólo el espacio interior del recuadro correspondiente.

Código entidad

Código sucursal

Número de cuenta

Código control





a) b)


N Variable entera

Número resultado del algoritmo

DC Variable entera

Valor del dígito de control obtenido

U Vector de dimensión 10

Contiene el número dato para el algoritmo

p Vector de dimensión 10

Vector conocido para la entidad bancaria

V Vector Contiene el código de cuenta corriente

i Índice Para vectores

FIN MÓDULO

INICIO

FIN

INICIO MÓDULO

Dpto. Ing. de Sistemas y Automática. Universidad de Sevilla. Examen FINAL. Fundamentos de Informática 1er Curso de Ingeniería Industrial. 5 de Septiembre de 2005


lápiz para respder a las preguntas del examen.

Las notas saldrán el día 13 de Septiembre de 2005 a las 21:00 Horas. Hoja 1/7

CUESTION 1 (1 Punto) El programa adjunto es traducido, montado y ejecutado en la máquina CIMA-E.

ORG 0 Se pide: SAL INI a) El usuario introduce por teclado el número 3. ¿Qué se obtiene en

pantalla? VAX: BSS 1 VAY: BSS 1 DY: DEF VAY INI: PUSH DY LEE I DY CAR DY b) ¿Y si se introduce el número 8?

MUL DY PUSH VAY ESC DY ESC I DY POP VAX

ESC VAX POP VAX ESC VAX ALM VAX

ESC VAX ESC VY STP SAP INI END





CUESTIÓN 2 (2,5 Puntos) La asignación de diputados en una provincia se rige por la ley D’Hont. En una versión muy simplificada la ley se aplica como se describe a continuación. Suponga que se tiene una provincia a la que se le asignan 5 diputados y donde hay 4 formaciones políticas relevantes (F1, F2, F3 y F4). Después de la cita electoral se tendrá un vector de votos (V) donde cada elemento del vector hace referencia a los votos de una determinada fuerza política. Dicho vector (V), además, estará ordenado en número de votos de forma decreciente. Con este vector de votos se crea una matriz A como la que aparece en la figura y donde cada columna se corresponde con el vector V dividido por 1,2,3, … y así sucesivamente hasta el total de los 5 diputados asignados. Ahora sólo falta escoger las 5 cifras más altas de la matriz A y asignar a cada una un diputado (celdas sombreadas en la figura). En este caso, el resultado será el que aparece en la tabla al margen derecho. Dicho resultado puede almacenarse en un vector de diputados ordenado (D). Dado un vector de votos V, ya ordenado en forma decreciente, de una provincia a la que se le asignan N diputados y en la cual existen M fuerzas políticas relevantes, se pide:

a) Realizar un diagrama de flujo tal que dado el vector de votos V, ya ordenado, cree la matriz A de dimensiones M x N.

b) Realizar un diagrama de flujo que cree un vector de diputados D, donde cada elemento será el número de diputados asignado a la fuerza política correspondiente. Este apartado debe resolverse en dos partes. Primero crear un módulo que calcule el máximo de la matriz A y su posición. Después resolver el apartado usando dicho módulo el número de veces que sea necesario.

NOTA: Los vectores y matrices conocidos, ya están almacenados en memoria y el resto inicializados a cero. Para la elaboración del diagrama de flujo utilice únicamente las operaciones +,-, ·, /, asignación (←), comparaciones <, >, ≤, ≥, =, lógicas “y”, “o”, acceso a memoria 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 correspondiente.

A4x5VOTOS

(V) V÷2 V÷3 V÷4 V÷5

F1 120000 60000,0 40000,0 20000,0 13333,3

F2 82000 41000,0 27333,3 13666,7 9111,1

F3 55000 27500,0 18333,3 9166,7 6111,1

F4 25000 12500,0 8333,3 4166,7 2777,8

FUERZAS POLÍTICAS

DIPUTADOS (D)

F1 2 F2 2 F3 1 F4 0


M Constante Número de fuerzas políticas

N Constante Número de diputados

V Vector de dimensión M

Vector conocido de votos

D Vector de dimensión M Vector de diputados

A Matriz de

dimensionesM x N

Matriz para el cáculo del número de diputados

i Índice Para vectores / matrices

j Índice Para vectores / matrices

k Índice Para vectores / matrices





a) b) b)

INICIO apartado a)

FIN apartado a)

FIN MÓDULO apartado b)

INICIO MÓDULO apartado b)

FIN apartado b)

INICIO apartado b)





CUESTIÓN 3 [ 1.0 punto] Se tiene un fichero binario DATOS.BIN en el que hay almacenados un número indeterminado de datos de tipo int. Escriba un programa en C que saque por pantalla los números que sean divisibles por 3.





CUESTIÓN 4 [ 2,5 puntos] a) Escribir la función diagonal_suma que proporcione una matriz diagonal a partir de una matriz

cuadrada genérica de dimensiones nxn (n menor que 10). Cada elemento de la matriz diagonal se obtendrá como suma de los elementos de la fila correspondiente de la matriz genérica. Esta función recibe como parámetros la matriz genérica y una matriz inicializada con ceros donde se almacenará el resultado.

b) Escribir la función diagonal_dominante que devuelva 1 si cada elemento de la diagonal es el mayor

en valor absoluto de todos los elementos de su misma fila y 0 en caso contrario. Desarrollar la función necesaria para realizar esta operación suponiendo que las dimensiones de la matriz serán como máximo de 128x128. Esta función recibe como parámetro la matriz.





PROBLEMA (3.0 puntos) En la redacción de una revista se dispone de un programa en lenguaje C para la creación de sopas de letras. Para ello se emplea una matriz cuadrada de dimensiones 10x10 cuyos elementos son caracteres del alfabeto. El programa inicialmente crea la matriz y la rellena con caracteres al azar. A continuación el usuario introduce las palabras que desee que aparezcan en la sopa de letras, indicando la posición de inicio dentro de la misma y un valor numérico que indique la orientación., entre una de las posibilidades siguientes:

Valor Orientación de la palabra 1 diagonal hacia abajo a la derecha 2 diagonal hacia arriba a la derecha

Cuando el usuario ha tecleado la palabra correspondiente, el punto de comienzo de la palabra y la orientación, el programa salta a una función llamada insertar_palabra cuyos argumentos de entrada serán:

• La matriz de la sopa de letras. • Una cadena de caracteres con la palabra a insertar. • El índice de la fila donde comienza la palabra (entre 0 y 9). • El índice de la columna donde comienza la palabra (entre 0 y 9). • La orientación con la que ha de quedar la palabra en la sopa de letras (1 ó 2).

A su término la función devolverá un valor entero:

• Igual a 1 si la operación se realizó con éxito. • Igual a 0 si fracasó debido a que parte de la palabra o su totalidad excedía los límites de la matriz. En este

caso la matriz debe mantener su valor inicial. A modo de ejemplo considérese el siguiente caso: La matriz original aparece a la izquierda. El usuario teclea “churchill”, indica la posición (1,1) y al orientación le da el valor “1” (diagonal hacia abajo a la derecha). La función insertar_palabra verifica que hay espacio para la palabra y transforma la matriz de la izquierda en la de la derecha.

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 a m e r r t e e w e 0 a m e r r t e e w e 1 f j f r q h u a u r 1 f c f r q h u a u r 2 t h s e o b g d e t 2 t h h e o b g d e t 3 u g a q o v s h d o 3 u g a u o v s h d o 4 e e e s t x p t s a 4 s u p x r o p t s a 5 x p w c l s b g a e 5 x p w c l c b g a e 6 s q r d a w a d x d 6 s q r d a w h d x d 7 g w g e s i s f a d 7 g w g e s i s i a d 8 j e d r t h d g x h 8 j e d r t h d g l h 9 u r d t h d w g q l 9 u r d t h d w g q l

Se pide: 1. Escribir en lenguaje C la función insertar_palabra y todas aquellas que ésta necesite para sus operaciones. 2. Explicar mediante comentarios todas las operaciones que realiza dicha función y las respectivas subfunciones. NOTAS

• Se dispone de una función de librería int LongitudCadena(char *cad) que devuelve el número de caracteres contenidos en la cadena dada.

• Se valorará la modularidad del programa, para lo cual el alumno puede dividir las tareas en todas las subfunciones que necesite.

• No es necesario incluir ficheros de cabecera, ni la función main(). El código se limitará a las funciones que resuelven el problema expuesto.

• No se permite el uso de variables globales.





Respuesta:

Dpto. Ing. de Sistemas y Automática. U. de Sevilla. Examen 1º Parcial. Fundamentos de Informática 1er curso Ing. Ind. 23 de enero de 2006


Las notas saldrán el día 13 de febrero de 2006 a las 21:00 Horas. Hoja 1/5

CUESTIÓN 1 (2.0 Puntos) A) (1.0 Puntos) Se desea realizar un circuito que realice la división por 3. El circuito recibe el contenido del registro A y devuelve el del registro B como el entero (incluyendo el cero) igual o inmediatamente superior a A/3. Como ejemplo véanse los siguientes cálculos.

- Si recibe A=6 devuelve B=2 - Si recibe A=5 devuelve B=2. - Si recibe A=-5 devuelve B=-1.

Suponga que el registro A sólo tiene 3 bits y representa un entero en complemento a 2. El registro B tiene 2 bits con igual representación. Se pide calcular la tabla de verdad del circuito. Si la representación de B no es posible indicarlo claramente en las casillas correspondientes mediante “--”. Calcular la función booleana SIN SIMPLIFICAR del bit b2.

B) (1.0 Puntos) Mostrar en la siguiente tabla el contenido de los registros que aparecen después de ejecutar cada una de las instrucciones del programa LS2 que se muestra en el recuadro. En la tabla podrán emplearse mnemónicos de las instrucciones pero NO ETIQUETAS. La primera fila se ha rellenado a modo de ejemplo.

P I A T 12 SAL 12 0 SAL 12

b2=

a3 a2 a1 b2 b1

0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

ORG 5 SAL INI DA: CTE 0 DB: CTE 10 DD: DRE DB P: ESP 1 UNO: CTE 1 N: CTE 20 INI: CAR DD ALM P BUC: CAR I P CAR P RES UNO ALM P RES DD SAP BUC F: ALT FIN





Se pide: Realizar un programa en LS2 para la máquina CESIUS que escriba por pantalla una matriz nmRA ×∈ en forma matricial, tal y como aparece en el ejemplo. La matriz A se supone previamente leída. Notas: - El código ASCII del carácter de control retorno de carro

(nueva línea) corresponde al número 10. - 43 == nym

Ejemplo de ejecución:

Ejecutor de programas CESIUS © Manuel R. Arahal-1999 E.S.I. Univ. Sevilla, España Abierto archivo C:\Alu\prog.ece Leido archivo ECE sin errores

Fin de la ejecución del programa CESIUS

ORG 500 SAL INI NF: CTE 3 ‘ número de filas NC: CTE 4 ‘ número de columnas MATA: ESP 12 ' matriz A K: ESP 1 ' índice filas J: ESP 1 ' índice columnas ‘ Declarar las variables y constantes que sean necesarias INI: ‘ El código de lectura de la matriz a memoria

ya está implementado aquí. … ‘ Seguir con la escritura de la matriz





A) Dada una matriz cuadrada A de orden N, se desea hacer un diagrama de flujo para calcular la suma de los elementos que componen su diagonal secundaria. (Suponga la matriz ya leída y en memoria)

B) Para la misma matriz anterior, hacer un diagrama de flujo

que determine si es simétrica respecto a la diagonal secundaria. Ejemplo, en la matriz de muestra, el elemento a14 debería ser igual al a25, y así para todos los elementos tomando como eje de simetría la diagonal secundaria.

Ejemplo:

11 12 13 14 15

21 22 23 24 25

31 32 33 34 35

41 42 43 44 45

51 52 53 54 55

a a a a aa a a a a

A a a a a aa a a a aa a a a a

⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥=⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦

i

j

q

p

diag. secundaria

Inicio módulo B

Fin módulo B

Inicio módulo A

Fin módulo A





Para hacer ciertas labores de fotoimpresión en una imprenta se hace un negativo especial de las fotos. Este negativo se les aplica a fotos en blanco y negro. Las fotos representan figuras cerradas descritas por un “mapa de bits” en blanco y negro. Dicha figura se representa con una matriz A de dimensiones m x n, cuyos elementos aij pueden valer “0” (color blanco) ó “1” (color negro). Se desarrolla un algoritmo para hacer el negativo, incluído el borde. Dicho algoritmo contiene un módulo interno denominado PUNTO INTERIOR que determina si un elemento aij está en el interior de la figura o no. Dicho módulo se subdivide en otros cuatro (ver figura abajo a la derecha), denominados ARRIBA, ABAJO, IZQUIERDA y DERECHA. Cada uno de estos módulos recorre la figura desde un elemento aijcualquiera hacia donde indica su nombre y hasta que encuentra un borde de la figura, si es que dicho borde existe (ver figura explicativa abajo a la izquierda). Cada módulo ARRIBA, ABAJO, IZQUIERDA y DERECHA,modifica el valor de la variable F. Así el primer módulo, ARRIBA, si encuentra un borde incrementa el valor de la variable F. Después el segundo módulo, ABAJO, haría lo mismo, y así sucesivamente. Si alguno de los módulos no detectase borde alguno, no se modificaría dicha variable. De este modo, si al pasar por los cuatro módulos el punto considerado está en el interior de la figura (es decir dentro de los bordes), Fdeberá valer 4.

NOTA: Para hacer los diagramas de flujo utilice únicamente las operaciones +,-, ·, /, asignación (←), comparaciones <, >, ≤, ≥, =, lógicas “y”, “o”, acceso a memoria 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.

Figura original 0 0 0 0 0 1 0 00 0 0 0 1 0 1 00 0 0 0 1 0 1 00 0 1 0 1 0 0 10 1 0 1 1 0 0 10 1 0 0 0 0 0 10 0 1 0 0 1 1 00 0 0 1 1 1 0 00 0 0 0 0 0 0 0

Figura en negativo

1 1 1 1 1 0 1 11 1 1 1 0 0 0 11 1 1 1 0 0 0 11 1 0 1 0 0 0 01 0 0 0 0 0 0 01 0 0 0 0 0 0 01 1 0 0 0 0 0 11 1 1 0 0 0 1 11 1 1 1 1 1 1 1

Se pide:

a) Realizar el diagrama de flujo del módulo ABAJOdentro del módulo PUNTO INTERIOR. Nótese que son módulos y no subprogramas. Suponga “i”, “j” ya conocidas para este apartado.

b) Realizar el diagrama de flujo que resuelve el problema al completo usando, obligatoriamente el módulo PUNTO INTERIOR. Es decir, se desea que dada una figura original (matriz A m x n, ya leida y en memoria), el algoritmo realice el negativo y lo escriba en la matriz B. Nótese que también se hace el negativo del borde de la figura.

aij

j

ARRIBA

ABAJO

IZQUIERDA

DERECHA

i

INICIO PUNTO INTERIOR

F ← 0

ARRIBA

ABAJO

IZQUIERDA

DERECHA

F=2

FIN PUNTO INTERIOR

F=3

F=1 NO

NO

NO

SI

SI

SI




INICIO ABAJO (apartado a)

FIN ABAJO (apartado a)




A Matriz m x n entera Figura original

aij Enteros Elementos “0” o “1” de la matriz A

i Entera Índice de filas j Entera Índice de columnas

F Entera Variable que describe si un punto es interior

B Matriz m x n entera

Negativo de la figura original

INICIO apartado b

FIN apartado b

Dpto. Ing. de Sistemas y Automática. U. de Sevilla. Examen Final. Fundamentos de Informática 1er curso Ing. Ind. 24 de junio de 2006


Las notas saldrán el día 6 de julio de 2006 a las 21:00 Horas. Hoja 2/4

bits

caracteres

.

.

Respuesta f)

CUESTIÓN 2 (2.5 Puntos) La unidad de control de una computadora de la marca AD (ACME DIGITAL) tiene una arquitectura idéntica a la de la computadora CESIUS, pero con registros de distinto tamaño y el siguiente juego de instrucciones:

DESCRIPCIÓN CÓDIGO DE OPERACIÓN

MODO DE DIRECCIONAMIENTO

0 E → M(D) 000 0 1 M(D) → E 001 0 2 M(D) → (A) 010 0 3 (A) → M(D) 011 0 4 P ← M(D) 100 1 5 (A) x M(D) → A 101 0 6 STOP 110 - 7 P ← (D) 111 0

D: Dirección de memoria. E: Registro de E/S. A: Registro acumulador. P: Registro puntero de instrucciones. La memoria de programa (representada en la tabla de abajo) está dividida en ROM y RAM dispuestas consecutivamente, y se direcciona a través del registro de selección mediante un bus de direcciones de 4 bits. La memoria ROM comienza en la dirección 0 y ocupa 4 bytes, y el resto de tipo RAM está vacía. La máquina opera con números positivos y negativos codificados en modo signo valor absoluto. La computadora empieza a ejecutar el programa en la dirección 0. Además los números son fraccionarios codificados en punto fijo, con el punto decimal como se aprecia en la figura a la derecha, en la que al bit de signo se le denomina s. Se pide:

a) Capacidad de la memoria. b) Valor en decimal del número almacenado en la dirección 3.

c) Mínimo valor entero negativo que es posible almacenar (en decimal). d) Realizar un programa que lea desde el teclado el valor del radio de una circunferencia, calcule de la forma

más aproximada que sea posible el área de dicha circunferencia y escriba su valor en la pantalla. Debe usar las constantes contenidas en la memoria ROM. Tenga en cuenta que no existe un programa traductor.

e) Capacidad en caracteres del programa que ha hecho incluido los datos almacenados en la memoria RAM, si es que los ha necesitado.

f) Escriba en el interior del recuadro al margen las transferencias entre registros de la instrucción con el código

de operación 100, al ser ejecutada. NOTA: Se ha tomado π ≈ 3.1416.

MEMORIA DIRECCIÓN DE MEMORIA CO MD D 0 111 1 0100 1 000 1 1001 2 000 1 1010 3 000 1 0000

s

Parte entera

Parte fraccionaria




CUESTIÓN 3 (5 Puntos) El SUDOKU (en japonés “números solos”) es un pasatiempo en el que se trata de rellenar un cuadrado de 9x9 casillas con números del 1 al 9. El cuadrado está formado a su vez por 3 sub-cuadrados de 3x3 casillas. Un SUDOKU ya resuelto es correcto si todas y cada una de sus casillas, de coordenadas (i,j), cumplen simultáneamente las siguientes condiciones:

- Condición1: El número que contiene la casilla (i,j) no se repite en la fila i, fila de la casilla (i,j).

- Condición2: El número que contiene la casilla (i,j) no se repite en la columna j, columna de la casilla (i,j).

- Condición3: El número que contiene la casilla (i,j) no se repite en la submatriz a la que pertenece la casilla (i,j).

Como ejemplo, obsérvese el SUDOKU de la Figura. La casilla de coordenadas (1,1), de valor 1, cumple las tres condiciones. Sin embargo la casilla de coordenadas (8,9), de valor 7, cumple Condición1 y Condición2 pero no cumple Condición3. Por tanto la casilla (8,9) NO es correcta.

1 2 3 4 5 6 7 8 9 4 5 6 7 8 9 1 2 3 7 8 9 1 2 3 4 5 6 2 3 4 5 6 7 8 9 1 3 4 5 6 7 8 9 1 2 5 6 7 8 9 1 2 3 4 6 7 8 9 1 2 3 4 5 8 9 1 2 3 4 5 6 7 9 1 2 3 4 5 6 7 8

Se desea realizar un algoritmo que compruebe si un SUDOKU ya resuelto es correcto o no. Supóngase que todos los números del SUDOKU han sido leídos y se encuentran en la memoria del computador. Nos referiremos con S a la matriz que contiene el SUDOKU y con Si,j al valor de la casilla (i,j) del SUDOKU. Se pide:

a) Realizar el Diagrama de Flujo de un algoritmo que compruebe si una casilla (i,j) cualquiera del SUDOKU cumple Condición3. Si cumple Condición3, el algoritmo pone la variable resultado con valor “1”. Si no la cumple, la pone con valor “0”.

b) El Diagrama de Flujo del apartado a) forma parte de un módulo llamado COMPRUEBA que comprueba si

una casilla (i,j) cualquiera es correcta, es decir si cumple las 3 condiciones. Si la casilla (i,j) es correcta, el módulo COMPRUEBA asigna un “1” a la variable correcta. En caso contrario le asigna un “0”. Supóngase que ya se ha realizado el Diagrama de Flujo del módulo COMPRUEBA, y por lo tanto puede utilizarse.

Se pide, empleando el módulo COMPRUEBA, comprobar si el SUDOKU contenido en la matriz S es correcto. Se escribirá por pantalla “1” si es correcto y, “0”, en caso contrario.

Nota: Las únicas operaciones aritméticas válidas son: +, -, *, /, todas operando SÓLO sobre números enteros.




inicio

fin

inicio

fin

a) b)

Dpto. Ing. de Sistemas y Automática. U. de Sevilla. Examen Final. Fundamentos de Informática 1er curso Ing. Ind. 9 de septiembre de 2006


Hoja 1/3

CUESTIÓN 1 (1.5 Puntos) A) Se desea realizar un circuito que realice la división por 1,5. El circuito recibe el contenido del registro A y devuelve el del registro B como el entero (incluyendo el cero) igual o inmediatamente inferior a A/1,5. Como ejemplo véanse los siguientes cálculos.

- Si recibe A=6 devuelve B=4 - Si recibe A=5 devuelve B=3 - Si recibe A=-5 devuelve B=-4

Suponer que A y B tienen 3 bits. Ambos representan enteros en complemento a 2. Se pide calcular la tabla de verdad del circuito. Si la representación de B no es posible, indicarlo mediante “--”.

B) Se tiene el siguiente código en LS-2 para el computador CESIUS. Se pide:

a3 a2 a1 b3 b2 b1

0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

ORG 100 CAR UNO ALM K BUC: CAR DV SUM K RES UNO ALM PUN LEE I PUN CAR K SUM UNO ALM K RES NUM SAN BUC SAC BUC ALT PUN: ESP 1 UNO: CTE 1 K: ESP 1 NUM: CTE 6 VECT: ESP 5 DV: DRE VECT FIN

B.2)¿Funcionaría el programa si se ejecuta varias veces? Justifique su respuesta.

B.1) Escribir el contenido binario de la memoria entre las direcciones 114 y 124 tras la segunda pasada del compilador. Si el contenido es indeterminado déjelo en blanco

Dir. Contenido (BINARIO)

114

115

116

117

118

119

120

121

122

123

124



Hoja 2/3

bytes

d)

bits

[ , ]

CUESTIÓN 2 (1.5 Puntos) La unidad de control de una computadora tiene una arquitectura idéntica a la de la computadora CESIUS, pero con registros de distinto tamaño y el siguiente juego de instrucciones:

DESCRIPCIÓN CÓDIGO DE OPERACIÓN

MODO DE DIRECCIONAMIENTO

0 E → M(D) 000 0 1 M(D) → E 001 0 2 M(D) → (A) 010 0 3 (A) → M(D) 011 0 4 (A) x M(D) → A 100 0 5 (A) x M(M(D)) → A 101 1 6 P ← (D) 110 0 7 STOP 111 -

D: Dirección de memoria. E: Registro de E/S. A: Registro acumulador. P: Registro puntero de instrucciones. La memoria de programa (representada en la tabla de abajo) se direcciona mediante un bus de direcciones de 4 bits. La máquina opera con números positivos y negativos codificados en modo signo valor absoluto. Además los números son fraccionarios codificados en punto fijo, con el punto decimal como se aprecia en la figura a la derecha, en la que al bit de signo se le denomina s. La computadora empieza a ejecutar el programa en la dirección 0. Se pide:

a) Capacidad de la memoria.

b) Número de bits del registro P.

c) Rango de valores de los números almacenados (en decimal).

d) Realizar el diagrama de flujo del programa que hay escrito en la memoria en el recuadro abajo a la derecha. e) ¿Escribe el programa algún resultado en la pantalla? en caso afirmativo diga cual en decimal.

NOTA: Para el direccionamiento indirecto de la memoria la dirección (D) se corresponde con los 4 bits menos significativos del número almacenado en memoria.

s

DIRECCIÓN M E M O R I A

0 110 0 0101 1 000 0 0011 2 000 1 1001 3 000 1 0000 4 000 0 1000 5 000 0 0100 6 010 0 0100 7 100 0 0010 8 101 1 0001 9 011 0 1111

10 001 0 1111 11 111 1 0110

Parte entera

Parte fraccionaria

INICIO

FIN



Hoja 3/3

CUESTIÓN 3 (2 Puntos)


A Matriz, dimensión MxN

Matriz dato del problema

N Constante Número de filas

M Constante Número de columnas

Se tiene una matriz A de dimensiones M x Ncon elementos positivos o nulos. Realice un diagrama de flujo que calcule simultáneamente:

• el valor máximo de los elementos de la matriz A, y su posición; y

• la fila que cumple con la condición de que la suma de sus elementos es la mayor de todas.

El diagrama de flujo debe resolverse de modo que ambas cálculos se realicen recorriendo una sola vez la matriz. Amplíe la tabla de objetos con todos los elementos que necesite para realizar estas operaciones.

NOTA: Para la elaboración del diagrama de flujo utilice únicamente las operaciones +,-, ·, /, asignación (←), comparaciones <, >, ≤, ≥, =, lógicas “y”, “o”, acceso a memoria con subíndices y expresiones literales en lenguaje natural. El diagrama de flujo ha de estar estructurado, ser claro y legible.

INICIO

FIN

Dpto. Ing. de Sistemas y Automática. Universidad de Sevilla. Examen 1º Parcial. Fundamentos de Informática 1er curso Ingeniería Industrial. 2 de febrero de 2007

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.


CUESTIÓN 1 (2 Puntos) Una máquina con una arquitectura de von Neumann, similar a CESIUS, posee un registro selector de posiciones de memoria S de 8 bits, el código de operación ocupa 6 bits, y el modo de direccionamiento 1 bit. Determine, respondiendo en esta página, los siguientes valores: Número de instrucciones distintas de la máquina (sin contar direccionamiento indirecto) Número total de posiciones de memoria Entero más negativo codificable en Ca2 en una palabra de memoria Número más negativo en Ca1 en el acumulador Máximo exponente (con signo) en punto flotante con 8 bits de mantisa Tamaño del enlace de datos M Tamaño de la palabra de memoria Tamaño del registro de instrucciones I Tamaño del contador de pasos de programa P Codificación en binario de la pseudoinstrucción “CTE -15” NOTA: los números se deben escribir en decimal. Se pueden expresar en potencias de 2. CUESTIÓN 2 (2 Puntos) Traducir a código de máquina, en binario, las siguientes instrucciones LS-2. Emplee sólo la tabla de la derecha. Decir qué número sale por pantalla tras la ejecución (puede expresarlo en potencias de 2). Emplee las características y tamaños de registro de la máquina CESIUS explicada en clase.

Instrucción Dirección (decimal) CO MD D

ORG 1 SAL INI NUM: CTE -8 DV: DRE NUM PUN: ESP 1 UNO: CTE 1 DOS: CTE 2 INI: CAR DV SUM UNO LCA I UNO MOD DOS RES NUM ALM PUN ESC I PUN ALT FIN

Número mostrado en la pantalla:

Códigos de Operación: CAR (0010), ALM (0001), RES (0110), MOD (1001), ESC (0011), SAL (1010), ALT (0000), LCA (1111).




CUESTIÓN 3 (3 Puntos) Realice en el recuadro adjunto el diagrama de flujo de un programa que lea desde teclado una lista de valores enteros positivos y los almacene en un vector v. La lectura por teclado finaliza cuando se introduzca un valor negativo. A continuación, el programa preguntará otros 2 números por teclado (en cualquier orden), y recorrerá el vector v, calculando el porcentaje de elementos que están entre el menor y el mayor de ambos números (incluidos los extremos). Ejemplo: Lista: 24, 30, 5, 9, 85, 19 Intervalo: 20, 5 Nºs en intervalo: 5, 9, 19. Resultado: 50%

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





Un antiguo videojuego llamado “Space Invaders” tenía como objetivo defender la Tierra de una invasión enemiga. La escena en la pantalla estaba formada por una matriz de puntos monocromos, blancos y negros. Los objetos estaban formados simplemente por un “mapa de bits” en negro sobre fondo blanco. Describiremos aquí la escena mediante una matriz A de dimensiones m x n, cuyos elementos akj pueden valer “0” (color blanco) ó “1” (color negro). Las formas de los objetos y la escena son exactamente como aparecen en la figura: las naves invasoras, la nave del jugador y los proyectiles. Los movimientos de los objetos son: las naves invasoras pueden moverse libremente, mientras que la nave del jugador sólo puede moverse en horizontal; los proyectiles de la nave del jugador salen desde el disparador y se mueven verticalmente hacia arriba; y los proyectiles de las naves invasoras se mueven en vertical hacia abajo. Teniendo en cuenta que los módulos son parte del algoritmo del videojuego, se pide:

a) Dada una posición apq de colisión entre entre el proyectil del jugador y una nave invasora, realice el diagrama de flujo de un módulo que se denomine DESTRUYE, tal que destruya la nave invasora, es decir borre por completo la nave invasora de la escena. Este módulo no debe detectar la colisión sólo destruir la nave invasora. Para facilitar la resolución tenga en cuenta que todas las naves enemigas están contenidas en submatrices de 3x3 y que están siempre separadas horizontalmente como mínimo por un hueco de 3x3 (ver figura).

b) Dada la posición akj de disparo del proyectil del jugador, realice el diagrama de flujo de un módulo que anime paso a paso el movimiento del proyectil del jugador desde que sale del disparador (ver figura) hasta que, o bien se encuentra con una nave invasora o bien llega al final de la escena sin acierto. Si hay una colisión con una nave invasora debe usar el módulo DESTRUYE del apartado anterior para destruirla proporcionándole las coordenadas correspondientes.

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.

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0

Nave del jugador

Naves invasoras

Proyectil jugador

Disparador

Posición de salida del proyectil akj (a “1” antes de salir el proyectil)

Posición apq




INICIO DESTRUYE (apartado a)

FIN DESTRUYE (apartado a)




A Matriz m x n entera Escena original

akj Enteros Elementos “0” o “1” de la matriz A

p Entera Índice de fila de la colisión del proyectil

q Entera Índice de columna de la colisión del proyectil

k Entera Índice de la fila de salida del proyectil

j Entera Índice de la columna de salida del proyectil

INICIO apartado b)

FIN apartado b)

Dpto. Ing. de Sistemas y Automática. Universidad de Sevilla. Fundamentos de Informática 1er Curso de Ing. Industrial. 14 de septiembre de 2007

APELLIDOS: NOMBRE: D.N.I.: Escriba las respuestas en los recuadros indicados. Entregue todas las hojas con su nombre y apellidos. Puede usar


Las notas saldrán el día 21 de septiembre de 2007 a las 21:00 Horas. Hoja 1/10

CUESTIÓN 1 (1.5 Puntos) Una máquina con una arquitectura similar a CESIUS posee 4096 direcciones de memoria. El código de operación ocupa 3 bits. Posee direccionamiento directo e indirecto. Además, puede almacenar números en punto flotante, ocupando 1 palabra de memoria completa. Determine, respondiendo en esta tabla, los siguientes valores: Capacidad de la memoria en kilooctetos (Kbytes) Número de instrucciones distintas de la máquina Número de salidas del decodificador de direcciones Tamaño del registro S (en bits) Tamaño de la palabra de memoria Tamaño del enlace de datos M Tamaño del registro antesala de la memoria T Tamaño del registro de instrucciones I Tamaño del contador de pasos de programa P Entero más negativo en Ca2 en una palabra de memoria Entero más positivo en Ca1 en una palabra de memoria Máximo exponente (con signo) en punto flotante con 8 bits de mantisa Codificación en binario de la directiva DRE DAT Codificación en binario de la instrucción “CAR I DAT” Codificación en binario de la pseudoinstrucción “CTE -15” Notas: Debe indicar la respuesta en decimal salvo donde se indique lo contrario. Puede expresar los valores en potencias de 2 y/o sumas donde lo necesite. Datos: Código de operación de CAR: 001. La etiqueta DAT corresponde a una línea que se codifica en la dirección 12, que a su vez contiene la directiva “CTE 10”.

Dpto. Ing. de Sistemas y Automática. Universidad de Sevilla. Fundamentos de Informática

1er Curso de Ing. Industrial. 14 de septiembre de 2007 APELLIDOS: NOMBRE: D.N.I.:

Escriba las respuestas en los recuadros indicados. Entregue todas las hojas con su nombre y apellidos. Puede usar lápiz para responder a las preguntas del examen.


CUESTIÓN 2 (1.5 puntos) Dado el programa en LS-2 de la derecha, indique en la tabla de abajo el contenido de cada registro de la máquina CESIUS tras la ejecución de sus instrucciones. Considere como dato de entrada (leído por teclado) el número 5. En la primera columna se debe anotar la dirección de memoria de la instrucción ejecutada. El contenido de los registros se debe representar en decimal. Utilice el mnemotécnico para representar el código de operación y modo de direccionamiento en caso de que el contenido del registro sea una instrucción. Suponga que al inicio de la ejecución del programa, todos los registros de la máquina tienen el valor 0.

ORG 10 SAL INI TABLA: CTE 61 CTE 40 CTE 25 CTE 70 CTE 55 CTE 44 NUM: ESP 1 DDAT: ESP 1 DTAB: DRE TABLA MSG1: CTE 68 'carácter D MSG2: CTE 72 'carácter H UNO: CTE 1 CINCU: CTE 50 INI: LEE NUM CAR NUM RES UNO SUM DTAB ALM DDAT CAR I DDAT RES CINCU SAN DEBE ESC I DDAT ECA MSG2 SAL FINAL DEBE: ESC I DDAT ECA MSG1 FINAL: ALT FIN

Dirección Instrucción P I A T S E

Dpto. Ing. de Sistemas y Automática. Universidad de Sevilla. Examen Final. Fundamentos de Informática 1er curso Ingeniería Industrial. 14 de septiembre de 2007





M Constante entera Número de filas

N Constante entera Número de columnas

A Matriz M x N entera Describe la piscina

akj Enteros Elementos “0” o “1” de la matriz A

k Entera Índice de fila

j Entera Índice de columna

p Entera Índice de la fila de salida del robot

q Entera Índice de la columna de salida del robot

t Entera Variable para el sentido de avance del robot

F Entera Variable que indica al robot el fin de limpieza

NO SE PUEDEN DEFINIR NUEVAS VARIABLES

Se ha diseñado un robot limpia piscinas llamado Cleaning-Robot (ver figura). El funcionamiento del robot es el siguiente:

1. El usuario lo arroja a la piscina en cualquier zona.

2. El robot se hunde y una vez llega al fondo calcula su posición respecto a los bordes de la piscina. Para ello el robot digitaliza la piscina mediante una matriz de puntos A de dimensiones M xN, cuyos elementos akj pueden valer “0” (zona aún sucia) ó “1” (zona limpiada). La digitalización la hace de modo que siempre deja un número par de celdas desde el mismo hacia las paredes (ver figura).

3. Una vez ha calculado su posición, por ejemplo apq, éste puede moverse sólo paralelo a las paredes de la piscina y celda a celda de la matriz (ver figura abajo).

Se desea hacer un algoritmo tal que, dada una posición cualquiera (p,q) de partida del robot, éste limpie por completo la piscina sin pasar dos veces por el mismo sitio. Para ello se pide completar en los recuadros A y B del diagrama de flujo dado, lo siguiente:

1. Recuadro A: aquí debe ir la actualización de los índices de la siguiente posición del robot en la matriz. El avance del robot debe ser celda a celda y en el sentido el indicado en la figura al margen del Recuadro (ver diagrama de flujo).

2. Recuadro B: rellenar los bloques del diagrama de flujo, sabiendo que existen dos módulos predefinidos: el primero denominado MOVER y hace que el robot se mueva celda a celda a la posición (contigua) indicada por los índices (k,j); y el segundo denominado RETROCESO que lleva al robot sin limpiar desde la posición (M,N) hasta la (1,1).

NOTAS: 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..

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Cleaning-Robot

Descripción del movimiento del Robot

Posición apq

Número par de celdas

Número par de celdasNúmero par de celdas

Número par de celdas

Dpto. Ing. de Sistemas y Automática. Universidad de Sevilla. Examen Final. Fundamentos de Informática 1er curso Ingeniería Industrial. 14 de septiembre de 2007



INICIO

FIN

F = 1

NO

k ← p, j ← qt ← 1 F ← 0

NO

j ← j + t

j = N y

k = M

akj ← 1

j = N

t ← -1k ← k + 1

SI

NO

t ← 1k ← k + 1

j = 1 SI

NO

SI

NO

SI

SI

Recuadro A

Recuadro B

Sentido de avance

xámenes 1er cuatrimestre cursos 2004/07

Documents