1-мавзу. Алгоритмик масалани ечиш асослари 4соат

---

1-мавзу. Алгоритмик масалани ечиш асослари - 4соат. 
Режа: 
1. Алгоритмларни лойиҳалаш ва таҳлил этиш назариясида ишлатилган 
тушунчалар ва таърифлар; 
2. 
Масалани тушуниш. Ҳисоблаш қурилмасининг имкониятларини аниқлаш. 
Масалани аниқ ёки тақрибан ечиш усулларини танлаш. Алгоритмларни 
лойиҳалаш усуллари. Алгоритм корректлигини баҳолаш. Алгоритмларни 
таҳлил қилиш. Алгоритмни кодлаш
; 
 
1. Алгоритмларни лойиҳалаш ва таҳлил этиш назариясида ишлатилган 
тушунчалар ва таърифлар 
 
Қуйида тажриба – синов асосида шакллантирилган қуйидаги жадвал ёки ўқув танланмалар берилган 
бўлсин: 






























N
m
k
m
k
m
k
N
k
k
k
N
k
k
k
r
N
m
m
m
N
N
k
k
k
x
x
x
x
x
x
x
x
x
X
x
x
x
x
x
x
x
x
x
X
...
...
...
...
...
...
...
...,
,
...
...
...
...
...
...
...
2
1
2
2
2
1
2
1
2
1
1
1
1
2
1
1
1
12
2
12
1
12
11
2
11
1
11
1
1
1
1
, 
бу ерда 
1. 


r
p
t
p
t
X
X
X
X
t
p
r
p
p
,
1
,
,
,
1








бўлиб,
2. 
𝑥
𝑝𝑖
𝑗
- 
p
-чи тўпламнинг i-чи объектни j-чи белгиси; 
r
- берилган тўпламлар сони, 
p
m
- 
p
-чи тўплам 
объектлари сони. 
3. N-белгилар сони: 
4. Шуни алоҳида таъкидлаб ўтиш жоизки, белгиларнинг бир фазосидан бошқа фазосига ҳосил бўладиган 
белгилар фазоси ўлчами бошланғич белгилар фазоси ўлчамидан кичик бўлиши талаб этилади.
5. Одатда, буни амалга ошириш учун шундай 
f
акслантиришни аниқлаш зарурки, бу акслантириш 
бошланғич белгилар фазоси ўлчами акслантирилган фазо ўлчамидан катта бўлганда, танлаб олинган 
I
мезон 
учун 
 
 


extr
X
f
I
Y
I


шартни қаноатлантирсин. Бу қисм фазо деб тушунилади. 
6. Белгилар қисм фазосини шакллантиришда 
N
ўлчовли 


N




,...,
,
2
1

буль вектордан
фойдаланилади. Бу ерда 
𝜆 вектор компоненталари 𝜆
𝑗
∈ {0,1} қийматларни қабул қилади. 
7. Фараз қилайлик 
ℓ сони берилган бўлсин. Унинг, ℓнинг қиймати ℓ ≪ 𝑁 бўлсин деб талаб қилинади. 
Шуларни эътиборга олиб, 
ℓ ўлчамли

векторлар тўплами қуйидагича белгиланали ва аниқланади: 
Λ
ℓ
= {𝜆: ∑
𝜆
𝑗
𝑁
𝑗=1
= ℓ}. Бу тўплам элементларининг сони С
𝑁
ℓ
=
𝑁!
(𝑁−ℓ)!ℓ!
орқали ҳисобланади. Одатда,
Λ
ℓ
тўпламни 
ℓ ўлчамли 

векторлар фазоси ҳам дейишади. 
7. Объектларнинг 
ℓ ўлчамли 

белгилар фазосида Евклид нормаси қуйидагича киритилади: 
‖𝑥‖
𝜆
= √∑
𝜆
𝑗
(𝑥
𝑗
)
2
𝑁
𝑗=1
. 
8. Х
p
синф объектларининг белгилари кесимида 
𝑥̅
𝑝𝑖
- ўрта объект қуйидагича аниқланади: 
𝑥̅
𝑝𝑖
= (𝑥̅
𝑝𝑖
1
, 𝑥̅
𝑝𝑖
2
, … , 𝑥̅
𝑝𝑖
𝑁
). Бу ерда унинг j=параметри қуйидаги формула асосида ҳисобланади: 
𝑥̅
𝑝𝑖
1
=
1
𝑚
𝑝
∑
𝑥̅
𝑝𝑖
𝑗
𝑁
𝑗=1
. 
9. Ҳар бир тўплам объектлари орасидаги ички масофа қуйидаги кўринишда ҳисобланади:
 




