GABARITO – ISC02
Questão 1
Programa em C. Os outros serão equivalentes:
Nota: Não inclui os #includes necessários, pois isso o compilador pode indicar os headers necessarios.
void calculeProdInterno( int n, int *v, int *u, int *resp ) {
for( int i = 0 ; i < n ; i++ )
resp[i] = v[i]*u[i];
}
int calculeModulo( n, resp ) {
int sum = 0;
for( int i = 0 ; i < n ; i++ )
sum += resp[i]*resp[i];
return (int)sqrt( sum );
}
void main( int argc, char **argv ) {
int n, *v, *u, *resp;
n = atoi( argv[1] ); // Pegue o tamanho dos vetores
v = (int *)malloc( n*sizeof( int ) );
u = (int *)malloc( n*sizeof( int ) );
resp = (int *)malloc( n*sizeof( int ) );
for( int i = 0 ; i < n ; i++ ) {
v[i] = atoi( argv[i+2] );
u[i] = atoi( argv[i+n+2] );
}
calculeProdInterno( n, v, u, resp );
int k = calculeModulo( n, resp );
for( int i = 0 ; i < n ; i++ )
printf( “resp*%d+ = %d”, i, resp*i+ );
printf( “\nValor do Modulo e' igual a %d\n”, k );
}
Questão 2
Este algoritmo começa por escolher um elemento do vetor, chamado pivot. Normalmente o pivot é o primeiro elemento do
vetor. Em cada etapa, este pivot é comparado com todos os elementos do vetor e cada elemento menor que o pivot é deslocado
para o começo do vetor. Após cada passada, todos os elementos menores se encontrarão no começo do vetor, e os elementos
maiores ficam no fim do vetor. O pivot é então trocado com o último elemento menor que este; suponha que esta seja a posição
i do vetor. Recursivamente, passamos a ordenar da posição zero até a i, e da posição i+1 até n. A recursão avança até que a
chamada tenha apenas que ordenar um elemento, que por si só, já está ordenado.
No entanto, se pegarmos o pivot sempre do primeiro elemento e o vetor já estiver ordenado em ordem crescente ou
2
decrescente, este algoritmo apresentará custo quadrático O(n ). Para evitar este custo, devemos escolher o pivot de uma
posição aleatória do vetor e deslocá-lo para a primeira posição. Desta forma o custo passa a ser O(nlogn), já que na maioria das
vezes o valor pego como pivot vai separar o vetor, em cada passo, mais ou menos ao meio.
Como exemplo, considere o vetor:
6 5 3 1 8 7 2 4 → Separando o vetor segundo o pivot “6”
6 5 3 1 2 4 8 7 → Troque o pivot com o “4” que é o ultimo numero menor
4 5 3 1 2 6 8 7 → Executa-se a separação dos subvetores “4 5 3 1 2” e “8 7”, uma vez que o número 6 já está em seu lugar.
Todos à esquerda são menores e todos à direita são maiores que ele. Seguindo este esquema de recursão, ao fim o vetor estará
organizado em ordem crescente.
Obs: No caso do vetor “8 7”, como só contém dois valores, faz-se a otimização de ordená-los diretamente.
O custo computacional pode ser visto da seguinte forma: considerando-se n elementos no vetor original, cada subdivisão o
separa em uma potência de 2, ou seja:
n
n/2 + n/2
n/4 + n/4 + n/4 + n/4
…
k
k
k
k
n/2 + n/2 + … (2 vezes) … + n/2
k
k
Perceba que n/2 = 1, o que leva a n = 2 ; ou k = log(n). Este valor equivale à altura da árvore. Como o custo para juntar cada
etapa no retorno da recursão tem custo n (o número de elementos do vetor), o que nos leva a um custo de ordenação de
O(nlogn).
Questão 3
Listas encadeadas são estruturas que permitem a alocação dinâmica de elementos que guardam dados de interesse,
sendo que esses elementos contêm, além dos dados, um ponteiro que aponta para o próximo elemento da lista.
Como exemplo mostramos abaixo uma estrutura em C que guarda um inteiro, a função principal que permite inserir
elementos diferentes de zero e, ao lado, a função de inserção na lista:
struct _elem {
int v;
struct *_elem prox;
} elem;
Void main() {
elem *primeiro = NULL;
int v = 1;
while( v != 0 ) {
scanf( “%d”, &v );
if( v != 0 ) insere( &primeiro, v );
}
Insere( elem **no, int v ) {
if( *no == NULL ) {
*no = malloc( sizeof(elem) );
(*no)->v = v;
(*no)->prox = NULL);
} eles {
insere( &(*no), v )
imprime( primeiro );
}
}
}
imprime( elem *no ) {
if( no != NULL ) {
printf( “%d “, no->v );
imprime( no->prox );
}
}
Do que jeito implementado, o custo de inserção será de O(n).
Questão 4
Esta arquitetura é dividida em três partes, a saber: nível externo, nível interno e nível conceitual, sendo esse último
um nível de interface entre os dois primeiros.
Nível Externo: é o ni´vel mais perto do usuário. Em termos de utilidade, ele pode ser um usuário ou um programa de
usuário ou um administrador, sendo que este último estará também interessado nos níveis conceitual e interno.
Um usuário terá a sua disposição uma linguagem de programação, podendo ser uma API SQL ou uma linguagem de
alto nível como Cobol, PL1, C. Sendo a linguagem de alto nível, ressaltamos que ou ela contém um subconjunto de
SQL, ou ela tem à disposição uma API que permite acessar uma sublinguagem SQL para fazer o acesso aos bancos de
dados.
Em princípio, toda sublinguagem SQL contém pelo menos duas partes bem distintas, “Data Definition Language”
(DDL), que permite a declaração de objetos para os bancos de dados, e a “Data Manipulation Language” (DML), que
permite a manipulação destes objetos.
Nível Interno: é uma camada de baixo nível, responsável por cuidar da gravação dos registros criados e salvos pelo
nível do usuário. No entanto, essa camada da arquitetura não lida diretamente com a paginação entre a memória
secundária e a memória principal. Ele define o esquema interno de representação dos registros, especifica os índices
necessários, como os registros gravados serão representados, a sequência física dos registros. Esta camada da
arquitetura é escrita em uma “data definition language” própria, que não precisa ter correlação com a DDL utilizada
pelo usuário no nível externo.
Nível Conceitual: é a camada intermediária, faz com que os dados entrados pelo usuário sejam representados em
um formato que permitirá, ao nível interno, gerenciá-los de modo adequado. Essa camada é escrita em outra “data
definition Language”. Para garantir independência entre a representação e os dados, as definições DDL neste nível
não devem ser baseadas em nenhuma consideração a respeito das estruturas dos registros a serem gravados, nem
às técnicas de acessos a esses registros.
Por fim, é importante mencionar que o nível conceitual não inclui apenas a representação intermediária dos dados
entre os níveis externo e interno, mas é responsável por importantes tarefas, tais como segurança e regras de
integridade dos dados.
Questão 5
O proposito de um sistema cliente/servidor de bancos de dados é fornecer, do lado dos aplicativos ou usuários, uma
interface de alto nível de acesso aos registros de dados. De um modo simplificado, tal arquitetura pode ser formada
por apenas duas camadas, de um lado um servidor (também chamado de “backend”) e do outro lado por vários
clientes (também chamados de “frontends”).
O Servidor é um “Data Base Manegement System” (DBMS). O DBMS é responsável por três tarefas principais: 1)
Intercepta os pedidos dos usuários e analisá-los; 2) Inspeciona o esquema externo para o usuário, gerencia o
mapeamento entre as camadas externas e conceitual, gerencia a representação conceitual, gerencia o mapeamento
entre as camadas conceitual e interna, e gerencia as definições das estruturas de armazenamento; 3) Por fim,
executa as operações necessárias sobre o banco de dados.
Os Clientes são os vários aplicativos que rodam se comunicando com o DBMS, pedindo acessos aos dados. Um
cliente pode ser também um usuário que, por via de comandos diretos, lança comandos de acessos ao servidor. Para
o servidor, não faz diferença se o pedido vem de um aplicativo ou de um usuário direto, uma vez que ambos estarão
usando o mesmo conjunto de funções de pedido de acesso aos dados.
Já os aplicativos podem ser separados em duas categorias: aplicativos implementados por usuários, normalmente
escritos em C ou Cobol, ou aplicativos fornecidos por empresas, também conhecidos como ferramentas. Essas
ferramentas podem se encaixar nas seguintes categorias: planilhas, pacotes estatísticos, ferramentas de
gerenciamento de copias, entre outas.
Se o servidor for executado em uma máquina e os clientes executarem em máquinas diferentes, essa configuração é
conhecida por processamento distribuído. As diferentes máquinas são conectadas via rede.
Entre as características de um sistema distribuído estão: 1) As respostas aos pedidos dos clientes já são feitas em
paralelos pois hoje em dia praticamente todos os computadores já são produzidos com multiprocessadores, o que
aumenta a eficiência nas respostas; 2) As máquinas que executam o DBMS podem ser montadas de modo a
melhorar ainda mais a performance do DBMS. 3) A maquina do cliente também pode ser personalizada de modo a
oferecer melhores interfaces para “query” ao DBMS e facilitar sobremaneira a utilização do lado do cliente; 4) Vários
clientes podem acessar um único servidor DBMS, diminuindo o custo de montagem de um sistema cliente/servidor.
Questão 6
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
<meta name="description" content="3rd Workshop on Applications for Multi Core Architectures" />
<meta name="keywords" content="multicore, manycore, applications" />
<script type="text/javascript" src="mdcr.js"></script>
<link rel="stylesheet" type="text/css" href="template.css" media="screen,projection" />
<link rel="stylesheet" type="text/css" href="print.css" media="print" />
<title>Concurso Cepel 2014</title>
</head>
<body>
<!-- Header -->
<center>
<tr><td colspan="2" class="header">
<br>
<h2>
<p style="font-family:times;color:#1919A0"> Ficticia S.A.<br></p>
</h2>
</td></tr>
</center>
<!-- ===================================================== -->
<table border="1" width="50%"
summary="This table gives some statistics about fruit
flies: average height and weight, and percentage
with red eyes (for both males and females).">
<caption><em>Tabela Teste Para a Prova do Cepel</em></caption>
<tr><th><center>Nome</center><td><center>Idade</center><td><center> Salário </center>
<tr><th>Rodrigo Maia Silva <td><center> 32 </center><td><center> 1.200,00 </center>
<tr><th>Regina Amaro Santos <td><center> 35 </center><td><center> 1.350,00 </center>
<tr><th>Laura Souza
<td><center> 30 </center><td><center> 1.150,00 </center>
</table>
<!-- ==================================================== -->
</body>
</html>
Questão 7
Exemplo de como criar uma tabela simples para guardar o nome, sobrenome e idade dos parentes:
Criando um database
create database familia;
Abrindo o database:
use familia;
Criando uma tabela:
create table silva ( nome
varchar(20),
sobrenome varchar(20),
idade
numeric(3), );
Ou “number” em sql.
Averiguando a tabela:
Show tables;
describe silva;
Inserindo os dados de dois parentes:
insert into silva (nome, sobrenome, idade) values ('Geraldo', 'Silva', 22 );
insert into silva (nome, sobrenome, idade) values ('Mario', 'Silva', 26 );
Listando os dados do bando de dados família:
select * from silva;
select * from silva where idade > 24;
Saindo do sql:
quit;
Questão 8
Árvores binárias de busca são estruturas que permitem o armazenamento organizado de dados. Este tipo de árvore
exige que se considere uma regra no momento da inserção de elementos. O mais usual é que cada novo elemento
seja comparado com cada elemento existente na árvore e, começando pela raiz, se o novo elemento for menor, será
inserido à esquerda do elemento atual; se for maior, será inserido à direita do elemento atual. Como exemplo
suponha a árvore abaixo:
10
6
4
12
15
20
O elemento 10 é a raiz da arvore. Se tentarmos inserir o número 8, ele será comparado com a raiz; como é menor e
existe um nó da árvore à esquerda, vamos compará-lo com este elemento a esquerda, ou seja, com o número 6. Por
ser maior, e como o 6 não tem elemento à direita, o número 8 pode ser inserido neste local, resultando em:
10
6
4
8
15
12 20
O pior caso acontece quando os valores inseridos estão em ordem crescente ou decrescente. Um conjunto de
números em ordem crescente resultaria numa árvore completamente desbalanceada, como vemos a seguir,
4
6
8
10
12
15
20
ocasionando um custo de insercao quadratico: O(n2)
Já o melhor caso, que foi mostrado no exemplo anterior, ocorre quando a inserção acompanha uma ordem em que
não há muita diferença de profundidade entre o ramo mais alto e o mais baixo da árvore. Neste caso se diz que a
árvore encontra-se balanceada.
Questão 9
Árvores rubro-negras são regidas por quatro regras que garantem seu balanceamento, ao contrário das árvores
binárias de busca comuns. Tais regras consistem em impor as seguintes restrições aos nós da árvore:
1.
2.
3.
4.
5.
Todo nó é colorido de preto ou vermelho.
A raiz da árvore é preta.
Todas as folhas da árvore são pretas.
Todo nó vermelho tem filhos pretos.
Qualquer caminho entre um nó da árvore e suas folhas descendentes, tem o mesmo número de nós negros.
Como exemplo, considere a árvore a seguir:
A argumentação sobre o balanceamento pode ser feita, de forma sucinta, pensando-se que se a partir da raiz, o
ramo esquerdo tem “k” filhos pretos, então o ramo direito poderá ter no máximo “2k” filhos vermelhos, o que
significa que esse ramo da árvore terá uma altura de no máximo o dobro da do outro ramo. Essa diferença, por ser
linear, é considerada um balanceamento em termos de custo computacional.
Questão 10
Classes são extensões dos tipos de dados abstratos “structure” que incluem, além da possibilidade de armazenar
dados em variáveis, funções que permitem que o tratamento desses dados seja feito de forma transparente para o
programador que utiliza essa classe. Essa característica traz vários benefícios. Podem ser criadas funções criadoras e
destruturas que se encarregam de inicializar e limpar qualquer alocação de memória, por exemplo.
Além disso, as funções membro das classes, como são chamadas em programação orientada a objetos, fazem com
que a manipulação dos dados de uma classe independa de o programador saber ou não o nome das variáveis. Isto
permite que um grupo que mantenha um conjunto de classes, ao manter o nome das funções membro, possa alterar
o interior das classes, sem que isso atrapalhe a reutilização de códigos e organizações externas destas classes.
Comparando com a programação procedural, na qual variáveis são criadas ao longo dos códigos, se o programador
precisa mudar o nome de uma variável, todas as funções que utilizem esta variável terão que ser alteradas por
todos os programadores que já a usaram.
Questão 11
O merge sort funciona em uma primeira etapa dividindo o vetor de n elementos ao meio; em seguida ele divide cada
subvetor ao meio, e assim por diante, até que reste apenas um elemento em cada subvetor. Quando chega nessa
etapa, por conter apenas um elemento, este subvetor está ordenado. Então começa a segunda etapa, na qual cada
dupla vizinha de subvetores é juntada de forma que, ao fim dessa fusão, os elementos estarão em ordem. Isto é feito
escolhendo-se o menor elemento entre os dois subvetores; o escolhido é transportado para um vetor auxiliar e,
repetindo-se esse procedimento para todos os elementos dos subvetores, garantimos que este subconjunto do vetor
original estará ordenado. Agora, repete-se o procedimento para todos os subvetores criados na primeira etapa.
Ao fim, o vetor original estará ordenado. Apresentamos um exemplo abaixo, no qual representamos a separação, em
cada etapa, por dois pontos:
65318724
6531:8724
6 5 : 3 1 :: 8 7 : 2 4
6 : 5 :: 3 : 1 ::: 8 : 7 :: 2 : 4
Agora que temos todos os subvetores com apenas um elemento, executamos o retorno da recursão, juntos cada
dupla de subvetores em ordem crescente:
5 6 : 1 3 :: 7 8 : 2 4
1356:2478
12345678
Pronto...
A análise da complexidade, caso algum candidato se aventure:
O custo computacional pode ser visto da seguinte forma: considerando-se n elementos no vetor original, cada
subdivisão o separa em uma potência de 2, ou seja:
n
n/2 + n/2
n/4 + n/4 + n/4 + n/4
…
n/2k + n/2k + … (2k vezes) … + n/2k
Perceba que n/2k = 1, o que leva a n = 2k ; ou k = log(n). Esse valor equivale à altura da árvore. Como o custo para
juntar cada etapa, no retorno da recursão, é n (o número de elementos do vetor), o custo de ordenação é de
O(nlogn).
Questão 12
Como exemplo de como fazer esta interação, implementamos uma simples calculadora aritimética para servir de
base para a solução:
<html>
<head>
<title>Calculadora Javascript</title>
<script language = javascript type = "text/javascript">
var plus,minus,divide,times
function initialise(){plus = document.calc.operator.options[0]
minus = document.calc.operator.options[1]
divide = document.calc.operator.options[2]
times = document.calc.operator.options[3]}
function calculate(){x = parseInt(document.calc.val1.value)
y = parseInt(document.calc.val2.value)
if(plus.selected)
document.calc.answer.value = x+y
if(minus.selected)
document.calc.answer.value = x-y
if(divide.selected)
document.calc.answer.value = x/y
if(times.selected)
document.calc.answer.value = x*y}
</script>
</head>
<body onLoad="initialise()">
<h2>Calculator</h2>
<br>
<form name="calc" action="post">
<input type=text name=val1 size=10>
<select name=operator>
<option value=plus>+
<option value=minus><option value=divide>/
<option value=times>*
</select>
<input type=text name=val2 size=10>
=
<input type=text name=answer size=10>
<input type=button value=answer onClick="calculate()">
</form>
</body>
</html>