ATIVIDADE AVALIATIVA

Prévia do material em texto

O êxito da vida não se mede pelo caminho que você conquistou, mas sim pelas dificuldades que 
superou no caminho. (Abraham Lincoln) 
 
 
ATIVIDADE AVALIATIVA 
 
 Teoria dos Grafos 
 
CIÊNCIA DA COMPUTAÇÃO - Período: 7° 
 
GABARITO (não rasurar) 
 
 A B C D E 
1ª questão X 
2ª questão X 
3ª questão X 
4ª questão X 
5ª questão X 
6ª questão X 
7ª questão X 
8ª questão X 
 
 
 
 
I PARTE OBJETIVA – 0.125 cada 
 
1. Analise as afirmações abaixo: 
 
I. Um grafo completo é um grafo no qual dois nós distintos quaisquer são adjacentes. 
 
 
PORQUE 
II. Um grafo completo é definido como um grafo onde todo par de vértices é ligado por uma aresta e 
pode ser denotado conforme os exemplos abaixo: 
 
 
O êxito da vida não se mede pelo caminho que você conquistou, mas sim pelas dificuldades que 
superou no caminho. (Abraham Lincoln) 
 
 
Sobre essas duas afirmativas, é correto afirmar que: 
 
a) a primeira é uma afirmativa verdadeira; e a segunda, falsa. 
b) a primeira é uma afirmativa falsa; e a segunda, verdadeira. 
c) as duas são verdadeiras, mas não estabelecem relação entre si. 
d) as duas são verdadeiras, e a segunda é uma complementação correta da primeira. 
e) as duas afirmativas são falsas. 
 
2. Um grafo consiste num conjunto de nós (ou vértices) e num conjunto de arcos (ou arestas). É correto 
afirmar que o grau de um nó é: 
 
a) o número de arcos incidentes nesse nó. 
b) um número associado ao arco, também chamado de peso. 
c) a distância entre este nó e um outro nó qualquer do grafo. 
d) a posição deste nó em relação ao nó raiz do grafo 
e) o número de pares ordenados que formam o arco. 
 
3. Com relação ao tema Estrutura de Dados - Grafos, entende-se por um "grau de um nó": 
 
a) Uma entidade, tal como "uma fruta", "uma pessoa". 
b) Uma relação que liga dois nós. 
c) Um conjunto de nós e um conjunto de arestas. 
d) O número de arestas a ele ligadas. 
e) Sequência de nós interligados que liga um nó (origem) e um outro nó (destino) 
 
4. Um grafo cujo nó de partida de um caminho coincide com o nó de chegada caracteriza um grafo: 
 
a) completo 
b) incompleto 
c) regular 
d) irregular 
e) cíclico 
 
5. Para que um sistema seja testado adequadamente, é preciso realizar uma quantidade mínima de testes. 
Para apoiar essa definição, foi criada a Complexidade Ciclomática de McCabe, com fundamentação na 
teoria dos grafos. Essa técnica define uma métrica de software que fornece uma medida quantitativa da 
complexidade lógica de um programa, apresentando um limite superior para a quantidade de casos de 
testes de software que devem ser conduzidos. 
 
A Complexidade Ciclomática pode ser calculada tanto pelo número de regiões quanto pelo número de 
arestas e nós. 
 
 
O êxito da vida não se mede pelo caminho que você conquistou, mas sim pelas dificuldades que 
superou no caminho. (Abraham Lincoln) 
 
 
 
 
Com base no grafo de fluxo acima, correspondente a um trecho de código a ser testado, a quantidade 
mínima de testes que devem ser realizados para garantir que cada caminho do código tenha sido 
percorrido em ao menos um teste é: 
 
a) 11 (onze); 
b) 4 (quatro); 
c) 6 (seis); 
d) 5 (cinco); 
e) 3 (três). 
 
6. A estrutura de dados formada por conjuntos de pontos (nós ou vértices) em um conjunto de linhas 
(arestas e arcos) que conectam vários pontos é denominada: 
 
a) lista encadeada. 
b) fila circular. 
c) grafo. 
d) árvore. 
e) pilha. 
 
7. Analise o texto atentamente: 
 
Mas, em 1890, um matemático chamado _______________provou que a demonstração de 
________________tinha um erro. No mesmo artigo, ele lamentava não ter sido capaz de obter nenhuma 
demonstração alternativa do teorema. Conseguiu, no entanto, dar mais um passo positivo; 
nomeadamente, provou o ___________________. Ele estudou também a questão do número de cores 
necessárias para colorir mapas sobre vários tipos de superfícies fechadas, para além da esfera, as 
chamadas superfícies esféricas com “asas”. Estas questões também já tinham sido abordadas 
anteriormente. Esse matemático deu uma contribuição relevante no estudo destes problemas. E, 
surpreendentemente, eles foram resolvidos antes do Problema das Quatro Cores. 
 
