Алгоритм. Түүний төрөл, шинж чанар. Алгоритм гэж юу вэ, яагаад хэрэгтэй вэ?Алгоритм ухагдахуун гэж юу вэ?

Компьютер ашиглан асуудлыг шийдэх нь алгоритм зохиохоос эхэлдэг. Алгоритм гэж юу вэ?

"Алгоритм" гэсэн нэр томъёоны гарал үүсэл нь дөрвөн арифметик үйлдлийг гүйцэтгэх дүрмийг боловсруулсан агуу математикч Мухаммед аль-Хорезми (763-850) нэртэй холбоотой юм.

ГОСТ 19781-74-ийн дагуу:

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

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

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

Алгоритмуудын үндсэн шинж чанарууд:

Бэлэн байдал оролт эх өгөгдөл.

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

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

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

Мөч – алгоритмын гүйцэтгэлийг хязгаарлагдмал тооны алхмаар гүйцээх ёстой.

Зөв байдал – алгоритм нь асуудлын зөв шийдлийг зааж өгөх ёстой.

Массын дүр (ерөнхий байдал) - эхний өгөгдлөөр ялгаатай тодорхой ангиллын асуудлыг шийдвэрлэх алгоритмыг боловсруулсан.

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

Алгоритм бичих арга замууд

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

байгалийн хэлээр (алгоритмын аман бичлэг);

блок диаграмм хэлбэрээр (график хэлбэр);

програмчлалын хэл дээр.

Алгоритмыг аман бичлэг хийх. Амаар хэлбэрийг ихэвчлэн боловсруулсан алгоритмуудыг тайлбарлахад ашигладаг жүжигчин - хүн. Тушаалуудыг энгийн хэлээр бичиж, дарааллаар нь гүйцэтгэдэг. Командууд нь томьёо болон тусгай тэмдэглэгээг ашиглаж болох боловч команд бүр нь гүйцэтгэгчдэд ойлгомжтой байх ёстой. Тушаалуудын байгалийн дарааллыг зөрчиж болно (жишээлбэл, өмнөх команд руу шилжих шаардлагатай эсвэл ямар нэг нөхцөлд дараагийн командыг алгасах шаардлагатай бол), энэ тохиолдолд командуудыг дугаарлаж, таны хүссэн тушаалыг зааж өгч болно. явахыг хүсч байна. Жишээлбэл, 3-р алхам руу очэсвэл 4-р алхамаас давт.

График хэлбэр. Алгоритмуудыг блок диаграмм хэлбэрээр үзүүлэв. Блок диаграммыг бүтээх тусгай стандартууд байдаг бөгөөд үүнд блокуудын график дүрслэлүүд тодорхойлогддог. Алгоритм командыг блок дотор энгийн хэлээр эсвэл математикийн томьёо ашиглан бичдэг. Блокууд нь командыг гүйцэтгэх дарааллыг харуулсан холбооны шугамаар тодорхой дүрмийн дагуу холбогддог.

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

