BAB I KETELITIAN DALAM PEMROGRAMAN
1.1 Pemograman dalam ukuran kecil 1.1.1 Bagaimana
menulis
program-program
yang
benar
dan
mengetahuinya •
Pandangan lama tentang suatu pemograman adalah :
1.
Pemograman cenderung akan memiliki kesalahan
2.
Pendekatan yang dilakukan adalah “Cut-and-Try”
•
Pandangan baru tentang suatu pemograman adalah
1. Kita dapat mempelajari pemograman yang perancangan yang konsisten dan penulisan program yang benar dari awal 2. Dapat memberikan penggunaan berikutnya
“error
free”
pada
uji
cobanya
dan
• Dengan berlatih menerapkan prinsip-prinsip pemograman terstruktur dan matematikanya kita diharapkan dapat menulis program yang benar dan meyakinkan pada kita dan orang lain bahwa program yang dituliskan adalah benar menurut logika dan akal, dibanding dengan “Trial dan Error” • Sekalipun jika kita sudah menemukan “last error” yang tersisa dalam program, kita tidak dapat memastikan apakah hal tersebut adalah yang kesalahan yang terakhir • Meningkatkan pengalamanan dalam penulisan program yang benar, dimulai dari program yang kecil, kemudian yang besar, akan memberikan suatu basis secara psykologi baru untuk menunjang dalam pemograman • Metode Pemograman Terstruktur akan memberikan kita untuk menulis ribuan baris program dalam dua puluh langkah dari lima puluh, tidak sebagai subprogramn yang terpisah, tetapi sebagai perluasan yang terus menerus dan pelaksanaan program secara bagaian per bagian Apakah Program yang benar itu ?
• Suatu program yang benar mendefinisikan suatu prosedur untuk suatu ketetapan pemrosesan yang ditujukan untuk memenuhi suatu spesifikasi yang ditetapkan •
Program dapat saja berubah-ubah yang disebabkan karena
1.
Perubahan spesifikasi
2.
Kesalahan pemograman
3.
Perbedaan pemrosesan
• Penulisan program yang benar tidak berarti bahwa program-program dapat ditulis sekali dan selamanya. Ini artinya bahwa program hendaknya ditulis tepat dengan yang diharapkan. Pembuktian dari kebanaran suatu program • Dengan menerapkan prinsip-prinsip pemograman terstruktur secara matematis pada penulisan program secara konsisten maka dimungkinkan seorang programmer dapat dibantu dalam penulisan sebuah program • Pembuktian secara matematika adalah dengan melakukan serangkaian percobaan untuk menjawab atas hitoptesa yang kita berikan sendiri •
Notasi matematika
1 Memberikan kesempatan untuk menggunakan pensil dan kertas dalam meluaskan pemikiran 2 Memberikan kesempatan kepada manusia untuk setuju pada aturanaturan untuk kesepatakan terhadap klaim pembuktian • Matematika memberikan suatu bentuk bahasa dan prosedur untuk pola pikir kita II.4 Suatu pendekatan intuisi (Intuitive Approach) menuju Kebenaran Program • Dikatakan pendekatan intuisi karena pendekatan ini berhubungan langsung dengan operasi dari program dan tidak menggunakan bentuk aljabar dari pemograman terstruktur •
Tujuan dari ini adalah hanya untuk menunjukan bahwa suatu
pembuktian dari kebenaran program adalah mungkin dilakukan •
Pertimbangkan Gambar dibawah ini
in : [X > 0]
Y := 0 init : [X > 0 and Y = 0]
cont : [Y 2 < X]
loop : [Y 2 < X]
Yes
Decision
Y := Y + 1
yes : [(Y+1) 2 < X]
No out : [ X tidak berubah and Y2 < X < Y (Y+1) 2]
Pemograman dalam ukuran besar Integritas secara konsep • Integritas secara konsep (Conceptual Integrity) adalah hal yang terpenting dalam pertimbangan pada perancangan system Perbedaan antara “Heuristic Design” dan “Rigorous Design” •
Rancangan :
1. Heuristic Design 2. Rigorous Design •
Heuristic Design merujuk pada "Trial and Error"
• Rigorous Design menyertakan suatu state machine yang mendefinisikan suatu himpunan tertutup dari transisi system, atau Recursive Function yang mendefinisikan suatu search space, atau mungkin formal grammar yang mendefinisikan semua kemungkinan input dan output untuk suatu program
• Rigorous Design menjadi basis dalam merawat integritas dalam pengembangan perangkat lunak Pemrograman Terstuktur dan Perancangan yang baik • Pemrograman Terstruktur ditulis untuk orang lain yang membaca dan untuk dimengerti. • Perancangan yang baik berarti penemuan solusi yang baik pada sebuah permasalahan yang sering terdefinisikan •
Langkah-langkah yang dilakukan
1.
Definisikan suatu permasalah yang benar
2.
Temukan solusi yang baik
• Suatu pemograman terstruktur tidak menjamin perancangan yang baik, melainkan hanya memberikan suatu kemungkinan terhadap perancanan yang baik • Suatu peracangan yang baik didasarkan atas kesederhanaan pada suatu tugas logika yang kompleks
dalamnya
1.2.4 Perbedaan antara Pendetailan dan Perancangan • Suatu program komputer tidak membutuhkan rancangan, tetapi “code”, dimana apabila kode benar maka komputer akan menghasilkan sesuatu yang benar • Terdapat satu kesukaran dengan pernyataan di atas; walaupun logika yang diberikan “benar” tetapi mustahil seseorang dapat membangun suatu program yang kompleks dan besar tampa terjadi suatu bentuk masalah • Pada kenyataannya istilah perancangan digunakan pemograman, tetapi istilah pendetailan adalah lebih cocok
dalam
• Perancangan menghasilkan Detail-detail, tetapi pendetailan tidak menghasilkan rancangan 1.2.5 Validasi Perancangan dengan Pengembangan Top-Down • Yang penting dari pengembangan Top-Down pada software yang besar adalah berasal dari pengalaman pahit dimana pengembangan Top-Down di-ikuti oleh pengembangan Bottom-Up
• Pada Pengembagan Bottom-Up dimana “Low Level code” ditulis terlebih dahulu dalam pengintegrasian dilakukan kemudian. • Rancangan yang kurang baik akan terlihat pada saat dilakukkannya pengintegrasian • Sebaliknya, pada pengembangan Top-Down, program-program kontrol yang mengintegrasikan secara fungsional dari kode, ditulis dan di test terlebih dahulu, dan functional code ditambahkan dengan bergerak maju. • Pada Sistem Software, pengembangan Top-Down dimulai dengan rancangan secara logika untuk menyelaraskan kooperasi dari beberapa program melalui akses terhadap beberapa himpunan “shared data” • Permasalahan yang yang ada pada pemngembangan Top-Down adalah tidak hanya bagaimana bentuk akhir dari sistem, tetapi juga bagaimana bentuk dari sistem selama pengembangan
1.2.6 Dasar dari “Software Reliablility” adalah pada perancangan bukan pada uji coba
•
Dengan testing tidak mungkin softtware dapat dibuat reliable
•
Rancangan dapat
1.
mengurangi ukuran dari sistem
2.
mengurangi interkoneksi
3.
mengurangi kompleksitas spesifikasi program
• Seorang perancang memiliki kesempatan untuk menggunakan rancangan Top-Down dan disiplin pengembangan pemograman terstruktur, untuk tetap memperluas rancangan dibawah pengawasan pengetahuan yang baik untuk menemukan kesederhanaan yang terdalam yang mungkin muncul pada setiap level, langkah demi langkah
BAB II ELEMEN-ELEMEN EKSPRESI LOGIKA 1.
Overview
• Pemograman perancangan
adalah
suatu
bentuk
khusus
dari
kreatifitas
• Pada awalnya program dibuat hanya untuk dimengerti oleh mesin, pandangan tersebut saat ini berubah, bahwa suatu program dibuat adalah juga untuk dimengerti oleh manusia • Dasar dalam membentuk suatu bentuk pemograman yang baik mencakup elemen yaitu English (Bahasa), matematika, bentuk-bentuk ekspresi logika
2.
Bahasa yang baik
• Bentuk bahasa yang baik dalam mendesripsikan suatu pemograman adalah dengan membentuk bahasa yang terstruktur • Pseudocode adalah salah satu bentuk bahasa yang terstruktur (English Structure)
3.
Formal Logic
3.1
Logical Propositions
• Formal Logic berhubungan dengan komunikasi manusia dan suatu bentuk yang dapat meyakinnya di antara manusia tentang suatu kebenaran dari suatu pernyataan • Formal Logic menyediakan suatu “axiomatic calculus” atau suatu perhitungan yang didasarkan atas suatu himpunan axiom
•
Dua model formal logic adalah 1. Propotional Calculus 2. Predicate Calculus
• Suatu pernyataan disebut logical proposition apabila terdapat suatu nilai yang menyatakan kebenaran terhadap pernyataan tersebut • 3.2
Nilai adalah True dan False Propositional Calculus
• Pada saat suatu kumpulan pernyataan di katakan sebagai proposition, dengan penyataan benar semuanya, Propositional Calculus memberikan suatu himpunan yang tetap dari berbagai cara pengkombinasian proposition lama ke dalam bentuk baru • Propositonal Calculus memberikan cara-cara bagaimana melakukan “Breaking Down” suatu proposition yang kompleks kedalam bentuk yang sederhana •
Kombinasi dari proposition disebut suatu logical expression
•
Tipe umum dari logical expresion adalah
1.
not ; suatu proposition p, penolakan, ditandai ~p
2. and ; dua proposition p,q, pernyataan dari kedua-duanya, ditandai dengan notasi p ∧ q 3. or ; dua proposition p,q, pernyataan untuk setidak-tidaknya satu, ditandai p ∨ q 4. equal ; dua proposition p,q, pernyataan yang p dan q memiliki nilai logika yang sama, ditandai p ↔ q 5. implies ; dua proposition p, q, pernyataan dimana jika p adalah benar maka q pasti benar, ditandai denan p → q • Nilai kebenaran pada suatu ekspresi tergantung pada nilai setiap propostion dan kemudian diterapkan pada tabel kebenaran
not
and
or
equals
implies
Rule
p
q
~p
p∧q
p∨q
p↔q
p →q
1
T
T
F
T
T
T
T
2
T
F
F
F
T
F
F
3
F
T
T
F
T
F
T
4
F
F
T
F
F
T
T
• Compound Logical Expression adalah merupakan kumpulan dari beberapa ekspresi logika
•
contoh
(F ∧ (~T)) ∨ ((F → T) ∨ (T ↔ T)) (F ∧
F ) ∨ ((F → T) ∨ (T ↔ T))
not, oleh aturan 1
F ∨
((F → T) ∨ (T ↔ T))
and, oleh aturan 4
F ∨
(T
∨ (T ↔ T))
implies, oleh aturan 3
F ∨
(T
∨ T
equals, oleh aturan 1
F ∨
T
)
T
or, oleh aturan 1 or, oleh aturan 3
a.
Predicate Calculus
• Proposional calculus mencakup analisa dari proposition yang dipecah menjadi proposition yang sederhana; dimana bentuk yang paling sederhana sudah tidak dapat dibagi lagi • Biar bagaimanapun, melihat proposition yang sederhana merupakan suatu bentuk struktur subyek dan predikat, dan khususnya suatu pernyataan yang subyeknya tidak diketahui •
Bentuk ini dikatakan sebagai Predicate Calculus
•
Suatu pernyataan terdiri dari
1. variable 2. predicate • P(x) adalah suatu predicate yang menjadi suatu proposition pada saaat x diberikan suatu kemungkinan nilai. •
Terdapat dua quantifier untuk pernyataan yang menuju ke proposition
baru terdapat (∃x)
beberapa p(x) = true ditulis ∃x p(x), atau ∃x(p(x)), atau (∃x)(p(x))
Existential quantifier untuk semua (∀x)
p(x) = true
Universal quatifier
ditulis ∀x p(x), atau ∀x(p(x)), atau (∀x)(p(x))
• Pertimbangkanlah dua merupakan proposition ?
ekspresi
logika
di
bawah
ini,
apakah
∃x(p(x,y)) ∃x(p(x)) ∧ q(x) •
Terdapat dua jenis skope dari variabel
1.
Bound
2.
Free
• Pertimbangkan dua ekspersi logika di bawah ini, apakah merupakan proposition ? ∀y(∃x(p(x,y))) ∀y (∃x(p(x)) ∧ q(x)) •
Contoh
∀x∀y r(x,y) ↔ ∀y∀x r(x,y) ∀x(~(p(x) ∨ q(x)) ↔ ~p(x) ∧ ~q(x))
a.
i.
Himpunan dan Fungsi
Himpunan
• Suatu himpunan adalah sekumpulan obyek yang terdefinisi dengan jelas • Kumpulan obyek pada suatu himpunan disebut anggota (member) atau elemen (element) • Relasi antara keanggotaan antara satu anggota m dan himpunan S dinyatakan m∈S •
Jika m adalah bukan anggota dari S, dinyatakan
m∉S • Himpunan tampa anggota dikatakan sebagai himpunan kosong dengan notasi ∅ • Himpunan dikatakan sama jika anggota-anggota yang ada pada dua himpunan adalah sama dengan tampa memperhatikan duplikasi yang ada pada anggotanya •
Jumlah elemen pada himpunan S, di notasikan sebagai |S|
• Suatu himpuna dapat diberikan aturan (rule) untuk mengenerate anggota dari suatu himpuna dengan menggunakan suatu Set Builder contoh fruit = {x | x = apple or x = grape or x = orange } •
Union A ∪ B ; A ∪ B = B ∪ A = { x | x ∈ A ∨ x ∈ B }
•
Intersection A ∩ B ; A ∩ B = B ∩ A = { x | x ∈ A ∧ x ∈ B }
•
Difference A - B ; A - B = { x | x ∈ A ∧ x ∉ B }
• Jika semua anggota dari himpuna A menjadi anggota dari himpunan B maka dikatakan A adalah subset dari B dengan notasi A ⊂ B, maka : A ⊂ A ∪ B, A ∩ B ⊂ A, A - B ⊂ A • Cartesian Product dari (A1, A2, .... An), dimana setiap elemen adalah suatu nama himpunan dan n adalah suatu integer, adalah suatu himpuan list-list, ditulis
A1 x A2 x ... x An = {(a1,a2,...an) | a1 ∈ A1 ∧ a2 ∈ A2 ∧ an ∈ An}
ii.
Relasi
• Suatu relasi adalah suatu himpunan yang memiliki anggota (jika ada) dimana semua merupakan pasangan yang berurutan • Pada himpunan, anggota pertama untuk setiap pasang disebut domain dari suatu relasi r dinotasikan dengan D(r) •
Anggota dari D(r) disebut argumen dari r
• Pada himpunan anggota kedua untuk setiap pasang disebut range dari suatu relasi r dinotasikan dengan R(r) •
Anggota dari R(r) disebut nilai dari r
•
Relasi dapat diklasifikasi pada beberapa cara
1. r adalah reflexive jika x ∈ D(r) menunjukan (x,x) ∈ r, dimana, r merupakan relasi “adalah sama seperti” 2. r adalah symmetric jika (x,y) ∈ r menunjukan (y,x) ∈ r, dimana r merupakan relasi “adalah kebalikan dari” 3. r adalah transitive jika (x,y) ∈ r, (y,z) ∈ r menunjukan (x,z) ∈ r, dimana r merupakan relasi “adalah pindahan dari” •
Pertimbangkan untuk contoh dibawah ini
equal
{(x,y) | x = y}
less than
{(x,y) | y < x}
opposite sign
{(x,y) | x * y , 0 }
kita melihat equal adalah suatu reflexive relation ( 7 = 7 adalah true) less than adalah bukan suatu reflexsive relation ( 7 < 7 adalah false)
equal adalah suatu symmetric relation ((2/4 = 1/2) → (1/2 = 2/4)) less than bukan suatu symmetric relation ((2 < 7) → (7 < ) false) less than adalah transitive relation (((2 < x) ∧ ( x < y )) → (2 < y )) opposite sign bukan transitive relation ((3*(-5) < 0) ∧ ((-5)*7<0) → (3*7 < 0) false)
1.2.7 Fungsi
• Suatu fungsi adalah suatu relasi, katakan f , di mana untuk setiap x ∈ D(f) terdapat suatu elemen yang unik (x,y) ∈ f, sering ditulis sebagai y = f(x). • Untuk mendefinisikan suatu fungsi f dengan pemberian domain, D(f) dan suatu rule (aturan) untuk penghitungan nilai korespondensi untuk setiap argumen pada domain • Pertimbangkan contoh di bawah ini f = {(x,y) | x ∈ {0,1}, y = x2+3x+2} di mana (x ∈ {0,1}) merupakan domain dan (y = x2+3x+2) menandai rule (aturan), sehingga dapat memberikan suatu pembilangan dengan bentuk f = {(0,2),(1,6)} • Fungsi dengan “Dummy Variable” adalah sebagai berikut f = {(x,y)|x(x-1)=0, y-x2-3x-2=0} • Jika f dan g adalah fungsi maka {(x,y)|y=f(g(x))} disebut “function composition” dari g dan f, di notasikan sebagai f • g • Suatu fungsi f adalah refleksif disebut “identity function” dimana f(x) = x untuk setiap x ∈ D(F) • Jika pertukaran suatu fungsi f adalah fungsi, maka f t(f(x)= f(f t(x)) = x dan f t dikatakan sebagai “inverse function” dari f • Jika range dari suatu fungsi f adalah hanya berisi 1 elemen maka fungsi tersebut dikatakan sebagai “constant function” • Jika range dari suatu fungsi adalah subset tidak kosong dari {true, false}, disebut suatu “predicate function” contoh p = {(x, true) | x ≥ 0} ∪ {(x,false) | x < 0}
• Predicate function biasa digunakan untuk menyatakan suatu kondisi aturan dengan bentuk (predicate → rule) dengan bentuk sebagai berikut ( p1 → r1 | p2 → r2 | . . . | pn → rn ) contoh f = {(x,y) | x ∈ D, (x dapat dibagi oleh 2 → y = x/2 | x dapat dibagi oleh 3 → y = x/3 | true → y = x }
2.4.4 Recursive Function
• Recursive function (Fungsi Rekursif) adalah suatu didefinisikan dengan menggunakan fungsi itu sendiri
fungsi
yang
• Pertimbangkan oddeven = {(x,y) | (x∈ {0,1} → y = x | x > 1 → y = oddeven(x-2) | x < 0 → oddeven(x+2))}
2.4.5 Digraph
• Suatu relasi g juga disebut digraph. didefinisikan sebagai suatu himpunan dari garis langsung, dimana setiap garis mengkoneksikan suatu anggota dari D(g) ke anggota dari R(g) • Pertimbangkan f = fD-R,D-R = ((x,y) ∈ f | x ∈ (D(f)-R(f)) ∧ y ∈ (D(f) ∩ R(f))}
D
R
2.4.6 State machine
• Suatu state machine adalah suatu fungsi yang memiliki anggota sebagai "ordered pair" dari "ordered pairs", yang dinotasikan sebagai m = {((state,input),(newstate,output))} •
Pertimbangkan
input state
blank
nonblank
excess
excess, λ
nonexecess, input
nonexces s
excess, input
nonexecess, input
nonblank / input
blank / nonblank / input excess
nonexcess blank / input
2.5 List dan String
2.5.1 Struktur List
• Suatu list adalah suatu urutan dari item • Operasi yang dapat dilakukan pada list adalah 1. Menambahkan item baru, a + L 2. Menggabungkan dua List, L + M • Pembangun list +, penambahan suatu item pada head dari suatu list dengan notasi a + ( L + M) • Perhatikan contoh berikut apple:(lettuce,"McIntosh","Winesap") melon:(peach,"Cantaloupe","Honeydew") lettuce:(melon,"Iceberg","Romaine")
maka apple.1.1.2 = "Cantaloupe" apple(2:3) = ("McIntosh","Winesap")
2.5.2 String dan Language
• Bahasa adalah merupakan himpunan dari string • Suatu formal language adalah merupakan himpunan string yang didefinisikan secara ekslusif oleh sekumpulan himpunan operasi dan relasi tampa terdapat suatu bentuk alami • Pertimbangkan D={0,1,2,3,4,5,6,7,9} I = D ∪ ( D x D ) ∪ (D x D x D) ∪ . . . . • Setiap definisi disebut suatu Production • Nama himpunan yang didefinisikan disebut Phrase • Simbol dari bahasa disebut Terminal symbols • Phrase khusus yang “Distinguised phrase”
mendefinisikan
• Language product didefinisikan sebagai A xx B = {x | a ∈ A, b ∈ B, x = a || b} • Yang membedakan antara A x B dan A xx B
• Pertimbangkan jika a∈A∧b∈B
seluruh
bahasa
disebut
maka ( a || b ) ∈ A xx B tetapi ( a || b ) ∉ A x B dan ( a , b ) ∈ A x B tetapi ( a , b ) ∉ A xx B
2.5.3 Formal Grammar
• Notasi yang sering digunakan untuk formal grammar adalah Backus Naur Form (BNF), yang dapat disimpulkan sebagai berikut 1 Operasi Language product dinotasikan dengan "Juxtaposting phrases" 2 "Juxtaposting Phrase" harus dipisahkan dari dirinya sendiri dengan menggunakan tanda bracket (<>), contoh
3 Anggota dari Language Alphabet simbolnya
di notasikan dengan literal
4 Definisi phrase menggunakan notasi ::= contoh ::= 5 Simbol Union (∪) digantikan dengan notasi vertical bar | 6 Jika suatu phrase terdapat dua definisi maka digunakan tanda |, contoh ::= ::= maka ::= | 7. Operasi iterative language dinotasikan dengan memberikan awalan *,+ • Suatu formal grammar dimana setiap definisi dengan bentuk
::= (apapun bentuk ekspresi bahasa) disebut “context free grammar” contoh ::= : <minute> ::= 0 | 1 | 2 <minute> ::= ::= 0|1|2|3 ::= |4|5 ::= |6|7|8|9
• Regular grammar memiliki bentuk ::= x • Sintax Diagram mendefinisi suatu bahasa dalam bentuk diagram contoh
2.5.4 Regular Expression
• Regular expresion adalah bagian sebelah kanan dari suatu production tunggal yang mendefinisikan suatu bahasa dengan operasi concatenation (language product), union, iteration • Notasi dari regular expresion mengijinkan beberapa alternative untuk merepresentasikan bahasa secara identik, yang mana suatu penyederhanaan dibutuhkan, dengan ketentuan +(A)*(A) = *(A)+(A) = +(A) *(A)*(A) = *(A) A*(A) = *(A)A = +(A)
A∅ = ∅A = A *(*(A)) = *(A) A(B|C) = (AB)|(AC), (B|C)A = (BA)|(CA) A(BC) = (AB)C +(A)| ∅ = *(A)
• Implementasi regular digambarkan sbb
A
B
ekspression
dalam
AB
A A|0
A B A A B A • Pertimbangkan
A|B
*(A)
+(A)
A+(A|B)
pemgograman
dapat
A B
A
A
p
q
q
C
A
((BA)|(CA))(+(A)|∅) = ((BA|(CA))*(A) = ((B|C)A)*(A) = (B|C)(A*(A)) = (B|C)+(A)
B A
p
C
q
BAB III ELEMEN-ELEMEN EKSPRESI PROGRAM
3.1. Overview
• Pembahasan pada bagian ini adalah untuk mengenalkan bentuk bahasa untuk pembuatan ekspersi yang tepat dan ringkas pada perancangan program • Bentuk bahasa tersebut dibedakan ke dalam outer syntax dan Inner syntax • Outer syntax membahas tentang struktur kontrol dan struktur data dan struktur modul •
Inner syntax membahas operasi-operasi dan test terhadap data
3.2. Process Design Language
3.2.1. Ide dari PDL
• Dengan adanya pengembangan dan evolusi terhadap perangkat lunak maka diperlukan sesuatu yang dapat digunakan untuk menjelaskan tentang rancangan suatu program • Bahasa pemograma tidak baik digunakan untuk mendeskripsikan suatu program, hal ini disebabkan karena suatu bahasa pemograman memberikan bentuk deskripsi yang ter-spesialisasi • PDL adalah suatu bentuk khusus akhir yang terbuka dari bahasa alami dan matematika
• PDL dapat memberikan deskripsi dari sisi logika hingga bentuk akhir pada media penyimpanan datanya
3.2.2
Outer Syntax dan Inner Syntax pada PDL
• Outer Syntax menjelaskan bagaimana operasi-operasi diberlakukan dan dikontrol, bagaimana data di-organisasikan, diakses dan di‘assign’, dan bagaimana program-program didefinisikan dan diorganisasikan ke dalam modul • Inner Syntax dari PDL menjelaskan tentang tipe data dan operasioperasi •
Struktur kontrol Outer Syntax pada PDL adalah
1. Sequence Structure (Struktur Urut) - Sequence (urut) - Indexed sequence (For do) 2. Alternation Structure (Struktur Alternasi) - IfThenElse - IfThen - Indexed Alternation (Case) 3. Iteration Strukture (Struktur Pengulangan) - WhileDo - DoUntil - DoWhileDo •
Data digolongkan
1. Data yang dinamai
- Scalar - Array - Record 2. Data yang tidak dikenal, diorganisasikan - Sequence - Queue - Stack - Set • Tiga level organisasi dalam struktur pada Outer Syntax Procedure, Modul
: Job,
• Job menjelaskan level tertinggi dari pengeksekusian program dimana dalam pengeksekusiannya melibatkan faktor-faktor dari luar seperti operator, waktu, dll • Procedure merupakan unit yang dapat dieksekusi pada suatu program tampa dipengaruhi oleh faktor luar • Modul adalah system unit, dimana beberapa procedure diorganisasikan untuk dipanggil oleh user (Job lain atau procedure lain) dengan mengakses suatu himpunan data yang ada • Suatu Procedure memberikan aturan (rule) untuk suatu fungsi (function) •
Suatu Modul memberikan suatu aturan untuk suatu state machine
3.2.3. Data Assignment pada PDL
• Penulisan Data assignment dengan menggunakan notasi ":=", contoh x:=y+z, dengan arti x diberikan nilai dari y + z •
Sisi kiri terdiri dari satu nama data single
•
Sisi kanan adalah suatu ekspresi pada nama-nama data
• Suatu Multiple (Concurent) assignment dinotasikan dengan suatu list nama pada sisi kiri dan suatu list ekspresi pada sisi kanan, contoh •
x,y,z := x+y, min(x,z), abs(x-y)
• dimana artinya adalah menghitung semua nilai pada sisi kanan dan memberikan nilai secara simultan untuk nama data pada sisi kiri
3.3. Struktur Kontrol Outer Syntax
3.3.1. Sequence Structure (Struktur Urut)
• Operasi pada stuktur urut adalah pengoperasian serangkaian operasi secara urut, secara umum dapat digambarkan sebagai berikut
firstpart Secondpart
... firstpart secondpart
nthpart
... nthpart ...
• Pada PDL operasi-operasi dispesifikasikan dengan pernyataan bahasa alami dan outer syntax symbol (;) memberikan pemisah antara bagian yang satu dengan bagian yang lain • Pada PDL biasanya untuk suatu struktur urut digunakan syntax do dan od, contoh ... do sort transaction file; update inventory file with transcation; od print inventory report; ...
•
Penempatan Do dan Od adalah untuk menstrukturkan perancangan
• Indexed Sequence atau fordo pada struktur kontrol adalah bentuk yang memilik notasi sebagai berikut
Index list dicapai
T
F
...
Assing anngota berikut ke list
for indexlist
Dopart
do dopart od ...
dimana indexlist adalah suatu ekspresi inner syntax yang mendefinisikan baik variabel index dan suatu list yang memiliki nilai untuk dicapai dopart adalah bagian yang dieksekusi secara urut
•
Pertimbangkan
...
...
for
j:=table(1)+table(2)
i:∈1 to 20 by 2 do
print j j:=table(3)+table(4)
j:=table(i)+table(i+1)
print j
print j
...
od
j:=table(19)+table(20)
...
print j ...
3.3.2. Alternation Structures (Struktur Alternatif)
•
Bentuk untuk dari ifthenelse
...
F
iftest
T
if iftest then thenpart else elsepart fi
Elsepart
thenpart
... • iftest mengevaluasi terhadap inner syntax untuk mendapatkan nilai true atau false, contoh ... if data requested is current status then search online personel file else search archive personal file fi ... • Struktur ifthen adalah bentuk khusus dari ifthenelse dimana untuk iftest dengan hasil evaluasi false tidak diberikan operasi. Bentuk umum untuk ini adalah
F
iftest
T
... if
thenpart iftest
then thenpart fi ...
contoh
...
if inventory transactions available then update inventory file fi ... • Struktur Indexed Alternation adalah suatu multibranch control structure dengan bentuk umum sbb ... case casetest
casetest (Caselist 1)
(Caselist 2)
(Caselist n)
part(caselist1) casepart1 part(caselist2) casepart2 ... part(caselist n) casepartn else elseapart esac ... • ...
contoh
casepart1 casepart1 casepartn
elsepart
case op part('add') add personel record part('delete') delete personel record part('modify') modify personel record part('display for salary','display for tenure') display personel record else display 'operation incorrec specified' esac ...
3.3.3. Iteration Structure (Struktur berulang)
•
Bentuk umum struktur whiledo adalah sbb
...
dopart
while whiletest do
whiletest
T
dopart od
F
...
dimana dopart akan dieksekusi selama whiletest akan menghasilakn nilai true, contoh
... while pay updates remain do retrieve next pay update record update corresponding record in master pay file od ...
•
Bentuk umum dari dountil
... do
dopart
dopart until untiltest
untiltest
F
T
od ...
dimana dopart akan dieksekusi selama untiltest akan menghasilkan nilai false, contoh ... do retrieve next pay update update corresponginh in master pay file until no pay updates aremain od ...
•
Bentuk umum dari struktur dowhiledo
...
dopart1
dopart2
do1 dopart1 while whiletest do2 dopart2 od ...
•
contoh
... do1 calculate error in value while error>tolerance do2 calculate new value od ...
whiletest F
T
3.3.4 Comment
•
Comment pada PDL dituliskan dengan menggunakan Bracket '[]'
•
contoh
...
[set x to min(a,b,c)] if a
• Struktur kontrol PDL adalah struktur 'one-entri one-exit' yang dapat digunakan untuk memperluas operasi secara individu kedalam detaildetail yang lebih detail •
Contoh satu bentuk awal dari suatu bagian PDL adalah sbb
... do if necessary, compute tax payment or refund for next record from tax file until all tax record processed
od ...
•
perluasan dari PDL di atas didapatkan
... do [if necessary compute tax payment or refund for next record from tax file] read next record from tax file if tax due not equal to withholding then if tax due greater than withholding then compute tax payment fi fi until all tax record processed od ...
• Pada dasarnya penguraian dari struktur PDL adalah dengan melakukan perluasan yang pada akhirnya akan hirarki yang unik •
Cara yang dapat dilakukan untuk ini adalah dengan penomoran dan
penggambaran struktur hirarki dengan diagram pohon Sequence
ifthenelse
whiledo
dountil
...
m.1 if
m.1 while
m.1 do
m.1 firstpart
m.2
m.2 secondpart
m.3 then
3 do
3 until
4
4
...
m.4 thenpart
m.n nth part
m.5 else
...
m.6
iftest
2
whiletest
dopart
5 od
elsepart
m.7 fi
•
contoh ...
m.1
do [if necessary compute tax payment or refund for next record from tax file]
2.1
read next record from tax file
2.1
if
2
tax due not equal to withholding
3
then
4.1 2 3 4 5
if tax due greater than withholding then compute tax payment else
2
dopart
untiltest
5 od
6
compute tax refund
7
fi
5 3
fi until
4 5
all tax record processed od ...
• pada beberapa PDL struktur kontrol dapat didiagramkan sebagai suatu pohon untuk menggambarkan penguraiannya dengan menggunakan aturan sbb
SEQ
FDO
firstpart secondpart ... nthpart
indexlist
IT
ITE
dopart
iftest thenpart
iftest thenpart
WDO
CASE
whiletest dopart
casetest (caselistn)
elsepart
(caselist1)
casepart1 casepartn elsepart
(caselist2) casepart2
DOU
DWDO
dopart untiltest
dopart1 whiletest dopart2
3.4 Outter Syntax Data Structure
1 Struktur Data Bernama
• sekumpulan daria dan fungsi aksesnya pada beberapa struktur data khusus dari data yang bernama dan anonimous data •
Scalar, Scalar adalah struktur data yang terdiri dari satu data tunggal
dengan tampa substruktur yang dapat diakses •
Deklarasi pada PDL adalah sbb
... scalar x,y,z ...
• Array, Array adalah suatu list dari struktur PDL yang diindeks oleh suatu cartesian product dari indeks-indeks. contoh
x(1, 1) x(1, 2) ...
x(1, n)
x(2, 1) x(2, 2) ...
x(2, n)
x(3, 1) x(2, 2) ...
x(3, n)
... x(m, 1)
... x(m, 2)
... ...
... x(m, n)
dimana index yang ada adalah cartesian product dari : {1,2,...,m} x {1,2,...,n} •
Pendeklarasian pada PDL dilakukan dengan cara sbb
... array a(3),b(2,4),c(3,2,4) ... •
Elemen-elemen pada array memiliki tipe data yang sama
• Record, Record adalah suatu struktur direpresentasikan oleh suatu tree seperti student = (name,address, class) address = (street, city, state)
data
yang
dapat
•
Suatu anggota adalah node pada suatu pohon
•
Suatu field adalah anggota yang tidak memiliki turunan
3.4.2 Struktur dari Anonimous Data
• Struktur data dapat dimodifikasi dimana dalam mengakses datanya dilakukan tampa satu data individu •
Empat bentuk ini adalah : sequence,stack,queue,set
•
List Builder :
+ dan ⊕
a + b : menambah anggota a di depan list b a ⊕ b : menambah anggota b di belakang list a
•
List Breaker : H+T+, H-T-
H+(a+b) = a T+(a+b) = b H-(a⊕b) = b T-(a⊕b) = a
•
Pertimbangkan list a = (A B C), b = (E F), maka
M + a = (M A B C) b ⊕ N = (E F N) H+(a) = A T+(b) = (F) H-(b) = F
T-(a) = (A B) • Stack, Suack adalah suatu struktur data yang memberikan akses LIFO (Least In First Out) terhadap anggotanya, dengan keyword top
Operasi
Definisi List
c:=top(a)
c,a := H(a),T(a) (a≠0)
top(a) := d
d,a := d,d+a
a := empty
a := ∅
•
contoh pada PDL ...
1 stack a 2 scalar b,c 3 top(a):= b 4 c:= top(a) ... • Queue, Queue adalah struktur data yang memberikan akses FIFO terhadap anggotanya, dengan keyword end
Operasi
Definisi List
c:=end(a)
c,a := H(a),T(a) (a≠0)
end(a) := d
d,a := d,d ⊕ a
a:=empty
•
a := ∅
contoh pada PDL ...
1 queue a 2 scalar b,c 3 end(a):= b 4 c := end(a) ... • Set, Set adalah struktur data yang memberikan akses secara acak terhadap anggotanya, dengan keyword member Operasi
Definisi List
c:=member(a)
c,a := H(a),T(a) (a≠0)
member(a) := d
d,a := d,P(d + a)
a:=empty
a:=∅
•
contoh pada PDL ...
1
set a
2
scalar b,c
3
b:=member(a)
4
member(a):=c ...
• Sequence, Sequence adalah struktur data yang memberikan akses terhadap anggotanya dengan menggunakan pointer dengan menggunakan keyword current, next, reset • Diberikan suatu sequence dengan nama a, list pertama dan kedua dinotasikan dengan a+ dan a- jadi a dinotasikan dengan a = a-.a+, contoh (A B C D E F G) dan pointer berada di antara C dan D, maka dapat dituliskan a = (A B C).(D E F G) dimana a- = (A B C) dan a+ = (D E F G)
pertimbangkan a- = (A) || (B C) a+ = D + (E F G) a = (A) || (B C) . D + (E E G) •
Keyword untuk sequence adalah current dan next dimana
current(a) = H-(a-) next(a) = H+(a+)
Operasi
Definisi List
reset(a)
a:=∅.a-||a+
c:=current(a)
c.a:=H-(a-),a
current(a):=d
d.a:=d.T-(a-)⊕d.a+
c:=next(a)
c.a:=H(a+),a-⊕H(a+).T(a+)
next(a) := d
d.a:=d,a-⊕d.∅
a:=empty
a:=a-.∅
•
Contoh pada PDL
... 1 sequence input,output 2 c:=next(input) 3 next(output) := d
(a-≠∅)
(a+ ≠ ∅)
...
3.4.3 Perluasan dari Sequence
Definisi List
Operasi backspace(a)
a := T-(a-).H-(a-)+a+ (a- ≠ ∅) c,a := H-(a-), T-(a-).H-(a-)+a- (a-≠ ∅)
c := back(a) addaftercurrent(a) := d
d,a := d, a- ⊕ d.a+
c := readanddeletenext(a) c,a := H(a+), a-.T(a+) (a+≠ ∅) c := mid(a)
c,a := H-(a-), T-(a-).a+ (a-≠ ∅)
mid(a) := d
d,a := d,(T-(a-) ⊕ d) ⊕ H- (a-).a+
3.4.4
Perluasan dari Set
Operasi
Definisi List
d := value(a, c)
a, c, d := a, c, x1 (a ≠ ∅)
value(a, c) := d
a, c, d := x2, c, d
c := argument(a, d)
a, c, d := a, x3, d (a ≠ ∅)
argument(a, d) := c
a, c, d := x4, c, d
b := domain(a) b := range(a) c ∈ domain(a) d ∈ range(a)
a, b := a, domain(a) a, b := a, range(a) c ∈ domain(a) d ∈ range(a)
delete(a,c,d)
hapus pasangan (c, d) dari a jika ada
dimana x1 ∈ {x | (c, x) ∈ a} x2 ∈ P((c, d) + a) x3 ∈ {x | (x, d ) ∈ a} x4 ∈ P((c, d) + a)
3.4.5 Data Space
•
Data Space ruang dimana suatu data di alokasikan
•
Keyword untuk menspesifikasikan, digunakan intial dan free
•
Pertimbangkan apabila S adalah Data Space maka
Initial name := value
Free name
Jika name adalah satu anggota S, value diletakan pada stack; kalau tidak tambahkan name ke dalam S dan value sebagai nilainya
Jika name adalah satu anggota S, hapus anggota teratas dalam S, dan jika akibat ini S kosong maka hapus name dari S; kalau bukan maka gagal (dalam pelaksanaan)
•
Contoh
Assumsikan telah aktif S : (x : (‘ab’), z: (8,1)) scalar y
S : (x : (‘ab’), z: (8,1))
y := z
S : (x : (‘ab’), y: (8), z: (8,1))
initial y := 3
S : (x : (‘ab’), y: (8,3), z: (8,1))
y := z
S : (x : (‘ab’), y: (8,8), z: (8,1))
free z
S : (x : (‘ab’), y: (8,8), z: (1))
initial x := ‘cd’
S : (x : (‘cd’, ‘ab’), y: (8,8), z: (1))
free z
S : (x : (‘cd’, ‘ab’), y: (8,8))
initial z := 0
S : (x : (‘cd’, ‘ab’), y: (8,8), z: (0))
• untuk mencek keaktifan dari suatu item data digunakan keyword active dengan menberikan nilai true jika item data tersebut aktif dan false jika tidak aktif, contoh active(a ∨ ( b ∧ c ) ∨ ( ~ d))
3.5 Struktur Sistem Outer Syntax
3.5.1 Job dan Procedure
• PDL procedure adalah program yang disimpan untuk pemanggilan oleh program lain • Procedure berhubugan dengan program-program yang disimpan pada system library untuk pengeksekusian di bawah sistem operasi •
Procedure pada PDL didefinisikan diantara keyword proc dan corp
• Procedure dipanggil oleh program atau procedure lain dengan menggunakan keyword run
•
Contoh
job printreverse queue inqueue,outqueue run reverse boj
proc reverse stack a a := empty outqueue:=empty while inqueue ≠ empty do top(a) := end(inqueue) od while a ≠ empty do end(outqueue) := top(a) od corp
• Passed data adalah data yang dikirimkan ke sebuah procedure melalui parameternya •
Local data adalah data yang dideklarasikan pada atau untuk
procedure itu sendiri • Data yang lewatkan dari dan ke suatu job disebut external data, sementara itu data lainnya dikatakan sebagai internal data •
contoh
job printreverse(inqueuemoutqueue) queue inqueue,outqueue run reverse(inqueue,outqueue) boj • Data yang dilewatkan ke atau dari suatu procedure dan external data ke atau dari suatu job dapat dikarakteristikan sebagai alterable data atau fixed data, dimana alterable data adalah data yang dapat dirubah dan fixed data adalah data yang tidak dapat dirubah •
Contoh
Job oddeven(in,out) sequence in,out run oddeven(alt out, fix in) boj
proc oddeven(alt output, fix input) sequence input, output scalar x while input ≠ empty do x:=next(input)
if x>0 then run positive(alt x) else run nonpositive(alt x) fi netx(output) := x od corp
proc positive(alt x) scalar x while x>1 do x := x - 1 od corp
proc nonpositive(alt x) scalar x while
x<0 do x := x + 1 od corp
3.5.2 System dan Modul
• Suatu cara yang baik dalam pengembangan sistem adalah dengan mengorganisasikan sistem kedalam unit-unit yang terdiri dari sekumpulan program-program, himpunan data dan sejumlah modul yang mendukung sistem • Pembentukan ini pada PDL dideklarasikan dengan menggunakan keyword mod, dom, programs, datasets, modules, dengan bentuk umum :
mod name programs program name list datasets data name list modules module name list dom • contoh
mod masstorage programs getdata, putdata, recoverspace ...
datasets textfiles, archives, checkpoint ... modules directoryservice ... dom
• Pembentukan di atas pada akhirnya akan membentuk suatu abstraksi (data abstraction)
3.6 Inner Syntax
3.6.1 Inner syntax Expression
• Tujuan dari inner syntax pada PDL adalah untuk membentuk data yang flexibel, sederhana, operasi yang dikenakan dan test pada perancangan program • Operasi-operasi terhadap data digambarkan dari arimetika, logic, dan pemrosesan karakter dan obyek data ditemukan pada bahasa pemograman tingkat tinggi seperti charakter string, numeral, dan nilai logical • Assignment pada PDL harus menspesifikasikan suatu ekspresi data yang memiliki proses evaluasi suatu nilai terhadap data untuk penugasan pada suatu identifier tujuan yang telah sipesifikasi •
Contoh
Operasi-operasi Arimetika a:=a-2 a:=(2*b) - (c+2*a)/factor
b:=b! c:=int(c)
Operasi-operasi String c:=concate(a,b) c:=a||b c:=substring(a,x,y) x:=index(a,b)
3.6.2
Tipe-tipe Data
• Suatu tipe data adalah suatu himpunan obyek yang di-assosiasikan suatu himpunan operasi, suatu himpunan test, dan himpunan simbol • Suatu spesifikasi tipe data pada PDL dituliskan dengan keyword type, dimana dalam pendefinisiannya juga dituliskan nama dengan tabel operasi dan test, contoh
type tricolor defined by
tricolor
tricolor
“brighter of”
“brighter than”
red
red
red
false
red
white
white
false
red
blue
red
true
white
red
white
true
white
white
white
false
white
blue
white
true
blue
red
red
false
blue
white
white
false
blue
blue
blue
false
•
Dua jenis type data yaitu
1. enumerates type, contoh type weekday = ( M, Tu, W, Th, F, Sa, Su) 2. Subrange type, contoh type workday = (M .. F) • Inner syntax type assignment dapat diimplementasikan ke dalam struktur data outer syntax sebagai
scalar a,b : integer
•
contoh lain
scalar a:string(50) sequence b,c : string(4) set d : logical stack e : string queue f,g : integer ≥ 0 array h : logical record k : logical, (string, integer)
BAB IV PROGRAM-PROGRAM TERSTRUKTUR
4.1 Overview
•
Pertimbangkan dua buah program dibawah ini
10
INPUT X
20
IF X = 10 THEN GOTO 30 ELSE GOTO 60
30
A=X+1
40
B=A*2
50
GOTO 80
60
A=X*1
70
B=A*3
80
END
BEGIN READ X; IF X = 10 THEN BEGIN A := X + 1; B := A * 2; END
ELSE BEGIN A := X - 1; B := A * 3; END; END.
• Penggunaan GOTO sebagai instruksi untuk mengontrol program pada program yang pertama mengakibatkan kesukaran bagi pembaca dalam menganalisa program • Penggunaan GOTO mengakibatkan penstrukturan program menjadi rumit •
Pemograman terstruktur menghilangkan hal yang demikian
4.2 Eksekusi Program
• Suatu flowchart (Bagan arus) adalah suatu direct graph yang menggambarkan arus dari kontrol eksekusi dari suatu program dan instruksi-instruksi yang di eksekusi • Setiap instruksi dari program berkorespondensi dengan suatu titik (node) pada flowchart •
Setiap kemungkinan kontrol arus berkorespondensi dengan garis
• Jika suatu node instruksi memiliki lebih dari satu garis yang keluar, ini dikatakan sebagai instruksi kontrol (Control Instruction)
• Jika eksekusi dari instruksi kontrol tidak memberikan efek terhadap data yang diterima maka ini disebut ‘pure instruction control’ • Jika suatu node pada flowchart memiliki satu garis tunggal yang masuk dan satu garis tunggal yang keluar disebut ‘function node’
f • Jika suatu node pada flowchart memiliki satu garis tunggal yang masuk dan dua garis yang keluar dan merupakan pure control instruction disebut ‘predicate node’
T
p F • Bentuk lain dari node adalah bentukan yang dikatakan ‘no-op’ node yaitu node yang tidak merubah atau mengevaluasi data, dengan dua garis masukan dan satu garis keluar disebut ‘collecting node’
•
contoh struktur control
g q p h
4.2.2 Proper Program
• Suatu proper program adalah suatu program dengan suatu struktur kontrol yang 1.
memiliki masukan tunggal dan keluaran tunggal
2. untuk setiap node, memiliki satu path (jalur) yang melewati node tersebut dari garis masukan menuju garis keluaran •
Contoh proper program
b a
q
p
c s
t d
• Bagian dari suatu proper program dimana bagian tersebut juga merupakan proper program disebut ‘proper subprogram’
4.2.3 Bagan dan Pohon Eksekusi (E-Chart/E-Tree)
• E-Chart merupakan bagan yang menggambarkan arur eksekusi program yang tertuang pada suatu flowchart • Diberikan suatu flowchart dari proper program , pembangun E-Chartnya dari node-node dan garis-garis dengan beberapa langkah sebagai merikut 1. Mulai E-Chart dengan garis masuk pada flowchart dan adjacent predicate, function, atau collecting node 2. Pada setiap langkah konstruksi, pertimbangkan setiap jalur eksekusi pada pengembangan E-Chart. 3. Pada saat semua jalur eksekusi mencapai terminasi pada garis keluar atau pada titik yang sebelumnya dimunculkan pada jalur, E-Chart selesai • Suatu Execution Tree (E-Tree) dari suatu flowchart program adalah suatu pohon yang memilki jalur (path) dari semua kemungkinan urutan eksekusi tanpa terdapat retracking • Pada E-Tree menjadi finite E-Tree apabila tidak terdapat suatu bentuk struktut pengulangan, sebaliknya akan terjadi suatu Infinite E-Tree jika terdapat suatu struktur pengulangan
•
Pertimbangkan
g f 1
p
2
f 1
2
p
2
g q
q
1
f f
p
g q
p
f g q
p
g q
4.3 Fungsi-fungsi program
4.3.1 Data Assigment
• Pernyataan assingment dapat dilihat sebagai suatu program pada sisi kanan yang mentransformasikan suatu initial data state menjadi suatu final data state dengan suatu cara yang spesifik • Pada level kompilasi dan mesin, suatu pernyataan assignment dapat gagal dalam pengeksekusiannya dengan berbagai alasan:
1. type yang tidak kompatibel 2. Pembagian dengan Nol 3. Struktur data yang tidak kompatibel • Suatu pernyataan assignment sebagai nama dari suatu fungsi yang mendefinisikan suatu state transition untuk semua data yang diketahui dalam program • Domain dari fungsi berkorespondensi ke initial data state yang ditransformasikan oleh pernyataan assignment menjadi suatu final data state, contoh, pada suatu program dengan data space x, y, z pernyataan
x := max(y , z)
berkorespondensi ke suatu fungsi assignment, yang merupakan suatu himpunan dari ordered pair dengan bentuk
max = {((y , z), (u))|( y ≥ z ∧ u = y ) ∨ ( z ≥ y ∧ u = z )}
atau dapat ditulis secara sederhana dengan sehingga bentuk dapat dinyatakan dengan
( x := max( y , z )) ={((x , y , z),( max( y , z ), y , z))}
4.3.2 Efek-efek program pada data
• Suatu eksekusi dari suatu program dapat berakhir pada E-tree dan kemungkinan setiap eksekusi akan mencapai akhir (terminate), walaupun
E-tree adalah suatu infinete
• Pertimbangkan, untuk setiap initial data state X yang mana mencapai akhir eksekusi, suatu final data state Y terdefinisi, nilai Y unik, diberikan dari X, maka himpunan ‘ordered pair’ {( X , Y )} didefinisikan adalah suatu fungsi, hal ini dikatakan sebagai ‘program function’ • Diberikan suatu proper program dengan nama P, dinotasikan dengan program functionnya oleh [P]
X
Y
P=
f
[P] = {( x , y ) | Y = f(X)} •
Suatu urutan dari dua fungsi
X
P=
Y
g
g = {( X , Y )}, h = {( Y , Z )} [P] = {( X , Z ) | Z = h(g(X))}
Z
h
•
Pertimbangkan Flowchart
f
q
g
p h
•
r
E-Chart untuk gambar di atas adalah
g
Y
f
q h
r N
p
(3)
N
g
Y
h
(4)
r N
•
g
Y
N
Y
(1)
(5)
Fungsi Program yang didapatkan adalah
(1) {(X,Y) | p(X) ∧ q(f(X)) ∧ Y = g(f(X))} (2) {(X,Y) | p(X) ∧ ~q(f(X)) ∧ r(h(f(X))) ∧ Y = g(h(f(X)))} (3) {(X,Y) | p(X) ∧ ~q(f(X)) ∧ ~r(h(f(X))) ∧ Y = h(f(X))} (4) {(X,Y) | ~p(X) ∧ r(h(X)) ∧ Y = g(h(X))}
(2)
(5) {(X,Y) | ~p(X) ∧ ~r(h(X)) ∧ Y = h(X)} • Fungsi program ini dapat didefinisikan juga dengan suatu conditional rule [P] = {(X,Y) | p(X) ∧ q • f(X) ∧ Y = g • f(X) | p(X) ∧ ~q • f(X) ∧ r • h • f(X) → Y = g • h • f(X) | p(X) ∧ ~q • f(X) ∧ ~r • h • f(X) → Y = h • f(X) | ~p(X) ∧ r • h(X) → Y = g • h(X) | ~p(X) ∧ ~r • h(X) → Y = h(X)} •
Pertimbangkan
g2 1
g1
g5 g3
2
p1
p2
3
p3
g4
g2
1
g1
2
g3
1
g5
p1 p3 3
p2 g4
2
3
E-Chart
f1
f2
g2 f3
g1
g3
g5
p1 p3 p2 g4
E-Tree f1 = {(X,Y) | Y = f2 • g1(X)} f2 = {(X,Y) | (p1 • g3(X) → Y = f1 • g2 • g3(X) | ~p1 • g3(X) → Y = f3 • g3(X))} f3 = {(X,Y) | (p2(X) ∧ p3(X) → Y = f3 • g5(X) | p2(X) ∧ ~p3(X) → Y = X | ~p2(X) → Y = f2 • g4(X))} maka [P] = f1 •
Pertimbangkan untuk PDL
[x := x + y ; y := x - y] = {((x, y), ( x + y, x))}
[if x > y then x := y fi] = {((x , y), (min(x, y), y))} = (x := min(x, y))
[while x >0 do x := x - 1 od] = {(x, min(0,x)) = (x := min(0, x))
[while x ≠ 0 do x := x - 1 od] = {(x, 0) | x ≥ 0} = (x ≥ 0 → x := 0)
[do x := x + 1 until x > y od] = {((x , y), (max(x + 1 , y + 1), y))} = (x := max(x + 1, y + 1))
4.3.3 Program Equivalence
• Konsep program equivalence digunakan dalam menyederhanakan suatu program • Jika dua program memiliki E-Tree yang sama maka keduanya dikatakan execution equivalence • Jika memiliki fungsi program yang sama maka dikatakan function equivalence •
Pertimbangkan
g
g p
q p
q
4.4.Struktur-struktur Program
4.4.1 Prime program
• Prime Program adalah suatu proper program yang tidak memiliki proper subprogram yang lebih dari satu Prime
Bukan Prime
• proper program dapat dihitung dari jumlah nodenya diklasifikasikan sebagai prime atau bukan prime program. •
Dari struktur kontrol didapatkan
[f] = f
dan
[g;h] = {(X,Y) | Y = h • g(x)}
[if p then g fi] = {(X,Y) | p(X) ∧ Y = g(X)) or (~p(X) ∧ Y = X)}
[while p do g od] = {(X, Y) | ∃k ≥ 0((∀j, 0 ≤ j < k)(p • gj(X) ∧ ~p • gk(X) ∧ Y = gk(X))}
[do g until p od] = {(X,Y) | ∃k > 0((∀j, 1 ≤ j < k)(~p • gj(X)) ∧ ~p • gk(X) ∧ Y = gk(X))}
[if p then g else h fi] = {(X,Y) | p(X) ∧ Y = g(X)) ∨ (~p(X) ∧ Y = h(X))}
[do g while p do h od] = {(X, Y) | ∃k ≥ 0((∀j, 0 ≤ j < k)(p • g • ( h • g )j(X) ∧ ~p • g• ( h • g )k(X) ∧ Y = g• ( h • g )k(X))}
4.4.2 Compound Structure • Jika suatu function node dari sebuah prime program digantikan oleh prime program yang lain maka suatu proper program baru akan dihasilkan • Suatu compound program menjadi sebuah program dibentuk oleh penempatan titik-titik fungsi dari suatu prime program dengan beberapa prime program • Compound program dapat didefinisikan dalam bentuk ukuran yang tidak tentu tetapi kompleksitas dari program dapat dikurang dengan menggunakan suatu himpunan ‘fixed set of prime’ yang disebut ‘basis set’
• Definisi : Suatu Program yang terstruktur adalah suatu compound program yang disusun dari suatu fixed basis set dari beberapa prime program
4.4.3 Teorema Struktur
• Teorema Struktur : Proper Program apapun adalah function equivalent dengan suatu program yang terstruktur dengan basis set {sequence, ifthenelse, whiledo}, penggunaan fungsi-fungsi dan predikat dari program asli dan assignment-assignment serta test pada satu ‘additional counter’ •
Pertimbangkan titik fungsi
i j
h
maka konstruksi yang baru adalah
i
h
gi =
L := j
• Pengikutan eksekusi fungsi (h), program ini memebrikan nilai j ke suatu nama variabel bari (L) (sebagai “Program Counter”) yang tidak terdapat pada program asli •
Pertimbangkan untuk titik predicate
j i
p k
maka konstruksi yang baru adalah
j gi =
i
p k
•
L := j
L := k
Pertimbangkan flowchart dibawah ini
2
1
1
f
1
3
p f
p 4
Dengan penstrukturan didapatkan bentuk sbb
0
L := 2
g1 =
1
p L := 3
g2 =
2
e
L := 0 L := 0
3
g3 =
q L := 4
g4 =
4
h
L := 1
L := 2
1
p L := 3
L=1 2
e
L := 0 L := 0
L= 2 3 L := 1
L>0
q
L=3
L := 4
4
h
L := 1
L=4
l
4.4.4 Recursi Program-program Terstruktur
• Pemograman dengan cara menerapkan teorema struktur akan mengalami beberapa kendala diantaranya adalah effisiensi dan kejelasan • Suatu bentuk ide yang dilakukan untuk mengurangi hal itu adalah dengan mengelimidasi ‘program counter’ yang dirasa tidak perlu ini, hal disebut ‘recursion structured program’ •
Pertimbangkan flowchart yang dihasilkan dari teorema struktur
L := 2
1
p L := 3
L=1 2
e
L := 0 L := 0
L= 2 3 L := 1
L>0
q
L=3
L := 4
4
h
L=4
l
L := 1
dengan mengeliminasi ‘L := 4’ didapatkan
L := 2
1
p
L=1
L := 3
2
e
L := 0 L := 0
L= 2 3 L := 1
L>0
q
L=3
h
L := 1
l
dengan mengeliminasi ‘L := 3’ didapatkan
L := 2
1
L := 0
p q h
L=1 2
L := 1
e
L := 1
L := 0
L= 2
L>0
l
dengan mengeliminasi ‘L := 2’ didapatkan
e 1
L := 0 L := 0
p q h
L := 1
L=1
l L := 1
L>0
pada akhirnya didapatkan
e p L := 1
L>0
L := 0 L := 0
q h
4.4.5 Penguraian Prime Program
•
Pekerjaan yang dibutuhkan untuk merubah suatu program yang tidak
terstruktur ke dalam bentuk yang terstruktur adalah dengan pengenalan bagian-bagian program tersebut • Hirarki dari prime program yang terbentuk dari compound program dapat di ditemukan dengan suatu ‘prime program parse’ • Suatu langkah penguraian didefinisikan oleh suatu himpunan ‘parse unit’ (unit uraian) yang membentuk suatu fungsi dengan dinotasikan sbb
identifikasi / jumlah node
•
Unit adalah merupakan bentuk dasar dari struktur kontrol
•
Pertimbangkan
a p t k b
l
x
c y d q
i u
r
f
g v
e j s
h w
BAB V PEMBACAAN PROGRAM-PROGRAM TERSTRUKTUR
5.1 Overview
• Suatu program yang terstruktur dalam ukuran yang sebesar apapun dapat dengan mudah dibaca dan dimnegerti denga nsuatu prilaku tertentu yaitu dengan pembacaan dan pengertian terhadap hirari dari prime program dan abstraksinya • Tujuan dari pembacaan prime program dalam untuk menemukan program functionnya
5.2 Dasar-dasar pembacaan
5.2.1 Ide Pembacaan Program
• Pada dasarnya kemampuan dari membaca program secara metode dam akurat adalah merupakan suatu bentuk keahlian dalam pemograman • Pembacaan program merupakan dasar dari ‘modification’ dan ‘validating’ • Terdapat dua alasan umum untuk membaca suatu program 1. Verifikasi bahwa suatu program adalah benar sesuatu dengan diskripsi fungsinya. Verification merupakan ‘Design Review’ 2. Penjelasan dari program function. Menjelaskan suatu program function adalah merupakan Design Discovery
Pendekatan yang dilakukan dalam pembacaan program dengan bentuk dokumentasi yang baik pada umumnya adalah pendekatan ‘Top Down’ Pendekatan yang dilakukan dalam pembacaan program dengan bentuk dokumentasi yang kurang baik pada umumnya adalah pendekatan ‘Bottom Up’ atau ‘Stepwise Abstraction’
5.2.2 Aljabar dari Program Terstruktur
• Apabila terdapat P adalah suatu proper subprogram dari Q, dan Apabila penggantian P digantikan oleh P’ maka Q menghasilkan Q’
[P] = [P’] → [Q] = [Q’]
• Terdapat dua implikasi penting dari axiom tersebut 1. Nilai kebenaran dari proposisi apapun yang melibatkan [Q] dirubah apabila P digantikan oleh P’ 2. Prime program dapat diabstraksikan sebagai function node. Dan function node dapat diperluas menjadi suatu prime program
Pertimbangkan proc r
proc r
proc r
a
while
while
b
p
p
do
do
c
f
corp
od
g
d
od
e
if
corp
q then h else I fi e corp
Pembacaan
Penulisan
Validasi
• Pertimbangkan program berserta abstrakasinya
if x<0 then
y := -x
y := abs(x)
else y := x fi [if x < 0 then y := -x else y := x fi] = [y := abs(x)]
• Aljabar dari suatu program yang terstruktur adalah prinsip dari pembacaan suatu program terstruktur
5.2.3 Pembacaan suatu prime program
• Cara yang dapat dilakukan dalam membaca suatu program adalah dengan memperhatikan Path yang ada pada E-Tree • Yang menjadi obyek dari pembacaan suatu program atau bagiannya adalah untuk mengenali langsung apa yang terjadi • Hasil yang didapatkan adalah suatu bentuk abstraksi yang memberikan kesimpulan dari kemungkinan hasil keluaran program dengan suatu pertimbangan, tidak memperhatikan ‘internal control structure’ dan ‘data operation’ • Contoh pembacaan pada PDL
Sequence
x := x - y y := x + y
Hubungan antara data ini dapat ditulis dengan menggunakan subcript dimana untuk Subcript 0 adalah untuk nilai awal Subcript 1 untuk nilai yang mengikuti assignment Subcript 2 untuk nilai akhir data
contoh dari program di atas
x1 = x0 - y0 y1 = x1 + y0
kemudian
x2 = x1 = x0 - y0 dan y2 = x1 + y0 = (x0 + y0) + y0 = x0
Equivalent Sequence-free program dapat dituliskan [ x := x - y; y := x + y] = [x,y := x - y, x]
Alternation
if x>y then z := y else z := x fi
dinyatakan dalam bentuk
1. Conditional assignment [x > y → x := y | true → z := x ] 2. Abstraksi [if x > y then z := y else z := x fi] = [ z:= min(x , y)]
Iteration
While x>1 Do x := x - 2 Od
Program function [While x > 1 Do x := x - 2 Od] = [x := min(x, Oddeven(x))]
BAB V KEBENARAN PROGRAM
6.1.
Overview
• Pada dasarnya kebenaran dari suatu program terstruktur dibuktikan dengan menggunakan teori fungsi • Kebenaran program pada pembacaan program adalah untuk mengetahui interprestasi dari suatu program • Kebenaran program pada penulisan membentuk program yang benar
program
adalah
untuk
• Kebenaran program pada saat validasi adalah untuk mengetahui apakah program menjalankan fungsi dengan benar • Kebenaran program ditentukan sebagai hubungan antara sebuah program dengan fungsi yang diinginkan, konsep aljabar digunakan untuk mengurangi masalah penentuan kebenaran program compound ke masalah penentuan unsur pokok • Teknik yang dapat digunakan untuk ini adalah Trace Table dan Disjoint Rule
6.2. Verifikasi Program Terstruktur
6.2.1. Kebenaran Verifikasi dalam Pembacaan dan Validasi
• Verifikasi pada saat pembacaan program adalah untuk setiap langkah prime program dan disimpulkan dalam bentuk dari sebuah hipotesa untuk sebuah program function. Contoh
if p then q
f = [if p then g else h fi]
else h fi
• Verifikasi pada saat penulisan program adalah untuk setiap langkah fungsi yang diberikan, dikembangkan ke dalam struktur prime yang sesuai, dan komponen function dan predicate ditentukan dimana hipotesa akan menghasilkan sebuah program function yang identik dengan fungsi yang diberikan
6.2.2. Aljabar Kebenaran Program Terstruktur
• Kebenaran program ditekankan pada 2 hal yaitu
1. Apakah f = [p] ? (Complete Correctness) cenderung menuju pada defenvise programming 2. Apakah f ⊂ [p] ? (Sufficient Correctness) cenderung menuju pada execption processing
• Pertimbangkan untuk program dibawah ini
f = ( x ≥ 0 ∧ y ≥ 0 → x, y := x + y, 0)
P1 = while y > 0 do x, y := x + 1, y - 1 od P2 = while y ≠ 0 do x,y := x + 1, y - 1 od
f = (x ≥ 0 ∧ y ≥ 0 → x, y, z := x + y, 0, z | true → x, y, z = x, y, “error”) P3 = if (x < 0) ∨ (y < 0) then z := “error” else while y > 0 do x, y := x + 1, y - 1 od fi
• Dalam membuktikan complete corectness akan sukar untuk program dengan bentuk compound program. Cara yang dapat dilakukan adakah dengan menghipotesa fungsi-fungsi pokok, Contoh
while x>0∧y>0 do x := x - 1 y := y - 1 od if y>0 then x := -y fi free y
SEQ:SUB
WDO:MAG
x>0∧y>0
IFE:SIGN
SEQ:DECR
y>0
x := x - 1 y := y - 1
Subproff
sub
= [mag;sign;free x]
mag = [while x > 0 ∧ y > 0 do decr od] decr = [x := x - 1; y := y - 1] sign
= [if y > 0 then x := -y fi]
atau
sub
⊂ [mag;sign;free x]
mag ⊂ [while x > 0 ∧ y > 0 do decr od] decr ⊂ [x := x - 1; y := y - 1] sign
⊂ [if y > 0 then x := -y fi]
x := -y
free x
6.3. Kebenaran Program-program Prime
6.3.1. Program Terminasi
• Terminasi pada program yang terbentuk dari bentukan komposisi fungsi tertentu yangtitentukan oleh satu lintasan pada e-chart dengan tampa ada pengulangan amatlah mudah ditentukan dimana dalam evaluasinya [P] adalah f, dan f merupakan komposi fungsi • Terminasi pada program yang mengandung pengulangan amat sukar ditentukan. Hal ini disebabkan adanya suatu keadaan yang tidak dapat diperkirakan untuk mengakhiri suatu program
6.3.2. Iteration Recursion Lemma
• Verifikasi untuk suatu program dengan adanya pengulangan dapat dilakukan dengan merubah program kedalam bentuk recursive p = while p do g od q = if p then q; f fi dimana f berhenti unutk semua argument f dan f adalah program function dari ifthen yang tidak memiliki pengulangan Contoh p = while v > 0 do u,v := u+1,v-1 od dari program tsb didapat f = ( u, v := u+v, 0) oleh karena itu didapatkan
q = if v > 0 then u,v := u+1,v-1; u, v := u+v,0 fi
• Dengan hal tersebut maka (while do)
(f = [while p do g od]) ↔ (term(f,while p do g od) ∧ f = [if p then g; f fi])
(do until)
(f = [do g until p od ]) ↔ (term(f,do g until p od) ∧ f = [g; if ~p then f fi])
(do while do)
(f = [do1 g while p do2 h od]) ↔ (term (f, do1 g while p do2 h od) ∧ f = [g; if p then h; f fi])
6.3.3. Teorema Kebenaran
• Teorema kebenaran hanya menentukan relasi-relasi himpunan apa yang harus diverifikasi unutk membuktikan kebenaran dari suatu program • Teorema Kebenaran menunjukan bahwa suatu sisi dari pertanyaanpertanyaan terminasi semua program-progream terstruktur yang dinyatakan dalam prime-prime sampai pada sebuah predicate yang dapat diverifikasi hanya oleh pengguna metode-metode beralasan yang dibutuhkan oleh program sequence dan ifthen, pembuktian mungkin membutuhkan kesabaran dibanding dengan pengetahuan • Untuk fungsi f dan program p kebenaran ditentukan oleh sebuah kondisi c untuk Complete correctness
( f = [p] (term(f, p) ∧ f = {(x, y) | c(x , y)}
Sufficient corectness
( f ⊂ [p] (term(f, p) ∧ f ⊂ {(x, y) | c(x , y)}
g; h
y = h • g(x)
for I ∈ L(i:n) do g od
y = gL(n) • . . . • gL(1)
if p then g fi
(p(x) → y = g(x) ∧ (~p(x) → y = x)
if p then g else h fi
(p(x) → y = g(x) ∧ (~p(x) → y = h(x))
case p
(p(x) ∈ CL1 → y = g(x) ∧
part (CL1): g
...
...
(p(x) ∈ CLn → y = h(x) ∧
part (Cln): h
(p(x) ∉ (CL1. . .Cln) → y = t(x))
else t esac while p do g od
(p(x) → y = f • g(x) ∧ (~p(x) → y = x)
do g until p od
(p • g(x) → y = g(x) ∧ (~p • g(x) → y = f • g(x))
do1 g while p do2 h od
(p • g(x) → y = f • h • g (x) ∧ (~p • g(x) → y = g(x))
• Contoh p = if p then g fi ditunjukan (f = [p] ↔ (term(f , p) ∧ f = {(x , y) | c( x , y)}) atau
(f ⊂ [p] ↔ (term(f , p) ∧ f = {(x , y) | c(x , y)}) dimana c(x,y) = (p(x) → y = g(x) ∧ (~p(x) → y = x)
6.3.4. Correctness proff syntax
• Pembuktian kebenaran dari prime program membutuhkan suatu bentukkan yang baju dalam penotasiannya. Hal ini dilakukan agar dalam dokumentasi dan komunikasi dapat dilakukan dengan baik. Oleh karena itu dibutuhkan keyword-keyword yang digunakan dalam komunikasi antara lain 1 function : menyatakan atau mengacu pada fungsi yang di-inginkan 2 program : menyatakan atau mengacu pada bagian program 3 proof
: menyatakan atau mengacu pada pembuktian
4 result
: pass, atau fail, suff atau comp
• contoh
c(x,y) = ((p(x) → y = g(x)) ∧ (~p(x) → y = h(x)) karena y = f(x) dalam c(x,y) maka dapat dinayatakan sebagai c(x,f(x)) = ((p(x) → f(x) = g(x)) ∧ (~p(x) → f(x) = h(x)) implikasi berikut p(x) → f(x) = g(x) aturan-aturan kondisi
(p(x) → f(x)) =(p(x) → g(x)) atau lebih sederhana (p → f) =(p → g) hal ini mengarah kepada proof untuk ifthenelse ifthen true (proof(p → f) = (p → g)) ifthen false (proof(~p → f) = (~p → h))
6.4. Teknik-teknik untuk Pembuktian Kebenaran
6.4.1. Trace Table
• Metode ini dengan menggunakan sebuah tabel dimana baris menunjukan hubungan ke setiap bagian program sequence dan kolom menunjukan setiap item data yang diberikan dalam sequence • Contoh x := x + y x := x + y x := x - y
Part
x
y
x := x + y
x1 = x0 + y0
y1 = y0
x := x + y
x2 = x1
y2 = x1 - y1
x := x - y
x3 = x2- y2
y3 = y2
Kemungkainan secara matematis
x3 = x2- y2
y3 = y2
= x1- (x1 - y1)
= x1 - y1
= y1
= x0 + y0 - y0
= y0
= x0
maka didapat x, y := y, x
6.4.2. Disjoint Rule
• Disjoint rule digunakan dalam menjabarkan pertambahan setiap predicate negasi dari semua predicate terdahulu • contoh suatu conditional rule (x > 0 → z := max(x, y) | y > 0 → z := min(x, y)) dapat dinayatakan sebagai (x>0→(x>y →z :=x | true → z :=y) | y>0 → (x 0 → (x > y → z := x | x ≤ 0 → z := y) | x ≤ 0 ∧
y>0 → (x 0 ∧ x > y → z := x | x > 0 ∧ x ≤ y → z := y | x ≥ 0 ∧ y > 0 ∧ x < y → z := x | x ≥ 0 ∧ y > 0 ∧ x ≥ y → z := y ) Predicate terakhir adalah false untuk x,y oleh karena itu (x ≤ 0 ≤ y) ∧ (x ≥ y) dapat dihapus dari disjoint rule. sisa dari rule dapat digambarkan dalam bentuk • Case Structure Trace Table • Contoh ( x ≥ 0 → x := x + y | true → y := y + x) ( y > 0 → y := x - y | true → x := y - x) ( x ≥ 0 → x := x - y | true → y := y - x) dapat dikonversikan ( x ≥ 0 → x := x + y | x < 0 → y := y + x) ( y > 0 → y := x - y | y < 0 → x := y - x) ( x ≥ 0 → x := x - y | x < 0 → y := y - x) terdapat 8 kasus dimana setiap kasus melibatkan trace table
Kasus 1,1,1 Part
Kondisi
x
y
x := x + y
x0 ≥ 0
x1 = x0 + y0
y1 = y0
y := x - y
y1 ≥ 0
x2 = x1
y2 = x1 - y1
x := x - y
x2 ≥ 0
x3 = x2 + y2
y3 = y2
kondisi x0 ≥ 0 ∧ y1 ≥ 0 ∧ x2 ≥ 0 = x0 ≥ 0 ∧ y0 ≥ 0 ∧ x1 ≥ 0 = x0 ≥ 0 ∧ y0 ≥ 0 ∧ x0 +y0 ≥ 0 = x0 ≥ 0 ∧ y0 ≥ 0 assignment x0= x2 - y2
y3 = y2
= x1 - (x1 - y1)
= x1 - y1
= y1
= (x0 + y0) - y0
= y0
= x0
Kasus 1,1,2 Part
Kondisi
x
y
x := x + y
x0 ≥ 0
x1 = x0 + y0
y1 = y0
y := x - y
y1 ≥ 0
x2 = x1
y2 = x1 - y1
y := x - y
x2 < 0
x3 = x2
y3 = y2 - x2
kondisi x0 ≥ 0 ∧ y1 ≥ 0 ∧ x2 < 0 = x0 ≥ 0 ∧ y0 ≥ 0 ∧ x1 < 0 = x0 ≥ 0 ∧ y0 ≥ 0 ∧ x0 + y0 < 0 = false Assigment : Tidak perlu Kasus 1,2,1 Part
Kondisi
x
y
x := x + y
x0 ≥ 0
x1 = x0 + y0
y1 = y0
x := y - x
y1 < 0
x2 = y1 - x1
y2 = y1
x := x - y
x2 ≥ 0
x3 = x2 - y2
y3 = y2
kondisi x0 ≥ 0 ∧ y1 < 0 ∧ x2 ≥ 0 = x0 ≥ 0 ∧ y0 < 0 ∧ y1 - x1 ≥ 0 = x0 ≥ 0 ∧ y0 < 0 ∧ y0 - (x0 + y0) ≥ 0 = x0 ≥ 0 ∧ y0 < 0 ∧ x0 ≤ 0 = x0 = 0 ∧ y0 < 0 assignment x3 = x2 - y2
y3 = y2
= (x1 - y1) - y1
= y1
= -x1
= y0
= - x0 - y0
Kasus 1,2,2 Part
Kondisi
x
y
x := x + y
x0 ≥ 0
x1 = x0 + y0
y1 = y0
x := y - x
y1 < 0
x2 = y1 - x1
y2 = y1
y := y - x
x2 < 0
x3 = x2
y3 = y2 - x2
kondisi x0 ≥ 0 ∧ y1 < 0 ∧ x2 < 0 = x0 ≥ 0 ∧ y0 < 0 ∧ y1 - x1 < 0 = x0 ≥ 0 ∧ y0 < 0 ∧ y0 - (x0 + y0) < 0 = x0 ≥ 0 ∧ y0 < 0 ∧ x0 > 0 = x0 > 0 ∧ y0 < 0 assignment
y3 = y2 - x2
x3 = x2 = y1 - x1
= y1 - (y1 - x1)
= y0 - (x0 + y0)
= x1
= - x0
= x0 + y0
Kasus 2,1,1 Part
Kondisi
x
y
y := y + x
x0 < 0
x1 = x 0
y1 = y0 + x0
y := x - y
y1 ≥ 0
x2 = x1
y2 = x1 - y1
x := x - y
x2 ≥ 0
x3 = x2 - y2
y3 = y2
kondisi x0 < 0 ∧ y1 ≥ 0 ∧ x2 ≥ 0 = x0 < 0 ∧ y0 + x0 ≥ 0 ∧ x1 ≥ 0 = x0 < 0 ∧ y0 + x0 ≥ 0 ∧ x0 ≥ 0 = false assignment tidak perlu
Kasus 2,1,2 Part
Kondisi
x
y
y := y + x
x0 < 0
x1 = x 0
y1 = y0 + x0
y := x - y
y1 ≥ 0
x2 = x1
y2 = x1 - y1
y := y - x
x2 < 0
x3 = x2
y3 = y2 - x2
kondisi x0 < 0 ∧ y1 ≥ 0 ∧ x2 < 0 = x0 < 0 ∧ y0 + x0 ≥ 0 ∧ x1 < 0 = x0 < 0 ∧ y0 + x0 ≥ 0 ∧ x0 < 0
= x0 < 0 ∧ y0 + x0 ≥ 0 assignment x3 = x2
y3 = y2 - x2
= x1
= (x1 - y1) - x1
= x0
= - y1 = - y0 - x0
Kasus 2,2,1 Part
Kondisi
x
y
y := y + x
x0 < 0
x1 = x0
y1 = y0 + x0
x := y - x
y1 < 0
x2 = y1- x1
y2 = y1
x := x - y
x2 ≥ 0
x3 = x2 - y2
y3 = y2
kondisi x0 < 0 ∧ y1 < 0 ∧ x2 ≥ 0 = x0 < 0 ∧ y0 + x0 < 0 ∧ y1 - x1 ≥ 0 = x0 < 0 ∧ y0 + x0 < 0 ∧ y0 + x0 - x0 ≥ 0 = x0 < 0 ∧ y0 + x0 < 0 ∧ y0 ≥ 0 assignment y3 = y2
x3 = x2 - y2 = y1 - x1 - y1
= y1
= - x1
= y0 + x0
= - x0
Kasus 2,2,2 Part
Kondisi
x
y
y := y + x
x0 < 0
x1 = x 0
y1 = y0 + x0
x := y - x
y1 < 0
x2 = y1 - x1
y2 = y1
y := y - x
x2 < 0
x3 = x2
y3 = y2 - x2
kondisi x0 < 0 ∧ y1 < 0 ∧ x2 < 0 = x0 < 0 ∧ y0 + x0 < 0 ∧ y1 - x1 < 0 = x0 < 0 ∧ y0 + x0 < 0 ∧ y0 + x0 - x0 < 0 = x0 < 0 ∧ y0 + x0 < 0 ∧ y0 < 0 = x0 < 0 ∧ y0 < 0 assignment x3 = x2
y3 = y2 - x2
= y1 - x1
= y1 - (y1 - x1)
= y0 + x0 - x0
= x1
= y0
= x0
Maka fungsi yang didapatkan adalah
(x ≥ 0 ∧ y ≥ 0 → x, y := y, x | x = 0 ∧ y < 0 → x, y := - x - y, y | x > 0 ∧ y < 0 → x, y := - x, x + y | x < 0 ∧ x + y ≥ 0 → x, y := x, - x - y | x < 0 ∧ x + y < 0 ∧ y ≥ 0 → x, y := - x, x + y | x < 0 ∧ y < 0 → x, y := y, x )
BAB VII PENULISAN PROGRAM TERSTRUKTUR
7.1. Overview
• Stepwise Refinement adalah merupakan proses perluasan dari fungsifungsi ke dalam bentukan prime program dan fungsi yang lebih sederhana. Pendekatan ini merupakan strategi Top-Down • Pemeriksaaan kebenaran dilakukan dengan “devide, connectm dan check” • Stepwise Reorganization adalah proses yang diberikan terhadap program 7.2. Dasar-dasar penulisan 7.2.1. Penemuan Program Terstruktur
• Penulisan program terstruktur adalah suatu proses mental kreatif yang membutuhkan studi dan latihan untuk profesi. • Pertimbangkan
(x ≥ 0 ∧ y ≥ 0 → x, y := x - y, free)
diasumsikan tidak ada operasi pengurangan dan pengurangan harus digunakan, dalam hal ini dapat diberikan diskripsi verbal sebagai solusi. Kurangkan x dan y dengan 1 sampai salah satu sama dengan 0. Kemudian hasil dari pengurangan, tidak termasuk tandanya, adalah variabel lain : jika y adalah 0, maka x adalah hasilnya tetapi jika x adalah o, maka -y adalah hasil yang dibutuhkan.
• Pertanyaan yang mungkin muncul adalah mental dan displin yang bagaimana yang mengarah pada penyelesaian yang terstruktur. • Penempatan node function dan predicate secara digabungkan ke dalam struktur pengawasan yang teratur
individu,
• Dari penjelasan verbal pada kasus di atas dapat dinyatakan sebagai 3 submasalah: 1. Menghitung inti dari perbedaan antara x dan y 2. Menentukan tanda perbedaan 3. Membebaskan y sehigga PDL yang didapatkan adalah [Menghitung inti dari x - y] while x>0∧y>0 do x, y = x - 1, y - 1 od [Menentukan tanda] if y >0 then x := -y fi free y
7.2.2. Disiplin Pengembangan Fungsi
• Pemograman terstruktur adalah proses penyelesaian masalah manusia yang membentuk struktur logika untuk program-program. • Peralatan dasar untuk pemograman terstruktur ditanamkan dalam fundamental axiom replacement untk program terstruktur, yaitu peletakan kembali fungsi-fungsi oleh program-program prime sebagai dalam perluasan prime PDL
F = g; h F = if p then g else h fi F = while p do g od
7.3. Strategi - Strategi Pemograman
7.3.1. Pemograman dengan Stepwise Refinement
• Perluasan fungsi mengarah ke stepwise refinement pemograman terstruktur, dimulai dengan fungsi yang diinginkan menjadi diprogramkan dan strategi rnacangan, pemrosesan melalui tingkat keberhasilan ekspresi, hingga program sesungguhnya telah dikembangkan dalam detil sufficient • Ide dalam stepwise refinement adalah “devide, connect, and check” • Stepwise refinement adalh suatu proses perekaman dan bukan suatu proses pemikiran.
7.3.2. Top-down Structure Programming
• Stepwise refinement daro program terstruktur besar dibawa keluar oleh penstrukturan segment. • Segment dibatasi oleh Proc dan Corp, dan mungkin saja akan mengacu kepada segment lain yang akan di Run • Proses pembentukan segment dalam pemograman tidak lain adalah merupakan strategi Top-Down Structured Programming • Operasi-operasi data pada subspesification (subfunction)
suatu
segment
ditunjuk
pada
7.3.3. Pemograman dengan Stepwise Organization
• Stepwise refinement dari sebuah rancangan program adalah merekam proses penyelesaian sebauh masalah dibawah pengawasan yang baik, kekomplesan proses rancangan dapat membuat proses menjadi sulit. • Stepwise Organization adalah sebuah strategi pemograman yang menampilkan kebenaran program • Strategi adalah sebagai berikut 1. Stepwise Refinement,Merancang program dengan fungsi benar 2. Stepwise Organization,Melakukan program yang dihasillkan 3.
proses
verifikasi
2
yang
terhadap
Penyertaan Kebenaran Program
4. Modifikasi program dengan mengikuti pola pembuktian kebenaran dalam mengurangi kerumitan program 7.2.3. Penggunaan Verifikasi Program dalam Rancangan Program
• Dikketahui sebuah program SUB yang memiliki rancangan yang dimotivasikan oleh Substraction umum dengan pengurangan, dimana x,y
adalah bilangan bulat
SUB = while y>0 do x ,y := x - 1, y - 1 od
dimana SUB adalah perluasan dari fungsi SUB yang diinginkan
SUB = (x, y := x - y,0)
dari hal di atas apakah 1. SUB = [SUB] (Completeness Correctnes) ? 2. SUB ⊂ [SUB] (Sufficient Correctness) ?
Pembuktian
Function SUB = ( x, y := x- y, 0) Program SUB = while y > 0 do x, y := x - 1, y - 1 od Proff Term
y dikurangi pada setiap iterasi sehingga whiletest y > 0 akan gagal Pass
Whiletest true
Part
Kondisi
x
y
y>0
y0 > 0
x1 = x0
y1 = y0
x, y := x-1,y-1
x2 = x1 - 1
y2 = y1 - 1
x, y := 0
x3 = x2 - y2
y3 =0
kondisi
y0 > 0
= x3 - y2 =x1 - 1 - ( y1 - 1) = x0 < 0 ∧ y0 + x0 < 0 ∧ y0 < 0 = x0 - y0
Program function
(y > 0 → x, y := x-y ,0)
dimana menyetujui SUB untuk whiletest true pass
whiletest false fungsi yang diinginkan adalah x, y := x - y, 0 tetapi program function untuk y ≤ 0 adalah identik x, y := x,y dan (x - y, 0) ≠ (x, y) x = y = 1: (0, 0) ≠ (-1, -1) Fail Result Fail
Pembuktian di atas menyatakan fail karena domain Sub memasukan y < 0, dimana tidak dapat ditangani dengan sendirinyua oleh SUB
