Grile AA
Algorithm Complexity Challenge
Test your knowledge on algorithm complexity, computational theory, and NP-hard problems with this engaging quiz! Dive into topics like approximation algorithms, complexity classifications, and recursion.
Features of the quiz:
- 30 challenging questions
- Multiple-choice format
- Instant feedback on correct answers
Pentru a arata ca o problema este NP-dura se poate folosi definitia conceptului de problema NP-dura sau o alta metoda. Dintre problemele urmatoare, conform cursului, pentru care se foloseste definitia conceptului de problema NP-dura pentru a arata ca este NP-dura?
K-acoperire
SAT
K-Ciclica
Q-Sume
Un algoritm se numeste de aproximare daca:
Este determinist cu complexitate temporala polinomiala
Este determinist
Este determinist cu complexitate temporala polinomiala si calculeaza o solutie aproximativa a problemei
Este determinist cu complexitate temporala polinomiala si calculeaza o solutie aproximativa a problemei cu un grad de calitate garantat in raport cu optimul
Consideram functia: f( n ) = n*n + 2*n +1. Care dintre urmatoarele afirmatii este falsa?
F( n ) = Theta( n*n )
F( n ) = O( n*n )
F( n ) = O( n*n*n )
F( n ) = o( n*n )
O( n )
O( 1 )
O( n*n*n )
O( n*n )
Este demonstrat ca:
P = NP
P diferit de NP
NP inclus in P
P inclus in NP
O (lg n)
O(n)
O(1)
O(n*n)
Consideram problema Q: "Fie n numar natural. Are n exact 6 divizori numere naturale?". Problema Q este:
Nedecidabila
Semidecidabila
Celelalte 3 raspunsuri sunt incorecte
Decidabila
Consideram tipul TList ( liste cu elemente de tip T ). Care dintre urmatorii constructori nu este constructor intern?
F4 : TList -> TList
F2 : T x T -> TList
F3 : T x T x TList -> TList
F1 : T x TList -> TList
O problema Q din Dec este in clasa NP daca:
Exista un algoritm nedeterminist cu complexitate temporala polinomiala care rezolva problema Q
Exista un algoritm nedeterminist cu complexitate temporala suprapolinomiala care rezolva problema Q
Exista un algoritm determinist care rezolva problema Q
Exista un algoritm nedeterminist care rezolva problema Q
Care este costul ( timp de executie ) operatiei a = b + c +1 daca folosim metrica unitara si omogena?
2
C, unde c este o constanta
1
3
T( n ) = 2 * T( n/2 ) + Theta( n )
T( n ) = 2 * T( n/2 ) + Theta( 1 )
T( n ) = T( n/2 ) + Theta( n )
T( n ) = T( n/2 ) + Theta( 1 )
Un algoritm se numeste partial corect daca:
Pentru orice intrare corecta a algoritmului iesirea algoritmului este corecta
Pentru orice intrare corecta algoritmul se termina
Este total corect si pentru orice intrare corecta algoritmul se termina
Pentru orice intrare corecta a algoritmului pentru care algoritmul se termina iesirea algoritmului este corecta
Θ(2*n)
Θ(n^2 )
Θ(n ^ n)
Celelalte 3 răspunsuri sunt incorecte
F(n) = Ω(n ^ 7 )
F(n) = Θ(n ^ 6 )
F(n) = O(n ^ 4)
Celelalte 3 răspunsuri sunt incorecte
Se considera recurenta de complexitate : T(n) = 7 * T(n/5) + Θ(n), T(1) = Θ(1). Solutia acestei recurente este :
Θ(n)
Θ(n ^ n ^ log n)
Θ(n ^ n)
Celelalte 3 răspunsuri sunt incorecte
A) {f3,f5}
{f2,f5}
{f2}
Celelate 3 raspunsuri sunt incorecte
Θ(log n)
Θ(n * log n)
Θ(n ^ 2 * log n)
Celelalte 3 răspunsuri sunt incorecte
Se ştie cu siguranţă (este demonstrat) că:
NP este inclusă în P
NPC este inclusă în P
P = NP
Celelalte 3 răspunsuri sunt incorecte
O(m)
O(1)
O(n)
Celelalte 3 raspunsuri sunt incorecte
Se consideră două grafuri neorientate G1 cu m noduri şi G2 cu n noduri. Câte noduri are graful compus G2[G1]:
N ^ m
M ^ n
2 * m * n
Celelalte 3 raspunsuri sunt incorecte
Notăm cu N mulţimea numerelor naturale. Care dintre următoarele afirmaţii este demonstrată ca fiind adevărată?
Hom(N,N) = Fr
Hom(N,N) – F r ≠ mulţimea vidă
F r – Hom(N,N) ≠ mulţimea vidă
Celelalte 3 răspunsuri sunt incorecte
Multimea P I,j este:
Infinit - numarabila
Infinit - nenumarabila
Finita
Celelate 3 raspunsuri sunt incorecte
Θ(2*n)
Θ(n^2)
Θ(n^n)
Celelalte 3 răspunsuri sunt incorecte
Se consideră funcţia de complexitate f(n) = 2*n^6+5*n^3 . Care dintre următoarele afirmaţii este adevărată?
F(n) = Ω(n^7 )
F(n) = Θ(n^6 )
F(n) = O(n^4 )
Celelalte 3 răspunsuri sunt incorecte
{f3, f5}
{f2, f5}
{f2}
Celelalte 3 răspunsuri sunt incorecte
Θ(log n)
Θ(n * log n)
Θ(n^2 * log n)
Celelalte 3 răspunsuri sunt incorecte
Se ştie cu siguranţă (este demonstrat) că:
NP este inclusă în P
NPC este inclusă în P
P = NP
Celelalte 3 răspunsuri sunt incorecte
O(m)
O(1)
O(n)
Celelalte 3 răspunsuri sunt incorecte
Se consideră două grafuri neorientate G1 cu m noduri şi G2 cu n noduri. Câte noduri are graful compus G2[G1]:
N^m
M^n
2*m*n
Celelalte 3 răspunsuri sunt incorecte
Notăm cu N mulţimea numerelor naturale. Care dintre următoarele afirmaţii este demonstrată ca fiind adevărată?
Hom(N,N) = Fr
Hom(N,N) – Fr ≠ mulţimea vidă
Fr – Hom(N,N) ≠ mulţimea vidă
Celelalte 3 răspunsuri sunt incorecte
Θ(m*n)
Θ(m+n)
Θ(m^n )
Celelalte 3 răspunsuri sunt incorecte
Se consideră funcţia de complexitate f(n) = 2*n5+3*n2 . Care dintre următoarele afirmaţii este adevărată?
F(n) = Ω(n^6 )
F(n) = Θ(n^2 )
F(n) = O(n^5 )
Celelalte 3 răspunsuri sunt incorecte
Se consideră recurenţa de complexitate: T(n) = 3*T(n/7) + Θ(n), T(1) = Θ(1) Soluţia acestei recurenţe este:
Θ(n)
Θ(n^2 * log n)
Θ(n^2 )
Celelalte 3 răspunsuri sunt incorecte
{f3, f5}
{f2, f4}
{f2}
Celelalte 3 răspunsuri sunt incorecte
Θ(log n)
Θ(n * log n)
Θ(n^2 * log n)
Celelalte 3 răspunsuri sunt incorecte
Se ştie cu siguranţă (este demonstrat) că:
P = NP
NP este inclusă în P
NPC este inclusă în P
Celelalte 3 răspunsuri sunt incorecte
M
N
M*n
Celelalte 3 răspunsuri sunt incorecte
Se consideră două grafuri neorientate G1 cu n1 noduri şi G2 cu 2*n1 noduri. Câte noduri are graful compus G1[G2]:
N1
4*n1
2*n1
Celelalte 3 răspunsuri sunt incorecte
Mulţimea Fr este:
� - numărabilă
� - nenumărabilă
Finită
Celelalte 3 răspunsuri sunt incorecte
Se consideră funcţia de complexitate f(n) = 2*n3+4*n. Care dintre următoarele afirmaţii este adevărată?
F(n) = Ω(n^4)
F(n) = Θ(n^2)
F(n) = O(n^2)
Celelalte 3 răspunsuri sunt incorecte
{f3, f5}
{f1, f2, f5}
{f1}
Celelalte 3 răspunsuri sunt incorecte
Θ(log n)
Θ(n * log n)
Θ(n2 * log n)
Celelalte 3 răspunsuri sunt incorecte
Se ştie cu siguranţă (este demonstrat) că:
P este inclusă în NP
NP este inclusă în P
NPC este inclusă în P
Celelalte 3 răspunsuri sunt incorecte
M
N
M+n
Celelalte 3 răspunsuri sunt incorecte
Notăm cu N mulţimea numerelor naturale. Mulţimea Hom(N, N) este:
� - numărabilă
� - nenumărabilă
Finită
Celelalte 3 răspunsuri sunt incorecte
Se consideră recurenţa de complexitate: T(n) = 3*T(n/4) + Θ(n^2), T(1) = Θ(1). Soluţia acestei recurenţe este:
Θ(log n)
Θ(n * log n)
Θ(n^2)
Celelalte 3 răspunsuri sunt incorecte
{"name":"Grile AA", "url":"https://www.quiz-maker.com/QPREVIEW","txt":"Test your knowledge on algorithm complexity, computational theory, and NP-hard problems with this engaging quiz! Dive into topics like approximation algorithms, complexity classifications, and recursion.Features of the quiz:30 challenging questionsMultiple-choice formatInstant feedback on correct answers","img":"https:/images/course8.png"}