lecture 3

Алгоритмын тухай ойлголт, алгоритмыг дүрслэх хэлбэрүүд

Товч агуулга:

·         Алгоритмын тухай ойлголт

·         Алгоритмын чанарууд

·         Алгоритмын үндсэн алхмууд

·         Алгоритмыг дүрслэх хэлбэрүүд

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

Алгоритмын тухай ойлголт

Хүмүүс өдөр тутмын үйл ажиллагаандаа олон тооны алгоритмыг гүйцэтгэж байдаг боловч үүнийгээ тэр болгон мэдэрдэггүй байна. Тухайлбал тухайн өдрийн ажил төрөл болон тодорхой нэгэн ажлыг хийхдээ тогтсон дэс дарааллыг мөрддөг. Алгоритмын тухай ойлголт нь нэгэн төрлийн бодлогуудыг бодох ерөнхий арга олж тогтоох гэсэн оролдлоготой уялдан математикт анх үүссэн. Алгоритм гэдэг нэр томъёог арифметикийн дөрвөн үйлдлийг гүйцэтгэх дүрэм боловсруулсан Узбекийн математикч Мухаммед Ибн Мусса Аль-Хорезмын нэрнээс гаралтай гэж үздэг.

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

Жишээ: Өгсөн m, n гэсэн хоёр натурал тооны хамгийн их ерөнхийлөн хуваагчийг олох алгоритмын үгээр дүрсэлсэн хэлбэрийг авч үзье.

1.       Өгсөн m, n тоонуудыг оруул

2.       Хэрэв m>n байвал 4-ралхамд, эсрэг тохиолдолд 3-р алхамд тус тус шилж

3.       Хэрэв mбайвал 5-ралхамд, эсрэг тохиолдолд 6-р алхамд тус тус шилж

4.       m-д m-n гэсэн утга олгоод 2-р алхамд шилж

5.       n-д n-m гэсэн утга олгоод 2-р алхамд шилж

6.       m-ийг бодлогын үр дүн (хариу) болгож ав

7.       Үр дүнг бичиж гарга

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

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

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

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

Алгоритмын чанарууд

Алгоритм нь дараах чанаруудтай байна.

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

2.       Алгоритмын аливаа алхмын үйлдлийг гүйцэтгэгч нэгэн утгатайгаар ойлгохын зэрэгцээгээр гүйцэтгэж чаддаг байна. Энэ нь алгоритмын тодорхой байх чанар юм.

3.       Алгоритм нь төгсгөлөг тооны алхамтай байна.

4.       Алгоритмын аливаа алхам болон алгоритмыг бүхэлд нь биелүүлэхэд тодорхой үр дүн гардаг байх ёстой. Үүнийг алгоритмын үр дүнтэй байх чанар гэнэ. Дээрх жишээний 4-р алхмын үр дүн нь m-ийн m-n –ээр багассан утга байна.

5.       Алгоритм нь зөвхөн тухайн өгөгдөлд төдийгүй уг өгөгдөлтэй ижил төрлийн бүх өгөгдөлд хүчинтэй байна. Энэ чанарыг алгоритмын нийтлэг чанар гэнэ. Жишээ нь дээрх алгоритмаар дурын хоёр натурал тооны ерөнхийлөн хуваагчийг олж болно.

Алгоритмын үндсэн алхмууд

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

Алгоритмчлалд тоо, хувьсагч гэсэн ойлголтыг хэрэглэх бөгөөд хувьсагчдыг өөр хооронд нь ялгах, тэдгээр дээр хийх үйлдлүүдийг бичихийн тулд үг, үсгээр тэмдэглэнэ. Энэ тэмдэглэгээг хувьсагчийн нэр гэнэ. Нэр нь хувьсагчийн утга хадгалагдаж байгаа санах ойн үүрийн хаягийг төлөөлнө. Энэ утгаар нь хувьсагчид нэр олгохыг хувьсагчийг хаяглах ч гэж нэрлэдэг. Хувьсагчийн нэр заавал үсгээр эхэлсэн байх ба харин дурын тооны үсэг, цифрээс бүрдсэн байж болно. Гэхдээ хаяг товч байх нь бичлэг хялбар болох сайн талтай юм. Алгоритм зохиох үйл ажиллагааны анхны элемент нь өгөгдөл, завсрын ба эцсийн үр дүн болох хэмжигдэхүүнүүдийг хаяглах явдал юм. Хэмжигдэхүүнүүд дээр үйлдэл хийхдээ тэдгээрийн хаягийг зааж өгнө. Жишээнь: I+1 бичлэг нь I хувьсагчийн утга дээр буюу I гэсэн дугаартай үүрэнд байгаа тоон дээр 1-ийг нэм гэсэн утга санааг илтгэнэ.

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

Алгоритмд хэмжигдэхүүнийг үйлдлийн тэмдгээр холбож илэрхийллийг үүсгэнэ. Илэрхийлэлд дараах үйлдлүүдийг бичиж болно.

1.       Нэмэх, хасах, үржих, хуваах, зэрэгт дэвшүүлэх гэсэн арифметик үйлдлүүд

