Atividade Avaliativa 1, 2, 3 e 4

Prévia do material em texto

Nome: Alan Di Masi Rodrigues – RA: 1422118803 – CPF: 385490218-22
Atividade 1
Assinale a alternativa que representa o número de arestas de um grafo com vértices de graus 5; 2; 2; 2; 2; 1.
1. 7 correto
2. 6
3. 9
4. 5
5. 8
Assinale a alternativa com o número de vértices de um grafo regular de grau 4 com 10 arestas.
1. 4
2. 7
3. 6
4. 5 correto
5. 8
Analise as questões abaixo, sobre o problema das pontes de Königsberg e assinale a alternativa correta.
a) O problema tem solução?
b) Qual o teorema que se reporta a esse problema?
c) O que teria de ser alterado no cenário de Königsberg para resolver esse problema.
1. a) não tem solução
b) é o Teorema de Euler que diz que um grafo conexo é euleriano se e somente se todo vértice tem grau par, ou dois vértices de grau impar e os demais pares.
c) Não há como transformar este problema em um problema soluvel
 
2. a) há solução
b) é o Teorema de Euler que diz que um grafo conexo é euleriano se e somente se todo vértice tem grau par, ou dois vértices de grau impar e os demais pares.
c) Teriam que ser ou derrubadas algumas pontes ou serem construído novas. Por exemplo, poderiam ser derrubadas uma de cada ponte dupla e a entre as duas ilhas. Outra solução seria ligar a segunda ilha também com duas pontes com cada margem.
3. a) não tem solução
b) é o Teorema de Euler que diz que um grafo não conexo é euleriano se e somente se todo vértice tem grau par, ou dois vértices de grau impar e os demais pares.
c) Teriam que ser ou derrubadas algumas pontes ou serem construído novas. Por exemplo, poderiam ser derrubadas uma de cada ponte dupla e a entre as duas ilhas. Outra solução seria ligar a segunda ilha também com duas pontes com cada margem.
4. a) não tem solução
b) é o Teorema de Euler que diz que um grafo conexo é euleriano se e somente se todo vértice tem grau par, ou dois vértices de grau impar e os demais pares.
c) Teriam que ser derrubadas algumas pontes ou serem construído novas. Por exemplo, poderiam ser derrubadas uma de cada ponte dupla e a entre as duas ilhas. Outra solução seria ligar a segunda ilha também com duas pontes com cada margem. correto
Assinale a alternativa que representa a definição de grafo.
 
1. Grafo é uma tripla, G(N, A, g) onde N é um conjunto de vértices, A é um conjunto de arestas e g é uma função que associa dada aresta a um par de vértices (x,y) que representam os extremos dessa aresta. correto
2. Grafo é uma tripla, G(N, A, g) onde N é um conjunto de arestas, A é um conjunto de vértices e g é uma função que associa dada aresta a um par de vértices (x,y) que representam os extremos dessa aresta.
 
3. Grafo é uma tripla, G(N, A, g) onde N é um conjunto de vértices, A é um conjunto de arestas e g é uma função composta que restringe uma dada aresta a um par de vértices (x,y) que representam os extremos dessa aresta.
4. Grafo é uma tripla, G(N, A, g) onde N é um subconjunto de A e N tem contido os vértices, sendo que A é um subconjunto de N contendo as arestas e g é uma função que associa dada aresta a um par de vértices (x,y) que representam os extremos dessa aresta.
5. Grafo é uma tripla, G(N, A, g) onde N é um conjunto de vértices, A é um conjunto de arestas e g é uma função que restringe cada aresta a um único par de vértices (x,y) que representam os extremos dessa aresta.
Atividade Avaliativa 2
Analise as afirmações abaixo e assinale a alternativa correta
1. Existe um grafo simples com cinco vértices dos seguintes graus 2,2,3,4,4
2. Existe um grafo simples com cinco vértices dos seguintes graus 3,4,3,4,3
3. Existe um grafo simples com cinco vértices dos seguintes graus 1,2,3,4,5
4. Existe um grafo simples com cinco vértices dos seguintes graus 1,1,1,1
5. Existe um grafo simples com cinco vértices dos seguintes graus 3,3,3,3,2 Correto
Analise as afirmações abaixo e assinale a alternativa que represente um grafo regular de grau 3 com 6 vértices.
1. O grafo não é bipartido, tem oito arestas e tem um caminho Hamiltoniano
2. O grafo é bipartido, tem oito arestas e tem um caminho Euleriano
3. O grafo é bipartido, tem nove arestas e tem um caminho Hamiltoniano correto
4. O grafo não é bipartido, tem nove arestas e tem um caminho Hamiltoniano
5. O grafo é bipartido, tem nove arestas e tem um caminho Euleriano
Analise as afirmações abaixo e assinale a alternativa CORRETA.
 
