Алгоритм

Алгоритм
	Алгоритм
... хөрмәтенә аталган	Әл-Хәрәзми
Җитештерү ысулы	алгоритмизация[d]
Нинди вики-проектка керә	Проект:Мәгълүмати технологияләр[d] һәм Проект:Математика[d]
EntitySchema для класса	Lua хатасы: unknown error.
	Алгоритм Викиҗыентыкта

Алгори́тм, әл-Харәзми (фар. خوارزمی [al-Khwārazmī]) галиме исеменнән килеп чыккан, - ул мәсьәләне чишү нәтиҗәсенә чикләнгән вакыт кисәге эчендә ирешү өчен башкаручы гамәлләр тәртибен тасвирлаучы күрсәтмәләрнең (инструкцияләрнең) төгәл җыелмасы. Элекке аңлатуда “тәртип” сүзе урынына “бер-бер артлы килү” (последовательность) сүзе кулланылган, әмма компьютерлар эшендә параллельлек үсеше белән «бер-бер артлы килү” сүзен гомумирәк нәтиҗәгә ия “тәртип” сүзенә алмаштыра башлаганнар. Бу алгоритмның кайсыдыр күрсәтмәләренең (инструкцияләренең) эшенең башка күрсәтмәләргә (инструкцияләргә) яки аларның эшенең нәтиҗәләренә бәйле булырга мөмкинлегенә бәйле. Шулай итеп, кайбер күрсәтмәләр (инструкцияләр) мәҗбүри рәвештә үзләре шуларга бәйле булган күрсәтмәләр (инструкцияләр) эшенең ахырыннан соң үтәлергә тиеш. Бәйсез күрсәтмәләр (инструкцияләр) яки үзләре шуларга бәйле күрсәтмәләр (инструкцияләр) тәмамланганнан соң бәйсез булган күрсәтмәләр (инструкцияләр) кулланучы процессор һәм операцион система мөмкинчелек бирсә теләсә нинди тәртиптә, я параллель, я бер үк вакытта үтәлергә мөмкин.

Элек еш «алгорифм» дип язалар иде, хәзер мондый язылыш сирәк кулланыла, әмма, шулай да очрый (мәсәлән, Марковның нормаль алгорифмы).

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

Алгоритм төшенчәсе математиканың беренчел, төп, базис төшенчәләренә карый. Алгоритмик характерлы исәпләү процесслары (бөтен саннар белән арифметик гамәлләр, ике санның иң зур уртак тапкырлаучысын табу, һ.б.) кешелеккә бик борыңгы заманнардан ук билгеле. Әмма, ачык рәвешендә алгоритм төшенчәсе XX гасыр башында гына формалашкан.

Алгоритм аңлатмасының формализациясе 1928 елда Давид Гильберт формалаштырган чишелеш проблемасын (алман. Entscheidungsproblem) чишеп караулардан башланган. Формализациянең киләсе этаплары эффектив исәпләүләрне билгеләү өчен яки “эффектив методны” билгеләү өчен кирәк булган; мондый формализацияләр арасында - 1930, 1934 һәм 1935 елларда Гедель – Эрбран – Клининың рекурсив функцияләре, 1936 елда Алонзо Чёрчның λ-исәпләве, 1936 елда Эмиль Постның 1 формулировкасы һәм Тьюринг машинасы. Методологиядә алгоритм базис төшенчә булып тора һәм фараз ителгән абсолютка якынаю белән сыйфат ягыннан яңа оптимальлек төшенчәсенә ия була. Хәзерге дөньяда формализацияләнгән күрсәтүендә алгоритм мисалларда, охшашлык буенча чагыштырып өйрәнүнең нигезен тәшкил итә. Эшчәнлекнең төрле сфераларында алгоритмнар охшашлыгы нигезендә эксперт системалар (теориясе) концепциясе формалашкан.

Төшенчә тарихы

Алгоритмның хәзерге формаль билгеләмәсе Тьюринг, Пост, Чёрч (Чёрч — Тьюринг тезисы), Н. Винер, А. А. Марков эшләрендә XX гасырның 30-50 елларында бирелгән.

“Алгоритм” сүзе үзе фарсы галиме Абу Абдуллаһ Мөхәммәд ибн Муса әл-Хорезми ﺍﺑﻭﻋﺒﺩاﷲ ﻤﺤﻤﺪ ﺍﺑﻥ ﻤﻭﺳﻰ (Аль-Хорезми) исеменнән килеп чыккан. 825 ел тирәсендә ул инша язган, шунда ул Һиндстанда уйлап чыгарылган позицион унарлы исәпләү системасына беренче мәртәбә аңлатма биргән. Кызганычка каршы, китапның фарсыча беренче язылган нөсхәсе сакланып калмаган. Әл-Хорезми яңа системада исәпләү кагыйдәләрен формулаштырган, һәм, мөгаен, беренче мәртәбә санда төшерелдереп калдырылган позициясен билгеләү өчен 0 цифрасын кулланган (аның һиндча атамасын гарәпләр (الصفر) “as-sifr” яки фәкать (صفر ) “sifr” дип тәрҗемә иткәннәр, моннан “цифра” һәм “шифр” кебек сүзләр килеп чыккан). Шул ук вакыт тирәсендә һинд цифрларын башка гарәп галимнәре дә куллана башлаганнар. XII гасырның беренче яртысында аль-Хорезминың китабы латинча тәрҗемәсендә Европага үтеп кергән. Безнең вакытка кадәр исеме сакланып калмаган тәрҗемәче аңа Algoritmi de numero Indorum (“Һинд исәбе турында алгоритмнар”) атамасын биргән. Китапның гарәпчә атамасы “Китаб әл-җәбр уә-ль-мукабәлә” (“Кушу һәм алу турында китап”) булган. Китапның элекке атамасыннан алгебра сүзе килеп чыккан (алгебра – аль-җәбр – кушу).

