Questões de Complexidade e Matemática

Prévia do material em texto

1. Sobre complexidade de algoritmos:
Considere um algoritmo cuja função de tempo é dada por T(n) = 3n² + 5n log n + 20. Qual das
alternativas melhor classifica a complexidade assintótica desse algoritmo? Explique como o termo
dominante influencia o comportamento do tempo de execução para valores grandes de n.
A) O(n)
B) O(n log n)
C) O(n²)
D) O(n³)
2. Teoria dos Grafos e conectividade:
Suponha um grafo não direcionado com 100 vértices e um número desconhecido de arestas.
Sabemos que o grafo possui exatamente 5 componentes conexas. Qual das alternativas descreve
corretamente a relação entre componentes, vértices e a necessidade mínima de arestas para tornar o
grafo totalmente conectado? Explique o raciocínio.
A) São necessárias 4 arestas adicionais
B) São necessárias 5 arestas adicionais
C) São necessárias 95 arestas adicionais
D) Não é possível determinar
3. Espaços vetoriais e bases:
Considere um espaço vetorial de dimensão 7. Uma base é formada por 7 vetores linearmente
independentes. Se adicionarmos um novo vetor v ao conjunto, qual é a condição para que o conjunto
ampliado continue sendo base? Discuta o conceito de dependência linear.
A) v deve ser combinação linear dos demais
B) v deve ser ortogonal a todos os vetores da base
C) v deve ser linearmente independente do conjunto existente
D) v deve ter norma 1
4. Probabilidade e variáveis aleatórias:
Considere uma variável aleatória X representando o tempo de execução de um algoritmo, medida em
segundos, modelada por uma distribuição contínua. Explique qual alternativa descreve corretamente a
interpretação de f(x), sua função densidade de probabilidade, e como ela se relaciona com a
probabilidade de X assumir um intervalo.
A) f(x) é a probabilidade de X = x
B) f(x) pode assumir valores maiores que 1
C) A integral de f(x) no domínio é 2
D) f(x) é sempre negativa
5. Álgebra booleana:
Considere a expressão booleana F(A,B,C) = A¬B + BC. Explique como aplicar as leis da álgebra
booleana para simplificar essa função. Mostre qual alternativa corresponde à forma simplificada
correta.
A) A + C
B) AB + C
C) A¬B + C
D) A + BC
6. Matrizes e transformações lineares:
Uma transformação linear T: R³ → R³ é representada por uma matriz 3×3. Explique como determinar
se T é invertível analisando essa matriz e qual das alternativas melhor descreve a condição necessária
e suficiente.
A) A soma dos elementos da matriz deve ser ≠ 0
B) O determinante da matriz deve ser ≠ 0
C) Todas as colunas devem ser ortogonais
D) A matriz deve ser simétrica
7. Análise combinatória:
Suponha que estamos analisando o número de possíveis chaves de um sistema criptográfico que usa
sequências de 10 símbolos, cada um podendo assumir 36 valores diferentes. Discuta qual alternativa
representa corretamente o total de combinações possíveis e relacione isso com o conceito de
explosão combinatória em segurança computacional.
A) 10 × 36
B) 36¹■
C) 10³■
D) 36 × 10!