Teori Komputeran [English]

                                                                                                           

Kemungkinan-kemungkinan rujukan:

• R. Bird, Programs and Machines. An Introduction to the Theory of Computation (Wiley)
• A.K. Dewdney, The Turing Omnibus (Computer Science Press)
• J. Glenn Brookshear, Computer Science. An Overview (Addison-Wesley) [Bab 11]

 

Objektif topik: Pelajar harus faham konsep aturcara, mesin dan pengkomputeran secara teori, dan sedar tentang isu-isu berkaitannya dalam teori komputeran.  

 

aturcara: suatu set berstruktur suruhan-suruhan yang membolehkan suatu ‘mesin’ mengenakan  satu persatu operasi-operasi dan ujian-ujian asas yang tertentu dalam cara berketentuan ke atas data awal, sehingga data tersebut telah diolah ke dalam bentuk yang dikehendaki.

 

♣      Aturcara carta aliran (‘cartaliran’)

♣      Aturcara ‘while’ (‘sementara’)

♣      Aturcara tatacara

 

Aturcara cartaliran

 

komponen-komponen:    

 

Contoh:

F, G, …           pengecam operasi T1, T2, …         pengecam ujian   aturcara ini sepadan dengan:   1: do F then goto 2 2: if T1 then goto 1 else goto 3 3: do G then goto 4 4: if T2 then goto 5 else goto 1   do – lakukan if – jika benar then goto – maka/kemudian ke else goto – jika tidak pergi ke   suruhan-suruhan terlabel – 2 bentuk: l: do F then goto l ' l: if T then goto l ' else goto l "

Suatu cartaliran P ialah set terhad suruhan-suruhan terlabel dengan ciri

                       

∀ suruhan i,j ∈ P                      jika λ(i) = λ(j) maka i = j

 [ λ(i) adalah label bagi i  ]

 

label awal – misalnya 1

label penamat – l yang muncul dalam P yang mana tiada i dalam P di mana l = λ(i)

 

Aturcara ‘while’

 

berdasarkan:

komposisi: jika P dan Q aturcara, P;Q (iaitu P kemudian Q) juga aturcara   kenyataan bersyarat: jika P dan Q aturcara, (if T then P else Q) ialah aturcara, yang jalankan P jika T benar atau Q jika T palsu   kenyataan ‘while’: jika P aturcara,  while T do (P) ialah aturcara, yang berulang-ulang menguji T dan melakukan P, sehinggalah ujian T memberikan hasil palsu   (kurungan dalam kenyataan adalah penting untuk menentukan jujukan operasi hasil komposisi)

           

binaan cartaliran yang sepadan dengan kenyataan ‘while’:

 

kenyataan ‘until’:

                                    until T do P       setara dengan       while ¬T do P

 

 

aturcara nol: I – tak buat apa-apa

                        jadi    I;P = P;I = P      ∀ P

 

Aturcara tatacara

 

berbentuk:

                        E where R₁ is E₁, R₂ is E_{2, …,} R_n is E_n.                         [ where – di mana        is – ialah ]

E – ungkapan awal

                                                                                                E_i – ungkapan yg mendefinisikan R_i

                                                                                                R_i – pengecam tatacara

♠         setiap pengecam tatacara, dan setiap pengecam operasi, secara tersendiri, ialah ungkapan

(I ungkapan nol)

♠         jika D dan E ungkapan,

D;E      juga ungkapan

(if T then D else E)     juga ungkapan

 

contoh:     R₁;R₂ where

                        R₁ is F;(if T then R₁ else G;R₂),

                        R₂ is (if T then I else F;R₁)

 

 

TEOREM

 

• diberi apa-apa aturcara ‘while’ P, boleh dibina aturcara cartaliran Q yang mana P ≡ Q
• diberi apa-apa aturcara cartaliran P, boleh dibina aturcara tatacara Q yang mana P ≡ Q

 

 

 

