АЛГОРИ́ТМОВ ТЕО́РИЯ

АЛГОРИ́ТМОВ ТЕО́РИЯ, раз­дел ма­те­ма­ти­ки, изу­чаю­щий об­щие свой­ст­ва ал­го­рит­мов. Часть А. т., в ко­то­рой изу­ча­ют­ся свой­ст­ва вы­чис­ли­мых функ­ций, не за­ви­ся­щие от слож­но­сти их за­да­ния и вы­чис­ле­ния, на­зы­ва­ет­ся об­щей или де­ск­рип­тив­ной А. т. К осн. по­ня­ти­ям А. т. от­но­сят­ся по­ня­тия вы­чис­ли­мой функ­ции, пе­ре­чис­ли­мо­го мно­же­ст­ва, т. е. мно­же­ст­ва зна­че­ний вы­чис­ли­мой функ­ции, и раз­ре­ши­мо­го мно­же­ст­ва (та­ко­го, для ко­то­ро­го су­ще­ст­ву­ет ал­го­ритм про­вер­ки при­над­леж­но­сти к не­му).

Про­бле­ма­ти­ка А. т. сфор­ми­ро­ва­лась при изу­че­нии ал­го­рит­мич. про­блем, в ча­ст­но­сти про­блем рас­по­зна­ва­ния свой­ст­ва ма­те­ма­тич. объ­ек­та, за­дан­но­го сво­им опи­са­ни­ем – кон­ст­рук­тив­ным объ­ектом. При­ме­ра­ми та­ких свойств яв­ляют­ся про­сто­та на­ту­раль­но­го чис­ла, су­ще­ст­во­ва­ние це­ло­чис­лен­но­го кор­ня у мно­го­чле­на с це­лы­ми ко­эф­фи­ци­ен­та­ми, ра­вен­ст­во двух эле­мен­тов груп­пы, вы­ра­жен­ных че­рез её об­ра­зую­щие, ис­тин­ность фор­му­лы ло­гич. язы­ка. Мн. про­бле­мы ал­геб­ры, ма­те­ма­тич. ло­ги­ки, тео­рии чи­сел, то­по­ло­гии и др. об­лас­тей ма­те­ма­ти­ки ока­за­лись не­раз­ре­ши­мы­ми (т. е. для них до­ка­за­но не­су­ще­ст­во­ва­ние ис­ко­мо­го ал­го­рит­ма). Не­раз­ре­ши­мость той или иной про­бле­мы рас­по­зна­ва­ния обыч­но до­ка­зы­ва­ет­ся све­де́­ни­ем к ней за­да­чи рас­по­зна­ва­ния при­над­леж­но­сти к не­раз­ре­ши­мо­му пе­ре­чис­ли­мо­му мно­же­ст­ву. Амер. ма­те­ма­тик и ло­гик Э. Л. Пост по­ста­вил про­бле­му су­ще­ст­во­ва­ния пе­ре­чис­ли­мо­го не­раз­ре­ши­мо­го мно­же­ст­ва, к про­блеме при­над­леж­но­сти к ко­то­ро­му сво­дят­ся не все про­бле­мы при­над­леж­но­сти к пе­ре­чис­ли­мым мно­же­ст­вам. Эта про­бле­ма и её по­ло­жи­тель­ное ре­ше­ние по­ло­жи­ли на­ча­ло ши­ро­ко­му кру­гу ис­сле­до­ва­ний, в т. ч. от­но­ся­щих­ся к фор­ма­ли­за­ции по­ня­тия све­де́­ния.

Точ­ная фор­му­ли­ров­ка ал­го­рит­мич. про­блем, воз­ни­каю­щих в раз­ных об­лас­тях ма­те­ма­ти­ки, тре­бу­ет ус­та­нов­ле­ния со­от­вет­ст­вия ме­ж­ду объ­ек­та­ми дан­ной об­лас­ти и на­ту­раль­ны­ми чис­ла­ми (или ины­ми кон­ст­рук­тив­ны­ми объ­ек­та­ми), что яв­ля­ет­ся пред­ме­том тео­рии ну­ме­ра­ций.

В А. т. ис­поль­зу­ют­ся уни­вер­саль­ные ал­го­рит­мы, ко­то­рые в при­ме­не­нии к па­ре $\left\langle x,y \right\rangle$ да­ют ре­зуль­тат при­ме­не­ния ал­го­рит­ма $x$ к объ­ек­ту $y$, а так­же т. н. диа­го­наль­ные кон­ст­рук­ции, где стро­ит­ся объ­ект, яв­но от­ли­чаю­щий­ся от лю­бо­го объ­ек­та за­дан­но­го се­мей­ст­ва. Тео­ре­ма о не­под­виж­ной точ­ке по­зво­ля­ет, опи­сав не­кую транс­фор­ма­цию про­из­воль­ной вы­чис­ли­мой функ­ции, ут­вер­ждать су­ще­ст­во­ва­ние функ­ции, не ме­няю­щей­ся при этой транс­фор­ма­ции.

В А. т. вы­де­ля­ет­ся тео­рия слож­но­сти, пред­став­лен­ная тео­ри­ей слож­но­сти вы­чис­ле­ния и тео­ри­ей слож­но­сти опи­са­ния. Тео­рия слож­но­сти вы­чис­ле­ния рас­смат­ри­ва­ет, в ча­ст­но­сти, вре­мя вы­чис­ле­ния (чис­ло ша­гов) и не­об­хо­ди­мый объ­ём па­мя­ти. Для не­ко­то­рых за­дач из­вест­ные ал­го­рит­мы их ре­ше­ния со­сто­ят в по­сле­до­ва­тель­ном пе­ре­бо­ре, напр. всех слов, и про­вер­ке для них ис­ко­мо­го свой­ст­ва. Од­на из от­кры­тых про­блем совр. ма­те­ма­ти­ки и вы­чис­лит. прак­ти­ки – про­бле­ма пе­ре­бо­ра – со­сто­ит (го­во­ря не­фор­маль­но) в вы­яс­не­нии то­го, су­ще­ст­ву­ют ли сре­ди этих за­дач та­кие, для ко­то­рых не­воз­мо­жен ал­го­ритм, ре­шаю­щий её бы­ст­рее, чем пе­ре­бо­ром (точ­нее, в по­ли­но­ми­аль­ное вре­мя). Слож­ность опи­са­ния объ­ек­та – это ми­ним. раз­мер ис­ход­но­го дан­но­го, из ко­то­ро­го фик­си­ро­ван­ный ал­го­ритм по­зво­ля­ет по­лу­чить этот объ­ект. Это по­ня­тие лег­ло в ос­но­ву ал­го­рит­мич. тео­рии ин­фор­ма­ции.

А. т. ис­поль­зу­ет­ся при по­строе­нии кон­ст­рук­тив­ной ло­ги­ки, кон­ст­рук­тив­ной ма­те­ма­ти­ки, на­хо­дит при­ме­не­ние в ма­те­ма­тич. лин­гвис­ти­ке, при про­ек­ти­ро­ва­нии и по­строе­нии уст­ройств ин­фор­мац. тех­но­ло­гий, раз­ра­бот­ке язы­ков про­грам­ми­ро­ва­ния, по­строе­нии кон­крет­ных ал­го­рит­мов и до­ка­за­тель­ст­ве пра­виль­но­сти их ра­бо­ты.