Рибак, Михайло2016-02-042016-02-042005Рибак М. В. Один із підходів до розв'язання задачі про знаходження оптимальної перестановки / М. В. Рибак // Наукові записки НаУКМА : Комп'ютерні науки. - 2005. - Т. 36. - С. 94-97.https://ekmair.ukma.edu.ua/handle/123456789/8108Серед задач, не розв’язаних за поліноміальний час, існує певний підклас задач, які розв’язуються ітеративно, причому кожна ітерація покращує розв’язок, який уже знайдено після всіх попередніх ітерацій. Таким чином, за умови існування певних обмежень на оціночну функцію розв’язку (наприклад, скінченність множини її значень) можна говорити про певну "поліноміальність" розв’язку - адже час, у гіршому випадку, лінійно залежить від потужності множини значень цієї функції. У праці розглянуто одну з таких задач і наведено відповідний ітеративний алгоритм.Among the problems which cannot be solved in polynomial time there is a subclass ofproblems that can be solved by means ofcertain iterative process where each iteration is used to improve the result achieved by all the previous ones. Hence, provided there are some certain constraintsfor the criterion function (for instance, finiteness of it s range), there is a polynomial solution in some sense - the solution is linearly dependent on the potency of the range of thisfunction. In this work one can find an example of such iterative algorithm.ukоціночна функція розв'язкуінтеративний алгоритмпродуктивність кодераArticle