Quyidagi masalardan qaysi biri np to‘liqlik masalalari bo‘la oladi

. Quyidagi masalardan qaysi biri NP to‘liqlik masalalari bo‘la oladi.
Grafani bo‘yash masalalari
2. Algoritmik yeffektivlikni isbotlash uchun qaysi usullar to‘g‘ridan-to‘g‘ri usulga qaraganda ko‘pincha qulayroqdir?
Axborot berish usuli
3. Darajali qator deb.
funksional qatorga
4. Quyimasalalar uchun maqbullik xususiyati (maqbul pastki tuzilishga yega):
Barcha muammoning maqbul yechimi quyimasalalarga maqbul yechimlarni o‘z ichiga oladi.
5. Agar ikki qo‘shni element noto‘g‘ri tartibda joylashib qolgan bo‘lsa, ularning o‘rnini almashtirish qaysi algoritm?
Pufakcha usulida saralash
6. Rekursiv funksiya tarkibidagi o‘z-o‘zini chaqirishlar soni nima deb ataladi?{
Rekursiya chuqurligi
7. Grafda izlashda qanday ikkita strategiya mavjud?
keng qidiruv va chuqur qidiruv
8. Xoffman jadvallaridan foydalangan holda nima aniqlanadi?
Binar satr sifatida har bir belgi uchun maqbul vakillik
9. Eng kichik kvadratlar usuli ayrim adabiyotlarda bu usul nima deb ataladi?
Kramer
10. Algoritmning ommaviylik xossasi –
har bir algoritm mazmuniga ko‘ra bir turdagi masalalarning barchasi uchun ham o‘rinli bo‘lishi
11. Tezkor saralash algoritmining murakkablik bahosi qanday?{
O(NlogN)
12. i index chap yarmida va j o‘ng yarmida joylashgan inversiya qanday nomlanadi?
Ajralgan inversiya
13. O‘rta kvadrat usuli algoritmi muallifi kim?{
Jon von Neymann
14. Quyidagi dasturda int a={2,4,6,7,4}, int k=0 va int S=0 bo‘lsa, for(int i=0;iS) {S=a[i]; k=i} ifodasida k ning qiymatini toping
3
15. Umumlashtirilgan grafik qidiruv qanday masalani yechimini topadi?
grafda qidirish
16. Quyida funksiya k=4 uchun qanday qiymat qaytaradi? int f(int k){ if(k==0) return 1; if(k==1) return 1; else return f(k-1)+f(k-2);}
3
17. Xasislik algoritmida 30,20,15 kg lik toshlar bo‘lganda 70 kg yuk oladigan yashikka eng ko‘pi bilan qancha og‘irlik joylanadi?
60
18. Rekursiv algoritmlarni qo‘llaganda samarali bo‘ladigan masalani aniqlang.
Xanoy minorasi masalasi
19. Rekursiyada yechimni olish vaqtida o‘z-o‘ziga murojaatni talab etmaydigan holatlar nima deb atatladi?{
Rekursiya bazisi
20. Rekursiya bilan eslab qolish yana nima deyiladi?{
”dangasa” dinamikasi
21. grafda buyurtma tanlash masalasi algoritmining murakkabligi qanday (berilgan massiv tartiblangan)?{
O (nlog)
22. Void join () nima qiladi?
joriy obyekti bajarilishini, usuli chaqirilgan obyekt oxirigacha to‘xtatadi
23. Polinimial masalalar bu…
Vaqt maboynida ishlovchi algoritmlar
24. Agar grafda n qirralar va m qirralar bo‘lsa, unda kenglik bo‘yicha izlash algoritmining murakkabligi qanday?
O (n * m)
25. Quyidagi algoritmik baholashlarning qaysi biri eng ko‘p vaqtda bajariladi?{
O(N^3)
26. Quyida funksiya k=5 uchun qanday qiymat qaytaradi? int f(int k) {if(k==0) return 1; if(k==1) return 1; else return f(k-1)+f(k-2);}{
5