Шулай итеп, Урта Азия галименең латинлаштырылган исеме китап башына куелганын күрәбез, һәм хәзер “алгоритм” сүзенең Европа телләренә нәкъ менә бу иншадан кергәне күренә. Әмма аның мәгънәсе турында сорау озак вакытлар буена аяусыз бәхәсләр китереп чыгарган. Күп гасырлар буена сүзнең килеп чыгышына бик төрле аңлатмалар бирелгән. Брокгауз һәм Ефронның энциклопедик сүзлеге үз аңлатмасын тәкъдим иткән. Анда “алгорифм” (сүз уңаеннан, инкыйлабка кадәр фита хәрефе аша алгориѳм язылышы кулланылган) “гарәп сүзе Аль-Горетм, ягъни, тамыр”дан чыгарыла. Әлбәттә, бу аңлатмаларны дөрес дип санау шөбһәле.

Әл-Хорезминың алдарак сүзгә алынган тәрҗемәсе беренче карлыгач булган һәм киләсе берничә йөз еллык дәвамында шул ук мәсьәләгә – цифрлар ярдәмендә исәп сәнгатенә багышланган булган күп яңа хезмәтләр дөнья күргән. Аларның барысының атамасында algoritmi яки algorismi булган.

Әл-Хорезми турында соңрак авторлар бернәрсә белмәгәннәр, әмма китапның беренче тәрҗемәсе «Dixit algorizmi: …» («Әл-Хорезми әйткән: …») дигән сүзләр белән башланган, һәм бу сүзне кәнкрит кеше исеме белән бәйләнгән булган.

Китапның грек чыганаклы булганы турында ялгышу киң таралган булган.

1250 ел тирәсендә инглиз астрономы һәм математигы Иоанн Сакробоско арифметика буенча Algorismus vulgaris хезмәтен язган, ул гасырлар буена унарлы исәпләү системасы буенча күп Европа университетларында төп дәреслек булган. Кереш сүздә Сакробоско фәннең авторы дип Алгус (Algus) дигән галимне атаган. Жана де Менның «Роза турында Роман»ында (1275—1280) “грек философы Алгус” Платон, Арсту (Аристотель), Евклид һәм Птолемей белән бер рәттән куела. Шулай ук исемнең Аргус (Argus) атамасы очраган. Гәрчә, борынгы грек мифологиясе буенча «Арго» корабын «Ясон» төзегән булса да, нәкъ менә шул Арго корабны төзегән дип әйтелгән.

«Мастер Алгус» (яки Аргус) урта гасыр әдәбиятында исәпләү сәнгатенең йөзе булган. Сүзгә алынган “Роза турында романда” һәм шулай ук итальян Дурантеның “Чәчәк” поэмасында фрагментларында хәтта «mestre Argus» та гашыйкларның ничә мәртәбә талашуын һәм татулашуын исәпли алмаганы турында сүзләр бар. Инглиз шагыйре Джефри Чосер «Герцогиня китабында» (1369 ел.), хәтта «данлы санаучы Аргус» (noble countour Argu) геройга төнге куркыныч төшләрендә күренгән куркыныч җанварларны исәпли алмавы турында яза.

Алгоритм – ул цифрлар ярдәмендә исәпләү сәнгате, әмма башта “цифр” сүзе нульгә генә караган. Мәшһүр француз трувер Готье де Куанси (Gautier de Coincy, 1177—1236) үзенең шигырьләрнең берсендә algorismus-cipher сүзләрен кулланган (алар 0 сүзен аңлаткан) бернәрсәгә дә яраклы булмаган кеше метафорасы буларак кулланган. Күренгәнчә, мондый образны аңлау өчен тыңлаучыларның билгеле әзерләвен таләп иткән, ә бу аларга яңа исәпләү системасы таныш булганын аңлата. Күп гасырлар буена абак фактик рәвештә исәпләүләр өчен бердәнбер эш коралы булган, аның белән сәүдәгәрләр дә, алмаштыручылар да, галимнәр дә кулланган. Хисап тактасында исәпләүләрнең отышлы якларын үзләрнең иншаларында Герберт Аврилактан (938-1003) кебек күренекле фикер иясе аңлаткан, ул аннан соң 999 нчы елда Сильвестр II исеме астында Рим папасы булган. Яңа әйбер шактый кыенлык белән танылган, математика тарихына алгорисмикларның һәм абацистларның (кайвакыт гербекистлар дип аталган) каты каршылыгы кергән, абацистлар исәпләүләр өчен гарәп цифрларына урынына абакны кулланырга чакырганнар. Кызыклы факт – француз математигы Николя Шюке (Nicolas Chuquet, 1445—1488) Лион шәһәренең салым түләүчеләр реестрына алгорисмик (algoriste) буларак кертелгән булган. Әмма яңа исәпләү ысулы ахыргача кулланыш тапканчы, гасырлар узган, гомуми билгеләмәләр ясау өчен, исәпләү методларын кәгазьдә язуга җайлаштыру һәм камилләштерү өчен шуның кадәр вакыт кирәк булган. Көнбатыш Европада арифметика укытучыларын XVII гасырга кадәр “абак магистрлары” дип атаганнар, мәсәлән, математик Никколо Тартальяны (1500—1557).

Шулай итеп, исәпләү сәнгате буенча иншалар “Алгоритмнар” дип атаганнар. Йөзләрчә иншалардан шигырь итеп язылган Александра де Вилла Деиның (Alexander de Villa Dei, 1240 елда үлгән) Carmen de Algorismo трактатын яки Вена астрономы һәм математигы Георг Пурбахның (Georg Peurbach, 1423—1461) Opus algorismi jocundissimi («Алгоритм буенча иң күңелле инша»)ны билгеләп үтәргә кирәк.

Тора бара сүзнең мәгънәсе киңәйгән. Галимнәр аны исәпләү өчен генә булганнарына түгел, ә башка математик процедураларга да куллана башлаганнар. Мәсәлән, 1360 нчы елда француз фәлсәфәчесе Николай Орем (Nicolaus Oresme, 1323/25-1382) Algorismus proportionum («Пропорцияләр исәпләве») математик трактатын язган, анда ул вакланмалы күрсәткечләр белән дәрәҗәләрне кулланган һәм фактик рәвештә логарифмнар фикеренә бик якын килгән. Абак урынына сызыкларда исәп килгәч, аның буенча күп санлы белешмә китапларын “Algorithmus linealis”, ягъни сызыкларда исәп кагыйдәләре дип атый башлаганнар.

