Cevaplı Algoritmalar ve karmaşıklık çalışma kâğıdı

Bir algoritmanın çalışma süresi O(n)'dir. Bu büyümeye ne ad verilir?

1. ALogaritmik
2. BKaresel
3. CDoğrusal
4. DSabit

Standart dizi tabanlı birleştirmeli sıralama ne kadar ek bellek kullanır?

1. AO(1)
2. BO(n)
3. CO(n²)
4. DO(log n)

Kaba kuvvet algoritması nedir?

1. ATüm olası aday çözümleri deneyen bir algoritma
2. BRastgele bir yanıt tahmin eden bir algoritma
3. CHer zaman özyineleme kullanan bir algoritma
4. DBirçok işlemci üzerinde çalışan bir algoritma

Bir problemin optimal alt yapıya sahip olması ne anlama gelir?

1. AProblemin tam olarak bir optimal çözümü vardır ve bu çözümü her alt problem paylaşır
2. BHer alt problem aynı boyuttadır
3. COptimal bir çözüm, alt problemlerinin optimal çözümlerinden oluşturulabilir
4. DProblem sabit zamanda çözülebilir

T(n) = 2T(n − 1) + O(1) yinelemesinin çözümü nedir?

1. AO(n)
2. BO(n²)
3. CO(2ⁿ)
4. DO(n log n)

Dinamik programlama, bir problemde hangisi olduğunda yararlıdır?

1. AÖrtüşen alt problemler ve optimal alt yapı
2. BHiç alt problem olmaması; bu yüzden tek adımda çözülebilir
3. CTek bir döngü
4. DYalnızca rastgele girdiler

NP sınıfının hangi tanımı doğrudur?

1. APolinom zamanda çözülemeyen problemler
2. BHiçbir algoritmanın çözemeyeceği problemler
3. CPolinom olmayan problemler
4. DEvet yanıtları bir sertifika verildiğinde polinom zamanda doğrulanabilen karar problemleri

Bu sağlanabilirlik problemlerinden hangisinin polinom zamanda çözülebildiği bilinmektedir?

1. ADevre sağlanabilirliği
2. BHer yan tümcenin en fazla iki literal içerdiği 2-SAT
3. CHer yan tümcenin tam olarak üç literal içerdiği 3-SAT
4. DBirleşimli normal biçimdeki formüller üzerinde genel SAT