Танилцуулга 5

Бүлэг 1. Логик дүгнэлт, мэдлэг боловсруулах системийн арга, машинуудын шинжилгээ 14

1.1 Логик дүгнэлт гаргах арга, машин 14

1.1.1 Логик дүгнэлтийн төрлүүдийн ангилал 14

1.1.2 Дүгнэлтийн аргуудын ангилал 16

1.1.3 19-р заалтыг хуваах арга

1.1.4 Дүгнэлт гаргах машин 23

1.2 Мэдлэг боловсруулах систем (KPS) 25

1.2.1 Тодорхойлолт, бүтэц 25

1.2.2 Ангилал 29

1.2.3 Үйлдлийн горимууд 31

1.2.4 Гүйцэтгэлийн үнэлгээ 33

1.3 1-р бүлгийн дүгнэлт 35

Бүлэг 2. Өөрчлөгдсөн дүгнэлтээс логик дүгнэлт хийх аргыг боловсруулах 36

2.1 Албан ёсны системүүд 36

2.2 Логик дүгнэлтийн бодлогын илэрхийлэл 37

2.3 Дүгнэлтийн томъёоны өргөтгөл

2.3.1 Үг үсгийг нэгтгэх 39

2.3.2 Шийдвэрийг зохицуулах 40

2.3.3 Дизюнкт 43 дахь нийтлэг хувьсагчдын утгын талаархи тохиролцоо

2.3.4 45-р заалтыг хэсэгчлэн хуваах

2.3.5 47-р зүйлийн бүрэн хуваагдал

2.3.6 Гаралтын журам 49

2.3.7 Хулгайлсан тайлбарыг бий болгох

2.3.8 Дүгнэлтийн томъёог өргөтгөхтэй зэрэгцээ дүгнэлт хийх арга

2.4 65-р дүгнэлтийн томъёог багасгах

2.4.1 Дүгнэлтийг багасгах журам 65

2.4.2 Дүгнэлтийг багасгах арга

2.5 Өөрчлөлтийн сонголтыг сонгох 69

2.6 Саналын тооцооллын дүгнэлтийн онцлог 72

2.7 Гаралтын жишээ 73

2.8 2-р бүлгийн дүгнэлт 77

Бүлэг 3. Өөрчлөгдсөн дүгнэлтэд зориулсан логик дүгнэлтийн системийг боловсруулах 80

3.1 Дүгнэлтийн системийн бүтэц 80

3.1.1 Системийн ерөнхий бүтэц 80

3.1.2 Системийн нарийвчилсан бүтэц 82

3.2 Логик дүгнэлтийн системийн ажиллах горимууд 85

3.2.1 Өөрчлөгдсөн дүгнэлт гаргах горим 86

3.2.2 Дедуктив дүгнэлт гаргах горим 88

3.2.3 Хулгайлах дүгнэлтийн горим 88

3.2.4 Тохируулах горим 88

3.2.5 Мэдлэгийн санд шууд нэвтрэх арга 89

3.2.6 Мэдлэгийн сан бүрдүүлэх

3.3 Өөрчлөгдсөн дүгнэлт гаргах логик дүгнэлтийн машин 90

3.4 Декларатив логик програмчлалын хэл

3.4.1 Логик программын бүтэц 96

3.4.2 Тодорхойлогч ба тогтмолууд 99

3.4.3 Сэтгэгдэл 100

3.4.4 Логик программын жишээ 101

3.5 Дүгнэлтийн системийн үр нөлөөг үнэлэх 102

3.5.1 Гүйцэтгэлийн үнэлгээний шалгуур 102

3.5.2 Татгалзах хугацааны тооцоо 103

3.5.3 Дүгнэлтийн өөрчлөлтийн зэрэглэлийн тооцоо 108

3.6 3-р бүлгийн дүгнэлт 110

Бүлэг 4. Өөрчлөгдсөн IZ дүгнэлтэд логик дүгнэлтийн системийг хэрэглэх

4.1 Хэрэглээ 113

4.2 Ухаалаг сургалтын систем 114

4.3 Эксперт систем 119

4.4 Тооцооллын процессын ухаалаг удирдлага 121

4.5 Өөрчлөгдсөн дүгнэлтийн логик гаралтын модуль 1

4.5.1 Боловсруулж буй програм хангамжийн ерөнхий шинж чанар 127

4.5.2 Гаралтын модулийн бүтэц 128

4.5.3 Мэдлэгийн сан, дүгнэлтийг дүрслэх хэл 129

4.5.4 Модуль 130 блокийн хэрэгжилт

4.6 Логик дүгнэлт хийх сургалтын хөтөлбөр “Логика-V” 134

4.6.1 Хөтөлбөрийн бүтэц 134

4.6.2 Эх сурвалжийн өгөгдлийг тайлбарлах хэл 135

4.6.3 Хэрэглэгчийн интерфейс 136

4.6.4 Програмыг ашиглах жишээ 141

4.7 4-р бүлгийн дүгнэлт 149

Дүгнэлт 152

Товчлолын жагсаалт 155

Ном зүй 156

Хэрэглээ 1

Ажлын танилцуулга

Энэхүү диссертаци нь саналын тооцоолол ба нэгдүгээр зэрэглэлийн предикатын тооцооллын томъёо хэлбэрээр танилцуулсан мэдлэгийн талаар өөрчлөх боломжтой дүгнэлтийг логик дүгнэлт хийх шинэ аргыг боловсруулахад зориулагдсан болно. Энэхүү аргыг ашиглан мэдлэг боловсруулах систем, логик дүгнэлтийн машиныг бий болгох асуудлыг, түүний дотор орчин үеийн зэрэгцээ тооцоолох платформ дээр програм хангамжийг хэрэгжүүлэх онцлогийг авч үзсэн. Логик дүгнэлтийн энэ аргыг ашиглах боломжит чиглэлүүдийг өгч, тооцооллын процессыг ухаалаг удирдах, сургалтын систем, шинжээчийн системд өөрчилсөн дүгнэлтийн логик дүгнэлтийг ашиглах талаар авч үзсэн.

Судалгааны сэдвийн хамаарал. Өнөөдөр тооцоолох системийн ирээдүйтэй чиглэлүүдийн нэг бол мэдлэг боловсруулах систем (KPS) юм. Тэд аль хэдийн өргөн тархсан (энэ нь ялангуяа шинжээчдийн системд (ES) хамаатай) бөгөөд ирээдүйд бараг бүх төрлийн тооцоолох системийн оюуны түвшинг дээшлүүлж, бараг хаа сайгүй ашиглах боломжтой болно. Гэсэн хэдий ч одоо байгаа ололт амжилтыг үл харгалзан орчин үеийн POP нь хэд хэдэн сул талуудтай байдаг. Тэр дундаа найдваргүй дүгнэлт гарсан тохиолдолд найдвартай дүгнэлттэй байхыг шаарддаг асуудлыг шийдэж чаддаггүй. Үүнээс гадна орчин үеийн POP нь зэрэгцээ платформ дээр үр дүнтэй ажилладаггүй.

Боловсруулах аливаа албан ёсны үйлдлийн операнд болох, боловсруулах системийн үүднээс семантик агуулгагүй өгөгдлөөс ялгаатай нь мэдлэг нь бодит ертөнцийн тодорхой талыг тусгадаг бөгөөд анхандаа семантик агуулгатай байдаг. Өнөөдөр мэдэгдэж байгаа мэдлэг боловсруулах хамгийн шилдэг систем бол хүний ​​тархи юм. Гэсэн хэдий ч энэ нь бас зарим сул талуудтай. Тэр дундаа олон асуудлыг шийдвэрлэхдээ гүйцэтгэл муутай, тархины үйл ажиллагаа олон хүчин зүйлээс шалтгаалдаг, алдаа гаргадаг. Нэмж дурдахад хүрээлэн буй орчны нөхцөл байдал нь хүнийг мэдлэгийг боловсруулах, шийдвэр гаргах систем болгон ашиглахыг зөвшөөрдөггүй. Хүний зан үйлийг загварчлах шаардлага бий.

Байгалийн оюун ухааны зан үйлийг загварчлах хоёр үндсэн арга байдаг. Тэдний эхнийх нь тархины бүтцийн бие даасан элементүүдийн ажлыг загварчлах явдал юм - мэдрэлийн эсүүд ба тэдгээрийн холболтууд (мэдрэлийн сүлжээний хандлага). Үүний онцлог сул тал бол сэтгэхүйн явцын семантик зургийг бүтээхэд хэцүү (ихэнхдээ боломжгүй) байдаг. Хоёрдахь арга нь тархины үйл ажиллагааны оюуны талыг загварчлах явдал юм: ойлголтын систем (семантик сүлжээ), үндэслэл болон бусад. Үүний зэрэгцээ, хүний ​​сэтгэхүйг загварчлах нь одоо ихэвчлэн ашиглагддаг, учир нь энэ нь тодорхой дүрмийн дагуу (жишээлбэл, логикийн дүрмийн дагуу) өндөр түвшний сэтгэхүйн үйл явцыг дуурайж, эх сурвалжийг энгийн байдлаар дүрсэлж, тайлбарлах боломжийг олгодог. үр дүн, түүнчлэн симуляцийн явцыг хянах.

Логик ашиглан үндэслэлийг загварчлах нь хиймэл оюун ухааны арга, хэрэгслийг судалдаг шинжлэх ухааны тэргүүлэх чиглэлүүдийн нэг юм. Нэгдүгээр эрэмбийн предикатын логик эсвэл саналын логикийн томьёо хэлбэрээр бичсэн үндэслэлүүд нь хүмүүст маш байгалийн юм шиг санагддаг. Томъёоны тайлбар нь энгийн бөгөөд шууд утгыг урьдчилан тодорхойлсон хэллэгээр, холбогчийг утгаараа тохирох үгсээр солихоос бүрдэнэ.

Саналын логик нь маш том илэрхийлэх чадваргүй нэлээд энгийн математик аппарат юм. Гэсэн хэдий ч томъёог боловсруулахад хялбар байдаг тул саналын логикийг өргөн ашигладаг. Нэгдүгээр эрэмбийн предикатын логик нь илүү их илэрхийлэх чадвартай байдаг. Гэхдээ предикатын тооцоонд томъёог боловсруулах нь илүү төвөгтэй байдаг, учир нь энэ нь предикатын тогтмолуудын утгуудын нэр томъёоны багцаас хамаарах хамаарлыг харгалзан үзэх, субьект хувьсагчдын утгыг зохицуулах, байх боломжийг харгалзан үзэх шаардлагатай байдаг. функциональ тогтмолуудын.

Үндэслэлийг загварчлах нь өөрөө логик дүгнэлтээр (LI) явагддаг. Логик дүгнэлт хийх анхны өгөгдөл нь байр, дүгнэлтийн томъёо юм. Байшин нь дүгнэлтийн баримт, дүрмийн багц бөгөөд хамтдаа мэдлэгийн баазыг бүрдүүлдэг. Дүгнэлт нь логик томъёо хэлбэрээр бичигдсэн бөгөөд (дүрмээр) гаднаас логик дүгнэлтийн системд ордог. Дүгнэлт хийх журам нь дүгнэлт, анхны байр суурийг боловсруулдаг бөгөөд ажлын үр дүн нь дүгнэлтийн зөв эсэх эсвэл анхны байр суурийг өөрчлөх тухай мессеж байж болно.

Ерөнхийдөө логик дүгнэлтийн дараах үндсэн төрлүүдийг ялгадаг: дедуктив, хулгайлах ба индуктив. Өгөгдсөн дүгнэлт нь анхны байр суурийн логик үр дагавар мөн үү гэсэн асуултад хариулахад дедуктив дүгнэлтийг ашигладаг. Хулгайлсан дүгнэлт нь эхний байр сууринаас дүгнэлт гаргах боломжгүй бол дүгнэлтийг гаргах боломжтой болохын тулд эхний байр суурийг баримтаар нөхөх боломжийг олгодог. Хулгайлсан дүгнэлтээс ялгаатай нь индуктив дүгнэлт нь анхны байр суурийг ерөнхий дүрмээр нөхөх боломжийг олгодог.

Эдгээр төрлийн дүгнэлт нь удаан хугацааны туршид мэдэгдэж байсан бөгөөд өргөн хүрээний асуудлыг шийдвэрлэхэд ашиглаж болно. Гэсэн хэдий ч, эдгээр төрлийн дүгнэлтийг ашиглан шийдвэрлэх боломжгүй эсвэл хэцүү асуудлуудын ангилал байдаг. Энэ ангиллын асуудал нь тодорхой сэдвийн хүрээнд зөв, бүрэн мэдлэгийн бааз, өөрчлөлтийг шаарддаг найдваргүй дүгнэлт байгаа гэж үздэг. Үүний үр дүнд логик дүгнэлтийн асуудлын цоо шинэ томъёолол гарч ирэв: анхан шатны үндэслэлийн үр дагавар болгохын тулд эхнээс нь гаргаж авах боломжгүй дүгнэлтийг өөрчлөх. Энэ асуудлыг шинэ төрлийн LP - өөрчилсөн дүгнэлтийн логик дүгнэлтийг ашиглан шийддэг. Энэ төрлийн гаралтын хэрэглээний дараах чиглэлүүдийг тэмдэглэж болно: - автомат удирдлагын систем. Ийм систем дэх хяналтын объектын төлөвийг логик дүгнэлтийн томьёогоор тодорхойлж, төлөв байдлын зөвшөөрөгдөх мужийг анхны байруудын томъёоны хэлбэрээр зааж өгсөн болно. Хэрэв объектын төлөв байдал зөвшөөрөгдөх хязгаараас гадуур байвал дүгнэлтийг объектыг хүлээн зөвшөөрөгдсөн төлөвт буцаахын тулд өөрчилнө;

Залруулах сургалтын системүүд. Анхны таамаглалын үндэс нь тодорхой сэдвийн хүрээнд авсан мэдлэгийг агуулдаг. Оюутан үнэн эсэхийг шалгасан мэдэгдлийг оруулна (анхны байр сууринаас дүгнэлт гаргах), хэрэв энэ нь буруу бол түүнийг засна;

Өгүүлбэрийн дүрмийн дүн шинжилгээ. Өөрчлөгдсөн дүгнэлтийн логик дүгнэлтийг өгүүлбэрийг сэргээж, шинэ өгүүлбэр бүтээхэд ашиглаж болно;

Динамик архитектур бүхий тооцоолох системүүд. Өөрчлөгдсөн дүгнэлтийн логик дүгнэлтийг динамикаар өөрчлөгдөж буй найрлага, тооцоолох хэрэгслийн холболттой системд тооцоолох процессыг дамжуулахад ашиглаж болно;

Мэргэшсэн системүүд. Хэрэв хэрэглэгчийн анхны дүгнэлт бүрэн бус эсвэл буруу байвал өөрчилсөн дүгнэлтийн логик дүгнэлт нь дүгнэлтийг тодруулах (засварлах) боломжтой болох бөгөөд зарим тохиолдолд нэмэлт шинж чанаруудыг судлах шаардлагатай байгааг харуулж байна.

Маш олон тооны логик дүгнэлтийн аргууд байдаг. Тэдний нэлээд хэсгийн гол сул тал бол мэдлэгийг боловсруулах тууштай зарчим юм. Энэ нь эдгээр аргуудыг ашиглан дүгнэлт хийх системийн гүйцэтгэлийг ихээхэн бууруулдаг. Үүнтэй холбогдуулан өгүүлбэрүүдийг хуваах журамд суурилсан зэрэгцээ логик дүгнэлт хийх аргуудыг анхаарч үзэх хэрэгтэй. Ийм гаралтын алхам бүр нь хэд хэдэн үйлдлүүдийг агуулж болох бөгөөд тэдгээрийн ихэнхийг зэрэгцээ хийж болно. Энэ нь өнөөгийн цаг үед онцгой ач холбогдолтой юм, учир нь ихэнх тохиолдолд процессоруудын архитектур, микро архитектурыг сайжруулах, цагийн давтамжийг нэмэгдүүлэх замаар компьютерийн гүйцэтгэлийг нэмэгдүүлэхээс гадна процессорын элементүүдийн (процессор ба цөм) тоог нэмэгдүүлэх замаар нэмэгддэг. .

Тиймээс нэн яаралтай ажил бол саналын тооцоолол ба нэгдүгээр зэрэглэлийн предикатын тооцооллын томъёо хэлбэрээр танилцуулсан мэдлэгийн талаархи өөрчилсөн дүгнэлтийг зэрэгцээ логик дүгнэлт хийх арга, системийг боловсруулах бөгөөд энэ нь SOZ-ээр шийдсэн асуудлын ангиллыг өргөжүүлэх болно. логик дүгнэлтийн системийн үндэс, тэдгээрийн ажлын хурдыг нэмэгдүүлэх.

Логик дүгнэлт хийх арга, хэрэгслийг боловсруулах, судлахад томоохон хувь нэмэр оруулсан нь М.Л.Цетлин, М.М.Бонгард, Я.З.Цыпкин, Д.А.Поспелов, В.К.Фин, Г.С.Осипов, В.Н.Вагин, Т.А.Гаврилова, В.Ф.Хорошев нар юм. П.Гаек, Т.Гавранек, С.Осуга, У.Саэки, А.Сэмюэл, Э.Хант, Ж.Марин, П.Стоун, Р.Мичальски, Ж.Карбонелл, Т.Митчелл Т.Митчелл), Д. Квинлан. Хулгайлсан LE-ийг C. S. Pierce, V. K. Finn, V. N. Vagin, E. Yu Golovina, D. A. Strabykin, M. L. Dozhenkova, D. D. Gabbay, P. Smets, C. Boutilier, P. Flach, A. Kakas нарын бүтээлүүдэд судалсан. , К.Иноуэ ), С.Сакама, Ж.Жосефсон, С.Маклрейт, Г.Пол болон бусад.

Судалгааны зорилго нь өгүүлбэрийн тооцоо, нэгдүгээр эрэмбийн предикатуудын тооцооллын өөрчилсөн дүгнэлтийг зэрэгцээ логик дүгнэлт хийх аргыг боловсруулж, түүний үндсэн дээр өөрчлөгдсөн дүгнэлтийн систем, LP машиныг бий болгоход оршино. Зорилгодоо хүрэхийн тулд дараахь ажлуудыг шийдвэрлэх шаардлагатай байна.

1. Үүсмэл бус дүгнэлтийг өөрчлөх, түүнийг эхний байруудын үр дагавар болгох боломжийг олгодог мэдэгдлийн тооцоо ба нэгдүгээр эрэмбийн предикатуудын тооцоололд зориулсан өөрчилсөн дүгнэлтийг зэрэгцээ логик гарган авах аргыг боловсруулах.

2. Өөрчлөгдсөн дүгнэлтийг параллель логик дүгнэлт гаргах машин бүтээ.

3. Өөрчлөгдсөн дүгнэлтэд зориулсан логик дүгнэлтийн машинд суурилсан параллель логик дүгнэлтийн системийг боловсруулах.

4. Өөрчлөгдсөн дүгнэлтийн зэрэгцээ логик дүгнэлт хийх систем ба машины үр ашгийг үнэлэх шалгуурыг боловсруулах.

Судалгааны аргууд. Ажилд тавьсан судалгааны зорилгодоо хүрэхийн тулд алгоритмын шинжилгээний аргууд, олонлогын онол, графикийн онол, математик логик, дүгнэлтийн онол, логик болон объект хандалтат програмчлалын аргыг ашигласан.

Судалгааны шинжлэх ухааны шинэлэг тал нь дараах байдалтай байна.

1. Хулгайлсан дүгнэлтийн үр дүнд олж авсан нэмэлт байранд дараах нэмэлт байруудыг хэрэглэдгээрээ мэдэгдэж буй аргуудаас ялгаатай нь саналын логик ба нэгдүгээр эрэмбийн предикатын логикийн өөрчилсөн дүгнэлтүүдийн зэрэгцээ логик дүгнэлт хийх аргыг боловсруулсан: a. Эдгээрээс дүгнэлтийн салангид хэсгүүдийн нэмэлт, дүгнэлтийг багасгах арга, түүнчлэн дүгнэлтийг өөрчлөх хувилбаруудыг үнэлэх зэрэгцээ алгоритмыг бий болгох боломжийг олгодог хувиргах тусгай журам. Энэ нь анхны байр суурийн үр дагавар болгохын тулд үл тоомсорлох дүгнэлтийг өөрчлөх боломжийг танд олгоно.

2. Саналын тооцоолол болон нэгдүгээр эрэмбийн предикатын тооцоололд зориулсан дүгнэлтийг багасгах аргыг боловсруулсан бөгөөд энэ нь шийдлийг олохын тулд мөчрүүдийн хэсгийг таслан шийдвэрийн модоор зэрэгцээ хайлт хийдэг гэдгээрээ мэдэгдэж буй дүгнэлтийн аргуудаас ялгаатай юм. Үүний зэрэгцээ дүгнэлтийн заалтуудаас дүгнэлт гаргах үйл явцад оролцдоггүй үг хэллэгийг хасч, улмаар өөрчилсөн дүгнэлтэд логик дүгнэлтийн системийн үр ашгийг нэмэгдүүлдэг.

3. Дүгнэлтийн заалтуудыг өөрчлөх хувилбаруудыг үнэлэх, сонгох зэрэгцээ алгоритмыг боловсруулсан бөгөөд энэ нь заалт бүрт тусгай үнэлгээний функцийг хэрэглэснээр олж авсан тодорхой тоон утгыг оноож өгдөг онцлогтой. Энэ нь сонгосон дизьюнктын үнэлгээний функцийн дагуу анхны дизюнктуудыг өөрчлөх бүх сонголтуудаас хамгийн сайныг нь сонгох боломжийг танд олгоно.

