ХОЛБООНЫ БОЛОВСРОЛЫН АЖИЛЛАГААНЫ УЛСЫН БОЛОВСРОЛЫН ДЭЭД МЭРГЭЖЛИЙН БОЛОВСРОЛЫН БАЙГУУЛЛАГА "ВОРОНЕЖИЙН УЛСЫН ИХ СУРГУУЛЬ" Т.К. Кацаран, Л.Н. Строева ТУРИНГ МАШИН БА РЕКУРСВИЙН ҮЙЛ АЖИЛЛАГАА Их, дээд сургуулиудад зориулсан сурах бичиг Воронежийн Улсын Их Сургуулийн Хэвлэл, хэвлэлийн төв 2008 он. 2008 оны 5-р сарын 25-ны өдөр PMM-ийн факультетийн шинжлэх ухаан, арга зүйн зөвлөлийн хурлаар батлагдсан, 9-р протокол, Техникийн шинжлэх ухааны доктор, шүүмжлэгч. Үйл ажиллагааны судалгааны математикийн аргын тэнхим Т.М. Леденева Сурах бичгийг Воронежийн Улсын Их Сургуулийн Механик Математикийн факультетийн Шугаман бус хэлбэлзлийн тэнхимд бэлтгэсэн. ВСУИС-ийн Хэрэглээний математик-математикийн факультетийн 1-р курс, ВСУ-ийн Старооскольский, Лискинскийн салбаруудын оюутнуудад зөвлөж байна. 010500 – Хэрэглээний математик, компьютерийн шинжлэх ухааны мэргэжлээр ОРШИЛ “Алгоритм” гэдэг үг нь 8-9-р зуунд (783–850) амьдарч байсан Узбекийн математикч, одон орон судлаач Мухаммед бен Муса аль-гийн нэрний латин үсэг болох алгоритмаас гаралтай. Хорезми. Хорезмын хамгийн агуу математикч (орчин үеийн Узбекистаны хот) Дундад зууны Европт ийм нэрээр алдартай байв. Тэрээр "Энэтхэгийн тооллогын тухай" номондоо араб тоогоор натурал тоо бичих дүрэм, түүн дээр ажиллах дүрмийг томьёолжээ. Дараа нь алгоритм гэдэг ойлголт зөвхөн математикт бус өргөн утгаар хэрэглэгдэж эхэлсэн. Математикч, дадлагажигч хоёрын хувьд алгоритм гэдэг ойлголт чухал байдаг. Тиймээс алгоритм нь ижил төрлийн бүх асуудлыг шийдвэрлэхийн тулд тодорхой үйлдлийн системийг тодорхой дарааллаар гүйцэтгэх, эхний өгөгдлөөс шаардлагатай үр дүнг авах боломжийг олгодог үйлдлийн дарааллыг тодорхойлдог нарийн жор гэж бид хэлж чадна. Энэ нь "алгоритм" гэсэн ойлголтын тодорхойлолт биш, зөвхөн түүний тайлбар, зөн совингийн утга учир гэдгийг анхаарна уу. Алгоритмыг хүн эсвэл автомат төхөөрөмжөөр гүйцэтгэхээр төлөвлөж болно. Энэхүү алгоритмын санаа нь математикийн үүднээс хатуу биш юм, учир нь энэ нь ерөнхийдөө нарийн тодорхойлогдоогүй "яг заавар", "анхны өгөгдөл" гэх мэт ойлголтуудыг ашигладаг. Аливаа алгоритмын онцлог нь тодорхой ангиллын асуудлыг шийдвэрлэх чадвар юм. Жишээ нь, энэ нь шугаман тэгшитгэлийн системийг шийдвэрлэх, график дахь хамгийн дөт замыг олох гэх мэт алгоритм байж болно. Хамгийн энгийн алгоритм ч бий болгох нь бүтээлч үйл явц юм. Энэ нь зөвхөн амьд биетүүдэд байдаг бөгөөд удаан хугацааны туршид зөвхөн хүмүүст л байдаг гэж үздэг. Өөр нэг зүйл бол одоо байгаа алгоритмыг хэрэгжүүлэх явдал юм. Энэ нь асуудлын мөн чанарыг судлах үүрэггүй, магадгүй үүнийг ойлгох чадваргүй субьект эсвэл объектод даатгаж болно. Ийм субьект эсвэл объектыг ихэвчлэн албан ёсны гүйцэтгэгч гэж нэрлэдэг. Албан ёсны гүйцэтгэлийн жишээ бол нунтаг хийхээ мартсан ч гэсэн түүнд заасан үйлдлүүдийг чанд гүйцэтгэдэг автомат угаалгын машин юм. Хүн мөн албан ёсны үүрэг гүйцэтгэгчээр ажиллаж болно, гэхдээ юуны түрүүнд янз бүрийн автомат төхөөрөмжүүд, түүний дотор компьютер нь албан ёсны үүрэг гүйцэтгэдэг. Алгоритм бүрийг маш тодорхой гүйцэтгэгчийг харгалзан бүтээдэг. Гүйцэтгэгч хийж чадах эдгээр үйлдлийг түүний зөвшөөрөгдсөн үйлдэл гэж нэрлэдэг. Зөвшөөрөгдсөн үйлдлийн багц нь гүйцэтгэгч командын системийг бүрдүүлдэг. Алгоритм нь зөвхөн тухайн гүйцэтгэгчийн зөвшөөрөгдсөн үйлдлүүдийг агуулсан байх ёстой. Тиймээс алгоритмыг бусад заавраас ялгахын тулд алгоритмын хэд хэдэн ерөнхий шинж чанарыг ихэвчлэн томъёолдог. Алгоритм нь дараах шинж чанаруудтай байх ёстой. Салангид байдал (тасралт, салангид байдал) - алгоритм нь асуудлыг шийдвэрлэх үйл явцыг энгийн (эсвэл өмнө нь тодорхойлсон) алхамуудын дараалсан гүйцэтгэл хэлбэрээр илэрхийлэх ёстой. Алгоритмоор өгөгдсөн үйлдэл бүрийг өмнөхийг нь гүйцэтгэсний дараа л гүйцэтгэнэ. Тодорхой байдал - алгоритмын дүрэм бүр тодорхой, хоёрдмол утгагүй байх ёстой бөгөөд дур зоргоороо байх зай үлдээхгүй. Энэ өмчийн ачаар алгоритмын гүйцэтгэл нь механик шинж чанартай бөгөөд шийдэгдэж буй асуудлын талаар нэмэлт заавар, мэдээлэл шаарддаггүй. Үр ашиг (хязгаарлагдмал байдал) - алгоритм нь асуудлыг хязгаарлагдмал тооны алхмаар шийдвэрлэхэд хүргэх ёстой. 4 Масс масштаб - асуудлыг шийдэх алгоритмыг ерөнхий хэлбэрээр боловсруулсан, өөрөөр хэлбэл зөвхөн анхны өгөгдлөөр ялгаатай тодорхой ангиллын асуудалд хамаарах ёстой. Энэ тохиолдолд эхний өгөгдлийг алгоритмын хэрэглээний талбар гэж нэрлэдэг тодорхой хэсгээс сонгож болно. Алгоритмын онол нь алгоритмын ерөнхий шинж чанарыг судалдаг математикийн салбар юм. Алгоритмуудын чанарын болон хэмжлийн онолууд байдаг. Алгоритмуудын чанарын онолын гол асуудал бол тодорхой шинж чанартай алгоритм бүтээх асуудал юм. Энэ асуудлыг алгоритмын бодлого гэж нэрлэдэг. Алгоритмын хэмжүүрийн онол нь алгоритмыг нарийн төвөгтэй байдлын үүднээс авч үздэг. Алгоритмын онолын энэ салбарыг алгоритмын нарийн төвөгтэй байдлын онол гэж бас нэрлэдэг. Зарим асуудлын шийдлийг хайж байхдаа тохирох алгоритмыг олоход удаан хугацаа шаардагддаг. Ийм асуудлын жишээ нь: а) аливаа предикатын томьёоны хувьд хязгаарлагдмал тооны үйлдлээр энэ нь ижил үнэн эсэхийг олж мэдэх аргыг зааж өгөх; б) Диофантины тэгшитгэл (бүхэл тоон коэффициент бүхий алгебрийн тэгшитгэл) бүхэл тоогоор шийдэгдэх боломжтой юу? Эдгээр асуудлыг шийдэх алгоритмуудыг олох боломжгүй байсан тул ийм алгоритмууд огт байдаггүй гэсэн таамаглал гарч ирсэн бөгөөд энэ нь батлагдсан: эхний асуудлыг А.Черч, хоёр дахь асуудлыг Ю.В. Матиясевич ба Г.В. Чудновский. Алгоритм хэмээх зөн совингийн ойлголтыг ашиглан үүнийг батлах нь зарчмын хувьд боломжгүй юм. Тиймээс алгоритм гэдэг ойлголтын математикийн нарийн тодорхойлолтыг өгөхийг оролдсон. 20-р зууны 30-аад оны дундуур С.К. Клин, А.А. Марков, Э.Пост, А.Тюринг, А.Черч болон бусад хүмүүс алгоритмын тухай ойлголтын 5-р математикийн янз бүрийн тодорхойлолтуудыг санал болгосон. Дараа нь эдгээр өөр өөр албан ёсны математик тодорхойлолтууд нь ямар нэг утгаараа ижил утгатай болох нь батлагдсан: тэдгээр нь ижил функцүүдийн багцыг тооцдог. Энэ нь алгоритмын зөн совингийн үндсэн шинж чанаруудыг эдгээр тодорхойлолтуудад зөв тусгасан болохыг харуулж байна. Дараа нь бид Тьюрингийн машин гэж нэрлэгддэг А.Тюрингийн санал болгосон алгоритмын математикийн сайжруулалтыг авч үзье. 6 1. ТЮРИНГ МАШИН § 1. Тьюрингийн машины математик загвар Английн математикч А.Тюринг 20-р зууны гучаад онд дэвшүүлсэн Тьюрингийн машиныг бүтээх санаа нь түүний алгоритм гэдэг ойлголтын математикийн нарийн тодорхойлолт. Тюринг машин (MT) нь хамгийн тохиромжтой дижитал компьютерийн математик загвар юм. Тьюрингийн машин нь функц, дериватив, интеграл, бүлэг гэх мэт математикийн ижил объект юм. Бусад математикийн ойлголтуудын нэгэн адил Тьюрингийн машин гэсэн ойлголт нь объектив бодит байдлыг тусгаж, тодорхой бодит үйл явцыг загварчилдаг. MT алгоритмыг тайлбарлахын тулд соронзон хальс, унших толгой, хяналтын төхөөрөмж, дотоод санах ой гэсэн дөрвөн хэсгээс бүрдэх төхөөрөмжийг төсөөлөхөд тохиромжтой. 1. Соронзон хальс нь эсүүдэд хуваагдсан (тэнцүү эсүүд) боломжит хязгааргүй гэж үздэг. Шаардлагатай бол тэмдэгт байрлах эхний эсвэл сүүлчийн нүдэнд хоосон нүдийг хавсаргана. Машин нь цаг хугацаанд ажилладаг бөгөөд энэ нь салангид гэж тооцогддог бөгөөд түүний моментууд нь 1, 2, 3, ... гэсэн тоогоор дугаарлагдсан байдаг. Ямар ч үед соронзон хальс нь хязгаарлагдмал тооны эсийг агуулдаг. А = (L, a1 , a 2 ,..., a n -1 ), n ³ 2 гадаад цагаан толгойноос зөвхөн нэг тэмдэг (үсэг)-ийг нүднүүдэд салангид хугацаанд бичиж болно. Хоосон нүдийг L тэмдгээр тэмдэглэж, L тэмдгийг өөрөө хоосон гэж нэрлэдэг бол үлдсэн тэмдгийг хоосон биш гэж нэрлэдэг. Энэхүү цагаан толгойн А үсгээр МТ-д өгөгдсөн мэдээллийг үг хэлбэрээр кодлодог (хязгаарлагдмал эрэмблэгдсэн тэмдэгтүүд). Машин нь үг хэлбэрээр өгсөн мэдээллийг шинэ үг болгон "боловсруулдаг". 2. Унших толгой (тодорхой унших элемент) нь соронзон хальсны дагуу хөдөлж, цаг мөч бүрт соронзон хальсны яг нэг нүдийг хардаг. Толгой нь нүдний агуулгыг уншиж, түүнд А цагаан толгойн үсгийн шинэ тэмдэгтийг бичих боломжтой бөгөөд үйл ажиллагааны нэг мөчлөгт зөвхөн нэг нүдийг баруун тийш (R), зүүн тийш (L) шилжүүлэх эсвэл байрандаа (N) үлдэх боломжтой. ). Толгойн хөдөлгөөний багцыг (шилжилтийг) тэмдэглэе D = (P, L, N). Хэрэв t мөчид толгой нь хамгийн гадна талын нүдэнд байгаа бөгөөд алга болсон нүд рүү шилжсэн бол шинэ хоосон нүд нэмэгдэх бөгөөд түүний дээр толгой нь t + 1 байх болно. 3. Машины дотоод санах ой нь Q = ( q0 , q1 , q 2 , ..., q m ), m ³ 1 дотоод төлөвүүдийн тодорхой хязгаарлагдмал багц юм. Бид хүчийг |Q | гэж таамаглах болно ³ 2. Машины хоёр төлөв нь онцгой утгатай: q1 нь анхны дотоод төлөв (хэд хэдэн анхны дотоод төлөв байж болно), q0 нь эцсийн төлөв эсвэл зогсолтын төлөв (үргэлж нэг эцсийн төлөв байдаг). Цаг мөч бүрт МТ нь толгойн байрлал, дотоод төлөвөөр тодорхойлогддог. Жишээлбэл, толгойн дээр байрлах нүдний доор машины дотоод төлөвийг зааж өгсөн болно. ¯ a2 a1 L a2 a3 q1 4. t мөч бүрт хяналтын төхөөрөмж нь тухайн агшинд уншиж буй соронзон хальс дээрх тэмдэг болон машины дотоод төлөв байдлаас хамааран дараах үйлдлүүдийг гүйцэтгэдэг: 1) ai унших тэмдгийг өөрчилнө. мөчид t шинэ тэмдэгт a j (ялангуяа үүнийг өөрчлөхгүй, өөрөөр хэлбэл ai = a j); 2) толгойг дараах чиглэлүүдийн аль нэгэнд шилжүүлнэ: N, L, R; 3) t мөчид байгаа 8 qi машины дотоод төлөвийг t +1 үед машин байх шинэ q j болгон өөрчилнө (энэ нь qi = q j байж болно). Хяналтын төхөөрөмжийн ийм үйлдлийг тушаал гэж нэрлэдэг бөгөөд үүнийг дараах хэлбэрээр бичиж болно: qi ai ® a j D q j , (1) энд qi нь тухайн үеийн машины дотоод төлөв; a i – энэ үед уншиж буй тэмдэг; a j – a i тэмдэг өөрчлөгдөх тэмдэг (ai = a j байж болно); D тэмдэг нь N, эсвэл L, эсвэл P бөгөөд толгойн хөдөлгөөний чиглэлийг заана; q j нь тухайн үеийн машины дотоод төлөв (магадгүй qi = q j). qi ai ба a j D q j илэрхийллүүдийг тус командын зүүн ба баруун тал гэж нэрлэдэг. Q \ (q 0 ) ба A олонлогууд нь төгсгөлтэй байдаг тул зүүн тал нь хосоороо ялгагдах командын тоо нь төгсгөлтэй тоо юм. Яг ижил зүүн талтай командууд байхгүй, өөрөөр хэлбэл хэрэв T машины программ нь qi ai ® a j D q j ба qt at ® ak D qk илэрхийллийг агуулж байвал qi ¹ qt эсвэл ai ¹ at ба D O (P, L, N) гэсэн утгатай. ). Бүх зааврын багцыг Тюринг машины програм гэж нэрлэдэг. Програмын командын хамгийн их тоо нь (n + 1) x m, энд n + 1 = A ба m + 1 = Q байна. q0 командын эцсийн төлөв зөвхөн командын баруун талд, q1 анхны төлөв нь командын зүүн болон баруун талд гарч болно гэж үздэг. Нэг командыг гүйцэтгэхийг алхам гэж нэрлэдэг. Тьюрингийн машины тооцоолол (эсвэл ажиллагаа) нь эхнийхээс нь эхлээд алгасахгүйгээр ар араас нь хийх алхмуудын дараалал юм. Тиймээс, MT нь дөрвөн төгсгөлтэй багц мэдэгдэж байгаа бол өгөгдөнө: гадаад цагаан толгой, дотоод Q цагаан толгой, толгойн хөдөлгөөний D багц ба командын төгсгөлтэй багц болох машины програм. 9 § 2. Тьюрингийн машины ажиллагаа Машины ажиллагааг эхний (эхний) агшинд хийх даалгавраар бүрэн тодорхойлно: 1) соронзон хальс дээрх үгс, өөрөөр хэлбэл соронзон хальсны нүдэнд бичигдсэн тэмдэгтүүдийн дараалал (a зүүнээс баруун тийш соронзон хальсны нүдэн дээрх эдгээр тэмдгийг уншсанаар үгийг олж авдаг); 2) толгойн байрлал; 3) машины дотоод байдал. Эдгээр гурван нөхцлийн хослолыг (одоогоор) тохиргоо (одоогоор) гэж нэрлэдэг. Ихэвчлэн эхний мөчид машины дотоод төлөв нь q1 бөгөөд толгой нь соронзон хальсны эхний зүүн эсвэл эхний баруун нүдний дээд талд байрладаг. Анхны төлөв q1, толгойн байрлал нь эхний үгнээс дээгүүр байгаа туузан дээрх өгөгдсөн үгийг анхны тохиргоо гэнэ. Үгүй бол Тьюрингийн машин нь анхны тохиргооны үгэнд хамаарахгүй гэж бид хэлж байна. Өөрөөр хэлбэл, эхний үед тохиргоог дараах хэлбэрээр илэрхийлж болно: тодорхой тооны нүднүүдээс бүрдсэн соронзон хальс дээр, нүд бүрт гадаад цагаан толгойн нэг тэмдэгтийг бичсэн, толгой нь эхнийх нь дээр байрладаг. соронзон хальсны зүүн эсвэл эхний баруун нүд ба машины дотоод байрлал нь q1. Энэ тушаалыг хэрэгжүүлсний үр дүнд соронзон хальс болон толгойн байрлал дээр гарсан үгийг эцсийн тохиргоо гэж нэрлэдэг. Жишээлбэл, хэрэв эхний мөчид соронзон хальс дээр a1La 2 a1a1 гэсэн үг бичигдсэн бол анхны тохиргоо нь дараах байдлаар харагдах болно: a1 a2 L a1 a1 q1 (дээр нь толгой байрладаг нүдний доор, машины дотоод байдал). заасан байна). 10

