Question

1-Sobre tempos polinomiais, analise as afirmativas a seguir:

I. Todo problema para o qual existe um algoritmo polinomial é dito ser tratável.

II. O algoritmo quicksort não pode ser resolvido em tempo polinomial.

III. Um problema é considerado intratável caso não haja algoritmo em tempo polinomial que o resolva deterministicamente

Neste contexto, é correto o que se afirma em:
Escolha uma:
a.
I e III, apenas.

b.
I, II e III.

c.
I, apenas.

d.
II, apenas.

e.
III, apenas.

2-Um algoritmo que resolve um dado problema é polinomial se seu consumo de tempo no pior caso é limitado por uma função polinomial do tamanho das instâncias do problema. (No caso do problema da fatoração, por exemplo, o tamanho de uma instância é o número de dígitos de n, ou seja, cerca de log n.) Em outras palavras, o algoritmo é polinomial se existe um número i — o mesmo para todas as instâncias — tal que o consumo de tempo do algoritmo é ____________.

Assinale a alternativa que preenche corretamente a lacuna.
Escolha uma:
a.
θ(iN), sendo N o tamanho da instância.

b.
Ο(Ni), sendo N o tamanho da instância.

c.
Ο(N), sendo N o tamanho da instância.

d.
Ω(Ni), sendo N o tamanho da instância.

e.
Ο(iN), sendo N o tamanho da instância.

3-Sobre tempos polinomiais e exponenciais, analise as afirmativas a seguir:

I. Algoritmos de tempo polinomial são suficientemente rápidos para muitos propósitos,

II. Algoritmos de tempo exponencial raramente são úteis devido à sua alta taxa de crescimento.

III. Todos os modelos computacionais determinísticos razoáveis são polinomialmente equivalentes.

Neste contexto, é correto o que se afirma em:
Escolha uma:
a.
I e II, apenas.

b.
I, apenas.

c.
III, apenas.

d.
I, II e III.

e.
II e III, apenas.

4-

Answer 1

Resposta:

2

b) Ο(Ni), sendo N o tamanho da instância.

Explicação:

Answer 2

Resposta:

2. Ο(Ni), sendo N o tamanho da instância.

3.

I. Todo problema para o qual existe um algoritmo polinomial é dito ser tratável.

III. Um problema é considerado intratável caso não haja algoritmo em tempo polinomial que o resolva deterministicamente

Explicação:

Corrigido pelo AVA