EXER_TEMAS_LOG E ALGORTIMOS

Prévia do material em texto

Exercício por
Temas
 avalie sua aprendizagem
O método de ordenação da bolha, ou Bubblesort tem como melhor caso a entrada já ordenada, que resulta em
complexidade O(n). Como seu pior caso, a entrada em ordem invertida, resultando em complexidade O(n2).
Baseado nessas duas a�rmações, podemos a�rmar que a sua complexidade de caso médio é:
ESTRUTURA DE DADOS
Lupa  
 
DGT1335_202208428215_TEMAS
Aluno: GABRIEL VIEIRA FRANCISCO Matr.: 202208428215
Disc.: ESTRUTURA DE DADOS  2023.3 EAD (G) / EX
Prezado (a) Aluno(a),
Você fará agora seu EXERCÍCIO! Lembre-se que este exercício é opcional, mas não valerá ponto para sua avaliação. O
mesmo será composto de questões de múltipla escolha.
Após responde cada questão, você terá acesso ao gabarito comentado e/ou à explicação da mesma. Aproveite para se
familiarizar com este modelo de questões que será usado na sua AV e AVS.
7390 - ALGORITMOS E A LINGUAGEM PYTHON
 
1.
O(nlog n)
O(n)
O(n2)
O(1)
O(log n)
Data Resp.: 20/10/2023 21:55:53
Explicação:
Pelas características da notação O, a única a�rmação que podemos extrair é que o caso médio é melhor ou igual
ao pior caso. Portanto, é possível a�rmar que o caso médio é O(n2), ou qualquer função assintoticamente
superior a n2, como n2log n, n3, 2n etc.. Como dentre essas a única opção disponível é O(n2) essa é a resposta
correta.
Podemos descartar O(1) e O(log n) por serem melhores que o melhor caso, o que contradiz a a�rmativa do
melhor caso.
Os casos O(n) e O(nlog n) seriam possíveis teoricamente para a complexidade média de um algoritmo qualquer
que seja O(n) no melhor caso e O(n2) no pior caso, mas não é possível a�rmar nenhuma das duas com as
informações dadas.
De fato, o caso médio do Bubblesort é O(n2).
javascript:voltar();
javascript:voltar();
javascript:voltar();
javascript:voltar();
javascript:diminui();
javascript:diminui();
javascript:aumenta();
javascript:aumenta();
Matrizes podem ser implementadas em Python utilizando a biblioteca numpy, trazendo diversas funções já
implementadas. Dentre os pares de função com sua funcionalidade a seguir, qual é o correto?
No contexto de complexidade de algoritmos, usualmente é utilizada a notação O para representar as
complexidades assintóticas analisadas. Dentre as a�rmações a seguir, a correta é:
Em Python é possível implementar um array utilizando o tipo padrão list. Essa implementação permite o uso das
seguintes funções para inserir e remover um elemento, respectivamente:
 
2.
matriz.sum() retorna a soma dos elementos da matriz.
matriz.min() retorna o valor médio da matriz.
matriz.std() retorna a variância da matriz.
matriz.mean() retorna o valor mínimo da matriz.
matriz.max() retorna o desvio padrão da matriz.
Data Resp.: 20/10/2023 21:57:20
Explicação:
Dentre os pares apresentados, o único correto é o da função sum() que é a soma dos elementos. std() e mean()
são funções estatísticas que retornam o desvio padrão e a média respectivamente. max() retorna o elemento de
maior valor e min(), por sua vez, retorna o elemento de menor valor.
 
3.
O(n) signi�ca que as operações variam em proporção logarítmica à entrada.
O(n) signi�ca que para n=50  o algoritmo executará no máximo 50 operações.
O(n2) signi�ca que as operações variam em proporção quadrática à entrada.
O(n) signi�ca que para n=50  o algoritmo realizará 50 operações no pior caso.
c -O(log n) signi�ca que para n=64  o algoritmo realizará 6 operações no pior caso.
Data Resp.: 20/10/2023 22:01:10
Explicação:
Com o uso da notação O, simpli�camos o número de operações, ignorando multiplicadores constantes do termo
dominante e todos os termos de menor complexidade. Por exemplo, 5n2+3  é O(n2), mas n2 também é O(n2).
Dessa forma, não é possível calcular exatamente o número de operações quando se usa a notação O. Apenas
podemos fazer a�rmações sobre a proporcionalidade ao tamanho da entrada n. Assim, a resposta correta é que
O(n2) é proporcional ao quadrado da entrada.
 
4.
insert, remove/destroy.
append, remove/pop.
impose, remove/destroy.
append, pop/delete.
insert, delete/pop.
Data Resp.: 20/10/2023 22:05:58
Explicação:
Em Python a função append insere um elemento ao �nal da lista. As funções "remove" e "pop" podem remover
um elemento, de maneiras diferentes. Remove tira um elemento conhecido usando o seu conteúdo, já pop
remove um elemento usando seu índice, ou seja, a sua posição na lista.
A complexidade computacional é uma abstração para facilitar a comparação de algoritmos de forma independente
do ambiente de execução e de variações na sua entrada. As complexidades podem ser representadas pelo número
de operações requeridas. Dentre as seguintes complexidades de pior caso, representadas pelo seu número de
operações, qual é a melhor? (menos operações)
Um vetor está armazenado em memória no endereço-base 24. Considerando que uma palavra em memória ocupa 1
byte, e esse vetor é constituído por elementos que ocupam 4 palavras, qual é o endereço de memória ocupado
pelos elementos de índices 2 e 50 respectivamente? .
O uso de funções recursivas pode facilitar a implementação de diversos algoritmos. Toda recursão depende de dois
elementos: o caso base e o passo recursivo. Dentre as opções a seguir, a que apresenta um passo recursivo é:
 