I - Um grafo de graus 2,2,2,2,2,4,4,4,6, tem 14 arestas e é Euleriano mas não é Hamiltoniano.
 
II - Um grafo regular de grau 3 com 6 vértices, é bipartido, tem nove arestas e tem um caminho Hamiltoniano
 
III - Existe um grafo simples com cinco vértices, o qual têm os seguintes graus 1,2,3,4,5
 
IV - Grafo é uma tripla, G(N, A, g) onde N é um conjunto de vértices, A é um conjunto de arestas e g é uma função que associa dada aresta a um par de vértices (x,y) que representam os extremos dessa aresta.
 
V - Um grafo regular de grau 4 com 10 arestas tem 5 vértices
1. Somente as alternativas I, III e IV estão corretas
2. Somente as alternativas I, III, IV e V estão corretas
3. Somente as alternativas I, II e IV estão corretas
4. Somente as alternativas I, II, IV e V estão corretas correto
5. Somente as alternativas II, III, IV e V estão corretas
Analise as afirmações abaixo e assinale a alternativa CORRETA.
 
I - O número de arestas de um grafo com vértices de graus 5; 2; 2; 2; 2; 1 é 7
 
II - O número de arestas de um grafo com vértices de graus 5; 2; 2; 2; 2; 1 é 6
 
III - Um grafo regular de grau 4 com 10 arestas, apresenta 11 vértices.
 
IV - O problema das pontes de Königsberg não tem solução
 
