Algoritmlarni loyihalash. Yakuniy nazorat savollari. Birinchi variant to'g'ri!


Download 0.79 Mb.
Pdf ko'rish
bet1/6
Sana05.08.2023
Hajmi0.79 Mb.
#1665399
  1   2   3   4   5   6
Bog'liq
Algoritm loyihalash@T4TUCHiK



Algoritmlarni loyihalash. Yakuniy nazorat savollari.
Birinchi variant to'g'ri!
Krustal algoritmiga ko’ra ustov(tayanch) daraxtni qidirish nimadan boshlanadi?
eng arzon qirradan
berilgan qirradan
berilgan uchdan
istalgan uchdan boshlash mumkin
“Ajrat va hukmronlik qil” tamoyiliga ko’ra amallar sonini kamaytirish mumkin bo’lgan algoritm quyidagi masalalardan qaysi biriga tadbiq qilinishi mumkin?
Sonli massiv elementlarini tartiblashtirish
Chiziqli algebraik tenglamalar sistemasini yechish
chiziqli dasturlash masalasi optimal yechimni topish
Graflarda kerakli marshrutlarni tanlash
“Ajrat va hukmronlik qil” tamoyiliga ko’ra bir qancha parallel hisoblash bloklariga ajratish mumkin bo’lgan masalani ko’rsating.
Matritsalarning ko’paytmasini hisoblash
Matritsalarni qo’shish
Vektorlarning skalyar ko’paytmasi
Aniq integralni taqribiy hisoblash
Algoritmlashda “dag’al kuch tamoyili” qanday asosda amalga oshiriladi?
Berilgan masalani imkoniyati bo’lsa ikki yoki undan ortiq mustaqil ishlanadigan qismlarga ajratish
Berilgan masalani yechish algoritmini siklik jarayonga keltirish
Berilgan masala yechimini tarmoqlanuvchi jarayonga keltirish
To’g’ri javob yo’q
”Hasis algoritmlar” ga ko’ra graf daraxtlari orasidan qandayi qidiriladi?
Qirralari narxlari eng anzoni
Berilgan uchidan chiqqanlari
Berilgan uchidan boshlangani
To’g’ri javob yo’q
Krustal algoritmiga ko’ra ustov(tayanch) daraxtni qidirish nimadan boshlanadi?
eng arzon qirradan
Berilgan qirradan
Berilgan uchdan
Istalgan uchdan boshlash mumkin
Prima algoritmiga ko’ra ustov(tayanch) daraxtni qidirish nimadan boshlanadi?
Ixtiyoriy uchidan
Berilgan uchdan
Berilgan qirradan
To’g’ri javob yo’q
Krustal algoritmiga ko’ra nima topiladi?
Berilgan graf daraxtlari orasidan eng arzoni
Berilgan graf uchun mumkin bo’lgan daraxtlar narxi
Berilgan graf uchun shajara daraxti
Shajara daraxti narxi
Prima algoritmiga ko’ra nima topiladi?
Berilgan graf daraxtlari orasidan eng arzoni
Berilgan graf uchun mumkin bo’lgan daraxtlar narxi
Berilgan graf uchun shajara daraxti
Shajara daraxti narxi
Graf qirralari narxlari matritsasiga ko’ra graf chizmasini tuzishni qanday boshlagan ma’qul?
Eng yuqori karrali uchlaridan biridan
Eng kichik karrali uchlaridan biridan
Ixtiyoriy uchidan
Ixtiyoriy qirrasidan
Graflar uchun “Kommivoyajer masalasi”da nima topiladi?
Berilgan graf uchun Gamilton sikllari orasidan harakat narxi eng arzoni
Berilgan graf uchun barcha Gamilton sikllarini
Barcha mumkin bo’lgan daraxtlar
To’g’ri javob yo’q
Quyidagi funksiyalardan qaysi biri rekursiv funksiya bo’ladi?
y=sin(sin(sin(sinx)))
y=a
0
x