Сургуулийн компьютерийн шинжлэх ухааны хичээлийн "Тюринг машин" сэдэв

И.Н. Фалина,
Москва

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

"Тюрингийн машин" сэдвийг 8-11-р ангид "Мэдээллийн үйл явц" сэдвийн хүрээнд судалж болно. Мэдээллийн боловсруулалт”, сонгон суралцах ангиудад, нэмэлт боловсролын системд, жишээлбэл, залуу програмистуудын сургуулиудад. Хэрэв багш "Тюринг машин" програм хангамжийн симулятор байгаа бол энэ сэдвийг судлахдаа компьютерийн дэмжлэгийг дагалдаж болно. Програмчлалын ахисан түвшний ангиудад оюутнууд Тьюрингийн машины програмыг бие даан бичих боломжтой. Энэ нийтлэлийн нэг хэсэг болгон бид танд "Тюринг машин" сэдвээр асуудлыг шийдвэрлэх семинарыг санал болгож байна. Энэ сэдвээр онолын материал Информатик сонины хуудсанд нэг бус удаа нийтлэгдсэн, жишээлбэл, 3/2004 дугаарт, I.N. Фалина "Алгоритмын онолын элементүүд".

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

Тюринг машин бүр хоёр хэсэгтэй:

1)хязгааргүйхоёр талын аялал тууз, эсүүдэд хуваагдсан;

