Adomo Birtuno
Algoritm teorijos paskait konspektas
2012 m. birelio 16 d.

---

Turinys
1 Algoritmo samprata
2
2 Hilberto tipo teigini skaiiavimas
3
2.1
Dedukcijos teorema . . . . . . . . . . . . . . . . . . . . . . . . . .
4
3 Sekvencinis skaiiavimas
7
4 Disjunkt dedukcin sistema. Rezoliucij metodas
9
4.1
Rezoliucij metodas . . . . . . . . . . . . . . . . . . . . . . . . .
12
5 Turingo mainos ir j variantai
13
5.1
Baigtiniai automatai . . . . . . . . . . . . . . . . . . . . . . . . .
14
5.2
Algoritm sudtingumas . . . . . . . . . . . . . . . . . . . . . . .
14
5.3
Por numeravimas . . . . . . . . . . . . . . . . . . . . . . . . . .
16
5.4
Baigtinumo problema . . . . . . . . . . . . . . . . . . . . . . . .
17
6 -skaiiavimas
19
7 Primityviai rekursyvios funkcijos
21
7.1
Dalinai rekursyvios funkcijos . . . . . . . . . . . . . . . . . . . .
22
7.2
Rekursyviai skaiiosios aibs . . . . . . . . . . . . . . . . . . . . .
24
7.3
Ackermann funkcijos. . . . . . . . . . . . . . . . . . . . . . . . . .
27
7.4
Universaliosios funkcijos . . . . . . . . . . . . . . . . . . . . . . .
28
1

---

skyrius 1
Algoritmo samprata
1 Ap.
(Algoritmas). (Intuityvus apibrimas.) Veiksm seka, kuri leidia
sprsti vien ar kit udavin.
Pagrindins algoritmo savybs:
* ingsni elementarumas;
* diskretumas (algoritmas suskirstytas atskirus ingsnius);
* determinuotumas (atlikus ingsn aiku, kok kit ingsn reikia atlikti);
* masikumas (skirtas ne vienam udaviniui, bet j klasei sprsti).
Algoritmo formalizavimo bdai:
1. sukurti idealizuot matematin main (Turingo, RAM);
2. apibrti rekursyvi funkcij klas (Dalinai rekursyvios funkcijos, -skaiiavimas).
1 Tg. (Church tez) Algoritmikai apskaiiuojam funkcij aib sutampa su
rekursyvij funkcij klase. (Sio teiginio nemanoma rodyti.)
2 Tg. Turingo mainomis apskaiiuojam funkcij aib sutampa su rekursyvij
funkcij klase.
2

---