4. Зүйлүүдийг хуваах замаар логик дүгнэлт хийх онцлог, сонгосон параллелизмын зэрэг, компьютерийн бүтэц, төрлүүд зэргийг харгалзан өөрчилсөн дүгнэлтийн систем, логик дүгнэлтийн машины үр ашгийг үнэлэх шалгуур, аргуудыг боловсруулсан болно. дүгнэлтийг өөрчлөх, энэ нь логик дүгнэлт хийхэд зарцуулсан цаг хугацаа, дүгнэлтийг өөрчлөх түвшинг тооцоолох боломжийг олгодог.

Судалгааны практик ач холбогдол нь дараах байдалтай байна.

1. Өөрчлөгдөж болох дүгнэлтүүдийн зэрэгцээ, логик дүгнэлт хийх системийг боловсруулсан бөгөөд тэдгээрийн ялгаатай шинж чанарууд нь: Зэрэгцээ LP арга, машин ашиглах, хоёр түвшний мэдлэгийн санг ашиглах, томъёоны тайлбарын блок байх, Энэ нь боловсруулсан логик дүгнэлтийн системд тулгуурлан янз бүрийн зориулалтаар өндөр хүчин чадалтай POP-уудыг бүтээх боломжийг олгодог. Дүгнэлт хийх үйл явцыг шууд утгаар нэгтгэх үйлдлүүдийн түвшинд хүртэл зэрэгцүүлж болох бөгөөд энэ нь зэрэгцээ тооцоолох платформ дээр логик дүгнэлт гаргах хурдыг нэмэгдүүлдэг.

2. Бодолтын тооцоо, нэгдүгээр эрэмбийн предикатын тооцооллын томьёо ашиглан мэдлэгийг дүрслэх, функциональ ашиглах, логик томъёог байгалийн хэлээр тайлбарлах чадварыг эзэмших боломжийг олгодог тунхаглалын логик програмчлалын хэлийг боловсруулсан.

3. Логик дүгнэлт хийх сургалтын хөтөлбөрийг боловсруулсан бөгөөд түүний өвөрмөц онцлог нь: Өөрчлөгдсөн дүгнэлтийн логик дүгнэлт, томъёог хөрвүүлэх механизмтай байх зэрэг мэдэгдлийг тооцоолох заалтуудыг хуваах замаар хэд хэдэн төрлийн логик дүгнэлтийг хэрэгжүүлэх явдал юм. олон заалт, томьёог байгалийн хэлээр тайлбарлах, явцын дэлгэрэнгүй тайлангийн гаралт. Системийн онцлог нь үүнийг логик дүгнэлтийн төрөл, аргуудыг судлахад ашиглах боломжийг олгодог.

4. Тооцооллын процессыг ухаалаг удирдах, ухаалаг сургалтын систем, шинжээчийн системд өөрчилсөн дүгнэлтийг зэрэгцээ логик дүгнэлт хийх арга, системийг ашиглах зөвлөмжийг боловсруулсан.

Хамгаалалтад дараахь зүйлийг ирүүлж байна.

1. Саналын логик ба нэгдүгээр эрэмбийн предикатын логикийн хувьд өөрчилсөн дүгнэлтийг зэрэгцээ логик гарган авах арга бөгөөд энэ нь гарал үүслийн бус дүгнэлтийг анхны байр суурийн үр дагавар болгохын тулд хувиргах боломжийг олгодог.

2. Дүгнэлтийн үйл явцад оролцдоггүй литералуудыг арилгах, улмаар дүгнэлтийн системийн үр ашгийг нэмэгдүүлэх боломжийг олгодог саналын тооцоолол ба нэгдүгээр эрэмбийн предикатын тооцооллын дүгнэлтийг багасгах арга.

3. Дүгнэлтийн заалтуудыг өөрчлөх хувилбаруудыг үнэлэх, сонгох зэрэгцээ алгоритм нь оновчтой шийдлийг олохын тулд сонгосон дүрмийн дагуу анхны заалтуудыг өөрчлөх бүх хувилбараас хамгийн сайныг нь сонгох боломжийг олгодог.

4. Зүйлүүдийг хуваах замаар логик дүгнэлт хийх онцлог, сонгосон параллелизмын зэрэг, компьютерийн архитектур, дүгнэлтийг өөрчлөх хэлбэрийг харгалзан өөрчилсөн дүгнэлтийг логик дүгнэлт хийх систем, машины үр ашгийг үнэлэх шалгуур, арга.

5. Зэрэгцээ логик дүгнэлтийн машинд суурилсан, логик дүгнэлтийн үндсэн төрлүүд, түүнчлэн өөрчилсөн дүгнэлтийн логик дүгнэлтийг гүйцэтгэх чадвартай параллель систем. Судалгааны үр дүнгийн хэрэгжилт. Хүлээн авсан онолын болон практик үр дүнг "Дүгнэлтийг өөрчлөх замаар логик дүгнэлтийн онол ба хэрэглээ" (ОХУ-ын Боловсролын яамны тэтгэлэг E02-2.0-93), "Хөгжлийн тухай" судалгааны ажилд ашигласан. Кластер тооцоолох системд зориулсан тунхаглалын логик програмчлалын орчин” (Вятка Улсын Их Сургууль, судалгааны ажил №412) . Логик дүгнэлтийн сургалтын хөтөлбөрийг Вятка муж, Вятка муж улсын хүмүүнлэгийн их сургуулийн сургалтын үйл явцад нэвтрүүлсэн.

Ажлын баталгаажуулалт. Судалгааны үндсэн заалт, үр дүнг “Интерактив систем: Хүн-компьютерийн харилцан үйлчлэлийн асуудал” олон улсын 5-р бага хуралд тайлагнаж, хэлэлцсэн, Ульяновск, Ульяновскийн Улсын Техникийн Их Сургууль, 2003; 9-р “Хиймэл оюун ухааны үндэсний бага хурал KII-2004”, Тверь, 2004; Вятскийн Улсын Их Сургуулийн "Шинжлэх ухаан-үйлдвэрлэл-технологи-экологи" Бүх Оросын жил бүр болдог шинжлэх ухаан, техникийн бага хурал, Киров (2004,2007,2008)

Үйлдвэрлэлийн системд дүгнэлт гаргах, шийдлийг хайх аргууд.

Урагш ба арагш гинжин хэлхээнд суурилсан дүгнэлтийн аргууд.

Үйлдвэрлэлийн дүрслэлд мэдлэгийн хүрээг үйлдвэрлэлийн багц дүрмээр, өгөгдөл нь одоогийн нөхцөл байдлын талаархи багц баримтаар илэрхийлэгддэг.

Дүгнэлтийн систем нь мэдээллийн санд хадгалагдсан дүрэм бүрийг өгөгдлийн санд байгаа баримтуудтай харьцуулдаг. Дүрмийн (нөхцөл) хэсэг нь баримттай таарч байвал дүрэм өдөөгдөх ба дараа нь хэсэг (үйлдэл) гүйцэтгэсэн. Өдөөгдсөн дүрэм нь 6.1-р зурагт үзүүлсэн шиг шинэ баримт нэмэх замаар олон баримтыг өөрчилж болно. Нөхцөл байдал, ойлголтыг илэрхийлэхийн тулд DB болон KB дахь үсгүүдийг ашигладаг.

Зураг 6.1. Шүдэнзний галын процедурын дагуу дүгнэлт хийх механизмын мөчлөг

Хэрэв дүрмүүд баримттай байвал хэсгүүдийн харьцуулалт гаралтын хэлхээ.Дүгнэлт гаргахын тулд ES нь дүрмийг хэрхэн хэрэгжүүлдэгийг дүгнэлтийн хэлхээ харуулж байна. Гинжинд суурилсан дүгнэлтийн аргыг харуулахын тулд энгийн жишээг авч үзье.

Өгөгдлийн санд анх A, B, C, D, E баримтууд багтсан бол мэдлэгийн сан нь зөвхөн гурван дүрмийг агуулдаг гэж үзье.

Дүрэм 1. Y&D → Z

Дүрэм 2. X&B&E→Y

Дүрэм 3. A→X

Зураг дээрх гаралтын гинж. 6.2. ES нь Z баримтыг гаргах дүрмийг хэрхэн хэрэгжүүлдгийг харуулж байна.

Зураг.6.2.Гаралтын гинжин хэлхээний жишээ.

Эхлээд нийтлэгдсэн А баримтаас шинэ X баримтыг гаргаж авахын тулд 3-р дүрмийг хэрэгжүүлнэ. Дараа нь 2-р дүрмийг анх мэдэгдэж байсан В, Е баримтаас Y баримтыг, мөн аль хэдийн мэдэгдэж байсан X баримтаас гаргаж авахын тулд 1-р дүрмийг хэрэгжүүлнэ. анх мэдэгдэж байсан баримт D болон шинээр олж авсан Y баримт нь ирж дүгнэлт Z.

ES нь тодорхой шийдвэрт хэрхэн хүрсэн талаар тайлбарлах өөрийн дүгнэлтийн хэлхээг тусгаж болно; Энэ нь түүний тайлбарлах эрх мэдлийн томоохон хэсэг юм.

Дүрмүүд хэзээ гарахыг дүгнэлтийн хөдөлгүүр шийдэх ёстой. Дүрмийг хэрэгжүүлэх хоёр үндсэн арга байдаг. Нэгийг нь урагшлах гинжин хэлхээ (болзолт дүгнэлт), нөгөөг нь урвуу гинж (зорилтот дүгнэлт) гэж нэрлэдэг.

Энэ жишээнд шууд гаралтын хэлхээг ашигладаг.

Урьдчилсан хэсгийг (нөхцөл) эхлээд шинжилдэг үйлдвэрлэлийн системүүд бол нөхцөлт дүгнэлтийн архитектур гэж нэрлэгддэг. Ийм архитектурын шинжээчдийн системийн жишээ бол META-DENDRAL юм.

Шинжээчдийн системд ихэвчлэн ашиглагддаг архитектурын өөр төрөл бол зорилго-үр дүнгийн (үйл ажиллагааны дүгнэлт эсвэл үр дагавар-үр дүнгийн) үйлдвэрлэлийн систем юм. Жишээлбэл, дүрэм гэх мэт

гэж тайлбарлаж болно

"A, B, C-ийн логик холболт нь D гэсэн утгатай" эсвэл

"D-г батлахын тулд A, B, C-г тогтоох шаардлагатай."

Сүүлчийн тохиолдолд дедуктив дүгнэлтээр зорилгодоо хүрэх ёстой. Үүнийг хийхийн тулд дүрмийн үр дагаврыг судалж, зорилгодоо хүрэх боломжийг олгодог дүрмийг олох болно. Ийм дүрэм олдвол түүний бүх нөхцөл үнэн эсэхийг шалгадаг. Хэрэв нөхцөл үнэн бол гаралтыг идэвхжүүлнэ. Үгүй бол тохиромжтой бүтээгдэхүүний эрэл хайгуул үргэлжилж байна.

Үр дагаврын архитектур бүхий үйлдвэрлэлийн системийн хялбаршуулсан жишээг авч үзье. Энд байгаа үсгүүд нь мэдээллийн сангийн элементүүдийг заадаг бөгөөд хэрэв тэдгээр нь түүнд агуулагдаж байвал тэдгээрийг үнэн гэж үзнэ.

Дүрэм 1: A&B&C→D

Дүрэм 2: D&F→G

Дүрэм 3: A&J→G

Дүрэм 4: B→C

Дүрэм 5: F→B

Дүрэм 6: L→J

Дүрэм 7: G→H

Зорилго нь H-ийн үнэнийг гаргах явдал гэж бодъё. Эхний алхам бол H мэдээллийн санд байгаа эсэхийг шалгах явдал юм? Энэ тохиолдолд тийм биш тул систем нь баруун талд H байгаа дүрмүүдийг ашиглан H-ийн үнэнийг гаргахыг оролддог. Энэ бол дүрэм 7. Одоо систем G-ийн үнэнийг гаргах гэж оролддог, учир нь түүний үнэн нь H-ийн үнэнийг агуулна. Өгөгдлийн санг дахин шалгана: мэдээллийн санд G байхгүй тул дүрмийн туйл Баруун талд байгаа G зохион байгуулалттай. Ийм хэд хэдэн дүрэм байдаг (хоёр, гурван). "Зөрчилдөөнийг шийдвэрлэх" стратегийн хувьд бид дүрмийг тэргүүлэх ач холбогдол бүхий хамгийн бага тоотой дүрэм журмын дагуу эрэмбэлсэн гэж үзнэ.

Энэ тохиолдолд 2-р дүрмийг сонгосон тул одоо зорилго нь D ба F-ийн үнэнийг гаргах явдал юм. Үүнийг хийхийн тулд А нь үнэн (мэдээллийн санд байгаа тул), В үнэн (доор) гэдгийг харуулахад хангалттай. дүрмийн 5-д), C нь үнэн (4-р дүрмийн дагуу). D ба F-ийн үнэн нь батлагдсан тул 2-р дүрмээс G-ийн үнэн, Г-ийн үнэнээс Н-ийн үнэн (7-р дүрэм) гарч ирнэ. Ийнхүү зорилгодоо хүрлээ. Үнэн болох нь батлагдсан элементүүдийг мэдээллийн санд нэмдэг. Энэ тохиолдолд эдгээр нь H, G, D, C.V элементүүд юм.

Фрейм ба семантик сүлжээний талаархи дүгнэлт.

Фрейм дээрх гаралт.

Хүрээний өгөгдлийн бүтэц.

Фреймийн систем дэх гаралтын талаар хэлэлцэхээс өмнө фреймийн өгөгдлийн бүтцийг нарийвчлан авч үзье.

Фреймийн систем нь шаталсан бүтэц бөгөөд зангилаа нь тодорхой өгөгдлийн бүтэцтэй фреймүүд юм.

1. Хүрээний нэр.Энэ нь фреймд оноосон танигч юм. Хүрээ нь өгөгдсөн хүрээний системд өвөрмөц нэртэй байх ёстой (өвөрмөц нэр). Фрейм бүр нь дурын тооны слотуудаас бүрдэх ба тэдгээрийн цөөхөн хэдэн хэсгийг систем өөрөө тодорхой функцийг гүйцэтгэхийн тулд тодорхойлдог бол үлдсэн хэсгийг нь хэрэглэгч өөрөө тодорхойлдог. Үүнд хүрээг харуулсан үүр - энэ хүрээний эцэг эх; хүүхдийн хүрээ заагч үүр, энэ нь хүүхдийн хүрээ заагчуудын жагсаалт; хэрэглэгчийн нэр, тодорхойлсон огноо, өөрчлөлт оруулсан огноо, тайлбарын хувь болон бусад үүрийг оруулах үүр. Слот бүр нь эргээд тодорхой өгөгдлийн бүтцээр илэрхийлэгддэг.

2. Слотын нэр.Энэ нь үүрэнд томилогдсон танигч юм; оролт нь хамаарах хүрээндээ өвөрмөц нэртэй байх ёстой. Ихэвчлэн үүрний нэр нь ямар ч утгагүй бөгөөд зөвхөн энэ үүрний таних тэмдэг болдог боловч зарим тохиолдолд энэ нь тодорхой утгатай байж болно. Эдгээр нэрс нь: хандлага; шууд хүүхдийн хүрээ заагч; хүрээ тодорхойлсон огноо; хүрээг өөрчлөх огноо гэх мэт.

3. Өв залгамжлах заагч.Эдгээр заагч нь хийсвэр-бетон харилцаанд суурилсан шаталсан төрлийн харилцаанд суурилсан шаталсан хэлбэрийн хүрээний системд л хамаатай. Тэд дээд түвшний хүрээн дэх үүрүүдийн талаарх ямар шинж чанарын мэдээллийг доод түвшний хүрээн дэх ижил нэртэй слотууд өвлөн авдгийг харуулдаг.

4. Өгөгдлийн төрлийн үзүүлэлт (слотын шинж чанарууд).Слот нь тоон утгатай, тоон утгатай эсвэл өөр фрейм рүү заагч болж байгааг илтгэнэ (өөрөөр хэлбэл энэ нь хүрээний нэрийг харуулдаг). Өгөгдлийн төрөлд заагч, бүхэл тоо, бодит, логик, хавсаргасан процедур, текст, жагсаалт, хүснэгт, илэрхийлэл гэх мэт орно.

5. Слотын үнэ цэнэ.Слотын утгыг энд оруулна. Слотын утга нь тухайн слотын заасан өгөгдлийн төрөлтэй тохирч байх ёстой бөгөөд өв залгамжлалын нөхцөл хангагдсан байх ёстой.

6. Процедур -демон. Дараах төрлийн процедурууд байдаг - демонууд: хэрэв шаардлагатай бол, өөрчилсөн бол, нэмсэн бол, устгасан бол.

Демон нь тодорхой нөхцөл хангагдсан үед автоматаар эхлүүлэх процедурыг зааж өгдөг. Тэдгээр. демоны төлөвийн тухай if хэллэгийн нөхцөлт хэсэг дэх атрибут нь утгыг өөрчлөх үед. Процедурууд - Слотоос өгөгдөл нэмэх эсвэл хасах оролдлого хийх үед демонууд идэвхждэг (анхдагч). Харгалзах үүрэнд хандах үед дэмонууд эхэлдэг. Жишээлбэл, утгыг нь слот руу нэвтрэх үед тохируулаагүй бол if-necessary демоныг ажиллуулна; if-added нь утгыг үүрэнд орлуулах үед идэвхждэг; Слотын утгыг арилгах үед if-remote ажиллуулна. Нэмж дурдахад демон нь хавсаргасан процедурын нэг төрөл юм.

7. Хавсаргасан журам (процедур - үйлчлэгч). Slot утгыг процедурын төрлийн програм болгон ашиглаж болно албан ёсны(LISP хэл дээр) болон арга(Smalltalk хэлээр). Энэ тохиолдолд хавсаргасан процедурыг өөр фреймээс дамжуулсан мессежээр эсвэл фрейм үүсгэх үед хэрэглэгчийн заасан нөхцөл хангагдсан үед өдөөгддөг.

Мэдлэгийг хүрээгээр илэрхийлэх загварууд нь процедурын болон тунхаглалын мэдлэгийг нэгтгэдэг гэж хэлэхэд бид хавсаргасан процедурыг процедурын үнэ цэнэ гэж үздэг. Түүнчлэн фрейм бүхий мэдлэгийг илэрхийлэх хэл нь гаралтын хяналтын тусгай механизмгүй тул хэрэглэгч хавсаргасан процедурыг ашиглан энэ механизмыг хэрэгжүүлэх ёстой.

Хүрээний систем дэх гаралт.

Хүрээний хандлагын хүрээнд систем дэх мэдлэгийг хэвшмэл ойлголтын талаархи мэдээллийг (жишээ нь тухайн объект, нөхцөл байдлын зарим ерөнхий шинж чанарын тухай) агуулсан тусдаа мэдлэгийн кластер эсвэл дэд бүтэц хэлбэрээр танилцуулдаг гэж үздэг. Энэ таамаглалаар системийн нөхцөл байдлыг ойлгох нь авч үзэж буй нөхцөл байдлыг хамгийн сайн дүрслэхийн тулд хуримтлагдсан бүтцийн жагсаалтаас хайхыг хэлнэ. Тохиромжгүй тохиолдолд шинэ фрейм хайж, үйл явц үргэлжилнэ.

Тиймээс бид хүрээний системд тохиолддог гурван үндсэн процессыг ялгаж салгаж болно.

1. Frame instance үүсгэх. Хүрээний жишээг үүсгэхийн тулд та тохирох хүрээ олж, түүний үүрийг авч үзэж буй нөхцөл байдлын онцлогийг тодорхойлсон мэдээллээр дүүргэх хэрэгтэй. Слотуудыг бөглөхийн тулд үүрний боломжит "дүүргэгч" -ийг хэрхэн олох талаар тусгай мэдээллийг ашигладаг. Энэ мэдээллийг ихэвчлэн процедурын хэлбэрээр хадгалдаг.

2. Хүрээг идэвхжүүлэх. Тухайн нөхцөл байдлыг дүрслэхэд тохиромжтой гэж үзвэл хүрээ нь дэлхийн үйл явцаар идэвхждэг. Хэрэв хүрээнүүдийн агуулга болон авч үзэж буй нөхцөл байдлын онцлог шинж чанаруудын хооронд хэт их ялгаа илэрсэн эсвэл тэдгээр нь хангалттай ноцтой шинж чанартай бол өөр, илүү тохиромжтой хүрээ хайх ажлыг зохион байгуулдаг. Энэ тохиолдолд "татгалзсан" хүрээ нь үүний оронд аль хүрээг судлах ёстойг зааж өгсөн байж болно (жишээлбэл, илүү ерөнхий эсвэл эсрэгээр илүү нарийн мэргэжлийн). Шинэ нэр дэвшигчдийг авч үзэхдээ "татгалзсан" хүрээний зайг бөглөхөд ашигласан зарим өгөгдлийг ашиглаж болно.

3. Дүгнэлтийн зохион байгуулалт нь фрэймийн сүлжээн дэх идэвхжүүлэлтийн дараалсан хайлтаас бүрдэх бөгөөд хамгийн тохиромжтойг олж, түүний үндсэн дээр фреймийн жишээг бүтээх хүртэл.

T. Winograd онд фрэйм ​​дэх тунхаглалын болон процедурын төлөөллийн давуу талыг хослуулахыг санал болгосон. Түүний саналын мөн чанар нь фрейм ашиглан тэдгээрийг шууд төлөөлөх чиг үүргийн талаархи мэдлэгийг тунхаг хэлбэрээр, харин фрейм ашиглах талаархи мэдлэгийг процедурын хэлбэрээр хадгалах явдал юм.

Ялангуяа процедур нь дараах асуултуудад хариулах боломжийг олгодог мэдлэгийг хадгалах боломжтой.

1. Хүрээг хэзээ идэвхжүүлэх вэ? "Чөтгөрүүд"-ийн нэгэн адил фрэйм ​​нь тохирох нөхцөл байдлыг хүлээн зөвшөөрвөл өөрөө идэвхжиж болно.