+ a
1
x
n-1
+ . . . + a
n-1
x+a
n
y=e
x
sinx* sqrt(x)
y=sqrt(sin
2
x+tg
2
x)
Sonli massiv elementlarini tartiblash masalasiga “ajrat va hukmronlik qil” tamoyilini taqbiq qilsak amallar soni qanday bo’ladi?
nlog
2
n tartibida
n
2
tartibida
n
3
tartibida
n tartibida
Quyidagi funksiyalardan qaysi biri rekursiv funksiya bo’ladi?
sqrt(sqrt(sqrt(.....sqrt(x))))
sqrt(x)·sqrt(y)·srqt(z)·sqrt(w)
sin(x)·sin(y)·sin(z);
e
x
, e
y
, e
z
;
Uchlari 9ta, qirralari 13ta bo’lgan graf daraxtida nechta qirra bo’ladi?
8
9
13
12
Uchlari 8ta, qirralari 12ta bo’lgan graf daraxtida nechta qirra bo’ladi?
7
8
11
12
Uchlari 9tabo’lgan to’liq grafda nechta qirra bo’ladi?
36
72
81
18
Uchlari 9ta bo’lgan graf daraxtida nechta qirra bo’ladi?
8
36
32
16
Quyidagi algoritmlardan qaysi biri P-algoritm (polynomial)ga misol bo’la oladi?
Integrallarni taqribiy hisoblashda Simpson formulasi
Determinantni hisolash
Sistemalarni yechishda Kramer usuli
Barcha javoblar to’g’ri
Quyidagi algoritmlardan qaysi biri NP-algoritmga misol bo’la oladi?
Chiziqli algebraik tenglamalar sistemasini yechishda Kramer usuli
Ko’phad qiymatini hisoblashda Gorner sxemasi
Algebraik tenglamalarni taqribiy yechishda vatarlar usuli
Chiziqli dasturlash masalasi tayanch yechimlarini topish algoritmi
Saralashning turlarini ko’rsating?
Qat’iy usul , yaxshilangan usul;
Qat’iy usul, murakkab usul;
Yaxshilangan usul, sodda usul
Sodda usul, murakkab usul
64 ta elementdan iborat sonli massivni tartiblashtirish uchun nechta taqqoslash amalini bajarish kerak?
63
2
63·64
64
2
63+64
32 ta elementdan iborat sonli massivni tartiblashtirish uchun nechta taqqoslash amalini bajarish kerak?
31
2
31·32
32
2
32·log
2
32
64 ta elementdan iborat sonli massivni tartiblashtirishni “ajrat va hukmronlik qil” tamoyiliga ko’ra bajarsak nechta taqqoslash amalini bajarish kerak?
64·log
2
64
64·63
63
2
64
2
32 ta elementdan iborat sonli massivni tartiblashtirishni “ajrat va hukmronlik qil” tamoyiliga ko’ra bajarsak nechta taqqoslash amalini bajarish kerak?
32·log
2
32
32·31
32
2
31
2
Pufaksimon saralash algoritmi bu?
n - 1 marta massivda quyidan yuqoriga qarab yurib kalitlar jufti-jufti bilan taqqoslanadi. Agar pastki kalit qiymati yuqoridagi jufti kalitidan kichik bo'lsa, u holda ularning o'rni almashtiriladi
Bu algotirm rekursiv bo'lib, o'rtacha N*log2N ta solishtirish natijasida saralaydi.
Bu algoritm massivdagi har bir elementni qidirilayotgan element bilan birma-bir solishtirib chiqadi
Eng kichik kalitga ega element tanlanadi. Ushbu element birinchi element bilan o"rin almashinadi. 
Quiksort - tez saralash algoritmi berilgan massivni saralash uchun uni nechtaga bo'lib oladi?
2
4
3
1
P
n
(x)= a
0
x

+ a
1
x
n-1
+ . . . + a
n-1
x+a
n
ko’phadning bir nuqtadagi qiymatini hisoblash uchun Gorner sxemasi bo’yicha nechta amal bajarish kerak?
2n
n(n+3)/2
n(n+1)/2
n(n-1)/2
P
n
(x)= a
0
x