2) машин(унших/бичих толгойг програм хангамжаар удирддаг).

Тюринг машин бүртэй холбоотой эцсийн хоёр цагаан толгой: оролтын тэмдэгтүүдийн цагаан толгой A = (a 0 , a 1 , ..., a m ) ба төлөвийн цагаан толгой Q = (q 0 , q 1 , ..., q p ). (Өөр өөр Тьюрингийн машинууд өөр өөр цагаан толгойн үсэгтэй холбоотой байж болно АТэгээд Q.) q 0 төлөвийг дуудна идэвхгүй. Хэрэв машин ийм байдалд орвол ажлаа дуусгасан гэж үздэг. q 1 төлөвийг дуудна анхны. Энэ төлөвт байх үед машин ажиллаж эхэлдэг.

Оруулсан үгийг соронзон хальсны дараалсан нүднүүдэд нэг үсгээр байрлуулна. Оролтын үгийн зүүн ба баруун талд зөвхөн хоосон нүднүүд байна (цагаан толгойн үсгээр Адандаа хоосон үсэг орно А 0 нь нүд хоосон байгааг илтгэнэ).

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

Машин нь зөвхөн нэг нүдийг "хардаг". Аль үсэгнээс хамаарна aiтэр хардаг, мөн түүнчлэн түүний нөхцөл байдлаас хамаарна qjМашин нь дараахь үйлдлүүдийг гүйцэтгэх боломжтой.

• · ажиглагдсан нүдэнд шинэ үсэг бичих;
• · соронзон хальсны нэг нүдийг баруун/зүүн тийш шилжүүлэх эсвэл хөдөлгөөнгүй байх;
• · шинэ төлөвт шилжих.

Өөрөөр хэлбэл Тьюрингийн машин гурван төрлийн үйлдэлтэй. Дараагийн хосуудын хувьд ( q j, a i) Тюринг машин нь тодорхой параметр бүхий гурван үйлдлээс бүрдсэн командыг гүйцэтгэдэг.

Тьюрингийн машины программ нь нүд бүрт команд бичсэн хүснэгт юм.

Нүд ( q j, a i) нь цагаан толгойн тэмдэг ба машины төлөв гэсэн хоёр параметрээр тодорхойлогддог. Команд нь заалт юм: унших/бичих толгойг хаашаа шилжүүлэх, одоогийн нүд рүү ямар тэмдэгт бичих, машин ямар төлөвт шилжих ёстой. Машины хөдөлгөөний чиглэлийг заахдаа "L" (зүүн), "P" (баруун) эсвэл "N" (хөдөлгөөнгүй) гэсэн гурван үсгийн аль нэгийг ашиглана.

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

Соронзон хальс нь оролтын үг агуулж байвал машин нь муж улсын зарим нүдний эсрэг байрладаг гэдгийг хүлээн зөвшөөрцгөөе q 1. Ашиглалтын явцад автомат машин төлөвт орох ёстой гэж бичсэн нүдэнд хүрэх хүртэл программ (хүснэгт)-ийн нэг нүднээс нөгөө нүд рүү үсрэнэ. q 0 . Эдгээр эсүүд гэж нэрлэгддэг эсийг зогсоох. Ямар ч ийм үүрэнд хүрсэн бол Тьюрингийн машин зогсдог.

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

Жишээ. Та соронзон хальс дээрх тоон дээр нэгийг нэмдэг Тюринг машин бүтээх хэрэгтэй. Оролтын үг нь соронзон хальсны дараалсан нүдэнд бичигдсэн аравтын бүхэл тооноос бүрдэнэ. Эхний үед машин нь тухайн тооны баруун талын цифрийн эсрэг байрладаг.

Шийдэл. Машин нь тухайн тооны сүүлийн орон дээр нэгийг нэмэх ёстой. Хэрэв сүүлийн цифр нь 9 бол түүнийг 0-ээр сольж, өмнөх цифр дээр нэгийг нэмнэ. Өгөгдсөн Тюринг машинд зориулсан програм дараах байдалтай байж болно.