3. Хэзээ бөглөх ёстой вэ - дуудлага хийх үед эсвэл дараа нь шаардлагатай бол?

Эдгээр чиг үүргийн хэрэгжилтийг хавсаргасан журамд хуваарилж болно. Процедурууд нь зайг бөглөхөд шаардлагатай мэдээллийг олоход чиглэсэн эвристикийг хэрэгжүүлэх боломжтой.

Тодорхой бус байдал.

Шийдвэр гаргагчид байдаг мэдээллийн нийтлэг шинж чанаруудын нэг нь түүний төгс бус байдал юм. Мэдээлэл нь бүрэн бус, зөрчилтэй, тодорхой бус, найдваргүй, тодорхой бус, санамсаргүй эсвэл эдгээр тайлбаруудын янз бүрийн хослол байж болно. Өөрөөр хэлбэл, мэдээлэл нь асуудлыг шийдвэрлэхэд бүрэн тохиромжгүй байдаг. Гэсэн хэдий ч шинжээч эдгээр дутагдлыг даван туулж, ихэвчлэн сайн дүгнэлт, шийдвэр гаргаж чаддаг. Ухаалаг DSS нь тодорхойгүй байдлыг даван туулж, үндэслэлтэй дүгнэлт хийх чадвартай байх ёстой.

Үндсэндээ ухаалаг DSS-ийн тодорхой бус мэдлэгийн дөрвөн эх сурвалжийг тодорхойлсон: үл мэдэгдэх өгөгдөл, тодорхой бус хэл, далд утга агуулга, янз бүрийн мэргэжилтнүүдийн үзэл бодлыг нэгтгэхтэй холбоотой бэрхшээлүүд.

Хэдийгээр тодорхойгүй байдал бодит ертөнцөд өргөн тархсан боловч практик AI системд үүнийг зохицуулах нь нэлээд хязгаарлагдмал байдаг.

Тодорхойгүй байдал бол ноцтой асуудал юм. Үүнийг анхааралдаа авахаас зайлсхийх оролдлого, түүнтэй ажиллах боломжуудыг ухамсарлах нь ухаалаг DSS-ийг хөгжүүлэхэд хамгийн сайн стратеги болж чадахгүй.

Тиймээс тодорхойгүй байдлыг шийдвэрлэх арга барилыг сайжруулах шаардлагатай байна.

Ухаалаг DSS болон ES нь тодорхойгүй байдлыг удирдах чадвартай байх ёстой, учир нь Бодит ертөнцийн аливаа сэдвийн талбар нь буруу мэдлэгийг агуулдаг бөгөөд та бүрэн бус, зөрчилтэй эсвэл бүр дутуу өгөгдлүүдийг даван туулах хэрэгтэй. Ухаалаг болон шинжээчдийн систем дэх тодорхойгүй байдлыг шийдвэрлэх янз бүрийн аргуудыг боловсруулсан. Бид тодорхойгүй байдлын менежментийн хамгийн алдартай аргуудыг авч үзэх болно: Байесийн магадлалын үндэслэл ба түүний өргөтгөлүүд, тодорхой байдлын онол, бүдэг логик.

Магадлалын дүгнэлт.

Магадлалын хандлага.

Санамсаргүй (эсвэл магадлалын) тодорхойгүй байдал нь үйл явдлын санамсаргүй байдал, жишээлбэл, эдийн засгийн нөхцөл байдал, объектын нөхцөл байдал, тоног төхөөрөмжийн эвдрэлийн санамсаргүй байдал болон бусад хүчин зүйлүүдтэй холбоотой байж болно. Ухаалаг DSS зохион бүтээх, мэдлэгийн суурьтай ажлыг зохион байгуулахдаа олон мэдлэг, баримт, үйл явдал, өгөгдлийн найдвартай, найдвартай байдлын түвшин харилцан адилгүй байдаг. Стохастик тодорхойгүй байдлын нөхцөлд үндэслэлийг албан ёсны болгохын тулд магадлалын онол ба статик шийдлүүдийг ашигладаг. Шийдлийн хувилбарын тодорхой таамаглалын магадлалыг тооцоолохын тулд тодорхойгүй байдлыг харгалзан үндэслэлийг хэрэгжүүлэхдээ ашиглах боломжтой. Байесийн хандлага.

Байесийн арга ба Бэйсийн дүрмийн үндсэн заалтуудыг авч үзье.

Болъё Абодит байдал дээрх үйл явдал бөгөөд IN- өөр үйл явдал. Ийм үйл явдал болсон гэж бодъё АТэгээд INбие биенээ үгүйсгэхгүй, харин нөгөө нь өөрийгөө илэрхийлэх үед нөхцөлт байдлаар үүсдэг. Үйл явдал болох магадлал Аүйл явдал тохиолдвол болно IN, дуудсан нөхцөлт магадлал.

Нөхцөлт магадлалыг математикийн хувьд гэж тэмдэглэнэ П(А|B), босоо зураас нь "болсон"-ыг илэрхийлэх ба бүрэн магадлалын илэрхийлэл нь "Үйл явдал тохиолдох нөхцөлт магадлал" гэж тайлбарлагддаг. А IN».

p(А|B)=(6.1)

Боломжит хамтарсан илрэлүүдийн тоо АТэгээд IN, эсвэл магадлал АТэгээд INхамтдаа тохиолдох болно, гэж нэрлэдэг хамтарсан магадлал АТэгээд IN.

Математикийн хувьд энэ нь харагдаж байна P(AÇB).

Боломжит илрэлүүдийн тоо INмагадлал юм IN, P(B), Тэгээд

(6.2)

Мөн үйл явдал тохиолдох нөхцөлт магадлал INүйл явдал болсон тохиолдолд Атодорхойлсон

(6.3)

p(BÇA) =p(B|A)´p(A)(6.4)

Хамтарсан магадлал нь солигддог тул

p(AÇB)= p(BÇ A)

Тиймээс

p(AÇB) =p(B|A)´P(A)(6.5)

(6.2)-д (6.5)-ыг орлуулснаар дараах тэгшитгэл гарна.

(6.6)

p(A|B) Аүйл явдал болсон тохиолдолд IN;

p(B|A)– үйл явдал болох нөхцөлт магадлал INүйл явдал болсон тохиолдолд А;

p(A) A;

p(B)- үйл явдал болох магадлал IN.

Тэгшитгэл (6.6) нь энэ дүрмийг санал болгосон 18-р зууны Британийн математикч Томас Бэйсийн нэрээр нэрлэгдсэн Бэйсийн дүрэм (эсвэл томьёо) гэж нэрлэгддэг.

Үйл явдал болсон гэж үзвэл нөхцөлт магадлалын тухай ойлголтыг санал болгодог Аүйл явдлаас хамааралтай байсан IN. Энэ зарчмыг үйл явдал болсон тохиолдолд сунгаж болно Атодорхой тооны үл нийцэх үйл явдлуудаас хамаарна B 1, B 2, ..., B n.

Дараах багц тэгшитгэлийг (6.2) -аас гаргаж болно.

p(AÇB 1) =p(A|B 1)´p(B 1)

p(AÇB 2) =p(A|B 2)´p(B 2)

p(АÇВ n) =p(А|В n)´p(В n)

Эсвэл нэгтгэсний дараа.

(6.7)

Хэрэв (6.7)-ыг B i үйл явдлын бүрэн жагсаалтад нэгтгэвэл бид олж авна

(6.8)

Энэ нь дараах нөхцөлт магадлалын тэгшитгэлд хүргэдэг, i.e. P(A)Нийт магадлалын томъёогоор илэрхийлнэ:

(6.9)

Хэрэв үйл явдлын илрэл Азөвхөн бие биенээ үгүйсгэсэн хоёр үйл явдлаас хамаарна, жишээ нь INТэгээд БАЙХГҮЙ БАЙНА, дараа нь (6.9) дараах байдалтай харагдана.

p(A)=p(A|B)´p(B)+p(A\ØB)´p(ØB) (6.10)

Энд Ø нь логик биш юм.

p(B)=p(B|A)´p(A)+p(B\ØA)´p(ØA) (6.11)

Одоо (6.11)-ийг Байесийн томъёонд (6.6) орлуулъя

Тэгшитгэл (6.12) нь ухаалаг систем дэх тодорхойгүй байдлыг удирдахад магадлалын онолыг ашиглах үндэслэлийг өгдөг.

Байесийн дүгнэлт.

(6.12) тэгшитгэлийг ашигласнаар бид магадлалын онолоос ухаалаг систем рүү анхаарлаа хандуулж чадна. Мэдлэгийн сан дахь бүх дүрмийг дараах хэлбэрээр үзүүлэв гэж бодъё.

Хэрэв Нүнэн

Дараа нь ХАМТүнэн (магадлалтай Р}.

Энэ дүрэм нь хэрэв үйл явдал бол Нтохиолдвол тухайн үйл явдал болох магадлал ХАМТтохиолдох болно Р.

Үйл явдал болвол яах вэ ХАМТболсон, гэхдээ үйл явдал болсон эсэхийг бид мэдэхгүй Н? Үйл явдал болох магадлалыг тооцоолох боломжийг авч үзье Нбас болсон.

Тэгшитгэл (6.12) нь үүнийг хийх боломжийг бидэнд олгодог. Бид зүгээр л ашигладаг НТэгээд ХАМТоронд нь АТэгээд IN. Ухаалаг системд Нихэвчлэн таамаглалыг илэрхийлдэг ба ХАМТ- эдгээр таамаглалыг батлах нотолгоо.

Ийнхүү таамаглал, нотлох баримтаар илэрхийлсэн тэгшитгэл (6.12) дараах байдалтай байна

p(H) – априори (болзолгүй) магадлалгэсэн таамаглал Нүнэн;

p(C|H)– таамаглал үүсэх магадлал Нүнэн бол нотлох баримтын үр дүн байх болно ХАМТ;

p(ØН)- таамаглал болох априори (болзолгүй) магадлал Нхудал;

p(С|ØН)- нотлох баримт олох магадлал ХАМТтаамаглал байсан ч гэсэн Нхудлаа.

Тэгшитгэл (6.13) нь таамаглалын магадлалыг харуулж байна Н, p(H)аливаа нотлох баримтыг шалгахаас өмнө тодорхойлох ёстой.

Ухаалаг DSS-д мэргэжилтнүүдийн тавьсан асуудлыг шийдвэрлэхийн тулд магадлал шаардагдана. Шинжээч нь боломжит таамаглалын урьдчилсан магадлалыг тодорхойлдог p(H)Тэгээд p(ØН), түүнчлэн ажиглагдсан нотлох баримтын нөхцөлт магадлал ХАМТ, хэрэв таамаглал бол Нүнэн, p(C|H), хэрэв таамаглал бол Нхудлаа p(С|ØН). Хэрэглэгчид ажиглагдсан нотлох баримтын талаар мэдээлэл өгч, ухаалаг систем тооцоолдог p(C|H)таамаглалын хувьд Нхэрэглэгчийн өгсөн нотлох баримтын дагуу ХАМТ. Магадлал p(C|H)дуудсан арын магадлалтаамаглал Нажиглагдахуйц нотлох баримттай ХАМТ.

Энгийн нотлох баримт дээр үндэслэн шинжээчийн нөхцөл байдлыг авч үзье ХАМТ, энгийн таамаглалыг сонгох боломжгүй, харин олон таамаглал дэвшүүлдэг N 1, N 2,…, N т.Эсвэл арвин нотлох баримт байгаа үед С 1, С 2, …, С nмөн шинжээч олон таамаглал дэвшүүлдэг.

Бид олон тооны таамаглалыг харгалзан (6.13) тэгшитгэлийг нэгтгэж болно N 1, N 2, …, N тмөн олон тооны гэрчлэл С 1, С 2, …, С n. Гэхдээ таамаглал, түүнчлэн нотолгоо нь бие биенээ үгүйсгэх ёстой.

Энгийн нотолгооны хувьд C ба олон таамаглал N 1, N 2, …, N тдараах:

(6.14)

Олон тооны нотлох баримтын хувьд С 1, С 2, …, С nболон олон тооны таамаглалууд N 1, N 2, …, N тдараах:

(6.15)

(6.15) тэгшитгэлийг хэрэглэхэд бүх таамаглалд нотлох баримтын боломжит бүх хослолын нөхцөлт магадлалыг авах шаардлагатай. Энэ шаардлага нь мэргэжилтэнд асар их ачаалал өгч, түүний ажлыг бараг боломжгүй болгодог.

Тиймээс ухаалаг DSS болон ES-д олон нотлох баримтын хамтарсан нөлөөллийн нарийн мэдрэмжийг анхаарч үзэх ёсгүй, гэхдээ янз бүрийн нотлох баримтуудын хооронд нөхцөлт бие даасан байдлыг зөвшөөрөх ёстой.

Үүний үр дүнд хэрэгжих боломжгүй тэгшитгэлийн оронд (6.15) бид олж авна

Ухаалаг систем нь бүх арын магадлалыг тооцоолж, эцэст нь үнэн байж болох таамаглалыг хэрхэн эрэмбэлдэгийг тодруулахын тулд энгийн жишээг авч үзье.

Гурван болзолт бие даасан нотлох баримттай шинжээч гэж бодъё C 1, C 2Тэгээд C 3, бие биенээ үгүйсгэсэн гурван таамаглалыг бий болгодог N 1, N 2Тэгээд N 3мөн эдгээр таамаглалуудын урьдчилсан магадлалыг өгдөг - p(H 1), p(H 2)Тэгээд p(H 3)тус тус. Мэргэжилтэн мөн бүх боломжит таамаглалуудын тэмдэглэсэн нотлох баримт бүрийн нөхцөлт магадлалыг тодорхойлдог.

Хүснэгт 6.1. шинжээчийн өгсөн априори болон нөхцөлт магадлалыг үзүүлэв.

Хүснэгт 6.1.

Приори ба нөхцөлт магадлал.

Эхлээд бид C 3 нотолгоог ажиглалаа гэж бодъё. Ухаалаг систем нь (6.14) тэгшитгэлийг ашиглан бүх таамаглалын арын магадлалыг тооцдог.

Тиймээс

Эндээс харахад нотлох баримтыг ажигласны дараа C 3, таамаглалд итгэх итгэл H 2ба таамаглалд итгэх итгэлтэй тэнцүү болно H 1. H 3 таамаглалд итгэх итгэл нэмэгдэж, тэр ч байтугай таамаглалд итгэх итгэл ойролцоогоор хүрдэг. H 1Тэгээд H 2.

Одоо бид нотлох баримтыг ажиглаж байна гэж бодъё C 1. Дараах магадлалыг (6.16) тэгшитгэлийг ашиглан тооцоолно.

Тиймээс

Таамаглал H 2одоо хамгийн их магадлалтай гэж үздэг, учир нь таамаглалд итгэх итгэл эрс буурч байна.

Нотлох баримтыг үзсэний дараа C 2 Smart DSS нь бүх таамаглалуудын хамгийн сүүлийн үеийн магадлалыг тооцдог.

Тиймээс

Хэдийгээр шинжээчийн санал болгосон анхны зэрэглэл нь байсан H 1, H 2 ба H 3, зөвхөн таамаглал H 1Тэгээд N 3бүх нотлох баримтын дараа хэлэлцэхээр үлдсэн ( C 1, C 2Тэгээд C 3) ажиглагдсан. Таамаглал H 2одоо бүрмөсөн устгаж болно.

Таамаглал гэдгийг анхаарна уу N 3одоо таамаглалаас илүүд үзэж байна H 1.

Байесийн логик дээр суурилсан аргуудыг ашиглах үед нөхцөлт магадлалыг тодорхойлоход шаардлагатай олон тооны өгөгдлийг олж авахад бэрхшээлтэй байдаг.

Практикт ажиглалтын бие даасан байдлын талаар таамаглал дэвшүүлдэг бөгөөд энэ нь статик загварын хатуу байдалд нөлөөлдөг бололтой. Үүнтэй төстэй таамаглалууд дээр санал болгосон Байесийн аргад суурилсан аргад байдаг.

Дуда, Харт, Ниэлсон нар мэдлэгийн инженерчлэлийн дүгнэлт хийх Бэйсийн томъёог өөрчилсөн бөгөөд субьект Bayes хэмээх дүгнэлтийн аргыг санал болгосон.

Энэ аргын гол зорилгыг тэд PROSPECTOR экспертийн системд амжилттай хэрэгжүүлсэн.

Ойролцоо үндэслэл.

Санал тооцооллын сонгодог онолд “Хэрэв А, Дараа нь IN", Хаана АТэгээд IN– саналын хувьсагч (саналын хувьсагч нь зөвхөн үнэн эсвэл худал байдлаар нь авч үздэг өгүүлбэрийн хувьсагч юм) гэж бичсэн. A®B, энд (®) далд утга нь үнэний хүснэгтээр тодорхойлогддог холбогч гэж тооцогддог.

Тиймээс А®ВºØАВ (6.17)

Тэр утгаараа A®B(A гэсэн үг Б) ба ØАÚВ(А эсвэл В биш) ижил үнэний хүснэгттэй байна. Манай тохиолдолд илүү чухал тодорхойгүй мэдэгдэл"Хэрэв А, Дараа нь IN", товчхон A®B, аль нь А(өмнөх үе) ба IN(үр дагавар) – саналын хувьсагч биш харин тодорхой бус олонлогууд (“санал” гэдэг нь өгүүлбэр, илэрхийлэл, мэдэгдэл гэсэн үг).

Мэдээллийн ердийн жишээ:

Хэрэв "том" бол "жижиг"

Хэрэв "гулгамтгай" бол "аюултай;"

Эдгээр нь өгүүлбэрийн товчлол юм:

Хэрэв x "том" бол y нь "жижиг";

Хэрэв зам "халтиргаатай" бол жолоодох нь "аюултай" болно.

Үндсэндээ энэ төрлийн өгүүлбэрүүд нь тодорхойгүй хоёр хувьсагчийн хоорондын хамаарлыг тодорхойлдог. Энэ нь тодорхой бус хэллэгийг (6.17) гэсэн утгаараа холбогч гэж бус (5.25) гэсэн утгаараа бүдэг бадаг хамаарал гэж тодорхойлох ёстой гэсэн үг юм.

Энд эхлээд тодорхойлохыг зөвлөж байна Декарт бүтээгдэхүүнхоёр бүдэг олонлог.

Болъё А- сэтгэхүйн домэйны тодорхой бус дэд олонлог Уорхи INнь үндэслэлийн өөр домэйны тодорхой бус дэд олонлог юм V. Дараа нь декартын үржвэр АТэгээд IN, тэмдэглэсэн А´В, дараах байдлаар тодорхойлогддог

(6.18)

Хаана U´Vолонлогуудын декарт үржвэр гэсэн үг УТэгээд В, өөрөөр хэлбэл

Хэзээ гэдгийг анхаарна уу АТэгээд IN– бүдэг биш, (6.18) нь олонлогуудын декартын үржвэрийн ердийн тодорхойлолт болж хувирсан.

Өөрөөр хэлбэл (6.18) гэсэн үг А´Вэрэмбэлэгдсэн хосуудын тодорхой бус багц ( у, в), , гишүүнчлэлийн зэрэгтэй (у, v)руу (A´B),томъёогоор өгөгдсөн. Энэ утгаар А´Втодорхойгүй харилцаа бий УТэгээд В.

Жишээ 6.1. Болъё

U=1+2(6.19)

V=1+2+3 (6.20)

A=1/1+0.8/2 (6.21)

B=0.6/1+0.9/2+1/3 (6.22)

A´B=0.6/(1.1)+0.9/(1.2)+1/(1.3)+0.6/(2.1)+0.8/(2.2 )+0.8/(2.3) (6.23)

(6.17)-д тодорхойлсон хамаарлыг харилцааны матрицаар илэрхийлж болно

Хэлбэрийн бүдэг бадаг мэдэгдлийн утга “Хэрэв А, Дараа нь IN"Хэрэв бид үүнийг болзолт мэдэгдлийн онцгой тохиолдол гэж үзвэл тодорхой болно. "Хэрэв А, Дараа нь IN, Үгүй бол ХАМТ", Хаана А, INТэгээд ХАМТ– тодорхой бус дэд олонлогууд, магадгүй өөр өөр талбарууд УТэгээд В, тус тус.

Декартын бүтээгдэхүүний хувьд сүүлчийн өгүүлбэрийг дараах байдлаар тодорхойлно.

Хэрэв А, Дараа нь IN, Үгүй бол ХАМТ (6.25)

Энд + гэдэг нь бүдэг олонлогуудын нэгдлийг илэрхийлнэ А´ВТэгээд (ØА´С).

Бүрхэг олонлогт материаллаг нөлөөллийн тухай ойлголтыг ерөнхийд нь илэрхийлэхийн тулд гэж бодъё УТэгээд В– хоёр өөр байж болох бүх нийтийн багц, ба А, БТэгээд ХАМТ– олонлогийн тодорхой бус дэд олонлогууд У, ВТэгээд Втус тус.

Эхлээд мэдэгдлийн утгыг тодорхойлъё

Хэрэв А, Дараа нь IN, Үгүй бол ХАМТ, дараа нь тодорхойлно

Хэрэв А, Дараа нь INмэдэгдлийн онцгой тохиолдол болгон If А, Дараа нь IN, Үгүй бол ХАМТ.

Тодорхойлолт.Хэрэв мэдэгдэл А, Дараа нь IN, Үгүй бол ХАМТдотор хоёртын тодорхой бус хамаарал байдаг U´V, дараах байдлаар тодорхойлсон:

Хэрэв A бол B, Үгүй бол C=A´B+ØA´C (6.26)

Өөрөөр хэлбэл, хэрэв А, БТэгээд ХАМТ- дахь нэгдмэл бүдэг харилцаа У, ВТэгээд В, дараа нь Хэрэв А, Дараа нь IN, Үгүй бол ХАМТ– хоёртын тодорхой бус хамаарал U´V, энэ нь декартын бүтээгдэхүүний нэгдэл юм АТэгээд IN(5.23) ба үгүйсгэлийн декартын үржвэр АТэгээд ХАМТ.

