АЛГОРИ́ТМ ВЫЧИСЛИ́ТЕЛЬНЫЙ

АЛГОРИ́ТМ ВЫЧИСЛИ́ТЕЛЬНЫЙ, од­но из осн. по­ня­тий вы­чис­лит. ма­те­ма­ти­ки, по­сле­до­ва­тель­ность дей­ст­вий, ко­то­рая, на­чи­ная с за­дан­ных ис­ход­ных дан­ных, за ко­неч­ное чис­ло ша­гов при­во­дит к ис­ко­мо­му ре­зуль­та­ту.

Про­стей­ши­ми при­ме­ра­ми А. в. яв­ля­ют­ся пра­ви­ла сло­же­ния, вы­чи­та­ния, ум­но­же­ния и де­ле­ния. Под А. в. час­то так­же по­ни­ма­ют по­сле­до­ва­тель­ность ин­ст­рук­ций (по­сле­до­ва­тель­ность ариф­ме­тич. дей­ст­вий и ус­лов­ных опе­ра­то­ров), ко­то­рые мо­гут быть од­но­знач­ным об­ра­зом реа­ли­зо­ва­ны в ви­де про­грам­мы на вы­чис­лит. ма­ши­не. Ариф­ме­тич. вы­ра­же­ние, как пра­ви­ло, не оп­ре­де­ля­ет од­но­знач­но А. в., по­сколь­ку оно ино­гда до­пус­ка­ет разл. по­ря­док вы­пол­не­ния опе­ра­ций, что для А. в. мо­жет ока­зать­ся су­ще­ст­вен­ным. На­при­мер, при вы­чис­ле­нии сум­мы чи­сел ви­да $n^{–2}$ от 1 до 1000000 на вы­чис­лит. ма­ши­не с пла­ваю­щей за­пя­той су­ще­ст­вен­ным яв­ля­ет­ся по­ря­док сум­ми­ро­ва­ния чи­сел. Ре­зуль­та­ты при пря­мом и об­рат­ном по­ряд­ках сум­ми­ро­ва­ния от­ли­ча­ют­ся друг от дру­га. Это свя­за­но с тем, что вы­чис­ле­ния про­из­во­дят­ся с ок­руг­ле­ния­ми; при пря­мом по­ряд­ке сум­ми­ро­ва­ния име­ют ме­сто су­ще­ст­вен­но бо́ль­шие ок­руг­ле­ния и, со­от­вет­ст­вен­но, боль­шее на­ко­п­ле­ние по­греш­но­сти ок­руг­ле­ний.

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

Предъ­яв­ля­ют­ся так­же тре­бо­ва­ния к ариф­ме­тич. слож­но­сти А. в. – ко­ли­че­ст­ву эле­мен­тар­ных опе­ра­ций, не­об­хо­ди­мых для его вы­пол­не­ния. В ка­че­ст­ве при­ме­ра мож­но при­вес­ти вы­чис­ле­ние вы­ра­же­ния $AB\boldsymbol x$, где $A$ и $B$ – квад­рат­ные мат­ри­цы раз­мер­но­сти $n×n$, а $\boldsymbol x$ – век­тор раз­мер­но­сти $n$. При­ве­дён­ное вы­ра­же­ние не оп­ре­де­ля­ет А. в., по­сколь­ку не оп­ре­де­лён по­ря­док дей­ст­вий. Вы­бор разл. по­сле­до­ва­тель­но­стей опе­ра­ций при­во­дит к двум ал­го­рит­мам $A(B\boldsymbol x)$ и $(AB)\boldsymbol x$, для пер­во­го из ко­то­рых ариф­ме­тич. слож­ность есть $O(n^2)$, а для вто­ро­го – $O(n^3)$. Ариф­ме­тич. слож­ность А. в. яв­ля­ет­ся од­ним из осн. кри­те­ри­ев его ка­че­ст­ва. В слу­чае ис­поль­зо­ва­ния мно­го­про­цес­сор­ной тех­ни­ки и па­рал­лель­ных вы­чис­ле­ний кри­те­рий ка­че­ст­ва А. в. ме­ня­ет­ся.