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

Hangi gösterim büyüme için bir üst sınırı tanımlar?

1. ABüyük Teta
2. BKüçük omega
3. CBüyük Omega
4. DBüyük O

O(n²) bir algoritma n = 1000 için 1 saniye sürüyor. n = 2000 için yaklaşık ne kadar sürer?

1. A2 saniye
2. B8 saniye
3. C1 saniye
4. D4 saniye

Alan karmaşıklığı neyi ölçer?

1. AGirdi büyüdükçe bir algoritmanın ihtiyaç duyduğu bellek miktarını
2. BProgramın derlendikten sonraki dosyasının disk alanını
3. CKod satırı sayısını
4. DBilgisayarın fiziksel boyutunu

Bir fonksiyon n yinelemeli bir döngü, ardından ayrı olarak n yinelemeli başka bir döngü çalıştırıyor. Zaman karmaşıklığı nedir?

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

Negatif olmayan kenar ağırlıklarına sahip bir grafta tek bir kaynaktan en kısa yolları hangi algoritma bulur?

1. ADerinlik öncelikli arama (DFS)
2. BDijkstra algoritması
3. CHer durumda Bellman–Ford gereklidir
4. DKruskal algoritması

Floyd–Warshall algoritması neyi ve ne kadar hızlı hesaplar?

1. AMinimum kapsayan ağacı O(E log V)'de
2. BTek bir kaynak düğümden diğer tüm düğümlere en kısa yolları O(V + E)'de
3. CTüm düğüm çiftleri arasındaki en kısa yolları O(V³)'te
4. DTopolojik sıralamayı O(V²)'de

Bir X karar probleminin NP-tam olduğunu kanıtlamak için hangi iki şey gösterilmelidir?

1. AX'in polinom algoritması olmadığı ve X'in karar verilebilir olduğu
2. BX'in NP'de olduğu ve bilinen bir NP-tam problemin polinom zamanda X'e indirgendiği
3. CX'in P'deki bir probleme indirgendiği ve X'in NP'de olduğu
4. DX'in P'de olduğu ve X'in SAT'a indirgendiği

Karar verilemez bir problem ile çözülemez (intractable) bir problem arasındaki fark nedir?

1. AKarar verilemez problemler NP'de, çözülemez problemler P'dedir
2. BÇözülemez problemler hiçbir algoritmayla çözülemez, karar verilemez olanlar ise yalnızca üstel zaman gerektirir
3. CKarar verilemez bir problemin tüm girdiler için algoritması yoktur; çözülemez bir problemin algoritması vardır ama çok yavaştır
4. DHer ikisi de problemin hiç algoritması olmadığı anlamına gelir