Дараагийн мэдэгдэл Хэрэв А, Дараа нь INгэсэн мэдэгдлийн онцгой тохиолдол гэж үзэж болно If А, Дараа нь IN, Үгүй бол ТаамаглалаарЮу ХАМТ- бүрэн багц В.

Тэр. Хэрэв А, Дараа нь INХэрэв А, Дараа нь IN, Үгүй бол V=А´В+ØА´V(6.27)

Үндсэндээ энэ нь If гэсэн мэдэгдлийн тайлбартай дүйцэхүйц юм А, Дараа нь INмэдэгдэл Хэрэв А, Дараа нь IN, Үгүй бол хайхрамжгүй.

Жишээ 6.2. Зураг (6.26) ба (6.27)

Ингэж жүжиглэе

A=жижиг=1/1+0.4/2

B=том=0.4/2+1/3

C=том биш=1/1+0.6/2

Дараа нь Хэрэв А, Дараа нь IN, Үгүй бол С=(1/1+0.4/2)´(0.4/2+1/3)+(0.6/2+1/3)´ (1/1+0.6/2)= 0.4/(1.2)+1/ (1.3)+0.6/(2.1)+0.6/(2.2)+0.4/(2.3)+1/ (3.1)+0.6/(3.2)

Харьцааны матрицаар юуг илэрхийлж болох вэ

Хэрэв А, Дараа нь IN, Үгүй бол C=

Үүний нэгэн адил

Хэрэв А, Дараа нь В=(1/1+0.4/2)´(0.4/2+1/3)+(0.6/2+1/3)´(1/1+1/2+1/3 ) =0.4/(1.2) )+1/(1.3)+0.6/(2.1)+0.6/(2.2)+0.6/(2.3)+ 1/(3,1)+1/(3,2)+1/(3,3)

Эсвэл түүнтэй адилтгах

Хэрэв А, Дараа нь B=

Мэдрэлийн сүлжээн дэх дүгнэлт.

Хопфилд сүлжээ.

Хопфилд эрчим хүчний функцийг урсгал сүлжээг бий болгох, тэдгээрийн динамикийг ойлгох хэрэгсэл болгон ашигласан. Хопфилдийн албан ёсны хэлбэр нь мэдээллийг динамик тогтвортой татагч болгон хадгалах зарчмыг тодорхой болгож, ассоциатив санах ой болон комбинаторын оновчлолын асуудлыг шийдвэрлэхэд давтагдах сүлжээг ашиглахыг дэлгэрүүлсэн.

Сүлжээний төлөвийг динамикаар өөрчлөхийг дор хаяж хоёр аргаар хийж болно: синхрон ба асинхрон. Эхний тохиолдолд бүх элементүүдийг үе шат бүрт нэгэн зэрэг өөрчилдөг, хоёрдугаарт, цаг мөч бүрт нэг элементийг сонгож, боловсруулдаг. Энэ элементийг санамсаргүй байдлаар сонгож болно. Эрчим хүчний функцийн гол шинж чанар нь тэгшитгэлийн дагуу сүлжээний төлөв байдлын хувьслын явцад буурч, орон нутгийн хамгийн бага хэмжээнд (трактор) хүрдэг бөгөөд энэ нь тогтмол энергийг хадгалж байдаг.

Ассоциатив санах ой

Хэрэв сүлжээнд хадгалагдсан загварууд нь татагч бол түүнийг ассоциатив санах ой болгон ашиглаж болно. Хадгалагдсан дээжийг татах хэсэгт байрлах аливаа жишээг сэргээхийн тулд заагч болгон ашиглаж болно.

Ассоциатив санах ой нь ихэвчлэн хоёр горимд ажилладаг: хадгалах болон сэргээх. Хадгалах горимд сүлжээн дэх холболтын жинг тодорхойлогддог бөгөөд ингэснээр татагч нар багцыг санаж байх болно p n- хэмжээст дээж ( x 1 , x 2 ,..., x p), үүнийг хадгалах ёстой. Хоёрдахь горимд оролтын жишээг сүлжээний анхны төлөв болгон ашигладаг бөгөөд дараа нь сүлжээ нь динамикийн дагуу өөрчлөгддөг. Сүлжээ тэнцвэрт байдалд хүрэх үед гаралтын хэв маягийг тогтооно.

Хэр олон жишээг онлайнаар хадгалах боломжтой nхоёртын элементүүд? Өөрөөр хэлбэл, сүлжээний хадгалах багтаамж хэд вэ? Энэ нь хязгаарлагдмал, учир нь сүлжээ нь nхоёртын элементүүд дээд тал нь байна 2нянз бүрийн мужууд, бүгдээрээ татагч биш. Түүнээс гадна бүх татагч нь ашигтай хэв маягийг хадгалж чаддаггүй. Хуурамч татагч нь дээжийг хадгалах боломжтой боловч сургалтын багцын жишээнээс ялгаатай.

Эрчим хүчийг багасгах. Хопфилдийн сүлжээ нь эрчим хүчээ багасгах чиглэлд хөгжиж байна. Энэ нь комбинаторын оновчлолын асуудлыг эрчим хүчийг багасгах бодлого болгон томъёолж чадвал тэдгээрийг шийдвэрлэх боломжийг олгодог. Ялангуяа аялагч худалдагчийн асуудлыг үүнтэй төстэй байдлаар томъёолж болно.

Хүснэгт 6.3-аас бусад сургалтын алгоритмуудыг дараах бүтээлүүдэд тайлбарласан болно: Адалин ба Мадалин, шугаман дискриминант шинжилгээ, Саммон проекц, үндсэн бүрэлдэхүүн хэсгийн шинжилгээ.

ANN боловсруулах үйл явц.

Хэдийгээр ANN үйл явц нь уламжлалт компьютерийн IC-ийн бүтцийн дизайны аргачлалтай төстэй боловч зарим үе шатууд нь мэдрэлийн сүлжээний хэрэглээнд зориулагдсан эсвэл нэмэлт хүчин зүйлтэй байдаг. Доор тайлбарласан үйл явцад мэдээллийн хэрэгцээг тодорхойлох, техник эдийн засгийн үндэслэлийг гаргах зэрэг системийг хөгжүүлэх урьдчилсан үе шатууд бүрэн дууссан гэж бид үзэж байна. Ийм алхамууд нь аливаа мэдээллийн системд нийтлэг байдаг.

Зурагт үзүүлсэн шиг. 6.8., ANN програм боловсруулах үйл явц нь есөн үе шаттай.

Асаалттай 1-р алхамСүлжээг сургах, турших зорилгоор өгөгдлийг цуглуулдаг.

ANN шийдлийг олж авахын тулд хийж буй даалгавар нь хүртээмжтэй бөгөөд энэ зорилгоор хангалттай өгөгдөл байгаа бөгөөд үүнийг олж авах боломжтой гэдгийг анхаарах нь чухал юм.

Асаалттай алхам 2Сургалтын өгөгдлийг тогтоож, сүлжээний гүйцэтгэлийг шалгах төлөвлөгөө гаргах ёстой.

Асаалттай 3-4 алхамСүлжээний бүтэц, сургалтын аргыг сонгосон. ANN хөгжүүлэх тусгай хэрэгслүүд байгаа эсэх нь ямар төрлийн мэдрэлийн сүлжээг бий болгохыг тодорхойлох боломжтой. Мэдрэлийн эсийн тодорхой тоо, давхаргын тоо нь чухал ач холбогдолтой.

Одоо байгаа мэдрэлийн сүлжээний загварууд нь сүлжээг хүссэн гүйцэтгэлийн түвшинд тохируулах параметрүүдтэй байдаг. 5-р алхам дахь үйл явцын нэг хэсэг нь сүлжээний жин ба параметрүүдийг эхлүүлэх бөгөөд гүйцэтгэлийн хариуг дагаж мөрддөг. Сургалтын үр нөлөө, үргэлжлэх хугацааг тодорхойлоход ихэвчлэн анхны үнэ цэнэ чухал байдаг. 6-р алхамын дараах процедур нь ашигласан өгөгдлийг мэдрэлийн сүлжээнд шаардлагатай төрөл, формат руу хөрвүүлдэг. Энэ нь программыг ашиглах гэсэн үг юм урьдчилсан эмчилгээөгөгдөл. Шаардлагатай үед мэдрэлийн сүлжээг тохь тухтай, үр дүнтэй давтан сургах зорилгоор өгөгдөл хадгалах, удирдах ажлыг зохион байгуулах ёстой. Түүнчлэн, ашигласан өгөгдлийг танилцуулж, зохион байгуулах арга нь ANN-ийн олж авсан үр дүнгийн үр ашиг, магадгүй үнэн зөвийг тодорхойлдог.

Асаалттай 7-8 алхамсургалт, туршилтыг сүлжээнд оролт, хүссэн гаралтыг үзүүлэх интервалын процесс хэлбэрээр явуулдаг.

Мэдрэлийн сүлжээ нь бодит гаралтыг тооцоолж, бодит гаралт нь хүссэн төлөвт тохирох хүртэл жинг тохируулдаг. Хүссэн гаралт ба тэдгээрийн оролттой харилцах харилцааг түүхэн өгөгдлөөс (1-р алхамд цуглуулсан мэдээллийн нэг хэсэг) олж авна.

Асаалттай алхам 9процессын явцад жингийн тогтвортой багцыг олж авдаг. Одоо сүлжээ нь хэвлэгдсэн оролтуудын хүссэн гаралтыг мөн сургалтын багц дээр хуулбарлах боломжтой. Мэдрэлийн сүлжээ нь бие даасан систем эсвэл өөр програм хангамжийн системийн нэг хэсэг болгон ашиглахад бэлэн байна.

Зураг.6.8.Хиймэл мэдрэлийн сүлжээг хөгжүүлэх, тохируулах үйл явцын дараалал.

“Сэдэв 4: Лекц 9: Үйлдвэрлэлийн системд дүгнэлт хийх, шийдэл хайх арга. Урагш ба арагш гинжин хэлхээнд суурилсан дүгнэлтийн аргууд. Үйлдвэрлэлийн явцад..."

Сахнюк П.А.

Сэдэв 4:

Лекц 9: Үйлдвэрлэлийн системд дүгнэлт гаргах, шийдлийг хайх арга.

Урагш ба арагш гинжин хэлхээнд суурилсан дүгнэлтийн аргууд.

Үйлдвэрлэлийн дүрслэлд мэдлэгийн талбарыг олонлогоор төлөөлдөг

үйлдвэрлэлийн дүрэм, өгөгдөл нь янз бүрийн баримтаар илэрхийлэгддэг

ТЭГВЭЛ,

Одоогийн нөхцөл байдал.

Дүгнэлтийн механизм нь мэдлэгийн санд хадгалагдсан дүрэм бүрийг баримттай харьцуулж,

Зураг 1. Шүдэнзний галын процедурын дагуу дүгнэлт хийх механизмын мөчлөг

Дүрмийн if хэсгийг баримттай тааруулах нь дүгнэлтийн гинжин хэлхээ үүсгэдэг. Дүгнэлт гаргахын тулд ES нь дүрмийг хэрхэн хэрэгжүүлдэгийг дүгнэлтийн хэлхээ харуулж байна. Гинжинд суурилсан дүгнэлтийн аргыг харуулахын тулд энгийн жишээг авч үзье.

Өгөгдлийн санд анх A, B, C, D, E баримтууд багтсан бол мэдлэгийн сан нь зөвхөн гурван дүрмийг агуулдаг гэж үзье.

Дүрэм 1. Y&D Z Дүрэм 2.

X&B&EY Дүрэм 3. AX Зураг дээрх гаралтын хэлхээ. 2. ES нь Z баримтыг гаргах дүрмийг хэрхэн хэрэгжүүлдгийг харуулсан.

Сахнюк П.А.

Зураг 2. Гаралтын гинжин хэлхээний жишээ.

Нэгдүгээрт, 3-р дүрэм нь нийтлэгдсэн А баримтын шинэ X баримтыг гаргахад түлхэц болно.

Дараа нь 2-р дүрмийг анх мэдэгдэж байсан В ба Е баримтаас Y баримтыг, мөн аль хэдийн мэдэгдэж байсан X баримтыг гаргаж авахын тулд 2-р дүрмийг хэрэгжүүлнэ. Эцэст нь Z дүгнэлтэд хүрэхийн тулд 1-р дүрэм анх мэдэгдэж байсан D баримт болон шинээр олж авсан Y баримтыг хэрэглэнэ.

ES нь тодорхой шийдвэрт хэрхэн хүрсэн талаар тайлбарлах өөрийн дүгнэлтийн хэлхээг тусгаж болно; Энэ нь түүний тайлбарлах эрх мэдлийн томоохон хэсэг юм.

Дүрмүүд хэзээ гарахыг дүгнэлтийн хөдөлгүүр шийдэх ёстой. Дүрмийг хэрэгжүүлэх хоёр үндсэн арга байдаг. Нэгийг нь урагшлах гинжин хэлхээ (болзолт дүгнэлт), нөгөөг нь урвуу гинж (зорилтот дүгнэлт) гэж нэрлэдэг.

Энэ жишээнд шууд гаралтын хэлхээг ашигладаг.

Урьдчилсан хэсгийг (нөхцөл) эхлээд шинжилдэг үйлдвэрлэлийн системүүд бол нөхцөлт дүгнэлтийн архитектур гэж нэрлэгддэг. Ийм архитектурын шинжээчдийн системийн жишээ бол META-DENDRAL юм.

Шинжээчдийн системд ихэвчлэн ашиглагддаг архитектурын өөр төрөл бол зорилго-үргэлжлэл (үйл ажиллагааны дүгнэлт эсвэл үр дагавар) үйлдвэрлэлийн систем юм. Жишээлбэл, A&B&CD хэлбэрийн дүрмийг “A, B, C-ийн логик холболт нь D гэсэн утгатай” эсвэл “D-г батлахын тулд A, B, C-г тогтоох ёстой” гэж тайлбарлаж болно.

Сүүлчийн тохиолдолд дедуктив дүгнэлтээр зорилгодоо хүрэх ёстой. Үүнийг хийхийн тулд дүрмийн үр дагаврыг судалж, зорилгодоо хүрэх боломжийг олгодог дүрмийг олох болно. Ийм дүрэм олдвол түүний бүх нөхцөл үнэн эсэхийг шалгадаг.

Хэрэв нөхцөл үнэн бол гаралтыг идэвхжүүлнэ. Үгүй бол тохиромжтой бүтээгдэхүүний эрэл хайгуул үргэлжилж байна.

Сахнюк П.А.

Үр дагаврын архитектур бүхий үйлдвэрлэлийн системийн хялбаршуулсан жишээг авч үзье. Энд байгаа үсгүүд нь мэдээллийн сангийн элементүүдийг заадаг бөгөөд хэрэв тэдгээр нь түүнд агуулагдаж байвал тэдгээрийг үнэн гэж үзнэ.

BD: AF Дүрэм 1: A&B&CD Дүрэм 2: D&FG Дүрэм 3: A&JG Дүрэм 4: МЭӨ 5 Дүрэм: FB Дүрэм 6: LJ Дүрэм 7: GH Зорилго нь H-ийн үнэнийг гаргах явдал гэж бодъё.

Юуны өмнө мэдээллийн санд H байгаа эсэхийг шалгадаг уу? Энэ тохиолдолд тийм биш тул систем нь баруун талд H байгаа дүрмүүдийг ашиглан H-ийн үнэнийг гаргахыг оролддог. Энэ бол дүрэм 7. Одоо систем G-ийн үнэнийг гаргах гэж оролддог, учир нь түүний үнэн нь H-ийн үнэнийг агуулна. Өгөгдлийн санг дахин шалгана: мэдээллийн санд G байхгүй тул дүрмийн туйл Баруун талд байгаа G зохион байгуулалттай. Ийм хэд хэдэн дүрэм байдаг (хоёр, гурван). "Зөрчилдөөнийг шийдвэрлэх" стратегийн хувьд бид дүрмийг тэргүүлэх ач холбогдол бүхий хамгийн бага тоотой дүрэм журмын дагуу эрэмбэлсэн гэж үзнэ.

Энэ тохиолдолд 2-р дүрмийг сонгосон тул одоо зорилго нь D ба F-ийн үнэнийг гаргах явдал юм. Үүнийг хийхийн тулд А нь үнэн (мэдээллийн санд байгаа тул), В үнэн (доор) гэдгийг харуулахад хангалттай. дүрмийн 5-д), C нь үнэн (4-р дүрмийн дагуу). D ба F-ийн үнэн нь батлагдсан тул 2-р дүрмээс Г-ийн үнэн, Г-ийн үнэнээс Н-ийн үнэн гарч ирнэ (7-р дүрэм). Ийнхүү зорилгодоо хүрлээ. Үнэн болох нь батлагдсан элементүүдийг мэдээллийн санд нэмдэг. Энэ тохиолдолд эдгээр нь H, G, D, S.V элементүүд юм.

Зорилтот дүгнэлтийн архитектурын жишээнд MYCIN орно.

Төрийн орон зайд шийдлийг олох ерөнхий аргууд.

Тооцооллын аргууд. Ухаалаг систем дэх олон асуудлын шийдлийг хайлтын асуудал гэж тодорхойлж болох бөгөөд эрэлхийлсэн шийдэл нь хайлтын зорилго бөгөөд зорилгодоо хүрэх боломжит замуудын багц нь хайлтын орон зайг (эсвэл төлөвийн орон зай) төлөөлдөг. Орон зайд шийдлийг олох нь эхний төлөвийг зорилтот төлөвт хувиргах операторуудын дарааллыг тодорхойлохоос бүрдэнэ.

Сахнюк П.А.

Төрийн орон зайд хайх асуудлыг ерөнхийд нь дараах байдлаар томъёолж болно.

Анхны бодлогыг гурвалсан (S, F, T) гэж тайлбарлая, S нь анхны төлөвүүдийн олонлог юм; F – нэг төлөвийг нөгөө мужид буулгах операторуудын багц; T – зорилтот төлөвүүдийн багц. Асуудлын шийдэл нь f1,f2,...,fk операторуудын эхний дарааллыг эцсийнх болгон хувиргах (fi F)-ыг олоход оршино. Төлөвийн орон зайн хайлтын асуудлыг график онолын ойлголтуудыг ашиглан тайлбарлав. Анхны орой (анхны төлөв) ба зорилтот оройнуудын багц F нь төлөвийн орон зайг бүтээхэд ашиглагддаг. дараагийн түвшин (орой нээх). Нуманууд нь хувиргах операторууд гэж тодорхойлогддог.

Үр дүнд нь залгамжлагч оройнууд нь зорилтот цэгүүд мөн эсэхийг шалгадаг. Дараа нь тэд дараагийн түвшинд шилжинэ. Терминал оройнууд нь оператор хэрэглэх боломжгүй байдаг. Өргөтгөл нь зорилтот буюу төгсгөлийн оройд хүрэх хүртэл үргэлжилнэ. Төлөвийн график хайлт нь зорилтот оройг агуулсан G графикийг бүтээх үйл явц юм. Энэ графикийг хайлтын график гэж нэрлэдэг. Тооцооллын аргыг хэрэгжүүлэх хэд хэдэн сонголтуудын хоорондох ялгаа нь оройнуудыг тоолох заасан дарааллаар ялгаатай байдаг.

Гүн-эхний хайлт. Гүнзгий хайлт хийхдээ хамгийн их гүнтэй оройг эхлээд илрүүлдэг. Нэг гүнд байрлах оройнуудаас нээх оройн сонголтыг дур зоргоороо тодорхойлно. Замын бус замаар явах боломжийг хязгаарлахын тулд гүнийн хязгаарыг нэвтрүүлсэн. Хилийн гүнд байрлах оройнууд нээгдээгүй байна.

Өргөн анхны хайлт. Оройнууд нь тэдний үеийн дарааллаар илэрдэг.

Оройн нээлт нь нэг түвшний дагуу явагддаг тул хайлтыг модны өргөний дагуу явуулдаг.

Зорилтот оройг өндөглөсний дараа шууд сонгоно. Эхлээд өргөнийг хайхдаа ийм зам байгаа бол зорилтот орой руу хүрэх хамгийн богино замыг олох боломжтой. Зураг дээр. Зураг 3-т хайлтын графикууд, эхлээд гүнзгийрүүлсэн хайлт, өргөнөөс эхлээд хайлт хийх бүтцийг харуулав.

Сахнюк П.А.

a) b) Зураг. 3. Гүн-эхний хайлт (a) ба өргөн-эхний хайлт (б) Нумын үнэд тулгуурлан хайлт хийх. Ихэнх тохиолдолд харгалзах дүрмийг ашиглах тооцоог гаргахын тулд нумануудад тодорхой утгыг өгдөг. Зорилтот оройг хайхдаа хамгийн бага зардлын замыг олохыг хичээдэг.

Оройнууд нь тэдний утгын өсөх дарааллаар илэрдэг. Орой бүрийн хувьд эхний оройгоос түүнд хүрэх замын хамгийн бага зардлыг санах хэрэгтэй.

Буцааж хайх (буцах). Ийм хайлтыг хэрэгжүүлэхдээ дүрмийг сонгохдоо буцах цэгийг тодорхойлдог, өөрөөр хэлбэл сонгосон чиглэлд цаашдын хайлт нь хүндрэлд хүргэдэг эсвэл найдваргүй байвал хайлтын эхний үе шатанд дамжуулсан буцах цэг рүү шилжинэ. . Дараа нь өөр дүрэм хэрэгжиж, хайлтын үйл явц үргэлжилнэ. Энд, мухардмал байдалд хүргэсэн бүх амжилтгүй давталтууд шинэ дүрэм хэрэгжсэн даруйд мартагдаж, хайлт өөр чиглэлд шилждэг. Энэхүү ухрах аргыг он цагийн дараалал гэж нэрлэдэг. Энэ нь амжилтгүй нөхцөл байдал, тодорхой замд тааралдсан хайлтын алхмуудыг санахгүй байх нь ихэвчлэн үр дүнгүй байдаг. Тэдний олонх нь дараа нь Сахнюк П.А-д үйлчилгээ үзүүлэх болно.