Algorismi сүзенең беренчел формасы күпмедер вакыт узгач, соңгы хәрефен югалткан, ә сүзнең үзе Европа әйтелеше өчен җайлы algorism рәвешен алган. Соңрак, ул да, үз чиратында бозылышка дучар булган, бу arithmetic сүзенә бәйле булгандыр дип фараз ителә.

1684 елда Готфрид Лейбниц Nova Methodvs pro maximis et minimis, itemque tangentibus… иншасында «алгоритм» (Algorithmo) сүзен беренче мәртәбә киңрәк мәгънәдә кулланган: дифференциаль исәпләү мәсьәләләрнең систематик чишү ысулы буларак.

XVIII гасырда Германия математика сүзлекләрнең берсендә, (Лейпцигта 1747 елда басылган), Vollstandiges mathematisches Lexicon да, algorithmus төшенчәсе һаман дүрт арифметика операцияләре турында төшенчә буларак аңлатыла. Әмма мондый мәгънә бердәнбер булмаган, ул вакытларда математика фәненең терминологиясе формалашкан гына әле. Хосусый очракта, algorithmus infinitesimalis гыйбарәсе чиксез кечкенә зурлыклар белән гамәлләр башкару ысулларына кулланылган. Алгоритм сүзен Леонард Эйлер та кулланган, аның эшләрнең берсе шулай атала да - «Пелль мәсьәләсен чишү өчен яңа алгоритмны куллану» (De usu novi algorithmi in problemate Pelliano solvendo). Күргәнебезчә, Эйлерның алгоритмны мәсьәлә чишү ысулы синонимы буларак аңлавы хәзерге мәгънәгә бик якын.

Әмма сүзнең һәммә иске мәгънәләре дә кулланылыштан чыксын өчен тагын ике йөз ел кирәк булган. Бу процессны «алгоритм» сүзенең рус теленә үтеп керү мисалында тикшерергә була.

Тарихчылар «Счётная мудрость» атамасы астында борынгы рус дәреслеккә 1691 ел датасын бирәләр. Бу инша күп вариантларда билгеле (шуларның кайберләре 100 елга диярлек элегрәк) һәм тагын да борынгырак XVI гасыр борынгы кулъязмаларына карый. Алар буенча гарәп цифрларын һәм алар белән гамәлләр кагыйдәләрен белү Русь иленә ничек әкренләп таралганын карарга була. Бу дәреслекнең тулы атамасы - «Сия книга, глаголемая по еллински и по гречески арифметика, а по немецки алгоризма, а по русски цифирная счётная мудрость».

Шулай итеп, «алгоритм» сүзен беренче рус математиклары Көнбатыш Европада кебек үк мәгънәсендә аңлаганнар. Әмма бу төшенчә В. И. Даль сүзлегендә дә, йөз ел үткәч чыккан Д.Н. Ушаков мөхәррирлеге астында (1935 ел) «Толковый словарь русского языка» (Рус теленең аңлатмалы сүзлегендә дә) булмаган. Шулай да, “алгорифм” сүзен инкыйлабка кадәр популяр булган Бертуган Гранатларның энциклопедик сүзлегендә, 1926-нчы елда чыккан Зур совет энциклопедиясенең беренче басмасында да табарга була. Икесендә дә ул бертөрле аңлатыла: шул кагыйдә буенча унарлы исәпләү системасында дүрт арифметик гамәлләрнең тегесе яки бусы башкарыла торган кагыйдә. Әмма XX гасыр башына математиклар өчен “алгоритм” сүзе төгәл билгеләнгән кагыйдәләр буенча башкарылучы теләсә нинди арифметик яки алгебраик процессны аңлаткан, һәм бу аңлатма шулай ук БСЭ ның киләсе басмаларында бирелә.

Алгоритмнар галимнәрнең җентекле игътибар әйбере булган һәм тора бара бу аңлатма хәзерге математикада үзәк урыннарның берсен алган. Математикадан ерак булган кешеләр исә, XX гасырның кырыгынчы еллар башына алар бу сүзне мәктәптә укыганда, “Евклид алгоритмы” кушылмасында ишетә алганнар. Моңа да карамастан, алгоритм һаман белгечләр арасында йөри торган төшенчә буларак аңлашылган, моны туры килә торган мәкаләләрнең күләме кечкенәрәк булган басмаларда юклыктан әйтеп була. Хосусый очракта, ул бер томлы энциклопедик сүзлекләрдә генә түгел, ә ун томлы Кече Совет Энциклопедияда (1957 ел) юк. Әмма ун ел тирәсе узгач, Зур совет энциклопедиянең (1969 ел) өченче басмасында алгоритм инде “гадирәк аңлатмалар төшенчәләрендә формаль билгеләмәсе булмаган, һәм турыдан туры тәҗрибәдән абстракцияләнгән” төп математика категорияләрнең берсе итеп сыйфатлана. Күргәнебезчә, БСЭның беренче басмасындагы аңлатудан да аерма шактый зур. Кырык ел эчендә алгоритм математиканың төп төшенчәләрнең берсенә әверелгән, һәм моның тануы булып сүзне энциклопедияләргә түгел, ә сүзлекләргә кертү булган. Мәсәлән, ул академик “Рус теле сүзлеге”ндә (1981 ел) математика өлкәсеннән төшенчә буларак бар.

Алгоритм төшенчәсенең үсеше белән бер үк вакытта әкренләп аның математикадан башка сфераларга экспансиясе барган. Һәм аңа компьютерларның килеп чыгышы баш биргән, бу сәбәпле «алгоритм” сүзе 1985 елда бөтен мәктәп информатика дәреслекләренә кергән һәм яңа тормышка ия булган. Гомумән әйткәндә, хәзерге мәшһүрлеге турыдан туры компьютерларның таралышына бәйле.

Мәсәлән, “Балалар энциклопедиясе”нең өченче томында (1959 ел) исәпләү машиналары турында күп әйтелгән, әмма алар ниндидер гадәти әйбер булмаган һәм якты, әмма ерак киләчәкнең атрибуты буларак кабул ителә. Әмма үткән гасырның 70-нче елларында инде, компьютерлар экзотик могъҗиза булудан туктагач, «алгоритм” сүзе көнкүрешкә тиз керә. Моны энциклопедик басмалар сизгер фиксациялиләр. «Кибернетика энциклопедиясе»ндә (1974 ел) «Алгоритм» мәкаләсендә ул инде исәпләү машиналарда реализациягә бәйле, ә “Совет хәрби энциклопедиясе”ндә (1976 ел) “ЭВМ да мәсьәлә чишү алгоритмы” дигән аерым мәкалә барлыкка килә.