p
m
i
p
pi
p
p
x
x
m
S
1
2
1


. 

---

Бу ерда 
 

p
S
катталик 

векторга нисбатан 
p
X
тўплам объектларининг ўртача квадратик 
тарқоқлигини тавсифлаб беради. 
10. Тўпламлар жуфтлиги объектлари аро ўртача квадратик тарқоқлик 

векторга нисбатан 
қуйидагича ҳисобланади:
 



q
1
,
2
,
x
-
p
r
q
p
q
p
q
p
x
x
x
R





. 
Яъни, 
 

q
p
R
,
қиймат 
p
Х
ва 


q
p
r
q
p
Х
q


;
,
1
,
тўпламлар жуфтлигидаги объектларнинг 
ўртача квадратик тарқоқлигини тавсифлаб беради. 
Берилган 𝑋
𝑝
ва 𝑋
𝑞
тўплам объектларининг 

векторлар фазосида жойлашувини баҳоловчи 
катталик қуйидагича ҳисобланади. 
 
 
 



r
p
p
q
p
S
R
I
1
2
,



(1) 
(1) – функционалнинг қийматига кўра 𝑋
𝑝
ва 𝑋
𝑞
тўплам объектларининг ўзаро жойлашуви 
аниқланади. Агар функционалнинг қиймати катта бўлса, у ҳолда бу тўплар обектлари бир-биридан 
ўзоқда жойлашганлигини билдирса қиймати кичик бўлса, у ҳолда тўплалар обектлари ўзаро яқин 
жойлашганликларини билдиради. Кўпгина адабиётларда 
ℓ = 1 бўлса, у ҳолда 
функционал содда 
Фишер мезони ҳисобланади. Ёки 
ℓ
ўлчамли 

векторга нисбатан Фишер мезони, яъни 
ℓ
ўлчамли 
Фишер мезони деб тушунилади.
11. Бошланғич белгилар фазосида 
N
ўлчовли 
a
ва 
b
векторлар киритилади ва уларнинг 
компоненталари қуйидагича аниқланади: 




.
N
1,
=
j
;
1
,
N
1,
=
j
;
1
1
2
1
,
2


















r
p
m
i
j
pi
j
p
p
j
r
q
p
j
q
j
p
j
p
x
x
m
b
x
x
a
Олинган натижавий векторларга кўра (1) функционални қуйидаги кўринишда ифодалаш 
мумкин: 
   
 



,
,
b
a
I

.
(2) 
(2) функционални
ℓ
ўлчамли Фишер типидаги мезон деб тушунилади. Чунки, 
N
ўлчовли 
a
ва 
b
векторлар бошқа формулалар орқали ҳам ҳисобланган бўлиши мумкин. 
Фишер типидпги (2) мезон эвристик мезон бўлиб, у тимсолларни аниқлаш назариясида 
“компактлик” гипотезасига асосланади, яъни синфлар орасидаги масофанинг катталашиши билан 
уларни ажратиш яхшиланиб боради. Синфлар орасидаги масофани максималлаштирган белгилар 
информатив деб фараз қилинади.
 

I
функционал объектлар орасидаги масофалардан ташкил топган бўлиб, у барча 
конфигурацияларни силжитишга нисбатан қатъий инвариантдир. 
Тўпламлар объектларининг ўзаро бир бирларидан фарқли эканлигини кўрсатувчи катталикни 
мезон деб олдик. Синф объектларининг
ℓ
ўлчамли фазода жойлашуви сифатини баҳолашда 
фойдаланиладиган бошқа турдаги мезонлар ахборот ва статистика назариясига асосланиб 
қурилади. Бундай мезонлар масофа, информацион ва эҳтимоллик ўлчовлари асосида 
шакллантирилади. 
Кўпинча амалий масалаларни ечишда ахборот ва статистика назарияси асосида қурилган 
мезонлардан кўра анча содда бўлган эвристик мезонлардан фойдаланилади. Эвристик мезонларни 
соддалигига қарамай улар кўплаб амалий масалаларни ечишда юқори натижалар беради. 
Фишер типидаги мезонлар содда бўлгани билан айрим камчиликларга ҳам эга: таҳлил 
қилинаётган синфларнинг мураккаб чизиқли бўлмаган хоссаларини инобатга олмайди, аммо 
бундай содда мезонлар кўп ҳолларда ишончли натижаларни беради, яъни аниқ информатив 
белгилар мажмуасини ажратмасада ҳеч бўлмаганда етарли даражада информатив белгилар 
мажмуасини ажратиш имконини беради. Мураккаб мезонлар эса жуда кўп ҳолларда ҳал қилувчи 
қоидани қуриш қийин бўлган информатив белгилар мажмуасини ажратади. 