бусад замыг хэрэгжүүлэхэд сөрөг нөлөө үзүүлэх. Тэр. Хайлтын цаашдын чиглэлийг шинжлэхэд маш их хэрэгтэй мэдээлэл хаягдаж, ашиглагдахгүй.

Гацаа, алдаа гаргахад хүргэдэг дүгнэлтийн үе шатуудад дүн шинжилгээ хийх шаардлагатай.

Үүнийг хийхийн тулд та гарах алхмуудыг санах хэрэгтэй. Нэмж дурдахад, тухайн мужаас өмнөх буцах цэг рүү биш, харин амжилтгүй хайлт хийсэн муж руу буцах ёстой.

Төлөвийн орон зайг график хэлбэрээр дүрслэхдээ шийдлийг олох аргуудын онцлог шинж чанар нь хэд хэдэн дараалсан дүрмийг хэрэглэсний үр дүнг хадгалах явдал юм. Өөр нэг онцлог нь тэд туршилтын горимд ажилладаг, өөрөөр хэлбэл ямар ч нөхцөл байдалд тохирох дүрмийг сонгох, ашиглах үед өөр дүрмийг ашиглахын тулд энэ нөхцөл байдалд буцаж очих боломжтой. Харгис хүчний аргын давуу тал нь тэдгээрийг хэрэгжүүлэхэд маш энгийн бөгөөд зарчмын хувьд хэрэв байгаа бол шийдлийг олох чадвар юм. Гэсэн хэдий ч практик дээр хайлтын хэрэгжилтийн явцад цаг хугацаа, санах ойн хязгаарлалт үргэлж байдаг. Том орон зай, цогц асуудлуудын хувьд харгис хүчний аргуудыг хүлээн зөвшөөрөх боломжгүй - комбинатын тэсрэлтийн бодит байдал. Хайлтыг нарийсгахын тулд эвристик гэх мэдээлэл хэрэгтэй.

Эвристик хайлтын аргууд. Таны хайж буй шийдлүүдийн тоог багасгах боломжийг олгодог зарим дүрэм журамтай үед эдгээр хайлтын аргуудыг ашиглаж болно. Эвристик мэдээлэл нь хөгжүүлэгчийн туршлага, нийтлэг ойлголт, таамаглал дээр суурилдаг.

Эвристик хайлтын аргуудыг ашиглах үед нээлттэй оройг эрэмбэлэх хандлагатай байдаг бөгөөд ингэснээр хайлтын үйл явц хамгийн ирээдүйтэй чиглэлд тархдаг. Хайлтын чиглэлийг тодорхойлохын тулд оройн хэтийн төлөв эсвэл энэ орой байрладаг замыг тодорхойлдог тодорхой хэмжүүрийг ашигладаг. Энэ хэмжүүрийг f(n) үнэлгээний функц гэж нэрлэдэг. Энэ функц нь n оройг дайран өнгөрөх тохиолдолд эхний оройноос зорилтот орой хүртэлх хамгийн богино замын зардлын тооцоо юм. Оройг тэлэх эсвэл замыг тодорхойлохдоо үнэлгээний функцийн хамгийн бага утга бүхий оройг сонгоно. Үнэлгээний функц нь хайлтын орон зайг зохих ёсоор тодорхойлох ёстой, өөрөөр хэлбэл. асуудлын талбарын талаар хангалттай их хэмжээний мэдлэг, төрийн орон зайд нарийвчилсан дүн шинжилгээ хийх шаардлагатай. Практикт энэ мэдлэгийг илэрхийлэх тоон шинж чанар, жингийн коэффициентийг ашиглах нь үндэслэлгүй, учир нь програм нь шийдлийг үр дүнтэй хайх боломжийг олгодоггүй (их хэмжээний тооцоолол шаардлагатай байж болно).

Үүнээс гадна, үнэлгээний функцийг ашиглан эвристик хайлтыг П.А.

төрийн орон зайн найдвартай мэдлэг. Гэсэн хэдий ч бодит амьдрал дээр шийдвэр гаргахдаа тэд хангалтгүй, бүрэн дүүрэн, тодорхойгүй баримт, мэдлэгтэй тулгардаг.

Үүнээс гадна хайлтын үйл явц нь ихэвчлэн цаг хугацааны дарамтанд өртдөг. Ийм нөхцөлд хүмүүс албан ёсны математик үндэслэлээс өөр аргуудыг ашигладаг.

Албан ёсны математик үндэслэл нь монотон, i.e. Дүгнэлт бүр өмнөхөөсөө гардаг. (Монотоник байдал гэдэг нь логик, математикийн зарим үйлдлүүдийн (функцуудын) шинж чанар бөгөөд ерөнхийдөө үйлдлүүдийн үр дүнд гарч болох өөрчлөлтийн чиглэл нь зөвхөн эдгээр үйлдлүүдийг гүйцэтгэх өөрчлөлтийн чиглэлээс хамаарна гэсэн үг юм. .) Шийдвэр гаргагчид монотон бус үндэслэл, эсвэл нийтлэг ойлголт (ерөнхий анхан шатны мэдлэг дээр үндэслэсэн) ашигладаг.

Хэдийгээр эрүүл ухаанаар сэтгэх нь хүмүүсийн хувьд нэлээд түгээмэл зүйл боловч хиймэл оюун ухаанд ийм үндэслэлийг хэрэгжүүлэх шаардлагатай түвшинд хүрэх нь маш хэцүү байдаг. (Гэсэн хэдий ч MYCIN, PROSPECTOR гэх мэт зарим сонгодог ES-д хайлтын зайг багасгахын тулд энэ аргыг нэлээд амжилттай хэрэгжүүлсэн.

Эрүүл ухаанаар дүгнэхэд хайлтын процедур нь эдгээр таамаглалтай зөрчилдсөн мэдээлэл байхгүй тохиолдолд тодорхой таамаглал дээр суурилдаг.

Нэмэлт тодруулах мэдээлэл гарах үед таамаглал өөрчлөгдөж болно, өөрөөр хэлбэл. Таамаглал дээр суурилсан хайлтын системд шинэ баримт, мэдлэг олж авахдаа нөхцөл байдлын мөн чанар, хайлтын чиглэлийн талаархи таамаглалуудыг хянаж үзэх шаардлагатай. (Буцах журамтай хослуулах) Бууруулах арга. Асуудлыг шийдвэрлэхэд шаардлагатай өгөгдлийн багцыг олох нь үндсэн дэд даалгавруудыг шийдвэрлэхэд хүргэдэг. Даалгавруудыг янз бүрийн аргаар дүрсэлсэн байдаг: жагсаалт, мод, массив. Асуудлыг тайлбарлах хэлбэрийг төлөвийн орон зайд хайх гэж үзье. Энэхүү дүрслэлд дэд даалгавруудыг хайлтын талбар дахь тодорхой төлөвүүдийн хоорондын холболтыг олох асуудал гэж үздэг. Анхны асуудлыг дэд даалгаврын багц хэлбэрээр илэрхийлэхийн тулд шинэ тайлбар руу шилжих операторыг ашиглана. Энэ оператор нь бүх залгамжлагч дэд асуудлууд шийдэгдэх үед анхны асуудлыг шийдэх арга замыг хувиргадаг.

Анхны асуудлын дүрслэл бүрийн хувьд ийм операторуудын тодорхой багц байж болох бөгөөд тус бүр өөрийн гэсэн дэд даалгавруудыг үүсгэдэг. Эдгээр дэд даалгавруудын зарим нь шийдвэрлэх боломжгүй болж хувирч магадгүй. Бусад дэд даалгавруудын хувьд процесс давтагдана, өөрөөр хэлбэл.

Тэд эргээд дэд даалгавар болж багасдаг. Энэ нь дэд асуудал бүр тодорхой шийдэлтэй болох хүртэл үргэлжилнэ.

Сахнюк П.А.

Өөрчлөлтийн үйл явцыг график бүтцийг ашиглан хялбархан дүрсэлсэн болно.

Энэхүү тайлбар бүхий анхны асуудлын шийдлийг олох үйл явц нь чиглэсэн бодлого бууруулах график юм. Энэ графикийг БА/ЭСВЭЛ график гэж нэрлэдэг. Энэ графикийн оройнууд нь даалгавар болон дэд даалгавруудын тайлбарыг илэрхийлдэг. AND/OR график нь хоёр төрлийн оройг агуулдаг. "I" төрөл - түүний бүх дэд даалгавруудыг харгалзах залгамжлагч оройд хэрэгжүүлэх нөхцөлд шийдвэрлэх боломжтой асуудалд тохирно. "OR" төрөл - харгалзах залгамжлагч оройн альтернатив дэд бодлогын аль нэгийг шийдэх замаар шийдлийг олж болох асуудалд тохирно. Зураг дээр. 4. AND/OR төрлийн графикийн хэсгүүдийг үзүүлэв.

б) Зураг. 4. Анхны асуудлыг дэд даалгаварт хуваахыг БА/ЭСВЭЛ график (a) хэлбэрээр илэрхийлэх ба БА/ЭСВЭЛ графикийг (б) хувиргах.

Анхны даалгавар S0 нь дэд даалгаврын бүлгүүдэд хуваагдана. Үүнийг S1 ба S2 дэд асуудлуудыг шийдвэрлэх замаар шийдэж болно; эсвэл S3; S4 ба S5. N, S3, M, S5 оргилууд нь "I" төрлийн оройнууд юм. Тасархай шугам нь анхны асуудлын шийдлийн графикийн хувилбарыг харуулж байна. S2, S7, S9, S10, S11 дэд даалгавруудын шийдлүүдийг мэддэг гэж үздэг. Бусад дэд асуудлуудын шийдэл тодорхойгүй байна. Нэмэлт оройг ихэвчлэн бүтцэд оруулдаг бөгөөд ингэснээр дэд даалгаврын багц бүр өөрийн эх оройн дор үүсдэг.

Сахнюк П.А.

AND/OR графын орой нь AND эсвэл OR төрлийн байж болно. Иймд анхны графикийг хувиргаж, нэмэлт N ба M оройнуудыг нэвтрүүлсэн бөгөөд энэ нь дэд асуудлын (S1, S2) болон (S4, S5) тусдаа эх орой болж үйлчилдэг. Тиймээс S0 оройг OR орой болгон хувиргадаг.

Бууруулах графикийн хэрэгжилт нь төлөвийн орон зайд шийдлийн хайлтын графикийг хэрэгжүүлэхтэй төстэй юм. Онцгой тохиолдолд, хэрэв AND орой байхгүй бол үр дүн нь энгийн төлөвийн орон зайн график юм. Тиймээс багасгах арга нь тодорхой хэмжээгээр төрийн орон зайн хандлагын ерөнхий ойлголт юм.

AND/OR график дээр хайх үйл явц нь шийдвэрийн график (эсвэл шийдвэрийн мод) байгуулахаас бүрддэг бөгөөд энэ нь бууралтын графикийн дэд хэсэг юм.

Том төлөвийн орон зайд шийдлийг олох аргууд.

Том орон зайд шийдлийн эрэл хайгуул, дүгнэлтийг зохион байгуулах янз бүрийн аргууд байдаг. Тодорхой аргыг ашиглах нь төрийн орон зайн шинж чанар, түүний бүтэц, хийсвэрлэлийн янз бүрийн түвшинд шийдлийн талбарыг дүрслэх чадвар, ирээдүйтэй хайлтын замыг үнэлэх чадвар болон бусад хүчин зүйлүүдтэй холбоотой байдаг.

Бодит асуудлын домэйн нь ихэвчлэн ийм том муж орон зайгаар тодорхойлогддог тул харгис хүчний аргыг ашиглан хайлтыг зохион байгуулахад маш хэцүү байдаг. Гэсэн хэдий ч асуудлын талбарт бүх боломжит шийдлүүдийг олох шаардлагатай байдаг. Ийм тохиолдолд шийдэл нь үүсгэх, баталгаажуулах аргыг ашиглах явдал юм. Хэрэв орон зайг хүчин зүйлээр тооцох боломжтой бол энэ аргыг ашиглаж болно, i.e.

үүнийг бүрэн бус шийдлүүдтэй нэлээн бие даасан дэд орон зайд хуваах боломжтой. Бүрэн бус шийдэл нь энэ дэд орон зайд бүрэн шийдлийг хайх хэтийн төлөвийг дүгнэх боломжийг бидэнд олгодог.

Аргын мөн чанар нь асуудлын талбарт тохируулсан генератор нь янз бүрийн дэд орон зайн тайлбарт тохирсон олон тооны бүрэн бус шийдлүүдийг бий болгодог явдал юм. Бүрэн бус шийдлүүдийг тусгай үнэлгээний журмаар шалгадаг бөгөөд хэрэв шийдэл нь хүлээн зөвшөөрөгдөөгүй гэж үзвэл түүний үүсгэсэн дэд орон зайн бүрэн шийдлийн бүх ангиллыг цаашид авч үзэхээс хасна. Хайлтын эхний үе шатанд төлөвийн зангилаа үүсгэх, шалгахгүйгээр хайлтын тодорхой салбаруудыг тасалсны үр дүнд дүн шинжилгээ хийх төлөвийн тоо мэдэгдэхүйц буурч байна. Хэрэв бүрэн бус шийдэл нь ирээдүйтэй гэж хүлээн зөвшөөрөгдвөл зохих дэд орон зайд түүний үндсэн дээр орон зайн тодорхойлолтын шатлалын гүнзгий түвшинд бүрэн шийдлүүдийг боловсруулж, үр дүнд нь зорилтот шийдэл мөн эсэхийг тодорхойлно.

Сахнюк П.А.

Үүсгэх, баталгаажуулах аргыг хэрэгжүүлэх шаталсан журам нь үүслийн эхний үе шатанд хувилбаруудыг таслах дүрмийг хэрэгжүүлэх боломжийг олгодог. Бүрэн бус шийдлийн шинж чанарыг үнэлэх найдвартай аргууд ихэвчлэн байдаггүй, өөрөөр хэлбэл бүрэн бус шийдлүүд дээр үндэслэн бүрэн шийдлийн боломжийн талаар дүгнэлт хийх боломжгүй байдаг тул хүчин зүйлчилсэн орон зайд үүсгэх, баталгаажуулах аргыг ашиглах нь хэцүү байж болно. . Энд эрэл хайгуулын эхний шатанд өндөр итгэл үнэмшилтэй ирээдүйгүй мөчрүүдийг таслах боломжгүй юм. Ирээдүйгүй мэт боловч нэмэлт мэдээлэл гарч ирэхэд цаашдын боловсруулалтанд шийдэл гаргах чадвартай муж улсын орон зайн хэсгийг хасах эрсдэл үргэлж байдаг.

Ийм нөхцөл байдал нь урт хугацааны төлөвлөлт, дизайны асуудалтай холбоотой байдаг.

Нэмж дурдахад, бүх боломжит шийдлүүдийг хайх шаардлагагүй, гэхдээ хүлээн зөвшөөрөгдсөн шийдэлтэй байх нь хангалттай юм.

Эдгээр тохиолдолд шийдлийн орон зайг хийсвэрлэнэ. Асуудлын шийдлийг хийсвэрлэлийн янз бүрийн түвшинд орон зайн дүрслэлийн эдгээр түвшинд дараалан тодруулах замаар гүйцэтгэдэг. Хийсвэрлэл нь асуудлыг тодорхойлсон чухал нарийн ширийн зүйлийг цааш нь илчилдэг. Үндсэн даалгавар нь дэд даалгаврын тодорхой багц болгон бууруулсан. Хийсвэр орон зайд энгийн тохиолдлуудад нэг хуваалт хангалттай бөгөөд тухайн асуудлын талбарын өөр өөр ажилд ашиглагддаг.

Хэрэв асуудлын талбарт олон тооны асуудал байгаа бол хайлтын зайг багасгах тодорхой хувилбарыг ашиглан бүх асуудлыг шийдэх боломжгүй юм. Үүний нэг жишээ бол сансарт хөдөлж, объектыг удирдах роботын үйлдлийг төлөвлөх асуудал юм. Эдгээр тохиолдолд хийсвэрлэл нь үйл ажиллагааны төлөвлөгөөний хувьсах бүтцийг тусгасан байх ёстой.

Дээрээс нь дараалсан боловсронгуй болгох аргыг ашиглах боломжтой. Энэ арга нь даалгавар бүрт тохирсон хийсвэрлэлийг бий болгодгоороо онцлог юм. Түүнээс гадна, асуудлыг шийдвэрлэх үйл явцыг хялбарчлахын тулд тэд эхлээд орон зайн ерөнхий тодорхойлолтыг олж авч, энэ орон зайд асуудлыг шийдэж, дараа нь орон зайн илүү тодорхой тайлбар руу шилждэг. Тиймээс асуудлын шийдлийг хийсвэр орон зайд хайх, тодорхойлохоос эхлээд энэ шийдлийг хувиргах, доод түвшний (өөрөөр хэлбэл илүү нарийвчилсан) дүрслэлээр тодорхой болгох хүртэл дээрээс доошоо хэрэгждэг.

Илүү тодорхой түвшинд шилжих нь тухайн хийсвэрлэлийн түвшинд шийдэл дууссаны дараа л хийгддэг.

Том төлөвийн орон зайд шийдлийг хайхдаа эвристик арга, процедурыг мөн ашигладаг. Цэвэр эвристик П.А.Сахнюкийг тодорхойлоход ихэвчлэн хэцүү байдаг.

журам, учир нь энэ нь нэрлэсэн аргуудын аль нэгэнд нь их бага хэмжээгээр суулгаж болно. Жишээлбэл, эвристик үнэлгээ нь үүсгэх, турших аргад байдаг бөгөөд генератор нь шинж чанарын бүрэн бус шийдлүүдийн талаархи таамаглалыг бий болгож, дараа нь шалгадаг. Дээрхээс дараалсан боловсронгуй болгох аргыг ашиглахдаа асуудлыг хийсвэрлэлийн дээд түвшинд шийдвэрлэх нь асуудлын тайлбарын илүү нарийвчилсан түвшинд шийдлийг тодорхойлох боломжийг олгоно гэж үзэж, зөвшөөрнө.

Шийдэл хайхдаа таамаглал дэвшүүлэх хэрэгцээ нь олон шалтгаанаас үүдэлтэй байж болно: аргыг хэрэгжүүлэхдээ шийдвэрийн тодорхой үе шатанд хайлтын чиглэлийг сонгох боломжгүй, баримт, мэдлэг хангалтгүй; янз бүрийн шийдлүүдийг судлах цаг хомс;

бусад нөөцийг хязгаарласан. Эдгээр тохиолдолд эрэл хайгуулын цаашдын чиглэлийн талаар үндэслэлтэй таамаглал дэвшүүлж, шийдвэрийн явцад олж авсан шинэ мэдээллийн үндсэн дээр эсрэгээр нь тодорхой болох хүртэл хүчинтэй хэвээр байна. Практикт тэд нийтлэг ойлголт, өөрөөр хэлбэл, дээр дурдсанчлан хиймэл оюун ухааны практик системд нэлээд хэцүү байдаг монотон бус үндэслэлийн дагуу үндэслэлийг хэрэгжүүлэхийг хичээдэг.

Алдааны ангилал

Интернет нөөц

Лекцийн тойм

Програм хангамжийн дибаг хийх

Лекц No8.

Тамбов 2011 он

Курс, бүлэг BIS-11, BIS-12

Сэдэв 6. Дибаг хийх програм хангамж

Лекц 8

Сахилгын програмчлалын технологи

Чиглэл 230400 "Мэдээллийн систем ба технологи"

Багш: Минин Юрий Викторович

Лекцийн зорилго

Лекцийн зорилго нь програм хангамжийг дибаг хийх үйл явц, техникийн талаар ойлголт өгөх явдал юм.

1. Алдааны ангилал

2. Програм хангамжийн дибаг хийх арга

3. Алдааны талаар нэмэлт мэдээлэл олж авах арга, хэрэгсэл

4. Програм хангамжийн дибаг хийх техник

Ном зүй

Үндсэн уран зохиол

1. Иванова Г.С. Програмчлалын технологи М.: MSTU-ийн хэвлэлийн газар im. Н.Э. Бауман, 2002. - 320 х.

2. Жоголев Е.А. Програмчлалын технологи М.: Шинжлэх ухааны ертөнц, 2004. - 216 х.

3. Гагарина Л.Г., Кокорева Е.В., Виснадул Б.Д. Програм хангамж хөгжүүлэх технологи. М .: "ФОРУМ" хэвлэлийн газар - INFRA-M, 2008. - 400 х.

нэмэлт уран зохиол

1. Kaner S., Folk D., Nguyen E. Програм хангамжийн туршилт. М .: DiaSoft, 2001. - 544 х.

2. Braude E. Програм хангамж хөгжүүлэх технологи. Санкт-Петербург: Петр, 2004. - 655 х.

3. Баранов С.Н., Домарацкий А.Н., Ласточкин Н.К., Морозов В.П. Програм хангамжийн бүтээгдэхүүн боловсруулах үйл явц. М.: ФИЗМАТЛИТ, Наука, 2000. - 176 х.

1. www.intuit.ru - Мэдээллийн технологийн интернетийн их сургууль.

2. http://citforum.ru/ - Мэдээллийн технологийн төв.

3. http://www.tstu.ru/r.php?r=education - TSTU-ийн цахим номын сан.

4. http://www.edu.ru/ - "Оросын боловсрол" Холбооны порталын номын сан

Програмыг дибаг хийх нь програм хангамжийг хөгжүүлэх хамгийн хэцүү үе шатуудын нэг бөгөөд дараахь талаар гүнзгий мэдлэг шаарддаг.