Соңгы бер ярым – ике ун еллыкта компьютер безнең тормышның аерылмый торган атрибуты булган, компьютер лексикасы гадәти булып киткән. “Алгоритм” сүзе безнең көннәрдә һәрбергә диярлек мәгълүмдер. Ул сөйләм телендә дә кулланыла.

Алгоритм билгеләмәләре

Формаль булмаган билгеләмә

Һәрбер алгоритм башлангыч (керү) бирелгән мәгълүматларның барлыгын фараз итә һәм эш нәтиҗәсендә билгеле нәтиҗәгә ирешүгә китерә. Һәрбер алгоритмның эше ниндидер элементар гамәлләр бер-бер артлы килүен башкару ысулы белән бара. Бу гамәлләр адымнар дип атала, ә аларны үтәү процессы алгоритмик процесс дип атала. Шулай итеп, алгоритмның дискретлыгы үзлеге ачык күренә. Алгоритмнарның мөһим үзлеге булып массалык тора, ягъни төрле керү мәгълүматларга куллану мөмкинлеге тора. Ягъни, һәрбер алгоритм бер типлы мәсьәләләр төркемен чишәргә тиеш.

Алгоритм шуңа канәгатьләндерә торган кирәк шарт булып детерминирлык яки билгелелек булып тора. Ягъни, алгоритмның командаларының үтәлүе бер өлге буенча бара һәм бер төрле керү мәгълүматлары өчен бер үк нәтиҗәгә китерә. Алгоритмның керү мәгълүматлары рөхсәт ителгән керү мәгълүматлары җыелмасы белән чикләнгән булырга мөмкин. Алгоритмны рөхсәт ителмәгән керү мәгълүматларына куллану алгоритмның бер кайчан да туктамавына яки чыга алмаслык халәткә (һавада асылынып тору)га эләгүенә китерергә мөмкин.

Формаль билгеләмәсе

Математиканың төрле теоретик проблемалары һәм физика һәм техниканың үсеше тизләнеше көн үзәгенә алгоритм төшенчәсенең төгәл билгеләүне куйган.

Алгоритм төшенчәсен беренче төгәлләп караулар һәм аны тикшерүләрне XX гасыр башында Алан Тьюринг, Эмиль Пост, Жак Эрбран, Курт Гедель, Андрей Марков, Алонзо Чёрч башкарганнар. Алгоритм төшенчәсенең берничә билгеләмәсе эшләнгән булган, әмма соңыннан алар барысы да бер үк төшенчәне аңлатканы ачыкланган. (Чёрч — Тьюринг Тезисын карагыз).

Тьюринг Машинасы

Тьюринг машинасы нигезендә ятучы төп фикер бик гади. Тьюринг Машинасы – ул эченә символлар язылган аерым күзәнәкләр тасмасы белән эшләүче абстракт машина (автомат). Машинаның язу өчен һәм күзәнәкләрдән символларны уку өчен башы бар, һәм ул тасма буенча хәрәкәтләнә ала. Һәрбер адымда машина баш күрсәтә торган күзәнәктән символны укый һәм укылган символ һәм эчке халәте нигезендә киләсе адымны ясый. Шуның белән бер рәттән машина үз халәтен үзгәртә ала, күзәнәккә башка символны яза ала яки башны бер күзәнәккә уңга яки сулга күчерә ала.

Бу машиналарны тикшерү нигезендә Тьюринг тезисы чыгарылган (алгоритмнарның төп гипотезасы):

Ниндидер әлифбада бирелгән функциянең зурлыкларын табу өчен ниндидер алгоритм бу функция Тьюринг буенча исәпләнгәндә генә, ягъни аны Тьюринг машинасы ярдәмендә исәпләп булганда гына бар.

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

Рекурсив функцияләр

Һәрбер алгоритмга ул исәпли торган функцияне туры китерергә мөмкин. Әмма шундый сорау туа: теләсә нинди функциягә Тьюринг машинасын туры китерергә буламы, ә булмаса, нинди функцияләр өчен алгоритм бар? Бу сорауларны тикшерүләр 1930-нчы елларда рекурсив функцияләр теориясе барлыкка килүгә китергән.

Исәпләнүче функцияләр классы аксиомалар системасы нигезендә ниндидер аксиоматик теория төзелүен хәтерләтүче образга язылган. Башта исәпләве ачык күренә торган иң гади функцияләр сайланган булган. Аннан соң инде булган функцияләр нигезендә яңа функцияләр төзү кагыйдәләре (операторлар) формулаштырылган. Кирәк булган функцияләр классы иң гади функцияләрдән операторлар ярдәмендә чыгарып була торган функцияләрдән тора.

Тьюринг тезисына охшаш рәвештә исәпләү функцияләре теориясендә “Чёрч тезисы” дип аталган гипотеза куелган:

Санлы функция шул очракта һәм бары тик шул очракта алгоритмик рәвештә исәпләнә – ул өлешчә рекурсив булган очракта. Исәпләнүче функцияләр классы Тьюринг буенча исәпләнүчеләр белән тәңгәл килү ике адымда исбатлана: башта иң гади функцияләрнең Тьюринг машинасында исәпләнүне исбатлыйлар, аннан соң операторлар ярдәмендә чыгарылган функцияләрне испләнүне исбатлыйлар. Шулай итеп формаль булмаган рәвештә алгоритмны дискрет детерминирланган процессны төгәл инструкцияләр (бирелмәләр) системасы буларак билгеләргә мөмкин. Ул башлангыч мәгълүматлардан (керүдә) эзләнелгән нәтиҗәгә (чыгуда) алып бара, әгәр дә ул нәтиҗә чикле адым эчендә бар икән; әгәр дә эзләнүче нәтиҗә юк икән, алгоритм я бер кайчан да эшен тәмамламый, я чыгусыз халәткә керә.

Марковның нормаль алгоритмы

Марковның нормаль алгоритмы – ул бер-бер артлы килүче алыштырулар системасы, бу алыштырулар ниндидер әлифба символларыннан төзелгән нигез сүзләрдән яңа сүзләрне чыгаручы билгеле процедураларны чынлыкка ашыра. Тьюринг машинасы кебек үк, “нормаль алгоритмлар” исәпләүләрнең үзләрен башкармыйлар: алар фәкать бирелгән кагыйдәләр буенча хәрефләр алыштыру ысулы белән сүзләрне әверелдерүне башкаралар.

“Нормаль исәпләнүче” дип нормаль алгоритм ярдәмендә башкарырга мөмкин булган функцияне атыйлар. Ягъни, функциянең рөхсәт ителгән мәгълүматлар күплегеннән һәрбер сүзне аның башлангыч мәгънәсенә әверелдерүче алгоритм ярдәмендә.

Нормаль алгоритмнар теориясен уйлап табучысы А.А. Марков Марковның нормализация принцибы дип аталган гипотезаны куйган:

Ниндидер әлифбада бирелгән функциянең мәгънәләрен табу өчен, алгоритм шул вакытта һәм бары тик шул вакытта бар – функция нормаль исәпләнүче булганда.

Тьюринг һәм Черч тезисларына охшаш рәвештә, Марковның нормализация принцибы математик ысуллар белән исбатлана алмый.

Стохастик алгоритмнар

Әмма, өстәрәк китерелгән алгоритмның формаль билгеләмәсе кайбер очракларда артык төгәл булырга мөмкин. Кайвакыт очраклы зурлыкларны куллануда ихтыяҗ килеп чыгарга мөмкин.

«Probabilistic algorithms should not be mistaken with methods (which I refuse to call algorithms), which produce a result which has a high probability of being correct. It is essential that an algorithm produces correct results (discounting human or computer errors), even if this happens after a very long time.» Henri Cohen, A Course in Computational Algebraic Number Theory.

Эше башлангыч бирелгән мәгълүматлар белән генә түгел, ә очраклы саннар генераторыннан чыгарылган мәгънәләр белән билгеләнүче алгоритм “стохастик” дип атала (яки ингл. randomized algorithm дан алынган сүз рандомизирланган дип атала)

Формаль рәвештә мондый алгоритмнарны алгоритмнар дип атарга ярамый, чөнки алар туктамас дигән (нульгә якын булган) ихтималлылык бар. Әмма стохастик алгоритмнар еш кына детеминирланганнардан эффективрак була, ә кайбер очракларда мәсьәләне чишәргә бердәнбер ысул булып тора.

Әмма стохастик алгоритмнарны һәм зур ихтималлылык белән дөрес нәтиҗәне бирә торган методларны аерырга кирәк. Методтан аермалы буларак, алгоритм озак дәвам иткән эштән соң да коррект нәтиҗәләр бирә. Кайбер тикшеренүчеләр стохастик алгоритм алдан билгеле булган ихтималлылык белән дөрес булмаган нәтиҗә бирер дигән ихтималлылыкны кабул итә. Шул чакта, стохастик алгоритмнарны ике типка бүләргә була:

Лас-Вегас тибы алгоритмнары гел коррект нәтиҗә бирәләр, әмма аларның эш вакыты чикләнгән
Монте-Карло тибы алгоритмнары өстәгеләрдән аермалы буларак билгеле ихтималлылык белән дөрес булмаган нәтиҗәләр бирергә мөмкин (аларны еш Монте-Карло методлары дип атыйлар).

Башка формализацияләр

Кайбер мәсьәләләр өчен өстәрәк атап әйтелгән формализацияләр чишелешләр эзләүне һәм тикшерүләр башкаруны авырайтырга мөмкин. Киртәләрне узу өчен “классик” схемаларның модификацияләре дә, алгоритмның яңа модельләре дә барлыкка килгән.

ахыр һәм күзәнәк автоматлар

Һәм башкалар.

Алгоритмнарның формаль үзлекләре

Алгоритмның ачык күренгән яки ачык күренмәгән формада билгеләмәләре түбәндәге гомуми таләпләр рәтендә бар:

Дискретлык — алгоритм мәсьәлә чишү процессын ниндидер гади адымнар тәртибе рәвешендә күрсәтергә тиеш. Шул ук вакытта һәрбер адымның алгоритмын үтәү өчен чикле вакыт кисәге кирәк, ягъни башлангыч бирелгән мәгълүматларны нәтиҗәгә әверелдерү вакыт буенча дискрет рәвештә башкарыла.
Детерминирланган булу (билгелелек). Һәрбер вакыт мизгелендә киләсе эш адымы бердәнбер итеп система халәте белән билгеләнә. Шулай итеп, бер үк башлангыч бирелгән мәгълүматлар өчен алгоритм бер үк нәтиҗәне (җавапны) бирә. Хәзерге заман аңлатуында бер үк алгоритмның төрле реализацияләрнең изоморф граф булырга тиеш. Икенче яктан, киләсе эш адымы агымдагы система халәтенә һәм генерацияләнгән очраклы санга бәйле булган ихтималлылык алгоритмнары бар. Әмма башлангыч “бирелгән мәгълүматлар” исемлегенә очраклы саннар генерациясе методын керткәндә, ихтималлылыклы алгоритм гади алгоритмның астөре була башлый.
Аңлашылучанлык — башкаручы өчен алгоритмда фәкать анда булган һәм аның командалар системасына керә торган командалар булырга тиеш.
Тәмамланучанлык (чиклелек) — коррект бирелгән керү бирелгән мәгълүматлары булганда алгоритм чикле сан адымнар эчендә эшне тәмамларга һәм нәтиҗәне бирергә тиеш. Икенче яктан, ихтималлылыклы алгоритм беркайчан да нәтиҗә бирмәскә мөмкин, әмма моның ихтималлылыгы нульгә тигез.
Массалылык (универсальлек). Алгоритм төрле җыелма башлангыч бирелгән мәгълүматлар кулланырлык булырга тиеш.
Нәтиҗәлелек — алгоритмның билгеле нәтиҗәләр белән тәмамлануы.
Алгоритм дөрес булмаган нәтиҗәләргә китерсә, яки бөтенләй нәтиҗә бирмәсә ялгыш алгоритм була.
Алгоритм теләсә нинди керү бирелгән мәгълүматлар өчен дөрес нәтиҗәләр бирсә хатасыз була.

Алгоритм төрләре

Берәр кулланылыш өчен алгоритмнар аерым роль уйныйлар, алар аерым кулланылыш мәсьәләләр чишү максатлы. Алгоритм мәсьәләнең таләпләренә туры килсә (мәсәлән, физик дөрес нәтиҗә бирсә) дөрес булып санала. Алгоритмда (программада) кайбер башлангыч бирелгән мәгълүматлар өчен дөрес булмаган нәтиҗәләр, эш бозылулар, баш тартулар, я бөтенләй бернинди нәтиҗәләр бирмәсә хаталар бар дип санала. Соңгы тезис алгоритмик программалау буенча олимпиадаларда катнашучылар төзегән программаларга бәя бирү өчен кулланыла.

рекурсив алгоритмнар (ниндидер кайтару шартына ирешкәнче үзләре үзен чакыручы алгоритмнар) мөһим роль уйныйлар. XX гасыр ахырыннан – XXI гасыр башыннан алып берничә операцияне бер үк вакытта башкарырга сәләтле исәпләү машиналары өчен булган параллель алгоритмнар актив уйлап эшләнә.

Алгоритмнарның нумерациясе

Алгоритмнарның нумерациясе аларның тикшерүендә һәм анализында мөһим роль уйный.

Теләсә нинди алгоритмны чикле сүз рәвешендә бирергә мөмкин булганлыктан (ниндидер әлифбаның чикле символлары бер-бер артлы килүе рәвешендә күрсәтергә), ә чикле әлифбада бөтен чикле сүзләр күплеге санаулы булганлыктан, бөтен алгоритмнар күплеге шулай ук санаулы. Бу натураль саннар күплеге белән алгоритмнар күплеге арасында бердәнбер чагылуын аңлата, ягъни һәрбер алгоритмга номер бирү мөмкинлеген аңлата.

Алгоритмнарның нумерациясе шулай ук барлык алгоритмик исәпләнүче функцияләрне аңлата, һәм шулай ук теләсә нинди функция чиксез номерлар микъдарына ия булырга мөмкин.

Нумерациянең булуы алгоритмнар белән саннар белән кебек үк эшләргә рөхсәт итә. Бигрәк тә башка алгоритмнар белән эш итә торган алгоритмнарны тикшергәндә нумерация файдалы.

Алгоритмнар ярдәмендә чишелми торган мәсьәләләр

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

$f$ функциясен функция билгеләмәсенең бөтен элементлар күплегенең мәгънәсен $f$ исәпли торган Тьюринг машинасы булса исәпләнүче функция дип атыйлар. Әгәр дә андый машина юк икән, $f$ функциясе исәпләнмәүче дип атала. Функция хәтта керү мәгълүматларның бөтен күплегенең аскүплеге өчен мәгънәне исәпли ала торган Тьюринг машинасы булса да исәпләнмәүче функция дип саналачак. Peter Linz, An Introduction to Formal Languages and Automata $f$ функциясенең исәпләү нәтиҗәсе “хакыйкать” яки “ялган” мантыйк гыйбарәсе (яки {0, 1} күплеге) булганда очрак $f$ функциясенең исәпләнүенә карап чишелә торган яки чишелми торган мәсьәлә дип атала. Керү мәгълүматларның рөхсәт ителгән күплеген төгәл күрсәтергә мөмкин, чөнки мәсьәлә бер күплек өчен чишелә торган икенче күплек өчен чишелми торган булырга мөмкин.

Чишелмәве исбатланган беренче мәсьәлә булып тукталу проблемасы тора. Ул түбәндәгечә формулаштырыла:

Тьюринг машинасы өчен программа тасвирламасы булганда, ниндидер керү бирелгән мәгълүматлары алып, программа вакыт узу белән эшен тәмамлаячакмы, әллә чиксез эшләячәкме икәнен билгеләргә мөмкин.

Тукталу проблемасының чишелмәве исбатлавы, аңа башка мәсьәләләрне китерергә булуы белән мөһим. Мәсәлән, буш юлда тукталу проблемасын (бирелгән Тьюринг машинасы өчен буш юлда хәрәкәткә китерелеп туктармы икәнен билгеләргә кирәк булганда) үзгәртеп гади мәсьәлә тукталуына китерергә мөмкин, шуның белән аның чишелмәве исбатлана.

Алгоритмнар анализы

Корректлылык исбатлавы

Мәгълүмат технологияләре таралышы белән программа эш бозылулары куркынычы артты. Алгоритмнарда һәм реализацияләрдә хаталардан арынуның бер ысулы булып системалар корректлылыгының математик ысуллар белән исбатлау тора.

Алгоритмнар һәм аларның реализацияләрнең анализы өчен математик аппаратны куллану формаль методлар дип атала. Формаль методлар формаль спецификацияләр куллануны һәм, гадәттә, синтаксик анализ һәм спецификацияләр үзлекләрен исбатлау өчен эш кораллары җыелмасы булуын истә тота. Реализация детальләреннән абстрактлашу система үзлекләрен аның реализациясенә бәйсез рәвештә билгеләргә мөмкинчелек бирә. Моннан тыш, математик раслауларының төгәллеге һәм бердәнбер мәгънәгә ия булулары табигый телләрнең күпмәгънәлелектән һәм төгәлсезлектән арынырга мөмкинчелек бирә.

Ричард Гейтс гипотезасы буенча, “хаталардан алдан арыну хаталарны төзәтүдән яхшырак”. Хоар гипотезасы буенча, “программаларны исбатлау корректлык, документация һәм ярашучанлык (совместимость) программасын чишә». Программалар корректлылыкның исбатлавы аларның бөтен керү бирелгән мәгълүматлар диапазонына карата үзлекләрен ачыкларга мөмкинчелек бирә. Моның өчен корректлылык төшенчәсе ике типка бүленгән булган:

Өлешчә корректлылык — программа тәмамланган очраклары өчен дөрес нәтиҗә бирә.
Тулы корректлылык — программа эшне тәмамлый һәм керү бирелгән мәгълүматлары дипазоныннан бөтен элементлар өчен дөрес нәтиҗәне бирә.

