«Алгоритм деген эмне» макаласын оңдоо, толуктоо, тактоо

Алгоритм, сейрек алгорифм (латынча algorithmi — ортоазиялык математик Аль-Хорезминин ысымынан) — айрым класстардын тапшырмаларын же жөн гана белгилүү бир тапшырмаларды чечүү үчүн, аткаруучуга иштин иретин баяндаган так берилген эрежелердин жыйындысы же нускамалардын топтому.

Макала мазмуну

Жалпы маалымат
Тарыхынан
Мааниси, колдонулушу
Түрлөрү
Алгоритмдик жактан чечилбеген тапшырмалар
Дагы караңыз

Жалпы маалымат
Эски түшүндүрмөдө «ирет» сөзүнүн ордуна «ыраат» сөзү колдонулган, бирок, компьютерлердин параллелдүүлүгүнүн өнүгүүсү менен «ыраат» сөзүн жалпыраак келген «ирет» сөзү менен алмаштыра баштаган.

Эгер колдонулуучу аткаруучулар мүмкүндүк берсе көз карандысыз нускамалар ар кандай иретте, параллелдүү аткарылышы мүмкүн.

Бардык машиналардын башкы өзгөчөлүгү — алардын иштөө негизинде, башкаруунун программалык негиздин жаткандыгында. Бул негиз маселени чечүү үчүн адам зарыл нускамаларды же буйруктардын тизмегин колдонот, ЭЭМ болсо ошол ирет боюнча улам бир буйрук аткаруу менен керектүү натыйжаны берет дегенди түшүндүрөт.

Алгоритм схемасы, мисал

Алгоритмди бир гана эсептөөчү машиналар колдонбойт, муну адамдар дагы колдонушат, мисалы, «бүгүн дүкөнгө барып, сүт сатып алам, анан кайра үйгө барам» деген сыяктуу.

Алгоритм түшүнүгүндөгү эсептөө процесстери жалаң эле цифралар менен болгон эсептөө деп дагы түшүнүүгө болбойт. Алгебрада тамгалуу туюнтмалар, арифметикада ар кандай символдор (кашаа, барабардык белгиси, кошуу, көбөйтүү, кемитүү, бөлүү белгилери ж. б.) кездешет.

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

Жөнөкөй тил менен айтканда, алгоритм — ишти кезеги менен жасоо деп түшүнсөк болот. Каалаган маселени чечүү үчүн, адегенде аны алгоритмдештирүү керек. Мисалы, биринчи фундамент куябыз, анан дубалдарды тургузабыз. Ушул кадам артынан кадам жасалган иш алгоритм болот. Дубалды тургузуп, анын үстүнө фундамент куйбайбыз да.

Информатикада алгоритм деп — көздөгөн максатка жетүүгө же коюлган маселени чечүүгө багытталган аракеттердин ырааттуулугун (иретин) ишке ашыруу үчүн аткаруучуга берилген түшүнүктүү жана так буйрукту (көрсөтмө) айтабыз.

Алгоритм кадамы — бул алгоритмдин ар бир өзүнчө иш-аракети.

Информатикада алгоритм — маалымат түшүнүгү сыяктуу эле фундаменталдуу түшүнүк. Ошондуктан аны терең түшүнүү маанилүү.

Алгоритм түшүнүгү кибернетиканын негизги түшүнүктөрүнүн бири, аны 7 параметр менен мүнөздөөгө болот:

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

Алгоритм математикалык эсептөөдө негизги мааниге ээ болуп, аны тактоону Э. Л. Пост менен А. Тьюринг биринчи сунуш кылган (1936). А. А. Марков менен А. Н. Колмогоров да тактоолорду киргизген.

Тарыхынан
Алгоритм термининин келип чыгышы орто кылымдагы Чыгыштын улуу окумуштуусу Мухаммед ибн Муса аль-Хорезминин (Хорезмдик Муса уулу Мухаммед) ысымы менен байланыштуу. Ал 783-850-жылдар аралыгында азыркы Өзбекстандагы Хорезм облусунун аймагында жашап өткөн. Ал көп орундуу сандар менен арифметикалык эсептөөлөрдү аткаруунун ыкмаларын (аларды силер мектептеги математика сабагынан жакшы билесиңер) сунуштаган. Кийин Европада бул ыкмалар алгоритмдер (Algoritmi — аль-Хорезминин ысмынын латынча жазылышынан) деп аталып калган.