Ашигласан техникийн хэрэгслийг удирдах онцлог,

Үйлдлийн систем

Програмчлалын орчин, хэл,

Хэрэгжүүлсэн процессууд,

Төрөл бүрийн алдааны шинж чанар, онцлог,

Дибаг хийх техник, холбогдох программ хангамж.

Энэхүү лекц нь сүүлийн хоёр асуултыг хэлэлцэхэд зориулагдсан болно.

Дибаг хийх-програм хангамжийн туршилтын явцад илэрсэн алдааг нутагшуулах, засах үйл явц юм. ЛокалчлалГүйцэтгэл нь ердийн тооцооллын процессыг тасалдуулахад хүргэсэн програмын мэдэгдлийг тодорхойлох үйл явц гэж нэрлэгддэг. Алдааг засахын тулд та үүнийг тодорхойлох хэрэгтэй шалтгаан, өөрөөр хэлбэл алдаа агуулсан мэдэгдэл эсвэл фрагментийг тодорхойлох. Алдааны шалтгаан нь тодорхой бөгөөд маш гүн нуугдмал байж болно.

Ерөнхийдөө дибаг хийхэд хүндрэлтэй байгаа нь дараахь шалтгааны улмаас үүсдэг.

Програмистаас ашигласан техник хангамжийг удирдах онцлог, үйлдлийн систем, орчин болон програмчлалын хэл, хэрэгжиж буй процессууд, төрөл бүрийн алдааны шинж чанар, онцлог, алдаа засах арга техник, холбогдох программ хангамжийн талаар гүнзгий мэдлэгтэй байхыг шаарддаг;

Сэтгэл зүйн хувьд эвгүй, учир нь та өөрийн алдаагаа хайх хэрэгтэй бөгөөд дүрмээр бол хязгаарлагдмал хугацаанд;

Хөтөлбөрийн өөр өөр хэсгүүдийн алдаанууд харилцан үйлчлэлцэх магадлалтай, жишээлбэл, хаягийн алдааны улмаас нэг модулийн санах ойн талбарыг нөгөө модуль арилгасны улмаас;

Тодорхой тодорхойлсон дибаг хийх арга байхгүй.

Алдаа гарч буй боловсруулалтын үе шатаас хамааран тэдгээрийг ялгадаг (Зураг 1):

- синтакс алдаа -програмын синтаксик болон хэсэгчилсэн семантик шинжилгээ хийх үед хөрвүүлэгч (орчуулагч, орчуулагч) -ийн бичсэн алдаа;

- зохион байгуулалтын алдаа -програмын модулиудыг нэгтгэх үед холбогч (холбоос засварлагч) илрүүлсэн алдаа;

- ажиллах үеийн алдаа -програмыг ажиллуулах явцад үйлдлийн систем, техник хангамж эсвэл хэрэглэгчдэд учирсан алдаа.

Зураг 1 - Програмын боловсруулалтын үе шатаар алдааны ангилал

Синтакс алдаа.Хэлний синтакс нь дүрмээр бол хатуу албан ёсны бөгөөд алдаа нь түүний байршлыг харуулсан нарийвчилсан тайлбар дагалддаг тул синтакс алдааг хамгийн энгийн гэж ангилдаг. Дүрмээр бол ийм алдааны шалтгааныг тодорхойлох нь тийм ч хэцүү биш бөгөөд хэлний дүрмийн талаар тодорхойгүй мэдлэгтэй байсан ч хэд хэдэн гүйлтээр энэ төрлийн бүх алдааг арилгах боломжтой байдаг.

Хэлний синтаксийн дүрмийг хэдий чинээ сайн албан ёсны болгох тусам хөрвүүлэгч нийт тооноос илүү олон алдааг илрүүлж, үүний дагуу дараагийн үе шатанд цөөн алдаа илрэх болно гэдгийг санах нь зүйтэй. Үүнтэй холбогдуулан тэд хамгаалагдсан синтакс болон хамгаалалтгүй синтакс бүхий програмчлалын хэлнүүдийн талаар ярьдаг. Эхнийх нь мэдээжийн хэрэг маш энгийн бөгөөд тодорхой тодорхойлогдсон синтакстай, програмыг эмхэтгэх үед маш сайн шалгагдсан Паскал, хоёр дахь нь - C/C++ бүх өөрчлөлтийг багтаасан болно. C/C+ хэл дээрх нөхцөлт оператор дээр даалгавар гүйцэтгэх чадвартай байх нь дор хаяж ямар үнэ цэнэтэй вэ, жишээ нь:

Энэ тохиолдолд c ба тиймийн тэгш байдлыг шалгахгүй, харин n утгын даалгаврыг гүйцэтгэсний дараа үйлдлийн үр дүнг тэгтэй харьцуулна. Хэрэв програмист даалгавар биш, харин харьцуулалт хийхийг хүсч байвал. дараа нь энэ алдаа нь хүлээгдэж байснаас ялгаатай үр дүнг авах үед зөвхөн гүйцэтгэлийн шатанд илрэх болно.

Байршлын алдаа.Нэрнээс нь харахад байршлын алдаа нь гадаад холбоосыг шийдвэрлэх явцад гарсан асуудлуудтай холбоотой юм. Жишээлбэл, өөр модулийн дэд програм руу залгах боломжтой боловч модулиудыг нэгтгэх үед энэ дэд програм олдохгүй эсвэл параметрийн жагсаалтыг нэгтгэдэггүй. Ихэнх тохиолдолд ийм төрлийн алдааг хурдан илрүүлж, арилгах боломжтой.

Ажиллах үеийн алдаа.Хамгийн урьдчилан таамаглах боломжгүй бүлэгт ажиллах үеийн алдаанууд орно. Юуны өмнө тэд өөр өөр шинж чанартай байж болох бөгөөд үүний дагуу өөрсдийгөө өөр өөрөөр илэрхийлж болно. Зарим алдааг үйлдлийн систем илрүүлж баримтжуулдаг. Ийм алдаа гарч болох дөрвөн арга байдаг:

Машины командын гүйцэтгэлийн хяналтын хэлхээнд бүртгэгдсэн алдааны мэдэгдлийн харагдах байдал, жишээлбэл, битийн сүлжээ халих, тэг нөхцөл байдалд хуваах, зөрчлийг арилгах гэх мэт;

Үйлдлийн системээс илрүүлсэн алдааны тухай мессеж гарч ирнэ, жишээлбэл, санах ойн хамгаалалтын зөрчил, бичихээс хамгаалагдсан төхөөрөмж рүү бичих оролдлого, заасан нэртэй файл байхгүй гэх мэт;

- үйлдлийн системийг дахин эхлүүлэхгүйгээр програмыг дуусгах боломжтой үед компьютерийг "хөлдөх" энгийн, мөн үргэлжлүүлэн ажиллахын тулд дахин ачаалах шаардлагатай үед "хүнд";

Хүлээгдэж буй үр дүн болон хүлээгдэж буй үр дүн хоорондын зөрүү.

Хэрэв гүйцэтгэлийн үе шатанд алдаа гарсан тохиолдолд хэрэглэгч эхний хоёр тохиолдолд холбогдох мессежийг хүлээн авсны дараа түүний зан чанар, хэрэгцээний түвшин, компьютертэй ажиллах туршлагаас хамааран хэрэглэгч юу болохыг ойлгохыг хичээх болно гэдгийг анхаарна уу. тохиолдсон, түүний бурууг хайж, эсвэл тусламж хүсэх болно, эсвэл энэ бүтээгдэхүүнтэй дахин хэзээ ч харьцахгүй байх болно. Компьютер хөлдөх үед хэрэглэгч ямар нэг зүйл буруу болсныг шууд ойлгохгүй байж магадгүй ч түүний гунигтай туршлага нь компьютер оруулсан тушаалд хурдан хариу өгөхгүй байх бүрт санаа зовдог бөгөөд үүнийг санаж байхыг зөвлөж байна. Хэрэглэгч буруу үр дүнг хүлээн авч, ажилдаа ашиглах нөхцөл байдал бас аюултай байж болно.

Ажиллах үеийн алдааны шалтгаан нь маш олон янз байдаг тул нутагшуулах нь маш хэцүү байдаг. Алдааны бүх боломжит шалтгааныг дараах бүлгүүдэд хувааж болно.

Эх өгөгдлийн буруу тодорхойлолт,

Логик алдаа

Тооцооллын үр дүнгийн алдааны хуримтлал (Зураг 2).

Оролт / гаралтын үйл ажиллагааны явцад аливаа алдаа гарсан тохиолдолд эх сурвалжийн өгөгдлийг буруу таних тохиолдол гардаг: дамжуулах алдаа, хөрвүүлэх алдаа, дахин бичих алдаа, өгөгдлийн алдаа. Түүгээр ч зогсохгүй техникийн тусгай хэрэгсэл, алдаагүй програмчлалыг ашиглах нь эдгээр алдааны зөвхөн заримыг нь илрүүлж, урьдчилан сэргийлэх боломжийг олгодог.

Логик алдаа нь өөр өөр шинж чанартай байдаг. Иймээс тэдгээр нь загварчлалын явцад, жишээлбэл арга сонгох, алгоритм боловсруулах, ангийн бүтцийг тодорхойлоход гарсан алдаанаас үүдэн гарах эсвэл модулийг кодлох явцад шууд нэвтрүүлж болно. Сүүлийн бүлэгт дараахь зүйлс орно.

Хувьсагчийн буруу ашиглалтын алдаа, жишээлбэл, өгөгдлийн төрлийг амжилтгүй сонгох, хувьсагчдыг эхлүүлэхээс өмнө ашиглах, массивын тодорхойлолтоос хэтэрсэн индекс ашиглах, байрлах өгөгдлийн төрлийг тодорхой эсвэл далд дахин тодорхойлох үед өгөгдлийн төрлийн харгалзах зөрчлүүд. төрөлжөөгүй хувьсагч, нээлттэй массив, нэгдэл, динамик санах ой, хаягийн арифметик гэх мэтийг ашиглах үед санах ойд;

Тооцооллын алдаа, жишээлбэл, арифметик бус хувьсагчид дээр буруу тооцоо хийсэн, бүхэл тооны арифметикийг буруу ашигласан, тооцооллын явцад өгөгдлийн төрлийг буруу хөрвүүлсэн, арифметик болон логик илэрхийллийн үйлдлүүдийн тэргүүлэх чиглэлийг үл тоомсорлосон алдаа гэх мэт;

Модуль хоорондын интерфейсийн алдаа, жишээлбэл, системийн конвенцуудыг үл тоомсорлох, параметрүүдийг дамжуулахдаа төрөл, дарааллыг зөрчих, албан ёсны болон бодит параметрүүдийн хэмжлийн нэгжийн нэгдмэл байдлыг дагаж мөрдөхгүй байх, орон нутгийн болон глобал хувьсагчийн хамрах хүрээг зөрчих;

Бусад кодчиллын алдаанууд, жишээлбэл, кодлохдоо програмын логикийг буруу хэрэгжүүлсэн, тухайн програмчлалын хэлний онцлог, хязгаарлалтыг үл тоомсорлодог.

Тоон тооцооллын үр дүнд алдаа хуримтлагдах нь жишээлбэл, тоонуудын бутархай цифрийг буруу хаясан, тооцооллын ойролцоо аргыг буруу ашигласан, компьютерт бодит тоог илэрхийлэх цифрийн сүлжээн дэх хязгаарлалтыг үл тоомсорлодог гэх мэт.

Дибаг хийх явцад дээрх алдааны бүх шалтгааныг санаж байх хэрэгтэй. Нэмж дурдахад дараах хүчин зүйлсийн нөлөөгөөр дибаг хийх нарийн төвөгтэй байдал нэмэгддэг.

алдааны шууд бус илрэл;

Алдааны харилцан нөлөөллийн боломж;

Өөр өөр алдааны гаднах ижил төстэй илрэлийг олж авах боломж;

Эхлэхээс эхлээд хөөргөх хүртэлх зарим алдааны илрэлийн давтагдах чадвар дутмаг (стохастик алдаа);

Хөтөлбөрт зарим өөрчлөлт оруулахдаа судалж буй нөхцөл байдлын алдааны гадаад илрэлийг арилгах чадвар, жишээлбэл, оношлогооны хэсгүүдийг хөтөлбөрт оруулсан тохиолдолд алдааны гадаад илрэлийг цуцлах эсвэл өөрчлөх боломжтой;

Програмын тусдаа хэсгүүдийг өөр өөр програмистууд бичих.

Ямар ч тохиолдолд програмыг дибаг хийх нь алдааны талаархи бүх мэдээллийг бодож, логикоор ойлгохыг шаарддаг. Ихэнх алдааг нэмэлт мэдээлэл авахгүйгээр програмын текст болон туршилтын үр дүнг сайтар шинжлэх замаар шууд бус нотлох баримтаар илрүүлж болно. Төрөл бүрийн аргыг ашигладаг:

Гарын авлагын туршилт;

Индукц;

хасалт;

Дахин сэргээх.

Гараар шалгах арга. Энэ бол энэ бүлгийн хамгийн энгийн бөгөөд байгалийн арга юм. Хэрэв алдаа илэрсэн бол та алдааг илрүүлсэн тестийн багцыг ашиглан туршилтын програмыг гараар ажиллуулах ёстой.

Энэ арга нь маш үр дүнтэй боловч том хэмжээний программууд, нарийн төвөгтэй тооцоололтой программууд болон зарим үйлдлийг хэрхэн гүйцэтгэх талаар програмист буруу ойлголттой байснаас алдаа гарсан тохиолдолд хэрэглэх боломжгүй.

Энэ аргыг ихэвчлэн бусад дибаг хийх аргуудын нэг хэсэг болгон ашигладаг.

Индукцийн арга. Энэ арга нь алдааны шинж тэмдгүүдийн нарийн дүн шинжилгээнд үндэслэсэн бөгөөд энэ нь буруу тооцооллын үр дүн эсвэл алдааны мессеж хэлбэрээр гарч ирж магадгүй юм. Хэрэв компьютер зүгээр л хөлдвөл хамгийн сүүлд олж авсан үр дүн болон хэрэглэгчийн үйлдэл дээр үндэслэн алдааны илрэлийн хэсгийг тооцоолно. Ийм аргаар олж авсан мэдээллийг програмын харгалзах хэсгийг үзэх замаар зохион байгуулж, сайтар судалж үздэг. Эдгээр үйлдлүүдийн үр дүнд алдааны талаархи таамаглал дэвшүүлж, тус бүрийг нь шалгадаг. Хэрэв таамаглал зөв бол алдааны талаарх мэдээлэл дэлгэрэнгүй, үгүй ​​бол өөр таамаглал дэвшүүлнэ. Индукцийн аргыг ашиглан дибаг хийх дарааллыг Зураг дээр үзүүлэв. 3 алгоритм диаграм хэлбэрээр.

Зураг 3 - Индукцийн дибаг хийх үйл явцын схем

Хамгийн чухал үе шат бол алдааны шинж тэмдгийг тодорхойлох явдал юм. Алдааны талаархи мэдээллийг зохион байгуулахдаа түүний илрэлийн талаар мэдэгдэж байгаа бүх зүйлийг бичиж, алдаатай фрагментийг хэвийн ажиллуулж байгаа нөхцөл байдал, алдаа илэрсэн нөхцөл байдлыг хоёуланг нь тэмдэглэхийг зөвлөж байна. Хэрэв өгөгдлийг судалсны үр дүнд ямар нэгэн таамаглал гарахгүй бол алдааны талаар нэмэлт мэдээлэл шаардлагатай болно. Жишээлбэл, ижил төстэй туршилтыг хийх замаар нэмэлт мэдээллийг авах боломжтой.

Баталгаажуулах явцад алдааны бүх илрэл нь өгөгдсөн таамаглалаар тайлбарлагдаж байгаа эсэхийг олж мэдэхийг оролддог.

Хасах арга. Хасах аргыг ашиглан алдааны энэ илрэлийг үүсгэж болох янз бүрийн шалтгааныг эхлээд бий болгодог. Дараа нь шалтгааныг задлан шинжилж, байгаа өгөгдөлтэй зөрчилдөж буй зүйлийг хас. Хэрэв бүх шалтгааныг хассан бол судалж буй фрагментийн нэмэлт шинжилгээг хийх шаардлагатай. Үгүй бол тэд хамгийн их магадлалтай таамаглалыг батлах гэж оролддог. Хэрэв таамаглал нь алдааны хүлээн авсан шинж тэмдгүүдийг тайлбарлавал алдаа олдсон, эс тэгвээс дараагийн шалтгааныг шалгана (Зураг 4).

Зураг 4 - Хасах аргыг ашиглан дибаг хийх үйл явцын схем

Буцах арга. Жижиг программуудын хувьд буцаах арга нь үр дүнтэй байдаг. Тэд буруу үр дүнд хүрсэн цэгээс эхэлдэг. Үүний тулд одоо байгаа үр дүнг олж авахад хүргэж болох үндсэн хувьсагчдын утгуудын талаархи таамаглалыг бий болгодог. Дараа нь энэ таамаглал дээр үндэслэн өмнөх цэг дэх хувьсагчдын утгын талаар саналууд гаргана. Процесс нь алдааны шалтгааныг олж мэдэх хүртэл үргэлжилнэ.

Лекц 9.I/O Control

9.1 Оролт гаралтын техник хангамжийн зарчим

Оролт/гаралтын удирдлагын системийн хоёр доод түвшин нь техник хангамж юм: үйлдлүүдийг шууд гүйцэтгэдэг төхөөрөмжүүд болон тэдгээрийн хянагч нь төхөөрөмжүүд болон бусад тооцоолох системийн хамтын ажиллагааг зохион байгуулахад үйлчилдэг. Дараагийн түвшин I/O төхөөрөмжийн драйверууд , үйлдлийн систем хөгжүүлэгчдээс тодорхой төхөөрөмжүүдийн үйлдлийн шинж чанарыг нууж, техник хангамж болон дээд түвшний хоорондох тодорхой интерфэйсийг хангах. , энэ нь эргээд драйверууд болон тооцоолох системийн програм хангамжийн хэсэг хоорондын харилцан үйлчлэлийн механизмыг бүрдүүлдэг.

Цагаан будаа. 1. I/O системийн бүтэц

Аливаа үйлдлийн системийн нэг хэсэг болох оролт/гаралтын төхөөрөмжийг хянадаг тусгай дэд систем байдаг. Энэхүү дэд системийг ашиглан шийдсэн гол ажлууд нь дараах байдалтай байна.

- дэд систем нь хэрэглэгчдэд нэг хэрэглэгчийн болон олон хэрэглэгчийн компьютерийн үйлдлийн горимд хяналтын самбарт хандахад тохиромжтой, ойлгомжтой интерфейсээр хангах ёстой; Үүний зэрэгцээ, төхөөрөмжийн бие даасан байдлын зарчмыг хэрэгжүүлдэг өөр өөр физик шинж чанартай хяналтын төхөөрөмжүүдэд нэвтрэх нэгдсэн интерфейсийг бий болгох шаардлага байнга гардаг;

- Цаг хуваах системийн олон программын горимд дэд систем нь төв боловсруулах нэгж (CPU) болон оролт-гаралтын төхөөрөмжийн ажиллах хугацаанд хамгийн их давхцаж байхын тулд өгөгдөл оруулах-гаралтын үйл явцын төлөвлөлтийг хангах ёстой.

- Оролт-гаралтын төхөөрөмж болон оролт-гаралтын төхөөрөмжийн үйлдлийн системийн дэд системийн бүтэц нь өөр өөр компьютеруудын хувьд ихээхэн ялгаатай боловч бүх дэд системүүдийн онцлог шинж чанартай нэг концепцийн зарчмыг тодорхойлж болно. Оролт гаралтын техник хангамжийг CPU-тэй зэрэгцэн бие биетэйгээ зэрэгцэн ажиллах чадвартай техник хангамжийн процессоруудын цуглуулга гэж ойлгож болно. Эдгээр процессорууд нь гадаад гэж нэрлэгддэг процессуудыг ажиллуулдаг. Жишээлбэл, хэвлэх төхөөрөмжийн хувьд уг процесс нь зөөвөрлөгч буцах, цаасыг нэг мөрөөр урагшлуулах, өгөгдсөн тооны тэмдэгтийг мөрөнд хэвлэх зэрэг үйлдлүүдээс бүрдэж болно.

Гадаад процессууд нь CPU болон санамсаргүй хандалтын санах ой (RAM) -аар гүйцэтгэдэг програм хангамжийн процессуудтай харилцан үйлчилдэг. Програм хангамжийн процессын гүйцэтгэлийн хурд нь гадаад процессын хурдаас хэд хэдэн дарааллаар илүү байж болох нь чухал юм.

Програм хангамжийн процессын үүднээс I/O удирдлагын үйлдлийн системийн дэд систем нь хяналтын самбартай интерфейс юм. PU-тэй гурван төрлийн үйлдэл байдаг:

1. өгөгдөл унших-бичих үйлдлүүд;

2. PU хяналтын үйл ажиллагаа;

3. удирдлагын нэгжийн байдлыг шалгах ажиллагаа.

9.1.1 I/O төхөөрөмжүүд

Төхөөрөмжүүдийг хоёр ангилалд хуваадаг (зарим нь аль алинд нь хамаарахгүй):

• блок төхөөрөмж - мэдээллийг блокоор уншиж, бичдэг, блокууд нь өөрийн гэсэн хаягтай (диск)
• тэмдэгтийн төхөөрөмжүүд - мэдээллийг тэмдэгтээр уншиж, бичдэг (принтер, сүлжээний карт, хулгана)

9.1.2 Төхөөрөмжийн хянагч

I/O төхөөрөмжүүд нь ихэвчлэн хоёр хэсгээс бүрдэнэ:

• механик (шууд утгаараа авах шаардлагагүй) - диск, принтер, монитор
• цахим - хянагчэсвэл адаптер