mesin:  memberikan semua maklumat yang tiada dalam aturcara supaya komputeran boleh dijalankan - makna-makna pengecam operasi dan ujian, masukan dan keluaran maklumat

 

operasi – pengolahan ke atas struktur ingatan mesin

ujian – fungsi kebenaran tertentu

 

mesin M mengandungi

-         set masukan/input X

-         set ingatan V

-         set keluaran/output Y

-         fungsi masukan I_M : X → V

-         fungsi keluaran O_M : V → Y

-         untuk setiap pengecam operasi F, fungsi F_M : V → V

-         untuk setiap pengecam ujian T, fungsi T_M : V → {benar,palsu}

 

contoh: X = Z           (set integer-integer)

                        V = Z×Z

                   Y = Z

                   I_M : Z→ Z×Z, dengan definisi I_M(x) = (x,0)

                        O_M : Z×Z→ Z, dengan definisi O_M(x,y) = y

                        F_M : Z×Z→ Z×Z, dengan definisi F_M(x,y) = (x-1,y)

                        G_M : Z×Z→ Z×Z, dengan definisi G_M(x,y) = (x,y+1)

                        T_M : Z×Z→{benar,palsu}, dengan definisi T_M(x,y) = benar, jika x = 0,

dan palsu jika tidak

 

                        - anggapkan ingatan terdiri daripada dua daftar, A dan B

                                                dengan             F:         A := A-1

                                                                        G:        B := B+1

                                                                        T:         (A = 0)

                        misalnya

                                    until A=0 do (A := A-1; B := B+1)

                                                adalah suatu aturcara ‘while’ untuk mesin M

 

 

beberapa jenis mesin:             mesin daftar

                                                mesin surihan

                                                mesin NORMA

                                                mesin keadaan terhad

                                                mesin Turing

                                                mesin capaian rawak

                                               

                       

                                                           

 

pengkomputeran: jujukan gabungan-gabungan unsur aturcara dengan keadaan ingatan mesin sepadan

 

untuk aturcara cartaliran P dgn label-label l_i ∈ L, komputeran P atas mesin M dgn keadaan-keadaan ingatan v_i ∈ V,

ialah

jujukan unsur-unsur L×V,          (l₁, v₁), (l₂, v₂), …, (l_j, v_j), ..., (l_n, v_n).       

            di mana

                                    ∀j, samada       l_j: do F then goto l                               berada dalam P

dgn l_j+1 = l dan v_j+1 = F_M (v_j)   

                                          atau            l_j: if T then goto l' else goto l"             berada dalam P

                                                                        dgn l_j+1 = l' jika T_M (v_j) = benar, dan l_j+1 = l" jika T_M (v_j) = palsu

dan v_j+1 = v_j    

 

pengkomputeran menamat jika l_n adalah label penamat

 

pengkomputeran P atas M        fungsi mP: X → Y

                                                            utk x ∈ X         v₁ = I_M (x)

                                                                                    mP(x) = O_M (v_n)

 

-- serupa untuk aturcara jenis lain; misalnya utk aturcara tatacara -         (X₁, v₁), (X₂, v₂), …    

X_i ungkapan

 

 

kesetaraan                  kesetaraan (kuat):        P ≡ Q       jika   mP = mQ      ∀M                  P setara Q atas M jika    mP(x) = mQ(x),     ∀x∈X

 

ketamatan                 P tamat atas M jika    mP(x) terdefinisi    ∀x∈X

 

kebetulan                 P separa betul terhadap φ dan ψ  (atas M)                                                        jika     ψ(x,mP(x)) benar ∀x∈X                                                             utk            φ(x) benar   dan    mP(x) terdefinisi                        (perlu tamat hanya utk yang memenuhi syarat)                 P sepenuhnya betul terhadap φ dan ψ  (atas M)                                                        jika     mP(x) terdefinisi                                                            dan   ψ(x,mP(x)) benar ∀x∈X    utk  φ(x) benar                        (perlu tamat utk semua kes)                       φ dan ψ  : syarat-syarat tentang apa yang diinginkan, dan apa yang didapati