АЛГОРИ́ТМ

АЛГОРИ́ТМ (от al­go­rithmi – лат. на­пи­сания араб. име­ни аль-Хо­рез­ми), ин­струк­ция, точ­ное опи­са­ние спо­со­ба дей­ст­вия с ис­поль­зо­ва­ни­ем про­стых, об­ще­по­нят­ных эле­мен­тов (напр., опе­ра­ций). В ма­те­ма­ти­ке по­ня­тие А. су­жа­ет­ся и уточ­ня­ет­ся сле­дую­щим об­ра­зом. Дей­ст­вие со­сто­ит в по­сле­до­ва­тель­но­сти пе­ре­хо­дов от од­но­го со­стоя­ния вы­чис­ле­ния (про­цес­са ра­бо­ты А.) к дру­го­му; со­стояния – это кон­ст­рук­тив­ные объ­ек­ты (напр., сло­ва в дан­ном ал­фа­ви­те; в ча­ст­но­сти, це­лые чис­ла в де­ся­тич­ной или дво­ич­ной за­пи­си). А. так­же яв­ля­ет­ся кон­ст­рук­тив­ным объ­ек­том. Пер­вое со­стоя­ние на­зы­ва­ет­ся ис­ход­ным дан­ным, по­след­нее – ре­зуль­та­том ра­бо­ты А. Фик­си­ро­ван­ный А. мож­но при­ме­нять к разл. ис­ход­ным дан­ным; для не­ко­то­рых он мо­жет не за­кан­чи­вать ра­бо­ту. Тем са­мым А. за­да­ёт (воз­мож­но, не всю­ду оп­ре­де­лён­ную) функ­цию, вы­чис­ляе­мую этим А. Та­кие функ­ции на­зы­ва­ют­ся вы­чис­ли­мы­ми. По­ня­тия А. и вы­чис­ли­мой функ­ции от­но­сят­ся к ис­ход­ным по­ня­ти­ям ма­те­ма­ти­ки и че­рез дру­гие по­ня­тия не вы­ра­жа­ют­ся. Рас­смат­ри­ва­ют­ся рас­ши­ре­ния по­ня­тия А., напр. ве­ро­ят­но­ст­ные А., т. н. А. с ора­ку­лом, А. взаи­модей­ст­вия с ок­ру­жаю­щей сре­дой, па­рал­лель­ные А. Час­то А. оп­ре­де­ля­ет­ся с по­мо­щью аб­ст­ракт­ной вы­чис­ли­тель­ной ма­ши­ны, по­лу­чаю­щей на вход про­грам­му дей­ст­вия и ис­ход­ное дан­ное.

До кон. 19 в. А. – об­щее по­ня­тие, от­но­ся­щее­ся к из­вест­ным А. та­ким, как А. вы­пол­не­ния ариф­ме­тич. опе­ра­ций в де­ся­тич­ной сис­те­ме счис­ле­ния, А. диф­фе­рен­ци­ро­ва­ния функ­ций, А. Евк­ли­да на­хо­ж­де­ния об­щей ме­ры от­рез­ков или наи­боль­ше­го об­ще­го де­ли­те­ля мно­го­чле­нов. В 1900–10-х гг. бы­ли осоз­на­ны труд­но­сти в по­строе­нии об­ще­го А. ре­ше­ния не­ко­то­рых мас­со­вых про­блем. В 1930-е гг. пред­ло­же­ны ма­те­ма­тич. оп­ре­де­ле­ния по­ня­тия вы­чис­ли­мой функ­ции, ис­хо­дя­щие из пред­став­ле­ний о том, что мо­жет де­лать че­ло­век-вы­чис­ли­тель; сре­ди них – по­ня­тие ре­кур­сив­ной функ­ции и по­ня­тие функ­ции, вы­чис­ли­мой ма­ши­ной Тью­рин­га. То­гда же бы­ла до­ка­за­на эк­ви­ва­лент­ность разл. по­ня­тий вы­чис­ли­мой функ­ции и клас­сов вы­чи­сли­мых фун­к­ций, по­рож­да­е­мых эти­ми по­ня­ти­я­ми; сфор­му­ли­ро­ван т. н. те­зис Чёр­ча, при­ня­тый в ка­че­ст­ве ес­теств.-на­уч. фак­та: класс вы­чис­ли­мых функ­ций сов­па­да­ет с лю­бым из упо­мя­ну­тых вы­ше клас­сов. Раз­ви­тие ком­пь­ю­тер­ных тех­но­ло­гий не из­ме­ни­ло пред­став­ле­ний о клас­се функ­ций, вы­чис­ляе­мых А.

По­строе­ние и ана­лиз кон­крет­ных А., пред­на­зна­чен­ных для вы­пол­не­ния ком­пь­ю­те­ром, от­но­сит­ся к про­грам­ми­ро­ва­нию. Вы­де­ля­ют­ся так­же клас­сы ал­го­рит­мов вы­чис­ли­тель­ных и ал­го­рит­мов об­уча­ю­щих­ся.

См. так­же ста­тьи Ал­го­рит­ми­че­ская про­бле­ма, Ал­го­рит­ма слож­ность, Ал­го­рит­мов тео­рия.