+ a
1
x
n-1
+ . . . + a
n-1
x+a
n
ko’phadning bir nuqtadagi qiymatini hisoblash uchun Gorner sxemasi bo’yicha nechta amal bajarish kerak?
n(n+3)/2
n(n+1)/2
n(n-1)/2
2n
Rekursiya deb nimaga aytiladi?
Rekursiya deb shunday konstruktsiyag aytiladiki, funktsiya o'zini o'zi chaqiradi.
Barcha element o'zidan keyingi elementga bo'glangan bo'ladi
Saralanmagan massivni taqqoslashga asoslangan holda saralovchi
Massivdagi har bir elementni qidirilayotgan element bilan birma-bir solishtirib chiqishga
Binar qidiruv algoritmi(Ikkilik qidirish algoritmi)
Ketma-ket ikkiga bo'lishga asoslanadi, ya'ni berilgan x ni massivning o'rtadagi elementi bilan solishtiradi, agar katta bo'lsa oxiri va o'rtasi orasidagi massivni oladi, agar kichkina bo'lsa boshi va o'rtasi orasidagi massivni
oladi, va har safar shu jarayon takrorlanib boradi toki x element solishtirilayotgan massivning elementga teng bo'lgunicha yoki massivning elementlari qolmaguncha.
Bu algotirm rekursiv bo'lib, o'rtacha 
n*log
2
n ta solishtirish natijasida saralaydi. 
Bu algoritm massivdagi har bir elementni qidirilayotgan element bilan birma-bir solishtirib chiqadi.
n - 1 marta massivda quyidan yuqoriga qarab yurib kalitlar jufti-jufti bilan taqqoslanadi. Agar pastki kalit qiymati yuqoridagi jufti kalitidan kichik bo'lsa, u holda ularning o'rni almashtiriladi
Uchlari 10 ta bo’lgan to’liq grafda Gamilton sikllarini necha xil usulda tuzish mumkin?
N=10!
N=10
2
N=10
3
N=10·9
Uchlari 10 ta bo’lgan to’liq grafdagi barcha Gamilton sikllari bo’yicha harakat narxlarini hisoblash uchun qancha qo’shish amalini bajarish kerak bo’ladi?
N=9·10!=32659200
N=10
2
=100
N=10!=3628800
N=10
3
=1000
"
A(n x m) matritsa elementlari orasidan eng kattasini topish jarayonini parallel ko’p prossersorli hisoblash markazida parallel hisoblash jarayoniga ajratishni qanday bajarish mumkin?
"
Matritsa qatori elementlaridan eng kattasini topish d
i
, i=1,2….,n. So’ngra d
i
lar ichidan eng kattasi topiladi turli prosessorlarda topiladi
Karrali sikli bo’lgan dastur asosida
Bajarib bo’lmaydi
To’g’ri javob yo’q
Agar masala tartibini belgilovchi n-parametr bo’lib uni yechish uchun sarflanadigan amallar soni qanday bo’lganida algoritm P-algoritm deyiladi?
Amallar soni N=P
k
(n) ko’phad bo’lib k-o’zgarmas n ga bog’liq bo’lmasa
Masala yechimi ko’phadlar orqali topilsa
Masala yechimini topish uchun amallar soni n- ning biror f(n) funksiyasi sifatida ifodalansa
To’g’ri javob yo’q
Quyidagi algoritmlardan qaysi biri NP-algoritmga misol bo’la oladi?
Faktorial (n!) ni hisoblash algoritmi
Tenglamalarni yechishning Nyuton usuli
Integrallarni taqribiy hisoblashda trapetsiyalar formulasi
Chziqli dasturlash masalasilarni yechishda simpleks usuli
Saralash samaradorligini qaysi mezonlar bo’yicha baholash mumkin?
Barcha javoblar to’g’ri
dasturni ishlab chiqishga ketgan vaqt.
saralash uchun talab qilingan operativ xotira;
saralashga ketgan vaqt;
Bo'lib tashla va hukmronlik qil algoritmlari nechta bosqichdan iborat bo'ladi va ular qanday nomlanadi?
"
3ta bosqichdan iborat 1) Bo'lib tashlash bosqichi 2) Hukumronlik bosqichi 3) Birlashtirish bosqichi
"
4ta bosqichdan iborat 1) Bo'lib tashlash bosqichi 2) Hukmronlik bosqichi 3) Bo'ysundirish bosqichi 4) Ajratish bosqichi
2ta bosqichdan iborat 1) Bo'lib tashla bosqichi 2) Bo'ysundirish bosqichi
2ta bosqichdan iborat 1) Bo'lib tashla bosqichi 2) Birlashtirish bosqichi
Faraz qilaylik, N = 0,01n2 + 10n - taqqoslashlar soni. Agar n < 1000 bo'lsa, u holda ikkinchi qo'hiluvchi katta, aks holda ya'ni, n > 1000 bo'lsa, birinchi qo'shiluvchi katta bo'ladi. Demak, kichkina n larda taqqoslashlar soni
n ga teng bo'ladi, katta n larda nimaga teng bo'ladi?
n
2
n+ 1
n
2n
Ichki va tashqi saralash nimasi bilan farq qiladi?
Ichki saralash ishga tushishdan oldin bevosita ОЗУ dan foydalanadi, tashqi saralash xotira qurilmalarini kattagina qismidan foydalanadi;
Ichki saralash ishga tushidan oldin qo’shimcha belgilangan xotiradan foydalanmaydi, yani ko’p bora elmentlarga bevosita murajat qiladi, tashqi saralash qo’shimcha massivlarni talab qiladi.
Ichki saralash ichki adresli ko’p joydan foydalanadi, tashqi saralash ko’satkichlarga murojat qiladi.
Ichki saralash ichida ko’p bora ishlaydi, tashqi saralash esa uni chegarasigacha boradi.
Alogoritmlarni vaqt bo'yicha baholash nimaga asoslanadi?
"
1. Bajarilgan amallar soniga qarab.
" "
1. Hisoblash formulalari murakkabligiga qarab.
" "
1. Algoritm dasturi hajmiga qarab.
" "
1. Oraliq va yakuniy natijalar egallagan hotira hajmiga qarab.
"
Alogoritmni hajm bo'yicha baholash nimaga asoslanadi?
Boshlang'ich, oraliq va natija o'zgaruvchilar egallagan hotira hajmiga qarab.
Hisoblash formulalari murakkabligiga qarab.
Algoritm dasturi hajmiga qarab.
Bajariladigan amallar soniga qarab.
Algoritmning universalligi qanday tushiniladi?
Berilgan turdagi har qanday masalaga tatbiq qilinishi.
Universal algoritmlar bo'lmaydi 
Har qanday masalaga tatbiq qilinishi.
Universal algoritm uchun doimo echim bo'lishi.
Tejamkor algoritmlar nima bilan farqlanadi?
Berilgan turdagi masalalarni yechish uchun eng kam amallar sarflashi bo'yicha.
Algoritmlar uchun tejamkor sifati bo'lmaydi.
Dasturning ixchamligi bo'yicha.
Xotira hajmini kam band qilishi bo'yicha.
Chiziqli algoritmlar qanday ajratiladi?
Algoritm barcha bandlari berilgan tartibda bajarilishi bilan.
Algoritmda faqat chiziqli formulalar ishlatilishi bilan.
Turli chiziqlar grafiklarini chizish bilan.
Algoritmlarda chiziqli sifati bo'lmaydi.
Tarmoqlanuvchi algoritmlar nimasi bilan farqlanadi?
Ma'lum shartlar bajarilishiga qarab algoritm biror bandini tanlash.
Algoritm biror bandini qaytadan bajarishi bo'yicha.
Algoritimda ikki yoki undan ortiq yo'nalishlar bo'yicha hisoblashlar olib borilsa.
Biror masalani turli formulalar bo'yicha yechishi bilan.
Algoritmlarning berilish usuli qanday?
Matn bo'yicha.
Barcha javoblar to'g'ri.
Dastur yordamida.
Blok-sxemalar orqali.
Sikllik algoritmlar belgisi qanday?
Algoritm ayrim bandlarining ko'p bor takrorlanishi bilan.
Algoritmda faqat takrorlanuvchi bandlar bo'lishi bilan.
Algoritmda bir xil formulalar takrorlanishi bilan.
Barcha javoblar to'g'ri.
Iteratsion sikllar qanday farqlanadi?
Takrorlanish soni ma'lum shart bajarilguncha davom etadigan sikllar.
Takrorlanish soni oldindan beriladigan sikllar.
Takrorlanish soni cheklanmagan sikllar.
To'g'ri javob berilmagan.
Qo’yilgan masalani yechilishiga olib keluvchi aniq harakatlarning chekli ketma-ketligi nima deyiladi?
Algoritm
Dastur
Masala
Funksiya
Tomonlari uzunligi a,b,c bo’lgan uchburchak yuzasini topish masalasini qaysi algoritm blok sxemasidan foydalaniladi.
tarmoqlanuvchi
takrorlanuvchi
to’g’ri chiziqli
barcha javob to’g’ri
Algoritmlar maxsus geometrik figuralar yordamida tasvirlanishi nima deyiladi?
Blok sxema
So’zli algoritm
Dastur kodi
Diagramma
Algoritmda kiruvchi ma’lumotlarning bajariladigan amallar soniga ma’lum bir qonuniyatlar asosida mos qo’yilishi nima deyiladi?
Algoritmning asimptotik baholash
Algoritm xatoligi
Algoritm samaradorligi
Dasturlashtirish
Tanlab saralash algoritmining murakkablik bahosi qanday?
O(n^2)
O(NlogN)
O(n^3)
O(n)
Quyidagi algoritmik baholashlarning qaysi biri eng kam vaqtda bajariladi?
O(N)
O(NlogN)
O(N^3)
O(N^2)
Algoritm O(N) murakkablik bilan bajarilishida 1024 s vaqt sarflasa, shu algoritm O(NlogN) murakkablik bilan qancha vaqt sarflaydi?
10240
100
1024
500
"
Algoritm O(N) murakkablik bilan bajarilishida 256 s vaqt sarflasa, shu algoritm O(NlogN) murakkablik bilan qancha vaqt sarflaydi?
"
2048
100
1024
500
Algoritm O(NlogN) murakkablik bilan bajarilishida 160 s vaqt sarflasa, shu algoritm O(N^2) murakkablik bilan qancha vaqt sarflaydi?
1024
100
10240
500
Algebraik va transendeng tenglamalarni taqribiy yechishda oraliqlarni aniqlash.
Agar biror [a;b]oraliqda y=f(x) funktsiya uzluksiz bo’lib, f(a)*f(b)<0 bo’lsa, shu oraliqda f(x)=0 tenglamaning kamida bitta ildizi mavjud bo’ladi.
f(x)=0 tenglama berilgan biror [a;b] oraliqda f(a)*f(b)<0 bo’lsa, tenglamaning oraliqda bir necha yechimlari mavjud.
Agar biror [a;b] oraliqda y=f(x) funktsiya uzluksiz bo’lib, f(a)*f(b)>0 o’lsa, shu oraliqda f(x)=0 tenglamaning kamida bitta ildizi mavjud bo’ladi.
Agar biror oraliqda y=f(x) funktsiya uzluksiz bo’lib, f(a)*f(b)<0 bo’lsa, shu oraliqda f(x)=0 tenglamaning bitta ildizi mavjud bo’ladi.

Download 0.79 Mb.

Do'stlaringiz bilan baham:
  1   2   3   4   5   6




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling