From Wikipedia, the free encyclopedia
Математикала һәм компьютер фәндәрендә алгоритм (фарсы телендә خوارزمی [al-Khwārazmī]) — этаплап иҫәпләү процедураһы. Анығыраҡ әйткәндә, алгоритм — мәсьәләне сисеүҙең аныҡ күрһәтмәләрҙән торған сикле теҙмә рәүешендә сағылдырылған ысулы. Алгоритм ярҙамында иҫәпләү процедураһы башланғыс күрһәтмәнән кереү мәғлүмәттәре менән башланып, башҡарылыу барышында эҙмә-эҙлекле аныҡ күрһәтмәләр аша үтә һәм, аҙаҡта сығыу мәғлүмәттәре булдырып, һуңғы күрһәтмәлә тамамлана.
Алгоритм | |
![]() | |
![]() | |
Кем хөрмәтенә аталған | Әл-Хәрәзми |
---|---|
Етештереү ысулы | алгоритмизация[d] |
Вики-проект | Проект:Информационные технологии[d] һәм Проект:Математика[d] |
EntitySchema для класса | Ошибка Lua в Модуль:Wikidata на строке 301: Неизвестный тип сущности.. |
![]() |
Алгори́тм (лат. algorithmi — Урта Азия математигы Әл-Хәрәзми исеменән алынған[1]) — билдәле бер мәсьәләне сығарыу өсөн башҡарыусының эш итеү тәртибен тасуирлаусы, ҡайһы бер класс мәсьәләләрен сығарыуҙың аныҡ ҡағиҙәләренән торған сикле йыйылма йәки күрһәтмәләр йыйынтығы. Иҫке трактовкала «тәртип» һүҙе урынына «эҙмә-эҙлеклек» һүҙе ҡулланыла, компьютерҙар эшендә параллеллек үҫешкән һайын «эҙмә-эҙлеклек» һүҙе дөйөмерәк «тәртип» һүҙе менән алмаштырыла башлай. Ирекле инструкциялар, әгәр ҡулланылған башҡарыусылар мөмкинлек бирһә, ирекле тәртиптә, параллель башҡарыла алалар.
Элегерәк рус телендә «алгорифм» тип яҙғандар, хәҙер ундай яҙыу һирәк ҡулланыла, шулай булыуға ҡарамаҫтан ташлама ғәмәлдә (Марковтың нормаль алгорифмы]]).
Йыш ҡына башҡарыусы сифатында компьютер сығыш яһай, ләкин алгоритм төшөнсәһе компьютер программаларына ғына ҡағылмай, шулай, мәҫәлән, аныҡ тасуирланған ашамлыҡ әҙерләү ысулы шулай уҡ алгоритм була, был осраҡта башҡарыусы булып кеше тора (ә бәлки ниндәйҙер механизм, мәҫәлән һанлы идара ителеүсе туҡыу станогы, һәм башҡалар).
Иҫәпләү алгоритмдарын (артабан һүҙ күберәк шулар тураһында бара), һәм идара итеү алгоритмдарын айырып ҡарарға була. Иҫәпләү алгоритмдары ниндәйҙер функцияны иҫәпләүҙе башҡарып, бирелгән башланғыс мәғлүмәттәрҙе сығыу мәғлүмәттәренә үҙгәртәләр. Идара итеү алгоритмдарының семантикаһы тулыһынса айырыла һәм билдәләнгән ваҡыттарҙа йәки тышҡы ваҡиғаларға реакция сифатында тейешле идара итеүсе ғәмәлдәр сығарыуға ҡайтарылып ҡалдырылырға мөмкин (был осраҡта, иҫәпләү алгоритмынан айырмалы рәүештә, идара итеү алгоритмы сикһеҙ башҡарыу ваҡытында рөхсәт ителә торған булып ҡалырға мөмкин).
Алгоритм төшөнсәһе математиканың төп, башланғыс төшөнсәләре иҫәбенә керә. Алгоритмик характерҙағы иҫәпләү процестары (бөтөн һандар өҫтөндә арифметик ғәмәлдәр, ике һандың иң ҙур уртаҡ бүлеүсеһен табыу һәм башҡалар) кешелеккә борондан билдәле булған. Шулай ҙа был төшөнсә XX быуат башында ғына асыҡтан-асыҡ формалаша.
Алгоритм төшөнсәһен өлөшләтә формалләштереү, Давид Гильберт 1928 йылда формулировкалаған хәл итеү проблемаһын хәл итергә маташыуҙарҙан башлана (нем. Entscheidungsproblem). Формалләштереүҙең артабанғы этаптары эффектив иҫәпләүҙәрҙе[2] йәки «эффектив ысулдарҙы»[3] билдәләү өсөн кәрәк була; шундай формалләштереүҙәр араһында — Гёдель — Эрбран — Клиниҙың рекурсив функциялары 1930, 1934 һәм 1935 йй., Алонзо Чёрчтың λ-иҫәпләмәһе 1936 й., Эмиль Посттың 1936 йылдағы «формулировка 1-е» һәм Тьюринг машинаһы.
Алгоритмдың төрлө билдәләмәләренә асыҡ йәки асыҡ булмаған формала түбәндәге бер нисә дөйөм талаптар ҡуйыла:
Математиканың төрлө теоретик проблемалары һәм физика һәм техниканың үҫешенең тиҙләнеше алгоритм төшөнсәһенең аныҡ билдәләмәһен биреүҙе талап итә.
Алгоритм төшөнсәһен беренсе аныҡларға маташыуҙар һәм уны өйрәнеү X быуаттың беренсе яртыһында Алан Тьюринг, Эмиль Пост, Жак Эрбран, Курт Гедель, А. А. Марков, Алонзо Чёрч тарафынан башҡарыла. Алгоритм төшөнсәһенең бер нисә билдәләмәһе эшләнә, аҙаҡтан уларҙың бөтәһенең дә бер үк төшөнсәне билдәләгәне асыҡлана (ҡарағыҙ. Тезис Чёрча — Тьюринга)[6]
Рәсәй математигы, Советтар Союзында структуралы лингвистикаға нигеҙ һалған В. А. Успенский алгоритм төшөнсәһе иң беренсе Эмиль Борелдең 1912 йылда аныҡ интеграл тураһында мәҡәләһендә күренә тип иҫәпләй. Унда ул «тормошҡа ашырырға мөмкин булған иҫәпләүҙәр» тураһында яҙа, шул уҡ ваҡытта: «Мин аңлы рәүештә күберәк йәки әҙерәк практик эшмәкәрлекте ситтә ҡалдырам; асылы шунда, был операцияларҙың һәр береһе сикле ваҡыт эсендә ышаныслы һәм ике мәғәнәле булмаған ысулдар менән башҡарыла алалар» тип һыҙыҡ өҫтөнә ала[7].
Тьюринг машинаһының нигеҙендә ятҡан төп идея бик ябай. Тьюринг машинаһы — ул символдар яҙылған айырым күҙәүҙәр таҫмаһы менән эшләүсе абстракт машина (автомат). Машинаның шулай уҡ күҙәүҙәрҙәге символдарҙы яҙыу һәм уҡыу өсөн таҫма буйлап хәрәкәт итә алған башы (головка) бар. Һәр аҙымында машина баш күрһәткән күҙәүҙәге символды уҡый, һәм, уҡылған символ һәм эске торошо нигеҙендә артабанғы аҙымын яһай. Шул уҡ ваҡытта машина үҙенең торошон үҙгәртергә, күҙәүгә икенсе символ яҙырға, йәки башын бер күҙәүгә уңға йәки һулға күсерергә мөмкин[8]
Был машиналарҙы тикшереү нигеҙендә Тьюринг тезисы тәҡдим ителә (алгоритдарҙың төп гипотезаһы):
![]() |
Ниндәйҙер алфавитта бирелгән функцияның ҡиммәттәрен табыу өсөн ниндәйҙер алгоритм, функция Тьюринг буйынса иҫәпләнгәндә генә һәм бары тик шул саҡта, йәғни уны Тьюринг машинаһында иҫәпләп булғанда ғына була. | ![]() |
Был тезис аксиома, постулат булып тора, һәм математик ысулдар менән иҫбат ителә алмай, сөнки алгоритм аныҡ математик төшөнсә түгел.
Һәр алгоритм менән ул иҫәпләгән функцияны ярашлы ҡуйып була. Әммә ирекле функцияға Тьюринг машинаһын ярашлы ҡуйып буламы тигән һорау тыуа, ә әгәр булмаһа, ниндәй функциялар өсөн алгоритм бар? Ошо һорауҙарҙы тикшереү 1930-сы йылдарҙ рекурсив функциялар теорияһына килтерә[9].
Иҫәпләнмәле функциялар класы аксиомалар системаһы нигеҙендә ниндәйҙер аксиоматик теорияны төҙөүҙе хәтерләткән һында яҙыла. Башта иҫәпләүе күҙгә күренеп торған иң ябай функциялар һайлап алына. Аҙаҡ булған функциялар нигеҙендә яңы функцияларҙы төҙөү ҡағиҙәләре (операторҙар) әйтеп бирелә. Кәрәкле функциялар класы иң ябай функцияларҙан операторҙарҙы ҡулланып алып була торған бөтә функцияларҙан тора.
Тьюринг тезисына оҡшаш рәүештә иҫәпләнмәле функциялар теорияһында Чёрч тезисы тип аталған гипотеза тәҡдим ителә:
![]() |
Һанлы функция өлөшләтә рекурсив булғанда ғына һәм бары тик шул саҡта ғына алгоритм ярҙамында иҫәпләнә. | ![]() |
Иҫәпләнмәле функциялар класы Тьюринг буйынса иҫәпләнеүселәр менән тап килеүен иҫбатлау ике аҙымда башҡарыла: тәүҙә иң ябай функцияларҙың Тьюринг машинаһында иҫәпләнеүен, ә аҙаҡ — операторҙар ҡулланыу һөҙөмтәһендә алынған функцияларҙың иҫәпләнеүен иҫбатлайҙар.
Шулай итеп, формаль булмаған рәүештә алгоритм, әгәр ул булһа, сикле һандағы аҙымдан һуң тәүге мәғлүмәттәрҙән (индереүҙә) эҙләнгән һөҙөмтәгә (сығарыуҙа) алып барыусы дискрет детерминистик процесты билдәләүсе аныҡ инструкциялар системаһы тип билдәләнә ала; әгәр эҙләнгән һөҙөмтә булмаһа, алгоритм йә бер ҡасан да эште тамамламай, йәки аптырап ҡала.
Марковтың нормаль алгоритмы (автор яҙыуында алгорифм) — ул билдәле бер алфавит символдарынан төҙөлгән төп һүҙҙәрҙән яңы һүҙҙәр алыуҙың билдәле бер процедураларын тормошҡа ашырыусы алмаштырыуҙарҙы эҙмә-эҙлекле ҡулланыу системаһы. Тьюринг машинаһы кеүек үк, нормаль алгоритмдар иҫәпләүҙәрҙең үҙҙәрен башҡармайҙар: улар тик хәрефтәрҙе бирелгән ҡағиҙәләр буйынса алмаштырыу юлы менән һүҙҙәрҙе үҙгәртеүҙе башҡаралар[10].
Нормаль иҫәпләнмәле тип нормаль алгоритм менән башҡарырға мөмкин булған функцияны атайҙар. Йәғни функцияның мөмкин булған бирелештәр күмәклегенән һәр һүҙҙе уның тәүге ҡиммәтенә үҙгәртеүсе алгоритм[11]..
Нормаль алгоритмдар теорияһын төҙөүсе А. А. Марков, Марковтың нормалләштереү принцибы тип аталған гипотезаны тәҡдим итә:
![]() |
Ниндәйҙер алфавитта бирелгән функцияның ҡиммәттәрен табыу өсөн, функция нормаль иҫәпләнмәле булғанда ғына һәм бары тик шул саҡта ғына ниндәйҙер алгоритм бар. | ![]() |
Тьюринг һәм Черчтың тезистарына оҡшаш рәүештә, Марковтың нормалләштереү принцибы математик ысулдар менән иҫбатлана алмай.
Юғарыла килтерелгән алгоритмдың формаль билдәләмәһе ҡайһы бер осраҡтарҙа үтә ҡәтғи булырға мөмкин. Ҡайһы берҙә осраҡлы дәүмәлдәрҙе ҡулланыу кәрәклеге килеп тыуа[12]. Баштағы бирелештәр менән генә түгел, Ҡалып:D-l алынған ҡиммәттәр менән дә эшләүсе алгоритм стохастик алгоритм тип атала[13]. Формаль рәүештә ундай алгоритмдарҙы алгоритм тип атарға ярамай, сөнки стохастик алгоритмдар йыш ҡына детерминирланғандарҙан нәтижәлерәк булалар, ә айырым осраҡтарҙа — мәсьәләне сисеүҙең берҙән-бер ысулы[12].
Практикала осраҡлы һандар генераторы урынына псевдо-осраҡлы һандар генераторы ҡулланыла.
Әммә стохастик алгоритмдарҙы һәм юғары ихтималлыҡ менән дөрөҫ нәтижә биреүсе ысулдарҙы айырып ҡарарға кәрәк. Ысулдан айырмалы рәүештә, алгоритм хатта оҙаҡ эшләгәндән һуң да дөрөҫ һөҙөмтәләр бирә.
Ҡайһы бер тикшеренеүселәр стохастик алгоритмдың алдан билдәле булған ниндәйҙер ихтималлыҡ менән дөрөҫ булмаған һөҙөмтә биреү мөмкинлеген таный. Ул саҡта стохастик алгоритмдарҙы ике төргә бүлергә мөмкин[14]:
Ҡайһы бер мәсьәләләр өсөн юғарыла аталған формализациялар сығарылышын эҙләүҙе һәм тикшеренеүҙәрҙе тормошҡа ашырыуҙы ҡыйынлаштырырға мөмкиндәр. Ҡаршылыҡтарҙы еңеп сығыу өсөн «классик» схемаларҙың модификациялары эшләнә, шулай уҡ алгоритмдарҙың яңы моделдәре булдырыла. Атап китергә мөмкин:
Логик-математик сара булараҡ алгоритмдарҙың төрҙәре кеше эшмәкәрлегенең күрһәтелгән компоненттарын һәм йүнәлештәрен сағылдыра, ә алгоритмдар үҙҙәре маҡсатҡа, мәсьәләнең башланғыс шарттарына, уны хәл итеү юлдарына бәйле. Ниндәйҙер кереү мәғлүмәттәрен сығыу мәғлүмәттәренә үҙгәртеүсе иҫәпләү характерындағы алгоритмдар (юғарыла телгә алынған Тьюринг, Пост, РАМ машиналары, Марковтың нормаль алгорифмдары һәм рекурсив функциялар тап шуларҙың формализацияһы булып торалар) һәм логик идара итеү алгоритмдары тип аталған интерактив алгоритмдар араһында принципиаль айырманы һыҙыҡ өҫтөнә алырға кәрәк (Тьюрингтың C-машинаһы барлыҡҡа килә, ингл. choice һүҙенән — һайлау, бөтә башланғыс мәғлүмәттәре иҫәпләү башланғансы уҡ бирелгән һәм сығыу мәғлүмәттәре иҫәпләү тамамланғансы билдәһеҙ булған классик A-машинанан айырмалы рәүештә, тышҡы тәьҫир көтә). Һуңғылары ниндәйҙер идара итеү объекты менән үҙ-ара тәьҫир итешеү өсөн һәм идара итеү объектынан килгән сигналдар сағылдырылған килеп тыуған хәлгә ҡарап дөрөҫ идара итеүсе йоғонто яһауҙы тәьмин итеү өсөн тәғәйенләнгәндәр[15][16]. Ҡайһы бер осраҡтарҙа идара итеү алгоритмы эштең тамамланыуын бөтөнләй күҙ уңында тотмай (мәҫәлән, ярашлы реакция бирелгән ваҡиғаларҙы көтөүҙең сикһеҙ циклын алып бара), шуға ҡарамаҫтан, тулыһынса дөрөҫ була.
Ошондай алгоритмдарҙы айырып күрһәтергә мөмкин:
Алгоритмдарҙы номерлау уларҙы тишереүҙә һәм анализлауҙа мөһим роль уйнай[18]. Теләһә ниндәй алгоритмды сикле һүҙ рәүешендә бирергә (ниндәйҙер алфавит символдарының сикле эҙмә-эҙлелеге рәүешендә күрһәтергә) мөмкин булғанлыҡтан, ә сикле алфавитта бөтә сикле һүҙҙәр күмәклеге иҫәпләмәле, бөтә алгоритмдар күмәклеге лә шулай уҡ иҫәпләмәле. Был бөтә натураль һандар күмәклеге һәм алгоритмдар күмәклеге араһында үҙ-ара бер ҡиммәтле сағылыш барлығын, йәғни һәр алгоритмға номер биреү мөмкинлеген аңлата.
Алгоритмдарҙы номерлау является бер үк ваҡытта бөтә алгоритм ярҙамында иҫәпләнмәле функцияларҙы ла номерлау булып тора, шуның менән бергә теләһә ниндәй функцияның сикһеҙ күп һанда номеры булырға мөмкин.
Номерлауҙы булдырыу алгоритмдар менән һандар менән эш иткән кеүек эшләргә мөмкинлек бирә. Номерлау бигерәк тә башҡа алгоритмдар менән эшләгән алгоритмдарҙы тикшергәндә файҙалы.
Евклид алгоритмы — иң ҙур уртаҡ бүлеүсене (ИҘУБ) иҫәпләүҙең эффектив ысулы. Грек математигы Евклид хөрмәтенә аталған; иң боронғо алгоритмдарҙың береһе, ул әле булһа ҡулланыла[19].
Евклидтың "Башланғыстар"ында (яҡынса б. э. т. 300 йыл), атап әйткәндә, VII һәм X китаптарында тасуирланған. Етенсе китабында бөтөн һандар өсөн, ә унынсы китабында — киҫек оҙонлоҡтары өсөн алгоритм.
Алгоритмдың бер нисә варианты бар, түбәндә псевдокодта яҙылған рекурсив варианты:
функция ИҘУБ(a, b) әгәр b = 0 әйләнеп ҡайтырға ә кире осраҡта әйләнеп ҡайтырға ИҘУБ (b, a mod b)
1599 һәм 650 һандарының ИҘУБ-ы:
Аҙым 1 | 1599 = 650*2 + 299 |
Аҙым 2 | 650 = 299*2 + 52 |
Аҙым 3 | 299 = 52*5 + 39 |
Аҙым 4 | 52 = 39*1 + 13 |
Аҙым 5 | 39 = 13*3 + 0 |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.