Корректлылыкны исбатлау вакытында программа текстын теләнгән керү-чыгу бирелгән мәгълүматлары нисбәте спецификациясе белән чагыштыралар. Хоар типы исбатлаулары өчен бу спецификация алшартлар һәм постшартлар дип аталучы расламалар рәвешендә була. Программаның үзе белән бергә аларны шулай ук Хоар өчлеге дип атыйлар. Бу расламалар түбәндәгечә языла:

P{Q}R

Монда P - Q программасы эш башының алдыннан башкарылырга тиеш алшарт, ә R – программа эшенең тәмамыннан соң дөрес булган постшарт. Формаль методлар киң даирә мәсьәләләр өчен уңышлы кулланылган, ә хосусый очракларда: электрон схемалар, ясалма интеллект, тимер юлда автоматик системалар эшләгәндә, микропроцессорлар верификациясендә, стандартлар спецификациясендә, программалар спецификациясе һәм верификациясендә.

Эш вакыты

Киң таралган алгоритмнарнарга бәя бирү критерие булып эш вакыты һәм керү бирелгән мәгълүматлары күләменә бәйле эш вакыты үсү тәртибе тора.

Һәрбер кәнкрит мәсьәлә өчен аның үлчәме дип аталган ниндидер сан төзиләр. Мәсәлән, матрицалар тапкырламасын исәпләү мәсьәләсенең үлчәме булып тапкырлаучы матрицаларның иң зур үлчәме торырга мөмкин, графларда мәсьәләләр өчен үлчәм булып графның кабыргалары микъдары торырга мөмкин.

Алгоритм мәсьәлә үлчәме $n$ функциясе буларак сарыф иткән вакытны бу алгоритмның вакытлы катлаулыгы T(n) дип атыйлар. Мәсьәлә үлчәме артканда бу функция тотышының асимптотикасын асимптотик вакытлы катлаулылык дип атыйлар, ә аның билгеләнүе өчен махсус нотация («O»зур һәм «o» кече) кулланыла. Нәкъ менә асимптотик катлаулылык алгоритм эшкәртә алган мәсьәләләрнең үлчәмен билгели. Мәсәлән, әгәр дә алгоритм $n$ үлчәмле керү бирелгән мәгълүматларын cn² вакыты эчендә эшкәрткәндә, монда c – ниндидер константа, мондый алгоритмның вакытлы катлаулыгы O(n²) дип атала.

Еш кына алгоритмнарны эшләп чыгарганда иң начар очраклар өчен асимптотик вакытлы катлаулылыкны киметеп карыйлар. Гамәлдә исә “гадәттә” еш эшли торган алгоритм җитәрлек була.

Тупасландырып әйткәндә, урта асимптотик вакытлы катлаулылыгын ике типка бүләргә була: аналитик һәм статистик. Аналитик метод төгәлрәк нәтиҗәләр бирә, әмма гамәлдә кулланырга катлаулы. Аның каравы статистик метод катлаулы мәсьәләрнең анализын тиз башкарырга мөмкинчелек бирә.

Түбәндәге таблицада коментарийлар белән киң таралган асимптотик катлаулылыклар китерелгән:

Катлаулылык	Комментарий	Мисаллар
O(1)	Тотрыклы эш вакыты мәсьәләнең үлчәменә бәйле түгел	Хеш-таблицада көтелгән эзләү вакыты
O(loglogn)	Кирәк булган вакытның бик әкрен үсеше	n элементларны интерполяцияләнгән эзләүнең көтелгән вакыты
O(logn)	Логарифмик үсеш —мәсьәләнең үлчәмен икеләтү эш вакытын даими зурлыкка арттыра	xⁿны исәпләү; n элементлардан торган массивта икеле эзләү (бинар эзләү)
O(n)	Сызыкча үсеш — мәсьәләнең үлчәмен икеләтү кирәк булган вакытны да икеләтә	n цифрдан саннарны кушу/алу; n элементтан торган массивта сызыкча эзләү
O(nlogn)	Линеаритмик үсеш — мәсьәләнең үлчәмен икәләтү кирәк булган вакытны ике мәртәбәдән бераз артыграк зурлыкка арттыра	Бергә кушылу белән сортировка яки n элементлар өеме белән сортировка; сортировканың түбәндәге чиге n элементларны чагыштыру белән
O(n²)	Квадратик үсеш — мәсьәләнең үлчәмен икеләтү кирәк булган вакытны дүрт мәртәбә арттыра	Элементар сортировка алгоритмнары
O(n³)	Кубик үсеш — мәсьәлә үлчәмен икеләтү кирәк булган вакытны сигез мәртәбә арттыра	Гади матрицалар тапкырлавы
O(cⁿ)	Экспоненциаль үсеш — мәсьәлә үлчәмен 1 гә арттыру кирәк булган вакытның c-мәртәбә артуына китерә; мәсьәлә үлчәменең икеләтә артуы кирәк булган вакытны квадратка арттыра	Кайбер коммивояжёр мәсьәләләре, тулы сынап карау ярдәме белән эзләү алгоритмнары

Башлангыч бирелгән мәгълүматлар һәм ниндидер нәтиҗә булуы

Алгоритм – ул төгәл билгеләнгән күрсәтмә (инструкция), аны бер-бер артлы башлангыч бирелгән мәгълүматларга кулланып мәсьәләнең чишелешен табарга була. Һәрбер алгоритм өчен башлангыч бирелгән мәгълүматлар рәвешендә рөхсәт ителгән ниндидер объектлар күплеге. Мәсәлән, матди саннарны (вещественные числа) бүлү алгоритмында бүленүче сан теләсә нинди булырга мөмкин, ә бүлүче нульгә тигез булырга тиеш түгел.

Кагыйдә буларак, алгоритм ниндидер бер мәсьәләне чишү өчен түгел, ә ниндидер класс мәсьәләләр чишү өчен хезмәт итә. Мәсәлән, кушу алгоритмы теләсә нинди пар натураль саннар өчен кулланылырга мөмкин. Монда аның массалыгы, ягъни алгоритмны бер классның теләсә нинди мәсьәләсе өчен күп мәртәбә куллану мөмкинчелеге үзлеге чагыла.