a l g o r i f m) нь логик, математикийн үндсэн ойлголтуудын нэг юм. A. гэж бид тооцооллыг тодорхойлсон яг зааврыг хэлж байна. өөр өөр байж болох анхны өгөгдлөөс хүссэн үр дүнд хүргэх үйл явц. Дээр дурдсан “тооцоолох”, “тооцоолох” гэсэн үгсийг дижитал тооцоолол гэдэг нарийн утгаар ойлгож болохгүй. Тиймээс аль хэдийн сургуулийн алгебрийн хичээл дээр тэд үсгийн тооцооллын талаар ярьдаг бөгөөд энд үсэг нь аль хэдийн арифметикийн хувьд тоонуудыг орлуулах үүрэг гүйцэтгэдэг. Тооцоололд ямар ч хэмжигдэхүүнийг заагаагүй тэмдэг гарч ирдэг: хаалт, тэнцүү тэмдэг, арифметик тэмдэг. үйлдлүүд. Бид цаашаа явж, дурын тэмдэг, тэдгээрийн хослол бүхий тооцооллыг авч үзэх боломжтой; "А." гэсэн ойлголтыг тайлбарлахдаа "тооцоолол" гэсэн нэр томъёог ийм өргөн утгаар ойлгодог. Тиймээс бид A. нэг хэлээс нөгөө хэл рүү орчуулах тухай, А. галт тэрэгний диспетчерийн ажил (галт тэрэгний хөдөлгөөний талаархи мэдээллийг захиалга болгон боловсруулах) болон алгоритмын бусад жишээнүүдийг ярьж болно. кибернетикийн судалсан хяналтын үйл явцын тодорхойлолт. А-ИЙН УТГА.“А” гэдэг үг өөрөө. 9-р зуунаас эхэлдэг. (энэ нь Алгоритмигаас гаралтай бөгөөд энэ нь Хорезмийн математикч аль-Хорезмигийн араб нэрийн 12-р зуунд хийгдсэн латин галиглал юм). Өнөө үед хамгийн энгийн А. нь бага сургуульд аль хэдийн гарч ирдэг - энэ бол А арифметик юм. үйлдлүүд (А. зууны дунд үед Европт А. орчин үеийн сургуулийн арифметик, өөрөөр хэлбэл аравтын бутархайн байрлалын тооллын систем ба түүн доторх тоолох урлагийг яг ингэж нэрлэдэг байсан, учир нь аль-Хорезмийн зохиол нь хамгийн анхны биш юмаа гэхэд анхныхуудын нэг байсан юм. Үүнээс гадна Европ нь албан тушаалын системтэй танилцсан). Бага ангид А дансны хичээл заадаг гэдгийг онцлон тэмдэглэе. Хүний тоо нэмэх чадварын тухай ярихдаа тэр аль нэг хоёр тооны хувьд эрт орой хэзээ нэгэн цагт тэдгээрийн нийлбэрийг олж чадна гэсэн үг биш, харин аливаа тооны тодорхой хоёр бүртгэлд хамаарах тодорхой нэг төрлийн нэмэх аргыг мэддэг байх ёстой. , өөрөөр хэлбэл, A. нэмэх (ийм А.-ийн жишээ бол "багана" дахь тоонуудын сайн мэддэг А. нэмэх явдал юм). А. нь шинжлэх ухаанд алхам тутамд олддог; аливаа асуудлыг "ерөнхий хэлбэрээр" шийдвэрлэх чадвар гэдэг нь үндсэндээ тодорхой А-г эзэмшсэн гэсэн үг юм. массын асуудал. "Асуудал" гэсэн нэр томъёог тодорхой шинж чанартай объектыг олох даалгавар гэж ойлгож болно; энэ объект гэж нэрлэгддэг асуудлын шийдэл (ялангуяа асуултын хариултыг олох асуудлын хувьд шийдэл нь тавьсан асуултын "тийм" эсвэл "үгүй" гэсэн хариулт юм). Асуудал нь шийдэлгүй бол шийдэгдэхгүй, өөрөөр хэлбэл. шаардлагатай шинж чанартай объект байхгүй. Тиймээс асуудлыг шийдвэрлэх боломжгүй байгаа нь агностицизмын үндэслэл болохгүй нь тодорхой байна. дүгнэлт; эсрэгээр, тодорхой асуудлын шийдэгдэх боломжгүй байдлыг тогтоох нь чухал танин мэдэхүй юм. Үйлдэл. Массын асуудал нь хэд хэдэн тусдаа, "ганц" асуудлуудаар тодорхойлогддог бөгөөд тэдгээрийг шийдвэрлэх ерөнхий аргыг (өөрөөр хэлбэл А.) олох шаардлагаас бүрддэг. Олон нийтийн асуудлыг шийдвэрлэх боломжгүй гэдэг нь захидал харилцааг олох боломжгүй гэсэн үг юм. A. Массын бодлого нь логик, математикийн хувьд туйлын онцлог бөгөөд чухал юм. Ганц асуудлыг шийдэх нь ч гэсэн ихэвчлэн үнэ цэнэтэй байдаг, учир нь энэ нь бүхэл бүтэн ангиллын асуудлыг шийдвэрлэх ерөнхий аргыг нэгэн зэрэг өгдөг; Үүний зэрэгцээ, массын асуудлыг томъёолох нь тодорхой ангиллын асуудлыг нэг асуудал болгон хувиргах гэсэн үг юм - энэ ангийн бүх асуудлыг шийдвэрлэх хариултыг олох асуудал; Эндээс хувь хүн, өвөрмөц, бүх нийтийн гэх мэт диалектикийн ангиллын хоорондын уялдаа холбоо илэрдэг. Массын асуудлын үүрэг нь утга учрыг тодорхойлдог A. Тодорхой массын асуудлыг шийдвэрлэх боломжгүй байдлыг тогтоох (өөрөөр хэлбэл тухайн цувралын бүх бие даасан асуудлын шийдлийг олох боломжийг олгодог нэг алгоритм байхгүй байх) нь танин мэдэхүйн хамгийн чухал үйлдэл юм. Тодорхой бие даасан асуудлыг шийдвэрлэхийн тулд ийм асуудал тус бүрт тусгайлсан аргууд үндсэндээ шаардлагатай байгааг харуулж байна. Тиймээс уусдаггүй массын асуудлууд байгаа нь танин мэдэхүйн үйл явцын шавхагдашгүй байдлын тодорхой илэрхийлэл болж өгдөг. Агуулна. "А." гэсэн ойлголтыг бий болгох үндэс болсон үзэгдлүүд нь шинжлэх ухаанд чухал байр суурь эзэлсээр ирсэн. Математик, логикт үүссэн олон асуудал нь тодорхой бүтээмжтэй аргуудыг хайхад оршдог. Ийм аргыг хайх нь ялангуяа тохиромжтой математик бий болсонтой холбогдуулан эрчимжсэн ба логик бэлгэдэл, түүнчлэн хэд хэдэн тохиолдолд эдгээр аргууд үндсэндээ байхгүй байгааг ойлгох нь энэ бүхэн шинжлэх ухааны хөгжилд хүчтэй хүчин зүйл болсон юм. мэдлэг. Аливаа асуудлыг шууд тооцоогоор шийдэх боломжгүй гэдгийг ухаарсан нь 19-р зуунд бий болсон. олонлогийн онол. үзэл баримтлал. Зөвхөн энэ үзэл баримтлалыг эрчимтэй хөгжүүлсний дараа (түүний хүрээнд орчин үеийн ойлголтод конструктив аргын тухай асуудал огтхон ч гарч ирдэггүй) сүүлийн хэдэн арван жилд дахин бүтээн байгуулалтын асуудал руу буцах боломжтой болсон, гэхдээ шинэ түвшинд. , талстжсан үзэл баримтлалаар баяжуулсан "А." (мэдлэгийн хөгжлийн спираль хэлбэрийн талаархи Лениний байр суурийг харуулсан өөр нэг жишээ). Хэдийгээр "А" гэсэн ойлголт байдаг. Энэ нь "багц" гэсэн ойлголт шиг тийм ч өргөн хүрээтэй хийсвэр зүйл биш бөгөөд түүхэндээ эдгээр ойлголтуудын эхнийх нь хоёр дахь ойлголтоос хожуу үүссэнийг санамсаргүй гэж үзэж болохгүй. ЖИШЭЭ A. “Олонлог”, “харилцаа”, “натурал тоо”, “харилцаа” гэх мэт ойлголттой адил “А” ойлголт. үндсэн логик-математик юм үзэл баримтлал (логик, математикийн ангиллын нэг). Энэ нь энгийн ойлголтоор дамжуулан албан ёсны тодорхойлолтыг зөвшөөрдөггүй, гэхдээ (бусад математикийн ангиллын нэгэн адил) туршлагаас шууд хийсвэрлэдэг. "А" гэсэн ойлголт. Зөвхөн жишээн дээр суралцах боломжтой. Жишээ 1. Боломжит анхны өгөгдөл нь саваа (I) -ээс бүрдсэн хязгаарлагдмал хоосон бус хослолууд, i.e. I, II, III объектууд гэх мэт. A. нь дараахь зүйлээс бүрдэнэ. дүрэм (1-р дүрэмээс эхлэн дагаж мөрдөх ёстой): 1 °. Доорх хамгийн зүүн талын савааны доогуур зурж, 2° дүрмээр явна уу. 2°. Хамгийн баруун талын савааг орой дээр нь тавиад 3° дүрмээр үргэлжлүүлнэ. 3°. Доогуур зураастай савааг шалгаж, доогуур зураагүй бол 4° дүрмээр явна. 4°. Доор нь зурсан савааг нэн даруй авч үзье; хэрэв доогуур зураагүй бол 5°-ын дүрэм рүү шилжинэ; хэрэв доогуур нь зурсан бол 7°-ын дүрмийг хэрэгжүүлнэ. 5°. Доод зураасыг доогуур зурааснаас дараагийн зураас руу нэн даруй шилжүүлж, 6 ° дүрмээр үргэлжлүүлнэ үү. 6°. Загалмайлсан саваанаас дээд шугамыг шууд урд талын шугам руу шилжүүлж, 7 ° дүрмийн хэрэгжилтийг үргэлжлүүлнэ үү. 7°. Загалмайлсан саваа болон түүнийг дагаж байгаа бүх савааг арчиж, 8 градусын дүрэм рүү шилжинэ. 8°. Доогуур зураастай савхны доод мөрийг арилгана; юу болсон бол үр дүн. Энэ А.-г анхны өгөгдөл болгон авсан |||| хослолд хэрэглэснээр бид дараалсан байдлаар олж авна: дүрмээр 1° – |||, дүрмээр 2° – ? || , дүрмийн дагуу 3°, 4°, 5° – | ? | , дүрмийн дагуу 6°, 3°, 4° – | ? | 7° дүрмийн дагуу – | ?, 8° дүрмийн дагуу – || (үр дүн). Хэрэв бид A.-г ||| хослолд хэрэглэхийг оролдвол: 1° дүрмийн дагуу – ? ||, 2° дүрмийн дагуу – ? | , дүрмийн дагуу 3°, 4°, 5° – | ? , 6° дүрмийн дагуу – | I |, дараа нь та 3 ° дүрмийг хэрэгжүүлэх хэрэгтэй, гэхдээ 3 ° дүрмийг зөвхөн доогуур зурсан савааг доогуур зураагүй тохиолдолд л хэрэгжүүлэх боломжтой. Тиймээс, одоогийн нөхцөл байдлын хувьд, А.-д хэрхэн үргэлжлүүлэх талаар зааврыг агуулаагүй болно; гэж нэрлэгддэг үр дүнгүй зогсолт (үр дүн дагалддаггүй зогсолт). Ерөнхийдөө үүнийг томъёолсон гэдгийг анзаарахад хялбар байдаг. A. тэгш тооны саваа ямар ч хослол хэрэглэж үед үр дүнг өгдөг бөгөөд энэ тохиолдолд үр дүн нь хагас саваа тоо бүрдсэн хослол юм; A. сондгой тооны савхаас бүрдэх ямар ч хослолд хэрэглэхэд ямар ч үр дүн өгөхгүй. Жишээ 2. Логик, математикт ямар ч төгсгөлтэй тэмдгийн багцыг нэрлэдэг. "цагаан толгой", үүнд багтсан тэмдэг нь цагаан толгойн "үсэгүүд" бөгөөд ар араасаа бичигдсэн үсгүүдийн эцсийн (хоосон) дараалал k.-l. цагаан толгой гэж нэрлэдэг Энэ цагаан толгойн "үг". Жишээлбэл, араб тоо нь цагаан толгойн үсгийг бүрдүүлдэг бөгөөд бүхэл тооны аравтын дүрслэл бүр энэ цагаан толгойн үг юм. a, b гэсэн хоёр үсгийн цагаан толгойг (a, b) авч үзье. Энэ цагаан толгойн үгсийн жишээ нь: v, aw, vva aaavavv гэх мэт. Дараахь зүйлсийн аль нэгийн дагуу энэ цагаан толгойн үсгээс ижил цагаан толгойн үсгийн өөр үг рүү шилжихийг "зөвшөөрөгдсөн" гэж нэрлэе. хоёр дүрэм: 1) хэрэв үг нь aP хэлбэртэй бол P нь дурын үг бол Pb үг рүү очно уу; 2) үг нь va? шиг харагдаж байвал хаана? – ямар ч үг, Рава гэдэг үг рүү оч. Дараа нь мөр, зааврыг томъёолсон болно: "к.-л. үгнээс эхлэн (анхны өгөгдөл болгон авсан) aa? хэлбэрийн үг авах хүртэл зөвшөөрөгдөх шилжилтийг хийнэ үү; ийм төрлийн үгийг олж авах үед. , эхний хоёр үсгийг хаяад үр дүн нь үлдэнэ." Хамгийн ихдээ нэг шилжилтийн дүрэм хэрэгжих боломжтой байдаг тул бид томъёолдог жор нь цагаан толгойн үсгийг бүрдүүлдэг бөгөөд анхны өгөгдөл нь цагаан толгойн үсгийн үгс (a, b). Ваваа гэдэг үгийг анхны өгөгдөл болгон авч үзье. 2-р дүрмийн дагуу бид waaava авдаг. 2-р дүрмийг дахин хэрэглэснээр бид aavaava авах болно. Бидний зааврын дагуу бид зогсоох ёстой; (ваваа гэдэг үгэнд А.-г хэрэглэсний) үр дүн нь ваваа. Ваава гэдэг үгийг анхны өгөгдөл болгон авч үзье. 2-р дүрмээр бид ававаа авдаг. 1-р дүрмээр бид ваававыг авдаг. Дараа нь бид ававава, вававав, вававава гэх мэтийг дараалан авдаг. Процесс хэзээ ч дуусахгүй гэдгийг баталж болно (өөрөөр хэлбэл, хоёр a үсгээр эхэлсэн үг хэзээ ч гарч ирэхгүй бөгөөд үүссэн үг бүрийн хувьд хүчинтэй шилжилт хийх боломжтой болно). Ийнхүү ваава үгэнд хэрэглэхэд ямар ч үр дүн өгөхгүй А. Ваав гэдэг үгийг анхны өгөгдөл болгон авч үзье. Бид vaavv, avvav, vvavav гэсэн дарааллаар авдаг. Цаашилбал, 1 ба 2-р дүрмийн аль нь ч хэрэгжих боломжгүй бөгөөд үүний зэрэгцээ үр дүн гарсангүй. Иймээс awaav гэдэг үгэнд хэрэглэхэд мөн л үр дүн гарахгүй. А.-ийн үндсэн шинж чанарууд А.А.Марковын үзэж байгаагаар А. нь дараах үндсэн шинж чанаруудаар тодорхойлогддог. онцлог: а) алгоритмын тодорхой байдал. жор, түүний нарийвчлал, ерөнхий ойлгомжтой байдал нь дур зоргоороо байх зай үлдээдэггүй (энэ жорын тодорхой байдлаас шалтгаалан алгоритмын үйл явц нь тодорхойлогддог: үйл явцын үе шат бүр дараагийн үе шатыг өвөрмөц байдлаар тодорхойлдог); б) А бүрийн боломжоос бүрдэх масс. тодорхой хязгаарт өөр өөр байгаа анхны өгөгдлөөс шилжих; в) хүссэн үр дүнд хүрэхэд чиглэсэн үр дүнтэй байдал. A.-ийн детерминизм нь нэг хүн өөр хүнтэй харилцах боломжийг баталгаажуулдаг бөгөөд ингэснээр нөгөө хүн эхнийх нь оролцоогүйгээр А.-г гүйцэтгэх боломжтой болно; Детерминизмын ижил шинж чанар нь А.-ийн гүйцэтгэлийг машинд шилжүүлэх боломжийг олгодог. Шинжилгээний массын шинж чанар нь боломжит анхны өгөгдлийн тодорхой багц (шинжилгээ тус бүрийн хувьд өөрийн гэсэн) байгааг таамаглаж байна. Энэ нийлбэрийг хэрхэн тогтоох нь өөр асуулт юм. Аливаа A.-тай харгалзах боломжит анхны өгөгдлийн багцыг A.-аас тусад нь заагаагүй, харин натурал байдлаар зааж өгсөн гэж бид үзэж болно. энэ А.-ийн агуулгын дагуу дүрс (жишээлбэл, А. баганаар нэмэхэд харгалзах олонлог нь аравтын бутархайн систем дэх бүх тооны хос бичлэгээс бүрдэнэ). Тодорхой объектыг А.-ийн анхны өгөгдөл болгон сонгосон тохиолдолд бид энэ объектод А.-г хэрэглэх тухай ярьдаг. Хэрэв A. тодорхой объектод хэрэглэхэд үр дүн өгдөг бол тэд үүнийг энэ объектод хэрэглэсэн гэж хэлдэг. A.-ийн үр нөлөө нь A. боломжит анхны өгөгдлүүдийн харгалзах багцаас дурын объектод хэрэглэгдэх ёстой гэсэн үг биш юм (Жишээ 1, 2-ыг үзнэ үү). Эхний A.-ийн дурын анхны өгөгдлөөс эхний A. тэдгээрт хамаарах эсэхийг таних A. байхгүй ийм алгоритмыг бий болгох боломжтой гэдгийг энд тэмдэглэх нь зүйтэй. Шинжлэх ухаанд А.-ийн онолын үндсэн хийсвэрлэлүүд. Практикт хэд хэдэн онцлог шинж чанарууд бий болсон. Математик болон логик хийсвэрлэлийн хувьд. Эдгээр нь юуны түрүүнд бодит хязгааргүй байдлын хийсвэрлэл, тодорхойлох хийсвэрлэл, боломжит бодит байдлын хийсвэрлэл юм. Сов. эрдэмтэн А.А.Марков А.Алгоритмийг авч үзэхэд сүүлийн хоёр нь зайлшгүй шаардлагатайг харуулсан. үйл явц нь хэлтэсүүдэд хуваагддаг. алхам бүр нь маш энгийн гэж үздэг тул боломж нь бодитой юм. хэрэгжилт нь эргэлзээгүй. Үүний зэрэгцээ үр дүнд хүрэхэд шаардагдах эдгээр энгийн алхмуудын тоо маш их байж болох тул үр дүнд хүрэх нь бараг боломжгүй гэж үзэж болно. Гэсэн хэдий ч практик санаа тодорхой тооны алхмуудыг хэрэгжүүлэх боломж эсвэл боломжгүй байдал нь харьцангуй юм. Энэ нь тооцоолол хөгжихийн хэрээр өөрчлөгддөг. гэсэн үг (зарчмын хувьд тодорхой алхамын үндсэн шинж чанарын талаархи санаа нь бас өөрчлөгдөж болно). Тиймээс А.-ын онолд тэд "практик хэрэгжих боломж"-оос хийсвэрлэж, ямар ч хязгаарлагдмал тооны алхмуудыг хэрэгжүүлэх боломжтой гэж үздэг. Тиймээс суралцахдаа А. боломжит боломжийн талаар хийсвэрлэх боломжийг олгодог бөгөөд энэ нь бидний чадавхийн бодит хил хязгаараас хийсвэрлэхээс бүрддэг. Өндөр хурдны цахим тооцооллын хөгжил. машинууд эдгээр хил хязгаарыг улам бүр урагшлуулж байна. Өчигдөр хэрэгжих боломжтой байсан зүйл өнөөдөр бараг хэрэгжих боломжтой болж байна. Энэ нь арифметикийн онолыг тооцоолох практикт ойртуулдаг. машинууд болон эдгээр хоёр салбарыг харилцан баяжуулах боломжийг олгодог. Даалгавруудыг машин руу s/l руу шилжүүлэх. Урьдчилсан мэдээлэлгүйгээр цуврал хийх боломжгүй. A. шийдвэр гаргах. Ийм А.-ийн эмхэтгэл нь дүрмээр бол үндсэн ач холбогдолтой (жишээлбэл, машин орчуулгын асуудалд гол зүйл бол А. орчуулгын эмхэтгэл юм). Боломжит боломжийн талаар хийсвэрлэх нь зөвхөн алгоритмын талаар бодоход зайлшгүй шаардлагатай. үйл явц, мөн эдгээр үйл явцад оролцож буй объектууд ("анхны өгөгдөл" ба "үр дүн" гэх мэт). Тиймээс, аливаа натурал тооны тухай ярихын тулд (илүү нарийвчлалтай, энэ тоог аравтын бутархайн системээр бичих тухай) ярихын тулд бид бөмбөрцөгт багтахгүй тийм том тооны бүртгэлийг авч үзэхийг зөвшөөрөх ёстой; ийн, мөн энд, физикээс хийсвэрлэх. ийм бичлэгийн техник эдийн засгийн үндэслэл, боломжит боломжийн хийсвэрлэлийг ашиглах. Ер нь өгөгдсөн цагаан толгойн үсгээр дур зоргоороо урт үг хэлэхийн тулд боломжит боломжийн хийсвэрлэлд хандах хэрэгтэй. Боломжит техник эдийн засгийн үндэслэлийг хийсвэрлэх хүрээнд барих, авч үзэх боломжтой объектуудыг (бодит хязгааргүй байдлын хийсвэрээс ялгаатай) гэж нэрлэдэг. бүтцийн объектууд. Эдгээр нь k.-l-ийн оруулгуудаар илэрхийлэгдсэн натурал тоонууд юм. тэдгээрийн тэмдэглэгээний систем, өгөгдсөн цагаан толгойн үсгийн үгс гэх мэт, түүнчлэн тоонуудын бүртгэлээс бүрдсэн хос, гурвалсан болон ерөнхийдөө хязгаарлагдмал дараалал, цагаан толгойн үсэг гэх мэт; рационал тоо (энэ нь натурал тооны гурвалсан тоогоор илэрхийлэгдэж болно) гэх мэт илэрхийлэл гэж нэрлэгддэг зүйлүүд нь мөн бүтээх объект юм. тооцоолол буюу албан ёсны системүүд нь А-ийн онолын аппаратыг сүүлийн үед хэрэглэх боломжтой болгодог.Аливаа А.(жорын жор гэж ойлгодог) (энэ жорыг зарим тэмдэгтийн хослол хэлбэрээр бичсэний дараа) гэж үзэж болно. бүтээх объект болгон. Үүний эсрэгээр, бодит хязгааргүй байдлын хийсвэрлэлгүйгээр авч үзэх боломжгүй объектууд нь бүтцийн объектуудын тоонд ордоггүй. Тиймээс, жишээлбэл, конструктив объектууд нь бодит тоо биш (Кантор, Дедекинд эсвэл Вейерштрасс гэсэн утгаараа), геометр юм. цэгүүд ("цэг" гэх мэт хийсвэрлэлд дүн шинжилгээ хийх нь цэгийг жижиг биетүүдийн хязгааргүй систем гэж үзэхэд хүргэдэг) гэх мэт. Бүтцийн объектуудыг байгалийн жамаар бүлэглэдэг. нийлбэр хэлбэрээр, жишээ нь өгөгдсөн цагаан толгойн бүх үгсийн цуглуулга ба ерөнхийдөө ангийн бүх объектын аливаа цуглуулга юм. жагсаалтаас "төрөл". дээрх төрлийн бүтцийн объектууд. Бүтцийн объектын ийм багц бүрийг түүнд хамаарах объектыг барих аргаар тодорхойлно. Бусад үндсэн Бүтээлч объект, архитектурыг авч үзэхэд ашигладаг хийсвэрлэл нь тодорхойлох хийсвэрлэл юм. Зарим тохиолдолд хоёр объектыг адилхан гэж ярьдаг. Тухайн нөхцөл байдалтай уялдуулан "ижил" байх нөхцлийг бүрдүүлдэг. Тиймээс, жишээлбэл, хүн цаасан дээр тооцоолол хийх үед тоонуудын бичсэн фонт нь ихэвчлэн хайхрамжгүй байдаг бөгөөд 1647 ба 1647 оруулгууд нь адилхан гэж тооцогддог; Гэсэн хэдий ч, роман болон налуу үсгийн хоорондох ялгаа мэдэгдэхүйц байх нөхцөл байдлыг төсөөлж болно (жишээлбэл, энэ Философийн нэвтэрхий толь бичигт байгаа үгсийг ойлгоход). Дараа нь хоёр бүртгэлийг аль хэдийн тэгш бус гэж үзэх боловч 1647 ба 1647 бүртгэл нь энгийн тохиолдолд ижил хэвээр байх болно (хэдийгээр эдгээр нь бие махбодийн хувьд өөр объектууд юм). Бүтээлч объектууд нь нэлээд энгийн "элемент хэсгүүд" -ээс бүрддэг (үг үсгээр бүтээгдсэнтэй адил) гэж ихэвчлэн хүлээн зөвшөөрдөг бөгөөд хэрэв тэдгээр нь ижил дарааллаар байрлуулсан ижил элементийн хэсгүүдээс бүрдсэн бол хоёр бүтээцтэй объектыг ижил гэж үздэг. Жишээлбэл, самбар дээр шохойгоор бичсэн тоо, дэвтэрт бэхээр бичсэн тоог ижил гэж үздэг "ижил байдал" гэсэн ойлголтгүйгээр суралцах боломжгүй юм. Танихын хийсвэрлэл нь ижил объектуудын талаар нэг ижил объект гэж ярих боломжийг бидэнд олгодог. Энэ нь "хийсвэр объект" гэсэн ойлголтыг бий болгоход хүргэдэг: тухайлбал хоёр ижил объектыг нэг хийсвэр объектын төлөөлөгч гэж үздэг. Ижил объектод хэрэглэсэн A. бүр нь ижил объект руу хүргэдэг. Тиймээс бид A. бүр хийсвэр конструктив объектыг хувиргах үйл явцыг тодорхойлдог гэж бид үзэж болно. A.-ийн энэхүү шинж чанар (детерминизмын хамт) нь тэдгээрийн давтагдах буюу давтагдах чадварыг тодорхойлдог: хийсвэр бүтээмжтэй объектууд дээр A. хэлбэрээр боловсруулагдсан тул тухайн А-д зөвшөөрөгдөх аливаа тодорхой конструктив объектын хувьд А.-г дахин дахин хуулбарлаж болно. Дээрхээс Эхний өгөгдөл нь эцсийн өгөгдөлтэй ижил байх нь тодорхой болох ёстой. к.-л-ийн хэрэгжилтээс үүсэх үр дүн. А., тэд үргэлж бүтээмжтэй объектууд байдаг ("төлөв" бүр алгоритм. үйл явц нь бүтээлч объект юм!). Бүтээлч бус объектууд дээр боломжит процессуудыг хийх боломжгүй байгаа нь тэдгээрийг ижил эсвэл өөр гэж таних арга байхгүйтэй холбоотой юм (харьц. Мэдээлэл хадгалах салангид хэлбэрийн тасралтгүй хэлбэрүүдээс давуу талуудын талаар кибернетикийн сайн мэддэг байр суурийг харна уу). ). Янз бүрийн үзэл бодол байдаг. А-г судлахад зөвшөөрөгдсөн аргуудын талаар. Математик, логикийн конструктив чиглэлийн төлөөлөгчдийн дэвшүүлсэн нэг нь А.-ийн үзэл баримтлалыг бий болгоход тодорхойлох, боломжит боломжийн хийсвэрлэл хангалттай байдаг. А.-ын онолыг боловсруулах нь эдгээр хийсвэрлэлүүдийн хүрээнд явагдах ёстой. Өөр нэг үзэл A.-г судлах боломжийг логик, математикт ерөнхийд нь зөвшөөрөгдсөн аливаа аргууд, түүний дотор. мөн бодит хязгааргүй байдлын хийсвэрлэлийг шаарддаг. Тиймээс, тодорхой А.-г тодорхой объектод хэрэглэхэд үр дүн өгнө гэдгийг нотлохын тулд хийсвэрлэхтэй нягт холбоотой хасагдсан дундын хуулийг ашиглах шаардлагатай болдог тохиолдлыг төсөөлж болно. бодит хязгааргүй байдлын. А-ийн онолын үндсэн ойлголтууд Үндсэн ойлголтуудын дунд. Арифметикийн үзэл баримтлалын үндсэн дээр үүссэн ойлголтуудад тооцоолж болох функц, шийдэгдэх олонлог, тоолж болох олонлогийн тухай ойлголтууд багтана. Функцийг дууддаг Энэ функцийг дараах байдлаар тооцоолох алгоритм байгаа тохиолдолд тооцоолох боломжтой. мэдрэмж: a) A. нь функцийн тодорхойлолтод багтсан аливаа объектод хамаарах бөгөөд үр дүнд нь энэ объектын аргумент болгон авсан функцийн утгыг өгдөг; b) A. функцийн хамрах хүрээнд ороогүй аливаа объектод хамаарахгүй. Бүтээлч объектуудын тодорхой цуглуулгад (жишээ нь энэ цуглуулгын зарим объектуудаас бүрдсэн олонлог) байрладаг олонлогийг нэрлэдэг. Энэ олонлогийг (заасан олонлогтой харьцуулахад) дараагийнх болгон шийдвэрлэх A. байгаа л бол шийдэгдэх боломжтой (хүссэн багцтай харьцуулахад). мэдрэмж: A. нь хамрах олонлогийн аль ч объектод хамаарах бөгөөд үр дүнд нь энэ объект авч үзэж буй олонлогт хамаарах эсэх асуултын хариултыг өгдөг. Эцэст нь хоосон бус багц (хоосон хэсгийг үзнэ үү) дуудагдана. Энэ олонлогийг дараагийн хэсэгт дугаарласан А байгаа л бол тоолж болно. мэдрэмж: a) ямар ч натурал тоонд А.-г хэрэглэсний үр дүн байгаа бөгөөд авч үзэж буй олонлогт хамаарна; б) зарим натурал тоонд арифметик хэрэглэсний үр дүнд авч үзэж буй олонлогийн элемент бүрийг авч болно. Тодорхойлолтоор хоосон багцыг ихэвчлэн тоолж болохуйц гэж ангилдаг. Ижил тооцоологдох функцийг (тус тусад нь шийдвэрлэх боломжтой олонлог, тоолж болох олонлогууд) өөр A-ийн тусламжтайгаар тооцоолж болно (тус тусад нь шийдвэрлэсэн, тоологдсон). Тодорхойлолтоос харахад тооцоолж болох функцийн аргумент ба утгууд, элементүүд нь шийдвэрлэх боломжтой эсвэл тоолж болох олонлог нь үргэлж бүтээмжтэй объектууд байдаг. Бүтээлч объектуудыг (тогтмол агрегатуудын тодорхой хэсэг) дурын алгоритмаар тэдгээрийн тоогоор солих. дугаарлалт (өөрөөр хэлбэл объектоос дугаараа олж авах алгоритм байдаг ийм дугаарлалт ба эсрэгээр) арифметикийн онолд ихэвчлэн хийдэг шиг зөвхөн ийм тооцоолж болох функцууд, аргументууд болон Эдгээрийн утгууд нь натурал тоо бөгөөд зөвхөн шийдвэрлэх боломжтой, тоолж болох олонлогууд бөгөөд тэдгээрийн элементүүд нь мөн натурал тоо юм. Шийдэгдэх олонлог бүр тоолж болохуйц байдаг гэдгийг баталж болно. Үүний зэрэгцээ тоолж болох боловч шийдвэрлэх боломжгүй багц бүтээх боломжтой байв. Энэхүү анхны тодорхой жишээ (Америкийн эрдэмтэн А. Черч 1936 онд "Элементар тооны онолын нэг шийдэгдээгүй асуудал" өгүүлэлд нийтэлсэн) алгоритм (тухайлбал, барьсан олонлогийг шийдвэрлэх алгоритм) байхгүйн эх сурвалж эсвэл жишээ байв. энэ төрлийн бараг бүх бусад жишээнүүд. Хэрэв энэ болон түүний нэмэлт (объектуудын хавсаргасан олонлогт) хоёуланг нь тоолох боломжтой бол олонлогийг шийдвэрлэх боломжтой болох нь тогтоогдсон. Тиймээс, тоолж болох олонлогт нэмэлтүүд байдаг бөгөөд тэдгээр нь өөрөө тоологдох боломжгүй байдаг. Логик ба логикийн онолын хоорондын холбоо. Шийдвэрлэх, тоолж болох олонлогийн тухай ойлголтууд нь тодорхойлолтуудын ангилалтай нягт холбоотой байдаг (бид зөвхөн ийм тодорхойлолтоор хязгаарлагддаг бөгөөд тэдгээр нь тус бүр нь тодорхой төрлийн объектыг эсвэл ижилхэн объектын тодорхой ангиллыг тодорхойлдог). Та бүхний мэдэж байгаагаар хоёр үндсэн зүйл байдаг. Тодорхойлолтын схемүүд: "Удам, зүйлийн ялгаагаар" болон "индукцаар". "Удам угсаа, өвөрмөц ялгаагаар" тодорхойлохдоо тодорхой нэг багц объектыг ("төрөл") зааж, объектуудаас ялгах онцлогийг ("төрлийн ялгаа") зааж өгсөн байдаг. . Хэрэв; Энэ тодорхойлолт нь бүтээлч, өөрөөр хэлбэл. Объектууд нь бүтээмжтэй бөгөөд тухайн төрөл зүйлийн элементэд зүйлийн ялгаа байгаа эсэх нь алгоритмын хувьд танигдах боломжтой бол тодорхойлсон олонлог нь шийдвэрлэх боломжтой болж хувирна (мөн шийдвэрлэх боломжтой олонлог бүрийг ингэж тодорхойлж болно). Тиймээс уусдаг олонлогууд нь төрөл, өвөрмөц ялгаагаар тодорхойлогддог багцуудаар тодорхойлогддог. "Индукцаар" гэсэн тодорхойлолт нь хоёр хэсгээс бүрдэнэ: тодорхойлогдож буй ангилалд хамаарах объектуудын тодорхой жагсаалтыг агуулсан үндсэн хэсэг, хэрэв ийм төрлийн объектууд ангилалд хамаарахыг заадаг индуктив хэсэг. Тодорхойлогдож буй анги, дараа нь эхний объектуудтай тодорхой хамаарлаар холбогдсон ийм ийм төрлийн объектууд мөн тодорхойлогдсон ангилалд хамаарна. (Объектуудын хэд хэдэн ангиллыг нэгэн зэрэг бие биенээр нь тодорхойлсон тохиолдолд хөндлөн тодорхойлолт гэж нэрлэгддэг илүү төвөгтэй тохиолдлууд бас боломжтой). Хэрэв бид тодорхойлолтыг бүтээлч гэж үзвэл, i.e. Объектууд нь бүтээмжтэй, үндсэн хэсэгт агуулагдах анхны объектуудын жагсаалт хязгаарлагдмал, аль хэдийн тодорхойлсон объектуудаас индуктив хэсэгт агуулагдах шинэ алгоритмд шилжих дүрмүүд (харилцаа байгаа эсвэл байхгүй гэсэн утгаараа индуктив хэсэг нь зарим төрлийн А.-ээр дамжин танигдвал индукцаар тодорхойлогддог олонлог, эсвэл (ижил утгатай) үр дүнтэй бий болсон олонлогийн тухай ойлголтод хүрдэг (ийм тодорхойлолт нь тодорхой үе шатанд үр дүнтэй үүсгэх үйл явцыг тодорхойлдог. хөгжил нь тодорхойлогдсон объектууд "гарч ирэх" эсвэл "үүсгэх"). Индукцийн аргаар оновчтой тодорхойлолтын жишээ бол шатрын зөвшөөрөгдөх байрлалуудын тодорхойлолт юм (өөрөөр хэлбэл тоглоомын үеэр самбар дээр гарч ирж болох байрлалууд). Үндсэн хэсэг нь нэг нэгжийг агуулдаг. эхлэх байрлал. Индуктив хэсэг нь хэсгүүдийн хөдөлгөөний дүрмийг агуулдаг. Тиймээс зөвшөөрөгдөх албан тушаалын багц үр дүнтэй бий болсон. Үр дүнтэй үүсгэсэн олонлогийн өөр нэг жишээ бол k.-l-ийн бүх нотлогдох томьёоны багц юм. албан ёсны систем буюу тооцоо: нотлох томьёоны тодорхойлолтын үндсэн хэсэг нь аксиом, индуктив хэсэг нь дүгнэлтийн дүрмийг агуулдаг (аксиомыг тодорхойлолтоор нотлох боломжтой гэж зарлаж, дараа нь ямар нэгэн томьёо нотлох боломжтой бол тэдгээрээс олж авсан томъёог хэлнэ. Дүгнэлт хийх дүрмүүд нь бас нотлогдож байна). Энд бий болгох үйл явц нь бүх нотлогдох томьёог батлах үйл явц юм. Эцэст нь хэлэхэд, тооцоолол дахь бүх хуурамч томьёог няцаах үйл явц нь үр дүнтэй үүсгэх үйл явцын жишээ юм. Үр дүнтэй үүсгэх үйл явцын тухай ойлголт нь А гэсэн ойлголттой маш нягт холбоотой. Бид А-ийн үзэл баримтлалд тулгуурлан үр дүнтэй үүсгэх үйл явцын тодорхойлолтыг (ойролцоогоор) өгсөн. Эргээд үүсгэх процессын тухай ойлголт нь бидэнд тодорхойлох боломжийг олгодог. Үүний үндсэн дээр, хэрэв А гэсэн ойлголт биш бол ямар ч тохиолдолд тооцоолж болох функцийн тухай ойлголт. Үнэн хэрэгтээ, тодорхой үүсгэх процесс нь хос (x, y) хэлбэртэй объектуудыг "үүсгэх" чадвартай байг, эхний гишүүнтэй давхцаж буй хоёр "үүсгэсэн" хосууд нь ижил хоёр дахь гишүүнтэй байг. Дараа нь процесс явагдана. y = f(x) функцийг ийм байдлаар тодорхойлно: хэрэв x0 нь c.-l-ийн эхний гишүүн бол функц нь x0 объектын хувьд тодорхойлогдоно. үүсгэсэн хос: энэ тохиолдолд x0 аргументийн функцуудын утга нь энэ хосын хоёр дахь гишүүнтэй тэнцүү байна. Тогтоолд тодорхойлсон чиг үүрэг. үр дүнтэй үүсгэх процесс гэдэг утгаараа үүнийг тооцоолох боломжтой [f(x0) олохын тулд бид эхний гишүүн болох x0-тэй хосуудыг олох хүртэл процессыг өргөжүүлэх хэрэгтэй]. Эсрэгээр, тооцоолох функц бүрийг үр ашигтай үүсгэх процессоор тодорхойлж болно. Алгоритм процессууд болон үүсгэх процессууд хоорондоо логикийн хувьд ойрхон байдаг. үзэл бодол. Тэд тус бүр нь зөвхөн бүтээлч үзэл баримтлал дээр суурилдаг. Тэдний хоорондох ялгаа нь алгоритм юм шаардлагын үндсэн дээр үйл явц өрнөж, тодорхой арга замаар ажиллах зөвшөөрлийн үндсэн дээр үүсгэгч үйл явц өрнөдөг. Энд шаардлагатай болон боломжтой хоёрын ялгаа гарч ирдэг (алгоритмын процесст үе шат бүр нь өвөрмөц, өөрөөр хэлбэл өмнөх үе шатаар зайлшгүй тодорхойлогддог бол үе шат бүрийн дараа үүсгэх үйл явц өрнөхөд дараагийн шатанд маш олон боломжууд гарч ирдэг. үе шат). Үр дүнтэй үүсгэх үйл явцын тухай ойлголтыг зохих ёсоор боловсронгуй болгосноор үр дүнтэй үүсгэсэн багц бүрийг тоолж болох ба эсрэгээр нь харуулж байна. Энэхүү нөхцөл байдал нь тоолж болох ба шийдвэрлэгдэх олонлогуудын хоорондох дээрх хамааралтай хослуулан дараах дүгнэлтийг хийх боломжийг бидэнд олгоно. Төрөл, өвөрмөц ялгаагаар бүтээмжтэй тодорхойлолтыг хүлээн зөвшөөрдөг аливаа объектын ангилал нь индукцээр конструктив тодорхойлолтыг хүлээн зөвшөөрдөг боловч эсрэгээр нь биш: индукцаар тодорхойлогддог объектын ангилал байдаг боловч төрөл, төрөл зүйлээр дамжуулан бүтээлч тодорхойлолтыг зөвшөөрдөггүй. тодорхой ялгаа; Энэ ангиллын объектуудад нэмэлт (бүтцийн объектуудын багцаас дээш) үр дүнтэй индуктив тодорхойлолтыг зөвшөөрдөггүй. Бүтээлч үүсгэх процесс бүрийг тохиромжтой тооцооллын баталгаатай томъёог олж авах процесс болгон төлөөлж болно. Тиймээс, саяхан тайлбарласан шинж чанаруудтай ангийн жишээг тодорхой тооцооллын бүх нотлогдох томьёоны анги болгон байгуулж болно. Түүгээр ч барахгүй энэ нөхцөл байдал хангалттай хэмжээгээр агуулагдаж байгаа хэн бүхэнд тохиолддог нь тогтоогдсон. тооцоолол (жишээлбэл, предикатуудын тооцоолол эсвэл арифметикийг албан ёсны болгодог тооцооллын хувьд), учир нь хэрэв тооцоолол хангалттай утга учиртай бол ямар ч үр дүнтэй үүсгэх процессыг түүгээр илэрхийлж болно. Ийм тооцооллын бүх нотлогдох томьёоны ангилал (мэдээжийн хэрэг тоолж болохуйц байх) нь шийдэгдэх боломжгүй тул тооцооллын томьёоны нотлох чадварыг хүлээн зөвшөөрөх алгоритм байдаггүй; Энэ утгаараа тооцооллыг шийдвэрлэх боломжгүй гэж хэлдэг. Бүх нотлогдох тооцооллын томъёоны ангиллыг шийдэх боломжгүй тул энэ нь нөхөх болно. үүний дагуу бүх нотлогдоогүй томьёоны анги нь тоологдох боломжгүй тул ямар ч үүсгэх процессоор олж авах боломжгүй; ялангуяа эх хувилбарын нотлогдоогүй бүх томьёог "няцаах" ийм тооцоог бүтээх боломжгүй юм. тооцоолол ба зөвхөн тэдгээр; Түүгээр ч барахгүй эдгээр бүх нотлогдоогүй томьёог эх хувилбараар нь үгүйсгэх аргагүй юм. тооцоо, тиймээс эхэндээ. тооцоололд гэж нэрлэгддэг зүйл байдаг шийдвэрлэх боломжгүй (өөрөөр хэлбэл нотлох, үгүйсгэх боломжгүй) томъёонууд. Эдгээр үзэл бодлын хувьд бид зөвхөн ийм томъёогоор хязгаарлагдах боломжтой. Тооцооллын тайлбарууд нь утга учиртай (жишээ нь, үнэн эсвэл худал) саналуудыг илэрхийлдэг тул ийм томьёоны дотроос шийдвэрлэх боломжгүйг нь олдог. Үүнээс үзэхэд үнэн зөв дүгнэлтийг илэрхийлсэн томьёог танилцуулах боломжтой боловч тооцоололд нотлогдох боломжгүй; энэ утгаараа системийг бүрэн бус гэж хэлдэг. Хийж буй үндэслэлийн ерөнхий шинж чанараас шалтгаалан бүрэн бус шинж чанар нь хангалттай агуулагдсан аливаа зүйлд байдгийг бид онцлон тэмдэглэж байна. тооцоо. Тооцооллын шийдэгдэхгүй байдлын тухай ойлголт нь арифметикийн үзэл баримтлалд суурилдаг бөгөөд тооцооллын онолын чиглэлээр хийсэн судалгааны үндсэн дээр шийдвэр гаргах боломжгүй гэсэн баримт нотлогддог нь гайхах зүйл биш юм.Маш чухал (болон анхны харцаар харахад гэнэтийн) юм. ийм ерөнхий логик байгаа нь үнэн. Тооцооллын бүрэн бус байдал гэх мэт баримтыг (Логик дүгнэлт гаргах үйл явцыг бүрэн албажуулах үндсэн боломжгүйг илэрхийлсэн баримтыг Австрийн эрдэмтэн К.Годель 1931 онд "А." гэсэн ойлголтоос өмнө хатуу нотолсон баримт) тодруулж болно. Бидний сая үзсэнчлэн арифметикийн онолын тусламжтайгаар олж авч болно.Энэ нөхцөл байдал л гэхэд арифметикийн онолыг логикийн асуудалд хэрэглэх асар их боломжийг харуулж байна. Эдгээр програмууд нь өгөгдсөн жишээгээр хязгаарлагдахгүй. 1932 онд Зөвлөлтүүд. эрдэмтэн А.Н. Колмогоров агуулгын тусламжтайгаар зөн билэгчдийн бүтээсэн конструктив логикийн тайлбарыг санал болгов. зөн совингийн хандлагатай ямар ч холбоогүй гэсэн үг; тухайлбал, Колмогоров конструктив логикийн өгүүлбэр бүрийг асуудал гэж тайлбарлахыг санал болгов. Асуудлын тухай ойлголт нь зөвхөн А-ийн аль хэдийн боловсруулсан онолын үндсэн дээр өгөх боломжтой тодорхойлолтыг шаарддаг байв. Амер конструктив логикийг тайлбарлахад тохиромжтой хоёр тусгай ангиллын асуудлыг тус тус санал болгосон. 1945 онд эрдэмтэн С.К.Клин болон шар шувуу. эрдэмтэн Ю.Т.Медведев 1955 онд 1956 онд шар шувуу. эрдэмтэн Н.А.Шанин шинэ үзэл баримтлал дэвшүүлсэн бөгөөд үүний дагуу конструктив логикийн мэдэгдэл бүр асуудал хэлбэрээр тайлбар хийхийг шаарддаггүй. Энэхүү санааны тойрогт сонгодог "бүтээлчлэх" эсвэл "бүтээлч аналогийг олох" гэсэн асуултууд багтдаг. математикийн үзэл баримтлал, санал; Эдгээр асуудлыг шийдвэрлэх нь зөвхөн онолын үндсэн дээр боломжтой юм A. Үндсэн зүйлийг конструктивжуулах. математикийн ойлголтууд дүн шинжилгээ нь одоо боловсруулж байгаа гэж нэрлэгддэг хүргэсэн. конструктив математик шинжилгээ. Бүтээн байгуулалт болон бусад математикийн аргуудыг тодорхойлсон. онолууд. Голуудын нэг Барилгажуулахад ашигладаг техникүүд нь судалж буй объектоос үргэлж бүтээмжтэй объект байдаг нэр рүү шилжих явдал юм. ШИЙДЭХ АСУУДАЛ. Олон нийтийн асуудлын онцгой тохиолдол бол асуудлыг шийдвэрлэх арга зам юм. k.-l-ийг шийдвэрлэх асуудал. олонлогийн тухай гэдэг нь энэ олонлогийг шийдвэрлэх алгоритмыг бүтээх асуудал юм. Харгалзах Энд байгаа хэд хэдэн бие даасан асуудлууд нь цогц объектуудын багцаас объект тус бүрд тавигдсан багцын гишүүнчлэлийн асуултанд хариулах асуудлуудаас бүрдэнэ. Үүний эсрэгээр, ямар ч масс асуудал тус тус. Асуултанд хариулах хэд хэдэн бие даасан асуудлыг тодорхой багц, тухайлбал "тийм" гэсэн хариулт бүхий эдгээр бие даасан асуудлын багцыг шийдвэрлэх асуудал гэж үзэж болно. Энэ нь асуудлыг шийдвэрлэх чухал үүргийг тодорхой харуулж байна. Үзэл бодлоороо судалсан хүмүүс л дээ. тэдгээрийн шийдвэрлэх чадвар. Шийдвэрлэх асуудлуудын дотроос нотлох боломжтой тооцооллын томъёоны ангиудад тавигдсан асуудлууд онцгой байр суурь эзэлдэг. k.-l-ийн бүх нотлогдох томьёоны ангиллын асуудлыг шийдвэрлэх асуудал. тооцоо гэж нэрлэдэг мөн тооцоолол өөрөө шийдэх асуудал. (Орос бичвэрүүдэд шийдвэрлэх асуудлыг ихэвчлэн "шийдвэрлэх чадварын асуудал" гэж нэрлэдэг; гэхдээ "шийдвэрлэх чадварын асуудал" -ыг "өгөгдсөн асуудалд шийдэл байгаа эсэхэд хариулах" гэж илүү сайн нэрлэдэг). Шийдвэрлэх боломжгүй массын асуудал. к.-л-ийн зөвшөөрлийн асуудал. Тооцоололд тоолж болох олонлогийг шийдвэрлэх асуудал үргэлж байдаг. Ерөнхийдөө математикт үүссэн шийдвэрлэх бүх асуудал нь тоолж болох олонлогуудыг шийдвэрлэх асуудал болж хувирав. Энэ бол 1936 онд Черчээс хэвлэгдсэн, уусдаггүй шийдлийн асуудлын (мөн ерөнхийдөө уусдаггүй массын асуудлын анхны жишээ) дээр дурдсан анхны жишээ юм. Энэ нь гэж нэрлэгддэг зүйл юм. Ассоциатив системүүдийн таних тэмдгийн асуудал, хэлбэрийг шийдэх боломжгүй байдлын нотолгоог 1947 онд А.А. Марков, Амер нар бие биенээсээ хамааралгүйгээр нийтлэв. эрдэмтэн E. L. Пост; Энэ үр дүн нь логик, онолоос гадуур (1914 онд) үүссэн массын асуудлыг шийдвэрлэх боломжгүй гэдгийг нотлох анхны жишээ болохын хувьд сонирхол татаж байна.Энэ бол 1912 онд тавигдсан бүлэг хүмүүсийн ижил төстэй байдлын тухай алдартай асуудал бөгөөд шийдвэрлэх боломжгүй байсан юм. 1952 онд батлагдсан. эрдэмтэн П.С.Новиков (Лениний шагнал, 1957). Тодорхойлолтын асуудал тус бүр нь өгөгдсөн цагаан толгойн үсгийн хоёр үгийн дүйцэх эсвэл тэнцэхгүй байдлыг тогтоох алгоритмыг олохоос бүрддэг (бид ассоциатив систем эсвэл бүлэгтэй харьцаж байгаа эсэх нь ижил төстэй байдлын нэг буюу өөр тодорхойлолтоос хамаарна). Тиймээс таних асуудлыг бие биетэйгээ дүйцэх бүх хос үгсийн багцыг шийдвэрлэх асуудал гэж үзэж болно (бүх боломжит хос үгсийн багцтай харьцуулахад). Түүгээр ч зогсохгүй, бие биетэйгээ дүйцэхүйц бүх хос үгсийг олж авах үүсгүүрийн процессыг зааж өгөх боломжтой тул ийм бүх хосын багцыг тоолж болно. Тууштай байдал. 1936 онд Сүмийн жишээнээс эхлээд 1944 он хүртэл үргэлжилсэн массын асуудлууд шийдэгдэх боломжгүй гэдгийг нотлох бүх нотолгоо дараах байдлаар хийгдсэн эсвэл хэрэгжиж болно. жигд арга. Сүмийн судалсан илт шийдэгдээгүй асуудлыг хэлэлцэж буй массын асуудал болгон бууруулсан тул хэрэв хэлэлцэж буй массын асуудал шийдэгдэх боломжтой байсан бол Сүмийн асуудал ч мөн шийдэгдэх боломжтой болж хувирах болно (энэ утгаараа бид үүнийг нотлох баримт гэж хэлж болно. хэлэлцэж буй асуудлын шийдэгдэх боломжгүй байдал нь Сүмийн асуудлыг шийдвэрлэх боломжгүй гэсэн нотолгоо болж буурсан). Шийдвэрлэх боломжгүй аливаа асуудлын хувьд түүний шийдэгдэхгүй байдлыг ийм байдлаар тогтоож болох уу гэсэн асуулт гарч ирэв. Бууруулах чадварын асуудал гэж нэрлэгддэг энэ асуултыг 1944 онд Пост тавьсан; Үүний зэрэгцээ, Пост шийдэгдэх боломжгүй асуудлын хэд хэдэн жишээг өгсөн бөгөөд түүний шийдвэрлэх боломжгүй байдлыг дээр дурдсанаас өөр аргаар тогтоосон (эдгээр жишээнүүд бууралтын асуудлыг хараахан шийдэж чадаагүй байна, учир нь энэ асуудал нээлттэй хэвээр байна. Сүмийн асуудлыг шийдвэрлэх боломжгүй гэдгийг нотлохын тулд багассан ийм шийдэгдэх боломжгүй нотолгоог олох нь тэдэнд боломжгүй байсан; дараа нь дээрх зарим жишээнүүдийн хувьд ийм нотлох баримт олдсон). Арифметикийн онолын судалгааны төвд 1956 он хүртэл ЗХУ бие даан шийдвэрлэгдэх хүртэл бууруулж болох асуудал байв. эрдэмтэн А.А.Мучник, Амер нар. эрдэмтэн R. M. Фридберг. Тэрээр шийдэгдээгүй шийдлийн асуудлын жишээг (тоолж болохуйц багцын хувьд) бүтээсэн бөгөөд Сүмийн асуудлыг энэ асуудал болгон бууруулснаар шийдвэрлэх боломжгүй гэдгийг батлах боломжгүй юм. Зөвхөн Сүмийн асуудал төдийгүй өөр ямар ч асуудал "шийдэх боломжгүй жишиг асуудал" болж чадахгүй гэдгийг Мучник бүр ч илүү харуулсан, учир нь тоолж баршгүй олонлогийн хувьд шийдвэрлэх боломжгүй аливаа асуудлыг шийдвэрлэх боломжгүй гэдгийг нотлох баримт байж болно.

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

"Алгоритм" гэдэг үг нь 8-9-р зууны Төв Азийн агуу эрдэмтний нэрнээс гаралтай. Аль-Хорезми (Орчин үеийн Узбекистаны нутаг дэвсгэр дэх Хорезмын түүхэн бүс нутаг). Аль-Хорезмигийн математикийн бүтээлүүдээс алгебрийн (энэ номын гарчигнаас алгебр гэдэг үг үүссэн) болон арифметик гэсэн хоёр бүтээл л хүрчээ. Хоёр дахь ном нь удаан хугацаанд алдагдсан гэж тооцогддог байсан ч 1857 онд түүний латин хэл дээрх орчуулгыг Кембрижийн их сургуулийн номын сангаас олжээ. Энэ нь арифметик үйлдлийн дөрвөн дүрмийг дүрсэлсэн бөгөөд одоо хэрэглэж байгаа бараг ижил дүрэм юм. Энэ номын эхний мөрүүдийг дараах байдлаар орчуулсан: “Алгоритм хэлсэн. Удирдагч, хамгаалагч Бурханаа зохих ёсоор магтацгаая." Тиймээс Аль-Хорезми гэдэг нэр нь Алгоритм болсон бөгөөд алгоритм гэдэг үг эндээс гаралтай. Алгоритм гэдэг нэр томьёо нь дөрвөн арифметик үйлдлийг тодорхойлоход ашиглагдаж байсан бөгөөд яг ийм утгаар Европын зарим хэлэнд нэвтэрсэн. Жишээлбэл, эрх мэдэл бүхий англи хэлний толь бичигт Вебстерийн шинэ ертөнцийн толь бичиг, 1957 онд хэвлэгдсэн, алгоритм гэдэг үгийг "хоцрогдсон" гэж тэмдэглэсэн бөгөөд араб тоогоор арифметик үйлдлүүд хийдэг гэж тайлбарладаг.

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

Тюринг А. Машин сэтгэж чадах уу?? М., Мир, 1960
Успенский В. Постны машин.Шинжлэх ухаан, 1988
Кормен Т., Лейзерсон, Ривс Р. Алгоритмууд. Барилга, дүн шинжилгээ. М., МТСНМО, 1999 он

"ALGORITHM"-г олоорой

АЛГОРИТМЫН ОЙЛГОЛТ. АЛГОРИТМЫН ХИЧЭЭЛ. АЛГОРИТМЫН ТӨРЛҮҮД. АЛГОРИТМЫГ ТОДОРХОЙЛОХ АРГА

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

Үндсэн шинж чанарууд алгоритмууд нь:

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

Алгоритмыг тодорхой дүрмийн дагуу тодорхой харааны хэрэгслийг ашиглан албан ёсны болгох ёстой. Эдгээрт алгоритм бичих дараах аргууд орно: аман, томъёо-амаар, график, оператор схемийн хэл, алгоритмын хэл.

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

Блок диаграм Мэдээлэл боловсруулах үйл явцын үе шат бүрийг гүйцэтгэсэн үйлдлүүдийн шинж чанараас хамааран тодорхой тохиргоотой геометрийн тэмдэг (блок) хэлбэрээр дүрсэлсэн алгоритмын логик бүтцийн график дүрслэл юм. Тэмдгүүдийн жагсаалт, тэдгээрийн нэр, харуулах функц, хэлбэр, хэмжээсийг ГОСТ-оор тодорхойлно.

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

• шугаман;
• салбарлах;
• мөчлөгийн.

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

Салбарлах Мэдээллийг боловсруулах чиглэлийг сонгохдоо анхдагч эсвэл завсрын өгөгдлөөс (ямар нэгэн логик нөхцөлийн биелэлтийг шалгасны үр дүнд) хамаардаг тооцооллын процесс юм.

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

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

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

Элементар байдал (ойлголт).Алгоритмын алхам бүр нь энгийн байх ёстой бөгөөд ингэснээр үйлдлийг гүйцэтгэж буй төхөөрөмж үүнийг нэг алхамаар дуусгах боломжтой болно.

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

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

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

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

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

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

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

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

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

Гурав дахь төрөл- эдгээр нь дурын цагаан толгойн үсгээр үгсийн хувиргалт бөгөөд үндсэн үйлдлүүд нь орлуулалт юм. үгийн хэсгийг (үг гэдэг нь цагаан толгойн үсгийн дараалал) өөр үгээр солих. Энэ төрлийн загварын давуу тал нь түүний хамгийн их хийсвэрлэл, алгоритмын үзэл баримтлалыг дурын (заавал тоо биш) шинж чанартай объектуудад ашиглах чадвар юм. Гурав дахь төрлийн загваруудын жишээ бол Америкийн математикч Эмиль Л.Постын каноник систем, Зөвлөлтийн математикч А.А.Марковын нэвтрүүлсэн хэвийн алгоритмууд юм.

Хоёр ба гурав дахь төрлийн загварууд нь хоорондоо маш ойрхон бөгөөд эвристик өргөлтөөр ялгаатай байдаг тул Пост өөрөө энэ тухай яриагүй ч Post-ын машины тухай ярьдаг нь санамсаргүй хэрэг биш юм.

Зарим хэл дээрх алгоритмын бичлэг нь програм юм. Хэрэв програм нь тусгай алгоритмын хэлээр бичигдсэн бол (жишээ нь, PASCAL, BASIC эсвэл бусад) дараа нь бид ярьдаг. анхны програм. Компьютер шууд ойлгох хэлээр бичигдсэн программыг (ихэвчлэн хоёртын код) гэж нэрлэдэг машин,эсвэл хоёртын.

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

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

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

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

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

■ аман– алгоритмыг хүний ​​хэлээр дүрсэлсэн;

■ бэлгэдлийн шинж чанартай– алгоритмыг олон тооны тэмдэгт ашиглан дүрсэлсэн;

■ график– алгоритмыг график дүрсийн багц ашиглан тайлбарласан.

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

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

Алгоритм диаграммд дараах төрлийн график тэмдгүүдийг ашигладаг.

ЭхлэхТэгээд ТөгсгөлАлгоритмыг ижил тэмдэгтүүдийг ашиглан тодорхойлсон (Зураг 21.1).

Цагаан будаа. 21.1.

Тодорхой хувьсагчид шинэ утга өгөх, тодорхой утгыг өөр утгыг олж авахын тулд өөрчлөхтэй холбоотой алгоритмын алхамыг тэмдэгтээр илэрхийлнэ. "процесс"(Зураг 21.2).

Цагаан будаа. 21.2.

Зарим хувьсах нөхцлөөс хамааран алгоритмыг гүйцэтгэх чиглэлийн сонголтыг "" тэмдгээр илэрхийлнэ. шийдэл"(Зураг 21.3).

Цагаан будаа. 21.3.

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

Өгөгдлийн оролт, гаралтын үйлдлүүдийн командууд болон бусад график тэмдэгтүүд байдаг. Одоогийн байдлаар тэдгээрийг ГОСТ 19.701–90 (ISO 5807–85) стандартаар "Хөтөлбөрийн баримт бичгийн нэгдсэн систем. Алгоритм, өгөгдлийн программ ба системийн схемүүд. Конвенци ба гүйцэтгэлийн дүрэм" гэж тодорхойлсон. Нийтдээ ESPD цуглуулгад 28 баримт бичиг багтсан болно.

Алгоритм диаграммыг ашигласнаар алгоритмын хэлээр анхны программ зохиоход хялбар байдаг.

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

Алгоритмуудад шугаман бүтэцүйлдлүүд ар араасаа дараалан хийгддэг.

Алгоритмуудад салаалсан бүтэцАливаа нөхцөл биелэх, биелэхгүй байхаас хамааран янз бүрийн дарааллаар үйлдлүүд хийгддэг. Ийм үйлдлийн дараалал бүрийг дууддаг алгоритмын салбар.

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

Энэ тохиолдолд мөчлөгийн нэг давталт гэж нэрлэдэг давталт.