5.
nlog n + 500
(nlog n)/2
100n + 5log n
2n
2n2
Data Resp.: 20/10/2023 22:07:18
Explicação:
O conceito de complexidade é assintótico, ou seja, o que importa é quando o tamanho da entrada n cresce
arbitrariamente. Por isso, os termos dominantes de cada resposta são os únicos relevantes. 500n é
assintoticamente menor que n2, por exemplo, pois para n acima de 500 o quadrado de n será maior que 500n.
Dessa forma podemos ordenar em forma crescente de complexidade os termos dominantes das respostas: n,
nlog n, n2, 2n. O menor deles é n, logo a resposta correta é 100n+5log n.
 
6.
28 e 220
32 e 224
26 e 74
32 e 220
28 e 224
Data Resp.: 20/10/2023 22:21:13
Explicação:
Para calcular o endereço absoluto em memória você deve utilizar a fórmula A=B+t*i . No caso B é o endereço
base (24), t é o tamanho de cada elemento (4) e i é o índice do elemento (2 e 50). Aplicando a fórmula temos
32=24+2*4  e 224=24+50*4
 
7.
fat(n)=n*fat(n-1)
fat(1)=1
par(n)=par(n)
�b(n)=n-1 + n-2
f(n)=g(n-1)
Data Resp.: 20/10/2023 22:22:32
Ao usar a biblioteca numpy para criar arrays, existem diversas facilidades que um programador pode utilizar, como
funções especí�cas para somar todos os elementos, encontrar valores mínimo e máximo dos elementos, entre
outros.
Entretanto uma desvantagem de usar array da biblioteca numpy é:
O método de ordenação da bolha, ou Bubblesort (BS) tem complexidade de pior caso O(n2) e melhor caso O(n).
Suponha que exista um algoritmo de ordenação MS que tem complexidade de melhor caso O(nlog n) e de pior caso
O(nlog n). Podemos a�rmar que:
Explicação:
O passo recursivo é o elemento que faz o cálculo da função recursiva mover-se em direção ao resultado. Deve
envolver a chamada da própria função com um valor diferente de entrada. Isso só acontece na resposta correta:
fat(n)=n*fat(n-1) , passo recursivo da função de cálculo de fatorial.
fat(1)=1  é o caso base dessa mesma função. par(n)=par(n)  é uma tautologia, e não uma recursão. As demais
respostas são funções que não chamam a si mesmas, não podendo ser passos recursivos.
 
8.
Diminuição no tempo de programação.
Não é possível adicionar novos elementos ao array.
Não é possível remover elementos do array.
Os índices passam a ser contados a partir de 1.
Todos os elementos devem ter o mesmo tamanho.
Data Resp.: 20/10/2023 22:11:11
Explicação:
A desvantagem é que os elementos do array devem ocupar o mesmo espaço de memória, então devem ser de
mesmo tamanho. Isso não permite que você crie arrays com elementos de tamanho assimétricos. Os índices
continuam sendo contados a partir de 0 e as operações de inserção e remoção continuam sendo possíveis. A
diminuição no tempo de programação é uma vantagem.
 
9.
Para um grande conjunto de entradas variadasde tamanho grande, BS executará em menos tempo que MS,
em média.
Para uma única entrada de tamanho grande, MS executará em menos tempo que BS.
Para um grande conjunto de entradas variadas de tamanho grande, MS executará em menos tempo que BS,
em média.
MS e BS são igualmente e�cientes em ordenar elementos, independente da entrada ou seu tamanho.
Para uma única entrada de tamanho grande, BS executará em menos tempo que MS.
Data Resp.: 20/10/2023 22:22:59
Explicação:
Pela natureza do tratamento de complexidade de algoritmos e o uso da notação O, a única a�rmativa verdadeira
é a de que em média, com um grande número de entradas distintas e de tamanho grande, MS executará mais
rápido que BS pois sua complexidade assintótica O(nlogn) é melhor que a de BS O(n2).
A a�rmação inversa está errada pelo mesmo argumento, O(nlogn) é melhor que O(n2).
As a�rmações que tratam de uma única entrada são falsas, pois você sempre pode escolher uma entrada que
seja de melhor caso para um dos algoritmos e seja ruim para o outro.
Por �m, a a�rmação de que ambos são igualmente e�cientes é desmentida pelo pior caso.
 
Dada a seguinte matriz M, inicializada com o código:
M=[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]
O código em Python para imprimir cada elemento da coluna iniciada pelo elemento 3 é:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
10.
for linha in M:
            print(linha)
for linha in M:
            print(linha[2])
for coluna in M:
            print(coluna)
for linha in M:
            print(linha[3])
print(M[2])
Data Resp.: 20/10/2023 22:13:33
Explicação:
O laço deve percorrer uma coluna, iterando linha a linha e extraindo dela o seu terceiro elemento, ou seja
linha[2]. A resposta correta itera pelas linhas e imprime o elemento  [2] de cada uma.
Dentre as respostas erradas, apenas escrever ¿print(linha)¿ imprimirá cada linha como um todo, resultando na
impressão de toda a matriz, linha a linha.
A resposta "print(coluna)" terá o mesmo resultado pois para o código linha e coluna são apenas nomes
escolhidos pelo programador. Poderia ser i, aux ou qualquer outra variável escolhida.
Já "print(linha[3])" está com o índice errado, imprimindo os elementos da coluna iniciada por 4. E ¿print(M[2])¿
imprime toda a linha iniciada por 9.
    Não Respondida      Não Gravada     Gravada
Exercício por Temas inciado em 20/10/2023 21:54:58.