Алгоритмнарны эшләү өчен “алгоритмизация” кулланыла – бу куелган кулланылыш мәсьәләләрне чишү өчен систематик алгоритмнар төзү процессы. Алгоритмизация программаларны эшләү һәм электрон хисаплау машинасында чишү процессында мәҗбүри этап булып исәпләнә. Нәкъ менә кулланылыш алгоритмнары һәм программалар өчен принципиаль рәвештә детеминирлаганлык, нәтиҗәлелек һәм массалык һәм шулай ук куелган мәсьәләләрнең чишелеше нәтиҗәләре дөреслеге принципиаль рәвештә әһәмиятле.

Алгоритм – ул максатны ирешү өчен гамәлләр тәртибен башкарып кылырга аңлаешлы һәм төгәл күрсәтмә.

Алгоритмнарның күрсәтелеше

Алгоритм язылышының формалары:

сүзләр ярдәмендә яки вербаль (тел, формула-сүз рәвешендә);
псевдокод (формаль алгоритмик телләр);
схематик:
- структурограммалар (Насси-Шнайдерман схемалары);
- график (блок-схема, стандарт таләпләренә туры китереп башкарыла).

Гадәттә (фикер дәрәҗәсендә алгоритм сүзләр белән тасвирлана, ләкин реализациягә якынаю белән ул формальрәк рәвешкә керә һәм башкаручыга аңлаешлырак телдә формулировкага ия була (мәсәлән, машина коды).

Алгоритмнарның эффективлыгы

Гәрчә алгоритм билгеләвендә нәтиҗәгә ирешү өчен фәкать адымнар санының чиклелеге таләп ителсә дә, гамәлдә миллиард булса да адымнарны башкару бик озак вакыт булып тора. Шулай ук башка чикләүләр дә бар (мәсәлән программа зурлыгына, рөхсәт ителгән гамәлләргә). Моның белән бәйле рәвештә алгоритм катлаулыгы кебек төшенчәләрне кертәләр (вакыт буенча, программаның зурлыгы буенча, исәпләү катлаулыгы һ.б.). Һәрбер мәсьәлә өчен максатка китерә торган күп алгоритмнар булырга мөмкин. Алгоритмнарның эффективлыгын арттыру хәзерге заман информатиканың мәсьәләләрнең берсе булып тора. XX гасырның 50-нче елларында хәтта аның бер өлкәсе - тиз алгоритмнар барлыкка килгән. Хосусый очракта, балачактан да бөтен кеше белгән унарлы саннарны тапкырлау мәсьәләсендә асимптотик мәгънәдә тапкырлама табуны шактый тизләтергә мөмкинчелек бирүче алгоритмнар рәте табылган. Тиз тапкырлауны карагыз.

Ачык мисал булып $\pi$ санын исәпләү өчен Чудновский алгоритмы тора.

Мисал

Мисал итеп Евклид алгоритмын китерергә була. Евклид алгоритмы - иң зур уртак бүлүчене эффектив исәпләү методы. (ИЗУБ). Грек математикы Евклид хөрмәтенә аталган, хәзерге заманга кадәр кулланыла торган иң борынгы алгоритмнарның берсе. Knuth D, The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Бу алгоритм Евклидның “Башлангычларында” (безнең эрага кадәр якынча 300-енче елда язылган), ә атап ук әйткәндә VII һәм X китапларда. Җиденче китапта бөтен саннар өчен алгоритм тасвирланган, унынчы китапта – кисемтәләр озынлыгы өчен. Алгоритмның берничә вариантлары бар, түбәндә китерелгәне псевдокодта язылган рекурсив вариант:

функция нод(a, b)
    если b = 0
       возврат a
    иначе
       возврат нод(b, a mod b)

функция изуб(a, b)
    әгәр b = 0
       кайтару a
    яисә
       кайтару изуб(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

Cи программалау телендә ике натураль санның иң зур уртак бүлүчесен табу программасы

/*greatest common divisor*/

int greatest_common_divisor (int a, int b) 
{
  if (b == 0)
  {
    return a;
  }
  return greatest_common_divisor (b, a % b);
}

int main ()
{
  int a, b;
  printf ("Ике натураль санның иң зур уртак бүлүчесен\n");
  printf ("табу программасы\n");
  printf ("А һәм В саннарын кертегез\n");
  scanf ("%d%d", &a, &b);
  printf ("A = %d B = %d и.з.у.б (А, В) = %d",
         a, b, greatest_common_divisor (a, b));
}

Программаның эшләү нәтиҗәсе:
Ике натураль санның иң зур уртак бүлүчесен
табу программасы
А һәм В саннарын кертегез
1024 192
A = 1024 B = 192 и.з.у.б (А, В) = 64

Искәрмәләр

Шулай ук карагыз

Әдәбият

Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн, Алгоритмы: построение и анализ
Дональд Кнут, Искусство программирования, том 1. Основные алгоритмы
Порублев Илья Николаевич, Ставровский Андрей Борисович, Алгоритмы и программы. Решение олимпиадных задач
Пшеничный П.В., Тагиров Р.Р, Примеры программ на языке СИ, Часть 2, СП «Диалог», Набережные Челны, Казань, 1990

Сылтамалар

«Слово „алгоритм“: происхождение и развитие», В. В. Шилов,
Журнал «Потенциал» — источник исторических сведений.
Алгоритмы, методы, исходники — сайт по алгоритмам и методам программирования
Дискретная математика: Алгоритмы 2006 елның 4 июль көнендә архивланган. — список алгоритмов
Юрий Лифшиц. Курс лекций Алгоритмы для Интернета
Геометрические алгоритмы
о Алгоритме в энциклопедии «Кругосвет»
Статьи по алгоритмам из научных библиотек
Сборник алгоритмов на сайте e-maxx.ru

Сүзлекләр һәм энциклопедияләр	Зур каталон · Брокгаузның һәм Ефронның · Кечкенә Брокгаузның һәм Ефронның · Британника (онлайн)
Норматив контроль	BNE: XX527980 · BNF: 119358199 · GND: 4001183-5 · LCCN: sh85003487 · LNB: 000052282 · NDL: 00560337 · NKC: ph114026