Texto retirado do artigo História do problema das quatro cores de Milene Maria Drumond Pimenta (2018). 
 
Assinale a alternativa em que a lacuna deve ser substituída corretamente: 
 
a) Percy Heawood | Alfred Kempe | Teorema das Cinco Cores 
b) Kenneth Appel | Percy Heawood | Teorema das Quatro Cores 
 
O êxito da vida não se mede pelo caminho que você conquistou, mas sim pelas dificuldades que 
superou no caminho. (Abraham Lincoln) 
 
 
c) Alfred Kempe| Guthrie Tait | Teorema das Cinco Cores 
d) Guthrie Tait | Alfred Kempe | Teorema das Quatro Cores 
e) Guthrie Tait | Kenneth Appel | Teorema das Quatro Cores 
 
8. Em 1847, _______________, utilizou a teoria dos grafos para fazer a análise de circuítos resistivos. 
 
 
 
 
 
Texto retirado do artigo História e Aplicação da Teoria dos Grafos.. 
 
 
Assinale a alternativa em que a lacuna deve ser substituída corretamente: 
 
a) Kenneth Appel 
b) Gustav Kirchhoff 
c) Alfred Kempe 
d) Guthrie Tait 
e) Carl Wilhelm 
 
 
 
II PARTE DISCURSIVA – 0.5 cada 
 
1. Observando o grafo ilustrado abaixo, determine a quantidade máxima de rotas que podem ser extraídas 
e o algoritmo computacional do caminho mínimo para as 03 (três) rotas mais curtas. 
 
 
 
 
 
Program Pzim ; 
 var rota1, rota2, rota3, rota4, ab, ac, ad, bz, bd, ce, de, ez: real; Begin 
 
O êxito da vida não se mede pelo caminho que você conquistou, mas sim pelas dificuldades que 
superou no caminho. (Abraham Lincoln) 
 
 
 write ('Qual é o valor da distancia entre os pontos A e B: '); read 
(ab); 
 write ('Qual é o valor da distancia entre os pontos A e C: '); 
read (ac); 
write ('Qual é o valor da distancia entre os pontos A e D: '); 
read (ad); 
 write ('Qual é o valor da distancia entre os pontos B e Z: '); 
read (bz); 
 write ('Qual é o valor da distancia entre os pontos B e D: '); 
read (bd); 
 write ('Qual é o valor da distancia entre os pontos C e E: '); 
read (ce); 
 write ('Qual é o valor da distancia entre os pontos D e E: '); 
read (de); 
 write ('Qual é o valor da distancia entre os pontos E e Z: '); 
readln (ez); rota1:=ab+bz; rota2:=ab+bd+de+ez; 
rota3:=ad+de+ez; rota4:=ac+ce+ez; 
writeln ('Mostre Rota 1: ', rota1); 
writeln ('Mostre Rota 2: ', rota2); 
writeln ('Mostre Rota 3: ', rota3); 
writeln ('Mostre Rota 4: ', rota4); 
if (rota1<rota2) and (rota1<rota3) and (rota1<rota4) then writeln ('A Rota 1 é a menor.') 
else if (rota2<rota3) and (rota2<rota4) and (rota2<rota1) then writeln ('A Rota 2 é a 
menor.') 
else if (rota3<rota4) and (rota3<rota2) and (rota3<rota1) then writeln ('A Rota 3 é a 
menor.') 
else if(rota4<rota3) and (rota4<rota2) and (rota4<rota1) then writeln ('A Rota 4 é a 
menor.') 
else if (rota1=rota2) and (rota1<rota3) and (rota1<rota4) then writeln ('As Rotas 1 e 2 
são as menores.') 
else if (rota1=rota3) and (rota1<rota2) and (rota1<rota4) then writeln('As Rotas 1 e 3 
são as menores.') 
else if (rota1=rota4) and (rota1<rota2) and (rota1<rota3) then writeln ('As Rotas 1 e 4 
são as menores.') 
else if (rota2=rota3) and (rota2<rota1) and (rota2<rota4) then writeln ('As Rotas 2 e 3 
são as menores.') 
else if (rota2=rota4) and (rota2<rota3) and (rota2<rota1) then writeln ('As Rotas 2 e 4 
são as menores.') 
else if (rota3=rota4) and (rota3<rota2) and (rota3<rota1) then writeln ('As Rotas 3 e 4 
são as menores.') ; End. 
 
 
 
2. Identifique e represente graficamente (05) cinco aplicabilidades da Teoria dos Grafos no mundo real. 
 
 
 
O êxito da vida não se mede pelo caminho que você conquistou, massim pelas dificuldades que 
superou no caminho. (Abraham Lincoln)