Хэрэв хянагч ба төхөөрөмжийн хоорондох интерфейс нь стандартчилагдсан (ANSI, IEEE эсвэл ISO) бол бие даасан үйлдвэрлэгчид нийцтэй хянагч, төхөөрөмжийг үйлдвэрлэх боломжтой. Жишээ нь: IDE эсвэл SCSI хөтчүүд.

Үйлдлийн систем нь ихэвчлэн төхөөрөмжтэй биш, харин хянагчтай харьцдаг. Удирдагч нь дүрмээр бол энгийн функцуудыг гүйцэтгэдэг, жишээлбэл, дискнээс уншихдаа битийн урсгалыг байтаас бүрдэх блок болгон хувиргаж, алдааг хянаж, засч залруулдаг бол блокийн хяналтын нийлбэр нь заасантай тохирч байвал шалгана. секторын толгой хэсэгт блокийг алдаагүй уншина, үгүй ​​бол дахин уншина.

9.1.3 Санах ойн хаягийн зураглалтай I/O

Хянагч бүр нь төв процессортой холбогдоход хэрэглэгддэг хэд хэдэн регистртэй байдаг. Эдгээр регистрүүдийг ашиглан үйлдлийн систем нь хяналт (унших, бичих, асаах гэх мэт) бөгөөд төхөөрөмжийн төлөвийг (бэлэн байдал) тодорхойлдог.

Олон төхөөрөмжүүд өгөгдлийн буфертэй байдаг (жишээлбэл: видео санах ой).

Хяналтын бүртгэл болон буферт хандах хандалтын хэрэгжилт:

• I/O портын дугаар - хяналтын регистр бүрт 8 эсвэл 16 битийн бүхэл тоо онооно. RAM болон оролт гаралтын төхөөрөмжүүдийн хаягийн зай нь энэ схемд давхцдаггүй.
  Алдаа дутагдал
  - тусгай командуудыг унших, бичихэд ашигладаг, жишээ нь IN болон OUT
  - процессыг хамгаалах тусгай механизм шаардлагатай
  - та эхлээд төхөөрөмжийн бүртгэлийг процессорын бүртгэлд унших ёстой

• санах ойн хаягийн зайны зураглалтай I/O - регистрүүдийг санах ойн хаягийн орон зайд буулгана.
  Алдаа дутагдал
  - санах ойг кэш хийх үед төхөөрөмжийн бүртгэлийг мөн кэш хийх боломжтой
  - Бүх төхөөрөмж санах ойн бүх хандалтыг шалгаж, алинд нь хариу өгөхийг тодорхойлох ёстой. Нэг энгийн автобусанд үүнийг хялбархан хэрэгжүүлж болох боловч хэд хэдэн автобусанд асуудал гарах болно.

• холимог хэрэгжилт - x86 болон Pentium-д ашигласан,
  0-ээс 64K хүртэл портуудад хуваарилагдсан,
  640-аас 1 сая хүртэлх зай нь өгөгдлийн буферт зориулагдсан.

Хяналтын бүртгэл ба буферт хандах хандалтыг хэрэгжүүлэх арга

9.1.4 Чигээрээ хандалт руу санах ой (DMA - Санах ойн шууд хандалт)

Санах ойн шууд хандалтыг ашиглан хэрэгжүүлдэг DMA хянагч.

Хянагч нь хэд хэдэн бүртгэлийг агуулдаг:

• санах ойн хаягийн бүртгэл
• байт тоолуур
• хяналтын бүртгэлд дараахь зүйлийг агуулж болно.
  - I/O порт
  - унших эсвэл бичих
  - зөөвөрлөх нэгжүүд (байтаар эсвэл үгээр)

Хянагчгүй бол дараахь зүйл тохиолддог.

1. Процессор нь диск хянагч руу өгөгдлийг буфер руу уншихыг зааварчилдаг.
2. Өгөгдлийг буферт уншиж, хянагч нь уншсан өгөгдлийн хяналтын нийлбэрийг шалгадаг (алдаа шалгах). Процессор тасалдахаас өмнө бусад ажил руу шилждэг.
3. Диск хянагч тасалдлыг эхлүүлнэ
4. Үйлдлийн систем ажиллаж эхлэх ба буферээс өгөгдлийг санах ой руу унших боломжтой

DMA хянагчийн ажиллагаа

Удирдлагад дараахь зүйл тохиолддог.

1. Процессор нь хянагчийг програмчилдаг (ямар өгөгдөл, хаашаа зөөх)
2. Процессор нь дискний хянагч руу өгөгдлийг буфер руу уншихыг зааварчилдаг
3. Өгөгдлийг буферт уншиж, дискний хянагч нь уншсан өгөгдлийн хяналтын нийлбэрийг шалгадаг (процессор тасалдахаас өмнө бусад ажил руу шилждэг).
4. DMA хянагч нь унших хүсэлтийг диск хянагч руу илгээдэг
5. Диск хянагч нь автобусанд өгөгдлийг нийлүүлдэг, санах ойн хаяг нь автобусанд байгаа, өгөгдлийг санах ойд бичдэг.
6. Бичиж дууссаны дараа диск хянагч нь DMA хянагч руу хүлээн зөвшөөрсөн мэдэгдлийг илгээдэг
7. DMA хянагч нь ашигласан хаягийг нэмэгдүүлж, байт тоолуурын утгыг бууруулдаг
8. 4-р алхамаас эхлэн тоолуурын утга тэг болох хүртэл бүх зүйл давтагдана.
9. DMA хянагч тасалдлыг эхлүүлнэ

Үйлдлийн систем нь өгөгдлийг санах ойд хуулах шаардлагагүй, энэ нь аль хэдийн байгаа.

9.1.5 Тасалдал

Оролт гаралтын төхөөрөмж ажиллаж эхэлсний дараа процессор бусад ажлууд руу шилждэг.

Процессорыг ажил дууссан гэж дохио өгөхийн тулд төхөөрөмж нь тухайн төхөөрөмжийн тусгай автобусны шугам дээр (зориулалтын утас биш) дохиог байрлуулснаар тасалдлыг эхлүүлдэг.

Тасалдлын хянагч - төхөөрөмжүүдээс ирж буй тасалдлын үйлчилгээ.

1. Хэрэв хүлээгдэж буй тасалдал байхгүй бол тасалдлыг шууд гүйцэтгэнэ.
2. Хэрэв зохицуулагдаагүй тасалдал байгаа бол хянагч тасалдлыг үл тоомсорлодог. Гэхдээ төхөөрөмж нь тасалдлын дохиог боловсруулах хүртэл автобусанд үргэлжлүүлэн барьдаг.

Үйл ажиллагааг тасалдуулах

Ажлын алгоритм:

• Төхөөрөмж тасалдлын дохиог тохируулдаг
• Тасалдлын хянагч нь төхөөрөмжийн дугаарыг зааж тасалдлыг эхлүүлдэг
• Процессор нь процедурыг дуудаж тасалдлын боловсруулалтыг хийж эхэлдэг
• Энэ процедур нь тасалдлын хянагч руу тасалдал хүлээн авсныг хүлээн зөвшөөрдөг.

9.2 Оролт гаралтын программ хангамжийн зарчим

9.2.1 Оролт гаралтын програм хангамжийн даалгавар

I/O програм хангамжийн шийдвэрлэх ёстой гол ажлууд:

• Төхөөрөмжөөс хараат бус байдал - жишээлбэл, файлаас өгөгдөл уншиж байгаа программ нь юу уншиж байгаагаа бодох шаардлагагүй (CD, HDD гэх мэт). Бүх асуудлыг үйлдлийн системээр шийдэх ёстой.
• Нэг төрлийн нэршил - файл эсвэл төхөөрөмжийн нэр ялгаатай байх ёсгүй. (UNIX систем дээр энэ нь үг хэллэгээр хийгддэг).
• Алдаатай ажиллах - алдаа нь хянагч, драйвер гэх мэт түвшинд баригдаж болно.
• Өгөгдөл дамжуулах - синхрон ба асинхрон(сүүлийн тохиолдолд процессор өгөгдөл дамжуулалтыг эхлүүлж, тасалдал хүртэл бусад ажил руу шилждэг).
• Буферлэх
• Зориулалтын (принтер) болон зориулалтын бус (диск) төхөөрөмжүүдийн асуудал - принтерийг зөвхөн нэг хэрэглэгч, дискийг олон хэрэглэгчдэд өгөх ёстой. Үйлдлийн систем нь үүссэн бүх асуудлыг шийдэх ёстой.

Оролт гаралтын үйлдлийг гүйцэтгэх гурван үндсэн арга нь:

• Програм хангамжийн I/O
• Тасалдал дээр суурилсан I/O
• DMA ашиглан I/O

Тэднийг илүү нарийвчлан авч үзье.

9.2.2 Програм хангамжийн I/O

Энэ тохиолдолд төв процессор бүх ажлыг гүйцэтгэдэг.

Энэ аргыг ашиглан ABCDEFGH мөрийг хэвлэх үйл явцыг харцгаая.

ABCDEFGH мөрийг хэвлэх алхамууд

Хэвлэх алгоритм:

1. Хэвлэх мөрийг хэрэглэгчийн орон зайд цуглуулдаг.
2. Системийн дуудлагыг дуудах замаар процесс нь принтерийг олж авдаг.
3. Системийн дуудлагыг дуудах үед процесс нь хэвлэгч рүү мөр хэвлэхийг хүсдэг.
4. Үйлдлийн систем нь мөрийг цөмийн горимд байрлах массив руу хуулдаг.
5. Үйлдлийн систем нь санах ойн зураглал бүхий хэвлэгчийн өгөгдлийн бүртгэлд эхний тэмдэгтийг хуулдаг.
6. Тэмдгийг цаасан дээр хэвлэсэн.
7. Заагчийг дараагийн тэмдэгт рүү тохируулсан.
8. Процессор нь принтерийн бэлэн битийг бэлэн болгохыг хүлээнэ.
9. Бүгд давтагдана.

Принтерийн буфер ашиглах үед эхлээд бүх мөрийг буферт хуулж, дараа нь хэвлэж эхэлнэ.

9.2.3 Тасалдал дээр суурилсан оролт/гаралт

Хэрэв өмнөх жишээнд буфер ашиглаагүй бөгөөд принтер секундэд 100 тэмдэгт хэвлэдэг бол тэмдэгт тус бүр 10 мс зарцуулагдах бөгөөд энэ хугацаанд процессор ажиллахгүй байж, принтер бэлэн болтол хүлээнэ.

Үүнтэй ижил жишээг харцгаая, гэхдээ бага зэрэг сайжруулсан.

Хэвлэх алгоритм:

1. 8-р цэгт мөн адил хамаарна.
2. Процессор нь принтерийг бэлэн болтол хүлээдэггүй, харин төлөвлөгчийг дуудаж өөр ажил руу шилждэг. Хэвлэх процесс хаагдсан байна.
3. Принтер бэлэн болмогц процессор руу тасалдал илгээдэг.
4. Процессор нь хэвлэх процесс руу шилждэг.

9.2.4 DMA ашиглан оролт/гаралт

Өмнөх аргын сул тал нь тэмдэгт хэвлэх бүрт тасалдал үүсдэг.

Алгоритм нь ялгаагүй, гэхдээ DMA хянагч бүх ажлыг гүйцэтгэдэг.

9.3 Програм хангамжийн түвшин ба оролт гаралтын функцууд

Дөрвөн I/O түвшин:

I/O түвшин

9.3.1 Тасалдал зохицуулагчид

Тасалдал нь үйлдлийн системийн гүнд аль болох гүн нуугдаж байх ёстой бөгөөд ингэснээр үйлдлийн системийн аль болох бага хэсэг нь тэдгээртэй харьцах ёстой. I/O эхлүүлсэн драйверийг хаах нь дээр.

Алгоритм:

1. Драйвер нь I/O үйлдлийг эхлүүлнэ.
2. Жолооч өөрөө блоклодог
   - семафор дээр буулгах процедурыг гүйцэтгэх замаар
   - төлөв хувьсагч дээр хүлээх процедурыг гүйцэтгэх замаар
   - мессеж дээр хүлээн авах процедурыг гүйцэтгэх замаар
3. Тасалдал үүснэ
4. Тасалдал зохицуулагч ажиллаж эхэлнэ
5. Тасалдал зохицуулагч нь драйверын блокыг тайлж чадна (жишээ нь семафор дээр дээшлэх процедурыг гүйцэтгэх замаар)

9.3.2 Төхөөрөмжийн драйверууд

Төхөөрөмжийн драйвер - төхөөрөмж бүрт шаардлагатай. Өөр өөр үйлдлийн системүүд өөр өөр драйверуудыг шаарддаг.

Драйверууд хянагчийн бүртгэлд хандахын тулд цөмийн нэг хэсэг байх ёстой (цул системд).

Энэ нь үйлдлийн систем гацах гол шалтгаануудын нэг юм. Учир нь драйверуудыг ихэвчлэн төхөөрөмж үйлдвэрлэгчид бичиж, үйлдлийн системд оруулдаг.

Төхөөрөмжийн драйверуудын логик байршил. Үнэн хэрэгтээ хянагч болон жолооч нарын хооронд мэдээлэл солилцох автобусаар дамждаг.

Драйверууд стандарт интерфейсээр дамжуулан үйлдлийн системтэй харилцах ёстой.

Драйверууд дэмжих ёстой стандарт интерфейсүүд:

• Блок төхөөрөмжүүдийн хувьд
• Тэмдэгтийн төхөөрөмжүүдийн хувьд

Өмнө нь цөмийг суулгахын тулд системийн цөмүүдийг дахин хөрвүүлэх шаардлагатай байсан.

Өнөө үед үйлдлийн системүүд ихэвчлэн драйверуудыг ачаалдаг. Зарим драйверууд халуун ачаалалтай байж болно.

Жолооч нарын гүйцэтгэдэг функцууд:

• унших эсвэл бичих хүсэлтийг боловсруулах
• төхөөрөмжийг эхлүүлэх
• төхөөрөмжийн эрчим хүчний менежмент
• төхөөрөмжийг халаах (сканнер)
• төхөөрөмжийг асаах эсвэл хөдөлгүүрийг асаах

9.3.3 Төхөөрөмжөөс хамааралгүй I/O програм хангамж

Төхөөрөмжөөс хамааралгүй I/O програм хангамжийн онцлогууд:

• Төхөөрөмжийн драйверуудын нэгдсэн интерфейс,
• Буферлэх
• Алдааны мессежүүд
• Хуваарилагдсан төхөөрөмжийг хураан авах, суллах (түгжих)
• Төхөөрөмжийн бие даасан блокийн хэмжээ

Төхөөрөмжийн драйверуудад зориулсан тууштай интерфейс

Энэ нь интерфэйсээс гадна асуудлуудыг агуулдаг

• төхөөрөмжийн нэршил
• төхөөрөмжийн хамгаалалт

Буферлэх

Буферийн зарим жишээг авч үзье.

a) Буфергүй оролт - оруулсан тэмдэгт бүрийн дараа тасалдал үүсдэг

b) Хэрэглэгчийн орон зайд буфер хийх - шаардлагатай санах ойн хуудсуудыг физик санах ойд ачаалах шаардлагатай.

в) Хэрэглэгчийн орон зайд хуулах замаар цөмд буфер хийх - зөвхөн цөмийн буфер дүүрсэн үед л хуудсыг ачаалдаг бөгөөд цөмийн буферээс хэрэглэгчийн буфер хүртэлх өгөгдлийг нэг үйлдлээр хуулдаг. Цөмийн буфер дүүрсэн, хэрэглэгчийн буфер хуудас хараахан ачаалагдаагүй үед асуудал үүсч болно.

d) Цөм дэх давхар буфер - хэрэв нэг буфер дүүрсэн ба түүнийг хуудаснаас гаргаж байх үед тэмдэгтүүд хоёр дахь буферт бичигдэнэ.

Алдааны мессежүүд

Хамгийн олон тооны алдаа нь оролт гаралтын үйлдлээс үүсдэг тул тэдгээрийг аль болох эрт илрүүлэх шаардлагатай. Төхөөрөмжөөс хамааран алдаа нь маш өөр байж болно.

Хуваарилагдсан төхөөрөмжүүдийг барьж, суллах

Нэг удаад зөвхөн нэг процесс ажиллах шаардлагатай төхөөрөмжүүдийн (хэвлэгч) хувьд төхөөрөмжүүдийг олж авах, гаргах чадвартай байх шаардлагатай. Нэг процесс нь төхөөрөмжийг эзлэх үед бусад нь дараалалд ордог.

Төхөөрөмжийн бие даасан блокийн хэмжээ

Блокийн хэмжээ нь дээд түвшний хувьд ижил байх ёстой бөгөөд төхөөрөмжөөс (диск дээрх салбарын хэмжээ) хамаарахгүй.

9.4. Хэрэглэгчийн орон зай I/O програм хангамж

Энэ програм хангамжийн функцууд:

• I/O системийн дуудлагад хандах (номын сангийн процедураар).
• Оролт/гаралтыг форматлах (форматыг жишээлбэл ASCII болгон өөрчлөх)
• Түр хадгалах (зориулалтын төхөөрөмжүүдийн хувьд) - процесс (жишээлбэл, хэвлэх дэмон) болон түр хадгалах лавлах үүсгэсэн.

Оролт/гаралтын түвшин ба функцүүдийн хураангуй

Оролтын гаралтын системийн түвшин ба үндсэн чиг үүрэг

Үндсэн I/O дэд систем Компьютерийн системийн процессууд болон драйверуудын хооронд зуучлагч болдог. Оролт/гаралтын үйлдлүүдийг гүйцэтгэх системийн дуудлагууд нь шаардлагатай төхөөрөмжийн драйверын функцүүдийн дуудлага болгон хувиргадаг. Гэсэн хэдий ч үүрэг хариуцлага үндсэн дэд системЗөвхөн ерөнхий системийн дуудлагыг хувийн драйверын функц руу шилжүүлэх үйлдлүүдээр хязгаарлагдахгүй. Үндсэн дэд системдэмжлэг үзүүлэх зэрэг үйлчилгээгээр тооцоолох системийг хангадаг блоклох, блоклохгүйТэгээд асинхрон системийн дуудлага, буферлэхТэгээд кэш хийхоролт, гаралтын өгөгдөл, түр зуурын хэрэгжилт, гадаад төхөөрөмжийг онцгойлон авах, алдаатай ажиллах болон тасалддагоролт/гаралтын үйл ажиллагааны явцад үүсэх, эдгээр үйлдлийг гүйцэтгэх хүсэлтийн дарааллыг төлөвлөх. Эдгээр үйлчилгээг илүү нарийвчлан авч үзье.

Блоклох, блоклохгүй, асинхрон системийн дуудлага

Оролт/гаралтын үйлдлүүдийг хэрэгжүүлэхтэй холбоотой бүх системийн дуудлагуудыг процесс ба оролт гаралтын төхөөрөмжийн хоорондын харилцан үйлчлэлийг хэрэгжүүлэх аргуудын дагуу гурван бүлэгт хувааж болно.

· Ихэнх програмистуудын хамгийн сайн мэддэг эхний бүлэгт багтдаг системийн дуудлагыг хаах. Нэрнээс нь харахад ийм дуудлагыг ашиглах нь түүнийг эхлүүлсэн процессыг хаахад хүргэдэг, өөрөөр хэлбэл процессыг үйлдлийн систем мужаас шилжүүлдэг. гүйцэтгэлмужид хүлээлт. Системийн дуудлагын дагуу заасан бүх оролт гаралтын үйлдлүүд дууссаны дараа үйлдлийн систем нь процессыг төлөвөөс шилжүүлдэг. хүлээлтмужид бэлэн байдал. Процесс дахин сонгогдсоны дараа гүйцэтгэл, энэ нь системийн дуудлагын эцсийн өгөөж болох газар байх болно. Ийм системийн дуудлагыг ашиглах ердийн тохиолдол бол процесс нь төхөөрөмжөөс тодорхой хэмжээний өгөгдлийг хүлээн авах шаардлагатай бөгөөд үүнгүйгээр цаашид ажиллах боломжгүй болно.

· Хоёр дахь бүлэгт багтана блоклохгүй системийн дуудлага. Тэдний нэр нь асуудлын мөн чанарыг яг нарийн тусгадаггүй. Хамгийн энгийн тохиолдолд ашигласан үйл явц блоклохгүй дуудлага, улсын мэдэлд шилжүүлээгүй хүлээлтбүх. Системийн дуудлага нь одоогийн нөхцөл байдлаас (төхөөрөмжийн төлөв байдал, өгөгдлийн бэлэн байдал гэх мэт) өгөгдсөн оролт гаралтын үйлдлүүдийг бүрэн, хэсэгчлэн эсвэл огт гүйцэтгэсэн даруйдаа буцаж ирдэг. Илүү төвөгтэй нөхцөл байдалд процессыг хааж болох боловч үүнийг задлах нөхцөл нь шаардлагатай бүх үйлдлүүдийг дуусгах эсвэл тодорхой хугацааны төгсгөл юм. Ердийн хэрэглээ хөдөлмөр их шаарддаг тооцоолол хийх үед гарнаас мэдээлэл хүлээн авах үе үе шалгалт байж болно.

· Гурав дахь бүлэгт багтана асинхрон системийн дуудлага. Хэрэглэсэн процесс асинхрон системийн дуудлага, үүнд хэзээ ч хаагддаггүй. Системийн дуудлага нь шаардлагатай I/O үйлдлүүдийг эхлүүлж, нэн даруй буцаж ирдэг бөгөөд үүний дараа процесс нь ердийн үйл ажиллагаагаа үргэлжлүүлдэг. Дараа нь үйлдлийн систем нь зарим хувьсагчийн утгыг өөрчлөх, түүнд дохио, мессеж илгээх эсвэл өөр аргаар оролт гаралтын ажиллагаа дууссан гэж процесст мэдэгддэг. Үүний ялгааг тодорхой ойлгох шаардлагатай блоклохгүйТэгээд асинхрон дуудлага. Блоклохгүй системийн дуудлагаүйл ажиллагаа явуулахунших нэн даруй буцаж ирэх боловч хүссэн тооны байт, бага тоо эсвэл огт уншихгүй байж болно. Асинхрон системийн дуудлагаУчир нь энэ үйлдэл нь мөн нэн даруй буцаж ирэх боловч шаардлагатай тооны байт эрт орой хэзээ нэгэн цагт бүрэн унших болно.