2.       Тоон хэмжигдэхүүнүүдийн утгыг жиших (>=,<=,=,<>,><) үйлдлүүд

3.       Логик нэмэх (OR), логик үржих (AND), логик үгүйсгэх (NOT) үйлдлүүд

Жишээ нь: Х>=0 AND Y>=0 гэсэн илэрхийлэл нь X, Y тоонууд зэрэг эерэг байх тохиолдолдл “ ҮНЭН”, бусад тохиолдлуудад “ХУДАЛ” гэсэн утгатай байна.

4.       │x│,  sin(x) , cos(x), tg(x), In(x), e^x, arctg(x), функцүүдийн утгыг олох үйлдлүүд

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

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

Бодолтын утга олгох алхам:  Компьютерийн нэг үндсэн үүрэг нь мэдээллийг хувирган боловсруулах явдал юм. Алгоритмд тодорхой томъёогоор хэмжигдэхүүний утгыг бодож гаргах алхам зайлшгүй гардаг. Энэ алхмыг бодолтын утга олгох алхам гэнэ. Энэ алхам нь утгыг бодож олох гэж байгаа илэрхийлэл,  гарах утгыг хадгалах хаяг гэсэн хоёр хэсэгтэй байна. Ямар нэгэн хэмжигдэхүүнд утга олгоход хуучин утга нь устдаг гэдгийг анхаарах хэрэгтэй. Жишээ нь: а-д 10, в-д 5 байсан үед а-д в-г олго гэсэн үйлдлийг хийхэд а-ийн утга 5 болно.

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

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

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

1.            Хэмжигдэхүүний нэр нь I, J, K, L, M, N гэсэн үсгүүдийн аль нэгээр эхэлсэн байвал бүхэл утгатай гэж үзнэ. 

2.            Хэмжигдэхүүний нэрний ард төрөл заах үндсэн үгийг бичнэ.

Алгоритмыг дүрслэх хэлбэрүүд

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

1. Хүмүүсийн харилцааны ердийн хэл
2. Блок-схем
3. Програмчлалын хэл

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

1.       Мэдээллийг оруулах алхмыг Х-ийг оруул гэж бичнэ. Үүнд: Х нь утгыг нь компьютерийн гараас өгөх хувьсагчийн нэр юм. Хэд хэдэн хувьсагчдыг оруулах гэвэл тэдгээрийн нэрний хооронд таслал тавина.

2.       Бодолтын утга олгох алхмыг Х-д Е-г олго гэж бичнэ. Үүнд Х нь хувьсагчийн нэр бөгөөд Е нь тогтмолтоо, хувьсагчийн нэр, илэрхийллийн аль нэг байна.

3.       Мэдээллийг бичиж гаргах алхмыг Х-ийг хэвлэ гэж бичнэ. Үүнд: Х нь хувьсагчийн нэр эсвэл тогтмол хэмжигдэхүүн байна.

4.       Нөхцөл шалгах алхмын удирдлага шилжүүлэх үйлдлийг N-р алхамд шилж гэж бичнэ. Үүнд N нь алхмын дугаар байна.Нөхцөл шалгах алхмыг :

Хэрвээ А байвал В эсрэг тохиолдолд С

гэж бичнэ. Үүнд: А нь ямар нэгэн нөхцөл, В, С гэдэг нь ямар нэгэн алхам эсвэл удирдлага шилжүүлэх үйлдэл байна. Энэ алхам нь А гэсэн нөхцлийг шалгаад уг нөхцөл үнэн байвал В үйлдлийг, нөхцөл худал байвал С үйлдлийг биелүүлэх болно. Одоо алгоритмыг блок-схемээр дүрслэхтэй танилцая. Блок-схем бол алгоритмын бүтцийг нүдэнд харагдахуйц байдлаар харуулан алгоритмыг графикаар дүрслэх хэлбэр юм. Блок-схемд алгоритмын алхам бүрийг геометрийн дүрсээр тэмдэглэх бөгөөд уг дүрс дотор тухайн алхмын товч утгыг томъёогоор бичнэ. Ийм дүрсийг блок ч гэж нэрлэдэг. Алгоритмыг блок-схемээр дүрслэхэд алгоритмын алхмуудыг дараах байдлаар зурж бичнэ.

1.      

а, b

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

                                                                                                                                                                                       гэж зурж бичнэ.

2.      

I=I+1

Бодолтын утга олгох алхмыг тэгш өнцөгтөөр зурж түүн дотор энэ алхмын томъёог бичнэ. Жишээ нь: I-ийн утгыг 1-ээр нэмэгдүүлэх буюу I-д I дээр нэмэх 1-ийг олго гэдгийг

гэж зурж бичнэ.

3.      

х

Мэдээллийг бичиж гаргах алхмыг хажуу хоёр талыг нь муруйгаар дүрсэлсэн тэгш өнцөгтөөр зурж түүн дотор хувьсагчдын нэрийг эсвэл бичиж гаргах тогтмолыг бичнэ. Жишээ нь: х-ийн утгыг хэвлэн гаргах алхмыг