Энэ Тюринг машинд q 1 - оронтой өөрчлөлтийн төлөв, q 0 - зогсолтын төлөв. Хэрэв чи чадвал q lмашин 0..8 тоог хараад дараа нь түүнийг 1..9-оор сольж, төлөвт орно. q 0, өөрөөр хэлбэл. машин зогсдог. Хэрэв тэр 9-ийн тоог харвал түүнийг 0-ээр сольж, зүүн тийш шилжиж, мужид үлдэнэ. q l. Энэ нь машин 9-өөс бага тоотой тулгарах хүртэл үргэлжилнэ. Хэрэв бүх тоо нь 9-тэй тэнцүү байсан бол тэдгээрийг тэгээр орлуулж, хамгийн өндөр цифрийн оронд 0 гэж бичээд зүүн тийш шилжиж, хоосон нүдэнд 1 гэж бичнэ. Дараа нь мужид орно q 0, өөрөөр хэлбэл. зогсох болно.

Практик даалгавар

1. Тюринг машины соронзон хальс нь “+” тэмдэгтүүдийн дарааллыг агуулдаг. Хоёр дахь "+" тэмдгийг "-" тэмдгээр сольдог Тьюрингийн машинд зориулсан програм бич. Орлуулах нь дарааллын баруун төгсгөлөөс эхэлнэ. Машин боломжтой q 1 заасан дарааллын тэмдэгтүүдийн аль нэгийг харна. Хүснэгтийн програмаас гадна муж бүрт машин юу хийж байгааг үгээр тайлбарлана уу.

2. Тоо өгсөн nнаймтын тооллын системд. Өгөгдсөн тоог нэмэгдүүлэх Тьюрингийн машин зохион бүтээ nдээр 1. Машин нь боломжтой q 1 нь оролтын үгийн тодорхой цифрийг хардаг. Хүснэгтийн програмаас гадна муж бүрт машин юу хийж байгааг үгээр тайлбарлана уу.

3. Натурал тооны аравтын тэмдэглэгээ өгөгдсөн n> 1. Өгөгдсөн тоог багасгах Тьюрингийн машин бүтээ nдээр 1. Машин нь боломжтой q 1 нь тухайн тооны баруун цифрийг харна. Хүснэгтийн програмаас гадна муж бүрт машин юу хийж байгааг үгээр тайлбарлана уу.

4. Натурал тоо өгөгдсөн n> 1. Өгөгдсөн тоог багасгах Тьюрингийн машин бүтээ n 1-ээр, харин гаралтын үгийн хамгийн чухал цифр нь 0 байж болохгүй. Жишээлбэл, хэрэв оролтын үг нь "100" байсан бол гаралтын үг нь "099" биш, харин "99" байх ёстой. Машин боломжтой q 1 нь тухайн тооны баруун цифрийг харна. Хүснэгтийн програмаас гадна муж бүрт машин юу хийж байгааг үгээр тайлбарлана уу.

5. Нээх, хаах хаалтны массив өгөгдсөн. Хос хос хаалтуудыг арилгах Тьюрингийн машин бүтээ, i.e. "()" эгнээнд байрладаг.

Жишээлбэл, ") (() (()" гэж өгвөл та ") . . . ((") авах хэрэгтэй.

Машин боломжтой q

6. Үсгийн цуваа өгөгдсөн " а"Ба" б" Бүх үсгүүдийг хөдөлгөх Тьюрингийн машин бүтээ. а” зүүн талд, үсэгнүүд “ б” - шугамын баруун талд. Машин боломжтой q 1 мөрийн хамгийн зүүн талын тэмдэгтийг харна. Хүснэгтийн програмаас гадна муж бүрт машин юу хийж байгааг үгээр тайлбарлана уу.

7. Тьюрингийн машины соронзон хальс дээр аравтын тооллын системд бичигдсэн тоо байна. Энэ тоог 2-оор үржүүлээрэй. Машин боломжтой q 1 нь тухайн тооны зүүн талын цифрийг харна. Хүснэгтийн програмаас гадна муж бүрт машин юу хийж байгааг үгээр тайлбарлана уу.

8. Хоёр натурал тоо өгөгдсөн мТэгээд n, нэгдмэл тооллын системд үзүүлэв. Тохирох тэмдэгтүүд нь “|” хоосон нүдээр тусгаарлагдсан. Машин боломжтой q 1 оролтын дарааллын хамгийн баруун талын тэмдэгтийг харна. Тооны нийлбэрийг соронзон хальс дээр үлдээх Тьюрингийн машиныг бүтээ мТэгээд n. Хүснэгтийн програмаас гадна муж бүрт машин юу хийж байгааг үгээр тайлбарлана уу.

9. Хоёр натурал тоо өгөгдсөн мТэгээд n, нэгдмэл тооллын системд үзүүлэв. Тохирох тэмдэгтүүд нь “|” хоосон нүдээр тусгаарлагдсан. Машин боломжтой q 1 оролтын дарааллын хамгийн баруун талын тэмдэгтийг харна. Туузан дээрх тоонуудын ялгааг үлдээх Тьюрингийн машиныг бүтээ. мТэгээд n. Энэ нь мэдэгдэж байна м> n. Хүснэгтийн програмаас гадна муж бүрт машин юу хийж байгааг үгээр тайлбарлана уу.

10. Тьюрингийн машины соронзон хальс дээр аравтын бутархай тоо байдаг. Энэ тоо 5-д үлдэгдэлгүй хуваагдах эсэхийг тодорхойл. Хэрэв энэ нь хуваагдаж байвал тооны баруун талд "тийм" гэж бичнэ, үгүй ​​бол "үгүй" гэж бичнэ. Машин нь оролтын дугаарын тодорхой цифрийг шалгадаг. Хүснэгтийн програмаас гадна муж бүрт машин юу хийж байгааг үгээр тайлбарлана уу.

Боломжтой q 1 машин дугаарын баруун төгсгөлийг хайж олох боломжтой q 2 - "+" тэмдгийг алгасаж, дарааллын төгсгөлд хүрэхэд - зогсоно. Боломжтой q 3-т машин нь "+" тэмдгийг "-" тэмдгээр сольж, дарааллын төгсгөлд хүрэхэд зогсдог.

Энэ асуудлын шийдэл нь дээр дурдсан жишээтэй төстэй юм.

муж q 1 - бид хамгийн бага (дараагийн) цифрийг 1-ээр бууруулна. Хэрэв энэ нь тэгтэй тэнцүү биш бол хамгийн бага цифр нь 0 бол буурсны дараа нэн даруй зогсоож, оронд нь 9-ийг бичиж, зүүн тийш шилжүүлж, хасах үйлдлийг дахин хийнэ . Торон дотор [ а 0 , q 1 ] Тюринг машин хэзээ ч цохихгүй тул түүнийг дүүргэлгүй орхиж болно.

Даалгавар 4 (даалгавар 3-ын хүндрэл)

муж q 1 - бид бага (дараагийн) цифрийг 1-ээр бууруулна. Хэрэв энэ нь 1-ээс их бол бууруулсны дараа бид шууд зогсдог, харин бага орон нь 0 бол оронд нь 9 гэж бичээд зүүн тийш шилжүүлж, хасах үйлдлийг хийнэ. дахин. Хэрэв бууруулж буй орон нь 1 бол оронд нь 0 гэж бичээд төлөв рүү очно q 2 .

муж q 2 - аль ч байрлалд "0" гэж бичсэний дараа энэ тэг нь хамгийн чухал цифр мөн эсэхийг (өөрөөр хэлбэл гаралтын үгийн бичлэгийн зүүн талд байгаа эсэх) дүн шинжилгээ хийх шаардлагатай. а 0).

муж q 3 - хэрэв бүртгэгдсэн "0" нь хамгийн чухал цифр бол түүнийг гаралтын үгийн бичлэгээс хасах шаардлагатай.

Тьюрингийн машин хэзээ ч ордоггүй эсүүд хоосон үлддэг.