skyrius 2
Hilberto tipo teigini
skaiiavimas
2 Ap. (Hilberto tipo teigini skaiiavimas). Skaiiavimas, kuriame yra aksiom
schemos:
1.
1 A (B A)
2 (A (B C)) ((A B) (A C))
2.
1 (A B) A
2 (A B) B
3 (A B) ((A C) (A (B C)))
3.
1 A (A B)
2 B (A B)
3 (A C) ((B C) ((A B) C))
4.
1 (A B) (B A)
2 A A
3 A A
ir taisykl Modus Ponens (MP):
prielaidos { A
A B
(MP), ia A, B, C - bet kokios teigini logikos formuls.
ivados {
B
Sakysime, jog formul F yra vykdoma Hilberto tipo teigini skaiiavime,
jeigu galima parayti toki formuli sek, kurioje kiekviena formul yra:
* arba aksioma,
* arba gauta pagal MP i ankstesni
3

---

ir kuri (seka) baigiasi formule F .
3 Tg. Jei formul yra rodoma Hilberto tipo teigini skaiiavime, tai ji yra
tapaiai teisinga ir atvirkiai (jei nra rodoma, tai nra tapaiai teisinga).
Sakysime, jog skaiiavimo aksioma yra nepriklausoma, jei j imetus i skai-
iavimo, ji nra ivedama jame.
Visos Hilberto teigini skaiiavimo aksiomos yra nepriklausomos.
2.1 Dedukcijos teorema
Sakysime, kad formul F yra ivedama i prielaid A1, A2, A3, . . . , An, jei
egzistuoja tokia formuli seka, kurioje kiekviena formul yra:
* arba aksioma,
* arba prielaida,
* arba gauta pagal MP i ankstesni
ir kuri (seka) baigiasi formule F .
Zymjimas: A1, A2, . . . , An
F
4 Tg. (Dedukcijos teorema)
A B , A
B, kur A,B - bet kokios
formuls, - baigtin formuli aib (gali bti tuia).
Proof.
Btinumas
Jei
A B, tada egzistuoja formuli seka:
1.
F1
2.
F2
* * *
i.
Fi
* * *
k.
Fk = A B
k+1.
A
prielaida
k+2.
B
MP i k ir (k+1).
kurioje:

aksioma
Fi =
prielaida i


gauta pagal MP i ankstesni
, A
B.
4

---

Pakankamumas
Jei , A
B, tai yra tokia formuli seka:
1.
F1
2.
F2
* * *
i.
Fi
* * *
k. Fk = B
kurioje:


aksioma
prielaida i
Fi =
prielaida

A
gauta pagal MP i ankstesni
Sukonstruokime toki formuli sek (kuri nebtinai yra ivedimas):
1.
A F1
2.
A F2
* * *
i.
A Fi
* * *
k. A Fk = A B
Dabar kiekvien A Fi keiiam tokiu bdu:
1. Jei Fi - aksioma, tada keiiam :
i.1 Fi (A Fi) 1.1 aksioma
i.2 F1
aksioma
i.3 A F1
MP i (i.1) ir (i.2)
2. Jei Fi - prielaida i , tada keiiam :
i.1 Fi (A Fi) 1.1 aksioma
i.2 F1
prielaida i
i.3 A F1
MP i (i.1) ir (i.2)
3. Jei Fi - prielaida A, tada A Fi = A A. Keiiam A A
ivedimu.
4. Tegu A Fu yra visos ivestos, kur u < i. Fi buvo gauta i kakoki
Fr ir Fl (kur r, l < i) pritaikius MP. Taigi mes jau turime ivestas
A Fr ir A Fl. Kadangi Fl = Fr Fi (arba Fr = Fl Fi), tai:
Fl
i.1 (A (Fr Fi)) ((A Fr) (A Fi)) 1.2 aksioma
i.2 (A Fr) (A Fi)
pagal MP
i.3 A Fi
pagal MP
5

---

Sakysime, jog skaiiavimas yra pilnas formuli aibs A atvilgiu, jei formul
A tada ir tik tada, jei ji yra rodoma skaiiavimu.
Hilberto tipo teigini skaiiavimas yra pilnas tapaiai teising formuli aibs
atvilgiu.
6

---

skyrius 3
Sekvencinis skaiiavimas
3 Ap. (Sekvencija). Tokia iraika F1, F2, . . . , Fn
G1, G2, . . . , Gm, jei n + m > 0.
anticedentas
sukcedentas
Pastaba.
*
F - formul yra tapaiai teisinga.
* A1, A2, . . . , An
F - i prielaid seka ivada F.
* A1, A2, . . . , An
B1, B2, . . . , Bm - i prielaid seka bent viena i ivad
B1, . . . , Bm.
* F
- formul yra tapaiai klaidinga.
4 Ap.
(Sekvencinis skaiiavimas G). Skaiiavimas su aksioma , A,
, A, ir taisyklmis (, , , , , - formuli sekos, A, B - formuls):
(
)
, A,
,
,
, A,
( )
,
, A,
, A,
,
(
)
,
, A, B,
,
, A B,
( )
, A,
,
, B,
,
, A B,
,
7

---

(
)
,
, A,
,
, B,
,
, A B,
( )
, A, B,
,
, A B,
,
( )
, A,
, B,
,
, A B,
( )
,
, A,
, B,
,
, A B,
,
Sakysime, kad sekvencija F1, . . . , Fn
G1, . . . , Gm yra ivedame skaiiavime
G, jei galime sukonstruoti tok med (graf), kurio visose virnse yra sekven-
cijos, aknyje yra pradin sekvencija F1, . . . , Fn
G1, . . . , Gm ir kiekvienai vir-
nei teisinga: jei virns N , kurioje yra sekvencija S, vaike(-uose) N1 (ir N2)
yra sekvencija(-os) S1 (ir S2), tai sekvencija S yra gauta i sekvencijos(-j) S1
(ir S2) pagal kakuri taisykl, ir kurio (medio) visuose lapuose yra aksiomos.
Sakysime, kad taisykl yra apveriama, jei teisinga: jei taisykls ivada i-
vedama, tai ivedamos ir visos taisykls prielaidos.
Visos sekvencinio skaiiavimo G taisykls yra apveriamos.
Jei ivedant gautas lapas, kuriame nra nei vienos formuls ir jis nra aksio-
ma, tai reikia, kad:
1. sekvencija yra neivedama, arba
2. skaiiavime buvo panaudota neapveriama taisykl.
5 Tg. Formul F yra tapaiai teisinga tada ir tik tada, kai sekvenciniame skai-
iavime G ivedama sekvencija
F .
8

---

skyrius 4
Disjunkt dedukcin
sistema. Rezoliucij
metodas
5 Ap. (Disjunktas). Liter disjunkcija. Litera yra kintamasis arba kintamasis
su neigimu.
6 Ap. (Atkirtos taisykl (AT)).
C p C
D p D
, kur p - litera, o C , C , D , D - disjunktai.
C C D D
7 Ap. (S
C). Sakysime, kad disjunktas C yra ivedamas i disjunkt aibs
S, jei galima parayti toki disjunkt sek, kur kiekvienas disjunktas:
* arba i aibs S,
* arba gautas pagal atkirtos taisykl i jau parayt
ir kuri (seka) baigiasi disjunktu C.
8 Ap. (Prietaringa formuli aib). Sakysime, kad formuli aib S yra prieta-
ringa, jei su bet kokia interpretacija bent viena formul i aibs S yra klaidinga.
Pastaba. Jei S nra prietaringa, tai S - vykdoma.
6 Tg. Jei i disjunkt aibs S ivedamas disjunktas C ir disjunktas C nra
vykdomas (tapaiai klaidingas), tai S - prietaringa.
Proof. (Prietaros bdu.)
Tarkime S
C ir C - nra vykdomas, bet aib S nra prietaringa.
Jei aib S nra prietaringa, tai yra tokia interpretacija , su kuria visi aibs
S disjunktai bus teisingi:
D (D S) : (D) = 1
9

---

Document Outline

• Algoritmo samprata
• • Dedukcijos teorema
• 
• ﾿
• 
  • Baigtiniai automatai
  • ﾿
  • Baigtinumo problema
• 
• Primityviai rekursyvios funkcijos
  • Dalinai rekursyvios funkcijos
  • ﾿
  • Ackermann funkcijos.
  • Universaliosios funkcijos

---