Буфер болон кэш хийх

Доод буферЭнэ нь ихэвчлэн хоёр төхөөрөмж, хоёр процесс эсвэл процесс ба төхөөрөмжийн хооронд өгөгдөл солилцох үед мэдээлэл хадгалах санах ойн тодорхой хэсгийг хэлдэг. Хоёр үйл явцын хоорондох мэдээлэл солилцох нь үйл явцын хамтын ажиллагааны талбарт хамаарах бөгөөд бид холбогдох лекцээр түүний зохион байгуулалтыг нарийвчлан авч үзсэн. Энд бид солилцоонд оролцогчдын нэг нь гадны төхөөрөмж байх тохиолдолд буферийн хэрэглээг сонирхох болно. Буфер ашиглахад хүргэдэг гурван шалтгаан бий .

· Эхний шалтгаан буферлэх– Эдгээр нь солилцоонд оролцогчдын мэдээлэл хүлээн авах, дамжуулах өөр өөр хурд юм. Жишээлбэл, гарнаас модем руу өгөгдлийн урсгал дамжуулах тохиолдлыг авч үзье. Гар нь мэдээлэл дамжуулах хурд нь хүний ​​бичих хурдаар тодорхойлогддог бөгөөд ихэвчлэн модемийн өгөгдөл дамжуулах хурдаас хамаагүй бага байдаг. Бусад процесс, төхөөрөмжид нэвтрэх боломжгүй болгохын тулд модемийг бичих бүх хугацаанд ашиглахгүйн тулд оруулсан мэдээллийг буфер эсвэл хангалттай хэмжээтэй хэд хэдэн буферт хуримтлуулж, буфер дүүргэсний дараа модемоор дамжуулан илгээхийг зөвлөж байна. .

· Хоёр дахь шалтгаан буферлэх– Эдгээр нь биржийн оролцогчид нэгэн зэрэг хүлээн авах эсвэл хүлээн авах боломжтой өөр өөр хэмжээний өгөгдөл юм. Өөр нэг жишээ татъя. Мэдээллийг модемоор хангаж, хатуу диск дээр бичнэ үү. Модем болон хатуу диск нь өөр өөр гүйлгээний хурдтай байхаас гадна өөр өөр төрлийн төхөөрөмж юм. Модем нь тэмдэгт төхөөрөмжба диск байх үед өгөгдлийг байтаар гаргадаг блок төхөөрөмжҮүний тулд бичих үйлдлийг гүйцэтгэхийн тулд буферт шаардлагатай мэдээллийн блокыг хуримтлуулах шаардлагатай. Энд нэгээс олон буфер ашиглаж болно. Эхний буферийг дүүргэсний дараа модем нь эхний буферийг хатуу диск рүү бичихтэй зэрэгцэн хоёрдугаарт дүүргэж эхэлдэг. Хатуу дискний хурд модемийн хурдаас хэдэн мянга дахин их байдаг тул хоёр дахь буфер дүүрэх үед эхнийх нь бичих ажиллагаа дуусч, модем дахин эхний буферийг дүүргэх боломжтой болно. хоёр дахь нь диск рүү бичихтэй зэрэгцэн.

· Гурав дахь шалтгаан буферлэхнь үйлдлийн системийн цөмийн буфер болон арын хэсэгт оролт гаралтыг гүйцэтгэдэг програмуудын мэдээллийг хуулбарлах хэрэгцээтэй холбоотой юм. Хэрэглэгчийн зарим процесс хаягийн орон зайн мэдээллийг гадаад төхөөрөмж рүү харуулахыг хүссэн гэж үзье. Үүнийг хийхийн тулд өгөгдөл байгаа санах ойн хэсгийн хаяг, түүний хэмжээг параметр болгон дамжуулж ерөнхий нэрээр системийн дуудлагыг гүйцэтгэх ёстой. Хэрэв гадаад төхөөрөмж түр зуур завгүй байгаа бол түүнийг суллах үед шаардлагатай хэсгийн агуулга эвдэрч болзошгүй (жишээлбэл, системийн дуудлагын асинхрон хэлбэрийг ашиглах үед). Ийм нөхцөл байдлаас зайлсхийхийн тулд хамгийн хялбар арга бол системийн дуудлагын эхэнд шаардлагатай өгөгдлийг RAM-д байнга байрладаг үйлдлийн системийн цөмийн буфер руу хуулж, энэ буферээс төхөөрөмж рүү гаргах явдал юм.

Үгний дор кэш(бэлэн мөнгө - "бэлэн мөнгө"), бид энд авч үзэхгүй, уг гарал үүслийг нь ихэвчлэн удаан санах ойн хаа нэгтээ байрлах мэдээллийн хуулбарыг агуулсан хурдан санах ойн хэсэг гэж ойлгодог бөгөөд энэ нь үйл ажиллагааг хурдасгах зорилготой юм. тооцоолох систем. Бид санах ойн шатлалыг авч үзэхдээ ийм ойлголттой танилцсан. IN үндсэн I/O дэд системЭнэ хоёр ойлголтыг андуурч болохгүй буферлэхТэгээд кэш хийх, Хэдийгээр эдгээр функцийг гүйцэтгэхийн тулд ихэвчлэн ижил санах ойн талбайг хуваарилдаг. Буфер нь ихэвчлэн системд байгаа цорын ганц өгөгдлийн багцыг агуулдаг бол кэш нь өөр газар байгаа мэдээллийн хуулбарыг агуулдаг. Жишээлбэл, процессын хэрэглэгчийн зайнаас диск рүү өгөгдлийг хуулахын тулд үндсэн дэд системд ашигладаг буферийг блок дээр өөрчлөх, дахин унших үйлдлүүд хангалттай давтамжтайгаар хийгдсэн тохиолдолд тухайн өгөгдлийн кэш болгон ашиглаж болно.

Функцүүд буферлэхТэгээд кэш хийхнутагшуулах албагүй үндсэн I/O дэд систем. Тэдгээрийг жолоочид, тэр ч байтугай хэсэгчлэн хэрэгжүүлж болно төхөөрөмжийн хянагч, чиглэсэн нууцлаг үндсэн дэд систем.

Дамжуулах болон төхөөрөмжийг хулгайлах

Үзэл баримтлалын талаар далдлахБид курсийнхээ эхний лекц дээр анх удаа нэг даалгаврын бодит оролт/гаралтын үйлдлүүдийг өөр нэг даалгаврын гүйцэтгэлтэй хослуулах боломжтой болсон механизмын талаар ярилцсан. Одоо бид энэ ойлголтыг илүү нарийн тодорхойлж чадна. Дамар гэдэг нь төхөөрөмжийн оролт эсвэл гаралтын өгөгдлийг агуулсан буферийг хэлж байгаа бөгөөд үүнийг ашиглахаас өөр өөр процессуудын хооронд зайлсхийх ёстой. Үнэн бол орчин үеийн тооцоолох системд дамарыг өгөгдөл оруулахад бараг ашигладаггүй, гэхдээ голчлон гаралтын мэдээллийг хуримтлуулах зориулалттай.

Принтерийг гадаад төхөөрөмж гэж үзье. Хэдийгээр хэвлэгч нь олон процессоос ирж буй мэдээллийг нэгэн зэрэг хэвлэх боломжгүй ч процессуудыг хэвлэгч рүү зэрэгцүүлэн гаргахыг зөвшөөрөх нь зүйтэй болов уу. Үүнийг хийхийн тулд үйлдлийн систем нь мэдээллийг принтер рүү шууд илгээхийн оронд гаралтын өгөгдлийг диск дээрх буферт хуримтлуулж, процесс тус бүрээр тусдаа дамар файл болгон зохион байгуулдаг. Процесс дууссаны дараа түүний харгалзах дамар файлыг бодит хэвлэхийн тулд дараалалд оруулна. Ийм үйлдлийг хангах механизмыг түр зуурын гэж нэрлэдэг.

Зарим үйлдлийн системүүд уралдааны нөхцлийг арилгахын тулд түр зуурын горимыг ашиглахын оронд төхөөрөмжийг процессоор дангаар нь олж авах механизмыг ашигладаг. Хэрэв төхөөрөмж үнэ төлбөргүй бол процессуудын аль нэг нь үүнийг онцгой эзэмшиж болно. Энэ тохиолдолд энэ төхөөрөмж дээр үйлдэл хийхийг оролдсон бусад бүх процессууд хаагдах болно ( хүлээлт), эсвэл төхөөрөмжийг барьж авсан үйл явц дуусгавар болох эсвэл үйлдлийн системд үүнийг ашиглахаас татгалзсан тухай тодорхой мэдэгдэх хүртэл үйлдлийг гүйцэтгэх боломжгүй тухай мэдээллийг хүлээн авах болно.

Түр хадгалах болон төхөөрөмж барих механизмаар хангах нь онцгой эрх юм үндсэн оролт/гаралтын дэд систем.

Тасалдал, алдааг зохицуулах

Хэрэв гадны төхөөрөмжтэй ажиллахдаа компьютерийн систем нь түүний төлөв байдлыг санал авах аргыг ашигладаггүй, харин механизмыг ашигладаг. тасалддаг, тэгээд хэзээ тасалддагӨмнө дурьдсанчлан процессор нь төлөвөө хэсэгчлэн хадгалж, хяналтыг тусгай боловсруулалтын програм руу шилжүүлдэг. тасалддаг.

Үүнтэй ижил боловсруулалтын журам тасалддаголон оролт гаралтын төхөөрөмжид ашиглаж болно (жишээ нь эдгээр төхөөрөмжүүд нь нэг шугамыг хуваалцдаг бол тасалддаг, тэднээс явах тасалдлын хянагч), иймээс боловсруулах програмын эхний үйлдэл нь ямар төхөөрөмж гаргасан болохыг тодорхойлох явдал юм таслах. Төхөөрөмжийг мэдсэнээр бид холбогдох үйлдлийг эхлүүлсэн процессыг тодорхойлж чадна. Учир нь таслахамжилттай болон амжилтгүй гүйцэтгэлийн аль алинд нь тохиолдвол бидний хийх дараагийн зүйл бол утгыг шалгах замаар үйл ажиллагаа амжилттай дууссан эсэхийг тодорхойлох явдал юм. алдааны битВ статусын бүртгэлтөхөөрөмжүүд. Зарим тохиолдолд үйлдлийн систем нь гарсан алдааг нөхөхийн тулд тодорхой арга хэмжээ авч болно. Жишээлбэл, уян диск унших алдаа гарвал та тушаалыг хэд хэдэн удаа ажиллуулж болно. Хэрэв алдааг нөхөх боломжгүй бол үйлдлийн систем нь дараа нь үйлдлийг хүссэн процесст мэдэгдэх болно (жишээлбэл, системийн дуудлагаас тусгай буцах кодтой). Хэрэв энэ үйл явцыг дуусгахаас өмнө хаасан бол үйлдлийн систем үүнийг төлөвт оруулдаг бэлэн байдал. Хэрэв суллагдсан төхөөрөмжид сэтгэл хангалуун бус бусад хүсэлт байгаа бол үйлдлийн систем нь дараагийн хүсэлтийг эхлүүлж, төхөөрөмжид нэгэн зэрэг мэдэгдэнэ. таслахболовсруулсан. Энэ бол үнэндээ боловсруулалт юм тасалддагдуусч, систем нь CPU-ийн ашиглалтыг төлөвлөж эхлэх боломжтой.

Боловсруулах үйлдлүүд тасалддаггарсан алдааны нөхөн төлбөрийг зохих жолоочийн мөрөнд хэсэгчлэн шилжүүлж болно. Үүнийг хийхийн тулд хоорондын интерфейс жолоочТэгээд үндсэн оролт/гаралтын дэд системөөр нэг функц нэмнэ - боловсруулах функц тасалддаг intr .

Асуулга төлөвлөлт

Ашиглаж байна блоклохгүй системийн дуудлагаХүссэн төхөөрөмж нь зарим үйлдлүүдийг хийх завгүй байгаа бололтой. Энэ тохиолдолд блоклохгүй дуудлагахүссэн тушаалуудыг гүйцээхгүйгээр шууд буцаж болно. ашиглан оролт гаралтын үйлдлийг гүйцэтгэх хүсэлтийг зохион байгуулахдаа блоклохэсвэл асинхрон дуудлагаХэрэв төхөөрөмж завгүй байвал тухайн төхөөрөмж рүү хүсэлт гаргах шаардлагатай болно. Үүний үр дүнд төхөөрөмж бүр муж дахь процессуудын сэтгэл ханамжгүй хүсэлтүүдийн жагсаалттай холбоотой байдаг хүлээлт, мөн асинхроноор ажиллаж байгаа хүсэлтүүд. муж хүлээлтнь янз бүрийн оролт гаралтын төхөөрөмжүүдийг хүлээж буй процессын дарааллын багцад хуваагддаг (эсвэл янз бүрийн объектын төлөвийн өөрчлөлтийг хүлээж байна - семафор, мессежийн дараалал, монитор дахь нөхцөлийн хувьсагч гэх мэт - 6-р лекцийг үзнэ үү).

Одоогийн хүсэлтийг бөглөсний дараа үйлдлийн систем (үр дүнг боловсруулах явцад тасалддаг) жагсаалтад байгаа хүсэлтүүдийн алийг нь дараа нь хангах ёстойг шийдэж, түүний гүйцэтгэлийг эхлүүлэх ёстой. Бэлэн болсон жагсаалтаас дараагийн гүйцэтгэх үйл явцыг сонгохын тулд бид богино хугацааны үйл явцын төлөвлөлтийг хийх ёстой байсан шиг энд ямар нэгэн төлөвлөлтийн алгоритмыг ашиглан төхөөрөмжүүдийн ашиглалтыг төлөвлөх хэрэгтэй. Ийм төлөвлөлтийн шалгуур, зорилго нь үйл явцын төлөвлөлтийн шалгуур, зорилгоос бага зэрэг ялгаатай.

Төхөөрөмжийн ашиглалтыг төлөвлөх ажлыг ихэвчлэн хуваарилдаг үндсэн оролт/гаралтын дэд системГэсэн хэдий ч зарим төхөөрөмжүүдийн хувьд хамгийн сайн хуваарийн алгоритмууд нь тэдгээрийн дотоод үйл ажиллагааны нарийн ширийн зүйлстэй нягт холбоотой байж болно. Ийм тохиолдолд эдгээр дэлгэрэнгүй мэдээлэл нь үндсэн дэд системээс далд байдаг тул хуваарь гаргах ажиллагааг холбогдох төхөөрөмжийн драйвер дотор шилжүүлдэг. Үүнийг хийхийн тулд драйверын интерфейс дээр өөр нэг тусгай функцийг нэмж оруулсан бөгөөд энэ нь дараагийн хүсэлт - стратегийн функцийг сонгоно

9. 5 . UNIX дахь I/O хяналтын дэд системийн үндсэн зарчмууд

1. Энэхүү дэд систем нь өгөгдлийн удирдлагын дэд системтэй (файлын систем) нэгдмэл байдлаар бүтээгдсэн. Хэрэглэгч нь хэрэглэгчийн интерфэйс болон файлуудын аль алинд нь нэвтрэх нэгдсэн арга замаар хангагдсан. UNIX үйлдлийн систем дэх файлыг диск, видео терминал гэх мэт өгөгдлийн багц гэж ойлгодог; аливаа PU нь тусгай файл гэж тооцогддог. Програм хангамжийн процесс нь өгөгдлийг тусгай файлд гаргах хүсэлт гаргахад үйлдлийн систем нь хүсэлтийг таслан авч, өгөгдлийг зохих төхөөрөмж рүү дамжуулдаг. Тусгай файлаас өгөгдлийг унших нь ижил төстэй байдлаар зохион байгуулагдсан - энэ нь хяналтын самбараас өгөгдлийг хүлээн авах явдал юм. Тиймээс, жишээлбэл, дискний файл болон тусгай дэлгэцийн файлд хандах хандалтыг ижил системийн дуудлагын багцаар хангадаг.

2. UNIX-ийн оролт гаралтын дэд системийн өөр нэг онцлог нь синхрон системээр ажилладаг. Оролцох шаардлагатай аливаа програм хангамжийн процесс нь хүсэлт гаргасан цэг дээр заасан тусгай файлаас оруулах ажиллагаа дуусах хүртэл түр зогсдог. Гаралт гаргах үед гаралтыг систем хэрэглэгчийн буферт хүлээн авах хүртэл гаралтыг хүссэн цэг дээр процесс түр зогсдог. Оролт-гаралтын ийм зохион байгуулалт нь CPU-ийн сул зогсолтыг бууруулснаар олон програмтай компьютерийн ажиллагааны горимд CPU-ийн цагийг ашиглах үр ашгийг нэмэгдүүлэхэд хүргэдэг. Бодит цагийн системд (RTS) оролт-гаралтын дэд системийн үйл ажиллагааны асинхрон зарчмыг илүү их ашигладаг болохыг анхаарна уу, учир нь энэ тохиолдолд яаралтай боловсруулах шаардлагатай үйл явдалд RTS-ийн хариу өгөх хугацаа багасдаг.

3. UNIX үйлдлийн систем дэх PU-г удирдахын тулд эдгээр PU-уудтай 2 төрлийн интерфэйсийг ашигладаг: байт чиг баримжаатай ба блок хандалттай. Блок чиглэсэн интерфэйс нь PU-уудтай харилцах боломжийг олгодог бөгөөд үүнийг 512 байт блокуудын дарааллаар шийдвэрлэх боломжтой. Ийм PU нь голчлон VZU юм. Ийм интерфейсийг зохион байгуулах үндэс нь OP-д дэмжигдсэн буферийн систем юм. Байт чиглэсэн интерфэйс нь хэвлэх төхөөрөмж, дэлгэцийн гар болон бусад зарим төхөөрөмжид хандахад ашиглагддаг бөгөөд буферлэлтийг ашигладаггүй.

4. Оролт гаралтын удирдлагын системд мөн драйверууд болон OS цөмийг янз бүрийн төхөөрөмжийн драйверуудтай логик холбох тусгай хүснэгтүүдийн багц багтана. Драйвер бүр 2 хэсгээс бүрдэх ба ижил төрлийн хэд хэдэн төхөөрөмжид үйлчлэх боломжтой.

Драйверын эхний хэсэг нь тусгай файлуудыг нээх, хаах, унших, бичих үйлдлүүдийг гүйцэтгэх, мөн хяналтын нэгжийн тусгай ажиллагааны горимыг удирдах програм хангамжийн модулиудын багцыг агуулдаг. Тодорхой төхөөрөмжтэй ажиллаж эхлэхийн тулд та тухайн төхөөрөмжтэй холбоотой тусгай файл нээх эсвэл үүсгэх хэрэгтэй. Файл нээх нь файлыг нээх процессын санах ойн хэсэгт хадгалагдсан файлын нэр болон зарим нэг хувьсагчийн хооронд холбоо тогтоох үйл явц юм. Файлын тодорхойлогчийн дугаар гэж нэрлэгддэг энэ хувьсагчийг нээлттэй файлын үйл ажиллагаанд цаашид ашигладаг. Файлыг нээсний дараа нээлхийг гүйцэтгэсэн процесс нь төхөөрөмжид хандах эрхтэй болно. Хаалтын ажиллагаа нь зорилгынхоо эсрэг бөгөөд програм хангамжийн процесс болон заасан PU хоорондын холболтыг таслахад хүргэдэг.

Драйверын хоёр дахь хэсэг нь тасалдлыг боловсруулах модуль юм. UNIX үйлдлийн систем дэх ихэнх хяналтын нэгжийг удирдахдаа таслах аргыг ашигладаг. Байт чиглэсэн PU-ийн хувьд байт дамжуулсны дараа, блок чиглэсэн PU-ийн хувьд блок дамжуулсны дараа тасалдал үүсдэг. Драйверын нэг хэсэг болох тасалдлыг боловсруулах модуль нь хяналтын хэсэгтэй ажиллахаа больсон эсвэл түүнтэй үргэлжлүүлэн ажиллаж, түүнд шинэ даалгавар өгдөг.

UNIX OS оролт-гаралтын системийг бий болгох зарчмуудын заримыг хожим бий болгосон үйлдлийн системүүдэд, жишээлбэл, 80x86 MP хэмжээтэй IBM PC компьютерт ажилладаг MS DOS дээр хэрэгжүүлсэн.

Оролт-гаралтын системийг бий болгох өөр нэг онцлогийг авч үзье. SRV эсвэл цаг хуваах системд ашиглагддаг олон програмтай компьютерийн ажиллагааны горимд ижил хяналтын нэгжийн хувьд өөр өөр програмуудын хүсэлтийн дараалал гарч ирж болно. Энэхүү хяналтын төвөөс хүлээн авсан үйлчилгээний хүсэлтийг дараалан гүйцэтгэх ажлыг зохион байгуулахын тулд OP-д тусгай хүснэгт зохион байгуулах ёстой бөгөөд түүний агуулга нь цаг мөч бүрт хүлээн авсан хүсэлтийн дараалал, агуулгыг хоёрдмол утгагүй харуулдаг; дараагийн өргөдлийг гүйцэтгэсний дараа энэ талаархи мэдээллийг авч үзэж буй хүснэгтээс хассан болно. Ийм хүснэгтийг компьютертэй харьцдаг ихэнх хяналтын нэгжүүдэд зориулж зохион байгуулах ёстой.