муж q 1: хэрэв “(” таарвал баруун тийш шилжүүлээд муж руу очно уу q 2 ; уулзсан бол" а 0", дараа нь зогсоо.

муж q 2: хосолсон "(" тэмдэгтийн шинжилгээ, хосолсон тохиолдолд ")" харагдана. Хэрэв энэ нь уурын өрөө бол зүүн тийшээ буцаж, муж руу яв q 3 .

муж q 3: эхлээд “(”, дараа нь “)” гэснийг арилгаад, руу очно уу q 1 .

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

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

ааа ->

a -> гаралтын үг нь оролтын үгтэй таарч, бид оролтын үгийг дуустал нь харна.

bbb -> гаралтын үг нь оролтын үгтэй таарч, бид оролтын үгийг дуустал нь харна.

b -> гаралтын үг нь оролтын үгтэй таарч, бид оролтын үгийг дуустал нь харна.

ab -> гаралтын үг нь оролтын үгтэй тохирч байвал бид оролтын үгийг дуустал нь харна.

Хэлэлцүүлгийн үр дүн. Тьюрингийн машин ямар үсгийн хэлхээг дагаж байгааг "ойлгох" ёстой, өөрөөр хэлбэл. дор хаяж хоёр мужтай байх ёстой. Төрд өгөөч q 1 - үсгийн хэлхээний дагуу хөдөлгөөн " а", А q 2 - үсгийн хэлхээний дагуух хөдөлгөөний байдал " б" Гинж нь нэг үсгээс бүрдэж болно гэдгийг анхаарна уу. Хэрэв бид муж улсын шугамын төгсгөлд хүрсэн бол q 1 эсвэл q 2, i.e. уулзсан а 0 , машин зогсох ёстой, бид бүх шугамыг боловсруулсан.

Оролтын үгсийн дараах сонголтуудыг анхаарч үзээрэй.

bba -> abb

bbbaab -> ааббб

aabbaab -> ааааббб

Хэлэлцүүлгийн үр дүн. Оруулсан үгийн эхний хувилбарыг дараах байдлаар дараалан боловсруулж болно. бба -> bbb-> үсгийн гинжин хэлхээний зүүн төгсгөл рүү буцах " б” -> abb(энэ хэлхээний эхний үсгийг " гэж солино. а"). Эдгээр үйлдлийг гүйцэтгэхийн тулд бид хоёр шинэ мужийг нэвтрүүлж, үүнээс гадна төрийг тодруулах шаардлагатай болно q 2. Тиймээс, энэ асуудлыг шийдэхийн тулд бид дараах төлөвтэй Тьюрингийн машин бүтээх хэрэгтэй.

q 1 - үсгийн гинжин хэлхээний дагуу баруун тийш яв " а" Хэрэв гинж дуусвал а 0, дараа нь очно уу q 0 ; " гэсэн үсгээр төгссөн бол б", дараа нь бид очно q 2 ;

q 2 - үсгийн хэлхээний дагуу баруун тийш яв " б” хэрэв гинж дуусвал а 0, дараа нь очно уу q 0 ; дуусвал" а", дараа нь " үсгийг солино. а"дээр" б", муж руу яв q 3 (зүйлийн гинжийг тухайн зүйлийн гинжээр сольсон);

q 3 - үсгийн хэлхээний дагуу зүүн тийш яв " б” зүүн төгсгөлд. Хэрэв уулзсан бол а 0 эсвэл " а", дараа нь бид очно q 4 ;

q 4 - солих " б"дээр" а” гэж бичээд оч q 1 (хэлбэрийн гинжийг маягтын гинжээр солино.

Асуудал 7

муж q 1 - тооны баруун (хамгийн бага) цифрийг хайх;

муж q 2 - 1 зөөвөрлөхгүйгээр тооны дараагийн цифрийг 2-оор үржүүлэх;

муж q 3 - 1 зөөвөрлөх тоог нэмснээр тооны дараагийн цифрийг 2-оор үржүүлэх.

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

Гэсэн хэдий ч хачирхалтай нь энэ асуудлыг шийдэх нь ихээхэн бэрхшээл учруулдаг. Ихэнх тохиолдолд оюутнууд мөчлөгийн үйлдлүүдийг гүйцэтгэдэг Тьюрингийн машиныг бүтээдэг: баруун тийш дараалан түлхэх. nзүүн тийш цус харвалт.

Энэ тохиолдолд тэдний програм дараах байдалтай байна.

муж q 1 - тусгаарлагч хайх;

муж q 2 - цус харвалтыг шилжүүлсэн;

муж q 3 - төгсгөлийг шалгана уу (бүх цохилтыг шилжүүлсэн эсэх).

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

Сургуулийн хүүхдүүдэд энэ даалгавар нэлээд хялбар мэт санагдаж байгаа ч Тюринг машиныг зогсооход бэрхшээлтэй тулгардаг. Энэ даалгаварт зориулсан Тюринг машины боломжит хувилбаруудыг доор харуулав.

Шийдлийн санаа (зогсоох нөхцөл). Соронзон хальс дээр хоёр анхны харвалтын массив байна.

Бид массивын зүүн төгсгөлөөс зураасыг арилгаж эхэлдэг м. Мөн бид массив дахь хамгийн зүүн талын зураасыг нэг нэгээр нь арилгадаг ммөн массив дахь хамгийн баруун талын харвалт n. Гэхдээ массив дахь зөв цохилтыг арилгахын өмнө n, бид энэ нь цорын ганц (жишээ нь устгах шаардлагатай сүүлчийнх) эсэхийг шалгадаг.

Эхлээд бидний асуудлыг шийдвэрлэхэд шаардлагатай Тьюрингийн машины төлөвүүдийг тайлбарлаж, дараа нь хүснэгтийн программыг байгуулъя.

муж q 1 - баруунаас зүүн тийш шилжих үед цус харвалтын массивуудын хоорондох тусгаарлагчийг хайх;

муж q 2 - массив дахь зүүн талын цохилтыг хайх м;

муж q 3 - массив дахь зүүн цус харвалтыг арилгах м;

муж q 4 - зүүнээс баруун тийш шилжих үед тусгаарлагчийг хайх;

муж q 5 - массиваас зөв харвалт хайх n;

муж q 6 - массив дахь энэ харвалтын өвөрмөц байдлыг шалгах n, өөрөөр хэлбэл энэ нь сүүлчийнх байсан эсэхийг тодорхойлох;

муж q 7 - хэрэв энэ нь сүүлчийнх байсан бол зогсоо, үгүй ​​бол алгоритмын гүйцэтгэлийн шинэ мөчлөгт шилжинэ.

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

A = ( а 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, D, A, N, E, T).

муж q 1 - тооны баруун төгсгөлийг хайх;

муж q 2 - тооны хамгийн бага чухал оронтой тоонд дүн шинжилгээ хийх; хэрэв энэ нь "0" эсвэл "5" -тай тэнцүү бол i.e. тоо нь 5-д хуваагдана, дараа нь төлөв рүү шилжинэ q 3 , өөрөөр хэлбэл төлөв рүү шилжих q 5 ;

муж q 3 - соронзон хальс дээрх үгийн баруун талд "D" үсгийг бичнэ үү;

муж q 4 - үгийн баруун талд "А" үсгийг бичиж, машиныг зогсоох;

муж q 5 - үгийн баруун талд "N" үсгийг бичих;

муж q 6 - үгийн баруун талд "E" үсгийг бичих;

муж q 7 - үгийн баруун талд "T" үсгийг бичиж, машиныг зогсооно.

Алгоритм болох Тьюрингийн машины шинж чанарууд

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

Салангид байдал. Тьюрингийн машин дараах руу явж болно ( k + 1) зөвхөн дууссаны дараа дах алхам - th алхам, учир нь яг -дах алхам нь юу болохыг тодорхойлдог ( k + 1)-р алхам.

Тодорхой байдал. Алхам бүрт цагаан толгойн тэмдэгт нүд рүү бичигдэж, автомат машин нэг хөдөлгөөн (L, P, N) хийж, Тюринг машин тайлбарласан төлөвүүдийн аль нэгэнд ордог.

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

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

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

РЕДАКТОРООС

Өгүүлэлд өгөгдсөн бүх асуудлыг дэвтэр дээр мэдээллийн зурвас, хүснэгтийн програм зурах замаар энгийн байдлаар шийдэж болно. Гэхдээ та энэ үйл явцыг илүү хөгжилтэй, үзэмжтэй болгож чадна: машины хэрэгжилтийг ашиглана уу - шуудангийн машин болон Радик Зартдиновын бүтээсэн "Algo2000" Тюринг машиныг орчуулагч. Хөтөлбөр нь ойлгомжтой интерфэйстэй бөгөөд түүний шаардлагууд хамгийн дунд зэрэг: IBM PC AT 486 ба түүнээс дээш компьютер, Windows 95/98/NT үйлдлийн систем.

"Algo2000" хэрхэн ажилладагийг ерөнхийд нь харцгаая.

Програмын цэснээс тухайн зүйлийг сонгоно уу Орчуулагчмөн бид ямар машинтай ажиллахыг хүсч байгаагаа зааж өгнө үү (манай тохиолдолд энэ нь "Тюринг машин").

Бидний өмнө Тьюрингийн машины талбар гарч ирнэ.

Одоо та гадаад цагаан толгойг тохируулах хэрэгтэй, i.e. шугаманд Гадаад цагаан толгойҮүнд ямар тэмдэгт багтсаныг заана уу (хэрэв мөр Гадаад цагаан толгойхарагдахгүй байгаа бол та цэсийн зүйлийг сонгох хэрэгтэй Харах | Гадаад цагаан толгой). Тэмдэгт бүрийг зөвхөн нэг удаа зааж өгөх боломжтой. Гадаад цагаан толгойн үсгийг оруулсны дараа хүснэгтийн эхний багана үүсдэг: энэ нь ижил дарааллаар гадаад цагаан толгойн тэмдэгтүүдээр дүүрэн байна. Гадаад цагаан толгойг засах үед хүснэгт автоматаар өөрчлөгддөг: мөрүүдийг оруулах, устгах, солих.

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

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

Жишээлбэл, хэрэв эхний тоо нь хоёр дахь тооноос их, тэдгээрийн хооронд хасах тэмдэг байгаа бол эерэг хоёр бүхэл тооны (аравтын тооллын системд) ялгааг олох алгоритмыг бий болгож байна.

Програмын талбар дараах байдлаар харагдах болно.

Нүд тус бүрийн командын формат aKq байна. Энд:
a нь одоогийн нүдний шинэ агуулга (одоогийн нүдэнд орсон гадаад цагаан толгойн шинэ тэмдэг), K нь Тюринг машины соронзон хальсны механизмын команд (зүүн, баруун, зогсоох), q нь шинэ дотоод төлөв юм. Тюринг машинаас.

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

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

"Зогс" командтай тулгарах эсвэл ямар нэгэн алдаа гарах хүртэл програмыг үргэлжлүүлэн ажиллуулна.

Хэрэв танд орчуулагч програмтай ажиллах явцад асуух зүйл байвал тусламжийн файлаас лавлана уу Algo2000.hlp. Үүнийг мөн "Algo2000" хөтөлбөрийг "Информатик" сонины вэбсайтаас үзэх боломжтой. http://inf.1september.ru"Татаж авах" хэсэгт.

Хиймэл оюун (AI, Англи хэл: Artificial intelligence, AI) - ухаалаг машин, ялангуяа ухаалаг компьютерийн программ бүтээх шинжлэх ухаан, технологи. AI нь хүний ​​оюун ухааныг ойлгохын тулд компьютер ашиглахтай ижил төстэй ажилтай холбоотой боловч биологийн үндэслэлтэй аргуудаар хязгаарлагдах албагүй.

Хиймэл оюун ухаан гэж юу вэ

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

1980-аад оны эхээр. Тооцооллын эрдэмтэд Барр, Файгенбаум нар хиймэл оюун ухааныг (AI) дараахь тодорхойлолтыг санал болгосон.

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

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

AI гэдэг нь чанартай, хурдацтай хөгжиж буй холбогдох технологи, үйл явцын цогц юм, жишээлбэл:

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

Хиймэл оюун ухааныг хөгжүүлэх үндэсний стратеги

• Үндсэн нийтлэл:Хиймэл оюун ухааныг хөгжүүлэх үндэсний стратеги

AI судалгаа

• Үндсэн нийтлэл:Хиймэл оюун ухааны судалгаа

AI дахь стандартчилал

2019 он: ISO/IEC-ийн мэргэжилтнүүд орос хэл дээр стандарт боловсруулах саналыг дэмжив

2019 оны 4-р сарын 16-ны өдөр Хиймэл оюун ухааны салбар дахь стандартчиллын дэд хороо RVC-ийн үндсэн дээр байгуулагдсан "Кибер-физик систем" Техникийн хорооны "Хиймэл оюун ухаан"-ыг хөгжүүлэх саналыг дэмжсэн нь тодорхой болсон. Стандарт. Үзэл баримтлал ба нэр томъёо" англи хэлний үндсэн хувилбараас гадна орос хэл дээр.

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

Дублин хотноо болсон ISO/IEC-ийн холбогдох дэд хорооны хуралдааны дараа ОУСБХ-ны мэргэжилтнүүд хиймэл оюун ухааны салбарт нэр томьёоны стандартыг англи хэлээр төдийгүй орос хэлээр нэгэн зэрэг боловсруулах тухай ОХУ-ын төлөөлөгчдийн саналыг дэмжив. Баримт бичгийг 2021 оны эхээр батлах төлөвтэй байна.

Уулзалтын үеэр ОУСБХ-ны мэргэжилтнүүд мөн ОХУ-ын хамтран редактороор ажилладаг Мэдээллийн технологи - Хиймэл оюун ухаан (AI) - хиймэл оюун ухааны системийн тооцооллын аргын тойм олон улсын баримт бичгийн төслийг боловсруулахыг дэмжив. Энэхүү баримт бичигт хиймэл оюун ухааны системийн өнөөгийн байдлын тойм, системийн үндсэн шинж чанар, алгоритм, хандлагыг тайлбарлахаас гадна хиймэл оюун ухааны салбар дахь тусгай хэрэглээний жишээнүүдийг багтаасан болно. Энэхүү баримт бичгийн төслийг боловсруулах ажлыг дэд хорооны хүрээнд тусгайлан үүсгэн байгуулсан 5-р “Хиймэл оюун ухааны системийн тооцооллын арга барил ба тооцооллын шинж чанар” ажлын хэсэг гүйцэтгэнэ (SC 42 Ажлын хэсэг 5 “Хиймэл оюун ухааны системийн тооцооллын хандлага ба тооцооллын шинж чанар”).

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

Хиймэл оюун ухааны чиглэлээр RVC-д суурилсан TC Cyber-Physical Systems нь 2019 оны сүүл - 2020 оны эхээр батлахаар төлөвлөж буй хэд хэдэн үндэсний стандартыг боловсруулж байна. Түүнчлэн зах зээлд оролцогчидтой хамтран 2020 он болон түүнээс хойшхи Үндэсний стандартчиллын төлөвлөгөөг (NSP) боловсруулахаар ажиллаж байна. "Кибер-физик систем" ТК нь сонирхсон байгууллагуудын баримт бичгийг боловсруулах саналд нээлттэй.

2018 он: Квантын харилцаа холбоо, хиймэл оюун ухаан, ухаалаг хотын салбарын стандартыг боловсруулах

2018 оны 12-р сарын 6-ны өдөр RVC-д суурилсан "Кибер-физик систем" Техникийн хороо нь "SafeNet" бүсийн инженерийн төвтэй хамтран Үндэсний технологийн санаачилга (NTI) болон дижитал эдийн засгийн зах зээлд зориулсан багц стандартыг боловсруулж эхлэв. 2019 оны 3-р сар гэхэд квант харилцаа холбооны салбарт техникийн стандартчиллын баримт бичгийг боловсруулахаар төлөвлөж байна гэж RVC мэдээлэв. Цааш унших.

Хиймэл оюун ухааны нөлөө

Хүн төрөлхтний соёл иргэншлийн хөгжилд эрсдэл

Эдийн засаг, бизнест үзүүлэх нөлөө

• Хиймэл оюун ухааны технологийн эдийн засаг, бизнест үзүүлэх нөлөө

Хөдөлмөрийн зах зээлд үзүүлэх нөлөө

Хиймэл оюун ухааны хазайлт

Хиймэл оюун ухаан (машины орчуулга, яриа таних, байгалийн хэл боловсруулах, компьютерийн хараа, автомат жолоодлого гэх мэт) бүх зүйлийн гол цөм нь гүнзгий суралцах явдал юм. Энэ нь тархины үйл ажиллагааг дуурайдаг гэж хэлж болох мэдрэлийн сүлжээний загваруудыг ашиглан тодорхойлогддог машин сургалтын дэд хэсэг тул тэдгээрийг хиймэл оюун ухаан гэж ангилах нь нэлээд хэцүү байх болно. Мэдрэлийн сүлжээний ямар ч загвар нь том өгөгдлийн багц дээр сургагдсан байдаг тул зарим нэг "ур чадвар" эзэмшдэг боловч тэдгээрийг хэрхэн ашиглах нь бүтээгчиддээ тодорхойгүй хэвээр байгаа бөгөөд энэ нь эцэстээ гүнзгий суралцах олон програмын хамгийн чухал асуудлын нэг болж хувирдаг. Шалтгаан нь ийм загвар нь юу хийдэг талаар ямар ч ойлголтгүйгээр албан ёсоор зурагтай ажилладаг. Ийм AI систем мөн үү, машин сургалтанд суурилсан системд итгэж болох уу? Сүүлчийн асуултын хариултын үр дагавар нь шинжлэх ухааны лабораториос давж гардаг. Тиймээс AI-ийн хэвийх үзэгдэл гэж хэвлэл мэдээллийн хэрэгслээр анхаарал хандуулах нь илт эрчимжсэн. Үүнийг "AI bias" эсвэл "AI bias" гэж орчуулж болно. Цааш унших.

Хиймэл оюун ухааны технологийн зах зээл

Орос дахь хиймэл оюун ухааны зах зээл

Дэлхийн хиймэл оюун ухааны зах зээл

AI-ийн хэрэглээний талбарууд

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

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

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

Батлан ​​хамгаалах, цэргийн асуудалд хиймэл оюун ухаан ашиглах

Боловсролд ашиглах

AI-г бизнест ашиглах

Луйврын эсрэг тэмцэлд хиймэл оюун ухаан

2019 оны долдугаар сарын 11-нд хоёрхон жилийн дараа луйвартай тэмцэхэд хиймэл оюун ухаан, машин сургуулийг 2019 оны долдугаар сарынхаас гурав дахин илүү ашиглах нь тодорхой болсон. Ийм мэдээллийг SAS болон Мэргэшсэн залилан мэхлэгчдийн холбоо (ACFE) хамтран хийсэн судалгааны явцад олж авсан. 2019 оны 7-р сарын байдлаар, судалгаанд оролцсон байгууллагуудын 13% нь луйврын эсрэг ийм хэрэгслийг аль хэдийн ашиглаж байгаа бөгөөд өөр 25% нь ойрын хоёр жилдээ багтаан хэрэгжүүлэхээр төлөвлөж байгаагаа мэдэгджээ. Цааш унших.

Цахилгаан эрчим хүчний салбарт хиймэл оюун ухаан

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

Үйлдвэрлэл дэх хиймэл оюун ухаан

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

Банкууд дахь AI

• Загвар таних - ашигласан зэрэг. салбар дахь үйлчлүүлэгчдийг таньж, тэдэнд тусгайлсан саналыг хүргэх.

Тээвэрлэлтийн AI

• Автомашины салбар хувьсгалын ирмэг дээр байна: нисгэгчгүй жолоодлогын эриний 5 сорилт

Логистик дахь хиймэл оюун ухаан

Шар айраг исгэх AI

Шүүх дэх AI

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

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

“Хиймэл оюун ухааны салбарын хөгжлийн талаарх мэдээ мэдээллийг өдөр бүр хараад та энэ салбарын судлаачид, хөгжүүлэгчдийн шавхагдашгүй төсөөлөл, үр өгөөжийг гайхшруулдаг. Шинжлэх ухааны судалгааны тайлангуудыг зах зээлд гарч буй шинэ бүтээгдэхүүнүүдийн тухай нийтлэлүүд, хиймэл оюун ухааныг янз бүрийн салбарт ашигласнаар олж авсан гайхалтай үр дүнгийн талаархи тайлангууд байнга давхцдаг. Хэрэв бид хиймэл оюун ухаан дахин мэдээний баатар болох хүлээгдэж буй үйл явдлуудын талаар ярих юм бол технологийн таамаглал гаргах эрсдэлгүй байх. Дараагийн үйл явдал бол хаа нэг газар хиймэл оюун ухаантай, шударга, ялзрашгүй маш чадварлаг шүүх бий болно гэж би төсөөлж байна. Энэ нь 2020-2025 онд болох бололтой. Мөн энэ шүүх дээр өрнөх үйл явц нь гэнэтийн эргэцүүлэл, олон хүмүүсийн хүслийг өдөөж, хүний ​​нийгмийг удирдах үйл явцын ихэнхийг хиймэл оюун ухаанд шилжүүлэх болно."

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

Хөгжим

Уран зураг

2015 онд Google-ийн баг мэдрэлийн сүлжээг бие даан зураг үүсгэж чадах эсэхийг шалгахын тулд туршиж үзсэн. Дараа нь олон тооны өөр өөр зураг ашиглан хиймэл оюун ухааныг сургасан. Гэсэн хэдий ч, машинаас ямар нэг зүйлийг бие даан дүрслэхийг "хүссэн" нь бидний эргэн тойрон дахь ертөнцийг зарим талаараа хачирхалтай байдлаар тайлбарласан нь тогтоогджээ. Жишээлбэл, дамббелл зурах ажилд зориулж хөгжүүлэгчид металыг хүний ​​гараар холбосон дүрсийг хүлээн авсан. Энэ нь сургалтын шатанд дамббелл бүхий дүн шинжилгээ хийсэн зургуудад гар байсантай холбоотой бөгөөд мэдрэлийн сүлжээ үүнийг буруу тайлбарласантай холбоотой байж магадгүй юм.

2016 оны 2-р сарын 26-нд Сан Франциско хотод болсон тусгай дуудлага худалдаагаар Google-ийн төлөөлөгчид хиймэл оюун ухаанаар бүтээсэн сэтгэцэд нөлөөлөх зургуудаас 98 мянган доллар цуглуулсан. Машины хамгийн амжилттай зургуудын нэгийг доор үзүүлэв.

Google-ийн хиймэл оюун ухаанаар зурсан зураг.

Бид үүнийг байнга хардаг. "RESTful" энэ, "REST" протокол тэр гэх мэт. Гэсэн хэдий ч бидний ихэнх нь яг юу гэсэн үг болохыг ойлгодоггүй. Бид энэ нийтлэлд яг тэр цоорхойг засах болно!

муж

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

Жишээлбэл, температур 80 хэмээс дээш бол дэлгэцийг улаан болгож, 80 хэмээс бага бол цэнхэр өнгөтэй болгодог програм бичдэг гэж хэлье.

Бид эхний төлөвийг (температур > 80 градус) "А", хоёр дахь төлөвийг (темпера< 80 degrees) state “B”. We’ll call the middling state (temp = 80 degrees) state “C”. As we can see, we have defined behaviours of the programs at state A and state B, but not at state C.

Энэ бол төрийн ерөнхий санаа юм. Бүгдийг мэддэг Википедиагийн өгсөн тодорхойлолтыг энд оруулав.

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

Товчхондоо, энэ нь програмын анхааралдаа авсан бүх мэдээллийн нэг төрлийн "хослол" юм.

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

Тюринг машинууд

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

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

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

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

Турингийн машиныг ашиглан компьютерийн эрдэмтэд компьютер дээр ажиллаж болох аливаа алгоритмын талаар дүгнэлт хийх боломжтой. Ер нь Тьюрингийн машин нь компьютерийн шинжлэх ухаанд олон дэвшил авчирсан.

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

Сүлжээ

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

Үйлчлүүлэгчид хурдан орж ирээд хоёр дахин хурдан гардаг. Иймээс сүлжээний систем дээр ажиллахдаа үйлчлүүлэгчийн төлөвийг барих нь тийм ч утгагүй юм.

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

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

Энэ протокол нь HTTP байсан бөгөөд HTTP дээрх ажлын үр дүнд бий болсон онолыг REST гэж нэрлэсэн.

АМРАХ

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

"АМРАЛТАЙ" гэж үздэг бүх систем дагаж мөрдөх ёстой хэд хэдэн хязгаарлалт байдаг.

Юуны өмнө, тэр ёстойүйлчлүүлэгч-сервер систем байх. Энэ хязгаарлалтыг өмнө нь өөрчилсөн боловч албан ёсны тодорхойлолтоор (мөн REST-ийн онолыг зөв ажиллуулахын тулд) бидэнд үйлчлүүлэгчид холбогдох серверүүд бий.

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

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

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

Одоо, эдгээр бүх шинж чанаруудыг нэгтгэхдээ юуг агуулдаг вэ?

REST-ийн үр дагавар

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

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

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

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

Нэг төрлийн интерфейс нь хамгийн чухал байж болох юм. SOAP-тай ажиллаж байхдаа HTTP-ийн энгийн формат нь серверийн кодыг дибаг хийх гэж оролдоход адислал бөгөөд бусад RESTful системүүдэд ч мөн адил гэдгийг хэлж чадна.

RESTful системийг зохион бүтээх

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

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

Бид эхлээд протоколын хэл хэрхэн ажиллахыг тодорхойлж эхэлдэг (HTTP-ийн GET ба POST үйл үгтэй адил):

QUOTE тэмдэг- тодорхой хувьцааны үнийг өгдөг
ADDTICKER тэмдэг- өгөгдсөн хувьцааг жагсаалтад нэмнэ
GETLIST - жагсаалтад байгаа хувьцааны таслалаар тусгаарлагдсан жагсаалтыг авна

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

Мөн, энэ бол бүх зүйл! Мэдээжийн хэрэг, бид үүнийг хэрэгжүүлэх шаардлагатай хэвээр байна, гэхдээ системийн ерөнхий санаа нь маш энгийн бөгөөд цэвэрхэн юм!

Дүгнэлт

Энэ нийтлэл танд REST-ийн талаар сайн ойлголт өгсөн гэж найдаж байна.

Түүнчлэн, та одоо "АМРАЛТАЙ" гэсэн нэр томъёог хэт их хаядаг хүмүүсийг дуудаж чадна гэж найдаж байна - би танд хэлье, тэд маш олон байна!

ТУРИНГ

ТУРИНГ(Тюринг) Алан (1912-54), Английн математикч, логикч, хожим компьютерийн технологийн үндэс болсон онолыг томъёолсон. 1937 онд тэрээр гарч ирэв Тюринг машин -оролтын командын багцыг хувиргах чадвартай таамагласан машин. Энэ бол орчин үеийн компьютеруудын анхдагч байсан. Тьюринг мөн компьютерийн санааг ашиглан Годелийн бүрэн бус байдлын теоремыг өөр бөгөөд энгийн нотолгоо болгон өгсөн. Дэлхийн 2-р дайны үед Германы хэрэглэж байсан шифрлэлтийн нарийн төвөгтэй арга болох Enigma-г шийдвэрлэхэд Тьюринг гол үүрэг гүйцэтгэсэн. 1948 онд тэрээр дэлхийн анхны компьютеруудын нэгийг бүтээхэд оролцсон. 1950 онд тэрээр гарч ирэв Тюринг тест -Энэ нь компьютерийн "сэтгэн бодох" чадварыг шалгах тест байх ёстой байсан. Үндсэндээ хүн машинтай яриа хэлцлийг өөр хүнтэй харилцахаас ялгаж салгаж чадахгүй гэж заасан. Энэхүү ажил нь ХИЙМЭЛ ОЮУНЫГ бий болгох эхлэлийг тавьсан юм. Тьюринг мөн онолын биологийн чиглэлээр ажилладаг байв. Ажиллаж байна "Морфогенезийн химийн үндэс"(1952) тэрээр биологи дахь организмын янз бүрийн бүтцийн хэв маягийн гарал үүслийг дүрсэлсэн загварыг санал болгосон. Түүнээс хойш ийм загварууд нь байгальд ажиглагдсан олон системийг тайлбарлах, тайлбарлахад ихэвчлэн ашиглагддаг. Тьюринг ижил хүйстэн гэж албан ёсоор буруутгагдаж амиа хорлосон.

Шинжлэх ухаан, техникийн нэвтэрхий толь бичиг.

Бусад толь бичгүүдэд "TURING" гэж юу болохыг хараарай:

Тьюринг, Алан Матисон Алан Тюринг Саквилл Парк дахь Алан Матисон Тьюрингийн хөшөө Төрсөн он сар өдөр ... Википедиа

- (Тюринг) Алан Матисон (1912 54), Английн математикч. 1936-1937 онд тэрээр алгоритмын хийсвэр эквивалент буюу тооцоолох функцийн математик ойлголтыг нэвтрүүлсэн бөгөөд тэр үед Тьюрингийн машин гэж нэрлэгддэг байсан... Орчин үеийн нэвтэрхий толь бичиг

- (Тюринг), Алан Матесон (1912 оны 6-р сарын 23 - 1954 оны 6-р сарын 7) - Англи. логикч, математикч. 1936-37 онд тэрээр тооцооллын хамгийн тохиромжтой машин загварыг санал болгосон. үйл явц - тооцоо хийж байгаа хүний ​​үйлдэлтэй ойролцоо тооцооллын схем, дэвшүүлсэн... ... Философийн нэвтэрхий толь бичиг

Тюринг А.- Английн математикч Тюринг А. Сэдвүүд мэдээллийн аюулгүй байдал EN Turing… Техникийн орчуулагчийн гарын авлага

Алан Тюринг Саквилл цэцэрлэгт хүрээлэн дэх Алан Тьюрингийн хөшөө Төрсөн огноо: 1912 оны 6 сарын 23 Төрсөн газар: Лондон, Англи нас барсан огноо: 1954 оны 6 сарын 7 ... Википедиа

Тюринг- Английн математикч Алан М.Тюринг, ялангуяа компьютерийн технологийн логик үндсийг бүтээгчдийн нэг, алгоритмын албан ёсны тодорхойлолтуудын нэгийг өгсөн; симуляци хийх боломжтой компьютерийн ангилал байдгийг нотолсон. Лемийн ертөнц - Толь бичиг ба гарын авлага

- (Тюринг) Алан Матисон (1912.06.23, Лондон, 1954.07.6, Манчестер хотын ойролцоох Вилмслоу), Английн математикч. Хатан хааны нийгэмлэгийн гишүүн (1951). Кембрижийн их сургуулийг төгсөөд (1935) Принстонд докторын зэрэг хамгаалжээ... ... Зөвлөлтийн агуу нэвтэрхий толь бичиг

Тюринг А.М.- TURING (Turing) Alan Mathieson (191254), Англи хэл. математикч. Үндсэн tr. математикт логик, тооцоолол. математик. 193637 онд тэрээр математикийг нэвтрүүлсэн. алгоритмын хийсвэр эквивалент буюу тооцоолох функцийн тухай ойлголтыг дараа нь гэж нэрлэдэг. машин Т... Намтар толь бичиг

- (бүтэн Алан Матисон Тюринг) (1912 оны 6-р сарын 23, Лондон, 1954 оны 6-р сарын 7, Вилмслоу, Их Британи), Британийн математикч, математик логик, тооцооллын математикийн бүтээлүүдийн зохиогч. 1936-1937 онд математикийн ухагдахууныг... нэвтэрхий толь бичиг

Номууд

• Машин сэтгэж чадах уу? Автоматуудын ерөнхий ба логик онол. Дугаар 14, Тюринг А., Анхны сэтгэдэг компьютерийг бүтээх эхлэл болсон Алан Тюринг, Жон фон Нейманн нарын бүтээлүүдийг багтаасан энэхүү ном нь философи-кибернетикийн сонгодог бүтээлүүдэд багтдаг... Ангилал: Мэдээллийн сан Цуврал: Хиймэл шинжлэх ухаан Нийтлэгч: URSS, Үйлдвэрлэгч: URSS,
• Машин сэтгэж чадах уу? Автоматуудын ерөнхий ба логик онол. Дугаар 14, Тюринг А., Компьютерийн анхны "сэтгэхүйн машин"-ыг бүтээх эхлэл болсон Алан Тюринг, Жон фон Нейман нарын бүтээлүүдийг багтаасан энэхүү ном нь философи-кибернетикийн сонгодог бүтээлүүдэд багтдаг. чиглэл... Ангилал: