Reja: Algoritm tushunchasi

1 begin

2 for u  V do

3 for v  V do F[и, v] := 0; (* нулевой начальный поток *)

4 repeat PSA; (*построение вспомогательной бесконтурной сети*)

5 if ДЛИНА[t]   then (* поток F не является максимальным *)

begin MAXPSA; (*построение максимального потока

во вспомогательной сети*)

(*перенести поток из вспомогательной сети в главную*)

for u  XV do (*XV = множество вершин вспомогательной

сети*)

8 for v  XV do

9 begin F[u, v] := F[u, v] – XF[u, v];

10 if F[u, v] > C[u, v] then

11 begin

F[v, u] := F[v, u] – (F[u, v] – C[u, v]);

12 F[u, v] := C[u, v]

13 end

14 end

15 end (* конец фазы*)

16 until ДЛИНА[t] =  (* поток F – максимальный *)

17 end


13-ma'ruza. NP bilan bog'liq muammolar. Hisoblash qobiliyatsizligi

Maruzachi o’qituvchi: katta o’qituvchi Ganihodjayeva Dilfuza Ziyavutdinovna

Reja

1. Kirish

2. Algoritmik echilmaydigan muammolarga misollar

3. Cantorning diagonal usuli

4. NP sinfi.

Hisoblangan har qanday funktsiyani turli xil algoritmlar (tanlangan universal ijrochi uchun turli xil dasturlar) bilan belgilash mumkin va har qanday universal ijrochi yordamida hisoblash mumkin: Turing va Post mashinalari, normal Markov algoritmlari va boshqalar, ammo algoritmik hisoblanmaydigan funktsiyalar ham mavjud.

Ammo u yoki bu sinfning algoritmik echimini topib bo'lmaydi, bu biron bir muammoni xuddi shu texnikadan foydalanib hal qilish mumkin emas degani emas.

Algoritm kontseptsiyasining rasmiylashtirilishi algoritmik echimlar mavjud bo'lmagan muammolar mavjudligini o'rganishga imkon berdi.