гэж зурж бичнэ.

4.      

а³b

Удирдлага шилжүүлэх үйлдлийг сумтай тахир шугамаар дүрсэлнэ. Нөхцөл шалгах алхмыг ромбоор зурж түүн дотор нөхцлөө бичнэ. Жишээ нь а нь b-ээс их юмуу тэнцүү гэсэн нөхцлийг шалгах алхмыг

+

-

 

                                                                                                                    

гэж зурж бичнэ. Ромбын дээд оройд өмнөх алхмаас шилжиж ирэх зам, хажуу хоёр оройд нөхцөл үнэн эсвэл худал байхад шилжиж очих зам харгалзана. Энд нэмэх тэмдэгтэй орой нь нөхцөл үнэн байх тохиолдолд бодолтыг үргэлжлүүлэх замыг заана. Нэмэх хасах тэмдгийн оронд харгалзан 1 ба 0 цифрийг эсвэл “тийм” ба “үгүй” гэсэн үгсийг хэрэглэж болно.

5.       Хэмжигдэхүүний төрлийг зарлах алхмыг блок схемд дараах дүрсээр дүрсэлж уг дүрс дотор хэмжигдэхүүний нэр ба түүний төрлийг заахад хэрэглэдэг түлхүүр үгийг бичнэ.

 

Хэмжигдэхүүний энгийн төрлүүд, түүнд харгалзах түлхүүр үгсийг дараах хүснэгтээр үзүүлэв.

Хэмжигдэхүүний төрөл	Төрлийг заах түлхүүр үг
Бодит тоон төрөл	бодит
Бүхэл тоон төрөл	бүхэл
Мөр төрөл	мөр
Тэмдэгт төрөл	тэмдэгт

Жишээ нь:  x нь бодит,  I  нь бүхэл утгыг авдаг хэмжигдэхүүнүүд бол тэдгээрийг дараах байдлаар зарлана.

a:  бодит; I:   бүхэл

 

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

№	Алхмын нэр	Блок-схемд хэрэглэх дүрс	Алхмын үүрэг
1. 2. 3. 4. 5. 6. 7. 8.	Бодолтын утга олгох алхам Нөхцөл шалгах алхам Оруулах алхам Гаргах алхам Эхлэл, төгсгөлийн алхам Хэмжигдэхүүний Төрлийг зарлах алхам Холбоос Тайлбар		Хэмжигдэхүүнийутгыгөөрчлөнө. Ямар нэгэн нөхцлөөс хамааран алгоритм биелэх замыг сонгоно. Өгөгдөл, завсрын хэмжигдэхүүнүүдийн утгыг оруулна. Өгөгдөл, завсрын хэмжигдэхүүнүүдийн утга болон үр дүнг гаргана. Эхлэл,  төгсгөл болон мэдээллийг боловсруулах процессыг зогсоохыг заана. Хэмжигдэхүүний төрлийг зарлахад хэрэглэнэ. Харьцангуй хол орших алхмууд хоорондын шилжилтийг заахад хэрэглэнэ. Ямар нэгэн алхмын гүйцэтгэх үүргийг дэлгэрэнгүй тайлбарлахад хэрэглэнэ.

               

Алгоритмыг блок-схемээр дүрслэхийн жишээ болгон Евклидийн алгоритмыг блок-схемээр дүрслэе.

алг-1

m,n

m>n

m

m

Тєгсгєл

n=n-m

m=m-n

 

+

-

                                                                                                                                                                       

+

-

                                                                                                                                

                                             

Энэ блок-схемийг өмнө авч үзсэн Евклидийн алгоритмын үгээр бичиж дүрсэлсэн хэлбэртэй нь харьцуулан харж ямар алхамд ямар блок харгалзаж байгааг болон үгээр бичсэн алгоритм, блок-схемээр дүрсэлсэн алгоритм хоёрын ялгаатай ба нийтлэг шинжүүдийг харж болно. Жишээ нь: блок-схемийн m=m-n гэсэн бичлэг нь m-д m-n гэсэн утгыг олго гэсэн өгүүлбэртэй тэнцүү чанартай байна. Блок-схемийн блокуудын байрлал ямар ч байж болох боловч блокуудыг хооронд нь сумаар холбоход хялбар байх, блокуудын биелэгдэх дэс дараалал ил тод байх зэрэг талуудыг бодолцон блокуудыг байрлуулах хэрэгтэй юм. Алгоритмыг програмчлалын хэлээр дүрслэхэд програмчлалын ямар нэгэн хэл сонгон авч тухайн хэлнийхээ үг зүй, өгүүлбэр зүйн дүрмүүдийг баримтлан алгоритмыг тэр хэлээрээ бичнэ. Алгоритмыг ийм байдлаар дүрслэхэд програмчлалын хэлний тухай мэдлэг алгоритм зохиогчид зайлшгүй шаардагдана. Иймээс алгоритмыг програмчлалын хэлээр дүрслэхийн өмнө урьдчилан програмчлалын хэл судлан, эзэмшсэн байх хэрэгтэй юм.