Арифметикалык эсептөөлөрдүн алгоритмдери аткаруучу — адам үчүн сыпатталган. Азыркы убакта алгоритм түшүнүгү арифметикалык эсептөөлөр менен эле чектелбестен, кеңири мааниде туюнтулат.

Мисалы: салат жасоо алгоритми, программа түзүү, унааны жасоо, эсеп чыгаруу, ийгиликке жетүү алгоритми дегендей, жашоодо алгоритм өтө көп кезигет. Жада калса эртең менен биз бетибизди жууп, анан таңкы тамакка отурабыз бул дагы алгоритм, бирок аны адам тилинде биз адат же балким салт деп коёбуз. Муну компьютерге түшүндүрүү үчүн алгоритмдерди камтыган программа түзүү зарыл.

Ошентип, алгоритм түшүнүгү ЭЭМдин пайда болушунан мурда эле келип чыккан. Бирок бул түшүнүк автоматтардын жана роботтордун доорунда кеңири жайылды.

Мааниси, колдонулушу
Алгоритмдерди түзүү жана окуп-үйрөнүү программалоочунун кесибин тандап алуучу окуучу-студенттерге гана керек деп ойлобогула. Кубулуштун алгоритмдик маңызын бөлүп алуу жана алгоритмди түзө билүү — түрдүү кесиптеги адамдар үчүн маанилүү.

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

Алгоритмди окуп-үйрөнүүгө киришүүдөн мурда абдан маанилүү түшүнүктүн бири — аткаруучу түшүнүгүн так аныктап алалы. Алгоритм кандайдыр бир объекттин (мисалы компьютердин деп коёлу) ишин башкаруучу командалардын ырааттуулугу (ирети). Ал башкарылуучу объект болот. Ал техникалык түзүлүш да, тирүү жандык да болушу мүмкүн. Мындан ары аны алгоритмди аткаруучу деп атайбыз.

Алгоритм түшүнүгү биз үчүн кандайдыр бир жаңы жана өзгөчө нерсе деле эмес. Алар биздин күнүмдүк турмушта ар бир кадам сайын жолугат. Эртең менен окуучу мектепке жөнөрдө апасы мындай көрсөтмөлөрдү бериши мүмкүн: «Мектептен келгенден кийин түшкү тамакты ич жана идиш-аякты жууганды унутпагын. Дүкөндөн жашылча-жемиш, азык-түлүк сатып келип, бир сааттай сейилде, андан кийин үйгө берилген тапшырмаларыңды аткар». Бул көрсөтмө окуучуун жүрүш-турушун аныктаган айрым көрсөтмөлөрдүн ирети. Ушунун өзү алгоритм болуп саналат.

Компьютердик алгоритми көбүнчө коштоп жүрүүчү нерсе бул — шарттуу операторлор: «эгер», «антпесе», «же», «жана» ж. б. Адамдар деле муну көп колдонот.

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

Ар бирибиз ойлонбостон эле күнүгө жүздөгөн алгоритмдерди колдонобуз. Мисалы, сандарды кошуу, алуу, бөлүү, көбөйтүү эрежелери; алгебралык туюнтмаларды өзгөртүү эрежелери; сөздөрдү жана сүйлөмдөрдү жазуунун грамматикалык эрежелери.

Ушундай эле маанайда адамдын кандайдыр бир ишти аткаруу аракеттеринин ырааттуулугун ишке ашыруу рецепттерин жана инструкцияларын алгоритмдер деп атасак болот. Мисалы, кулинардык рецепт — бул ашпозчунун тамак даярдоо максатындагы иштөө алгоритми.

Сыр менен омлет даярдоо үчүн төмөнкүдөй иретте жасалат:

50 г ак нандын жумшак бөлүгүнө 3 аш кашык сүт кошуп эз;
Бул аралашмага 3 жумуртка чегип, анын баарын кашык менен жакшылап чал;
50 г майдаланган сырды кош;
Туз кош, аралаштыр, андан кийин ысытылган табага 1 чоң кашык май куй;
Акырындык менен аралаштырып күчтүү оттун табына кууру;

Бул келтирилген рецепт да алгоритмдин мисалы болуп саналат. Дагы бир мисалды карайлы. Автомобилге түшүп, аны айдоо үчүн, бир катар аракеттерди аткаруу зарыл:

Автомобилдин руль жагына отур;
Колуң менен от алдыруучу ачкычты саат жебесинин багыты боюнча бура, кыймылдаткычты иштет;
Сол бутуң менен чиркештирүү педалын бас, оң бутуң менен рычагды (же кнопканы) жүрүүнүн биринчи берүүсүнө туташтыр;
Бир эле убакта сол бутуң басып турган чиркештирүү педалын акырындык менен коё бер, ал эми оң бутуң менен ошондой эле күч менен "акселератор" педалын же кыргызча газды полго жабыштыра бас :-) Албетте тааша, акырындык менен басуу керек;
Рулдун дөңгөлөгүн оңго-солго айлантып, автомобилди керектүү тарапка багыттап айда;
Анда-санда арткы күзгүнү кара.

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

Мектептеги предметтерде да алгоритмдердин көп мисалдары келтирилет. Мындай мисалдардын көбү математика курсунда кездешет. Бул силерге түшүнүктүү болсо керек, себеби математика ар кандай алгоритмдерди изилдөөнү жана жаңыларын түзүүнү окутуп-үйрөтөт эмеспи.

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

Алгоритм тилинде алгоритмдердеги кызматчы сөздөр айырмаланган шрифт менен жазылат. Программалоо тилинде (алгоритм тили сыңары) бир гана белгилүү мааниге ээ болгон сөздөр кызматчы сөздөр деп аталат.

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

Түрлөрү
Алгоритмдерди ар кандай белгилери боюнча классификациялоого болот. Негизги түрлөрү кийинкидей:

Процессти уюштуруу ыкмасы боюнча:

Сызыктуу — кадам артынан кадам ырааты менен аткарылат.
Бутактануучу — кийинки кадамдарды аткаруунун тандоосун аныктаган шарттарды камтыйт (эгер, антпесе, же, жана)
Циклдик — жыйынтык чыгаруучу шарты аткарылмайынча кайталануучу иш-аракеттерди камтыйт.

Тапшырманы чечүү ыкмасы боюнча:

Детерминирленген — бирдей кириш маалыматтарда бирдей аткарылат.
Детерминирлен эмес — бирдей кириш маалыматтарда ар кандай жыйынтыктарды бериши мүмкүн.

Маалыматтардын түзүмү боюнча:

Зыкым же сараң алгоритмдер — ар бир кадамда оптималдуу локалдуу чечимди тандашат.
Динамикалык программалоо — тапшырманы майда тапшырмаларга бөлүп, алардын жыйынтыктары кайталанып колдонулат (бир жасалган чечимди, кайра-кайра аткарбастан дароо жыйынтыгын алат).
Бөлүп ал жана бийле — тапшырманы рекурсивдүү бөлүктөргө бөлүп, аларды өзүнчө чечип, жыйынтыкты бириктирет.
Кайтарым издөө (Backtracking) — тапшырманы чечүү мүмкүн эмес болгондо, артка кайтып мүмкүн болуучу варианттарды иштетет.

Колдонуу тармагы боюнча:

Сорттоо (тез, көбүктүк, коюуулар менен ж. б.)
Издөө (сызыктуу, бинардык)
Графтык алгоритмдер (DFS, BFS, Дейкстрлер, Беллман-Форд)
Криптографиялык (RSA, AES, SHA)
Жасалма интеллект (генетикалык алгоритмдер, нейро тармактар)

Алгоритмдик жактан чечилбеген тапшырмалар
Алгоритмдик жактан чечилбеген тапшырмалар — бул, алгоритм колдонууга мүмкүн болбогон тапшырмалар. Башкача айтканда, мындай тапшырмануу чечүүгө программа түзүүгө болбойт. Мисалы:

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

Айтылгандар, үч гана мисал болду, мындан тышкары дагы башка алгоритмдик жактан чечилбеген тапшырмалар да болот.

Чечилбегендикти кантип аныктоо керек? Көп учурда чечилбегендикти редукциянын же Кантордун диагоналдык ыкмасынын жардамы аркылуу тастыкташат.

Дагы караңыз

Компьютердин архитектурасы
Компьютердин тузулушу
Компьютердин аппараттык жабдылышы
Клавиатура жонундо тушунук
Принтер тууралуу маалымат
Информатика деген эмне