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