---

Курсимизда қуйидаги кўринишдаги мезонлардан ҳам фойдаланамиз: 
 
 
 


r
q
s
R
R
G
I
sq
sq
p
r
p
,
1
,
,
:
max
0
,
1







.
(3) 
 
 
 


r
s
G
G
R
I
s
s
pq
r
q
p
,
1
,
:
min
0
,
1
,







. 
(4) 
 
 
   




q
p
pq
r
q
p
G
G
R
I
2
,
1
,
min


. 
(5) 
бу ерда 
 










p
q
m
i
m
k
N
j
j
pk
j
pi
j
q
p
p
x
x
m
m
G
1
1
1
2
1
2
2


.
(6) 
 









p
q
m
i
m
k
N
j
j
pr
j
pi
j
q
p
pq
x
x
m
m
R
1
1
1
2
1
1


. (7) 
Қуйидаги белгилашлар киритиб 





N
j
j
j
p
p
b
b
1
,


, 





N
j
j
j
pq
pq
a
a
1
,


, 









p
p
m
i
m
j
j
pr
j
pi
p
p
j
p
x
x
m
m
b
1
1
2
1
1
2
, 








p
p
m
i
m
k
j
qr
j
pi
q
p
j
pq
x
x
m
m
a
1
1
2
1
1
(6) ва (7)ни қуйидаги кўринишга келтириш мумкин: 
 
 
 






,
,
,
pq
pq
p
p
a
R
b
G


. 
У ҳолда (5) қуйидаги кўринишга келади: 
 



  




,
,
,
min
,
1
,
q
p
pq
r
q
p
b
b
a
I



. 
(8) 
Ушбу мезоннинг хусусий ҳолларидан бири 
2

r
да у қуйидаги кўринишда бўлади: 
 
 
  




,
,
,
2
c
b
a
I

,
(9) 
бу ерда (*,*)-векторларнинг скаляр кўпайтмаси. Адабиётларда (9) типидаги мезонларни ГОрелик 
типидаги мезонлар деб тушунилади. 
Горелик типидаги мезонларни қуйидаги кўринишлари ҳам мавжуд:
    

   





,
,
,
,
c
b
d
a
I



.
(10) 
   

  





,
,
,
,
c
b
d
a
I

.
(11) 
   
 
 
  






,
,
,
,
,
2
d
c
a
b
a
I


,
(12) 
бу ерда 
 




p
m
i
p
pi
p
x
x
m
b
1
2
1
,


, 
 




q
m
i
q
qi
q
x
x
m
c
1
2
1
,


p
X
ва 
q
X
синф 
объектларининг 

-га нисбатан ўртача квадратик жойлашиши. 
Юқорида (10), (11) ва (12) формулада келтирилган мезонлар Фишер ва Горелик типидаги 
мезонларининг комбинирлашганидир, яъни, биринчи қўшилувчи Фишер, иккинчи қўшилувчи эса 
Горелик мезонидир. 
Юқорида келтириб ўтилган барча мезонлар “компактлик” гипотезасига асосланган ҳолда 
шакллантирилган бўлиб, уларни маълум бир ягона тизимга келтириш ва улар учун умумий усулни 
ишлаб чиқиш масаласи пайдо бўлди. 

---

Курс давомида қуйидаги оптимизация масаласини ечиш мисолида алгоритмларни
лойиҳалаш
{
𝐼(𝜆) → 𝑚𝑎𝑥
Λ
ℓ
=
{
𝜆: 
∑
𝜆
𝑗
𝑁
𝑗=1
= ℓ
}
Ва таҳлил қилиш ишлари амалга оширилади. 

---