ПРОГРА́ММ ОПТИМИЗА́ЦИЯ

ПРОГРА́ММ ОПТИМИЗА́ЦИЯ, пре­об­ра­зо­ва­ние про­грамм для ЭВМ, на­прав­лен­ное на улуч­ше­ние та­ких их ра­бо­чих ха­рак­те­ри­стик, как вре­мя вы­пол­не­ния и объ­ём ис­поль­зуе­мой па­мя­ти. Од­но из тре­бо­ва­ний, предъ­яв­ляе­мых к П. о., – её кор­рект­ность: пре­об­ра­зо­ван­ная про­грам­ма долж­на быть эк­ви­ва­лент­на ис­ход­ной по сво­им ре­зуль­та­там. Ино­гда до­пус­ка­ет­ся, что­бы об­ласть оп­ре­де­ле­ния пре­об­ра­зо­ван­ной про­грам­мы бы­ла ши­ре ис­ход­ной об­лас­ти. Дру­гое тре­бо­ва­ние со­сто­ит в том, что­бы П. о. име­ла при­ем­ле­мую ал­го­рит­мич. слож­ность при реа­ли­за­ции на ЭВМ.

По сте­пе­ни за­ви­си­мо­сти оп­ти­ми­за­ции от осо­бен­но­стей ЭВМ П. о. де­лят на ма­шин­но за­ви­си­мую, ма­шин­но ори­ен­ти­рован­ную и уни­вер­саль­ную. По раз­ме­ру оп­ти­ми­зи­руе­мо­го уча­ст­ка про­грам­мы раз­ли­ча­ют ло­каль­ную, ква­зи­ло­каль­ную и гло­баль­ную оп­ти­ми­за­ции. Для ус­ко­ре­ния П. о. ис­поль­зу­ют фак­то­ри­за­цию управ­ляю­ще­го гра­фа (см. Про­грамм ана­лиз): про­грам­ма пред­став­ля­ет­ся в ви­де ие­рар­хии вло­жен­ных фраг­мен­тов (т. н. га­ма­ков, ин­тер­ва­лов, зон), а гло­баль­ная оп­ти­ми­за­ция за­ме­ня­ет­ся се­ри­ей ква­зи­ло­каль­ных, при­ме­няе­мых к вы­де­лен­ным струк­тур­ным фраг­мен­там про­грам­мы.

При П. о. час­то от­де­ля­ют фа­зу ана­ли­за про­грам­мы, на ко­то­рой вы­де­ля­ют­ся фраг­мен­ты управ­ляю­ще­го гра­фа, а так­же вы­де­ля­ют­ся раз­но­об­раз­ные свой­ст­ва про­грам­мы, су­ще­ст­вен­ные с точ­ки зре­ния улуч­ше­ния её эф­фек­тив­но­сти, от фа­зы соб­ст­вен­но пре­об­ра­зо­ва­ния, на ко­то­рой про­из­во­дит­ся улуч­ше­ние про­грам­мы.

Наи­бо­лее важ­ны­ми с прак­тич. точ­ки зре­ния яв­ля­ют­ся сле­дую­щие ви­ды П. о.: умень­ше­ние час­тот вы­пол­не­ния фраг­мен­тов про­грам­мы («чи­ст­ка» цик­лов, зон и ре­кур­сив­ных об­лас­тей); эко­но­мия из­бы­точ­ных и об­щих вы­ра­же­ний; «чи­ст­ка» про­грам­мы за счёт уда­ле­ния не­дос­туп­ных, не­ис­поль­зуе­мых или не влияю­щих на ре­зуль­тат фраг­мен­тов про­грам­мы; уп­ро­щаю­щие ал­геб­ра­ич. пре­об­ра­зо­ва­ния с ис­поль­зо­ва­ни­ем свойств при­ме­няе­мых в про­грам­ме опе­ра­ций.

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