V - Para se obter uma solução para o problema das pontes de Könisgsberg, é necessário derrubar algumas pontes ou serem construído novas. Por exemplo, poderiam ser derrubadas uma de cada ponte dupla e a entre as duas ilhas. Outra solução seria ligar a segunda ilha também com duas pontes com cada margem.
1. Somente as alternativas II, IV e V estão corretas 
2. Somente as alternativas III, IV e V estão corretas 
3. Somente as alternativas II, III e V estão corretas
4. Somente as alternativas II, III e IV estão corretas 
5. Somente as alternativas I, IV e V estão corretas correto
Analise os grafos em anexo e assinale a alternativa correta
1. O grafo 1 é Euleriano e Hamiltoniano O grafo 2 é Euleriano e não é Hamiltoniano O grafo 3 é Euleriano e é Hamiltoniano
2. O grafo 1 é Euleriano e Hamiltoniano O grafo 2 é Euleriano e não é Hamiltoniano O grafo 3 não é Euleriano e é Hamiltoniano. correto
3. O grafo 1 não é Euleriano e Hamiltoniano O grafo 2 é Euleriano e não é Hamiltoniano O grafo 3 não é Euleriano e é Hamiltoniano.
4. O grafo 1 é Euleriano e não é Hamiltoniano O grafo 2 é Euleriano e não é Hamiltoniano O grafo 3 não é Euleriano e é Hamiltoniano
5. O grafo 1 é Euleriano e Hamiltoniano O grafo 2 é Euleriano é Hamiltoniano O grafo 3 não é Euleriano e é Hamiltoniano
Atividade 3
Um especialista em algoritmos construiu a análise de três algoritmos, classificando-os como: Algoritmo A: O(log n); Algoritmo B: O(n2); Algoritmo C: O(n.log n). Considerando esta análise é corretor afirmar que:
1. C é o menos eficiente.
2. A é o menos eficiente.
3. B é o menos eficiente. correto
4. A não é o mais eficiente nem o menos eficiente.
5. C é o mais eficiente.
Dado um algoritmo responsável por concatenar vetores inteiros na forma ordenada, o qual recebe dois vetores ordenados de tamanho N, e tem como saída um vetor de tamanho 2N, isto é, não há elementos repetidos nos dois vetores de entrada. Dado este contexto, assinale a alternativa que representa a complexidade de tempo de melhor caso desse processo.
1. O(N), pois se precisa fazer uma cópia de cada um dos elementos originais, o que implica uma varredura completa de cada vetor de origem. correto
2. O(1), pois se precisa fazer apenas uma cópia simples de cada um dos elementos originais.
3. O(log N), pois se usa a busca binária para determinar qual será o próximo elemento copiado para o vetor de destino.
4. O(Nlog N), pois se precisa fazer uma busca de cada elemento para depoisinseri-lo no vetor de destino.
5. O(N2 ), pois, como há dois vetores, precisa-se fazer dois laços de forma aninhada (um dentro do outro), gerando uma multiplicação das quantidades de elementos.
Ao desenvolver um sistema de análise financeira, foi utilizado um algoritmo de complexidade de tempo no pior caso igual a O(N). Porém ao se refinar o sistema outro algoritmo de melhor complexidade foi identificado para solução do problema. Neste contexto assinale a alternativa que representa a complexidade do algoritmo identificado como de melhor complexidade.
1. O(n!).
2. O(log n). correto
3. O(n2).
4. O(2n).
5. O(n log n).
Para se solucionar um problema P, que tem uma entrada de tamanho N, foram apresentados cinco algoritmos com diferentes complexidades, e sabendo que cada uma das alternativas representa um algoritmo. Neste contexto e considerando a analise assintótica (Big O) assinale a alternativa que representa o algoritmo de menor complexidade.
1. 2 + 10log n correto
2. 5n + 128
3. 2n3 + 1000
4. 4n
5. 3n2 + n
Analise o algoritmo dado, quanto a sua complexidade de tempo, no pior caso, e sabendo que n corresponde ao número de elementos da variável vetor, assinale a alternativa correta.
int algoritmo( int TAM, int vetor[])
{
            int x, y, tr, troca=1;
            for( x = 0; x < TAM-1 && troca; x++ )
            {
                        troca = 0;
                        for( y = 0; y < TAM-x-1 ; y++)
                        {
                                   if( vetor[y] > vetor[y+1])
                                   {
                                               tr = vetor[y];
                                               vetor[y] = vetor[y+1];
                                               vetor[y+1]=tr;
                                               troca = 1;
                                   }
                        }
            }
            return 0;
}
1. T(n).
2. T(n log n).
3. O(n2). correto
4. O(n2 log n).
5. O(n log n).
Atividade 4
Dado o algoritmo abaixo, que tem como objetivo buscar o maior elemento de um vetor v[0...n-1]. Assinale a alternativa que representa a complexidade de tempo do mesmo.
int max( int n, int v[])
{
    int j, x = v[0];
    for (j=1; j<n; j+=1)
       if(x <v[j]) x=v[j]
    return x
}
1. O(n2)
2. (n.logn)
3. O(log n)
4. O(1)
5. O(n) correto
A notação O-Grande (Big-O notation) é denominada complexidade do algoritmo, sendo exemplos dessa notação O(n2), O(log n), O(n), (n.logn), O(1). Neste contexto, analise as afirmações abaixo que tratam da complexidade de um algoritmo, e assinale a alternativa correta.
I. É uma medida da eficiência do algoritmo quando o tamanho do conjunto de dados tende para infinito.
II. É uma medida do número de ciclos de CPU necessários para processar um dado conjunto de dados.
III. A complexidade de um algoritmo varia, se mais processadores forem usados.
IV. A complexidade de um algoritmo é menor em processadores mais rápidos.
V. É uma medida do tempo necessário para processar um dado conjunto de dados.
1. Somente a III é correta
2. Somente a V é correta
3. Somente a IV é correta
4. Somente a II é correta
5. Somente a I é correta correto
Tomando o algoritmo de busca binária, e sabendo que o mesmo é um algoritmo de desempenho ótimo para encontrar um item em:
1. um vetor ordenado correto
2. uma árvore B
3. uma lista ligada ordenada
4. um heap binário
5. uma árvore de busca binária
Dado o vetor ao lado, ordenado de forma crescente. Assinale a alternativa que represente o número de iterações necessárias para que o valor 80 seja encontrado, aplicando o algoritmo de busca binária.
 
1. 4 correto
2. 2
3. 8
4. 9
5. 3
A descrição de um programa recursivo é representada pela formula anexa. Assinale a alternativa que representa sua complexidade.
 
 
1. O(2n).
2. O(n x log n).
3. O(n2).correto
4. O(n2 x log n)
5. O(n3).