Font size
WorksheetsQuiz sobre Complexidade de Algoritmos Conteúdo Aula 1
Total questions: 91
Worksheet time: 8hrs 35mins
Qual dos seguintes tópicos NÃO é mencionado no conteúdo do documento?
Benchmarks
Contagem elementar de instruções
Análise assintótica
Algoritmos de ordenação
O que é abordado inicialmente no documento?
Benchmarks
Problemas e sua complexidade
Contagem elementar de instruções
Análise assintótica
Qual conceito é mencionado em relação ao desempenho do código?
Impacto das comparações e de outras operações
Estruturas de dados
Programação funcional
Algoritmos de busca
Qual notação é mencionada no documento para análise assintótica?
Notação Theta
Notação Omega
Notação Big-O
Notação Sigma
Qual é a principal diferença entre um exercício e um problema, segundo Paul Zeitz?
Um exercício requer muita reflexão e pesquisa.
Um problema é uma questão que você conhece como resolver imediatamente.
Um exercício é uma questão que você conhece como resolver imediatamente.
Um problema não requer técnicas específicas.
De acordo com Paul Zeitz, o que um problema demanda antes de encontrar a abordagem apropriada?
Pouca reflexão e pesquisa.
Muita reflexão, pesquisa e esforço.
Apenas técnicas específicas.
Resolução imediata.
Quem é o autor da citação sobre a diferença entre problemas e exercícios?
Albert Einstein
Isaac Newton
Paul Zeitz
Stephen Hawking
O que a "completude" de um algoritmo garante?
Que o algoritmo encontrará uma solução ótima.
Que o algoritmo oferece certeza de encontrar uma solução.
Que o algoritmo utilizará menos memória.
Que o algoritmo será mais rápido.
O que a "otimização" de um algoritmo busca alcançar?
Encontrar uma solução ótima para o problema.
Reduzir o tempo de execução do algoritmo.
Minimizar o custo de implementação.
Garantir a completude do algoritmo.
O que a "complexidade de tempo" de um algoritmo mede?
A quantidade de memória necessária para executar o algoritmo.
O custo da implementação e manutenção do algoritmo.
O tempo necessário para executar o algoritmo.
A certeza de encontrar uma solução para o problema.
O que a "complexidade de espaço" de um algoritmo mede?
A quantidade de memória necessária para executar o algoritmo.
O tempo necessário para executar o algoritmo.
O custo da implementação e manutenção do algoritmo.
A certeza de encontrar uma solução para o problema.
O que a "complexidade algorítmica" de um algoritmo avalia?
A quantidade de memória necessária para executar o algoritmo.
O tempo necessário para executar o algoritmo.
O custo da implementação e manutenção do algoritmo.
A certeza de encontrar uma solução para o problema.
Qual notação é frequentemente utilizada para representar a complexidade de um algoritmo?
Notação P
Notação Q
Notação O
Notação R
O que é um polinômio?
Uma função composta por coeficientes e termos
Uma função composta apenas por variáveis
Uma função composta apenas por números inteiros
Uma função composta apenas por números complexos
Qual é a forma geral de um polinômio P(x)?
P(x) = a_nx^n + a_(n-1)x^(n-1) + ... + a_2x^2 + a_1x + a_0
P(x) = a_nx^n + a_(n-1)x^(n-1) + ... + a_2x^2 + a_1
P(x) = a_nx^n + a_(n-1)x^(n-1) + ... + a_2x + a_1x + a_0
P(x) = a_nx^n + a_(n-1)x^(n-1) + ... + a_2x^2 + a_1x^2 + a_0
O que são os coeficientes de um polinômio?
Números complexos (usualmente números inteiros)
Variáveis do polinômio
Graus do polinômio
Termos independentes do polinômio
O que é a variável de um polinômio?
x
n
a_n
a_0
O que é o grau de um polinômio?
n, um número natural (inteiro positivo)
x, a variável do polinômio
a_n, o coeficiente principal
a_0, o termo independente
Qual é o grau do polinômio P₁(x) = 3x³ - 6x + 8?
2
3
4
5
Quais são os coeficientes do polinômio P₁(x) = 3x³ - 6x + 8?
3, -6 e 8
3, 6 e -8
-3, 6 e 8
-3, -6 e -8
Qual é o termo independente do polinômio P₂(x) = -4x⁵ + x³ + 2?
-4
x³
2
-2
Qual é o grau do polinômio P₂(x) = -4x⁵ + x³ + 2?
2
3
4
5
Quais são os coeficientes do polinômio P₂(x) = -4x⁵ + x³ + 2?
-4, 1 e 2
4, -1 e -2
-4, -1 e 2
4, 1 e -2
Qual é o grau do polinômio P₃(x) = x² - 5x - 7?
2
3
4
5
Quais são os coeficientes do polinômio P₃(x) = x² - 5x - 7?
1, -5 e -7
-1, 5 e 7
1, 5 e -7
-1, -5 e 7
Qual é o grau do polinômio P_4(x) = 8x^4 + 6x^3 + 3x^2 - 2x + 8?
A) 2
B) 3
C) 4
D) 5
Qual é o termo independente do polinômio P_4(x) = 8x^4 + 6x^3 + 3x^2 - 2x + 8?
A) 8
B) 6
C) 3
D) -2
Quais são os coeficientes do polinômio P_4(x) = 8x^4 + 6x^3 + 3x^2 - 2x + 8?
A) 8, 6, 3, -2, 8
B) 8, 6, 3, 2, 8
C) 8, 6, 3, -2, -8
D) 8, 6, -3, -2, 8
Por que P_5(x) = 5x^{-2} + 2x + 6 não é considerado um polinômio?
A) Porque 5 não é um número natural
B) Porque -2 não é um número natural
C) Porque 2 não é um número natural
D) Porque 6 não é um número natural
Qual é a forma geral de uma função exponencial de base a?
f(x) = ax
f(x) = a^x
f(x) = x^a
f(x) = a + x
Na função exponencial f(x) = a^x, o que representa a variável 'a'?
O expoente
A base
Uma constante
O coeficiente
Na função exponencial f(x) = a^x, o que representa a variável 'x'?
A base
O coeficiente
O expoente
Uma constante
Qual das seguintes opções NÃO pode ser a base 'a' de uma função exponencial?
5
1.2
6
1
Qual é a base da função exponencial g(x) = 1.2^x?
1.2
x
1
0.5
Qual é a função exponencial crescente representada na imagem?
y = 2^x
y = (1/2)^x
y = x^2
y = 2x
Qual é a função exponencial decrescente representada na imagem?
y = 2^x
y = (1/2)^x
y = x^2
y = 2x
Qual é o valor de y quando x = 1 na função y = 2^x?
1
2
4
1/2
Qual é o valor de y quando x = -1 na função f(x) = (1/2)^x?
1/2
1
2
4
Qual é a ferramenta gratuita mencionada para comparar o comportamento de algumas funções?
www.math-tools.com
www.mathe-fa.de/pt
www.graphs.com
www.functions.com
Qual é a notação de complexidade para um algoritmo com crescimento exponencial de base 4?
O(x^2)
O(log x)
O(4^x)
O(x)
Nos polinômios, o que acontece com o crescimento da curva quando o grau aumenta?
O crescimento da curva diminui
O crescimento da curva permanece o mesmo
O crescimento da curva aumenta
O crescimento da curva se torna logarítmico
Como se comportam as funções logarítmicas para valores grandes de x?
O valor da função cresce rapidamente
O valor da função permanece constante
O valor da função ainda será pequeno
O valor da função diminui
O que caracteriza um problema intratável?
Problemas que podem ser resolvidos com recursos limitados em situações reais mais complexas.
Problemas que podem ser resolvidos com recursos ilimitados em situações simples.
Problemas que não podem ser resolvidos com recursos limitados em situações reais mais complexas.
Problemas que podem ser resolvidos em tempo linear.
Quando um problema é considerado intratável?
Quando é resolvido em tempo linear.
Quando é resolvido em tempo polinomial.
Quando é resolvido em tempo exponencial ou pior.
Quando é resolvido em tempo constante.
Qual é um exemplo de problema intratável?
Problema com solução do tipo O(n).
Problema com solução do tipo O(log n).
Problema com solução do tipo O(n^2).
Problema com solução do tipo O(2^n).
O que caracteriza um problema tratável?
Pode ser resolvido com recursos ilimitados.
Pode ser resolvido com recursos limitados ou razoáveis.
Não pode ser resolvido com recursos limitados.
Pode ser resolvido apenas com recursos infinitos.
Quando um problema é considerado tratável?
Quando a complexidade do algoritmo é exponencial.
Quando a complexidade do algoritmo é polinomial.
Quando a complexidade do algoritmo é constante.
Quando a complexidade do algoritmo é logarítmica.
Como são classificados os problemas tratáveis?
Problemas P e Problemas NP.
Problemas P e Problemas Q.
Problemas NP e Problemas Q.
Problemas P e Problemas R.
O que caracteriza os problemas tratáveis de tipo P?
São resolvidos em tempo exponencial em uma máquina determinística.
São resolvidos em tempo polinomial em uma máquina determinística.
São resolvidos em tempo logarítmico em uma máquina determinística.
São resolvidos em tempo constante em uma máquina determinística.
O que caracteriza os problemas tratáveis de tipo NP?
São resolvidos em tempo exponencial em uma máquina não-determinística.
São resolvidos em tempo polinomial em uma máquina não-determinística.
São resolvidos em tempo logarítmico em uma máquina não-determinística.
São resolvidos em tempo constante em uma máquina não-determinística.
O que caracteriza um computador determinístico?
Pode estar em múltiplos estados ao mesmo tempo.
Pode executar múltiplos processos simultaneamente.
Só pode estar em um estado por vez.
Não possui limitações de hardware.
Qual das seguintes afirmações é verdadeira sobre computadores não determinísticos?
Eles têm limitações de hardware.
Eles só podem executar um processo de cada vez.
Eles podem executar um número infinito de processos simultaneamente.
Eles são iguais aos computadores determinísticos.
Qual é a definição de um problema determinado?
Problema que pode ter indefinido número de soluções.
Problema que não pode ter mais de uma solução.
Problema que não pode ser resolvido.
Problema que pode ser resolvido por um computador não determinístico.
Qual é a definição de um problema indeterminado?
Problema que pode ter indefinido número de soluções.
Problema que não pode ter mais de uma solução.
Problema que não pode ser resolvido.
Problema que pode ser resolvido por um computador determinístico.
Qual é a base da função exponencial mencionada na lenda do jogo de xadrez?
2
3
4
5
Quantas casas tem o tabuleiro de xadrez mencionado na lenda?
32
64
128
256
Qual é a fórmula geral para calcular a quantidade de moedas em cada casa do tabuleiro de xadrez?
2^n
3^n
4^n
5^n
O que o inventor do xadrez pediu ao rei para colocar na primeira casa do tabuleiro?
Uma moeda de prata
Uma moeda de ouro
Duas moedas de ouro
Quatro moedas de prata
Qual é o valor de 2^30 calculado na calculadora do Windows?
1.073.741.824
1.000.000.000
2.147.483.648
536.870.912
Quantas pessoas saberão o "segredo" depois de uma semana?
3^6
3^5
3^7
3^4
Como é representada a difusão do "boato" na imagem?
Como uma função linear
Como uma função quadrática
Como uma função exponencial
Como uma função logarítmica
Quantas pessoas conhecerão o boato em uma semana, de acordo com a imagem?
3.280
2.380
1.280
4.280
Qual é a soma das potências de 3 apresentada na imagem?
3^0 + 3^1 + 3^2 + ... + 3^6
3^0 + 3^1 + 3^2 + ... + 3^7
3^1 + 3^2 + 3^3 + ... + 3^7
3^0 + 3^1 + 3^2 + ... + 3^8
Qual é a função exponencial usada para descrever a difusão do "boato"?
f(n) = 2^n
f(n) = 3^n
f(n) = n^3
f(n) = n^2
Quantas pessoas conhecerão o segredo no dia 30, segundo a função exponencial dada?
205.891.132.094.649
305.891.132.094.649
105.891.132.094.649
405.891.132.094.649
Qual é a quantidade de dias considerada para a propagação do boato no exemplo dado?
20 dias
25 dias
30 dias
35 dias
Qual é o tempo de execução para a função de custo n^3 quando n = 40?
10^-3 s
8.10^-3 s
27.10^-3 s
64.10^-3 s
Para n = 50, qual é o tempo de execução da função de custo n^5?
0,1 s
3,2 s
24,3 s
5,2 min
Qual é o tempo de execução para a função de custo 2^n quando n = 20?
10^-3 s
1 s
17,9 min
12,7 dias
Para n = 10, qual é o tempo de execução da função de custo 3^n?
59.10^-3 s
58 min
6,5 anos
3855 s
Qual é o tempo de execução para a função de custo n^2 quando n = 60?
10^-4 s
4.10^-4 s
25.10^-4 s
36.10^-4 s
Para n = 30, qual é o tempo de execução da função de custo n?
10^-5 s
2.10^-5 s
3.10^-5 s
4.10^-5 s
Qual é o tempo de execução para a função de custo n^5 quando n = 60?
0,1 s
3,2 s
24,3 s
13 min
Para n = 50, qual é o tempo de execução da função de custo 3^n?
59.10^-3 s
58 min
108 s
10^13 s
Qual é a eficiência do algoritmo mencionado no texto?
O(1)
O(n)
O(n^2)
O(log n)
Qual é o método de ordenação mencionado no documento para ordenar os trabalhadores alfabeticamente?
Método da seleção
Método da inserção
Método da bolha
Método rápido
Qual é a eficiência do método bubble sort mencionado no documento?
O(n)
O(n log n)
O(n^2)
O(1)
Quem foi Leonardo Fibonacci?
Um pintor italiano
Um matemático italiano
Um cientista francês
Um filósofo grego
Qual é a sequência de Fibonacci?
1, 2, 4, 8, 16, 32, ...
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
2, 4, 6, 8, 10, 12, ...
1, 3, 6, 10, 15, 21, ...
Em que ano nasceu Leonardo Fibonacci?
1170
1200
1300
1400
Qual é a nacionalidade de Leonardo Fibonacci?
Francês
Espanhol
Italiano
Alemão
O que é a sequência de Fibonacci?
Uma sequência de números primos
Uma sequência de números pares
Uma sequência de números onde cada número é a soma dos dois anteriores
Uma sequência de números ímpares
Como é definida a sequência de Fibonacci para n=0?
fibo(n) = 1
fibo(n) = n
fibo(n) = 0
fibo(n) = n+1
Qual é a complexidade de tempo do algoritmo para calcular a sequência de Fibonacci de forma recursiva?
O(n)
O(n^2)
O(2^n)
O(log n)
Qual é a fórmula recursiva para calcular o enésimo número de Fibonacci quando n > 1?
fibo(n) = fibo(n-1) + fibo(n-2)
fibo(n) = fibo(n-1) * fibo(n-2)
fibo(n) = fibo(n-1) - fibo(n-2)
fibo(n) = fibo(n-1) / fibo(n-2)
Quais são os dois primeiros números da sequência de Fibonacci por definição?
1 e 2
0 e 1
1 e 1
0 e 2
Quais são os principais critérios que a maioria dos autores utilizam para avaliar a eficiência de um algoritmo?
Memória utilizada e tempo de execução
Número de linhas de código e tempo de desenvolvimento
Complexidade sintática e número de variáveis
Facilidade de leitura e número de comentários
Como pode ser medida a complexidade de um algoritmo e sua eficiência?
Contagem de instruções, benchmark ou estimativa matemática
Número de linhas de código e tempo de desenvolvimento
Complexidade sintática e número de variáveis
Facilidade de leitura e número de comentários
O que é um benchmark?
Um teste para avaliar ou testar algoritmos em condições de hardware semelhantes
Um método para contar o número de linhas de código
Uma técnica para melhorar a legibilidade do código
Um processo para adicionar comentários ao código
Para que são utilizados os benchmarks?
Avaliar a performance de um processador ou a eficiência de um dispositivo
Contar o número de linhas de código em um programa
Melhorar a legibilidade do código
Adicionar comentários ao código
Qual é o foco da disciplina em relação à eficiência de algoritmos?
Avaliar a eficiência de algoritmos efetuando benchmarks
Realizar uma estimativa matemática
Comparar diferentes processadores
Avaliar dispositivos móveis
