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

a
n
= n * f(t) / T
NP masalalar sinfi nima?
NP – polinom vaqtida tekshirilishi mumkin bo'lgan masalalar sinfi
P - polinomda (kirish kattaligidan) vaqt ichida yechiladigan masalalar sinfi
P – polinom vaqtida tekshirilishi mumkin bo'lgan masalalar sinfi
NP - polinomda (kirish kattaligidan) vaqt ichida yechiladigan masalalar sinfi
Algoritmlarni loyihalashning markaziy muammolaridan biri bu…
P va NP sinflarning tengligi masalasi
P va NP sinflarning tengmasligi masalasi
P sinfining masalasi
NP sinfining masalasi
P sinfi NP sinfiga tegishlimi?
Ha, tegishli. P sinfi NP sinfining bir qismidir
Ha, tegishli. P sinfi NP sinfining to’ldiruvchi qismidir
Yo’q, tegishli emas. P sinfi va NP sinfi alohida-alohida masalalar sinfidir
Yo’q, tegishli emas. Ammo P sinfi va NP sinfi masalalar bir-birini to’ldiruvchi sinflardir
NP sinfiga qanday turdagi masalalar kiradi?
Determinallashmagan polynomial murakkablikka ega masalalar
Polinomial murakkablikka ega masalalar
Determinallashgan masalalar
Yechimi topilishi oson bo’lgan masalalar
Kommivoyajer masalasi – bu…
Oldindan berilgan punktlarni minimal vaqt ichida yoki yo’lning minimal bo’lishiga erishgan holda aylanib o’tish masalasi
Turli yuklarni ko’pchilik manbalardan turli manzillar bo’yichа yetkazib berish masalasi
Mahsulotga ketgan xarajatlarni minimallashtirish masalasi
Daromadni oshirish modelini qurish masalasi
NP – to’liq masalalarni yechishda aniq usullarni ko’rsating
To’liq qayta tanlash; Dinamik dasturlash; Tarmoqlar va chegaralar
FF turidagi usullar
Ochko’z va gradiyent usullar
Tasodifiy usullar
Agar grafda gamilton sikli bo’lmasa ... bo’ladi?
Yechimlar to'plami bo'sh
Yechimlar to'plami
Qirra
Shajara
NP – to’liq masalalarni yechishda taqribiy usullarni ko’rsating
Ochko’z va gradiyent usullar; Tasodifiy usullar; FF turidagi usullar
To’liq qayta tanlash
Dinamik dasturlash
Tarmoqlar va chegaralar
Quyidagi algoritmik baholashlarning qaysi biri eng kam vaqtda bajariladi?
O(N)
O(N^3)
O(N^2)
O(NlogN)
A[5×5] va B[5×5] matritsalarni ko`paytirishda nechta amal bajariladi?
225
224
223
222
A[2×3] va B[3×4] matritsalarni ko`paytirishda nechta amal bajariladi?
40
30
20
10
A[5×3] va B[3×4] matritsalarni ko`paytirishda nechta amal bajariladi?
100
80
60
120
A[4×4] va B[4×4] matritsalarni ko`paytirishda nechta amal bajariladi?
112
114
100
120
A[3×3] va B[3×3] matritsalarni ko`paytirishda nechta amal bajariladi?
45
40
25
81
A[2×2] va B[2×2] matritsalarni ko`paytirishda nechta amal bajariladi?
12
14
8
4
A[3×2] va B[2×3] matritsalarni ko`paytirishda nechta amal bajariladi?
27
9
36
10
A[4×3] va B[3×2] matritsalarni ko`paytirishda nechta amal bajariladi?
40
72
14
20
A[2×4] va B[4×2] matritsalarni ko`paytirishda nechta amal bajariladi?
28
16
20
32
Sonli massiv elementlarini tartiblash masalasiga “ajrat va hukmronlik qil” tamoyilini taqbiq qilsak amallar soni qanday bo’ladi?
rekursiv - o'zini o'zi takrorlash(re - qayta degani)
masalan, retake - qayta o'qish
to'liq graf deyilsa n(n-1)/2
shunchaki graf deyilsa, n-1
tartiblashtirishda n ta element uchun
(n-1)^2 ta taqqoslash amali kerak
ajrat so'zini standart bilan bog'lasak,
logarifmik funksiyaning standart ko'rinishi
n ta ko'paytirish va n ta qo'shish => n+n=2n
Krustal algoritmiga ko’ra ustov(tayanch) daraxtni qidirish nimadan boshlanadi?
e^x–10x-2=0 funksiyani [-1;0] oraliqda taqribiy yechimini e=0.01 aniqlikda Urunmalar usuli bilan i=2 qadamdagi taqribiy yechini toping.
[0;1] oraliqda f(x)=sinx
funksiyaning aniq integrali qiymatini Simpson formulasi bo’yicha O(10 ) aniqlikda hisoblash uchun h – qadamni qanday olish kerak?
1024*log1024=1024*10=10240
256*log256=256*8=2048
N*logN=160 ==>> N=32
N*N=32*32=1024
(0;1) ==> (0; 1/2) yoki (1/2; 1) - 1-qadam
(0; 1/4) yoki (1/4; 1/2) yoki (1/2; 3/4) yoki (3/4; 1) - 2-qadam
2-qadam (0; 1/4) dan boshlanadi
to'g'ri to'rtburchakda qadam h bo'lsa
ko'paytirilganda 8ta element paydo boladi, har bir element uchun
3ta ko'paytirish va 2ta qo'shish amali bajariladi. 8*5=40
ko'paytirilganda 25ta element paydo boladi, har bir element uchun
5ta ko'paytirish va 4ta qo'shish amali bajariladi. 25*9=225
tayanch yechimda eng kamida 1ta 0 qatnashadi
tayanch yechimda eng kamida 1ta 0 qatnashadi
orttirma = qadam = h
kvadrat formadagi funksiya kvadrat model deyiladi
chiziqli formadagi funksiya chiziqli model deyiladi